Анализ доменной структуры сети

АНАЛИЗ ТЕОРЕТИЧЕСКИХ ОСНОВ ПОСТРОЕНИЯ СЕТИ НА БАЗЕ ТЕХНОЛОГИИ Netsukuku

Анализ протокола сети

4.1.1 Сетевая модель

Приоритеты Netsukuku это стабильность и масштабируемость сети: сеть должна иметь возможность расти до размеров 2²⁷ узлов.

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

Это предположение является законным, потому что местоположение узла Wi-Fi, установленного на вершине здания, не будет меняться, и его единственными динамическими действиями были бы соединение и разъединение к и от сети и изменений качества этих соединений.

Однако, есть некоторые последствия связаные с этим предположением:

- узлы мобильных телефонов не поддержаны алгоритмами Netsukuku (Есть возможность использовать другие мобильные протоколы для обьединения с Netsukuku, таким же образом как они соединяются с Интернетом (наподобии gprs и др.). Ради простоты мы принемаем, то что работаем на уровне 0 (уровень, сформированный 256 единственными узлами);

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

Алгоритм маршрутизации. Одна из самых важных частей Netsukuku - алгоритм открытой маршрутизации, который ответственен за то чтобы найти все самые эффективные маршруты сети.

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

В Netsukuku существует собственный алгоритм, QSPN. Он основан на предположениях, описанных выше.

 

4.1.2 Топология сети

Один QSPN не был бы способен к обработке целой сети, потому что будет все еще требоваться слишком много памяти. Например, предположим что мы сохраняем только один маршрут, чтобы достигнуть одного узла и даже если бы этот маршрут стоял из одного байта, мы нуждались бы в 1 гигабайте памяти для сети, составленной из 10⁹ узлов (текущий Интернет). Поэтому необходимо структурировать сеть в удобной топологии.

Иерархическая топология. Netsukuku адаптирует иерархическую структуру: 256 узлов сгруппированы в узле группы (gnode), 256 узлов группы сгруппированы в единственной группе узлов группы (ggnode), 256 групп узлов группы сгруппированы в gggnode, и так далее.

Начиная от каждого gnode, являющегося единственным реальным узлом, QSPN начинает оперировать непосредственно на каждом уровне иерархии.

Пока считается что в каждом уровне есть максимум - 256 (g) узлов, QSPN будет всегда ­оперировать максимально с 256 (g) узлами. Поэтому мы должны были бы только убедиться, что это работает как и ожидается на все случаи графа, составленного из ≤ 256 узлов. Между прочим, мы непосредственно проанализируем общий случай.

 

4.1.3 Трассирующий пакет

TP (трассирующий пакет) является фундаментальным понятием, на котором базируется QSPN: это - пакет, который сохраняет идентификатор пройденных перелетов в своем теле.

Движение трассирующего пакета. TP не посылают определенному адресату, вместо этого, он используется, для движения по сети. Говоря "узел A посылает TP", мы подразумеваем, что "узел A запускает движение TP".

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

Свойства трассирующего пакета. Узел D, который получил TP, может знать точный маршрут, пройденный TP. Поэтому, D может знать, что маршрут достигает исходного узла S (который послал TP), и маршруты достижения узлов, стоящих в середине маршрута движения ТР.

Например, предположим, что TP, полученный D: {S, A, B, C, D}. Смотря на пакет, D будет знать, что маршрут, достижения B является C→B, достигния A - C→B→ A, и наконец чтобы достигнуть S - C→B→А→ S. То же самое происходит со всеми другими узлами которые получили TP, то есть, B знает, что маршрут, чтобы достигнуть S является А→ S.

Букет S - набор всех TP, который будет предан или послан узлом S во время движения пакета. Первый TP этого букета, полученного универсальным узлом D, будет TP, который прошел самый быстрый маршрут, который подключает S к D. Самый быстрый S→D маршрут является маршрутом с минимальным rtt (Round – Trip Time) между S и D. Это свойство также правильно, если S - узел, который запустил движение TP, то есть первый узел, который послал первый букет движения TP.

Рисунок 4.1 - Простой граф

 

Предположим, что D посылает TP. TP пройдет маршруты: D→E→ F и D→ C→B→A. Когда TP достигнет узла F и узла A, движение остановится, потому что любой A и F не в состоянии отправить TP любому другому узлу.

В конце A будет знать маршрут, A →B→ C→ D, а F будет знать движение F→E→D (рис. 4.1).

Нециклическое движение трассирующего пакета. Нециклическое движение не ограничено как нормальное движение TP: один или более ATP(Acyclic Tracer Packet) могут посылаться от того же самого узла. Конец движения задан таким правилом: узел не будет отправлять ATP кому-нибудь из своих соседей, если его идентификатор узла уже присутствует в маршруте, содержавшемся в теле пакета. С этим правилом ATP может идти в цикле только единожды, отсюда и название.

Наконец, как в нормальном TP, узел не отправляет ATP соседу, от которого получил пакет непосредственно.

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

Непрерывный трассирующий пакет (Continuos Taracer Paket - CTP) является расширением движения TP: узел будет всегда отправлять TP всем своим соседям, за исключением того, от которого он получил TP.

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

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

Интересное информационное правило. Это правило может быть описано в единственной фразе: трассирующий пакет продолжит передвигаться в сети, пока он несёт интересующюю нас информацию.

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

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

Если TP неинтересен для узла N, то это также неинтересно для всех других узлов (соседей). Это потому что неинтересный TP содержит маршруты, которые были ранее получены, запомнены и отправлены узлом N. Поэтому все другие узлы также уже знают те же самые маршруты.

Рассмотрим этот граф, представленный на рис. 4.2

Рисунок 4.2: цикл A-B-C-A

 

Предположим, что A посылает CTP. Два CTP, покроют следующие два пути и остановятся:

A→B→C→A→B→C

A→C→B→A→C→B

Проанализируем первый CTP шаг за шагом, полагая, что перед посланным CTP, ни один из узлов не знал маршрута.

A→B В этом пункте B не знает никакого маршрута достижния A, поэтому он рассматривает этот CTP как интересный и передает его к C.

A→B→C, смотря на этот пакет, C получает маршруты достижения A и B.

A→B→C→А, узел A изучает маршрут достижения C.

A→B→C→А→B, узел B изучает маршрут достижения C.

A→B→C→А→B→C, Наконец C уничтожает пакет, потому что он уже знает все маршруты, содержавшиеся в CTP.

 

4.1.4 Динамика сети

QSPN v2, описанный до сих пор, не является подходящим для динамических сетей.

Расширенный трассирующий пакет. ETP (Extended Tracer Packet) решает проблему того, как граф должен быть исследован и переисследован, для обновления карты узлов, интересовавшихся сетевыми изменениями. Этот способ работы, основан на простом наблюдении: когда в сети происходит изменение, только информация, хранившаяся в узлах, затронутых изменением, должна быть обновлена. У незатронутых узлов информация должна обновиться, при помощи использования расширенных трассирующих пакетов.

ETP - нециклический трассировщик пакетов (Acyclic Tracer Packet), который содержит часть карты (ATP является нормальным TP со следующим правилом: узел удаляет полученный ATP, если его идентификатор узла уже присутствует в маршруте, содержавшемся в теле пакета. Отметьте также, что, так как это - нормальный TP, он не возвращается назад если достигает конца сегмента.).

Так как карта - ряд маршрутов, и маршрут может быть описан TP, ETP можно рассмотреть как обьединение различных TP. Каждый TP ETP соблюдает интересное информационное правило (описанное выше).

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

Измененное соединение предполагает что качество соединения A B изменяется, (оно может улучшиться или стать очень плохим).

Давайте исследовать события, начинающиеся с A, имея в виду, что ситуация аналогична для B.

Начиная с изменения соединения l, оно может быть анологично и для B, чтобы обнаружить новые оптимальные маршруты. Поэтому A пошлет в B ETP со всеми маршрутами своей карты, кроме таковых из формы А→B→…… Если B найдет кое-что интересным, то он будет передано ETP.

Подробнее:

1) А обновляет свою карту.

