Kademlia-directed ID-based Routing Architecture (KIRA)

3.1. Addressing, NodeIDs and the XOR Metric

Every KIRA instance uses a single NodeID as its address. The NodeID is taken from a larger unstructured address space [0..2^B-1] (typically B=112). KIRA uses the XOR (logical exclusive or) metric in this address space to define the distance between two NodeIDs X and Y (see also [Kademlia2002]). The distance function d(X,Y)= X XOR Y is interpreted as integer and fulfills all properties of a metric (d(X,Y)>=0, and d(X,Y)=0 <=> X=Y; d(X,Y)=d(X,Y); as well as the triangle inequality d(X,Y)<=d(X,Z)+d(Z,Y)). This distance function largely corresponds to a prefix bit distance metric d_p(X,Y) = B-lcp(X,Y), where lcp(X,Y) denotes the length longest common prefix in bits. The XOR metric is finer than the d_p(X,Y) metric though, because when there are X,Y, and Z with d_p(X,Y)=d_p(Y,Z)=d_p(X,Z), the XOR metric can uniquely determine whether Y or Z are closer to X. More generally speaking, for a given distance d(X,Y)=d there exists exactly one Y so that d(X,Y)=d. This property is important since it allows to unambiguously determine which NodeID is ID-wise closer to a given other NodeID and it provides the basis for KIRA's loop-freedom. Note that the ID space with this metric is not cyclic (i.e., a node with a very small NodeID is not close to a node with a very large NodeID).¶

The XOR metric defines an overlay structure across all KIRA nodes in the ID space: KIRA nodes establish logical connections with their ID-wise closest overlay neighbors (which are typically different from the physical neighbors) with respect to the XOR metric as distance metric, i.e., the ID-wise closer neighbors have a smaller distance according to XOR. KIRA uses this metric to determine the next KIRA node that a KIRA message is forwarded to in order to reach a certain destination NodeID. R²/Kad messages are forwarded by using source routing between overlay hops.¶

In addition to NodeIDs, KIRA can use any ID from the ID space as destination address. Typically, names of objects can be hashed to result in a key value, which is called Resource ID. In this case, the ID-wise closest KIRA node will be found as responsible node for storing a value (or a referral) for this key. This makes it possible to provide an integrated DHT for name-to-NodeID registration and lookup.¶

3.2. NodeID Creation

NodeIDs are randomly generated and are taken from a 112 bit address space. Future versions of this specification will detail an algorithm to create self-certifying NodeIDs as using certain hash functions from a public key. NodeIDs are unique with high probability. However, in case two nodes possess the same NodeID, protocol mechanisms can be used to detect this situation and the conflict can be resolved by letting one side generate a new NodeID. Depending on a KIRA node's capabilities, NodeIDs (together with other protocol parameters) may be stored in non-volatile memory so that nodes keep their NodeID even after restart. Other KIRA nodes may choose to generate a new NodeID on every restart.¶

3.3. Routing Table

The entries in the routing table (RT) are called 'contacts'. Contact data contains the NodeID of the contact as well a set of discovered paths that lead to this contact (besides other node state and attributes). A path to a contact is stored as path vector that contains a complete sequence of NodeIDs, which can be traversed to reach the contact. Except for contacts in its routing table, a KIRA node does not know paths to other destinations, but they can be discovered by using a recursive overlay routing strategy: a KIRA node source routes a packet to the contact (using the known path) that is the ID-wise closest to the destination ID according to its routing table. The next overlay hop performs the same action until the destination node is reached. After the initial discovery phase, only PNs and some contacts from the 3-hop physical neighborhood are stored in the routing table.¶

R²/Kad's efficiency and flexibility is closely related to its routing table. It is structured as tree of k-buckets as in [Kademlia2002]. A k-bucket in the routing table contains a list of (at most) k contacts in distance between 2^i and 2^{i+1} (i.e., the bucket's range, where 0<=i<112) from this node. Usually, k>=20 is constant and the same for all buckets and nodes, but it can also be varied per node (k=40 is RECOMMENDED as default for R²/Kad). Buckets at deeper levels share more prefix bits with the node's own ID, however, buckets for small values of i are generally empty as no appropriate nodes exist in this address space. Thus, the highest bucket (depth 1) contains contacts from half of the ID space whose highest NodeID bit differs from the node's ID, whereas the deepest buckets contain all nodes that are ID-wise closest to the node (i.e., the ID-wise closest overlay neighbors).¶

