DRT (Dynamic Routing Table – dinamikus útválasztási táblázat)

The DRT is a novel concept utilized in swarm technology to maintain P2P connections. In this approach, group members establish a graph of nodes, each identified by a unique hash, and these nodes must be interconnected.

Therefore, a structural framework is required that accomplishes the following objectives:

1. Mindig maximalizálja a csatlakoztatott csomópontok számát.

2. Minimalizálja az üzenetküldési időt.

3. Csökkenti a kapcsolatok számát a társak között.

4. Minimális számítási erőforrást igényel.

Számos megoldást javasoltak a célok eléréséhez:

1. Each node is connected to the next node, resulting in only \(N\) connections. However, this approach is not efficient for transmitting messages since the message must traverse all peers one by one.

2. Every node is connected to all other nodes, leading to \(N^2\) connections. This configuration is effective for message transmission but demands more resources. This option will be selected for the first version.

3. Az ütemterv-grafikon lefedettségének maximalizálása az optimális mozgástervezés érdekében (Maximizing the Coverage of Roadmap Graph for Optimal Motion Planning) című cikk bemutatsa egy másik megoldás, amely optimális mozgástervezési lefedettséget kínál. de jelentős számítási számításokat tesz szükségessé.

4. Utilizing the DHT algorithm for the routing table, which effectively addresses all four points and is already employed by Jami in their UDP implementation.

Ezenkívül a csatornák számának optimalizálása érdekében a ConnectionManager egy aljzatot foglal le, amely lehetővé teszi a csatornák multiplexelését egy adott kivonattal. Ez azt jelenti, hogy ha több fájlt kell továbbítani, és valakivel csevegni kell, akkor csak egy csatorna kerül felhasználásra.

A definíciók

Jelölések:

• \(n\): Node identifier

• \(N\): Number of nodes in the network

• \(b\): Configuration parameter

Feltételek és fogalmak:

• Mobil csomópont: A hálózat egyes eszközei dinamikus kapcsolatot tudnak létrehozni, lehetővé téve számukra a gyors csatlakozást és leválasztást az akkumulátorhasználat optimalizálása érdekében. Ahelyett, hogy egy dedikált P2P (peer-to-peer – ponttól-pontig) csatornát tartana fenn ezekkel az eszközökkel, a protokoll a meglévő csatornák használatát választja, ha elérhető, vagy push-értesítésekre támaszkodik az adatok továbbítására. Ezek a csomópontok egy dedikált jelzővel vannak megjelölve a protokollban.

• Bucket (vödör): Ez az osztály a kapcsolatok manipulálására és tárolására, valamint a csomópontok állapotának kezelésére szolgál (csatlakozó, ismert, mobil). Az ismert csomópontok akkor használatosak, ha a kapcsolat egy csomóponttal offline állapotba kerül.

• Routing Table (útválasztási táblázat): Vödörök rendszerezésére szolgál, lehetővé téve a legközelebbi csomópontok keresését, és kapcsolatot létesítve a swarm manager és a DHT (Distributed Hash Table – elosztott kivonat-táblát) között.

• Swarm Manager (raj-kezelő): Ez az összetevő felelős a belső logika kezeléséért és a hálózaton belüli kapcsolatok elosztásának felügyeletéért.

• Swarm Protocol (raj-protokoll): A társak közötti adatcserére szolgál. A következő típusú adatok cserélhetők:

  • Request (Kérés) (pl. FIND (KERESÉS)): Query | num | nodeId (Lekérdezés | szám | csomópont Identitás)

  • Response (Válasz) (pl. FOUND (TALÁLT)): Query | nodes | mobileNodes (Lekérdezés | csomópontok | mobilCsomópontok)

  • Message (Üzenet): Version | isMobile | Request or Response (Verzió | ezMobil | Kérelem vagy Válasz)

Algoritmusok összehasonlítása

Chord (Akkord)

In a Chord network, each node is associated with a unique key computed using either the SHA-1 or the MD5 hash function. The nodes are organized into a ring in increasing order, and each node maintains a routing table that stores information about its nearest nodes. Each entry \(i\) in the routing table contains nodes with keys such that \(\mathrm{hash} = (n + 2i - 1) \mod 2^m\), where \(m\) represents the number of bits in the key.

Minden csomópont tisztában van utódjaival és elődeivel az akkordhálózatban.

Az adatok lekéréséhez egy csomópont kérést küld a közvetlen utódjának. Ha a csomópont rendelkezik a szükséges kulccsal, válaszol; ellenkező esetben a kérelmet továbbítja saját jogutódjának.

Amikor új csomópontot ad hozzá a hálózathoz, a csomópont üzeneteket küld a többi csomópontnak, hogy frissítse az útválasztási táblákat és biztosítsa a megfelelő integrációt.

Ha egy csomópont elérhetetlenné válik, frissítenie kell az útválasztási táblázatát, hogy a forgalmat más elérhető csomópontokon keresztül irányítsa át.

The distance between two nodes is: \(d(n_1,n_2) = (n_2-n_1) \mod 2b\)

The routing table size is: \(\log(N)\)

The number of hops to get a value is: \(\log(N)\)

Sources:

1. Liben-Nowell, David; Balakrishnan, H.; Karger, David R. “Analysis of the evolution of peer-to-peer systems.” ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (2002).

2. Liben-Nowell, David, Balakrishnan, H.; Karger, David R. “Observations on the Dynamic Evolution of Peer-to-Peer Networks.” International Workshop on Peer-to-Peer Systems (2002).

3. Stoica, Ion; Morris, Robert Tappan; Karger, David R; Kaashoek, M. Frans; Balakrishnan, H. “Chord: A scalable peer-to-peer lookup service for internet applications.” Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (2001).

Pastry (Péksütemény)