2) Создание следующего набора:

где:

,

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

М является набором всех маршрутов карты B

gw (r) является первым перелетом маршрута r.

dst (r) является адресатом маршрута r.

rem (r) является Мерой Эффективности Маршрута(Route Efficiency Measure) r.

Если R = 0 тогда алгоритма останавливается.

3) Каждый маршрут r R сохранен как (dst (r), rem (r)).

Создание ETP:

a) А записывает установку R в ETP;

b) А применяет ID узла, наряду со значением эффективности ссылки l;

c) А устанавливает 1 - флаг интересности пакета.

А посылает ETP к B.

Предположим, что узел C получил ETP от своего соседа N (C может быть B, и N может быть А). C исследует ETP и, если он интересный, обновляет его карту, и передает ETP другим соседям:

Если идентификатор узла C уже присутствует в полученном ETP, то C немедленно уничтожает ETP и пропускает весе следующие шаги (Это ациклическое правило).

Пусть R быдет набором маршрутов, содержавшихся в ETP, полученном C.

Пусть М. быть набором всех маршрутов, содержавшихся в карте C.

Для каждого маршрута r R, узел C ищет маршрут m M вроде этого:

dst (m) = dst (r), gw (m) = N

Если m существует, то C устанавливает rem (m): = rem (r) (С этой операцией, мы фактически заменяем m r в карте M). Иначе r скопируется во временно установленное R '.

M сортирован, то есть маршруты карты C сортированы в порядке эффективности.

Для всех r ' R ', допустим m ' M маршрут типа dst (r ') = dst (m '). Если r ' является лучшей альтернативой m ' и если каждый перелет r ' доступен C, то r ' сохранен в карте C как тройственность (dst (r '), N, rem (r ')+rem (C → N)). Карта теперь упорядочена.

4) C создает следующий набор:

5) Если

(a) C создает новый ETP, прилагая установку S и его ID на нем. Флаг интереса, этого ETP, установлен в O.

(b) ETP посылают в N.

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

Причина для вышеупомянутой процедуры проста: C считает неинтересным, некоторые из маршрутов, содержавшихся в полученном ETP, тогда C отсылает назад свои лучшие маршруты, у которых есть тот же самый адресат тех, которые принадлежат R (надеясь, что они будут полезны для предыдущих интересовавшихся узлов).

Пусть

Если , то ETP все еще интересен: флаг представляющий интерес, остается установленным в 1.

