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 underlay 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. Reserved NodeIDs Section 6.1 MUST NOT be used as NodeID of a KIRA node. 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 Underlay Neighbors (ULNs) and some contacts from the 3-hop underlay neighborhood are stored in the routing table. Underlay Neighbors are nodes attached to the links of the KIRA node (i.e., neighbors in the sense of [RFC8200] that are directly reachable via link layer and the Internet-layer or higher-layer tunnels).¶

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. Underlay 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 ULN 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 ID-wise closest contact if all paths have equal length or if destination Z falls into the node's deepest bucket.¶

Each contact typically contains the following information:¶

• NodeID of the contact.¶
• State: the state that the contact is considered to be in. It is one of undefined, valid, rediscovering, invalid, dead.¶
• A set of path vectors, i.e., a complete sequence of NodeIDs that lead to the contact when traversed. There is an active path (used as default), a proposed path and possibly several backup or alternative paths. Paths possess also timestamps for points in time when they were last validated and when they were refreshed (using PathSetupRsp or ProbeRsp, see also Section 3.10).¶
• Sequence Number: a sequence number that is determined by the contact and that changes when the underlay connectivity state changes at the contact, i.e., with newly detected or failed underlay neighbors.¶
• LastSeen: time of last direct contact¶
• Sync ULN Sequence Number: a sequence number used for state synchronization with ULNs.¶
• UnderlayNeighbor: a bool value indicating that this contact is an underlay neighbor¶
• NodeDegree: the contact's number of underlay neighbors.¶
• Rediscovery State: temporary state keeping track of the rediscovery process.¶

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 underlay adjacencies, i.e., its underlay neighbors (ULNs) that can be directly reached via link-local communication on one of their network interfaces. KIRA nodes periodically send ULNHello messages to a well-known link local multicast address ALL-KIRA-NODES, and receiving nodes may reply with a ULNDiscoveryReq to set up an adjacency. This ULNDiscoveryReq MUST be answered by a ULNDiscoveryRsp to establish an adjacency. The protocol exchange ensures that bidirectional communication is possible between directly adjacent nodes. ULNs may be put into the ULNTable either after receiving a ULNDiscoveryReq as answer to a transmitted ULNHello or after receiving a ULNDiscoveryRsp as answer to a transmitted ULNDiscoveryReq. The ULNTable contains a mapping from NodeID to the link local unicast address of the ULN. This address is either taken from the source address of the ULNDiscoveryReq or the ULNDiscoveryRsp 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 ("vicinity graph"). The latter is used to precompute PathIDs for the 2-hop vicinity. ULNDiscoveryReq and ULNDiscoveryRsp messages contain a list of underlay neighbors so that all ULNs of ULNs will be learned, i.e., the 2-hop vicinity. However, possibly not all nodes in the 2-hop vicinity will be stored in the RT, therefore the vicinity graph structure is used to keep track of the 2-hop vicinity (new nodes and links). Especially, the state sequence numbers of all the nodes should be stored in the vicinity graph as well. All nodes in the 2-hop vicinity are queried for their ULNs by using a QueryRouteReq. QueryRouteReq/QueryRouteRsp messages are used to get ULNs or RTable objects from nodes in the vicinity. Depending on their NodeID and other criteria (e.g., NodeDegree), nodes from the 3-hop vicinity will be stored as contacts into the routing table. The vicinity graph structure is used to determine whether a new QueryRouteReq must be initiated according to the State Sequence Number.¶

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 ULNs 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 example 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 ULN 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.7. Overhearing of R²/Kad Messages

KIRA nodes use overhearing mechanisms for R²/Kad messages. This is an important mechanism for KIRA to learn new contacts and better or improved paths.¶

Nodes that forward R²/Kad messages SHOULD use the contained source route to improve their own routing information: they may learn new contacts or shortcut routes to known contacts. However, only the so far traversed path is considered as it can be assumed that all traversed links worked recently. Additionally, NotViaList information (see Section 4.4.2.3) is used to invalidate contacts that have an active path vector containing a link from the NotViaList.¶

The source routing path of incoming requests and responses is also considered for improving the RT. Some messages like FindNodeRsp, QueryRouteRsp or UpdateRouteReq contain RTable objects that are evaluated likewise.¶

Bypassing QueryRouteRsp messages contain RTable objects (as requested by QueryRouteReq) and are inspected for interesting contacts and paths.¶

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 ULNs by link layer notifications, missing ULNHello or ULNDiscoveryRsp 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 ULN. 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 "external" entries (i.e., those that are neither locally used nor precomputed) are deleted after three refresh intervals have passed without any refresh. Soft states are necessary, because paths are aggregated toward the same destination and usage relations are complex so it is nearly impossible to get a tracking completely right. For PathIDs that are used locally and not precomputed, a counter is kept that reflects the number of contacts using this PathID (note that different contacts may use the same first path segment).¶

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 external entries.¶

6.1. Reserved NodeIDs

Reserved NodeIDs:¶

            Undefined NodeID = 0x00..00 (all zeros)
            AllNodes  NodeID = 0xff..ff (all ones)