ЗаТелеком 🌐

Про mesh-сети давайте попробую коротко объяснить. Но это сложно, да.

Некоторые товарищи полагают, что mesh-сети это прямо вот панацея от всех болезней, связанных с регулированием интернетов. Типа, полносвязанные одноранговые построения невозможно заблокировать, выключить, фильтровать. Это действительно так. В теории.

Но на практике нужно взять в руки калькулятор и посчитать. Вот сколько гипотетических маршрутов прохождения пакета существует для полносвязанной сети из 2 узлов? Ответ: 1. А для 5? ответ: 5!-1, где (!) — это факториал. Всего, получается, 119 маршуртов. Подсчитать результат для сотни узлов у меня уже кончился калькулятор — 157-значное число. При этом, нам же нужно не просто посчитать произведение сотни чисел — нам нужно построить оптимальный граф прохождения пакета, что увеличивает необходимость рассчетов до сложности двойного факториала.

И эти числа нужно считать на каждом узле для каждого пакета, ибо сеть-то наша еще и динамически изменяется — узлы постоянно перемещаются, выключаются, появляются новые.

Для создания _полного_ и математически решаемого алгоритма функционирования динамической mesh-сети нам нужно решить ни много, ни мало — одну из "задач тысячелетия", которая называется "Равенство классов P и NP" или "проблему перебора". Уровень сложности которой лежит в одной плоскости с гипотезами Римана, Пуанкаре или решение уравнений Навье-Стокса (гугл ит!).

Вот довольно хорошее видео про эту задачу, которое объясняет: https://www.youtube.com/watch?v=aB_6ZsLjzzc

А как же работают mesh-сети сейчас, спросит читатель?

А вот это у меня в пост уже не очень влезет. Коротко:

1. Существующие алгоритмы все для статических сетей, где узлы прибивают гвоздем буквально
2. Все эти алгоритмы базируются на неполном решении и используют "муравьинную логику" (стигмергию)
3. Работают эти алгоритмы, честно говоря, хреновенько. Иначе, все давно бы уже строили сети по mesh-топологии.

Но мы не сдаемся! :)

Например, существуют следующие протоколы для создания и управления mesh-сетями:

1. Better Approach To Mobile Adhoc Networking (B.A.T.M.A.N.) — наиболее проработанный на сегодня протокол с практическими внедрениями.
2. Netsukuku is a project with similar goals
3. Ad hoc On-Demand Distance Vector Routing (AODV)
4. Associativity-Based Routing (ABR)
5. Dynamic Source Routing (DSR)
6. Ad hoc routing protocol (целый список)
7. Mobile ad hoc network (MANET)
8. Wireless ad hoc network
9. Lugro-Mesh
10. JOKER is a B.A.T.M.A.N.-based opportunistic routing protocol for mesh networks
и еще ряд Open Source реализаций той или иной степени эффективности:
10.1 Babel
10.2 BIRD
10.3 OpenBGPD
10.4 OpenOSPFD
10.5 Quagga
10.6 XORP
10.7 Zebra
10.8 Optimized Link State Routing Protocol
10.9 FRRouting

Все это можно загуглить.

Но в конце хочу вот чего еще: каждый год по данной теме проходит целый фестиваль mesh-активистов разной степени упоротости. В большинстве, конечно, это галимые фрики, которые за анархию и прочую партизанщину. Но в рамках фестиваля проходит и соревнования эффективности алгоритмов, что очень круто. Называется Battle Mesh.

В этом году он был в Париже в июле. Я опять профакапил сроки, хотя очень хотел съездить. Ну, на будущий год обязательно съезжу, да.

Вот страничка 12 слёта: https://www.battlemesh.org/BattleMeshV12

Очень рекомендую, да. Особенно тем, кто пытается строить "коммунальные mesh-сети". Там для вас столько материала, что кукуха съедет окончательно. Ну, или просветление придет. Одно из двух.

YouTube

≠ Собирай рюкзак по алгоритму, если будет NP=P

Есть задачи, которые решаются долго, но что значит «долго»? Все зависит от сложности алгоритма — объема работы и входных данных. Что такое задача коммивояжера, как собрать рюкзак в путешествие, и играть в тетрис в режиме Бога. Давайте разбираться вместе с…

11.6K viewsedited 07:51