C упаковывает ETP набором и добавляет его идентификатор. ETP посылают всем соседям кроме N. (Шаг осуществляет Интересное Информационное правило: только при хороших маршрутах, другие откидываются. Обратите внимание на расширение: если бы у ETP был только один маршрут, то это было бы почти равно CTP (у CTP нет ациклического правила)).

Режимы C будут использовать ту же самую процедуру. Таким образом, ETP продолжит размножаться, до того пока считается неинтересным.

Наблюдение: Предположим, что следующие суждения возможны:

node N node D

где V N – объединение всех соседей N.

 

 

Дан , пусть таким образом, что

 

 

,

 

где M карта N.

Если свойство существует, то шаг 5 может быть опущен (фактически, предположить N, посылает ETP в C и что C считает маршрут r содержавшимся в этом как неинтересный).

 

Шагом 5 C отсылает назад к N свой известный оптимальный маршрут s, с dst (s) = dst (r), rem (s)> rem (r). Однако, s уже послал C в N (то есть когда соединение N C была стабильно), таким образом свойство , N запомнил s в своей карте M. Поэтому обратное распостранение ETP не приносит новой информации. Если карта топологи описсання ниже, используется, то свойство сохраняется.

Новое соединение. Случай, где новое соединение А B установлено, обработано таким же образом как и изменённое соединение, потому что мы можем рассмотреть l как соединение с новым rem.

Поломанное соединение

1) B создает набор R:

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

Если R = 0 тогда это остановит алгоритм.

Каждый маршрут r R сохранен как пара (dst (r), rem (r)).

B обновляет свою карту:

это устанавливает

Маршруты тогда отсортированы в порядке эффективности.

3) B создает следующий набор:

B заполняет ETP:

(a) B добавляет в этом, набор R.

(b) B прилагает свой идентификатор.

(c) B устанавливает в 1 флаг представляющий интерес.

Наконец, B посылает ETP всем своим соседям, кроме A.

В этом пункте ETP распостраняется таким же образом как и в случае Измененного соединения.

 

Присоединение новых узлов Предполагают, что узел A присоединяется к сети. Его соседи, В1, В2, …,В N которые все уже сцеплены, но они не присоединяются к сети. Тогда, случай нового соединения применен к каждому соединению

Отмирание узела, Когда узел A отмирает, случай Поломанного соединения просто применен к каждому соединению A.

4.1.5 Оптимизация QSPN

Несвязные маршруты. Таблица маршрутизации каждого узла должна быть дифференцирована, то есть она не должна содержать избыточные маршруты.

Например, рассмотрим этот P→S маршрут:

 

PBCFGIG2G3G4G5G6G7 … G19S (1)

PRTEGIG2G3G4G5G6G7 … G19S (2)

PZXMN O1O2O3O4O5S(3)

PQPVYIY2Y3Y4S (4)

 

Маршруты (1) и (2) почти идентичны, они только отличаются только по первым трем перелетам. С другой стороны, последние два полностью отличаются от всех других.

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

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

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

Теперь предположим, что узел P получает TP (TP, возможно прошел а возможно и нет через другие узлы приходя от N).

Возьмем , где T - набор всех троек, записанных в TP. P вычислит следующее значение:

(4.1)

где t₃ - третий элемент тройки t, и ITsl - ряд элементов набора ITsl.

Число m указывает, насколько несвязны маршруты, содержавшийся в T P из предыдущих маршрутов. Если m ≥2, тогда маршрут точная копия предыдущего маршрута. Если m ≈2, то маршрут приблизительная копия предыдущего маршрута. Если m =1, маршрут определенно оригинален.

Рассмотрим пример, представленный на рис. 4.3

Если er - эффективность маршрута r, используя значение m относительно r, мы можем получить новое значение эффективности:

 

 

где k - соответствующий позитивный коэффициент. Полученная эффективность оценивает, может использоваться Q2, чтобы решить, интересен ли маршрут r или нет.

Рисунок 4.3 - Пример механизма несвязного маршрута

 

Криптография QSPN. Узел мог легко подделать TP, вводя ложные маршруты и информацию о ссылках в сети. Атака только создала бы временное местное повреждение, благодаря распределенной природе QSPN. Однако оптимальное решение состоит в том, чтобы предотвратить эти атаки.

Всякий раз, когда присоединяеся к Netsukuku, она генерирует новую пару RSA ключей. Последующая генерация ключей предотвращает утечку анонимности узлов. Узел совместно использует свой открытый ключ ко всем другим узлам его группового узла.

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

Размер, требуемый для сохранения сигнатуры в TP, может быть сохранен используя постоянную составную систему сигнатуры.

 

Анализ топологии сети

4.2.1 Основные определения

Узел. Мы называем node любым компьютером, который присоединен к сети Netsukuku.

Rnode обозначим in-Range Node (узел в радиусе): учитывая что узел X, это - любой другой узел, непосредственно связанный с X, то есть это - сосед X.

Карта - это файл, сохраненный каждым узлом, который содержит всю необходимую информацию о сети, т.е. состояние узлов и маршруты.

REM является Route Efficiency Measure (Мера Эффективности Маршрута). Это - значение, которое указывает качество маршрута. REM может быть вычислен различными способами, т.е., беря в учетной записи общее количество rtt и способность ширины полосы частот маршрута. Мы обозначаем REM маршрута r как REM (r). Если r - лучший маршрут чем s, то rem (r)> rem (s).

