Wow, that makes me wish more of the protocol docs I had to read were written by mad Italian anarchists.
As far as I can tell it's a hierarchical path-vector routing protocol. There are up to 256 nodes per group, up to 256 level 1 groups per level 2 group, etc. The address space overlaps with the IP address space in order to make use of existing software, so for IPv4 there are up to 4 levels, and for IPv6 there are up to 16. Each node knows the shortest path to every other node in its group, and the shortest path to every other level 1 group, every other level 2 group etc. Paths within a group are discovered by a periodic broadcast protocol with two phases, qspn_close and qspn_open. When a node first receives a copy of the qspn_close packet it "closes" the link on which it received the packet and sends out copies of the packet on all its other links. If it receives additional copies (due to the crossing letters effect) it closes those links as well. If all of a node's links are closed it is an "extreme node", and it starts a qspn_open broadcast. Each qspn_open is flooded through the whole group, with the path it follows being recorded in the packet. In this way every node learns the shortest path to every other node. The protocol uses somewhere between O(m) and O(nm) messages. The best case is a chain or a ring, with two extreme nodes. The worst case is a star, with n-1 extreme nodes. On average QSPN is more efficient than traditional periodic broadcast protocols, which require O(nm) messages for all topologies. QSPN broadcasts occur periodically, but only if the topology has changed. A qspn_close broadcast can be started by any node that needs to report a topology change. Nodes within a group try to keep their clocks synchronised in order to start the qspn_close phase at the same time. There's some stuff about contiguous groups of starters which I don't understand. The same protocol is used to discover paths between groups, but in this case the border nodes in a group must agree on whether the group is an extreme group (hi Echelon), so each time a border node closes a link it informs the other border nodes in its group. There's a problem if two groups choose the same group ID and later discover one another. The proposed solution involves clock synchronisation but I don't understand how it solves the problem. ANDNA is a decentralised naming service, basically a DHT built on top of an unstructured network. To look up a name you hash the name and contact the node with the closest address to the hash, and it tells you the address associated with the name. Mappings are cached on intermediate nodes to relieve hotspots. When you register a name you must supply a public key, and updates to the mapping have to be signed with the corresponding private key - intermediate nodes can perform a man in the middle attack. To mitigate the problem of name squatting there's a queue for each name, and the first five mappings in the queue are returned. There's also a counter that keeps track of how many names each public key has registered, although it seems like it would make more sense to keep track of the number of names per node - but even then there's no real security because an attacker can invent any number of nodes. Cheers, Michael
