Yoann Desmouceaux
email: yoann.desmouceaux@polytechnique.edu

Mark Townsley
email: townsely@cisco.com

Thomas Heide Clausen
email: thomas.clausen@polytechnique.edu

Zero-Loss Virtual Machine Migration with IPv6 Segment Routing

With the development of large-scale data centers, Virtual Machine (VM) migration is a key component for resource optimization, cost reduction, and maintenance. From a network perspective, traditional VM migration mechanisms rely on the hypervisor running at the destination host advertising the new location of the VM once migration is complete. However, this creates a period of time during which the VM is not reachable, yielding packet loss.

This paper introduces a method to perform zero-loss VM migration by using IPv6 Segment Routing (SR). Rather than letting the hypervisor update a locator mapping after VM migration is complete, a logical path consisting of the source and destination hosts is pre-provisioned. Packets destined to the migrating VM are sent through this path using SR, shortly before, during, and shortly after migration -the virtual router on the source host being in charge of forwarding packets locally if the VM migration has not completed yet, or to the destination host otherwise. The proposed mechanism is implemented as a VPP plugin, and feasibility of zero-loss VM migration is demonstrated with various workloads. Evaluation shows that this yields benefits in terms of session opening latency and TCP throughput.

I. INTRODUCTION

Data-centers are shifting to hosting more and more heterogeneous workloads, whose lifetimes can vary greatly, and which can exhibit rapidly changing resource demands and inter-application dependencies. Furthermore, the development of live virtual machine (VM) migration [START_REF] Clark | Live migration of virtual machines[END_REF] (and more recently, of container migration [START_REF] Bolla | Seamless and transparent migration for tcp sessions[END_REF]) has allowed for extended flexibility in the assignment of tasks to machines. In this context, many architectures have been developed in which workload migration is used as a baseline to achieve different goals [START_REF] Ahmad | A survey on virtual machine migration and server consolidation frameworks for cloud data centers[END_REF]: energy minimization [START_REF] Ghribi | Energy efficient VM scheduling for cloud data centers: Exact allocation and migration algorithms[END_REF], network usage minimization [START_REF] Kopri | Network-aware virtual machine consolidation for large data centers[END_REF], operational cost minimization [START_REF] Zeng | Cost minimization for big data processing in geo-distributed data centers[END_REF], maintenance [START_REF] Wang | Virtual routers on the move: live router migration as a network-management primitive[END_REF], etc.

From a network perspective, a challenge raised by live migration lies in maintaining connectivity to a VM after it has been migrated. Indeed, hypervisors normally assume that VMs are migrated within a single LAN, using Reverse ARP (RARP) to advertise the new location of a VM after migration. Traditional techniques to overcome this issue rely on Layer 2 overlays, such as VXLAN [START_REF] Mahalingam | Virtual eXtensible Local Area Network (VXLAN): A Framework for Overlaying Virtualized Layer 2 Networks over Layer 3 Networks[END_REF] or NVGRE [START_REF] Garg | NVGRE: Network Virtualization Using Generic Routing Encapsulation[END_REF]. Other approaches include making use of Mobile IP [START_REF] Johnson | Mobility Support in IPv6[END_REF] or of LISP [START_REF] Saucez | Designing a deployable internet: the locator/identifier separation protocol[END_REF]. However, with the emergence of IPv6 [START_REF] Deering | Internet Protocol, version 6 (IPv6) specification[END_REF] datacenters, new opportunities appear, both for the addressing of workloads and for re-engineering the data-path. Among the proposed approaches for mobility within IPv6 data-centers, Identifier-Locator Addressing (ILA) [START_REF] Herbert | Identifier-locator addressing for network virtualization[END_REF] has been proposed at the IETF, using high-order bytes of addresses to denote locators and low-order bytes of addresses to denote identifiers.

A drawback of all these approaches is that they incur a period of time, during which packets addressed to the migrating VMs are lost. This raises concerns for applications that are intolerant to packet losses (e.g. UDP-based delaycritical applications, virtual network functions, ...).

A. Statement of Purpose

The purpose of the paper is to introduce a VM mobility solution, which provides "zero-loss" capabilities: assuming that the network is not lossy, any packet destined to a migrating VM will eventually be received. To that purpose, the Segment Routing (SR) [START_REF] Filsfils | The segment routing architecture[END_REF] architecture is leveraged.

SR is an architecture which allows packets within a designated domain to be added an extraneous header, designating an ordered list of segments through which the packet is expected to go. Segments represent abstract functions to be performed on packets, and can be as simple as forward to next segment (enabling source routing and traffic engineering), but can also represent more complicate instructions (from custom encapsulation or routing behavior to complete virtual network functions). This paper specifically targets the IPv6 flavour of SR, in which segments are represented by means of IPv6 addresses, and where an IPv6 extension header [START_REF]IPv6 Segment Routing Header (SRH)[END_REF] contains the list of segments. Backwards compatibility with non-SR-aware routers is maintained, by having the waypoints modify the destination address of the packet to that of the next segment, allowing traversal of arbitrary routers while travelling between two segments.

The idea underlying this paper is to use SR to solve the locator/identifier mapping synchronization problem during VM migration, by letting the gateway (proactively) route packets destined to a migrating VM through a path comprising the old and the new hosts. This way, the responsibility of the old host is reduced to (i) forwarding packets locally while the migration is not complete and (ii) forwarding packets to the next segment (the new host) once migration has completed. This way, no packets are lost during the migration, whereas traditional solutions would require a mapping to be updated once migration has completed, leading to potential packet losses during this period of time. Furthermore, the overhead on the old host is kept to a minimum, since no tunnel has to be opened and no Layer-2 overlay is required.

B. Related Work

Many solutions have been proposed to address the issue of maintaining Layer-3 network connectivity during and after VM migration. The simplest solutions involve using a Layer-2 overlay [START_REF] Mahalingam | Virtual eXtensible Local Area Network (VXLAN): A Framework for Overlaying Virtualized Layer 2 Networks over Layer 3 Networks[END_REF], [START_REF] Garg | NVGRE: Network Virtualization Using Generic Routing Encapsulation[END_REF], and relying on hypervisors sending gratuitous Reverse ARP messages after migration. In addition to the operational complexity incurred by running such overlays, the VM is not reachable on the new host until the RARP has propagated, leading to potential packet losses.

Another simple solution consists of creating an IP tunnel between the source and the destination hosts. In [START_REF] Bradford | Live wide-area migration of virtual machines including local persistent state[END_REF], the Xen hypervisor is modified so that after migration, packets reaching the hypervisor at the source host are tunnelled towards the new host. After migration, the VM uses two different addresses (an "old" and a "new" address), and Dynamic DNS is used so that external clients can reach the VM via the new address. The drawback of this approach is that the hypervisor must co-operate with the destination host during an unpredictable amount of time by performing tunnelling. This is incompatible with recent architectures, where packets destined to VMs are handled by virtual switches rather than by the hypervisor itself.

In [START_REF] Li | Hypermip: Hypervisor controlled mobile ip for virtual machine live migration across networks[END_REF], Mobile IP is used to assist the migration process. Traffic from/to the VM is routed through a home agent, which tunnels it to the correct server hosting the VM. It is the role of the hypervisor to update the home agent with the new location of the VM once it has migrated. Thus, after VM migration, packets can wrongfully reach the source host before registration of the new location is complete. This approach is improved in [START_REF] Watanabe | A performance improvement method for the global live migration of virtual machine with ip mobility[END_REF], by configuring, before migration, a dummy secondary interface for the destination network, and swapping primary and secondary interfaces after migration. This requires co-operation with the VM as two interfaces are used.

In [START_REF] Raad | Achieving sub-second downtimes in large-scale virtual machine migrations with lisp[END_REF], LISP is used to address the issue of Layer-3 connectivity during VM migration. Packets destined to a VM traverse a LISP router, which encapsulates them towards the current resource locator of the VM. The hypervisor is modified so that, after VM migration, the mapping system is updated to reflect the new resource locator of the VM. This avoids triangular routing, but once again the VM is not reachable during the period of time when the mapping is being updated.

Finally, some other approaches are orthogonal to the context of this paper, but worth mentioning. In [START_REF] Kalim | Seamless migration of virtual machines across networks[END_REF], TCP options are used to facilitate migration of TCP connections. In a Software Defined Networking (SDN) context, [START_REF] Mattos | Xenflow: Seamless migration primitive and quality of service for virtual networks[END_REF] proposes a framework for virtual router migration, in which control planes and data planes are migrated during two distinct phases.

II. SR-BASED MIGRATION