If KIRA node X learns a new contact Y, it puts it into the corresponding k-bucket b_l in case it still has capacity left. The bucket index l is determined by calculating the common prefix length between X and Y (number of high-order zero bits of d(X,Y)). If the bucket contains k entries already, it is split into two new buckets (and the contained entries moved to them accordingly) in case X falls into the bucket's range. Otherwise, a selection algorithm determines whether the new contact should replace an existing entry in this bucket. In our case we use Proximity Neighbor Selection (PNS) so that contacts with shorter path lengths are preferred. In case path lengths are equal, nodes with a higher degree are preferred as this results in shorter paths. An additional mechanism for path selection improves path diversity and prevents route flapping: in case an alternative path of equal length has been discovered for an already known contact, this path replaces the previous path only if the hash sum of the path elements is closer to the node's own NodeID. Due to the uniqueness property of the XOR metric, the path selection will always unambiguously converge to a unique path. Physical neighbors are kept in special buckets that have no capacity limit, i.e., they will never be preempted. In general, routing also works without this PN buckets extension of [Kademlia2002], but the resulting stretch will be slightly higher.¶

X identifies its closest known contact in its RT by locating the k-bucket that corresponds to the longest matching prefix of destination Z with its own NodeID X by using d(X,Z). It then selects a contact with the shortest path vector from within the bucket; this is called Proximity Routing (PR). The XOR metric is used to uniquely select the closest contact if all paths have equal length or if no prefix-wise progress can be made by the bucket (e.g., it is the deepest bucket).¶

3.4. Node Startup and Vicinity Discovery

KIRA nodes generate their NodeID first (see Section 3.2). After that they start an initial discovery phase to explore their physical vicinity. After that, a join procedure and continuous discovery are periodically repeated. To let the node stay connected to its overlay and to improve the quality of discovered routes.¶

In its initial discovery phase, a KIRA node discovers its physical adjacencies, i.e., its physical neighbors (PNs) that can be directly reached via link-local communication on one of their network interfaces. KIRA nodes periodically send PNHello messages to a well-known link local multicast address ALL-KIRA-NODES, and receiving nodes may reply with a PNDiscoveryReq to set up an adjacency. This PNDiscoveryReq MUST be answered by a PNDiscoveryRsp to establish an adjacency. The protocol exchange ensures that bidirectional communication is possible between directly adjacent nodes. PNs may be put into the PNTable either after receiving a PNDiscoveryReq as answer to a transmitted PNHello or after receiving a PNDiscoveryRsp as answer to a transmitted PNDiscoveryReq. The PNTable contains a mapping from NodeID to the link local unicast address of the PN. This address is either taken from the source address of the PNDiscoveryReq or the PNDiscoveryRsp respectively.¶

KIRA nodes also discover all nodes in their 3-hop physical neighborhood to populate their routing table, but the 2-hop vicinity is fully stored in a local graph structure. The latter is used to precompute PathIDs for the 2-hop vicinity. PNDiscoveryReq and PNDiscoveryRsp messages contain a list of physical neighbors so that all PNs of PNs will be learned, i.e., the 2-hop vicinity. Additionally, all nodes in the 2-hop vicinity are queried for their PNs by using a QueryRouteReq. QueryRouteReq/QueryRouteRsp messages are used to get PNs or RTable objects from nodes in the vicinity. Depending on their NodeID, nodes from the 3-hop vicinity will be stored as contacts into the routing table.¶

A KIRA node continues to populate its routing table by sending FindNodeReq messages to certain nodes and also to randomly chosen destinations (i.e., a randomly chosen ID from the NodeID space, a KIRA node does not need to exist for the chosen ID, the FindNodeReq will simply end at the KIRA node that is ID-wise closest to the destination ID). FindNodeRsp messages return a set of contacts that are ID-wise closest to the destination NodeID from the viewpoint of the responding KIRA node. The returned information is analyzed whether it can improve the local routing table, e.g., new and 'better' contacts or 'better' paths to already known contacts.¶