Рисунок 4.4 - Узлы A, B и C

 

Пример:

A это rnode B.

B это rnode A и C.

C это rnode B.

 

4.2.2 Топологии сети

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

Иерархическая топология. Уровень 1.

Прежде всего мы подразделим сеть на группы по 256 узлов, и мы будем использовать следующие определения:

Gnode(group node) означает узел группы. Узел группы G состоит из ряда соединенных узлов. Каждый узел сети принадлежит только одному gnode. Узлы группы G соединены следующим образом:

путь a→b все содержавшиеся в G

В netsukuku реализации gnode содержит максимум 256 узлов.

Написав мы указываем число узлов, содержавшихся в G.

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

 

Рисунок 4.5: bnode A и B, принадлежат соответственно gnode G и G

Пример:

Написав мы подразумеваем, что bnode b принадлежит gnode G.

, A - узел, принадлежащий gnode G, его rnode - B.

, B - узел, принадлежащий gnode G, его rnode - A.

A - bnode G, в то время как B - bnode G ’.

Уровень n. Мы далее подразделяем топологию сети на группы из 256 групп узлов и мы продолжаем называть их как gnode.

В этом пункте мы повторяем рекурсивно этот процесс подразделения, пока мы не сможем сгруппировать все узлы сети в единственный gnode.

Делая так, мы структурировали сеть в n+1 уровнях (от 0 до n).

В основном уровне (уровень 0), есть 256 единственных узлов.

В первом уровне (уровень 1), есть 256 gnodes. Каждый из которых содержит 256 единственных узлов.

Во втором (уровень 2), 256 gnodes уровня 1.

В третьем (уровень 3), есть 256 групп 256 групп 256 групп 256 узлов.

Продолжая таким образом, мы достигаем последнего уровня (уровень n), где есть единственная группа, которая содержит целую сеть.

Алгоритм QSPN в состоянии работать независимо на любом уровне, представляя каждый gnode как единственный узел уровня 0. Поэтому мы можем рассмотреть топологию Netsukuku как иерархию, где каждый уровень составлен единственным узлом.

Рисунок 4.6 - пример иерархической топологии Netsukuku.

 

Пример иерархической топологии Netsukuku на рис. 4.6

В этой топологии каждый gnode содержит четыре узла, то есть каждая группа содержит четыре элемента. Сеть структурирована в 6 уровнях.

Красные элементы, единственные узлы (уровень 0).

Четыре узла формируют единственную группу узлов (уровень 1).

Единственный ярко-зеленый круг - группа групп узлов (уровень 2).

Зеленые круги - группы групп групп узлов (уровень 3).

Темно-синий круг - группы групп групп групп узлов (уровень 4).

Наконец, яркий синий круг - gnode, который содержит целую сеть (уровень 5).

 

Членство.Давайте назначать числовой идентификатор (ID) на каждый (g) gnode, начинающийся с последнего уровня:

1. в последнем уровне (n) есть только один гигант gnode, таким образом мы назначим ему ID “0”. Наш глобальный идентификатор будет: 0;

2. в n ₁ есть 256 gnodes, который принадлежит gnode 0 из уровня n, таким образом мы назначаем им идентификаторы от 0 до 255. Глобальный идентификатор становится:

;

3. мы повторяем шаг 2, рекурсивно получающий идентификатор этой формы:

, ;

4. так как последний уровень всегда 0, мы его опустим и рассмотрим только начальные n уровни.

В сети с максимумом 232 узлов (максимум, позволенный ipv4), было бы пять уровней (n = 4), где каждый gnode будет составлен из 256 узлов. Поэтому, идентификатор будет в обычной форме IP:

0... 255·0... 255·0... 255·0... 255

Например, единственный узел уровня 0 из сети представляется в виде

3·41·5·12

Поэтому, каждый gnode сети принадлежит только одной комбинации gnodes из различных уровней. Из нашего предыдущего примера мы имеем:

g3 = 3

g2 = 41

g1 = 5

g0 = 12

где каждый g_i соответствует gnode идентификатору уровня i. Отметим, что g0 – идентификатор приписанный единственному узлу, на уровне 0. Наконец, мы можем назначить на каждый gnode G, любого уровня, контрольную сумму (fingerprint) fg (G), которая идентифицирует G уникальным способом, отличным от его идентификатора: у двух разных gnodes может быть тот же самый идентификатор, но не та же самая контрольная сумма файла. Правильная контрольная сумма файла - fg (G) = (uptime (G), rid (G)), где rid (G) случайно сгенерированный идентификатор во время создания G.

 

Иерархическая карта. Преимущества использования иерархической топологии ясны. Узел N, вместо того, чтобы запомнить информацию о каждом узле целой сети, сохраняет только, ту информацию относительно gnodes, которым принадлежит.

Предположить у узла N был этот идентификатор:

g3 ·g2 ·g1 ·g0

Это сохранит в информацию памяти относительно:

1. 256 единственных узлов, которые принадлежат тому же самому gnode уровня 1, или другими словами, 256 узлов gnode g1;

2. 256 gnodes gnodes, которые принадлежат тому же самому gnode уровня 2, другими словами, 256 gnodes gnode g2;

3. наконец, 256 gnodes, которые принадлежат gnode g3.

