ABSTRACT

Categories and Subject Descriptors

Keywords

INTRODUCTION
1.
A significant benefit from using network overlays is the separation of complex and ossified physical networks and virtual networks. Logical topologies isolated from physical networks can be changed agilely to respond to various demands. This characteristic is essential for to- day's virtualized environments such as clouds and net- Figure 1: The rate of transmitting throughput via tunneling protocols compared with the nor- mal transmission on Linux kernel 4.2.0. work function virtualization (NFV). However, overlay- ing networks requires additional protocol processing to transmit packets. This can lead to overheads, especially in host operating systems. A typical end point of network overlays is software network stack of host OS. In clouds, hypervisors con- nect to overlays directly and virtual machines on the hypervisors are accommodated in the overlaid inner net- works. In NFV, software-based middleboxes as service functions are connected by overlays [1]. Moreover, load balancers sometimes utilize overlays for topology iso- lation [2, 3].  Tunneling protocols that build network overlays are implemented as pseudo network interface drivers at the host OS. A pseudo interface becomes an entry point to an overlay network. Packets sent to a pseudo tunnel interface via a network stack are en- capsulated by the interface and transmitted to underlay physical networks via a network stack again. This conventional OS network stack design of tunnel- ing protocols involves overhead and degrades through- put.  To demonstrate the degradation at the OS, we measured transmitting throughput with 5 tunneling pro- tocols: IPIP, GRE, GRETAP (Ethernet over GRE), VXLAN and NSH¹ on Linux kernel version 4.2.0 with Intel Core i7-3770K 3.50-GHz CPU and Intel X520 10- Gbps NIC. The test traffic was a single UDP flow gen- erated in kernel space.  Figure 1 shows the result of this experiment. The x-axis refers to the rate of trans- mitting throughput via each tunneling protocol to the normal transmission (no encapsulation). As Figure 1 shows, using tunneling protocols in the host OS causes over 30% to 43% throughput degradation. In this study, 1) we show a fine-grained bottleneck analysis of tunneling protocols on a Linux network stack. The resulting analysis shows the required time for each part of the network stack through tunneling protocols. Based on the analysis, 2) we propose a new forward- ing information base (FIB) architecture for tunneling protocols. This architecture provides a shortcut for the second network stack processing. Furthermore, the FIB is protocol independent, so that the proposed architec- ture can be adapted to existing and future tunneling protocols. We implemented the proposed FIB using a software dummy interface and an Intel 10-Gbps NIC driver. The evaluation results show that the transmit- ting throughput is improved in 5 tunneling protocols and the kernel throughput is approximately doubled in particular protocols.
CASE STUDY: LINUX TUNNEL IM-
2.
PLEMENTATION
Although new tunneling protocols are being proposed continuously for various purposes, all tunneling proto- cols can be classified into three models by logical topol- ogy type: point-to-point, multipoint-to-multipoint and path-setup. Point-to-point is a classic model that inter- connects two hosts via a virtual wire. Typical protocols are IPIP and GRE. The multipoint-to-multipoint model constructs full-mesh topology between multiple hosts. A typical multipoint-to-multipoint protocol is VXLAN. Finally, path-setup, which is used for NFV, constructs virtual circuits on overlays.  Network Service Header (NSH) is a typical tunneling protocol of the path-setup type. We consider that the bottleneck of transmission (TX) path via tunneling protocols may change, based on the topology models. Hence, we selected 5 tunneling protocols from three topology models as measurement targets: IPIP, GRE, GRETAP, VXLAN and NSH. We measured the time required for each part of the network stack processing to occur through 5 tunneling protocols on a current Linux kernel.  Figure 2 shows the TX path of a Linux kernel and the experiment overview. The TX path through a tunnel is classi- fied into three parts.  Inner-TX processes transmit- ted packets after IP routing for layer-3 (e.g., fragmenta- tion), layer-2 (e.g., ARP) and delivers them to a tunnel interface via dev_queue_xmit() in the same manner as physical interfaces.  Pseudo Tunnel Interface pro- cesses packets according to a tunneling protocol of this interface such as destination lookup on an overlay and headroom allocation for outer headers (Tunnel Pro- cessing) and encapsulates the packets in the tunnel header and outer IP header (Encapsulation).  After that, IP Routing runs for the outer destination IP ad- dress.  Finally, the encapsulated packets are delivered to the network stack again via ip_local_out_sk(). Outer-TX processes the encapsulated packets for layer- 3 and layer-2 and delivers them to an outgoing interface in the same manner as Inner-TX. To measure the time required for these parts, we used a modified Linux kernel. We added timestamp fields to the packet buffer ( struct sk_buff ), and inserted RDTSC instructions to the start and end of each part. In this experiment, a packet generated by the traffic generator went through each part and transit times were stored in the timestamp fields of the packet buffer. The dummy interface shown in Figure 2 saved the times- tamp fields and dropped the packet immediately when it received a packet.  By using this method, we mea- sured the time required for each part on the TX path with 5 tunneling protocols. For this experiment, we used a modified Linux kernel 4.2.0 with an Intel Core i7-3770K 3.50-GHz CPU and test packets were 64-byte UDP packets generated in kernel space. Figure 3 shows the result of this experiment. The y- axis refers to the time required as the number of CPU clock cycles. The value of each part is the median of the results of 300 runs for each protocol. The x-axis refers to tunneling protocols; NoEncap means the nor- mal TX (no encapsulation), so that there is only Inner- TX on NoEncap. From the result, it can be seen that additional processing time due to tunneling cannot be ignored. In vxlan and NSH, the required CPU time to transmit a packet is approximately doubled compared with the normal TX. In VXLAN and NSH, the required CPU time for IP routing for the outer IP header (the red stack in Fig- ure 3) is larger than for the other cases. This is ascrib- able to differences of the topology models. IPIP, GRE and GRETAP are point-to-point models, so that the destination of the outer IP header is always the same. Therefore, the routing cache is used instead of outer IP routing.  By contrast, in multipoint-to-multipoint (VXLAN) or path-setup (NSH) models, the destination IP address of the outer IP header is determined for each transmitting packet by their lookup mechanisms. Thus, IP routing cannot be omitted, so that the outer IP rout- ing occupies over 16% of the TX path. The reason why the Inner-TX of IPIP and GRE is shorter than other protocols is that packet copy due to headroom allocation for outer headers occurs in the Tunnel Processing instead of the Inner-TX. Layer-2 over- lay protocols allocate necessary headroom for the inner Ethernet header, tunnel header, outer IP and Ethernet headers together in the Inner-TX. On the other hand, layer-3 overlay protocols allocate headroom in the Tun- nel Processing because the Inner-TX does not need to allocate headroom for the inner Ethernet header. In addition to the CPU time measurement, we mea- sured TX throughput of the Linux kernel. In this exper- iment, the traffic generator kept generating test traffic and the dummy interface kept dropping the packets. Then, we counted the number of transmitted packets in 60 seconds.  Figure 4 shows the result of the experiment. Using tunneling protocols causes over 40% throughput degradation on the Linux kernel. Moreover, the result indicates that the current kernel network stack cannot make full use of the link speed.  With 1500-byte packets, TX throughput of IPIP was 26 Gbps and VXLAN was 18.9 Gbps. These results are not sufficient for today's and future interface link speeds of 25 Gbps, 40 Gbps, 50 Gbps and 100 Gbps. As described, using tunneling protocols on a host OS involves additional overhead and highly degrades TX throughput.
3.
APPROACH
In this study, we aim to shrink the gap of throughput with/without the tunneling protocols described in Sec- tion 2.  Before describing the approach, protocol inde- pendence has to be considered.  New tunneling protocols are being proposed on a daily basis. Thus, a method specialized in a particular protocol will soon be out of date. Moreover, such dedicated methods are difficult to deploy in the real world. Accordingly, we propose a protocol-independent for- warding information base (FIB) architecture for net- work overlays. This architecture omits the second pro- tocol processing after encapsulation as shown in Fig- ure 5. The original layer-3 FIB is an IP forwarding ta- ble composed of entries of a destination prefix as a key and gateway information such as a destination MAC address. In contrast to the layer-3 FIB, the proposed FIB, called overlay FIB, is composed of entries of some sort of identifier as a key, a destination and parameters for encapsulation. In the normal TX path, layer-3 and layer-2 protocol processing run twice for inner and outer headers of a packet. By using the overlay FIB, protocol processing for outer headers is omitted.
3.1
Overlay Forwarding Information Base
This section describes the overlay FIB architecture and its protocol independence.  Even if protocols or their topology models are different, the task of tunnel- ing to transmit packets is the same:  determining the destination and encapsulating the packets. The overlay
FIB corresponds to these two tasks. Identifiers for determining the destination address of the outer IP header are different for each tunneling protocol. For instance, point-to-point protocols do not have identifiers because the tunnel has only one desti- nation. Typical multipoint-to-multipoint protocols use the inner destination MAC address as an identifier to determine a destination.  NSH, a path-setup model, determines a destination in accordance with the Ser- vice Path ID and Service Index embedded in the NSH header [4].  To handle these different lookup mechanisms as a single logic process for protocol independence, we define offset and length for the identifiers used in, for example, the BPF [5] approach. Although identifiers for lookups are different for each tunneling protocol, they can be considered as the same type of processing: checking a particular byte-string embedded in a packet and determining a destination. Identifiers are always embedded in packets; therefore, identifiers can be specified by offset and length. The parameter offset indicates the beginning of the identi- fier and the length indicates the bit length of the iden- tifier in the packets. Table 1 shows offset and length values for major tunneling protocols. In the case of VXLAN, offset is 16 bytes for UDP and VXLAN head- ers and length is 48 bits for destination MAC address. In the case of NSH over VXLAN-GPE, offset is 20 bytes for UDP, VXLAN and NSH base headers and length is 32 bits for Service Path ID and Service Index.  In this manner, protocol-specific lookup mechanisms can be handled as a single operation on the overlay FIB. An overlay FIB entry consists of a byte-string as an identifier and a destination IP address. In addition to the destination, necessary parameters for encapsulation are also stored: source IP address, IP header param- eters such as ToS and TTL, destination MAC address (gateway router's MAC address), source MAC address, and an outgoing physical interface. When transmitting a packet via a tunnel interface, the overlay FIB finds an entry corresponding to the identifier embedded in the packet. Thus, the packet is encapsulated in outer IP and Ethernet headers with parameters stored in the found entry from the FIB, and finally transmitted to a physical interface. In this TX path, there is neither IP routing nor protocol processing. The overlay FIB is updated by entry operations and lower  layers. The layer-3 FIB is updated by layer-3 routing table operations (route add or delete) and lower layers such as ARP table change (layer-2) and link down or up (layer-1). The overlay FIB update is similar to that in the layer-3 FIB except that the overlay FIB is placed on layer-3. The overlay FIB is updated by entry add or delete and in lower layers such as IP routing table change (layer-3), ARP table change (layer-2) and link down or up (layer-1). Altogether, update notifications are yielded from lower layers to the overlay FIB layer. Moreover, when an overlay FIB entry is added, update notifications are yielded from the overlay FIB layer to lower layers; then, the gateway's IP and MAC addresses are resolved and stored into the FIB entry.
3.2
Offloading Second Protocol Processing
to the Overlay FIB
The overlay FIB is placed between tunnel pseudo interfaces and outgoing physical interfaces in the TX path. Figure 6 shows the normal TX path and the pro- posed path with the overlay FIB on a Linux kernel. In the normal TX path, the tunnel pseudo interface de- termines an outer destination IP address of a packet, encapsulates the packet in tunnel and IP headers, runs IP routing for the outer destination IP address and fi- nally delivers the encapsulated packet to the network stack again. In the proposed TX path, determination of the desti- nation and encapsulation for the outer IP and Ethernet headers are offloaded from the tunnel pseudo interface to the overlay FIB. Consequently, IP routing for the outer IP header is omitted. Tunnel pseudo interfaces only encapsulate packets in the tunnel header and de- liver the packets to the overlay FIB. When the overlay FIB receives packets, the FIB finds entries for the pack- ets based on the lookup mechanism described in Sec- tion 3.1. Then the packets are encapsulated in outer IP and Ethernet headers and delivered to the physical outgoing interface in accordance with the FIB entries. As a result, the overlay FIB architecture reduces the CPU time needed to transmit a packet by omitting IP routing and the second protocol processing for the outer IP header. In addition to outer IP and Ethernet header encapsulation, UDP encapsulation can also be offloaded to the overlay FIB. The overlay FIB can be implemented in both soft- ware and hardware.  As hardware, it is implemented in NICs. NICs have the FIB table and a configuration API that has functions to set offset and length, add and delete an entry composed of an identifier and corre- sponding parameters. This API is similar to switchdeve API [6] introduced to Linux kernel version 3.19. The switchdev provides kernel with hardware independent configuration API to notify layer-2 and layer-3 FIB en- tries to NIC. The overlay FIB entries can be notified from kernel to NIC in a similar way.  Moreover, pro- posed architecture can be implemented in hardware by using various technique like FPGA [7], hardware pro- gramming [8, 9] and dedicated ASIC certainly.
4.
EVALUATION
The proposed overlay FIB architecture provides a shortcut for second protocol processing on the TX path via tunneling protocols. By using the architecture, TX throughput with tunneling protocols is improved.  In this section, we investigate throughput improvement due to the proposed architecture from two aspects: 1) measuring the required CPU time to transmit a packet and 2) actual throughput. For this evaluation, we mod- ified IPIP, GRE, GRETAP, VXLAN and NSH drivers to support the overlay FIB. All modifications for drivers are less than a few dozen lines of code. Source codes for all experiments described in this pa- per are available at https://github.com/xxx/xxx.
4.1
Measuring CPU Time on the TX Path
First, we measured the CPU time required for each part on the TX path with the overlay FIB in the same manner as for the experiment discussed in Section 2. In this experiment, we assumed that the overlay FIB was completely implemented in the NIC hardware; thus, lookup identifier, second protocol processing, outer UDP, IP and Ethernet header encapsulation are omitted from the TX path of the kernel. Tunnel pseudo interfaces delivered packets to the dummy interface immediately after encapsulation.  We experimented with modified Linux kernel version 4.2.0 and an Intel Core i7-3770K 3.50-GHz CPU machine. Figure 7 shows the CPU time required to send a packet when the FIB is implemented in NICs. In Fig- ure 7, Outer-TX means the time required from the end of tunnel interface to the start of dummy interface pro- cessing.  IP routing, IP and UDP encapsulation are com- pletely removed from TX paths compared with Figure 3. As a result, the CPU time required to send a packet in the kernel is reduced in all tunneling protocols. In addition, IPIP with the FIB is shorter than NoEn- cap.  That is because of the packet copy for headroom al- location. In the normal TX path of IPIP, headroom for outer IP and Ethernet headers is allocated in the Tunnel Processing as described in Section 2. By contrast, al- locating headroom is not needed if outer encapsulation is offloaded to NIC hardware by the proposed method. As a result, CPU time for IPIP becomes shorter than for no encapsulation, which requires headroom alloca- tion for the Ethernet header in the Inner-TX. On the other hand, time for the Tunnel Processing of GRE, which uses layer-3 tunneling, does not decrease, because headroom allocation is still needed for the GRE header. In VXLAN, the Tunnel Processing is almost removed. When using the FIB, protocol processing of VXLAN only involves adding a VXLAN header to a packet. Lookup VXLAN FDB, determining destination IP ad- dress, encapsulating VXLAN and UDP headers are re- moved from the Tunnel Processing.  As a result, the CPU time required to transmit a packet via the VXLAN tunnel with the FIB has decreased by 47% compared with the normal VXLAN.