In a Pastry network, each node is associated with a 128-bit identifier generated from a hashing function. Pastry is commonly used with IP addresses, and nodes are organized in a ring with increasing order. The routing table is divided into segments, typically determined by \(128 / 2b\), where \(b\) is typically set to \(4\), and IP addresses are placed within these segments.

Ha egy üzenetet egy levélcsomóponthoz kell továbbítani, az közvetlenül a címzettnek kerül elküldésre. Ha az üzenetet nem levélcsomópontnak szánják, a hálózat megpróbálja megtalálni a legközelebbi csomópontot, és továbbítja az adatokat annak a csomópontnak további továbbítás céljából.

Distance is: \(d(n_1,n_2) = (\mathrm{prefix}(n_2) - \mathrm{prefix}(n_1)) \mod 2b\)

Size of the routing table: \((2b - 1)\log_{2}(N)\)

Number of hops to get a value: \(\log_{2}(N)\)

where \(b\) is generally \(2\).

Sources:

1. Tirée de Castro, Miguel; Druschel, Peter; Hu, Y. Charlie; and Rowstron, Antony Ian Taylor. “Exploiting network proximity in peer-to-peer overlay networks.” (2002).

Kademlia

The Kademlia network algorithm is used by BitTorrent and Ethereum networks. In this scheme, each node is assigned a 160-bit identifier, and nodes can be organized in a ring with increasing order. Data is stored in the nearest nodes. However, the routing table employs a binary tree structure with \(k\)-buckets (where \(k\) represents the number of nodes in each bucket) to store information about the nearest nodes.

Amikor egy csomópont csatlakozik a DHT-rendszerhez (Distributed Hash Table – elosztott kivonat-táblát), megkísérli feltölteni az útválasztási táblát úgy, hogy a felfedezett csomópontokat a megfelelő gyűjtőhelyekbe illeszti. Ha egy vödör megtelik, a csomópont figyelmen kívül hagyható, ha túl távol van; Ha azonban a vödör a legközelebbi elérhetőt képviseli, akkor az új csomópont befogadása érdekében két részre lesz osztva. Új csomópont hozzáadásakor a rendszer lekérdezi annak útválasztási tábláját, hogy adatokat kapjon a legközelebbi csomópontokról.

Egy adott érték lekéréséhez egy csomópont kérést küld a legközelebbi csomópontnak a megfelelő kivonattal.

Distance is \(d(n_1, n_2) = n_1 \oplus n_2\)

Size of the routing table: \(K \log_{2}(N)\)

Number of hops: \(\log_{2}(N)\)

A végrehajtás

A Jami indításakor minden beszélgetés elindítja az útválasztó tábla létrehozását. A kezdeti lépés az első csomóponttal való kapcsolat létrehozása a többi csomóponttal való összehangolás megkezdéséhez. Ez a folyamat „rendszerindítás” (angolul: bootstrapping) néven ismert, és két fő részből áll.

The first part involves retrieving all known devices in a conversation. This is accomplished by checking for known certificates in the repository or verifying the presence of certain members on the DHT (Distributed Hash Table). If a TCP connection already exists with any device in the conversation, it will be utilized. Additionally, known nodes are injected into the routing table. If no connection is successful, attempts to find new devices by performing a „GET” request on the DHT to get devices for each member.

Az útválasztási tábla ezt követően minden alkalommal frissül, amikor esemény történik egy csomóponton.

During routing table updates, the component will attempt to establish connections with new nodes if necessary. The decision to connect to new nodes is determined by the following conditions:

• For the nearest bucket, a connection attempt is made if \((\mathrm{maxSize}(\mathrm{bucket}) - \mathrm{connectedNodes} - \mathrm{connectingNodes}) > 0\).

• For other buckets, a connection is initiated if \((\mathrm{maxSize}(\mathrm{bucket}) - \mathrm{connectingNodes}) > 0\).

A különbség abban rejlik, hogy a legközelebbi vödör esetében a cél az, hogy szükség esetén megkíséreljük a vödrök szétválasztását, miközben kompenzáljuk a többi kanál megszakadásait. Ez elengedhetetlen a legközelebbi csomópontok ismeretének fenntartásához.

Új csomóponthoz való csatlakozáskor a rendszer egy „KERESÉS”(FIND) kérést küld a közelben lévő új azonosítók felderítésére és az összes mobil csomópont azonosítására. Ezt követően tíz percenként elküldik a „KERESÉS” (FIND) kérést, hogy az útválasztási tábla naprakész legyen.

A kódbázisban ezért a folyamatért felelős elsődleges osztály a SwarmManager (Rajkezelő), és a rendszerindítási fázist a beszélgetés szakasza kezeli.

Építészet

Performance analysis

Eszközök

To validate the implementation and performance of the DRT component, several tools have been developed and are located in daemon/tests/unitTest/swarm, including swarm_spread, bootstrap, and more.

To interpret the results, the following tools are utilized:

• gcov a tesztlefedettség elemzéséhez.

• ASan, hogy ellenőrizze a memóriaszivárgást és a kupac túlcsordulást.

• gdb a belső struktúrák hibakereséséhez.

While the major focus is on unit tests, for performance analysis, swarm_spread is relied on to assess various aspects, including:

• Az üzenettovábbításhoz szükséges ugrások száma.

• A csomópontonként fogadott üzenetek száma.

• Az egyes csomópontok által fogadott legfeljebb és legalacsonyabb üzenetek meghatározása.

• Az összes csomóponthoz üzenet továbbításához szükséges ismétlés kiszámítása.

• Üzenetfogadási idő mérése.

Eredmények

Jövőbeli munka

1. Dynamic bucket size limit to get different bucket sizes depending on the size of the routing table.

2. Declining some connections to speed up the transmission a bit.