Отметим, что, делая так, узел N не будет видеть все другие gnodes. Не будет знать никакой информации относительно узлов принадлежащих другим gnodes уровня 1 отличных от g1.

Даже с этой нехваткой знания, как мы увидем позже, узел N все еще в состоянии достигнуть всех других узлов сети. И в заключение N нуждается только в 256n записей в карте, вместо 232. Чтобы разъяснить идеи предположим что каждая запись весит один байт. В простой топологии мы нуждались бы в 4 гигабайтах, в то время как в иерархической мы нуждаемся только в 256·4 b = 1 КБ.

IP v4 и v6. Netsukuku полностью совместим с ipv4 и ipv6.

В ipv4 есть максимум 232 IP, таким образом у нас есть пять уровней n = 4. В ipv6 есть максимум в 2128 IP, таким образом n = 16.

Внутренняя и внешняя карта. Для простоты мы делим карту узла N, на внутреннею карту и в внешнюю. Внутренняя карта содержит информацию относительно узлов принадлежащих g1. Внешняя карта описывает все другие уровни топологии.

 

Маршрутизация CIDR

Бесклассовая адресация (англ. Classless InterDomain Routing, англ. CIDR) — метод IP-адресации, позволяющий гибко управлять пространством IP-адресов, не используя жёсткие рамки классовой адресации. Использование этого метода позволяет экономно использовать ограниченный ресурс IP-адресов, поскольку возможно применение различных масок подсетей к различным подсетям.

QSPN, для каждого уровня, выстраивает маршруты, необходимые для подключения каждого (g)node ко всем другим (g)nodes того же самого уровня. Маршруты будут сохранены в картах каждого узла.

Если узел N = g3 ·g2 ·g1 ·g0 хочет достигнуть узла М, который принадлежит другим gnodes, например М = g3 · g2 · h1 · h0, это добавит CIDR маршрут в таблицe маршрутизации ядра:

все пакеты, адреса которых g3 ·g2 ·h1 ·0... 255 будут отправлены в шлюз X.

Мы позже увидим почему шлюз X был выбран.

 

4.3.1 Внутренняя карта и ее миопия

Мы определяем маршрут r N узла N следующим образом:

 

r N: = (dst, gw, rem)

 

где: dst - узел: узел адресата маршрута

gw - узел: шлюз маршрута

rem - число: значение REM маршрута

 

Мы будем использовать dst (r), gw (r), rem (r), для индикации соответственно первое, второй и третий элемент r. Допустим VN является объединением всех соседей N. Допустим R является набором всех маршрутов узла N (для простоты мы рассматриваем только один показатель для всех маршрутов. Однако, как это можно легко увидеть что следующие суждения правильны для разных показателей маршрутов (нужно только использовать другие устанавки R m для каждого показателя m)).

Мы можем определить следующий отношение эквивалентности:

 

С мы указываем эквивалентный класс r. Возьмем является оптимальным маршрутом маршрутов в со шлюзом x, где , то есть:

 

 

Рассмотрите следующее подмножество R:

 

 

где G - gnode уровня 1 таким образом что

В этом пункте мы можем определить внутреннюю карту N как подмножество , где

.

Следующее свойство будет иметь место:

 

c

 

Алгоритмически, когда узел N хочет сохранить в М маршрут s, который имеет то же самое назначение маршрута , следующий алгоритм будет принят:

 

if

if [s лучше чем t]

заменям t на s;

else ничего неделаем;

else сохраняем s в M;

 

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

Маршрут сохраняем во внутренней карте, при помощи етой тройки(dst,gw,rem), а не последовательности узлов, поэтому узел N не знает весь свой путь. Поэтому мы может сказать, что обзор узла N всей сети является миопией, или локальным. Как мы будем видеть позже, эта миопия может быть легко применена к более высоким уровням. Отметим также то, что QSPN v2 является независимым от вышеупомянутых определений, то есть его работа не изменяется.

С точки зрения QSPN v2, урони являются "плоскими", потому что распространение ETP3 в целой сети точно такое же как прежде, кратко: пакет распостраняется, пока это не интересно, подразделение узлов в gnodes

просто проигнорируем. Единственное добавленное правило служит, чтобы сэкономить пространство:

допустим что T является универсальным Трассирующим пакетом и пусть будет конечной последовательностью узлов. Каждая подпоследовательность таким образом, что , где G - gnode любого уровня, заменен идентификатором G. rem, связанный с идентификатором G, является суммированием rem каждой тройки (dst, gw, rem) подпоследовательности. Это правило правильно для любого уровня, и его называют правилом группы.

Плоские урони.

Некоторые примеры:

1. Трассирующий пакет

 

11.22.1, 11.22.80, 11.22.35

 

не может быть группирован, потому что

2. Трассирующий пакет

 

11.22.1, 11.22.80, 11.22.35, 11.44.13

 

может быть группирован в следующем Трассирующем пакете:

 

11.22. *, 11.44.13

 

3. Трассирующий пакет

 

11.22.1, 11.22.80, 11.22.35, 11.44.13, 55.32.20

 

может быть группирован в следующем трассирующем пакете:

 

11. *, 55.32.20 (4.2)

 

Описание маршрута во внешней карте является локальным, как во внутренней карте. Например, когда узел 55.32.12 получает Трассирующий пакет (4.2), он сохранит следующий маршрут:

