Какой основной принцип отправки пакетов IP на конкретный узел (хост) сети Интернет?

Question

[Даниил]

Разрабатываю децентрализованную сеть соединений между узлами(клиентами), и вот углубился в компьютерные сети, но учебник был написан в прошлом веке.
Короче задача такая. Есть Клиент, он подключен к нескольким другим клиентам, а те к другим в свою очередь. Образуется сеть. Клиент А хочет отправить запрос клиенту Z. Он знает лишь его имя в сети, он отправляет всем своим клиентам запрос на поиск клиента, те же своим, и т.д. соответственно запрос не посылается, тем клиентам, кому он уже был доставлен, короче обход Графа. После нахождения клиента, тот клиент формирует ответ источнику, и источник отправляет тело сообщения.
Нужно, как то оптимизировать, к примеру, если в сети будет миллион клиентов, то каждый из них получит запрос, Как устроена сеть, как она определяет маршрут именно в реализации
Возможно к моменту ответа, я уже найду ответ, но все же совет гуру не помешает.
Структура Запроса:
type -> Tип запроса //в случае обхода find
target -> Имя клиента в сети, который должен быть найден
source -> Адрес : порт Источника, ему должен быть прислан ответ, от target
token -> Индикатор запроса, ставиться у посещенных узлов, и проверяется, не был ли поставлен до, что бы прекратить запрос на этот узел
visits - список упорядоченный посещенных узлов(пока лишний балласт проекте)



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

Comments

[Saboteur]

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

Answer 1

[Dimonchik]

Данил молодец, хорошо рисуешь

принцип очень прос - любой хост имеет путь по умолчанию (ну, можно и не иметь,в общем-то) и таблицу маршрутизации - через какой хост слать к какой сети

в самом простом случае эта таблица содержит одну строку - родную сеть (ну и вторую - локалхост)

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

угу, при крывых руках может ходить по кругу, для этого есть ttl (или хз как , забыл) с прохождением каждого узла уменьшаюшийся , кто ловит ttl 1 - дропает пакет

Comments

[Даниил]

Я просто одно не могу понять, мне в моей сети, запрос отправить 1 клиенту, а тот 1 другому итд., или всем соседнем, а те все своим итд. У меня вроде есть своя таблица обычных имен клиентов( connections),только клиенты не просто хранят адрес, но еще и подключены, и у каждого клиента она своя. Он соотносит имя и посылает всем своим узлам. В интернете, все проще(сложнее), там IP-шник есть, и можно выходить на более высокий уровень идентификации сети, к примеру 133.32.1.56 ищет 23.1.2.3, он смотрит все свою локальные адреса, не находит идет к 133.32.0.1 тот ищет с маской 255.255.0.0, у своих, не находит идет выше на 133.0.0.1 и ищет с маской 255.0.0.0, не находит, но он знает о 23.0.0.1, идет к нему, тот выдает 23.1.0.1, тот 23.1.2.0, а тот уже и искомый 23.1.2.3. Примерно же так будет, я правильно понимаю?

[Mystray]

Даниил, неправильно. Рано или поздно (скорее всего рано, 2-й или 3-й операторский маршрутизатор) будет иметь в памяти таблицу со ВСЕМИ доступными в интернете маршрутами (которую он составит при помощи протокола BGP, получив так называемый Full View, и сейчас насчитывает под 700 000 маршрутов). В этой таблице содержится лучший, на данный момент времени, маршрут к желаемому назначению. Работает это таким образом, грубо говоря: если владелец сети, в которую включен 23.1.2.3, захочет, чтоб этот 23.1.2.3 был доступен из Интернета - он "рассказывает" своим провайдерам-соседям о сети ( 23.1.2.0/24, или короче, в зависимости от того, что есть и что хочет владелец). Те - соответственно, рассказывают своим соседям, что знают маршрут к этой сети, и так далее. Если где-нимбудь встретятся маршруты к одной сети от двух разных маршрутизаторов - из них по различным критериям выберется лучший и передастся дальше. В итоге - все маршрутизаторы будут знать, как можно достичь конкретной сети, если она, конечно, в данный момент проанонсирована в интернете. Если к одному и тому же адресу будет несколько подходящих анонсов с разной длиной префикса (к примеру 23.1.2.0/24 и 23.1.0.0/22) - из них будет выбран тот, у которого префикс длиннее.

Answer 2

[Станислав Бодро́в]

Как устроена сеть

Куча автономных систем со своей внутренней динамической маршрутизацией между узлами сети. Обычно по протоколу OSPF, может быть IS-IS или даже IBGP. В пределах AS на маршрутизаторах хранится информация о всех маршрутах их стоимости до каждой подсети.

как она определяет маршрут именно в реализации

AS связаны между собой по протоколу динамической маршрутизации BGP. Он отличается принципом работы от протоколов внутри AS. Маршрутизатор, настроенный по этому протоколу знает о маршрутах только у соседних маршрутизаторов. В зависимости от настроек BGP трафик между автономными системами пойдёт по тому или иному пути и не всегда оптимальному (зависит от того как и о чем договорятся админы AS). Далее трафик через граничный маршрутизатор попадает внутрь нужной AS, где направляется по поределённому пути, который тоже не всегда может быть кратчайшим.
Потом трафик доходит до нужного маршрутизатора и по внутренней сети направляется к абоненту.

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

Answer 3

[Ярослав]

Я правильно понимаю, что:
- есть некая Mesh-сеть (все-со-всеми), предназначенная для обмена некими сообщениями
- канал связи между узлами - прямое TCP-соединение
- в случае обрыва прямого соединения, должна обеспечиваться возможность транзитного прохождения сообщения
- количество узлов может быть очень большим - возможно, тысячи узлов

