-- Note: You are invited to update the wiki with the text provided in this email. --
I've finally read at length the DART paper (http://dart.cs.ucr.edu/). Initially, I hoped to find some new techniques that would greatly outperform Netsukuku. However, this is not the case. It seems that Netsukuku and DART are very similar, but more features (and documentation) are available in Netsukuku (f.e. P2P over Ntk, ANDNA, Viphilama). Luckily enough, the reading of the DART paper has inspired a new optimisation for ANDNA, and for the Network Splitting problem (see below). In the following text, "they" will refer to the DART's authors. 1) The topology structure is essentially the same: replace "groupnode" with "subtree" and require 2 nodes per gnode (not 256 as it is in ntk), in this way you get their configuration. (Btw, sometimes in order to represent the gnode configuration of the net, it is easier to draw gnodes as trees). 1.1) The allocation method for joining nodes (hooking phase) is the same: a node gets the IP from the largest unoccupied gnode. 1.2) Their Prefix Subgraph Constraint is equivalent to the Netsukuku requirement that "Gnodes must be internally connected" 2) About the routing mechanism, they say """ PeerNet uses a distance vector approach in updating its routing tables. Although link state routing is also an option, we choose distance vector for its low overhead, low computational cost per router, and ease of implementation. """ However, I haven't found a detailed description of their routes update system. Again, the ETP of the QSPN is essentially a Distance Vector routing mechanism (see http://en.wikipedia.org/wiki/Distance-vector_routing_protocol ) [TODO: explain in qspn.pdf why the ETP can be regarded as a DV routing] About the count-to-infinity problem they say: """We will now discuss how we detect and effectively avoid routing loops, which are a concern to all Distance Vector based protocols. [...] The key idea here is that a path should not enter the same address subtree twice.""" What they propose is exactly the use of Tracer Packets with the addition of the Acyclic Rule, which is used in the ETP: """If the ID of the node C is already present in the received ETP, then C immediately drops the ETP and skips all the following steps4""" (http://netsukuku.freaknet.org/doc/main_doc/qspn.pdf paragraph 4.1 Extended Tracer Packet ) 3) About the problems that are named in topology.pdf as "Uniform gnodes", and "Compact gnodes" they say: """ We are currently evaluating techniques to find a good balance between tree balancing and interarea connectivity. Address tree balancing: if a particular area becomes congested, using up all locally available address space, new nodes that try to obtain an address may be unable to do so. We would like nodes to proactively migrate in the tree in order to balance it. Maximizing the intra-area connectivity: we want to select addresses in such a way that nodes within an area are well connected by physical links.""" However, they don't present any method that allows to resolve these problems. In Netsukuku, the Communicating Vessel system is used for the first problem. While for the second, a proposed solution is the Compact gnodes system". (See 7.1 Uniform gnodes, 7.3 Compact gnodes in topology.pdf) The Communicating Vessel system might be the current substantial difference between DART and Netsukuku (excluding other features as P2P Over Ntk, Viphilama). 4) Replace "hostname" with "node identifier", and "ANDNA" with "node lookup" and you get their method to resolve the routing address (IP) of a node from an identifier (f.e. its hostname). Note: they plan to use Internet IPs as identifiers. In Netsukuku hostnames are arbitrary strings chosen by the users. Even here, their technique is essentially the same to that of ANDNA: compute the hash of the hostname, find the node with the most similar address to the hash. (however they use xor, ANDNA uses |x-y|) 2.1) They propose a good solution to update the IP associated to an hostname, in a "local" manner. Here below I describe a modified version for Netsukuku. I name it as "NTK_RFC 0015 -- Local ANDNA". This solution is based on the following assumption: it is more probable that a node changes its lower gnodes than its higher ones. F.e, say that the netsukuku IP of the node is 11.22.33, that is 33 is the ID of the gnode of level 1 22 is the ID of the gnode of level 2 11 is the ID of the gnode of level 3 Then, the following changes: 11.22.33 becomes 11.22.77 11.22.33 becomes 11.22.55 11.22.33 becomes 11.22.16 are more probable than the following: 11.22.33 becomes 77.22.33 11.22.33 becomes 11.88.33 11.22.33 becomes 99.88.33 We call this assumption as the "Local IP Change assumption". Considering this, we might want to split the IP and store _separately_ the split parts using ANDNA, in a local manner: Suppose the node N wants to register the hostname "myhostname". Let's say a.b.c.d is the hash of "myhostname". Let's say 11.22.33.44 is the Ntk IP of N. Do the following: Contact the node 11.22.33.d, and tell it to store the pair (11.22.33.44, "myhostname") Contact the node 11.22.c.d, and tell it to store the pair (11.22.33, "myhostname") Contact the node 11.b.c.d, and tell it to store the pair (11.22, "myhostname") Contact the node a.b.c.d, and tell it to store the pair (11, "myhostname") Suppose N changes its IP from 11.22.33.44 to 11.22.30.40. Do the following to update the hostname: Contact the node 11.22.33.d, and tell it to store the pair (11.22.33.40, "myhostname") Contact the node 11.22.c.d, and tell it to store the pair (11.22.30, "myhostname") Halt. Suppose M wants to resolve "myhostname". Do the following: Calculate the hash a.b.c.d of "myhostname" Contact the node a.b.c.d and ask it about "myhostname". It receives the answer from a.b.c.d and has thus completed the resolution. In order to answer, the node a.b.c.d does the following: It retrieves the (11, "myhostname") pair from its database. It contacts the node 11.b.c.d and asks it about "myhostname". It receives the answer from 11.b.c.d and sends it back to M. In order to answer, the node 11.b.c.d will do the following: It retrieves the (11.22, "myhostname") pair. It contacts the node 11.22.c.d and asks it about "myhostname". It receives the answer from 11.b.c.d and sends it back to a.b.c.d. In order to answer, the node 11.22.c.d will do the following: It retrieves the (11.22.33, "myhostname") pair. It contacts the node 11.22.33.d and asks it about "myhostname". It receives the answer from 11.22.33.d and sends it back to 11.b.c.d. In order to answer, the node 11.22.33.d will do the following: It retrieves the (11.22.33.44, "myhostname") pair, __which is the complete IP__. It sends the IP back to 11.22.c.d. The procedure is thus complete. In all the above procedures, the "approximation method" will be used. F.e., if the node a.b.c.d doesn't exist, than the node a'.b'.c'.d' will be used, where a'.b'.c'.d' is the closest available IP to a.b.c.d. These are some advantages of the presented method: 1) Faster hostname updates. As shown above, if a node changes its IP it will updated only the changed parts in an efficient way. This fact mitigates the overhead posed by the Communicating Vessel System, Network Splits and Network merging. 1.1) It is more mobile-oriented: the nodes can change their IP without worrying to much about hostname updates. However, this doesn't automatically make Netsukuku mobile compliant. 1.2) For the same reason as above, this method could mitigate the effects of using a "Compact gnodes" system. (See topology.pdf, paragraph 7.3) 2) Hostnames of "local" nodes can be resolved faster: suppose 10.20.30.40 wants to resolve "myhostname", and suppose that "myhostname" is associated to the IP "10.20.33.44". suppose that a.b.c.d is the hash of "myhostname" 10.20.30.40 does the following at the same time, or in sequentially: 1. it tries to resolve "myhostname" using 10.20.30.d 2. it tries to resolve "myhostname" using 10.20.c.d 3. it tries to resolve "myhostname" using 10.b.c.d 4. it tries to resolve "myhostname" using a.b.c.d In this example, the first try will fail, because the nodes keeping the hostname association are: 10.20.33.d 10.20.b.d 10.c.b.d a.c.b.d However, the subsequent tries will succeed, and it is more probable that the second will be the first to send back the answer, in fact, the node 10.20.c.d is nearer to 10.20.30.40 than the nodes 10.b.c.d, a.b.c.d (if b!=20 and a!=10). 3) SNSD could be improved with this method, using the same insights. TODO: - see if the Communicating Vessel System isn't in conflict with the "Local IP Change assumption" - add this RFC in the wiki and in andna.pdf 5) Quoting the DART paper: """We envision tunneling through the Internet to interconnect disconnected PeerNet networks initially and when available. In addition, we want to develop protocols and tools to facilitate the communication be- tween PeerNet and Internet nodes.""" (http://dart.cs.ucr.edu/PeerNet_IPTPS_03.pdf) In Netsukuku this has been already planned, see Viphilama and http://netsukuku.freaknet.org/doc/main_doc/inetntk.pdf 6) In order to solve the Network Splitting and Merging problems they assign a network ID to each groupnode of each level. In Netsukuku, the network ID is shared by all the nodes, thus the situation is simplified (see 7.2 Internal connection, topology.pdf) and requires less overhead. However, their solution is safer. In fact, the following problem might arise in Netsukuku: Suppose that the followting a1 -- a2 -- a3 -- a4 -- a5 -- a6 is the configuration of a network. All the nodes shares the same network id (say 1234). Suppose the network splits: a1 -- a2 -- a3 a4 -- a5 -- a6 and that the two network evolves separately. The two networks still shares the same network id, because the network id is generated only when a new network is created. And this is not the case. Since the two nets evolve in a separate manner, it might be the case that a2 chooses the same ip of a5. Suppose that the two network joins: a1 -- a2 -- a3 -- a4 -- a5 -- a6 Now the problem is: since the network id is the same of all the node a1,...,a6, the nodes won't be aware of the conflict between a2 and a5. TODO: update the "7.2 Internal connection" considering this problem. TODO: Given the great similarity between Ntk and DART, it should be possible to use their performances results, which seem quite good. Final considerations: Netsukuku has always been developed independently from DART. The great similarity between DART and Netsukuku might be explained with one of the following hypothesis: 1) When someone wants to solve the Netsukuku-DART problem, i.e. developing a scalable Ad-Hoc network, the Netsukuku-DART solution is the first and easiest solution that can be found. 2) The Netsukuku-DART solution is a necessary way to develop a scalable Ad-Hoc network. 3) ? Best regards. -- :wq! "I don't know nothing" The One Who reached the Thinking Matter '.' [ Alpt --- Freaknet Medialab ] [ GPG Key ID 441CF0EE ] [ Key fingerprint = 8B02 26E8 831A 7BB9 81A9 5277 BFF8 037E 441C F0EE ]
pgp7XSSDYSKZ7.pgp
Description: PGP signature
_______________________________________________ Netsukuku mailing list [email protected] http://lists.dyne.org/mailman/listinfo/netsukuku