3.5. Join Procedure

As result of the vicinity discovery, all PNs of X and some nodes within its 3-hop radius will populate X’s RT. However, in order to get network connectivity and to contribute to connectivity, the node needs to find its ID-wise closest overlay neighbors and make itself known to them. Thus, to join the network KIRA node X simply "searches" for the k closest nodes to its own NodeID: X sends a FindNodeReq for its own NodeID X and the closest neighbor replies with FindNodeRsp. This is repeated with a limited exponential backoff in order to detect or heal any network partitioning. In case node X finds itself in situations where it needs to respond with "Dead End" Error messages to FindNodeReqs, it resets the backoff timer again, because it may be a hint for network partitioning or other inconsistencies. In order to let a joining node X quickly learn all existing ID-wise closest overlay neighbors, X sends a QueryRouteReq to every newly learned contact that enters X’s currently deepest k-bucket. The queried contact replies with a QueryRouteRsp returning its RT entries for the k closest contacts to node X. The so returned contacts will very likely also fall into X’s deepest bucket, possibly leading to a further split of its deepest bucket. Therefore, X will quickly populate its set of ID-wise closest overlay neighbors, which are needed for consistent overlay connectivity.¶

3.6. Path Discovery

Consider the exemplary topology in Figure 2. Assume node X needs to send a message to node Z. In case Z is a known contact of X, a path vector is stored already in the routing table that can be used for strict source routing in order to reach Z. Otherwise, a path to Z must be discovered using ID-based overlay routing. R²/Kad uses a recursive version of Kademlia (hence its name Routing with Recursive Kademlia – R²/Kad). The Path Discovery procedure uses a request/response message pair, FindNodeReq/FindNodeRsp. In this example, assume that X identifies its contact Y (learned from PN A) as next (ID-wise closest) overlay hop toward Z. In order to discover a path to Z, X creates a FindNodeReq message that contains destination NodeID Z and source route r=⟨X, A, Y⟩ using path vector ⟨A⟩ of contact Y. The FindNodeReq is forwarded along r (strict source route). Message forwarding between overlay neighbors requires source routing, because the path in the underlay may lead via nodes that are (ID-wise) further away from the destination (e.g., Y routes via ⟨A, Q, M⟩ to Z in Figure 2): using the ID-based overlay routing scheme on a hop-by-hop basis (i.e., between directly adjacent nodes in the underlay) would inevitably lead to forwarding loops in most cases.¶

                Y
               /
           X--A--Q--M--Z
            \      /
             B----/

When the FindNodeReq arrives at Y, the same procedure is repeated (since it is a recursive variant of Kademlia). Node Y tries to find a contact closer to Z than Y itself. If this contact exists, source route r is appended by the corresponding path vector and the FindNodeReq is forwarded to this contact. In the given example of Figure 2), we assume that Y knows Z as its contact with path vector ⟨A, Q, M⟩. It extends source route r of the FindNodeReq by ⟨A, Q, M, Z⟩ and forwards it to A as next hop in the source route. If routing information has been converged, this ID-based routing scheme guarantees progress in the ID space [Kademlia2002] during forwarding and eventually finds node Z.¶

The destination node Z responds with a FindNodeRsp message along the reversed source path with any cycles removed (⟨Z, M, Q, A, X⟩). Due to XOR’s symmetry, the responding node Z also learns the new contact X as neighbor. The FindNodeRsp returned to X not only provides a path to Z, but also a list of k closest contacts to Z together with their path vectors. This list is used to improve X’s routing table.¶