This paper assumes that a VM is located within an IPv6 data-center, and accessible through a virtual address (VIP). Each machine within the data-center is accessible at a physical address (PIP), and can host several VMs. A location database maintains a mapping between each virtual address and the physical address of the server hosting the corresponding VM. Located at the edge of the data-center, a gateway advertises (e.g. with BGP) the whole virtual address prefix. When receiving traffic for a given VIP, the router will steer it through an SR policy consisting of one segment, namely the PIP of the machine hosting the VM. Each machine is running a virtual router (in our implementation, VPP 1 ), which is connected to the physical interface(s) of the server, and to each VM by means of a virtual interface (in our implementation, a vhost-user interface). In sum, under normal operation (when the VM is running on a single host), the gateway will tunnel traffic for a VM towards the machine hosting it.

The mechanism introduced in this paper assumes that a controller is running in the data-center, which decides about the allocation of VMs to physical machines. When the controller decides to move a VM from a host to another, it proactively modifies the routing tables of the gateway, so that the traffic for the corresponding VIP is steered into an SR policy consisting of two segments, corresponding to the old and new machines hosting the VM. This way, when the VM is migrating, the gateway will steer traffic to the old host. As long as the VM has not completed migration, traffic will be intercepted by the old host (figure 1); as soon as migration is complete, the old host will simply forward traffic to the next segment, namely the new host. This way, no synchronization is required between the old host and the network: traffic is loosely sent to a logical path comprising both hosts.

III. DETAILED SPECIFICATION

This section introduces a formal description of the SR functions necessary to perform zero-loss migration, as well as the behavior of the gateway.

A. Segment Routing Functions

Three SR functions are defined: 1) Forward to Local (f w): The f w function simply forwards the packet to the next segment. In SR terminology [START_REF] Filsfils | SRv6 Network Programming[END_REF], this corresponding to the END behavior.

2) Forward to Local if Present (f wp): The f wp function forwards the packet to the last segment (skipping intermediary segments), only if the corresponding VIP v is present locally; otherwise it acts as the f w function and forwards the packet to 1 https://gerrit.fd.io/r/vpp the next segment. The forwarding decision is made by the virtual router by inspecting its routing table, and seeing whether the entry for v corresponds to a virtual (local) interface, whose link-status is up. This corresponds to the END.S behavior [START_REF] Filsfils | SRv6 Network Programming[END_REF] with a custom policy for forwarding decisions.

3) Buffer and Forward to Local (bf w): The bf w function inspects the last segment v. If v is not present locally (i.e. if the corresponding virtual interface is not ready), it will buffer the packets for further delivery. Otherwise, it flushes any buffered packet to the virtual interface corresponding to v, and forwards the current packet to the last segment v. This is achieved thanks to a packet buffer in the virtual router, which must be provisioned with a size large enough to handle all potential packets coming during the VM downtime phase. If a VM is expected to receive traffic at rate of r packets/s and to be down during ∆t seconds, buffers must be provisioned with a size of r • ∆t packets.

B. Gateway Operation

For each VIP v, the controller maintains an entry L(v) in the gateway which is either R(s 1 ) ("running on s 1 ") or M (s 1 , s 2 ) ("migrating from s 1 to s 2 "), depending on the state of v. Conceptually, this forms a mapping v → L(v), where L(v) is the location of v. Practically, this is implemented by means of routing adjacencies in the FIB of the gateway. The gateway uses the transit behavior T.INSERT [START_REF] Filsfils | SRv6 Network Programming[END_REF] for v, that is, this routing adjacency triggers insertion of an SR header on packets destined to v. When the gateway receives a packet for v, if the corresponding entry L(v) is R(s 1 ), then a SR header 2 (s 1 ::f w, v) is inserted. If the corresponding entry L(v) is M (s 1 , s 2 ), then a SR header (s 1 ::f wp, s 2 ::bf w, v) is inserted. 2 SR headers are shown in reverse packet order (traversal order).

C. Detailed Migration Process 1) Normal Operation: Under "normal operation", that is, when a VM v is running on a server s 1 , the gateway is configured to map v to L(v) = R(s 1 ). Thus, packets destined to v are forwarded to s 1 by means of a single-hop SR tunnel.

2) Migration Operation: Figure 2 provides an example of the operation that occurs when a VM is migrated. When the controller decides to move v from s 1 to s 2 , it updates the gateway so as to remap the entry for v to L(v) = M (s 1 , s 2 ). It then queries the hypervisors running on s 1 and s 2 to initiate the live migration process.

As a first step, the VM is stopped on s 2 and running on s 1 , while the memory of v is iteratively copied by the hypervisor (out-of-band) from s 1 to s 2 . The gateway inserts an SR header (s 1 ::f wp, s 2 ::bf w, v) in the packets it receives for v. Since the virtual router on s 1 sees that the virtual interface of the VM is up, upon triggering of the f wp function, it will simply forward these packets to that interface (skipping the s 2 segment).

As a second step, the hypervisor has finished iteratively copying the memory of the VM to the new host, and needs to perform the copy of the last memory pages as well as the CPU state. At this point, the VM is stopped on both s 1 and s 2 . The gateway still inserts an SRH (s 1 ::f wp, s 2 ::bf w, v) in packets it receives. Now that the VM is stopped on s 1 (which the virtual router at s 1 detects by inspecting the status of the corresponding virtual interface, now in link-down state), the f wp function will simply forward packets to the next segment. Since s 2 is not yet running the VM (which the virtual router at s 2 detects by inspecting the status of the corresponding virtual interface, also in link-down state), the bf w function will temporarily buffer the packet.

As a third step, the VM is started back on host s 2 . Before the controller (and thus the gateway) is notified of this, the gateway has a stale mapping L(v) = M (s 1 , s 2 ), and the same SRH is inserted in the packets destined to v. Thus, the first server s 1 forwards these to s 2 . Now, the bf w function on s 2 will trigger release of the buffered packets to the virtual interface of the VM, and further packets are forwarded without buffering.

As a fourth step, the controller is notified of the end of the migration, and can update the gateway to map v to L(v) = R(s 2 ): normal operation resumes, packets reach s 2 directly.

IV. EVALUATION

A. Testbed and Methodology

The SR functions described in section III-C have been implemented as VPP plugins. No collaboration between VPP and the hypervisor is needed; rather, forwarding decisions are made from within VPP by inspecting the state of the vhost-user interface corresponding to the VM of interest. Buffers for the bf w function are sized to 8192 packets (consuming 16 MB of RAM), allowing to sustain MTU-sized traffic at ≈ 1 Gbps for a typical VM downtime of 100 ms.

A simple testbed is set up with three physical machines, as in figure 1: the first one plays the role of a gateway

C. HTTP Workload (ants)

To understand the behavior of SR-migration when facing a delay-sensitive workload, a simple evaluation scenario is carried out. The server VM v 0 is set up with an Apache HTTP server -serving a default static file (whose size is 12 KB). As previously, the VM is first running on s 1 , then migrated from s 1 to s 2 . A traffic generator is attached to the gateway, sending a Poisson stream of 6000 queries with rate λ = 1500 s -1 , during which the VM is migrated. The experiment is repeated 10 times, for each of the four previously-introduced evaluation scenarios. Response times for all queries are recorded and reported in figure 4.

The majority of queries are executed when the VM is not migrating, and exhibit small response times (≤ 3 ms). The other queries correspond to those that started while the VM was migrating. With non-SR migration, TCP SYN packets are lost when the VM is down, but some are also lost after the VM has restarted on s 2 , due to the reconfiguration delay. Due to the SYN retransmit delay of 1 s, those queries exhibit a response time ≥ 1 s (more than 19% of queries are concerned). With SR migration without buffer, TCP SYN packets are lost when the VM is down, but as soon as the VM is up they are successfully transmitted again. This explains why queries suffering from a SYN retransmit are less numerous than with the baseline scenario: less than 4% of queries have a response time greater than 1 s. Finally, with SR migration with buffer, TCP SYN packets are buffered while the VM is down. The corresponding response time is simply delayed by the VM downtime (≈ 100 ms in these experiments), rather by the SYN retransmit delay. Less than 0.7% of queries exhibit a response time greater than 1 s, whereas more than 99.2% of queries have a response time lower than 200 ms. A similar experiment is then performed on a more realistic workload. This time, the workload consists in drawing a random number k (from an exponential distribution with mean E[k] = 4) and serving k copies of the previous static file. This allows to induce variability in the response times, as well as more network traffic. Again, the experiment is repeated 10 times, and client response times are recorded: results are depicted in figure 5. With non-SR migration, more than 19% of queries are replied to within 1 s or more. In comparison, less than 4% of queries exhibit a response time greater than 1 s with SR migration without buffer, and this drops to 0.4% for SR migration with buffer. Furthermore, 99.5% of queries are served within less than 200 ms with the latter mechanism.

D. Iperf Workload (elephants)

