Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: DmitryTurin.narod.ru <DmitryTurin-Q+l+L2ir60w <at> public.gmane.org>
Subject: Roll to collect knowledge (and improve algorithms)
Newsgroups: gmane.network.peer-to-peer.netsukuku
Date: Sunday 3rd October 2010 09:40:47 UTC (over 7 years ago)

Netsukuku resume




  • The same html-file is attached

Foreword:

  • Below i repeated (on russian and english) all, what i have understood in documentation. LET'S START A ROLL: anybody, who know CONCEPTS, ALGORITHMS, IDEAS (instead of names of variables and other details of implementation), or who have QUESTIONS ABOUT THEM, please, APPEND INTO TAIL - we will summarize our comprehension in this roll. After this, i will write self-co-ordinated and regularized documentation on russian, will translate it into english, and somebody from mailing list will give literature form for it. To not break numeration, use <del> to cross question out, to which you appended answer, instead of removing question
  • Protection against censorship can be provided only by cryptography, while distributive traffic supplies this possibility in small degree. Stop positioning project as facility against censorship, because it is not so. To let other people obtain financing, more often use phrases "we are going to lease/rent underground wired lines and govenment satellite channel for inter-city communication; mobile variant of netsukuku will be sole citizen communication during any war, because towers with repeaters for cellular phones will be destroied by rokets and bombs just in first day". I.e. make re-positioning of project to reach bigger loyalty

