Как оценить общее количество узлов в сети P2P?

Question

Я создаю сеть p2p без главного узла. Как подсчитать общие живые узлы? Точность - это не ключевой, но легкий и эффективный.

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

1. Каждый узел имеет случайное число в качестве идентификатора. Каждый узел имеет огромный бит-массив, изначально только бит в index == ID равен 1 и другим 0. Каждый узел обменивает его бит-массив с известными одноранговыми узлами. Битовый массив узла объединяется со сверстниками, используя бит OR. По ходу этого процесса каждый узел должен иметь аналогичный бит-массив, а число 1 указывает количество узлов в сети. Преимущество состоит в том, что это можно сделать параллельно и по времени. Во время запроса ответ может быть очень быстрым (потому что результат уже существует). Недостатки: а). Трудно обрабатывать узлы, которые ушли. б). Битовый массив слишком велик, если есть миллионы узлов.

2. Что-то вроде BFS. Из исходного узла он запрашивает у всех известных одноранговых узлов, сколько узлов связано. Затем суммируйте все ответы как общий размер тестируемой сети. Это подход рекурсии. Если узел уже получил такой запрос, он будет игнорировать тот же самый запрос от других узлов. Также как BFS. Недостатком является то, что это имеет высокую вероятность быть неточным. Если посмотреть на дерево BFS, для каждого узла это может быть одноточечный сбой, из-за чего весь запрос с этого узла отсутствует. Рассмотрим инициализацию запроса от узла A, запрос подключенных узлов B & C. B & C затем распространите запрос в сеть, к которой они подключаются. По какой-то причине C терпит неудачу и не может ответить на A. Тогда все узлы, получающие прямой или косвенный запрос из C, не будут учитываться. Эта проблема может произойти в любом узле сети и может привести к минимальной неточности или большой неточности, как в вышеупомянутом подходе, вероятно, к 50% сети.

Любая идея, как практически оценить общие узлы в сети P2P?

Answer 1

Нет идеального подхода. Если есть узловая часть критической части, которая является шелушащейся (часто идет вниз и вверх), тогда есть большой шанс, что вы пропустите часть сети из-за этого и не сообщите, насколько велика эта часть. Даже при наличии хорошо подключенной сети сложно дать правильный счет, так как состояние сети может измениться во время работы алгоритма.

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

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

Идея очень похожа, но вместо того, чтобы считать все ваши узлы (ваши идентификаторы должны быть уникальными и довольно последовательными) и очень большой бит-массив, вы можете иметь случайные идентификаторы (каждая машина выбирает случайный 32/64 бит id), а вместо битового массива вы проходите вдоль фильтра цветка и счетчика. Фильтр цветения похож на массив, так как он может сказать, что идентификатор еще не вставлен. Однако это намного больше пространства. Недостатком является то, что, хотя он имеет 100% -ный отзыв (если фильтр говорит, что идентификатор отсутствует, его действительно нет), он не имеет 100% -ной точности (фильтр может сказать, что идентификатор вставлен, но на самом деле он не было). Для алгоритма это означает, что вы обязательно избегаете двойного счета (хорошего), но в зависимости от порядка вставки вы можете пропустить некоторые узлы.

Остальная часть алгоритма такая же. Начните с ввода своего идентификатора и установите счетчик 1. Отправьте состояние всем одноранговым узлам.Когда вы получаете состояние, проверьте, был ли ваш идентификатор уже вставлен и если он не вставлен, добавьте 1 и отправьте состояние всем своим сверстникам. Если у вас одинаковое состояние фильтра цветения с разными значениями, выберите большую (поскольку мы уверены, что нет двойного счета). В конце концов государства сходятся, и это ваш ответ.

Here's ссылка на то, как работает фильтр цветения.

Answer 2

Если у вас есть DHT или аналогичная сеть наложения (что вы, вероятно, делаете, как еще вы собираетесь иметь чисто распределенную сеть?), Вы можете оценить ее размер, посмотрев на распределение идентификаторов в небольшом суб- пространство идентификационного пространства. Ваши подходы в основном стараются быть точными, поэтому они оказываются непрактичными. Если посмотреть только на часть идентификационного пространства и сделать выводы об остальной части, это явно неточно в целом, оно работает только в том случае, если идентификаторы случайны, и если вы знаете о достаточном количестве узлов, которые вы можете вызвать закон больших чисел. Если вы сохраните соответствующие таблицы маршрутизации, вы можете сделать эту оценку чисто локально, но если ваши запросы позволяют это, вы можете решить, чтобы узлы были близки к некоторому произвольно сгенерированному идентификатору, и теперь у вас есть две оценки, которые вы можете усреднить (но это дорогой трюк) , Есть много статей о том, как сделать это более устойчивым к определенным атакам, более точным в случае высокого оттока и с фактическими формулами для оценки.