The previous set of experiments gave insight on the behavior of the different migration mechanisms in presence of shortlived flows. To understand the influence of SR-migration on longer connections, an experiment with parallel TCP flows is performed. The same experimental platform as in the previous section is used -except that this time, a delay of 2.5 ms is added between the VM v 1 (representing clients) and the VM v 0 (representing the server to be migrated), so as to represent clients outside the data center. An instance of iperf with 50 parallel connections is started on the client VM, for 10 seconds (the rationale for using many parallel connections is to smooth the effects of TCP congestion control). In the meantime, the server VM is migrated from machine s 1 to s 2 , using the same 4 mechanisms as before. The experiment is repeated 10 times. Figure 6 depicts the instantaneous throughput (aggregated over the 50 subflows) for one of the 10 runs, collected every 0.5 s. Before and during VM migration, the throughput is rather stable, oscillating around 3.5 Gbps. When the migration ends, around t = 7s, there is a drop in throughput, due to the VM downtime (≈ 150 ms in these experiments). While this drop is significant with non-SR migration (going to 1.8 Gbps in the run reported in figure 6), it remains reasonably high with SR migration (2.7 Gbps in this experiment). The low performance of non-SR migration can be explained by TCP reducing its congestion window, due to the large amount of time when no packets are received by the VM. With SR migration, this downtime is lower, and thus the congestion window is less reduced. The impact of buffering, versus dropping packets while the VM is not yet up on the new host, seems to be negligible.

In order to quantify these behaviors, figure 7 depicts the distribution of the instantaneous aggregate throughput (collected every 0.5 s), over all the 10 runs. With the no migration scenario, the instantaneous throughput stays between 2.9 and 3.7 Gbps. SR migration is able to maintain the throughput above 2.3 Gbps at all times, whereas with non-SR migration the instantaneous throughput can drop to 0.4 Gbps during the migration phase. With non-SR migration, the throughput is lower than 2.2 Gbps for 5% of the time (compared to never with SR migration), and lower than 2.9 Gbps for 10% of the time (compared to 5% of the time with SR migration).

E. Iperf Sink Workload

The same set of experiments is repeated, except that in this case the iperf instance running in the VM is acting as a sink. This can model use-cases where the VM receives a lot of data -for instance, if it is an HTTP proxy or a firewall. In such a scenario, packets lost during the migration process are actual data packets (rather than simple TCP acknowledgements packets, as in the previous set of experiments), thus packet loss is expected to have a greater influence on the overall quality of service.

As previously, figure 8 reports the instantaneous throughput (aggregated over the 50 subflows) for one of the 10 runs, collected every 0.5 s. This time, the drop in throughput when using non-SR migration is more critical, going to 0.2 Gbps. Figure 7 depicts the CDF of the instantaneous aggregate throughput as collected every 0.5 s, over the 10 runs. Non-SR migration still exhibits low performance, with the 5-th percentile for throughput being 0.6 Gbps, as compared to 1.9 Gbps for SR migration. Furthermore, in this case, there is a (small yet perceptible) benefit from buffering packets vs dropping them when using SR migration, as each x-th percentile for throughput is greater with SR migration with buffer than with SR migration with drop.

V. CONCLUSION

This paper has introduced a mechanism to perform zero-loss VM migration in IPv6 data-centers. Contrary to traditional approaches, which maintain connectivity to migrating VMs reactively by updating the location of VMs after they have migrated, this paper introduces a proactive mechanism, which pre-provisions a logical path through which packets will flow shortly before, during, and shortly after, migration. This is enabled by the use of IPv6 Segment Routing, allowing to steer packets destined to a migrating VM through this logical path. This way, coupling between the data plane and the hypervisor is reduced to a minimum: the only operation that a virtual router performs upon receipt of a packet, is checking whether the corresponding interface is up, and forward the packet locally or to the next segment accordingly. Implementation on a real virtual router, VPP, and evaluation by means of diversified workloads, show that the proposed mechanism is indeed able to provide zero-loss VM migration, with benefits both in terms of TCP throughput and session opening latency.

This paper has focused on VMs processing traffic from/to the outside of the data-center, i.e. egress-facing servers or virtual network functions. An interesting question to be investigated is how to use similar techniques to provide seamless migration for VMs handling intra-data-center traffic.

Figure 1 .

 1 Figure 1. SR VM Migration: migrating VM.

Figure 2 .

 2 Figure 2. SR Migration: detailed example.

Figure 4 .Figure 5 .

 45 Figure 4. Evaluation of SR migration: response times for the static HTTP workload, λ = 1500 s -1 (log-log scales).

Figure 6 .Figure 7 .

 67 Figure 6. Evaluation of SR migration: instantaneous aggregate throughput, for one iperf run with 50 clients.

Figure 8 .Figure 9 .

 89 Figure 8. Evaluation of SR migration: instantaneous aggregate throughput, for one iperf sink run with 50 clients.

In its standard implementation, the ping utility adapts its sending rate if it sees that probes are not replied to. Here, it was recompiled so that packets are sent with the same rate, no matter how many of them are not answered.

Sent (ms)

gw, and the two other ones s 1 , s 2 represent compute nodes, which are candidates to host virtual machines. A client VM v 1 (representing the "outside" of the data-center) is attached to the gateway. A VM v 0 represents a server that will be migrated. That VM is first running on s 1 , then migrated from s 1 to s 2 . In order to reflect this, the gateway is configured in the M (s 1 , s 2 ) state, i.e. it inserts (s 1 ::f wp, s 2 ::bf w, v 0 ) in all packets destined to v 0 . Four mechanisms are compared:

1) no-migration, i.e. the VM is not migrated; 2) non-SR migration ("baseline scenario"), i.e. the gateway is first in state R(s 1 ), and once the migration is complete the controller puts the gateway in state R(s 2 ) (without going through a migration state M (s 1 , s 2 )); 3) SR migration without buffer, i.e. the gateway is in state M (s 1 , s 2 ) but packets received on s 2 while the VM is not yet up are dropped instead of buffered; 4) SR migration with buffer ("zero-loss migration" as in section III-C), i.e. the gateway is in state M (s 1 , s 2 ) and packets received on s 2 while the VM is not yet up are buffered. The baseline scenario serves as an illustration of mechanisms such as LISP-based migration [START_REF] Raad | Achieving sub-second downtimes in large-scale virtual machine migrations with lisp[END_REF], wherein packet loss occurs due to the locator mapping being updated only after migration.

B. Ping (illustration)

In order to illustrate the behavior of these four mechanisms, a ping 3 is run between the client VM v 1 and the server VM v 0 , while v 0 is migrated. One packet is sent every millisecond, and the RTT for each packet is recorded. Figure 3 shows the time at which an echo answer is received as a function of when the corresponding echo request was sent. Without migration, each answer is received approximately 0.1 ms after the corresponding query is sent. With non-SR migration, packets were lost during 722 ms (corresponding to the VM downtime, plus the network reconfiguration time), whereas with SR migration without buffer, packets were lost for only 174 ms (corresponding to the VM downtime). Finally, with SR migration with buffer, 175 packets were buffered while the VM was down, and replied to as soon as the VM went up again.


Arthur Toussaint
email: arthur.toussaint@polytechnique.edu

Mohammed Hawari
email: mohammed.hawari@polytechnique.edu

Thomas Clausen
email: thomas.clausen@polytechnique.edu

Chasing Linux Jitter Sources for Uncompressed Video

Beyond the transport of uncompressed video over IP networks, defined in standards such as ST2022-6, the ability to build software-based Video Processing Functions (VPF) on commodity hardware and using general purpose Operating Systems is the next logical step in the evolution of the media industry towards an "all-IP" world. In that context, understanding the jitter induced on an ST2022-6 stream by a commodity platform is essential. This paper describes a general methodology to enumerate jitter sources on commodity platforms and to quantify their relative contribution to the overall system jitter. The methodology is applied to the Linux kernel, producing a classification of the different sources of jitter, and a quantification of their impact.

I. INTRODUCTION

Live video processing in the broadcasting industry has historically been done using dedicated hardware appliances, interconnected by Serial Digital Interface (SDI) family interfaces e.g., ST292M [START_REF]SMPTE standard -1[END_REF] for SDI over coaxial cable for HD video streams. Development of protocols such as ST2022-6 and ST2110-20 [START_REF]ST 2022-6:2012 -SMPTE standard -transport of high bit rate media signals over ip networks (HBRMT)[END_REF], [START_REF]ST 2110-20:2017 -SMPTE standard -professional media over managed ip networks: Uncompressed active video[END_REF], specifying encapsulation of SDI data over Ethernet/IP networks, has since 2012 indicated a trend towards replacing dedicated appliances with commodity hardware and networks, to gain operational flexibility and to reduce cost. These protocols -used in the video production world -differ from those used by end-users on the Internetthe video distribution world -since the former encapsulate raw video data whereas the latter rely on compression: the nominal rate of an ST2022-6 stream is never lower than 1.5 Gbit/s, compared to the tens of Mbit/s for a compressed distribution HD stream. These standards for video production streams require the sender to emit packets at a Constant Bitrate (CBR). Also, while distribution streams can tolerate delays in the order of seconds, to allow for the interactivity required for broadcasting operations, e.g., video stream mixing, production streams bound the delay at a few milliseconds.