(dst = 11.* = любой узел gnode 11, gw = мой сосед 55.32.20, rem)

Наконец, набор М использованный для описания ETP в разделе QSPN, изменен от набора всех маршрутов внутренней карты к набору всех маршрутов (внутренний и внешний).

Аппроксимизация правила группы.

Правило группы подразумевает что узел не может знать внутренности G, то есть он не знает, какие узлы принадлежит G и как они расположены. Фактически, оптимальный маршрут r c, чтобы достигнуть любого узла G является только маршрутом, который достигает узел , который является самым близким узлом G к c. Однако маршрут r правилен достигнуть любого узла , потому что gnode, по определению, является подключенным набором узлов (см. 4.1.1). То, что не сохраняется, является точностью маршрута: r - оптимальный маршрут, чтобы достигнуть , но это не может быть оптимальный маршрут, чтобы достигнуть , где . В каждый случай, r - приближение оптимального маршрута, чтобы достигнуть : с тех пор , d знает оптимальный маршрут , таким образом маршрут будет . приближение может быть улучшено с использованием causting маршрутизации и налагая, который значение rem маршрута содержало в G, где b является bnode, и не слишком отличается от любого другого маршрута , содержавшийся в G.

 

4.3.2 Фаза присоединения

Процедура подключения служит для:

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

- сохранения gnodes внутренне подключенным

- сохранения gnodes компактным.

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

Униформа gnodes. Допустим G является не пустым gnode. Так как G должен быть внутренне подключен, узел n может стать узлом G если он непосредственно связан по крайней мере с одним узлом . Этот факт приносит некоторые проблемы в распределении и распределении бесплатных IP.

Мы говорим, что G распределен если он не пустой. Говорят gnode уровня l насыщен если все его узлы распределены. Весь gnode любого уровня l может быть сохранен распределенным единственным узлом n, таким образом возможно быстрое насыщение gnode уровня l + 1. Насыщенный gnode может казаться полным, даже если он имеет пустое пространство, т.к. предполагают, что gnode насыщался gnodes , предположим также, что A полон, а у B и C есть некоторое свободное пространство. Узел n, который является непосредственно связанный с узлом , не будет в состоянии участвовать в . Фактически, n не сможет стать узлом А, потому что это полный gnode, и не сможет стать узлом B и C, потому что непосредственно не подключен ни к одному из узлов. Поэтому, единственная возможность, оставленная n, ето создание нового gnode в . Однако, если самый высокий gnode, то есть gnode всех узлов сети, n не сможет этого потому что насыщается A, B, C. Эту проблему называют насыщаемостью gnodes (gnodes saturation).

Стратегия решения проблемы насыщаемости gnodes состоит в том, чтобы однородно распространить узлы: у всего gnodes сети будет приблизительно одно и то же количество узлов, в любое время. Это достигнуто, благодаря использования системы, которая имеет вид сообщающихся сосудов:

1. сцепляющийся узел n (т.е. узел, который присоединяется к сети) создаст набор содержащий имена всех самых высоких не насыщеных gnodes, весего уровеня l. n может составить , смотря карту своих соседей. Из он выберет , который является gnode с самым низким количеством узлов, то есть.

тогда, он станет новым (g) node уровня l-1 из gnode ;

2. допустим b является bnode gnode уровня 1, и B набор соседей b, таким образом что . Допустим G(c) является gnode уровня 1 из узла c и

Если , остановимся здесь, другими словами является gnode с самым низким число узлов, то есть . Тогда b станет сцепляющим узлом, таким образом это создаст новый gnode, или это станет узлом H, оставив G.

После чего, b сообщит его соседям, принадлежащим G повторить эту ту же самую процедуру (некоторые соседи соединены с b который сейчас является узлом H, будут являтся bnodes G, гранича с H). Сосед сообщивший что не может выполнить эту процедуру, пошлет ETP в G, сообщать другим узлам об уходе b из G.

Пример:

1. Рассмотрим следующий сценарий, где у нас есть только один уровень, насыщаемый 3 gnodes:

11.11 ↔22.11 ↔33.11

2. Два узла присоединяются 11.*:

11.33 ↔11.22 ↔ 11.11 ↔ 22.11 ↔ 33.11

3. Правило сообщающихся сосудов применено:

11.33 ↔ 11.22 ↔ 22.22 ↔ 22.11 ↔ 33.11

4. Другие два узла присоединяются 11.*:

11.55 ↔11.44 ↔11.33 ↔ 11.22 ↔22.22 ↔22.11 ↔33.11

Ситуация развивается к

11.55 ↔ 11.44 ↔11.33 ↔ 22.33 ↔ 22.22 ↔ 22.11 ↔ 33.11

11.55 ↔ 11.44↔11.33 ↔ 22.33 ↔22.22 ↔ 33.22 ↔ 33.11

Узел координатор. Переход узлов от gnode А к другому B, должен быть преобразован в последовательный режим. Узлы не могут транслировать одновременно, потому что, когда узел n перемещается, он знает |A | и |B |, но это не знает, сколько других узлов переходит в B и как много уходят из A. Таким образом, без последовательного упорядочения, слишком много узлов может уйти из gnode или войти в другой, не смотря на правила сообщающихся сосудов.