Верно?

Тогда есть смысл реализовать схему маршрутизации, аналогичную принятой в BGP.
Я отойду от специфически сетевой терминологии и постараюсь передать суть.

Итак, у каждого узла есть свой идентификатор - имя.
Оно отвязано от его ip-адресации, и, по-хорошему, один и тот же узел может быть доступен по нескольким ip-адресам одновременно.

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

Пример:
Узел "Вася" подключается к узлу "Петя".
В момент подключения, "Вася" сообщает:
Я "Вася". Я знаю, как добраться до:
- "Вася", кратчайший путь: ""
- "Коля", кратчайший путь: "Вася"
- "Настя", кратчайший путь: "Вася, Коля" (Возможно, есть ещё более длинный маршрут, но нам достаточно сообщить наиболее короткий)

"Петя" делает следующее:
- отдаёт Васе аналогичный список известных ему узлов с маршрутами до них
- отбрасывает полученные от "Васи" маршруты, в кратчайшем пути до которых нашёл свой имя (во избежание петель маршрутизации)

Для того, чтобы понять, в какое соединение отправить сообщение для Насти, Пете достаточно из известных ему маршрутов до неё выбрать тот, у которого маршрут короче.

Потенциальные грабли, которые стоит учесть:
1. Не забывать сообщать соседям об изменении своей таблицы маршрутизации:
- при пропадании соседа
- при появлении нового соседа
- если для какого-то возможного получателя изменился наиболее короткий маршрут
2. Не забывать отбрасывать маршруты, в которых нашёл самого себя
3. Поскольку из-за некорректной работы некоторых узлов "закольцовывание" всё равно возможно, необходим аналогичный TTL механизм, ограничивающих количество транзитных узлов, которое может пройти сообщение перед своим уничтожением.

Comments

[Даниил]

В общем да, а какой стандартный размер таблицы в маршрутизаторе, сколько маршрутов. К примеру у меня приложение рассчитано не более чем 1000 узлов, и каждый узел может быть связан с 1 до 5 узлов, мне в таком случае будет выгодно каждому узлу выдать маршрут до каждого узла и его длину, просто я не понимаю как сделать маршрут длиннее чем 2 или 3.
Вот например моя таблица Узлы по номерам, для Узла "1". Узел "1" связан с "2" и "3",

"от узла" | "до узла" | "длинна"
. | 2 | 1
. | 3 | 1
2 | 22 | 2
1 | 22 | 3
1 | 18 | 2

("." сам этот узел). Правильно ли я составил? Если ,вдруг, то если я ее отправлю узлу 2, и увеличит пути на 1, то он для себя не чего не выберет, ведь у него все его маршруты, будут более выгодными, единственное, что он добавит маршрут 1 18 с путем 2+1 о котором не знал раньше.

[Mystray]

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

[Ярослав]

Если хранить только длину пути, без перечисления промежуточных узлов, есть шанс при выборе пути закольцевать трафик.
Соответственно, BGP AS Path - это оно самое.

Алгоритм Дейкстры же (привет, OSPF!) заставляет каждый узел хранить не просто информацию о доступности, а полный актуальный граф связей между узлами.
Да и ещё при этом важно не накосячить с реализацией.
И в случае Full Mesh это будет матрица 1000 * 1000.
Миллион элементов.

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

Сейчас - увы - гигабайты и гигагерцы считать немодно, а потом у людей комп на восьмиядерном процессоре чего-то тормозит ;)

[Станислав Бодро́в]

Узел "Вася" подключается к узлу "Петя".
В момент подключения, "Вася" сообщает:
Я "Вася". Я знаю, как добраться до:
- "Вася", кратчайший путь: ""
- "Коля", кратчайший путь: "Вася"
- "Настя", кратчайший путь: "Вася, Коля" (Возможно, есть ещё более длинный маршрут, но нам достаточно сообщить наиболее короткий)

Проблема в том как и на основании чего считать путь кратчайшим, точнее лучшим. Бывает кратчайший путь не всегда самый быстрый. Трассировка не всегда верный показатель. Когда сравниваешь трассировку TCP, UDP, ICMP пакетами, они часто между собой отличаются иногда разительно - не понятно какое очередное policy пров подкинет для того или иного трафика. Если капнуть глубже, то трассировка не может верное отображать все пертурбации с пакетом в сети.

[Ярослав]

Станислав Бодро́в: предлагаю вернуться к исходному обсуждению.

Вопрос Даниил, насколько я его понял, заключается в следующем: какие наработки в технологии построения Ip-сетей можно было бы использовать при создании сети системы Distributed Messaging.

Разумеется, все мы здесь эксперты, знаем, как работает Traffic Engeneering, и помним, что в том же BGP, кроме AS Path, есть куча других замечательных полей, таких, как local preference, MED, origin, разных видов communities.

Однако, мне, почему-то, кажется, что при начальном разворачивании Distributed Messaging-сети это всё не пригодится ;)

Хотя да, есть один момент, который мешать не помешает, но с непривычки с толку сбить может, ибо, поскольку при неполной связности узлов могут образоваться равнозначные маршруты, то:
1. Исходящие сообщения могут, в зависимости от выбранного алгоритма выбора пути в таком случае, каждый раз уходить разным путём
2. Если предполагается что-то вроде Remote Procedure Call с явными запросом и ответом, надо быть готовым к тому, что запрос уйдёт одним путём, а ответ придёт совершенно другим, то, что в ip-сетях называется асимметричным прохождением трафика