# P4-KBR: A Key-Based Routing System for P4-Programmable Networks
## 4 P4-Kbr  
### Key-Based Routing Mechanism  
The P4-KBR routing mechanism is inspired by Chord [8], a widely used application level DHT (Distributed Hash Table) protocol. The forwarding information used by Chord and its lookup procedure have been the foundations to define the routing mechanism of P4-KBR that, unlike Chord, is totally implemented at network level. By way of summary, the upper part of Figure 2 shows the basic concepts of Chord. In particular, the finger table of a node is shown, and how it is used by the Chord lookup mechanism to forward a packet to the node responsible for the searched key. Figure 1: P4 ecosystem. The Chord lookup procedure, which checks the finger table from bottom to top to locate the next node towards the one responsible for the searched key, can be adapted to become a network-level key-based routing mechanism totally implemented at network level in P4 networks (or in OpenFlow-based networks as the predecessor OFC-KBR). This network level implementation results in a set of Match-Action flow table entries that will be inserted into each network device. The match fields of each entry determine a range of virtual identifiers, and the action fields indicate what to do when a packet destined to a value included in the range is received. The SDN controller makes use of its global knowledge of the network to identify the node responsible of each finger table entry and to perform the translation, configuring the flow table of each network element adequately. The table at the bottom of Figure 2 shows the set of key ranges that are obtained for a network element and the forwarding action that should be done depending on the key value the packet is destined for. For a node n, \(finger\_table(n+2^{i})\) refers to the value of the finger table entry \(n+2^{i}\), that is, the network element responsible of key value \(n+2^{i}\), and \(\to x\) means the action _send to node \(x\)_. At the control plane, once the ranges and associated actions are obtained by the controller, it will instruct each network element to install the adequate flow entries. Instead of defining a shim P4-KBR header to contain the source and destination key values (vids) of a packet, the proposed implementation of P4-KBR uses IPv4 address fields to store the vid values. Consequently, the destination IPv4 address is the matching field in the flow table entries used for routing tasks. Depending on the matched entry, a receive packet will be forwarded to the next network element towards the network element responsible for the destination vid. As can be seen in the example shown in Figure 3, but without loss of generality, most of the obtained ranges cannot be expressed by bitmasked values directly. For example, the range \([303,319[=[000100101111,00010011110]\) cannot be expressed by one bitmasked value. This fact causes a technical difficulty in OpenFlow-based networks, as it was identified in [4], because OpenFlow specification only enables the use of bitmasks to express ranges of values in the IPv4 source and destination matching fields. To solve this problem in OpenFlow networks, proposed the use of the prefix expansion algorithm [22] was proposed, converting each obtained range into a set of bitmasked equivalent ranges. Figure 2: The upper part of the figure depicts the Chord basics: the definition of the finger table and the lookup mechanism. At the bottom of the figure, the set of value ranges and associated actions after transforming the lookup mechanism into a network level solution is shown. Using the previous example, the range \([303,319]\) would be expressed by the set of bitmasked ranges: \([303]\), \([304,311]\), \([312,315]\), \([316,317]\) and \([318]\). This is a practical solution, but it involves the insertion of a relatively high number of flow tables entries in the nodes. Offering a greater potential and flexibility, P4 Runtime does support the insertion of table entries where a specific match key field is defined for a RANGE match.