Решение состоит в том, чтобы назначить объединению узлов координатора co(G) на каждый gnode любого уровня. Это по существу достигнуто, используя “P2P по Ntk”: координатор P2P сервиса создан, и все узлы являются неявными участниками. В этом разделе, достаточно сказать, что предоставленным gnode G мы можем достичь своих координаторов узла сo(G).

Узел n войдет в контакт с сo(G) для любого из следующих случаев:

- n хочет стать узлом G, если | G | удовлетворяет данное условие (т.е. -где N является gnode n)

- n хочет покинуть G, если | G | удовлетворяет данное условие (т.е. )

- n хочет создать новый gnode

- n хочет знать текущий | G |

n выполнит относительное действие, только если сo(G) ответит утвердительно. Чесно говоря сo(G) должна обработать запросы последовательным способом, то есть обработку одного запроса и блокирование всех других. сo(G) рассмотрит запрос как категорический, когда получит относительный ETP, другими словами вернет изменение после времени ожидания, т.е. n может спросить и предоставить запрос на присоединение к G. Это возможно, не соблюдая это и сo(G), рассмотрит его как пустой запрос после времени ожидания 30 секунд, восстанавливая |G |.

Пределы Сообщающихся Сосудов.

сообщающаяся система сосудов - основная аппаратная часть Netsukuku, и самая требовательная к условиям работы, потому что, когда узел изменяет gnode, он изменяет и IP. Это - также основная причина для отрицания мобильности Netsukuku. Чтобы смягчить эти проблемы, нужно классифицировать узлы как статические и гостевые: узлы подключенные больше чем 10 мин. и эффективные узлы Netsukuku вместо последних подключенных к сети через NAT соседей. Данная проблема находится на стадии разработки.

Внутреннее подключение. gnode G внутренне подключен если

путь a→b все содержится в G gnode может стать сломанным (внутренне не подключенным) если другой gnode сети принимает тот же самый gnode ID, или если одно или более соединений в gnode умрет, разбивая gnode на две отдельные части. Практически, первый случай может случитеся, только если две отдельные сети встречают друг друга впервые: допустим являют собой 2 gnodes уровня l + 1, и встречаются впервые. Предположим это , тогда узлы наименьшего gnode или у каво самый старый период работоспособности повторно перераспределятся.

Второй случай, где G разбит на две части будет обработан нижеследующим образом: bnode получает ETP для разрыва соединения. Обновление карт с этим ETP, напомню, что у него нет никакого маршрута, достижения каких либо узлов. Назовем E набором недостижимых узлов (факт, что n не знает ни одного маршрута достижения d, не подразумевает что такие маршруты не существуют, однако согласно структуре внутренней карты применение правильно).

Есть две возможности: узлы E изменили gnode при помощи системы сообщающихся сосудов, или разрывая связь эффективно разбивают G на две части. n может отличить эти два случая, потому что ETP, сгенерированный системой сообщающихся сосудов отмечена специфическим способом. Если n находится во втором случае, то он принадлежит набору . Если , то n решает стать сцепляющим узлом, и сообщает это всем другим узлам , чтобы сделали то же самое.

 

Рисунок 4.7 - В первом шаге у нас есть gnode 11.* (красный). Во втором, gnode становится сломанным. В третьем, после того, как процедура, описання выше, применина, у нас есть два gnodes: 11.* и 22.*

 

Компактный gnodes. gnode G компактен, если, устанавливал значение rem в ,

где является лучшим путем от а до b.

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

Оптимальная методика, сохранения gnodes компактнее еще не была найдена. Как пример, рассмотрите следующий, который был вдохновлен гравитационной моделью: допустим n является узлом и V n набор его соседей. Поскольку каждый граничит

, n вычисляется следующим значение привлекательности (attraction value):

где - набор всех оптимальных маршрутов n, проходящих через v

n тогда привлечен соседом , у которого есть самое высокое значение привлекательности: n ввойдет в gnode v (если он еще не там).

Проблема с любой Компактной gnodes системой состоит в том что группирование узлов становится зависящим от качества связей, таким образом сеть может быть перенастроена чаще.

 

Анализ доменной структуры сети

ANDNA (Abnormal Netsukuku Domain Name Anarchy) - распределенная, не иерархическоя, и децентрализированая система управления именеми хостов Netsukuku. Она заменяет систему DNS.

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

4.4.1 ANDNA

ANDNA основан на принципе, что каждое имя хоста h является строкой не больше 512 байтов. Беря хеш H (h) имени хоста, мы получаем число. Мы считаем это число IP, и мы называем узел хеш узлом, которому принадлежит тот же самый IP. Каждый хеш узел хранит маленькую часть распределенной базы данных ANDNA.

Узел n

ip: 123.123.123.123

хеш (имя хоста: "netsukuku")=11. 22. 33. 44

||

Узел i

ip: 11.22.33.44

{[База данных Andna узла i]}

{хеш ("netsukuku")---> 123.123.123.123}

Регистрация имени хоста h, узлом n следует ниже:

- n вычисляет i = H (h);

- n посылает регистрационный запрос i;

- i ассоциируется в базе данных H (h) с IP n, который является IP (n).

Разрешающая способность имени хоста h узлом m:

- m вычисляет i = H (h)

- m посылает запрос разрешающей способности i

- i отсылает назад к m IP, связанного с H (h), который в этом примере является IP (n).