This informs packet buffer dimensioning on video production appliances: more buffering at the ingress of a device, yields a greater delay. Thus, ST2022-6 receivers have small buffers -a side-effect of which is, that production streams cannot accommodate for much, if any, jitter. Thus, software-based Video Processing Functions (VPF) executed on Commodity Off-The-Shelf (COTS) servers need to minimize the jitter they introduce as much as possible. As any VPF needs to receive packets first, it is necessary to understand what minimal jitter the Operating System (OS) and its network stack introduce.

A. Related Work

Understanding jitter on general-purpose OS'es has, especially, been studied for real-time or High-Performance Computing (HPC) applications. OS jitter quantifies how unpredictable the performance of a running application will be. An experimental analysis of the effects hereof on CPU-bound tasks in a distributed HPC environment is given in [START_REF] Vicente | Exploratory study on the linux os jitter[END_REF] -which shows that jitter affects the overall performance of multi-stage workloads, where each stage is running on parallel nodes. Specifically, jitter significantly impacts the synchronisation steps between each stage, incurring a significant waste of computing capacity. In-kernel methods to quantify accurately the contribution of each jitter source to the overall system jitter are developed and evaluated in [START_REF] Morari | A quantitative analysis of OS noise[END_REF], [START_REF] De | Identifying sources of operating system jitter through fine-grained kernel instrumentation[END_REF].

For hard real-time applications, a deterministic lower bound on the performance is required. A recurring problem is determining the variability of the response time i.e., the total elapsed time from when an interrupt request is raised, and until the corresponding application-level thread is scheduled. From this perspective, [START_REF] Barbalace | Performance comparison of VxWorks, Linux, RTAI, and Xenomai in a hard real-time application[END_REF] compares Real-Time Operating Systems (RTOS) and general purpose OS'es, in the context of embedded systems used in experimental nuclear physics.

Aside from the analysis in [START_REF] Welponer | Measuring and reducing the impact of the operating system kernel on end-to-end latencies in synchronous packet switched networks[END_REF] of periodic networked systems with events in the order of 100 µs on a FreeBSD-based COTS server, little attention has been given to characterising jitter on periodic events.

Yet, with ST2022-6 prescribing a CBR stream giving rise to a packet arrival time with a periodicity in the order of 7.41 µs, if a VPF is to be successfully executed on a COTS server, a granular understanding of its jitter properties is required.

B. Statement of Purpose

This paper characterises the jitter, introduced by a COTS x86 server running a Linux-based operating system, upon reception of network packets corresponding to an ST2022-6 video stream. This includes an analysis of the packet reception path in the Linux kernel, an enumeration of identified jitter sources, and an experimental quantification of the relative contribution of each of these.

C. Paper Outline

The remainder of this paper is organised as follows: section II describes the data-path taken by a packet, from wire to application, enumerating the potential sources of jitter that can be encountered. Section III motivates and introduces the 978-3-903176-14-0 c 2018 IFIP experimental setup used to quantify these sources of jitter, which is then used for producing the results presented in section IV. This paper is concluded in section V.

II. FROM WIRE TO APPLICATION

The jitter sources along the path of a packet through a COTS server, depicted in figure 1, from its arrival at the Network Interface Card (NIC) until it is delivered to an application, are analysed in this section.

A. From Wire to Interrupt

When a packet arrives at the NIC, it is decoded and copied into RAM using Direct Memory Access (DMA). DMA allows external devices, such as NICs, controlled access to a portion of the CPU's RAM. DMA uses the system PCI bus, which is a shared resource with potential contention for access -and hence, is a potential source of jitter. Another source of jitter is access to the RAM itself, since the NIC (hardware), and the NIC driver (part of the operating system) will be competing for access hereto. Finally, multiple layers of cache, which are shared with all the processes of a CPU, can introduce further jitter during the phases of copying data to and from RAM.

Once a packet has been copied into RAM, the NIC raises an interrupt to signal to the CPU that a new packet is available. Interrupts are also raised through the system PCI bus, where contention may again introduce jitter. However, some NICs also implement Interrupt Rate Throttling (ITR), which delays or suppress some interrupts from being raised, so as to avoid interrupt overload at high data rates. While this feature does reduce the OS per-packet processing cost, it does constitute an additional source of jitter, especially among packets received in a periodic stream. Illustrating this by a simple example, if ITR suppresses 9 out of 10 interrupts, then packet number 1 in a stream will incur a further delay of receipt of another 9 packets before an interrupt is raised, and it can be processed, whereas receipt of packet number 10 will cause an interrupt to be raised immediately.

B. From Interrupt to Application

A raised interrupt triggers a call to the kernel Interrupt Service Routine (ISR). The time from an interrupt is raised, and until the beginning of the execution of the ISR can vary, e.g., due to other higher-priority or non-masked interrupts, or the need to awaken the core executing the ISR from suspension. Thus, this constitutes a potential jitter source.

Execution of the ISR is the first event, which can be timestamped in software by the operating system. In Linux, specifically, this is the irq_entry event. Then the ISR calls the New API (NAPI) component, which attempts to reduce the load induced by network activity on the CPU during high load scenarios, by processing packets in bursts. Thus, this also constitutes a potential jitter source.

NAPI calls the NIC driver, which fetches the packets from RAM (where they had been placed using DMA by the NIC) -and hands these off to the set of kernel components constituting the network stack, see figure 1, for further processing (decoding received packet headers, extracting metadata corresponding to the different network layers, etc). This processing is subject to optimisations such as memory prefetching, cache hits, etc., and therefore also constitutes a potential jitter source.

The processing step in the networking stack is to identify if a given packet matches an open socketi.e., if there's an application able to receive the payload of the packet. If there is, and if the application process is sleeping, or is waiting for data from this socket, it is awoken by the kernel -which requires (i) a call to the scheduler and (ii) a context switch. These two operations also constitute a potential jitter source.

C. Network-Independent Jitter

In addition to the jitter sources within the data-path itself other sources of jitter -henceforth network-independent jitter -exist. Essentially, those consists of events that temporarily interrupt packet processing anywhere on the path discussed in section II-B and illustrated in figure 1.

First, the Linux kernel's scheduler can preempt running processes. Suspending a running process from execution will cause jitter, as the process will not be able to perform any action during the time it is not scheduled.

Second, hardware interrupts take precedence over any other kernel-space or userspace task. Thus, a non-masked interrupt being raised will trigger the kernel ISR, interrupting any other execution on the CPU core charged with handling that interrupt. This can introduce jitter in any part of the stacknoting that a high-priority interrupt being raised can delay the execution of the ISR corresponding to a packet arrival. Completely transparent to the operating system, System Management Interrupts (SMI) literally steal control of a CPU from the OS, for doing low-level house-keeping tasks. With no direct proof of their execution provided to the operating system kernel, SMIs are both a potential jitter source and are very hard to detect. One possible way to detect SMIs is to run an infinite loop polling the current time and to detect gaps in those measurements.

III. EXPERIMENTAL SETUP

To quantify the contribution of the potential jitter sources, identified in section II, to the overall jitter of a VPF receiving an ST2022-6 stream, each is studied in an isolated environment.

A. A Packet Sink VPF

In order to eliminate any application impact (such as memory bandwidth consumption, CPU cache pollution, etc), a "packet sink VPF" with minimal application behaviour is used: on receipt of a packet, the application generates a timestamp, drops the packet without inspecting the payload, and computes the sequence of packet inter-arrival times T . The resulting time series can then be analysed to quantify the jitter introduced by the server.

To differentiate between hardware-level and kernel-level jitter, another source of timestamps is needed -at the ingress of the kernel. For this purpose, the Linux kernel event tracing subsystem 1 is used, to record events at key steps of the packet data path. In particular, this allows recording timestamps for ISRs triggered by interrupts raised from the NIC, thus providing a second time series related to packet arrivals.

B. Quantitative Scope

The test setup is illustrated in figure 2, where the stream at the ingress of the server is assumed to be CBR. Understanding to what extent this assumption is true is necessary, to be able to interpret the recorded time-series meaningfully.

Thus the COTS server in figure 2 was substituted by an ST2022-6 hardware network analyser 2 . The measurement results are depicted in figure 3 and show a standard deviation 1 https://www.kernel.org/doc/html/v4.17/trace/index.html 2 Tektronix PRISM. = 0.6µs in the distribution of the packet inter-arrival times. The stream received in the experimental setup is, therefore, CBR with a precision of 1 µs, and any sub-microsecond packet delay variation observed, therefore, cannot be attributed to the server hardware or software in this setup.