In case that the FindNodeReq arrives at Y and it cannot find a contact closer to Z, the FindNodeReq is terminated at Y and a response is sent back depending on the "ExactFlag" Section 4.4.1 in the FindNodeReq. If the ExactFlag was not set, Y sends a FindNodeRsp back to originator X that contains an RT excerpt of Y’s (at most) k closest contacts to Z in a so called RTable object. This enables finding the responsible node for a destination ID Z if used as object key. The latter allows for so called key-based routing that is used to realize DHTs. If exact was set, X assumed that a node with ID Z must exist, but the current node is the ID-wise closest node to Z and does not know Z as contact. Consequently, the node cannot forward the FindNodeReq closer to Z and returns a "Dead End" Error message (which may happen occasionally during convergence). In case source route r contains a broken link or unreachable node, a "Segment Failure" Error message will be sent back to X along the reversed source route.¶

3.8. Periodic Path Probing

Periodic Path Probing aims at reliably detecting any RT inconsistencies (e.g., seemingly valid contacts with paths that contain recently failed links). Each node periodically checks the path validity for all of its contacts by sending a ProbeReq message to them. ID-wise closest neighbors are probed more often than other contacts and those recently contacted (≤ 2s) are not probed. In case a path has a link or node failure, the ProbeReq will elicit a "Segment Failure" Error message from an intermediate node along the broken path, notifying about the failed link. The contact’s state will be set to invalid and a rediscovery process is scheduled (see Section 3.9.1).¶

3.9. Dynamics: Recovery from Failures

In order to improve R²/Kad’s robustness against link or node failures we introduce a recovery procedure that notifies about failures and actively tries to find alternative paths that route around the failure. This procedure is highly robust and achieves a fast convergence. R²/Kad nodes detect link and node failures of PNs by link layer notifications, missing PNHello or PNDiscoveryRsp messages as well as "Segment Failure" errors anytime during forwarding along source routes. To recover from such failures, R²/Kad’s recovery procedure uses the following mechanisms:¶

• Notify own nearest overlay neighbors about failed links or unreachable nodes ("bad news") by sending UpdateRouteReqs via a non-impacted physical link.¶
• Rediscover a feasible alternative route to the affected node using FindNodeReqs. These carry NotViaList information about failed links that must not be considered for routing. Rediscovery is not performed for nodes that lost their only link, which can be deduced by the node’s degree information that is conveyed in R²/Kad messages.¶
• Per contact state sequence numbers avoid using obsolete information for path rediscovery. Additionally, an aging mechanism is used to avoid dissemination of obsolete routing information. It uses time periods to assess the currentness of the related path.¶
• Overhearing of NotViaList information and UpdateRouteReqs about failed links during forwarding R²/Kad messages informs nodes about failed links, which initiates a path rediscovery. Overhearing is also used to update obsolete path information.¶
• When an alternative path has been found for a prior affected contact or a link comes back up again, an UpdateRouteReq is sent to own ID-wise closest overlay neighbors for disseminating the "good news".¶

The ID-based overlay routing scheme is used for rediscovery of a route, because NodeIDs are randomly distributed all over the underlying topology. Therefore, a rediscovery uses different paths that are likely not affected by the failure. However, if overlay nodes still have obsolete routing information, i.e., they would normally route via the failed link, they can detect the need to update their routes as well by seeing the more current NotViaList information.¶

3.10. Fast Forwarding of CP Traffic

A potential drawback of R²/Kad is its use of source routing to forward between two overlay hops. Handling a (potentially long) list of source routing hops is currently not as efficiently realized as regular destination-based routing. Moreover, source routing increases per-packet overhead. To forward data packets more efficiently, the Forwarding Tier (see Figure 1) leverages an approach similar to label switching, whereas the Routing Tier still uses source routing for R²/Kad messages to remove cycles, detect shortcuts, and so on. Every source routing path (that consists of NodeIDs) to a contact is represented by up to two PathIDs that correspond to path segments. A PathID is a hash value of all NodeIDs along the corresponding path segment, e.g., PathID(⟨A, Q, M, Z⟩)=H(A|Q|M|Z). It serves as unique label for the path segment. The uniqueness is an important distinction from common label switching approaches where nodes assign labels of node local scope. It enables KIRA nodes to distributedly compute a set of PathIDs in advance. This avoids explicit path setup signaling for PathID installation in many cases. Only for paths longer than 5 hops PathID mappings have to be installed in some intermediate nodes. Another feature of PathIDs is their automatic aggregation toward a sink, i.e., paths that merge in a certain node and use the same residual path to a destination use the same PathID. The Forwarding Tier uses IPv6 GRE [RFC7676] to carry PathIDs in addition to source and destination NodeIDs (other encapsulation methods, e.g., using segment routing [RFC8754] are possible and can be defined later).¶

