Бутстреп сети

Сколь нод в совокупности?

Кхм. Двести тысяч. Нет, правда.

Из мыслей есть что... Выбирать случайный адрес в своих подсетях, проверять, есть ли там кто живой, если есть - выходить на связь. Тока вот так как-то. Может еще можно улучшить, делясь соседями.

Но наверняка что-то уже есть.

А задача минимизации трафика и оптимизации топологии, надеюсь, не стоит?

Предлагаю двухуровневую иерархию. 1-й уровень: пусть ноды организуются в кластера по N-штук и внутри себя перекрёстно мониторят. Тут они могут чуть ли не full-mesh сделать, смотри сам.

2-й уровень: каждый кластер имеет k внешних связей до других кластеров.

Такой вариант пойдёт? Если подойдёт то его можно дальше развивать.

Discovery, обычно, делается двумя путями: броадкастами в свою сетку и какая-либо центральная нода.

Я видел алгоритмы перебора адресов — раз ноды в одном ДЦ то и адреса у них близки. Мне это не нравится. Тут как раз парочка-тройка центральных серверов которые собирают список нод сильно облегчает страдания. Т.е. это уже однородный p2p, тут есть ноды которые несут дополнительные функции. Но, имхо, это очень разумно.

Вспомнил. Посмотри wireless sensor network. Там как раз речь о слабеньких сенсорах с ограниченными ресурсами.

Всякое p2p вещание, думаю, не подойдёт т.к. там другие приоритеты (там, скорее, управление трафиком для честного распределения полосы пропускания, минимизация задержек и выявления читеров).

Задача минимизации и оптимизации не стоит к щастью. Хотя релевантной литературы бы хоть краем глаза было бы полезно глянуть.

Вариант, в принципе пойдет. Есть ли чего на эту тему почитать?

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

Я с ходу ничего путного почитать не дам. Ння :) http://scholar.google.com/scholar?q=distributed monitoring Так же вбей «p2p availability monitoring».

Может, ещё чем-то DHT пригодится.

DHT мне там ничем не пригодится, мне нужно в режиме онлайн собирать очень поганую, неудобную для распределенки, статистику по датацентрам. Там и так кассандра кругом. А так - окей, и на том спасибо.

Ботнет делаешь?

Нет, был бы ботнет - я бы статистикой, связностью и датацентрами бы не заморачивался. И какая кассандра в ботнете, ты што.

всё просто. Каждой ноде даёшь номер из N битов. Считаешь метрику как расстояние между узлами(число бит, которые разные). Сохраняешь в каждой ноде список из M соседей. Поиск тривиален, т.к. вся сеть представляет собой узлы N-мерного гиперкуба. Сабж тоже тривиален, т.к. ноде надо найти саму себя.

man Kademlia как пример сети с N=128, M=1000.

200 тыс. нод вроде бы не очень много? Можно при самом первом запуске сходить на какой-то сервер, самодобавиться там и забрать список всех остальных, например. А вот что делать дальше - интересно. Вы планируете протоколировать выпадания узлов? Если да, то где хранить эти логи? В кассандре?

это вы про эрланг?

Да, планирую. Да, в кассандре. Впрочем, уже несущественно. Рабочую тактику придумал, а там посмотрим, потребуются ли улучшения или и так прокатит.

Не очень много? Я не знаю, как-то никогда с таким количеством не сталкивался даже в мыслях.

Какой еще эрланг-херланг?

Какой еще эрланг-херланг?

он же финн...кто финн? (c)

насколько понял суть такова: есть ДЦ, в нём N-тысяч хостов воткнуты в некую сеть. Вам хочется сделать некий распределённый децентрализованный процесс который скажет кто из хостов работает, и подаст тревогу если это число меньше 5% ? из ограничений - центральный узел выделять нельзя и нельзя строить жёсткие иерархии, сеть использовать жалеючи..

интересная задачка, которая вообще-то в лоб решается запросом аппаратуры коммутации, но предположим мы этого неможем :-)

тогда задача сводится к совместному хранению и обновлению подобия arp-таблицы, когда на каждой ноде есть только неполная часть и её надо экономно обновлять..

в первом приближении: нода через какое-то время после загрузки отправляет multicast с частью своей arp-таблицы. Подписанные на группу обновляют свои таблицы. Периодически нода отправляет anycast в группу, подписант аналогично обновляется. Вместо периодического случайного обмена можно организовать «передачу маркера», но это сложный протокол. При обоснованно разумном выборе таймеров и случайных моментов получается гораздо меньшая нагрузка на сеть чем широковещание.

чтоб получить «список живых» надо либо просто подождать пока всё прилетит, либо предусмотреть обмен anycast_запрос -> ответ_отправителю;

если _вдруг_ железо криво поддерживает anycast (например доводит датаграмму не любому_в_группе а ближайшему_в_топологии) то с некоторым гимором он заменяется на много маленьких multicast

Круто. Спасибо за идею низкоуровневого решения.

Вам, наверное, нужно посмотреть в сторону Gossip: http://en.wikipedia.org/wiki/Gossip_protocol

Уже. Это ж «молва» пресловутая.

Не очень много?

Ну, много, конечно, но весь список адресов при необходимости можно хранить на каждой ноде.

Рабочую тактику придумал

А какую, если не секрет?

Мне придумалась такая схема:

- каждая нода как-то получает упорядоченный список соседей. Например, из кассандры, или генерирует в зависимости от своего адреса

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

- если нода обнаруживает что ее мониторят несколько других нод (восстановилась нода/связь) - сообщает мониторящим и протоколирует

Схема простая, наверняка что-то в ней не так. Но что именно не так - как-то сходу не соображу, вроде должно работать

Круто. Спасибо за идею низкоуровневого решения.

конечно пожалуйста, но освежил в памяти - «правильный» anycast это эксперементальная фича, которую пробовали в академических сетях,а в реальное железо не прошла (1-го бита нехватило в ethernet`е), а в ipv6 поддерживается на уровне BGP то есть сильно-сильно сбоку. :-(

то есть придётся вам что-то выдумывать с mulicast группами (которые везде работают правильно). И жестокого тервера будет до едрени фени...

так что проще и продуктивнее опрашивать железо - коммутаторы и так знают кто у них жив, кто нет. Нужная вам информация УЖЕ есть в сети - её надо только забрать