Собственно, думаю, как грамотно побороть сабж. Ситуация такая:

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

Серверу приходит пакет, содержащий IP нового клиента. Сервер должен добавить этот IP в список клиентов и переслать этот IP всем серверам в сети (естественно, кроме того, который прислал ему этот пакет).

Получается проблема "снежного кома": уже на втором шаге на наш сервер может еще раз придти пакет с этим-же IP (от третьего сервера, например). Это не проблема: сохраняем пул обработанных запросов и если этот пакет уже был отправлен остальным серверам — просто ничего не делаем.

Проблема в другом: кол-во гоняемых по сети пакетов. По первым прикидках из расчета 10 серверов получаем максимальное кол-во гоняемых туда/сюда пакетов около 80 (!).

Вопрос: что можно сделать, чтобы существенно сократить кол-во пересылаемых пакетов с учетом необходимости иметь на каждом сервере актуальный список клиентов? Сеть одноранговая и главного сервера нет, т.е. нет централизованной обработки пула клиентов.

Как быть?

З.Ы. Пакеты маленькие и очень нежелательно их раздувать за счет включения в них маршрута прохождения пакета.
З.З.Ы. Протокол — TCP. UDP не предлагать — задача стоит именно на TCP.

Здравствуйте, Аноним, Вы писали:

А>Как быть?

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

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

как вариант, из всех, кто online, можно устроить "выборы" мастера и всё делать через него.

ЗЫ а почему не UDP? broadcast как раз для этих целей.

> Серверу приходит пакет, содержащий IP нового клиента. Сервер должен
> добавить этот IP в список клиентов и переслать этот IP всем серверам в
> сети (естественно, кроме того, который прислал ему этот пакет).

Если не широковещятельные пакеты (как одно из требований), то как ентот
первый покет от нового узла найдёт хоть один компьютер сети? Если только
не принудительно сказать.

Что же до рассылки — если броадкаст неприемлем — так пусть тот сервер
который получил пакет нового узла и пошлёт его всем остальным узлам (если
я правильно понял у него, как и у каждого узла сети, есть информация
обовсех серверах) с командой — "Зарегестрировать новый узел XXXXX"

Здравствуйте, PK Sly, Вы писали:

PS>то есть, в любой момент времени все клиенты знают обо всех?
PS>Тогда пускай вновь подключаемому сообщается список всех остальных, а он им всем говорит о себе. сам.

Как вариант, кстати. Спасибо. Только давайте сразу введем постулат: сервер — это и клиент одновременно (P2P, я уже упоминал ). Так что по первым прикидкам придется немного усложнять алгоритм — если я все правильно понял, то подключаемый сервер в ответ на отсыл им IP клиента получает список серверов, который есть у сервера, к которому подключились? И, соответственно, продолжает рассылку этого IP клиента всем остальным серверам до тех пор, пока не исчерпается список.

Тогда рассмотрим другой вариант: пусть я — сервер А. Первое подключение идет к серверу B (не имеющему адресов других серверов сети). Примем постулат: я хочу синхронизировать список серверов так, чтобы у каждого сервера из приведенных в пример четырех (А, B, C, D) имелись адреса других 3-х серверов.

Я имею (сервер А) адреса серверов В и С. Я соединяюсь с сервером B, затем c сервером С (имеет адрес сервера D). Сервер B после этого будет знать мой адрес (сервера А) и адрес сервера С (я ему его сообщил). У сервера B в списке больше нет адресов других серверов (добавлять в мой список для обработки нечего). Далее я подключаюсь к серверу С, сообщая ему свой адрес и адрес сервера B. Он мне возвращает адрес сервера D. С сервером D ведется аналогичная работа — сообщение ему списка известных мне серверов (к данному шагу это A (я сам), B и С). Но сервер B, подключение к которому я уже обработал, не будет знать о сервере D ровным счетом ничего, т.к. на момент работы с ним я сам еще не знал о существовании сервера D. Добавлять в pending list для отсылки адрес сервера D? Но я не сохраняю информацию о тех серверах (слишком большой overhead), у кого уже есть адрес сервера D. Как следствие — имеем N overhead-пакетов, которые будут отправлены впустую... Этого хочется избежать.

PS>как вариант, из всех, кто online, можно устроить "выборы" мастера и всё делать через него.

Это сложнее, т.к. сильно увеличивает нагрузку на "мастер"-сервер. А это может быть и достаточно слабая клиентская машина.

PS>ЗЫ а почему не UDP? broadcast как раз для этих целей.

Партия сказала — надо TCP

Здравствуйте, Аноним, Вы писали:

А>Как быть?

А>З.Ы. Пакеты маленькие и очень нежелательно их раздувать за счет включения в них маршрута прохождения пакета.
А>З.З.Ы. Протокол — TCP. UDP не предлагать — задача стоит именно на TCP.