Хеш gnode. Есть вероятность, что хеш H (h) не ответит никакому активному узлу: если есть в общей сложности 230 активных узлов, и мы используем IP 32 битов, то, беря 32 битный хеш h вероятность равна 25 %. Кроме того, даже активные узлы могут выходить из сети.

Поэтому, регистрация имени хоста будет сохранена всеми узлами единственного gnode. Это гарантирует распределённость и избыточность базы данных. gnode связанный с H (h) является хеш gnode, и это - просто gnode уровня 1 из хеш узла H (h). Мы обозначим gH (h) как предыдущий и n H (h) как последующий. Мы можем написать что:

n H (h) gH (h).

Аппроксимизированный хеш gnode. Даже если хеш gnodes не может существовать, стратегия аппроксимизации будет использоваться: самый близкий активный gnode к хеш gnode станет округленным хеш gnode, который полностью займет место оригинала (не существующего) хеш gnode. Округленный хеш gnode (rounded hash gnode) обозначим как rgH (h).

Вообще, когда мы обращаемся к gnode, который принял регистрацию,­ нет никакого различия между двумя видами gnodes, их всегда называют хеш gnodes.

Присоединение. Когда узел присоединяется к Netsukuku, то он автоматически становится частью хещ gnode, таким образом он также выполнит andna присоединение. Присоединяясь он получит всь кэш и базы данных, которые уже распространены в его хеш gnode.

Криптография ANDNA. Прежде, чем сделать запрос к ANDNA, узел генерирует несколько RSA ключей, то есть открытый и закрытый ключи. Размер открытого ключа будет ограничен для экономии пространства. Запрос имени хоста, сделанного к ANDNA, будет подписан при помощи секретного ключа, и в том же самом запросе будет прикреплен открытый ключ. Таким образом, узел будет в состоянии идентифицировать себя при своих будущих запросах.

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

Реализация предела. Встречный узел - узел с ip равным хешу открытого ключа узла, который регистрировал имя хоста h. Мы обозначим встречный узел связанный с узлом n как cr (n). Таким образом, для каждого узла n, который регистрировал ­имя хоста h, существует его соответствующий встречный узел cr (n).

Встречный узел cr (n) сохранит число имен хоста регистрированным n.

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

cr (n) активируется запросом проверки, который посылает хеш gnode. n должен сохранить cr (n) активным следуя за теми же самыми правилами бездействия (hibernation rules). Фактически, если cr (n) не получает больше запросы проверки, он деактивирует себя, и все зарегистрированные имена хостов станут недопустимыми.

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

Регистрация шаг за шагом:

1. Узел n хочет регистрировать своё имя хоста h,

2. Он находит округленный хеш gnode rgH (h) и связывается с одним из ее узлов случайным образом. Позволим этому узлу быть y.

3. n посылает регистрационный запрос в y. Запрос включает открытый ключ узла n. pkt также подписан секретным ключом n.

4. Узел y проверяет, чтобы быть эффективно самым близким gnode к хеш gnode, при обратном он отклоняет запрос. Правильность сигнатуры также проверяется.

5. Узел y входит в контакт со счетчиком gnode cr (n) и посылает к нему IP, хеш имени хоста, который будет зарегистрирован и копию регистрационного запроса.

6. cr (n) проверяет данные и дает добро.

7. Узел y, после утвердительного ответа, принимает регистрационный запрос и добавляет запись в его базе данных, сохраняя дату регистрации.

8. y передает gnode свой регистрационный запрос.

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

Бездействие имени хоста. Хеш gnode сохраняет имя хоста в состоянии бездействия в течение приблизительно 30 дней с момента его регистрации или последнего обновления. Время истечения очень долгое, для стабилизации домена. Таким образом, даже если кто-то нападает на узел, чтобы захватить его домен, он должен будет ждать 30 дней, чтобы полностью получить его.

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

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

У пакета запроса обновления есть id, которое равно числу уже посланных обновлений. pkt также подписан секретным ключом узла, чтобы гарантировать истинность запроса. pkt посылают в любой узел хеш gnode, который пошлет копию запроса на счетчик gnode, чтобы проверить его активность и что запись, связанная с обновляемым именем хоста, существует. Напротив, запрос обновления отклоняется.

Мутация хеш gnodes. Если общий округленный gnode переходит в новый gnode, который ближе к хеш gnode, он обменяет свою роль с ним, то есть новый gnode станет округленным хеш gnode.

Этот переход является пассивным. Когда узел регистра обновит свое имя хоста, он непосредственно свяжется с новым округленным gnode. Так как имя хоста, сохраненное в старом округленном gnode не будет обновлено, оно будет упущено.

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

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

Таким образом, регистрация имени хоста автоматически передана от старого gnode в новый.

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

Чтобы предотвратить это, новый хеш gnode будет всегда проверять регистрационный запрос дважды, входя в контакт со старым хеш gnode.

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

Кэш andna сохранит очередь в записиях MAX_AN DNA_QUEUE (5). Когда функционирование имени хоста на вершине очереди завершиться, оно автоматически заменится следующим именем хоста.

Распределенный кэш для разрешающей способности имени хоста. Чтобы оптимизировать разрешающую способность имени хоста, используется простая стратегия: узел, каждый раз когда разрешает имя хоста, сохраняет результат в кэше. Для каждой следующей разрешающей способности того же самого имени хоста