In detail, KIRA implements fast forwarding as follows:¶

• All paths of length ≤2 for a node’s full 2-hop vicinity are discovered (as described in Section 3.4) and are then used for the precomputation of incoming and outgoing PathIDs, i.e., irrespective of their actual use. Longer paths to contacts are split into two path segments as follows: paths of lengths 4 and 5 hops have a second segment of 2 hops length and a first segment of length 2 or 3 hops respectively. Paths of length L≥6 hops have a second segment of 3 hops and a first segment of variable length L-3.¶
• The node creates forwarding table entries in the form of Incoming PathID -> (Outgoing PathID, Next Hop). The source route for the incoming PathID includes the own NodeID, whereas it is stripped off for computing the outgoing PathID. When forwarding to the last node of a path segment, the outgoing PathID is omitted.¶
• A node that wants to send a data packet (see example in Figure 3), sets the outgoing PathIDs of the source route path segments as destination addresses of the outer encapsulation headers (X uses H(A|Q|M|Z) as first segment and H(Z|C|E|T) as second segment in Figure 3) and sends it to its PN. Source routes of less than 4 hops in length require only one PathID, the other two PathIDs. The source address of the outer header is set to the sender’s NodeID so that errors can be reported back. The destination address of the inner most header is the destination NodeID.¶
• A node that receives a packet containing an incoming PathID tries to match it in its forwarding table. If it finds an entry, it rewrites the PathID with an outgoing PathID or removes the outermost PathID header in case the path segment ends at the next node. Including the own NodeID into the incoming PathID has the advantage of being more resilient against misrouted packets. If no entry is found, a corresponding Error is sent back, indicating a temporary inconsistency.¶

            1.[X,H(Q|M|Z)]
            2.[X,H(Z|C|E|T)]   1.[X,H(Z|C|E|T)]
            3.[X,S]            2.[X,S]
                  |            |          1.[X,H(E|T)]
                  |            |          2.[X,S]
                  |            |          |
          X --> A --> Q --> M --> Z --> C --> E --> T
            |            |          |           |
            |            |          |           1.[X,S]
            |            |          1.[X,H(C|E|T)]
            |            |          2.[X,S]
            |            1.[X,H(M|Z)]
            |            2.[X,H(Z|C|E|T)]
            |            3.[X,S]
            |
            1.[X,H(A|Q|M|Z)]
            2.[X,H(Z|C|E|T)]
            3.[X,S]

Each node computes all PathIDs for its 2-hop vicinity to avoid path setup signaling, because it allows all nodes to assume that PathIDs exist for all source paths of length ≤3 hops. PathID precomputation for the full 2-hop vicinity provides a good trade-off between the number of a priori computed PathIDs and required path setup signaling. Intermediate nodes along a source route may not have computed the necessary PathIDs for others. Nodes explicitly setup paths via PathSetupReq only for paths >5 hops. In the example of Figure 3, only nodes A and Z must install additional forwarding states when receiving a PathSetupReq, because all other nodes have precomputed the PathIDs already. The PathSetupReq is answered with a PathSetupRsp by the node that marks the beginning of the second path segment. The forwarding states are implemented by soft states: contact probing also refreshes any required PathIDs in the intermediate nodes and so called "foreign" entries (i.e., those that are neither locally used nor precomputed) are deleted after three refresh intervals have passed without any refresh.¶

The routing information from the Routing Tier is used by the Forwarding Tier to generate two forwarding tables inside each node: one based on the calculated PathIDs and one based on NodeIDs (generated from RT). One can employ common longest prefix matching for both tables. For NodeIDs the matching prefix length corresponds to the bucket depth. Thus, required prefix length is typically much shorter than the full length of the NodeIDs. The PathID forwarding table size comprises at least all stored contacts, but it is usually larger due to the number of precomputed and foreign entries.¶