4.2
Measuring Throughput
We next evaluated throughput using the dummy in- terface and the modified ixgbe driver, which is the Intel 10-Gbps NIC driver. With the dummy interface, trans- mitted packets were dropped immediately the packets were delivered to the dummy interface; this is the same as for the experiment shown in Figure 4.  Altogether, the throughput of the dummy interface means the through- put of the Linux kernel itself. In addition, we imple- mented the overlay FIB as software into an ixgbe driver. With the modified ixgbe driver, packets delivered to an ixgbe interface were encapsulated in outer IP and Eth- ernet headers in accordance with the overlay FIB in the device driver. Then, the packets were transmitted to a wire via X520 NIC. We measured throughput of the modified ixgbe at an receiver machine connected to the NIC. For this experiment, we used the same machine as that used in the experiment described in Section 4.1. Table 2 shows transmitting throughput using the dummy interface and the modified ixgbe driver. In all cases, the proposed method improves TX throughput. Through- puts of the dummy interface with IPIP and VXLAN with 64-byte packets are also approximately doubled as, expected from the result of the experiment about CPU time in Section 4.1 On the other hand, the over- lay FIB software implementation also improves actual throughput to the wire when using the ixgbe driver in all tunneling protocols. When it was implemented in the NIC hardware, the throughput of the ixgbe was im- proved at the same rate as for the dummy interface.
5.
DISCUSSION
Other identifiers: The proposed method assumes that the identifier is embedded in the packet and is just a byte-string. This assumption is correct for MAC ad- dresses or labels; however, it does not work for identi- fiers that have some sort of semantics. Locator Iden- tifier Separation Protocol (LISP) [10] utilizes the inner destination IP address as the identifier to determine a destination on a LISP overlay network. Thus, the over- lay FIB has to be capable of the longest prefix match in order to support LISP. Other bottlenecks on the TX path: Many bot- tlenecks on the TX path are well known. For instance, socket API, system call overhead and per-packet pro- cessing have been mentioned for high-speed packet I/O approaches [11, 12, 13, 14].  Meanwhile, network pro- tocol processing never disappears from host OS. This means, no matter how fast the network stack is, proto- col processing becomes the bottleneck on the TX path. In the Arrakis operating system [15], which has a very optimized network stack, network protocol processing occupies 44.7% of its TX path.  When protocol pro- cessing becomes a bottleneck as it does in Arrakis, the current design of overlays where packets go through the network stack twice involves serious overheads. There- fore, the proposed method, which avoids the second pro- tocol processing, can achieve throughput improvement. even if other bottlenecks are also relieved. Hardware offloading techniques: The proposed method can coexist with existing NIC offloading tech- niques. For example, the generic segmentation offload (GSO) delivers large (over 60-kbyte) packets to NICs. Then, NICs divide large packets into small packets cor- responding to MTU size. GSO reduces the number of packets that are handled by the network stack, so that it achieves TX throughput improvement. By applying the overlay FIB before the GSO to NICs, large packets are encapsulated in outer IP and Ethernet headers and then divided into small packets. In addition, UDP tun- nel offload [16, 17], checksum offload can also coexist.
6.
CONCLUSION
In this paper, we have investigated the bottleneck of tunneling protocols in the Linux kernel network stack. Based on the investigation, we have proposed a new FIB architecture for network overlays. The overlay FIB pro- vides a shortcut for second protocol processing of tun- neling protocols. Moreover, this architecture is protocol independent, so that it can be adapted to existing and future tunneling protocols. We demonstrated that our proposed method could improve transmitting through- put with 5 protocols, and the kernel throughput was approximately doubled in IPIP and VXLAN. We plan to implement the architecture in a FPGA card with 10- Gbps NIC. Finally, we aim to evaluate and discuss the architecture in more detail in the future.
7.