Ой-ой! Если у тебя 5 серверов, то "маршрут" уложится в 5 бит, признак того, что k-й сервер получил этот пакет и переслал дальше.

В худшем случае будет разослано 1 + (N-1) + (N-1)*(N-2) = 1+(N-1)^2 пакетов, где N — количество серверов.
Для N=5, это всего лишь 17.

Другой вариант состоит в назначении диспетчера. Серверы договариваются между собой (можно передавать эстафету). Если пакет приходит не к диспетчеру — тот отсылает его "в центр".
Поскольку соединение TCP, то серверы могут проверять, живы ли их коллеги, и оперативно менять конфигурацию сети.

---

Кстати, а что должно происходить, если один сервер выпал, в это время нагнали данных извне, а потом сервер поднялся? Он будет синхронизовываться, или останется в неведении?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Аноним, Вы писали:

А>>Как быть?

А>>З.Ы. Пакеты маленькие и очень нежелательно их раздувать за счет включения в них маршрута прохождения пакета.
А>>З.З.Ы. Протокол — TCP. UDP не предлагать — задача стоит именно на TCP.

К>Ой-ой! Если у тебя 5 серверов, то "маршрут" уложится в 5 бит, признак того, что k-й сервер получил этот пакет и переслал дальше.

А если 1000?

К>В худшем случае будет разослано 1 + (N-1) + (N-1)*(N-2) = 1+(N-1)^2 пакетов, где N — количество серверов.
К>Для N=5, это всего лишь 17.

Во-во, а для 10 серверов уже 80

К>Другой вариант состоит в назначении диспетчера. Серверы договариваются между собой (можно передавать эстафету). Если пакет приходит не к диспетчеру — тот отсылает его "в центр".
К>Поскольку соединение TCP, то серверы могут проверять, живы ли их коллеги, и оперативно менять конфигурацию сети.

К>

---

К>Кстати, а что должно происходить, если один сервер выпал, в это время нагнали данных извне, а потом сервер поднялся? Он будет синхронизовываться, или останется в неведении?

Будет синхронизироваться.

Здравствуйте, Аноним, Вы писали:

К>>В худшем случае будет разослано 1 + (N-1) + (N-1)*(N-2) = 1+(N-1)^2 пакетов, где N — количество серверов.
К>>Для N=5, это всего лишь 17.

А>Во-во, а для 10 серверов уже 80

Почему-то я (невнимательно читал) был уверен, что серверов — 5.

Тогда вот ещё такой вопрос: сколько серверов одновременно могут быть выключены? Допустим, D.
Значит, если мы построим граф с N вершинами, каждая из которых смежна с D+1 другими, то пакет будет гарантированно разослан всем.
В худшем случае будет отправлено
1 + 1*(D+1) + (D+1)*L,
где L — диаметр графа. L ~ N/D, тут надо подумать над точным значением.

Пример: D=1, делаем кольцо. k-й сервер общается с k-1 и k+1.
D=2. k общается с k-1, k+1 и k+(N/2)
D=N-1. Каждый общается с каждым.

Здравствуйте, Кодт, Вы писали:

[]

К>Тогда вот ещё такой вопрос: сколько серверов одновременно могут быть выключены? Допустим, D.

В каждый конкретный момент может быть выключено N серверов из N . Задача сервера — при подъеме начать коннектится к серверам из своего списка (т.е. сохраняется некий архив серверов, доступных на момент последнего включения) и синхронизировать данные о серверах. Результатом всей этой работы должны быть практические идентичные списки у всех серверов в сети. В принципе, достаточно поддерживать их 90%-ную актуальность. Я подумываю, что вариант, предложенный PK Sly, может вполне пригодиться для этих целей — сервер, подключаемый в сеть, будет сам сообщать о себе всем серверам в сети, синхронизируя списки. Рано или поздно синхронизация пройдет полный круг (во всяком случае — должна по прикидкам). А если при получении нового сервера еще сделать возврат назад (т.е. разослать его адрес серверам, с которыми я уже синхронизировался), то, думаю, overhead будет не таким большим при выполнении условия поддержания актуальности списков.

К>Значит, если мы построим граф с N вершинами, каждая из которых смежна с D+1 другими, то пакет будет гарантированно разослан всем.
К>В худшем случае будет отправлено
К>1 + 1*(D+1) + (D+1)*L,
К>где L — диаметр графа. L ~ N/D, тут надо подумать над точным значением.

К>Пример: D=1, делаем кольцо. k-й сервер общается с k-1 и k+1.
К>D=2. k общается с k-1, k+1 и k+(N/2)
К>D=N-1. Каждый общается с каждым.

Спасибо, подумаю над этим.