C. Hardware setup

The hardware setup is as follows, with reference to figure 2

IV. EXPERIMENTS AND RESULTS

This section experimentally quantifies the contribution of each source of jitter, as enumerated in section II. In the setup of section III, all known sources of jitter eliminated, a baseline is established. These sources are then restored one by one and their impact is measured.

A. Baseline: Minimal Jitter

To eliminate external jitter sources, some of the available CPU cores are isolated from the scheduler, and assigned statically and exclusively to executing the (user-space) VPF, handling NIC interrupts, and handling other (non-NIC) interrupts. This is done by way of using the Linux kernel options, indicated in table I, as follows:

nohz_full=<CPU_LIST> isolcpus=<CPU_LIST> ,! rcu_nocbs=<CPU_LIST> rcu_nocb_poll
Moreover, as illustrated in figure 4a, the VPF is shielded from all interrupts other than those raised by the receiving NIC, as they are routed to a core different from the one running the VPF.

To eliminate jitter at the hardware level i.e., between the arrival of the packet and the execution of the interrupt handler, the following is implemented. First, interrupt throttling is disabled in the i40e kernel module -the NIC driver used by the Intel XL710 -as follows:

ethtool -i <interface> -C adaptative-rx off ethtool -i <interface> -C rx-usecs 0
Then, as illustrated in figure4a, the ISRs corresponding to the NIC are shielded from the rest of the interrupts of the system as these are routed to a CPU core different from the one executing the NICs ISRs. For each interrupt number <INT> and target CPU core <CPU>, rerouting interrupts is achieved as follows:

echo <CPU> > /proc/irq/<INT>/ ,! smp_affinity_list
All energy saving options are disabled by adding the following kernel options (described in table I):

processor.max_cstate=1 intel_idle.max_cstate ,! =0

With the same purpose, all CPU cores are configured to run at their maximum frequency:

echo performance | sudo tee /sys/devices/ ,! system/cpu/cpu * /cpufreq/ ,! scaling_governor

In order to further reduce the CPU core wake-up penalty and as illustrated by figure 4a, the NICs interrupts are routed to the same CPU core as the one which the VPF is scheduled, which spares one CPU core wake-up and one Inter-Processor Interrupt (IPI), as the network stack (running on the same CPU core as the ISR) will not need to communicate with another CPU core when notifying the VPF. Finally, the packet sink VPF used for the experiments and described in section III is implemented in polling mode; by calling recvfrom in a tight loop with the MSG_DONTWAIT flag, the VPF never blocks which eliminate the call to the scheduler evoked in section II.

B. Baseline: Experiments and Results

To differentiate the network-independent jitter defined in section II-C from the jitter introduced by the processing of incoming packets, a dummy program is implemented; it consists of a loop, busy waiting for 7.41 µs and generating a timestamp at each iteration. Therefore, this dummy program has no interaction with the network stack and is able to provide measurements of the network-independent jitter of the system. In that setup, the sequence of timestamp should increase by 7.41 µs at every iteration, unless the dummy program is somehow interrupted. In that case, the time series T corresponding to the difference between a sampled timestamp and the next one in the loop would show some spikes in the same order of magnitude of the network-independent jitter.

Figure 5 shows the results obtained with the dummy program running for one million iterations -corresponding to 7.41 s in the baseline configuration. Four spikes in the order of 15 µs can be observed, which gives an idea about the minimum jitter that can be observed on such a system, independently from the network stack.

In that same setup, figure 6b depicts the time series of packet inter-arrival times as measured by the VPF, while figure 6a shows the time series of the duration between two consecutive ISR, this data being obtained with the kernel tracing subsystem. Confronting both figures as well as figure 5 suggests that the jitter seen by the VPF is a mixture of (i) network-independent jitter as shown by the similarity of the spikes in figure 5 and figure 6b, and (ii) network jitter as shown by the similarity of the 1 µs-wide noise around the 7.41 µs average in figure 6a and6b.

Figure 7a and figure 7b give finer-grained information about the jitter introduced by the network stack itself i.e., from ISR to the VPF. For example, there is a small but noticeable amplification in the standard deviation between the distribution Given the previous analysis of the baseline system, the sources of jitter enumerated in section II are restored independently so as to study their relative contribution.

C. ISR Start Of Execution

For multiple reasons, the elapsed time between interrupt and ISR execution can vary, hence jitter. For example, the CPU core handling the interrupt can be idle when the interrupt is raised. This is evaluated by removing the idle=poll kernel parameter. In this situation, figure 8 shows the apparition of many spikes in the order of 15 µs when compared to figure 6a.

When interrupts are routed to a different CPU core than the one on which the VPF is scheduled, it is plausible to assume jitter reduction as ISRs are granted a dedicated core. Jitter increase is also plausible because of the requirement for intercore synchronisation, which is a source of jitter i.e., because of cache synchronisation or IPIs. Jitter increase is also possible because the newly dedicated core is not doing anything else, which means it is likely to be asleep, hence a wake-up-induced jitter at ISR execution.

To discriminate between those hypotheses, three experiments have been designed as follows: In the first experiment (figure 6a) NIC interrupts are routed to the same CPU core as the one on which the VPF is scheduled, in the second (figure 9a), NIC interrupts are re-routed to a different CPU core, and on the third (figure 9b), NIC interrupts are re-routed to a different CPU core, but the latter is kept busy by an infinite loop. The CPU core configuration in those two last experiments is illustrated in figure 4b. According to these figures, the most likely hypothesis is that routing the interrupts to a dedicated core slightly increases jitter in the absence of another program on the same core, and significantly increases it in the presence of an always runnable thread on that CPU core (with frequent spikes in the order of 15 µs).

D. Linux Scheduler induced jitter