Definitions:

  • First mentioning of terms, already existing in industry, are emphesized as green by <q>; terms of Andrea Lo Pumo - as blue by <em>; and another, as it seems for me, necessary terms - as red by <dfn>; ideas, new in industry, are emphesized as underlined by <u>; questions - as oblique by <i>. Emphesizing as bold by <b> is reserved for readers, that they mark interesting places during reading
  • Sometimes spaces inside terms are removed, and first letters of their words are turned into capital letters, e.g. "rounded hash Gnode" → RoundedHashGNode, that foreigners do not search sense in part of term
  • That term is chosen from several synonyms, which is comprehensible without clarifications in home life, e.g. synonyms "neighbour, RNode, gateway" → neighbour. Than it is used in all cases (razor of Occam)
  • Term "set" is used in primary documentation in two senses - to designate several devices and to designate several routes. In the same time, several devices have second name - GNode, where "G" obviously means "Group". So i have refered to several routes as to "set", and to several devices - as to "group" (let's define gloval terms and use them via all pdf- and txt-files, instead to define local terms in each new paragraph)
  • Maximum quantity of dublets (look definition below), registered in one device, are changed from 256 to 250 to avoid cognitive dissonance with 256 devices in a group
  • Word "routing" in term "caustic routing tree" is removed as redundant; word "tree" is changed to "bouquet", because these routes have identical end, and so they are not a tree, and word "tree" brings incomprehensibility; thus "caustic bouquet" is proposed for CRT

Structure

  1. Коммуникационные устройства (они же Node, x, n), способные общаться между собой, называются группой, или GNode. Группы вложены друг в друга - как планеты в солнечные системы, те - в галактики, галактики в скопления и т.д. Устройство, могущее без посредников передавать сообщения данному, называется его соседом, иначе RNode, gateway (все его соседи вместе обозначаются как V). Устройство называется экстремальным, если имеет только одного соседа. Называется граничным, BNode, если имеет соседа из другой группы. Новое устройство, подсоединяющееся к сети, называется HNode (видимо "hooking node").

    Communication devices (they are also Node, x, n), which is able to communicate with each other, have name group, or GNode. Groups are enclosed into each other - like planets into solar systems, solar systems into galaxies, galaxies into accumulations, and so on. Device, able to transfer messages to other device without mediator, is named as its neighbour, or RNode, gateway (all its neighbours together is designated as V). Device is named as extreme device, if it has only one neighbour. Device is named as border device, BNode, if it has neighbour from another group. New device, connecting to net, has name HNode (obviously "hooking node").

  2. Каждое устройство имеет 1-байтовый идентификатор (у устройств в разных группах идентификатор может совпадать) и 512-байтный UID, или hostname. Устройства перемещаются в пространстве, в каждой новой группе идентификатор генерируется заново как случайное число, а UID сохраняется и служит для установления самоидентичности. Группа, содержащая 256 устройств, называется насыщенной. Существует два вида HNode: присоединяющееся устройство (добавляется к уже существующей группе) и основывающее устройство (начинает новую группу).

    1. Если один и тот же сервер имеет UID/Netsukuku-адрес и IP/Internet-адрес (т.е. подключен к обеим сетям), поисковому роботу нужен специальный сервис Netsukuku (назовем его SukuInter), чтобы узнать у сервера по его Netsukuku-адресу его Internet-адрес, чтобы не выкачивать один и то те сервер дважды (один раз через Netsukuku-сеть, второй раз через Internet-сеть). Таким образом дистрибутив Netsukuku должен содержать демон для этого сервиса, не так ли?

    Each device has 1-byte identifier (identifier can coincide for devices from different groups) and 512-bytes UID, or hostname. Devices move in space, identifier is generated once again as random number in each new group, and UID is saved and serves to found self-identity. Group, containing 256 devices, has name saturated. There exist two kind of HNode: appending device (it is added to already existing group) and founding device (it begins new group).

    1. If the same server has UID/Netsukuku-address and IP/Internet-address (i.e. is connected to both nets), search robot needs special Netsukuku service (let's name it as SukuInter), to find server's Internet-address on base of its Netsukuku-address to not download the same server twice (first time via Netsukuku-net, second time via Internet). Thus Netsukuku distributive should contain daemon for this service, isn't it?

  3. Каждая группа выбирает в группе, в которую она вложена, одно устройство в качестве маяка. Таким образом устройства также предстают перед нами подобно XML-элементам, и к ним применимы понятия XPath: корень, ребенок, родитель, потомок, предок, брат (термин "path" не будем использовать, т.к. он вызывает когнитивный диссонанс с термином маршрут для сообщений). Адресом любого устройства является перечень идентификаторов маяков из всех предковых групп плюс идентификатор самого этого устройства. Т.е. адрес "резиновый", состоит из произвольного количества идентификаторов. Если корень одной иерархии устройств оказывается в пределах досягаемости группы другой иерархии, то две иерархии сливаются - либо в первой иерархии дистальнее этой группы, либо во всей второй иерархии изменяются адреса. Адреса изменяются в том конгломерате устройств, который численно меньше. Численно меньшим считается тот, у которого меньше вычислительная мощность (вычисляется функция f(x) mod k; f(x) еще не придумали; k - случайное число из диапазана [216...232]).

    1. Присоединяющееся устройство узнает идентификатор маяка от собственных братьев. Основывающее устройство спрашивает в родительской группе, какие её устройства не являются маяками; выбирает один из них как маяк, информирует его об этом, и спрашивает у него его адрес, чтобы вычислить свой. Правильно?
    2. Каждое устройство должно помнить всех своих детей чтобы сообщать им об изменении своего адреса, если это случится, не так ли?

    Each group choose one device as beacon in group, into which it is nested. Thus devices appear also before us like XML-elements, and notions root, child, parent, descendant, ancestor, sibling of XPath are appliable for them (we will not use term "path", because it make cognitive dissonance with notion route for messages). Address of any device is list of identifiers of beacons from all ancestor's groups plus identifiers of this device itself. I.e. address is "rubber", consists of arbitrary quantity of identifiers. If root of one hierarchy of devices occurs within reach of group of other hierarchy, two hierarchies merge - addresses are changed either more distant than this group in first hierarchy, or in whole second hierarchy. Addresses are changed in conglomerate of devices, which is numerically less. So conglomerate is considered numerically less, which has less computability power (function f(x) mod k is calculated; f(x) is not imagined just now; k is random number inside [216...232]).

    1. Appending device find identifier of beacon from own siblings. Founding device ask parent group about what its devices are not beacon; choose one of them as beacon, inform it about this, and asks its address to calculate own address. Right?
    2. Each device should remember all own children to inform them about changing of own address, if it will happen, isn't it?

  4. Дублет {hash(UID), адрес} хранится и обновляется в DHT. P.S. Понятие HashGNode, используемое ниже в QSPN для криптографии, возникает так. Результат хэш-функции от UID называется H. Устройство, чей адрес равен вычисленному H, называется HashNode, или nH. Группа, которой принадлежит HashNode - HashGNode, gH. Ближайшая к ней все еще активная группа - RoundedHashGNode, rgH; дублеты храняться на всех устройствах этой последней. Процесс копирования дублетов на устройство, примкнувшее к RoundedHashGNode, называется AndnaHook. Устройства регистрируют не более 250 дублетов (чтобы не перегружать маломощную аппаратуру типа сотовых телефонов), для 251-го предлагают выбрать другой UID.

    1. Чтобы защититься от подмены дублета крекером, устройство, регистрирующее дублет, должно по адресу из дублета запросить UID. Решение, предложенное в документации - 30-дневное хранение (andna.pdf, #3.7) - не решает поставленной задачи, не так ли?
    2. Количество байт |H|=const, в то время как количество байт в адресе переменно, он "резиновый". Какова функция отображения H в адрес?
    3. Пока еще не поздно (существует только альфа-версия продукта), унификация и экономия программистских усилий требует, чтобы для всех сервисов (SukuInter, ANDNA, кэширование web-страниц в DHT, раздавание и выкачивание частей файлов через P2P, электронная почта, луковичная маршрутизация, tor/carciofo, все другие будущие сервисы) был использован универсальный повторно используемый формат подобный XML (BinaryXML), а не изобретались частные форматы подобные ANDNA для каждого нового сервиса, не так ли? P.S. К сведению: на передаваемые таким образом xml-элементы удобно вешать триггеры, если складывать элементы в СУБД по мере поступления (см. http://sql50.euro.ru/sql5.19.2.pdf">sql50.euro.ru/sql5.19.2.pdf)

    Doublet {hash(UID), address} is stored and updated in DHT. P.S. Term HashGNode, used in QSPN for cryptography, appears so. Result of hash-function from UID has name H. Device, whose address is equal to calculated H, has name HashNode, or nH. Group, to which HashNode belongs - HashGNode, gH. Group, still active and nearest to HashGNode - RoundedHashGNode, rgH; doublets are stored in all devices of this the last group. Process of coping of doublets to device, appended to RoundedHashGNode, is named as AndnaHook. Devices register no more 250 doublets (to not overburden not powerful equipment like cellular phones), and seggest to imagine other UID for 251-th dublet.

    1. To protect against changing of doublet by cracker, device, registering doublet, should ask UID on base of address from doublet. Decision, proposed in documentation - 30-days storing (andna.pdf, #3.7) - does not solve task, isn't it?
    2. Quantity of bytes |H|=const, while quantity of bytes in address is variable, address is "rubber". What is the function to convert H into address?
    3. While it is not too late (only alpha version of product exists), unification and economy of efforts of software engineers require to use some universal repeatedly-used format like XML (BinaryXML) for all services (SukuInter, ANDNA, cashing of web-pages in DHT, scattering and downloading of parts of files via P2P, email, onion routing, tor/carciofo, all other future services), instead to invent particular format like ANDNA for each new service, isn't it? P.S. For information: it is comfortable to hang triggers on xml-elements, transfered so, if elements are entered into DBMS on arrival (see http://sql50.euro.ru/sql5.19.2.pdf">sql50.euro.ru/sql5.19.2.pdf)

  5. Несколько маршрутов, r называются множеством, R. Множество с одинаковым последним адресом называется классом эквивалентности, r . Класс эквивалентности с одинаковым первым адресом называется букетом. Наилучшим маршрутом B (обозначается заглавной буквой !) является кратчайший. Качество маршрута характеризуется числом REM, которое равно сумме REM для частей маршрута и увеличивается(!), когда качество улучшается. Каждое устройство является роутером. Таблица маршрутизации состоит из триплетов [адресат, сосед, REM] (таким образом в таблице не более 256+256*(N-1)=256*N триплетов, где N - количество уровней в иерархии устройств, т.е. размер таблицы растет как логарифм количества устройств) и не содержит альтернативных триплетов, указывающих дублирующие маршруты, т.к. обычно все дублирующие маршруты имеют общие части, и обрыв одного маршрута означает обрыв и альтернативных. Таблица состоит из внутренней карты, задающей марштуры к собственным братьям (её частью являются BNode map), и внешней карты, задающей маршруты ко всем предкам и их братьям.

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

    Several routes, r have name set, R. Set with identical last address has name class of equivalence, r . Class of equivalence with identical first address has name bouquet. The best route B (designated by capital letter !) is the most short. Quality of a route is characterized by number REM, which equal summ of REM for part of route and encreases(!), when quality improves. Each device is a router. Routing table consists of triplets [addressee, neighbour, REM] (thus there are no more 256+256*(N-1)=256*N triples in table, where N is quantity of levels in hierarchy of devices, i.e. size of table grows as logarithm of quantity of devices), and does not contain alternative triplets, specifing duplicated routes, because usually all duplicated routes have common parts, and break of one route means break of alternative routes too. Table consists of internal map, specifing routes to own siblings (BNode map is part of it), and of external map, specifing routes to all ancestors and their siblings.

    1. Probably, REM is not negative number - so what is the algorithm to calculate it?
    2. In external map, triplet for route to parent is enough, another triplets are redundant, isn't it (messages go not arising in hierarchy, but directly between sibling's groups; moving device can inform about re-organization of net simultaneously with updating of own dublet in DHT)?

  6. Распределение трафика между двумя устройствами по всем возможным маршрутам называется едкой маршрутизацией, CR; сами эти маршруты - едкими букетами, CRT; таблица маршрутизации, хранящая триплеты для всех возможных маршрутов - едкой таблицей. Линия связи, у которой выбрана вся пропускная способность, называется насыщенной.

    Distribution of traffic between two devices on all possible routes are named as caustic routing, CR; these routes themselves - as caustic bouquet, caustic routing tree, CRT; routing table, storing triplets for all possible routes - as caustic table. Link, whole bandwidth of which is already used, has name saturated.

  7. Существует два способа перестроения таблиц маршрутизации - OLSRD для мобильных устройств и QSPN для стационарных.

    There are two ways to reconstruct routing tables - OLSRD for mobile devices and QSPN for stationary ones.

Functioning along OLSRD

  1. временное сообщение: OLSRD должно быть изучено и описано здесь. Сайт olsrd.org (www.olsrd.org), на который ссылается документация, недоступен.

    temporary note: OLSRD should be studied and described here. Site olsrd.org (www.olsrd.org), to which documentation refers, is not available.

Functioning along QSPN

  1. Перестроение таблицы маршрутизации осуществляется служебными пакетами следующих разновидностей: tracer package (TP, T), acyclic tracer package (ATP), continuous tracer package (CTP), extended tracer package (ETP). TP, ATP, CTP записывают в себя пройденные адреса. ETP несет в себе таблицу маршрутизации. Все служебные пакеты подвергаются преобразованиям при прохождении устройств до достижения экстремального устройства. TP - преобразованию под названием "групповое правило": [11.22.1, 11.22.80, 11.22.35, 11.44.13, 55.32.20] -> [11.22.*, 11.44.13, 55.32.20] -> [11.*, 55.32.20]. ATP - под названием ациклическое правило: устройство удаляет пакет, если обнаруживает свой идентификатор в нем. CTP - преобразованию под названием "правило интересной информации": устройство удаляет пакет, если обрануживает дублирующийся переход (от устройства к устройству). Для перестроения своей таблицы маршрутизации каждое (!?) устройство порождает служебный пакет и передает его всем своим соседям, те размножают пакет и пересылают всем соседям дальше, таким образом устраивая наводнение (flood). Соответственно существуют TP-наводнение, ATP-наводнение, CTP-наводнение.

    1. Внутреннюю, внешнюю или обе карты несет в себе ETP?
    2. Подвергаются ли служебные пакеты преобразованиям при прохождении устройств _после_ достижения экстремального устройства?
    3. Существует ли ETP-наводнение как отдельное явление?
    4. Что отсутствует в сообщениях о реорганизации сети (см. вопрос Structure.5.2), чтобы сделать наводнения ненужными (i.e. Δ vs. flood)?
    5. Почему недостаточно выполнять наводнения из не-граничных устройств только в пределах группы, а из граничных - в пределах группы и в соседней группе (граничные устройства задерживают пакеты наводнения в своей группе до тех пор, пока наводнение в соседних не будут завершены)? Ведь за пределами групп и соседних групп служебные пакеты собирают одну и ту же информацию.

    Reconstruction of routing table is executed by service packages of the following varieties: tracer package (TP, T), acyclic tracer package (ATP), continuous tracer package (CTP), extended tracer package (ETP). TP, ATP, CTP write gone addresses into themselves. ETP carries routing table in itself. All service packages are subjected to transformation during passing via devices before achievement of extreme device. TP - to transformation under name "group rule": [11.22.1, 11.22.80, 11.22.35, 11.44.13, 55.32.20] -> [11.22.*, 11.44.13, 55.32.20] -> [11.*, 55.32.20]. ATP - under name acyclic rule: device removes package, if has found own identifier in it. CTP - to transformation with name "interesting information rule": device removes package, if has found duplicated hops (from device to device). To reconstruct own routing table, each (!?) device create service package and send it to all own neighbours, which duplicate package and send to all neighbours further, so making flood. Thus TP-flood, ATP-flood, CTP-flood exist.

    1. Internal, external, or both maps are caried in ETP?
    2. Are service packages subjected to transformation during passing via devices _after_ achievement of extreme device?
    3. Exist ETP-flood as separate phenomena?
    4. What is absent in messages about re-organization of net (look at question Structure.5.2) to make floods unnecessary (i.e. Δ vs. flood)?
    5. Why it is not enough to perform floods from not-border devices only inside group, and from border devices - inside group and in neighbour group (border devices delay service packages of own group, until flood in neighbour group will be finished)? You see, service packages collect the same information outside groups and neighbour groups.

  2. Для перестроение группы в ней выделяется CoordinationNode; кто из группы им будет - устройства договариваются по принципу P2P. Устройства перемещаются из группы в группу последовательно, по одному, регистрируясь в CoordinationNode; процесс перемещения(!) называется сериализацией. Чтобы не одна группа не стала насыщенной, т.е. для постоянного существования возможности перестроения сети, все группы поддерживаются в состоянии с равным количеством устройств в каждой группе.

    1. Из каких групп или из каких устройств состоит communication vessel?
    2. Что такое компактная группа?
    3. Как вычисляется attraction value?

    To reconstruct group, CoordinationNode is assigned in it; who from group will be it - devices decide by principle P2P. Devices are transfered from group into group consecutively, by one, with registration in CoordinationNode; process of transfer (!) has name serialization. That no one group becomes saturated, i.e. for permanent existence of possibility to reconstruct a net, all groups is supported in state with equal quantity of devices in each group.

    1. Of which groups, or of which devices are consist communication vessel?
    2. What is the compact group?
    3. How attraction value is calculated?

  3. Для HNode вместе с идентификатором генерируются открытый PubKey и закрытый PrivKey ключи по алгоритму RSA. Устройство, чей адрес равен hash(PubKey), называется CounterNode, cr; оно рассматривается в теории вместо HashNode. На практике вместо HashGNode применяется CounterGNode. В него записываются: PubKey новичка; дуплет, подписанный PrivKey новичка; счетчик, содержащий количество устройств, зарегистрировавших дуплет. TP содержит адреса, подписанные PrivKey устройств, через которые TP прошел.

    1. Зачем нужен счетчик?
    2. Вставка информации в CounterGNode происходит в две итерации: первая зановит дублеты со счетчиками, равными 1; вторая изменяет все счетчики?
    3. Содержимое ATP, CTP, ETP также подписывается PrivKey?

    Open key PubKey and close PrivKey are generated by algorithm RSA for HNode together with identifier. Device, whose address equal hash(PubKey), has name CounterNode, cr; it is considered in theory instead of HashNode. On practice, CounterGNode is used instead of HashGNode. PubKey of HNode; dublet, signed by PrivKey of HNode; counter, containing quantity of devices, registered dublet, are written into CounterGNode. TP contains addresses, signed by PrivKey of devices, via which TP has gone.

    1. What counter is necessary for?
    2. Inserting of information into CounterGNode occurs in two iterations: the first enters dublets with counters, equal 1; the second changes all counters?
    3. Content of ATP, CTP, ETP is signed by PrivKey too?

 
CD: 5ms