Project topics and materials
Get Complete Project Material File(s) Now! »
Zero-Loss Virtual Machine Migration with IPv6 Segment Routing
Virtual Machine (VM) live migration [87] is a way to transfer a VM from a machine to another, by iteratively copying its memory. It is further suggested in [88, 89] that it is possible to perform live migration of individual processes or containers, thus attaining one further level of granularity of task placement flexibility. These techniques naturally find applications in the context of data centers, as these host heterogeneous workloads, whose lifetimes can vary greatly, and which can exhibit rapidly changing resource demands and inter-application dependencies. With live VM mi-gration, applications need not be tied to a specific machine – and their relocation can become part of a “natural” mode of data center operation. In this context, architectures have been developed in which workload migration is used as a baseline to achieve different goals [90]: energy minimiza-tion [91], network usage minimization [92], operational cost minimization [93], maintenance [94], etc. Thus, VM migration not only provides a way to accommodate hardware failures without service downtime, but more generally may be beneficial to the efficiency of the whole data center.
From a network perspective, a challenge raised by live migration lies in maintaining connec-tivity 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 [25] or NVGRE [26]. Other approaches include making use of Mobile IP [95] or of LISP [77]. The emergence of IPv6 [14] data-centers introduces other opportunities, 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) [78] 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 delay-critical applications, virtual network functions, …).
Statement of Purpose
The purpose of the chapter 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 by said VM. To that purpose, the Segment Routing (SR) architecture is leveraged.
As introduced in section 1.2.1, 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 engineer-ing), but can also represent more complicate instructions (from custom encapsulation or routing behavior to complete virtual network functions). With IPv6 Segment Routing (SRv6), segments are represented as IPv6 addresses embedded as a list in an IPv6 extension header [47].
The idea underlying this chapter is to use SRv6 to solve the locator/identifier mapping syn-chronization 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 host machine. This way, the responsibility of the old host machine is reduced to (i) forwarding packets locally while the migration is not complete and (ii) forwarding packets to the next segment (the new host machine) once migration has completed. This way, no packets are lost during the migration, whereas tra-ditional 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 machine is kept to a minimum, since no tunnel has to be established and no Layer-2 overlay is required.
Related Work
Numerous solutions have been proposed to address the issue of maintaining Layer-3 network connectivity during and after VM migration. The simplest involves using a Layer-2 overlay [25,26], and relying on hypervisors sending gratuitous Reverse ARP messages after migration. In addition to the operational complexity incurred by such overlays, the VM is not reachable on the new host machine 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 host machines. In [96], the Xen hypervisor is modified so that after migration, packets reaching the hypervisor at the source host machine are tunnelled towards the new host machine. 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 machine during an unpredictable amount of time by performing tunnelling. Furthermore, this is incompatible with para-virtualized interfaces such as virtio-net [97], where packets destined to VMs are not handled by the hypervisor.
In [98], 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 machine 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 machine before registration of the new location is complete. This approach is improved in [99], 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 [100], 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, other approaches orthogonal to the context of this chapter are worth mentioning. In [101], TCP options are used to facilitate migration of TCP connections. In a Software Defined Networking (SDN) context, [102] proposes a framework for virtual router migration, in which control planes and data planes are migrated during two distinct phases.
Chapter Outline
The remainder of this chapter is organized as follows. Section 3.2 introduces the high-level assumptions and mechanisms used for SR-based migration, before a formal specification is given in section 3.3. The proposed mechanism is then evaluated on different workloads in section 3.4. Finally, section 3.5 concludes this chapter.
SR-based Migration
As described in section 1.4, this chapter assumes that a VM is located within an IPv6 data-center, and accessible through a virtual IP address (VIP). Each machine within the data-center is accessible at a physical IP address (PIP), and can host several VMs. Located at the edge of the data-center, a gateway advertises (e.g., with BGP) the whole virtual address prefix.
A location database maintains a mapping between each virtual address and the physical address of the machine hosting the corresponding VM. When receiving traffic for a given VIP, the router will apply an SR policy consisting of one segment (the PIP of the machine hosting the VM). Each machine is running a virtual router (in the implementation described in section 3.4, VPP1), which is connected to the physical interface(s) of the machine, and to each VM via a virtual interface (in the implementation described in section 3.4, a vhost-user interface2). In sum, under normal operation (when the VM is running on a single machine), the gateway will tunnel traffic for a VM towards the machine hosting it.
The mechanism introduced in this chapter assumes that an orchestrator is running in the data-center, which decides on the allocation of VMs to physical machines. When the orchestrator decides to move a VM from a host machine to another, it proactively modifies the routing tables of the gateway, so that the traffic for the corresponding VIP is applied 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 direct traffic to the old host machine. As long as the VM has not completed migration, traffic will be intercepted by the old host machine (figure 3.1); as soon as migration is complete, the old host machine will simply forward traffic to the next segment (i.e., the new host machine). This way, no synchronization is required between the host machines and the networking infrastructure: rather, traffic is loosely sent to a logical path comprising both machines.
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.
Definitions
Forward to Local (f w)
The f w function simply forwards the packet to the next segment. In SR terminology [50], this corresponding to the END behavior.
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 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 [50] with a custom policy for forwarding decisions.
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 corre-sponding 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. Implementation-wise, packets are buffered in the local memory of the virtual router, per interface and in order. Such packet buffers 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.
Detailed Migration Process
For each VIP v, the controller maintains an entry L(v) in the gateway which is either R(m1) (“running on m1”) or M (m1, m2) (“migrating from m1 to m2”), 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 way of routing adjacencies in the FIB of the gateway. The gateway uses the transit behavior T.INSERT [50] for v, that is, this routing adjacency triggers insertion of an SR header on packets destined to v.
Table of contents :
I Introduction
1 Introduction
1.1 Background
1.1.1 Network Protocols
1.1.2 Data Center Architectures
1.2 Extending the Network Layer
1.2.1 Segment Routing (SR)
1.2.2 Bit-Indexed Explicit Replication (BIER)
1.3 Thesis Statement: Augmenting Data Centers through the Network Layer
1.4 Definitions and Working Assumptions
2 Thesis Contributions
2.1 Thesis Summary and Outline
2.2 List of Publications
II Task Mobility
3 Zero-Loss Virtual Machine Migration with IPv6 Segment Routing
3.1 Statement of Purpose
3.1.1 Related Work
3.1.2 Chapter Outline
3.2 SR-based Migration
3.3 Detailed Specification
3.3.1 Definitions
3.3.2 Detailed Migration Process
3.4 Evaluation
3.4.1 Ping (illustration)
3.4.2 HTTP Workload
3.4.3 Iperf Workload
3.4.4 Iperf Sink Workload
3.5 Summary of Results
4 Flow-Aware Workload Migration in Data Centers
4.1 Statement of Purpose
4.1.1 Related Work
4.1.2 Chapter Outline
4.2 Data Center Representation
4.2.1 Tasks and Machines
4.2.2 Network Model
4.3 Mathematical Modeling
4.3.1 Variables
4.3.2 Constraints
4.3.3 Objective Functions
4.3.4 Linearization
4.4 Flow-Aware Workload Migration
4.4.1 Resolution Algorithm
4.4.2 Computational Example
4.5 Pareto Front Approximation
4.5.1 Heuristic Formulation
4.5.2 Computational Experiments
4.6 Summary of Results
III Reliable Content Distribution
5 Reliable Multicast with BIER
5.1 Statement of Purpose
5.1.1 Related Work
5.1.2 Chapter Outline
5.2 Reliable BIER – Specification
5.2.1 Source Operation
5.2.2 Destination Operation
5.2.3 Parameter Discussion
5.3 Data-Center Simulations
5.3.1 Simulation Parameters and Setup
5.3.2 Uncorrelated, Localized Losses
5.3.3 Correlated, Localized Losses
5.3.4 Unlocalized, Bursty Losses
5.3.5 Influence of the Aggregation Timer
5.4 ISP Topology Simulations
5.5 Reliable BIER Performance Analysis
5.5.1 Model, Assumptions and Definitions
5.5.2 Computation of T[i], X[i]→j , and M⋆
5.5.3 Total Traffic Approximation
5.5.4 Discussion
5.5.5 Proof of Theorem 5.1
5.6 Summary of Results
6 Reliable BIER with Peer Caching
6.1 Statement of Purpose
6.1.1 Related Work
6.1.2 Chapter Outline
6.2 Overview: Reliable BIER with Peer Caching
6.2.1 Segment Routing Recovery
6.2.2 Peer Caching with Peerstrings
6.3 Specification
6.3.1 Source Operation
6.3.2 Intermediate Router Operation
6.3.3 Destination Operation
6.4 Peer Selection Policies
6.4.1 Random Peer Selection
6.4.2 Deterministically Clustered Peer Selection
6.4.3 Adaptive Statistically-driven Peer Selection
6.5 Policy Analysis
6.5.1 Recovery Locality
6.5.2 Clustered and Random Policies
6.5.3 Going Adaptive: the ε-Greedy Policy
6.6 Simulation Environment
6.6.1 Links and Link Loss Model
6.7 Data-Center Simulations
6.7.1 Network Topology
6.7.2 Evaluation Objectives
6.7.3 Static Peer Policy – One-Peerstring Mode
6.7.4 Static Peer Policy – Two-Peerstrings Mode
6.7.5 Adaptive Peer Policy
6.8 ISP Simulations
6.8.1 Network Topology
6.8.2 Peer Selection Policies Evaluation
6.9 Summary of Results
IV Load-Balancing
7 6LB: Scalable and Application-Aware Load Balancing with Segment Routing
7.1 Statement of Purpose
7.1.1 Related Work
7.1.2 Chapter Outline
7.2 Service Hunting with Segment Routing
7.2.1 Description
7.2.2 Connection Acceptance Policies
7.2.3 Protocol Overhead
7.2.4 Reliability
7.3 Horizontal Scaling with Consistent Hashing
7.3.1 Generating Lookup Tables
7.3.2 Analysis
7.4 In-band Stickiness Protocol
7.4.1 SR Functions
7.4.2 Handshake Protocol
7.4.3 Failure Recovery
7.5 Performance Analysis
7.5.1 System Model
7.5.2 Expected Response Time
7.5.3 Additional Forwarding Delay
7.5.4 Fairness Index
7.5.5 Wrongful Rejections
7.5.6 Response Time Distribution
7.5.7 Reducing the Number of Application Instances
7.6 Evaluation
7.6.1 Experimental Platform
7.6.2 Poisson Traffic
7.6.3 Wikipedia Replay
7.6.4 Throughput Evaluation
7.7 Summary of Results
8 Stateless Load-Aware Load Balancing in P4
8.1 Statement of Purpose
8.1.1 Chapter Outline
8.2 Overview
8.3 Description
8.3.1 History Matrix Computation
8.3.2 Possible covert channels
8.4 P4 Load-Balancer Implementation
8.4.1 Data Plane
8.5 P4-LB Implementation Performance
8.5.1 Effect of SR Header Insertion on Latency
8.5.2 Effect of TCP Parsing on Latency and FPGA Resources
8.6 Consistent Hashing Resiliency
8.7 Summary of Results
9 Joint Auto-Scaling and Load-Balancing with Segment Routing
9.1 Statement of Purpose
9.1.1 Related Work
9.1.2 Chapter Outline
9.2 Joint Load-Balancing and Autoscaling
9.2.1 First-available-instance Load-Balancing
9.2.2 Autoscaling
9.3 First-Available-Instance LB with 2 Instances
9.3.1 Markov Model
9.3.2 Applying RRR to the Markov Model
9.3.3 Closed-form Solution for c = 1
9.3.4 Solving for c ≥ 2
9.4 First-Available-Instance LB with n ≥ 3 Instances
9.5 Numerical Results
9.6 Wikipedia Replay
9.7 Summary of Results
V Conclusion
10 Conclusion