The straightforward approach to packet reception is to use the recvfrom function exposed by the kernel, which in its default behaviour, and if no packet is available in the socket queue at the time of the call, blocks and triggers a context switch and a call to the Linux scheduler. It will, therefore, need to be rescheduled as soon as the network stack makes a packet available to the socket, hence introducing additional jitter. Even with the idle=poll kernel option, such an approach shows spikes of up to 16µs (figure 10. Without the latter kernel option, this blocking leads to even more jitter, showing spikes of up to 60µs

As explained in section IV-A, that jitter can be eliminated by receiving packets in polling mode.

E. Interrupt Throttling jitter

The major source of jitter studied in this paper originates in the NIC's interrupt moderation capacities. Those features prevent the NIC from flooding a CPU core with interrupts at high data rates by limiting the rate at which it triggers an interrupt. But at low data rates, those features introduce unnecessary and variable latency, as some interrupts are delayed, preventing the CPU from processing the incoming packet unless the throttling period has elapsed.

As described in [START_REF]/XL710 Datasheet[END_REF], the Intel XL710 NIC, supports two interrupt moderation features: Interrupt Throttling (ITR) and Interrupt Rate Limiting (INTRL). ITR limits the instantaneous interrupt rate, and guarantees a minimum gap between two consecutive IRQs, whereas INTRL limits the average number of interrupts per second on a given period.

On the vanilla 4.13 Linux kernel, those options were not configurable at runtime and needed a kernel compilation in order to be changed. The default behaviour is to use an adaptive algorithm to change the ITR period depending on the current input bandwidth. On the 4.17 kernel, ITR is configurable using ethtool but INTRL still remains alwayson. The results described hereafter were obtained with a custom kernel, specifically tweaked so as to disable INTRL.

The effects of ITR is quantified in this section by enabling it on the 4.17 kernel and choosing an ITR period equal to 100 µs. This value is chosen because it is the same as the default value on Linux 4.13. Results of this experiment are depicted in figure 11. The 100 µs spikes caused by ITR can easily be observed in this figure. These processing phases show nearly no jitter and do not show any pattern change if a blocking socket is used instead of a nonblocking polling loop. This last behaviour can be explained, as even a recvfrom call in a blocking setup will block once in every 100 µs as shown in figure 11. Therefore, ITR hides all the other sources of latency studied here.

V. CONCLUSION

As video production streams have a low tolerance for jitter, characterising it on a COTS server running a generalpurpose OS is a crucial step, on the path towards building VPFs for a software-based, all-IP, video production setup. A detailed analysis of the packet reception path showed that sources of jitter can be classified as either (i) hardwarerelated such as ITR or the variable delay between the ISR and the interrupt, (ii) network-stack related such as the impact of the Linux scheduler, or (iii) network-independent such as SMIs, unrelated interrupts, or any higher priority code stealing cycles from the CPU. A quantitative study assessed that, in the context of ST2022-6 reception, hardware-related effects and especially ITR have the stronger impact, as they easily hide the impact of the Linux scheduler. The experimental methodology exposed in this paper consists of building a baseline system with a minimal jitter (through system analysis and experimental iterations) and reinstating each potential source of jitter, to study its impact.

The jitter characterisation for ST2022-6 achieved here gives, at the same time, results about the particular hardware setup used in the performed experiments -allowing to better understand the constraints a VPF needs to satisfy and the performance it can get from the OS -and a generic methodology to reproduce the study on any commodity platform, potentially enabling the implementation of software-based VPFs in a variety of environments.

Figure 1 .

 1 Figure 1. Schematic view of the path taken by a data packet -from Network Interface Card (NIC) to Application.

Figure 2 .

 2 Figure 2. Abstract view of the analysed system

Figure 3 .

 3 Figure 3. Histogram of the packet inter-arrival times at the ingress of the server

Figure 4 .

 4 Figure 4. Interrupt and scheduling affinity. Involved cores are identified as core 1, 2 and 3.

  : (a) A commercial SDI to ST2022 converter configured to output an ST2022 stream encapsulating a 1080i 29.97 frames per second video test pattern is used as CBR Generator. (b) A server with two Intel(R) Xeon(R) CPU E5-2690 v4 is used as the COTS server. (c) An Intel(R) XL710 with a 40 Gbit/s optical interface is used as the Ingress NIC. (d) An interconnection between the packet generator and the COTS server through a Cisco Nexus 9000 fully nonblocking switch.

Figure 5 .Figure 6 .

 56 Figure 5. Dummy program : 1M acquisitions

Figure 7 .Figure 8 .

 78 Figure 7. Baseline system: Histogram of T

Figure 9 .

 9 Figure 9. System with re-routed interrupts: irq_entry

Figure 11 .

 11 Figure 11. Measurements with ITR activated and setting of T IT R = 100µs


Benoît Pit-Claudel
email: benoit.pit-claudel@polytechnique.edu

Yoann Desmouceaux
email: yoann.desmouceaux@polytechnique.edu

Pierre Pfister
email: ppfister@cisco.com

Mark Townsley
email: townsley@cisco.com

Thomas Clausen
email: thomas.clausen@polytechnique.edu

Stateless Load-Aware Load Balancing in P4

Leveraging the performance opportunities offered by programmable hardware, stateless load-balancing architectures allowing line-rate processing are appealing. Moreover, it has been demonstrated that significantly fairer load-balancing can be achieved by an architecture that considers the actual load of application instances when dispatching connection requests. Architectures which maintain per-connection state for resiliency and/or track application load state for fairness are, however, at odds with hardware-imposed memory constraints. Thus, a desirable load-balancer for programmable hardware would be both stateless and able to dispatch queries to application instances according to their current load.

This paper presents SHELL, a stateless application-aware load-balancer combining (i) a power-of-choices scheme using IPv6 Segment Routing to dispatch new flows to a suitable application instance from among multiple candidates, and (ii) the use of a covert channel to record/report which flow was assigned to which candidate in a stateless fashion. In addition, consistent hashing versioning is used to ensure that connections are maintained to the correct application instance, using Segment Routing to "browse" through the history when needed. The stateless design of SHELL makes it suitable for hardware implementation, and this paper describes the implementation of a P4-NetFPGA prototype. A performance evaluation of this SHELL implementation demonstrates throughput and latency characteristics comparable to other stateless load-balancing implementations, while enabling application instance-load-aware dispatching and significantly increasing per-connection consistency resiliency.

I. INTRODUCTION

In data-center and cloud architectures, workload virtualisation has become the norm, with applications replicated among multiple application instances, each capable of independently serving incoming queries [START_REF] Bernstein | Containers and cloud: From lxc to docker to kubernetes[END_REF], [START_REF] Dragoni | Microservices: yesterday, today, and tomorrow[END_REF], [START_REF] Hindman | Mesos: A platform for fine-grained resource sharing in the data center[END_REF]. An important functional part in these architectures is the load-balancer (LB), dispatching incoming queries amongst application instances. To make the load-balancer "invisible", a Virtual IP Address (VIP), shared by all application instances providing the same service, is advertised to the Internet in place of the address of the load-balancer, requiring the load-balancer to provide perconnection consistency (PCC), i.e. ensuring that traffic from a connection (typically identified by its network 5-tuple: source & destination addresses, L4 protocol, source & destination port) is always directed to the same application instance. Naive load balancing use Equal Cost Multi-Path (ECMP) [START_REF] Thaler | Multipath issues in unicast and multicast nexthop selection[END_REF] mapping connections to application instances, using a hash function and a modulo operation.

A. Challenges

A drawback of using ECMP for load-balancing is the lack of resiliency to changes to the application instance set, which causes the modulus in the ECMP operation to change and most connections to be redistributed across application instances, thus breaking PCC and causing connection resets. Consistent hashing [START_REF] Karger | Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web[END_REF], [START_REF]Web caching with consistent hashing[END_REF], [START_REF] Thaler | Using name-based mappings to increase hit rates[END_REF] attempts to address this, by providing a more resilient mapping of connections across application instances [START_REF] Eisenbud | Maglev: A fast and reliable software network load balancer[END_REF], [START_REF] Patel | Ananta: cloud scale load balancing[END_REF] through maintaining an intermediate table which, with high probability, yields a persistent mapping of the 5-tuple space to the set of application instances, even when faced with changes in the application instance set. Maglev [START_REF] Eisenbud | Maglev: A fast and reliable software network load balancer[END_REF] uses consistent hashing with per-connection state to maximize the probability of PCC: a connection breaks only when both (i) per-connection state is removed (if memory is exhaustede.g. due to a denial-of-service attack -or if traffic is rebalanced to a new LB instance) and (ii) consistent-hashing changes the mapping of the connection to a different application instance (if there is a change in the set of application instances, which should affect only a small number of connections).

The pseudo-random nature of consistent hashing assigns queries to application instances regardless of their actual load state [START_REF] Eisenbud | Maglev: A fast and reliable software network load balancer[END_REF]. While this does not pose any problem for non-CPU-intensive applications (e.g. serving static Web pages), performance may degrade for CPU-intensive applications (e.g. data processing), for which the number of concurrently served queries per application instance must be minimized. Assigning queries to the least loaded from among two randomly chosen application instances (rather than to one randomly chosen application instance) was shown in [START_REF] Mitzenmacher | The power of two choices in randomized load balancing[END_REF] to improve load-balancing fairness. Based on this, 6LB [START_REF] Desmouceaux | 6lb: Scalable and application-aware load balancing with segment routing[END_REF] combines a Maglev-like consistent hashing with assigning connections to set of two application instances, which decide amongst themselves which will accept the connection. This is achieved by forwarding connection request (SYN) packets using IPv6 Segment Routing (SR) [START_REF] Filsfils | The segment routing architecture[END_REF] and then by maintaining state in the LB as to which server has accepted the connection.

The need to keep connection-state make Maglev and 6LB difficult to implement on programmable hardware devices, whereas it is known that hardware-based load-balancers offer a potential performance benefit [START_REF] Miao | Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics[END_REF], [START_REF] Gandhi | Duet: Cloud scale load balancing with hardware and software[END_REF], [START_REF] Olteanu | Stateless datacenter load-balancing with beamer[END_REF]. Beamer [START_REF] Olteanu | Stateless datacenter load-balancing with beamer[END_REF] circumvents this state requirement, by calling on assistance from servers hosting application instances to maintain PCC. When the set of application instances changes, and consistent hashing maps a flow to a different application instance, Beamer directs packets from that flow to that new application instance, while also embedding the address of the previously used application instance in the packet header. This allows the new application instance, in case it does not have connection state for a received packet, to forward it to the previous instance.

A shared requirement of [START_REF] Desmouceaux | 6lb: Scalable and application-aware load balancing with segment routing[END_REF], [START_REF] Olteanu | Stateless datacenter load-balancing with beamer[END_REF] is that an application instance is able to direct packets to a second application instance, when needed. For 6LB, only connection establishment packets are proposed to two application instances, allowing load sharing -at the expense of state in the LB for forwarding subsequent packets directly to the correct application instance. Beamer offers packets to two application instances only when there is a change in consistent hashing -but, then, does so for all packets in a flow, to avoid keeping state in the LB.

Thus the question: is it possible to provide a stateless loadbalancer that dispatches queries according to the state of the applications? This requires the LB to be able to (i) send connection requests through a chain of "candidate" application instances for local connection acceptance decisions, and (ii) statelessly direct packets in an established flow to the one application instance which accepted the connection request.

B. Statement of Purpose

This paper introduces SHELL, an application-agnostic, application-load-aware, stateless load-balancer, which (i) proposes new connections to a set of pseudo-randomly-chosen application instances, each making a local acceptance decision, and (ii) "marks" subsequent packets in a flow so as to allow the load-balancer to direct them to the appropriate application instance without requiring the load-balancer to maintain perconnection-state.

The statelessness of the load-balancer makes it a candidate for an implementation in a hardware platform. Thus, this paper proposes a prototype P4-NetFPGA [START_REF] P4 | P4 → NetFPGA: A low-cost solution for testing P4 programs in hardware[END_REF] implementation of SHELL targeting the NetFPGA SUME [START_REF] Zilberman | Netfpga sume: Toward 100 gbps as research commodity[END_REF] platform, as well as an extensive performance evaluation of the P4 implementation and of the stable hashing algorithm.

C. Paper Outline

The remainder of this paper is organized as follows: section II provides an overview of SHELL, with section III de-tailing key design aspects. The P4-NetFPGA implementation of the load-balancer is detailed in section IV, followed by a performance evaluation in section V. Resiliency of consistent hashing is evaluated in section VI, before section VII concludes this paper.

II. OVERVIEW

SHELL consists of 3 main components: a control plane, a P4-based load-balancing data-plane, and a server agent. An exemple execution is illustrated in figure 1.

The control-plane constructs two tables (see section III-B): (i) a consistent hashing table, used to direct new connection request packets (e.g. TCP SYNs) to a set of candidate application instances, which improves fairness, and (ii) a choice history table, for directing subsequent packets in a flow (e.g. TCP ACKs), which improves resiliency.

The P4 load-balancer uses 5-tuple hashing to map each new connection request to a set of candidate application instances from the consistent hashing table provided by the controlplane. Segment Routing (SR) [START_REF] Filsfils | The segment routing architecture[END_REF] is then used to direct such packets through the selected set of application instances, until one accepts the connection (note that the last application instance in the set must always accept), as in [START_REF] Desmouceaux | 6lb: Scalable and application-aware load balancing with segment routing[END_REF]. The position in the list of the application instance which accepted the connection, c i , is communicated back to the client (see section III-C), which in turn includes it in all further packets from the client to the load-balancer. This enables the P4 load-balancer to send these packets directly to the application instance handling the connection. When a change in the set of application instances causes modifications to some of the consistent hashing buckets, changes are saved in a history. The P4 load-balancer then directs (using SR) subsequent packets to the current and previous application instances associated with the value c i received in the packets.

Finally, the server agent (i) accepts new connection requests or forwards them to the next candidate application instance, and (ii) forwards further packets until reaching the application instance that accepted the connection. This server agent is

Algorithm 1 Consistent hashing history table construction update version numbers for b ∈ {0, . . . , B -1}, i ∈ {h-1, h-2, . . . , 1}, j ∈ {0, . . . , c-1} do t[b][i][j] ← t[b][i -1][j] end for build new consistent hashing table for b ∈ {0, . . . , B -1}, j ∈ {0, . . . , c-1} do t[b][0][j] ← consistentHashing(b, j) end for remove duplicates for b ∈ {0, . . . , B -1}, j ∈ {0, . . . , c-1} do if t[b][0][j] = t[b][i][j] for some i = 0 then delete t[b][i][j] and shift t[b][i + 1, . . . , h -1][j] upwards end if end for

III. DESCRIPTION

In this section, c is the number of candidate application instances, through which connection requests are directed, B the number of buckets used in consistent hashing, h the "depth" of the consistent hashing "history matrix" maintained for a bucket t[b] (an example of t[b] for a bucket b is shown in table I).

A. Data Plane

The behavior of the P4 load-balancer and of the application instance depends on which packet is received:

1) A connection request (TCP SYN) received at LB is hashed, on its 5-tuple, into a bucket with index b. The first row of the history matrix for b, t[b][0][:], is then used for generating an IPv6 SR header [START_REF] Previdi | IPv6 Segment Routing Header (SRH)[END_REF] with a segment list of

(t[b][0][0], . . . , t[b][0][c-1]
) followed by V IP -in the example from table I: (s 3 , . . . , s 4 , V IP ).

2) A connection request (TCP SYN) received at application instance is processed by the server agent -which examines its local state (e.g. its CPU load), and determines to either accept the request, or to forward the packet to the next segment in the SR header. Note that the last candidate in the list must always accept the connection.

A server agent having accepted a connection will record, for the connection lifetime, its own index c i in the segment list received with the connection request.

3) When an application instance accepts a connection, it will embed the recorded c i for that connection in the TCP SYN-ACK and in all future outgoing for that connection, using a covert channel -how this is accomplished is discussed in section III-C. 4) All subsequent (i.e. TCP non-SYN) packets sent by the client will also encode c i , again using a covert channel. 5) All subsequent (i.e. TCP non-SYN) packets received at the LB are hashed, on their 5-tuple, identifying a bucket b. The LB also extracts the value c i from the covert channel. The c ith colum of t[b] is then used to generate an IPv6 SR header with segment list

(t[b][0][c i ], . . . , t[b][h-1][c i ]
) followed by the VIP -in the example from table I: (s 3 , s 2 , . . . , s 13 , V IP ).

6) All subsequent (i.e. TCP non-SYN) packets received at the application instance will be examined, and if corresponding connection-state is found, will be processed locallyotherwise, are forwarded to the next segment 1 .

B. Control Plane -Consistent Hashing Table Computation

The algorithm described in [11, algorithm 3] is used to generate, for each bucket b, a candidate list of application instances = (s 1 , . . . , s c ). This list is recorded as the first row of the history matrix for the bucket:

t[b][0][:] = .
When the set of application instances is modified, all entries in the history matrix are offset by one (i.e. ∀b,

t[b][i+1][:] ← t[b][i][:]),

C. Possible covert channels

The server-state-aware and stateless load-balancing approach described in this paper relies on the application instance being able to inform clients to include c i (the position of the application instance in the segment list at time of connection establishment) in all packets subsequent to the connection request. This c i is used by the load balancer to direct these to the appropriate application instance.

If it is possible to modify the client networking stack so as to cooperate with the load-balancing architecture, a simple option would be to embed the identifier (rather than the value of c i ) of the application instance having accepted the connection in packets sent from the application instance, then reflect this identifier in the packets sent by the client. This can be achieved with transport protocols such as QUIC, which embed a connection identifier chosen by servers and reflected by clients.

However, for TCP connections, it is necessary to convey c i from the application instance to the client, and make the client relay c i in subsequent packets, without client-side modification. This requires using a covert channel from the application instance, through the client, and to the application instance, which the client neither inspects nor interferes with. Approaches accomplishing this include:

TCP sequence numbers, which are reflected by endpoits in the acknowledgement field. For connections shorter than 1/c of the sequence number space (i.e. 2 32 /c bytes), this allows implementing the covert channel through the high-order bits of the sequence number. For longer connections, a flow table will be however required.

TCP timestamps, which are also reflected by TCP endpoints. The covert channel can be carried in the low-order bits of the TCP timestamp, as is done in [START_REF] Duchene | Making multipath tcp friendlier to load balancers and anycast[END_REF] -and according to [START_REF] Medina | Measuring interactions between transport protocols and middleboxes[END_REF], [START_REF] Honda | Is it still possible to extend tcp?[END_REF] is resilient to middlebox processing. Modifying the timestamp by at most c -1 units (c = 2 usually [10]) will have a negligible effect on RTT estimation.

To avoid using a flow table, SHELL uses TCP timestamps as covert channel for TCP connections: the server agent of the accepting application instance encodes its index c i in the low-order bits of the TCP timestamp -and the LB inspects TCP timestamp sent by clients.

IV. P4 LOAD-BALANCER IMPLEMENTATION

The workflow of the P4 implementation of the LB dataplane of SHELL is illustrated in figure 2. It uses three matchaction tables, corresponding to (i) segment lists to be inserted into SYN packets, as given by the first row of the history matrix, (ii) segment lists to be inserted in non-SYN packets, as given by columns of the history matrix, and (iii) a Layer-2 lookup for output packets.

Processing a packet starts with parsing its headers. If they do not match the expected format (e.g. the packet uses UDP), the packet is dropped; otherwise, they are processed by the match-action pipeline. Both (i) the 5-tuple hash of the packet, computed by way of an external function from the P4-NetFPGA framework, and, (ii) in case of a non-SYN packet, the covert channel value as found in the TCP timestamp field (see below), are used as keys to the match tables, to access the corresponding segment list. The segment list is then fed to an action, which builds the SR header. To complete the matchaction pipeline, a match is performed on the newly-added destination address of the packet (i.e. the first SR segment), which calls an action making the packet egress through the correct interface. Finally, the de-parsing stage emits the packet with the newly-built headers.

For want of a lookahead function and of variable-length header support in the compiler, only a set of "reasonable options" is parsed (specifically, SACKs and timestamps, i.e. those that can be found in non-SYN packets according to [START_REF] Medina | Measuring interactions between transport protocols and middleboxes[END_REF]). Depending on the length of the TCP header found in the "data offset" (d of f ) field, an option header of suitable type is parsed, corresponding to lengths d of f ∈ {8, 11, 13, 15}. Figure 3 depicts an example of such a parsing, when d of f = 11. The bits of the covert channel are then stored into a meta-data field 2 . A parameter of interest to the performance of the dataplane is the maximum size of the parsed TCP header d max of f : its influence on the performance is evaluated in section V.

V. P4-LB IMPLEMENTATION PERFORMANCE

A key element to the performance of SHELL is the perpacket latency, incurred in the P4-dataplane of the LB. It depends primarily on two factors: (i) the latency incurring when receiving a packet over an ingress interface, inserting an SR header, and transmitting this (now larger) packet over an egress interface (section III-A), and (ii) the latency incurring from extracting c i from within a TCP option (TCP timestamp, section III-C).

These factors are evaluated using the P4-NetFPGA framework and the Xilinx Vivado software suite, simulating packets going through one interface of a 10G NetFPGA-SUME, and are documented in this section.

A. Effect of SR Header Insertion on Latency

For the purpose of the simulations, c = 2 choices were used for SYN packets, and a history of h = 2 was used for ACK packets, thus SR headers with 3 segments were inserted, increasing the packet size by 56 bytes between ingress and egress. Feeding ingress packets at maximum line-speed fills the egress interface queue over time, thus progressively increasing packet forwarding latency -as depicted in figure 4, showing stable results from above 1500 packets. When the egress buffer is empty, the latency is 2.1 µs, and when the buffer is full it oscillates between 8.2 µs and 9.0 µs. Thus, for subsequent simulations, batches of 4800 packets are injected at line-rate on the ingress interface.

Table II reports the throughput and worst-case latency obtained: SHELL, comparable to Beamer [START_REF] Olteanu | Stateless datacenter load-balancing with beamer[END_REF], can sustain 60 Mpps, i.e. 22× as much as what is reported for the single-core software implementations of Maglev [START_REF] Eisenbud | Maglev: A fast and reliable software network load balancer[END_REF], while also providing application instance load-awareness.

B. Effect of TCP Parsing on Latency and FPGA Resources

As explained in section IV, the TCP timestamp option is parsed by matching a predefined set of option headers, thus the greater d max of f (maximum admissible size of parsed TCP headers), the more program branches -and the greater the latency. This is evaluated by testing d max of f ∈ {8, 11, 13, 15}, and depicted in figure 5. The latency varies from 1.8 µs (d max of f = 8) to 2.1 µs (d max of f = 15) for an empty egress queue, and its average after the egress queue has filled up goes from 7.7 µs (d max of f = 11) to 8.5 µs (d max of f = 15). This allows noting that, in a controlled environment (e.g. a data-center, where SHELL typically would be deployed), where a strict set of TCP options can be enforced, it is possible to trade off parsing safety against reduced latency. However, parsing more potential options increases the amount of logic consumed on the FPGA. As reported in table III, which depicts the resource usage on the FGPA for different values of d max of f , this can increase LUT usage by up to one third.

VI. CONSISTENT HASHING RESILIENCY

Long-lived connections are particularly vulnerable to application instance reconfigurations -thus, as a worst-case scenario, simulations using infinite-length connections, and subject to successive application instance removal/insertions, are performed; each simulation is repeated 5 times.

For a random connection, assuming that it was uniformly drawn from among the B × c buckets and choices possible, the probability that it is reset3 after n application instance reconfigurations, is depicted in figure 6 (top), which shows the impact of the history depth h, and figure 7 . SHELL consistent hashing evaluation: probability for a connection started at time t = 0 to be reset after n server reconfigurations. 500 servers, c = 2 choices, h = 3, different number of buckets B. Top: infinite connections. Bottom: connection duration and server reconfiguration rate model from [START_REF] Miao | Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics[END_REF], [START_REF] Roy | Inside the social network's (datacenter) network[END_REF].

In realistic scenarios, application instance reconfigurations are expected to be rare, and connections are unlikely to last for more than a few application instance reconfigurations -at most. The bottom graphs of figures 6 and 7 depict the connection reset probability using the connection duration distribution model from [22, Figure 7.a], and with the application instance reconfiguration rate distribution taken as the highest 1% rates over a month for 100 clusters from [13, Figure 2] -with a median reconfiguration rate of 13.5 min -1 .

In these conditions, less than 1% of the connections were lost when using SHELL with a non-void history (h > 1). Without history (i.e. h = 1, as would be the case in [START_REF] Eisenbud | Maglev: A fast and reliable software network load balancer[END_REF], [START_REF] Desmouceaux | 6lb: Scalable and application-aware load balancing with segment routing[END_REF]), more than 5% of the connections were lost.

VII. CONCLUSION

This paper has introduced SHELL, an application-agnostic load-balancing architecture which combines application load awareness (by using a power-of-choices scheme upon connection establishment), statelessness (by using a covert channel to indicate which of the candidates had accepted the connection), and resiliency (by using consistent hashing and versioning). Being stateless makes SHELL suitable for a hardware implementation, as demonstrated in this paper through prototype development using the P4-NetFPGA framework. An evaluation of throughput and latency of this prototype implementation shows that the attainable performance is equal to that of other hardware implementations, while providing applicationawareness and therefore improving load-balancing fairness. Further, simulation of the consistent hashing resiliency shows that the number of long-lived connections dropped, even in worst-case scenarios, is negligible.

Figure 1 . 2 )

 12 Figure 1. SHELL overview. (a) A SYN packet is steered through c = 2 candidate servers (c 1 , c 2 ), in this example (s 2 , s 1 ). Here, the second candidate c 2 = s 1 accepts the connection. This choice c 2 is reported in the covert channel of the SYN-ACK packet. (b) Subsequent packets from the client are steered by the LB to the correct server s 1 , by looking up the covert channel value c 2 in a consistent hashing table. (c) Upon server reconfiguration, with high probability the assigned server is not modified due to consistent hashing. (d) A server reconfiguration modifies the candidate list to (c T 1 , c T 2 ) = (s 3 , s 2 ). SHELL then uses the history matrix to go through previous servers that were c 2 for this bucket -here, (c T 2 , c T -1 2 ) = (s 2 , s 1 ).

  and the new mapping of candidate application instances for each b is calculated, as per[11, algorithm 3].Since consistent hashing will leave most bucket entries unmodified after server reconfigurations [8, figure12] [11, figure 7], i.e. t[b][0][:] = t[b][START_REF] Bernstein | Containers and cloud: From lxc to docker to kubernetes[END_REF][:] for most b, duplicate history entries are removed as per algorithm 1.

Figure 3 .

 3 Figure 3. Example TCP TLV parsing in the P4 LB, for d of f = 11.

Figure 4 .Figure 5 .

 45 Figure 4. SHELL P4 dataplane evaluation: per-packet latency for a burst of 4800 packets (c = 2, h = 2, d max of f = 11)

Figure 6 .

 6 Figure 6. SHELL consistent hashing evaluation: probability for a connection started at time t = 0 to be reset after n server reconfigurations. B = 35591 buckets, 500 servers, c = 2 choices, different history depths h. Top: infinite connections. Bottom: connection duration and server reconfiguration rate model from[START_REF] Miao | Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics[END_REF],[START_REF] Roy | Inside the social network's (datacenter) network[END_REF].

Figure 7

 7 Figure 7. SHELL consistent hashing evaluation: probability for a connection started at time t = 0 to be reset after n server reconfigurations. 500 servers, c = 2 choices, h = 3, different number of buckets B. Top: infinite connections. Bottom: connection duration and server reconfiguration rate model from[START_REF] Miao | Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics[END_REF],[START_REF] Roy | Inside the social network's (datacenter) network[END_REF].

  (top), which shows the impact of the number of buckets B.

	Connection reset probability	0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4	503 buckets 8737 buckets 31489 buckets 63709 buckets		Infinite connections
		0	50	100	150	200	250	300
	Connection reset probability	0 0.002 0.004 0.006 0.008 0.01 0.012 0.014	503 buckets 8737 buckets 31489 buckets 63709 buckets		Connection durations from model
		0	50	100	150	200	250	300
				Number of server reconfigurations

In the unlikely event that there is no next segment, the packet is droppedthis corresponds to the case where the history was not long enough to include the application instance that had accept the connection in the first place.

To ensure compatibility with clients not using TCP timestamps, if a SYN packet is missing the TCP timestamp option (detected by d of f ≤ 8), an SR header with only one candidate will be inserted. Lack of a TCP timestamp in non-SYN packets is then interpreted as a covert channel value of c 1 = 1.

A connection assigned to a bucket/choice pair is deemed reset after n reconfigurations if the application instance to which it was initially assigned no longer appears in the corresponding history table.

ACKNOWLEDGEMENTS

This work was supported, in part, by the Cisco-Polytechnique chair "Internet-of-Everything" (https://www.internet-of-everything.fr/).