Muhammad Siraj Rathore

Markus Hidell
email: mahidell@kth.se

Peter Sjödin

M Siraj Rathore

Data Plane Optimization in Open Virtual Routers

Keywords: network virtualization, virtual router, SoftIRQ, NAPI, Softnet API

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With the continuous growth of the Internet to new areas, services and applications, the demands increase on the ways in which we organize and manage networks. Future networks need to be flexible, support a diversity of services and applications, and should be easy to manage and maintain. One way of addressing these requirements is to virtualize routers. Router virtualization involves running several router instances on the same physical hardware, in a way that allows each instance to appear as a separate, independent router. This makes it possible to support a multitude of services, management disciplines, and protocols in parallel on different virtual routers.

A general approach to router virtualization is to use computing virtualization techniques to run multiple operating systems as guests in parallel on the same hardware, and let each guest run one instance of the router software. In open source virtual routers, these operating systems are based on open source software that can be combined with commodity PC hardware.

Broadly virtualization techniques can be categorized into hypervisor-based and container-based virtualization. With hypervisor-based virtualization (such as KVM and Xen), the hardware is virtualized so that each guest runs its own operating system. In contained-based virtualization (sometimes also called jails or operating system virtualization), the operating system is partitioned into multiple domains, where each guest runs in its own domain. Examples of container-based virtualization include FreeBSD Jail, Linux-VServer, OpenVZ, and Linux Namespaces. Containerbased virtualization is more -light weight‖ in the sense that it is based on partitioning of the operating system resources, something that could potentially be achieved with no or little extra processing overhead. The drawback is that all guests need to run the same operating system, as they are sharing the same operating system kernel. Hypervisor-based virtualization is more flexible in this respect but incurs a larger overhead, which limits the number of concurrent guests.

The purpose of our work is to study how container-based virtualization can be used for router virtualization. We focus on contained-based virtualization because of its potential for low processing overhead and support for many simultaneous guests. The starting point for our work is the observation that there is a significant performance penalty for performing packet processing in guests. The performance penalty comes from the level of indirection between network interfaces and virtual routers: When a packet arrives on a network interface, the corresponding virtual router should be identified, and the packet should be redirected to the virtual router. The way in which this redirection is performed has fundamental impact on overall performance.

A common solution is to use existing kernel components such as software bridges and virtual interfaces. In previous work we have shown that this is a costly solution in terms of performance, as it introduces considerable processing overhead [START_REF] Rathore | Performance Evaluation of Open Virtual Routers[END_REF]. A more promising approach is to use the macvlan device -a kernel object specifically designed for support of multiplexing and demultiplexing of packets between physical and virtual interfaces based on MAC addresses. The purpose of this paper is to investigate how a virtual router framework can be designed around the macvlan device and Linux Namespaces. We find that macvlan exhibits undesirable behavior at overload -when traffic load increases above a certain point, the effective throughput goes down. This is a considerable disadvantage of any routing platform, and we therefore propose a revised version, called NAPI-macvlan. The performance of NAPI-macvlan is studied in terms of throughput, scalability, and virtual router isolation properties. We demonstrate that NAPI-macvlan has superior performance, compared to macvlan, and does not exhibit the negative behavior at overload. The rest of this paper is organized as follows: Section 2 surveys related work on virtual router platforms. Thereafter, Section 3 describes a Linux virtual router framework based on macvlan devices and Namespaces. This section also introduces the NAPI-macvlan and gives the rationale behind its design. Section 4 presents and analyses performance measurements of virtual router configurations using macvlan and NAPI-macvlan. Finally, Section 5 concludes the paper.

Related Work

There are many examples of work, where different virtualization technologies are evaluated as virtual router platforms. For instance, Xen virtualization has been investigated in detail [START_REF] Egi | Evaluating Xen for virtual routers[END_REF] and it has been shown that Xen can achieve a considerable forwarding rate in the privileged domain, but that guest domain forwarding results in poor performance. Studies on data plane virtualization using Xen can also be found [START_REF] Anhalt | Analysis and experimental evaluation of data plane virtualization with Xen[END_REF], where packet forwarding through guest domain is suggested in order to virtualize the data plane. Another work demonstrates how to make efficient use of multicore commodity hardware for virtual routers [START_REF] Egi | Towards High Performance virtual routers on commodity hardware[END_REF]. It also identifies performance bottlenecks associated with the currently available commodity hardware.

VINI [START_REF] Bavier | In VINI Veritas: Realistic and Controlled Network Experimentation[END_REF] presents a virtual network infrastructure for network experimentation in a realistic and controlled environment. For router virtualization, VINI uses User-Mode Linux (UML) and Click to define custom data planes. The data plane runs in user space, something which gives great flexibility, but the implementation is also subject to a significant performance penalty.

Another platform for virtual networks is Trellis [START_REF] Bhatia | Trellis: A Platform for Building Flexible[END_REF]. Router virtualization in Trellis is based on customized components that have been introduced to improve forwarding rates. The resulting throughput is compared with virtual routers based on Xen and Openvz, it is shown that higher throughput can be achieved in Trellis.

An alternative virtual router enabling technology is to use a source code merging scheme as a mechanism to define custom data planes for virtual routers [START_REF] Keller | Virtualizing the data plane through source code merging[END_REF]. Source code is a language used to define the packet path for each virtual router. The packet path is specified in terms of networking functions that are connected together. Click and Linux VServer is used to provide virtual routers platform.

PdP (Parallel data Plane) presents a virtual network platform to achieve high speed packet processing [START_REF] Liao | PdP: Parallelizing Data Plane in Virtual Network Substrate[END_REF]. It runs control and data planes in guest machines for better isolation and flexibility. In order to boost the forwarding rate, PdP uses an architecture where multiple guest machines perform packet forwarding in parallel.

The Crossbrow architecture [START_REF] Liao | Crossbow: From Hardware Virtualized NICs to Virtualized Networks[END_REF] is yet another example of a virtual network platform. The focus is network resource virtualization to achieve fair bandwidth sharing among various virtual instances. Virtualization of physical network interfaces is proposed using different virtual devices (such as VNIC and virtual switch).

Linux Based Virtual Routers

A virtual router sends and receives packets on virtual interfaces. Besides this, a virtual router is just like a physical router: is has a routing table, routing protocols, packet filtering rules, management interface, and so on. A virtual router runs in a host environment, which is responsible for allocating resources to the virtual router, and for managing these resources. There can be multiple virtual routers in the same host environment, sharing the available resources, as illustrated in Fig. 1. Even though a virtual router communicates on virtual interfaces, its purpose is often to process packets that appear on the physical interfaces in the host environment. This means that the host environment needs to redirect packets between physical and virtual interfaces. When a packet is received on a physical interface, the host environment checks the packet in order to identify the virtual router to which the packet should be redirected, and makes the packet available to the virtual router on one of its virtual interfaces, When the virtual router has processed the packet and determined the next hop, the packet is placed on an outgoing virtual interface from where it is finally transmitted on a physical interface.

The redirection of packets between physical and virtual interfaces introduces a layer of indirection that is not present in a physical router. This functionality can be implemented in several ways. One common configuration is to use the regular software bridge module in the Linux kernel to interconnect the interfaces, as shown in [START_REF] Rathore | Performance Evaluation of Open Virtual Routers[END_REF]. The software bridge provides a general-purpose switching function that allows packets to be switched between interfaces (virtual or physical) based on MAC addresses and MAC address learning. This solution is general in the sense that it allows packet to be switched between any pair of interfaces, and it is an attractive solution being based on a well-known software component already available in the kernel. However, for the purpose of redirecting packets between virtual and physical interfaces, it introduces a considerable amount of overhead. This, in turn, incurs performance penalties, something that was investigated in previous work [START_REF] Rathore | Performance Evaluation of Open Virtual Routers[END_REF]. Similar solutions that have been used are the virtual switch [START_REF] Pfaff | Extending Networking into the virtualization layer[END_REF] and the short bridge [START_REF] Bhatia | Trellis: A Platform for Building Flexible[END_REF]. It is also possible to use, for example, IP routing and Network Address Translation (NAT) for traffic to and from virtual machines, but those are not suitable for virtual routers.

A promising solution from a performance point of view is to replace the software bridge with a multiplexing/demultiplexing module. This is a more restricted solution, but potentially more efficient, since it can move packets from physical interface to virtual with less overhead. In the following we will investigate this solution closer. We start by examining the packet processing path in a Linux-based virtual router in more detail.

Fig. 1. General design of Linux-based virtual routers

Packet Processing Path

When a packet is received on a Network Interface Card (NIC), the packet is transferred to a receive buffer in main memory, and an RX (receive) interrupt is generated. Interrupt processing is costly and can have large impact on forwarding performance [START_REF] Bianco | Open-Source PC-Based Software Routers: A viable Approach to High-Performance Packet Switching[END_REF]. Modern NICs provide features like interrupt coalescing and interrupt throttling for mitigating the negative effects of interrupt handling [START_REF]Intel: Interrupt moderation using Intel Gigabit Ethernet controllers[END_REF]. Current Linux use an RX interrupt processing scheme called NAPI [START_REF] Salim | Beyond softnet[END_REF], adopted from kernel 2.4.20 [START_REF] Rio | A map of the networking code in Linux kernel 2.4.20[END_REF]. Instead of using one hardware interrupt per packet, NAPI combines interrupts with polling so that multiple packets can be processed within a single hardware interrupt. The NAPI interrupt handler accumulates packets in receive buffers, and schedules a software interrupt (SoftIRQ) to trigger processing of a batch of incoming packets. After a SoftIRQ, the packet is delivered towards a virtual router via the corresponding virtual interface (VIF). Virtual interfaces are exactly like physical interfaces except that they are completely implemented in software. Therefore, no hardware interrupts are involved. A common example of a virtual interface is veththe virtual Ethernet device. It has its own MAC address and an administrator has full access to its configuration in terms of MAC address, IP address assignment etc. Another example of virtual interfaces is the macvlan device, which will be discussed in more detail below. Both veth and macvlan are the part of the Linux kernel (2.6.x). When the virtual router has processed a packet from its incoming virtual interface, the packet will be scheduled for transmission on an outgoing NIC. The outgoing NIC has a transmit (TX) queue where outgoing packets are placed. The NIC is then informed that outgoing packets are ready for transmission. The NIC's DMA engine fetches the packet from host memory and transmits it onto the physical media.

The macvlan Virtual Interface

In previous work we investigated how a careful selection of virtual interface and approach for redirecting packets between virtual and physical interfaces can improve the overall system performance [START_REF] Rathore | Performance Evaluation of Open Virtual Routers[END_REF]. We compared a macvlan-based virtual router with veth/bridge-based virtual router using both OpenVZ and Linux namespaces virtualization environments. We concluded that, in comparison with veth/bridge, a macvlan based virtual router is far less CPU demanding and can achieve higher throughput. In addition, it shows better behavior in overload situations.

Fig. 2. Data plane for a macvlan based virtual router

The macvlan device provides a mechanism to define multiple virtual interfaces on top of a single physical interface. Each virtual interface is bound to a physical interface and has its own MAC address. A MAC address table is maintained for the virtual/physical address mapping. Fig. 2 depicts the packet data path for a macvlanbased virtual router. A packet received in a physical ingress interface enters into the virtual router through a virtual interface, macvlan A. After MAC level processing, the packet is queued in a backlog queue and a SoftIRQ is scheduled. When the SoftIRQ occurs, the packet is fetched from the queue for processing in the virtual router. As a result of the processing, an outgoing virtual interface is determined, and the packet is handed over to this virtual interface, macvlan B. There, the packet is buffered in another backlog queue and a new SoftIRQ is scheduled. Finally, upon the new SoftIRQ, the packet is moved from the backlog queue to the transmission queue of the physical egress interface.

Like a physical interface, a virtual interface always delivers a packet for receive interrupt processing after interface level processing. It can be observed in Fig. 2 that there is a backlog queue following each macvlan device. This design stems from the use of the Softnet API (a predecessor of NAPI). Upon completion of interface level processing, the macvlan device calls Softnet API, which buffers the packet in a backlog queue and schedules a SoftIRQ for further packet processing [START_REF] Salim | Beyond softnet[END_REF]. The Softnet API performance limitations are well known for physical interfaces [START_REF] Bianco | Open-Source PC-Based Software Routers: A viable Approach to High-Performance Packet Switching[END_REF], and can create livelock situations at high traffic loads. We believe that the use of the Softnet API for virtual interfaces has the following design weaknesses: Backlog queue congestion can cause serious throughput degradation for bridge/veth based virtual routers [START_REF] Rathore | Performance Evaluation of Open Virtual Routers[END_REF]. The backlog queue is maintained on a per CPU basis, which means that virtual routers running on the same CPU will share the same queue. This may result in resource contention, something that can corrupt isolation properties between virtual routers. It may also limit overall system scalability. There are multiple queuing points along the data path. This may cause unnecessary delays in packet processing, and lead to inefficient usage of CPU resources.

Fig. 3. Data plane for a NAPI-macvlan based virtual router

In order to address these issues, we introduce two changes in the data path:

The backlog queues are eliminated from the data path. Packet receive processing is modified to that a packet is carried from the ingress interface, through virtual router, to the TX queue of outgoing physical interface in a single SoftIRQ.

The modified data path is illustrated in Fig. 3. We have implemented this data path as a modified macvlan device, called NAPI-macvlan. It is different from a macvlan device in the sense that it uses NAPI (netif_receive_skb) instead of Softnet API so that packets are delivered directly to the next processing module without being stored in an intermediate queue.

Performance Evaluation

This section presents a performance evaluation of macvlan and NAPI-macvlan based virtual router platforms from different performance perspectives, considering throughput, scalability, isolation and latency. In all test cases, we use Linux namespaces as the foundation for virtualization. We relate the performance of a virtual router to regular IP forwarding in a non-virtualized Linux based router. Throughout this section, the latter is denoted -IP Forwarder‖, and we use it as a reference to study the effects of applying virtualization.

Experimental Setup

We adopt a standard method to examine router performance in conformance with RFC 2544 [START_REF]RFC 2544 -Benchmarking methodology for interconnecting devices‖[END_REF]. A source machine generates network traffic that passes through a device under test (DUT), which forwards towards the destination machine. The nodes are connected using 1 Gb/s links.

We use an AMD Phenom quad core 3.2 GHz machine as traffic generator (GEN). The machine is equipped with 4GB of memory and two Gigabit Ethernet Intel® PRO/1000 PT server adapters (controller chip 82571GB). Another machine with the same specifications is used as destination (SINK). We use an Intel dual core 2.6 GHz machine (E8200) as the DUT. The machine has 4GB memory and a quad port Gigabit Ethernet Intel PRO/1000 PT server adapter. The DUT is running Linux kernel version 2.6.33-Netnext. All network interfaces are running NAPI-aware network drivers. Interrupt throttling is turned off for all interfaces. We use pktgen [START_REF]Olsson -pktgen the Linux packet Generator‖[END_REF], an open source tool for traffic generation and throughput computation at sink. For all tests, 64 byte packets are generated. The DUT is running a single CPU, unless something else is specified.

Throughput

Case I

We start with a simple scenario: a DUT with two physical interfaces, forwards packets from one interface to another (unidirectional traffic flow). The results are show in Fig. 4. With this scenario, non-virtualized IP forwarding reaches a maximum throughput of 785 kpps. This provides the baseline forwarding performance as a reference for the other measurements. Fig. 4 also shows the throughput for virtual routers with two virtual interfaces, using macvlan devices as well as NAPI-macvlan. One virtual interface is connected to the ingress physical interface while the other virtual interface is connected to the egress physical interface. Fig. 4 shows that the macvlan-based virtual router attains up to 690 kpps while the the NAPI-macvlanbased virtual router achieves around 700 kpps.

Fig. 4. Load vs throughput (Case I)

Case II For the next step we add a physical interface to the setup. We offer load on two interfaces and use the third as egress interface. A single CPU core is thus processing traffic belonging to three physical interfaces. For this scenario, we consider aggregate offered load on the system (on both physical interfaces). The results are shown in Fig. 5 (three interfaces). The native IP Forwarder reaches a packet rate of 785 kpps. The macvlan-based virtual router achieves a peak rate of 600 kpps at an offered load of around 600 kpps. Then, as the load increases, the packet rate will drop down to 480 kpps. The NAPI-macvlan-based virtual router peaks at 700 kpps, which is sustained as the offered load increases-a significant performance difference under overload.

To understand the throughput difference between macvlan and NAPI-macvlan, we study packet drop locations along the data path. In case of macvlan (Fig. 2), we find that packets are dropped at two locations: in the backlog queue after the incoming macvlan device (after -Macvlan A‖ in Fig. 2) and on the ingress physical interface. When the load is increased beyond 600 kpps, packet drop starts in the backlog queue. Increasing offered load results in more packet drop and throughput degradation, but packets are still accepted by the ingress interfaces. This situation remains until the aggregated load on the ingress interfaces reaches 1000 kpps. Above this load level, the ingress physical interface starts dropping packets, and from that point a throughput of 480 kpps is maintained for increasing load, as shown in Fig. 5. This type of behavior has been explained in detail for veth/bridge-based virtual routers [START_REF] Rathore | Performance Evaluation of Open Virtual Routers[END_REF]. In case of NAPI-macvlan, the only packet drop location is on the ingress physical interface. When the load is increased above 700 kpps (Fig. 5), the ingress interfaces start dropping packets, and a throughput of 700 kpps is sustained for higher loads. Clearly, this more graceful overload behavior is much more preferable.

Fig. 5. Load vs throughput (II, III)

An interesting conclusion that can be made from this test case is that the cost of dropping packets in software is significant compared to dropping packets directly on the ingress interfaces. In Case II, we explain the gradual throughput degradation of macvlan virtualization for loads between 600 and 1000 kpps by the fact that packets are still accepted by the ingress interfaces and accordingly the CPU has to spend cycles both on packets that get dropped and on packets that get forwarded. Spending CPU cycles on packets that eventually will be dropped is clearly a waste of resources, adding overhead and reducing performance. This behavior cannot be seen for NAPImacvlan virtualization since the only drop location is on the physical interface. Once a packet has been accepted by the macvlan device from the physical interface, the packet will be processed throughout the entire data path and delivered to the egress interface.

Case III

In this test case, we add yet another physical interface to the DUT and spread the offered load over three ingress interfaces while having a single egress interface. In this case, throughput for macvlan degrades even further. The backlog queue is now shared by even more ingress interfaces, something which increases the drop rate at the CPU level. The performance of NAPI-macvlan, on the other hand, is not affected by adding yet another physical ingress interface.

Scalability

Our first scalability study is to analyze the impact of running multiple virtual routers on the same physical platform. Therefore, we extend the experimental setup of case III with an increasing number of virtual routers. We create up to 32 virtual routers, each with four virtual interfaces (three ingress and one egress). Each ingress physical interface is now shared by up to 32 ingress virtual interfaces. A pktgen script is used to send 10 million packets in a row through one virtual router at a time. We do not observe any noticeable throughput degradation in the DUT when adding virtual routers. It can be seen in Fig. 6 that the maximum throughput for the DUT remains almost constant irrespectively of the number of existing virtual routers (1 to 32). This behavior is the same both for macvlan and NAPI-macvlan. The tests indicate a promising scalability property of Linux namespaces. Another important scalability concern is to study the impact of IP route lookup on forwarding performance. Until now we consider a unidirectional virtual router with a single routing table entry-a valid test setup but not a practical scenario. We move towards a more realistic scenario by considering bidirectional traffic flows together with a larger routing table.

We extend the setup of case I and update the virtual router with 512 routing table entries. We offer load on both physical interfaces, which is forwarded towards each other through the virtual router (i.e. bidirectional). As a first step, we offer load with the same IP destination in all packets. In this case, routing information is available in routing cache and there is no need to consult routing table. The results are shown in Fig. 7 (single destination, 2 virtual interfaces). The NAPImacvlan router achieves 700 kkpps and macvlan router reaches 660 kpps. A minor drop rate in the backlog queue can be observed for macvlan. As the next step, we offer load with 512 different IP destinations to see the impact of having the CPU make a route lookup with misses in the route cache. Fig. 7 (multiple destinations, 2 virtual interfaces) shows a minor throughput degradation for NAPI-macvlan (680 kpps). However, for macvlan packet drops in the backlog queue are now becoming substantial. As a result, throughput drops to 500 kpps. In the above scenario, the virtual router has only two virtual interfaces so there are only two entries for virtual/physical device mapping. All packets arrive on one interface and are transmitted on the other. Such a setup will not allow studies of the impact of virtual/physical device mapping, something which is important from scalability perspective. Furthermore, a virtual router with two virtual interfaces may not always be useful. We increase the number of virtual interfaces in the setup. For each physical interface, 256 virtual interfaces are created (512 in total). The bidirectional load is offered with 512 different IP destinations so that different egress virtual interfaces will be used for different destinations. We investigate the impact of device mapping. The results are shown in Fig. 7 (512 virtual interfaces). It shows a small throughput degradation for NAPI-macvlan (670 kpps), compared to the earlier peak rate of 700 kpps. For macvlan, throughput degrades to 300 kpps as a result of more severe backlog congestion. We observe that when the computational burden increases on the CPU, the backlog congestion becomes more adverse. 8, gives a more detailed picture of throughput versus the number of virtual interfaces. The number of IP destinations in the traffic flow is increased along with the number of virtual interfaces. The impact is minor for the NAPI-macvlan based router. However, throughput drops sharply for the macvlan case.

Isolation

In the previous subsection we verified that an increasing number of passive virtual routers had almost no effect on the overall throughput performance for neither macvlan nor NAPI-macvlan (Fig. 6). However, it is also important to investigate how multiple active virtual routers, running on the same CPU, might affect each other's operation. We refer to this as isolation properties. In this subsection, we study these isolation properties through an experiment where we analyze how a high offered load on one virtual router might influence the operation of another virtual router sharing the same CPU. The setup has two virtual routers, each one with a dedicated pair of physical interfaces and unidirectional traffic flow. As a first step, we offer a load of 300 kpps on the ingress physical interfaces of both virtual routers at the same. We observe an aggregate throughput of 600 kpps. It shows that both virtual routers are working independently without affecting each other. The result is the same for both macvlan and NAPI-macvlan virtual routers. Thereafter, we increase the offered load to 1000 kpps on the ingress physical interface of VR1 while still offering 300 kpps on the ingress interface of VR2. For this scenario, the throughput results are presented in Table 1

NAPI-Macvlan

We can note that the overall throughput for NAPI-macvlan is higher than for macvlan virtualization (650 kpps vs 535 kpps). Moreover, the overload on VR1 in the macvlan case results in serious performance degradation in VR2. In the NAPImacvlan, on the other hand, no such effects can be seen.

The explanation to this difference in isolation can again be described by the backlog queue that is present in macvlan virtualization. Since the backlog queue is on a per CPU basis, it is shared between the two virtual machines. So, even though we have isolation at the physical interface level, this isolation cannot be preserved between VR1 and VR2 because of the shared backlog queue. For NAPI-macvlan, VR1 and VR2 do not have any drop location in common. Therefore, packet drops occur only on the physical interfaces and the isolation properties can be preserved.

Latency

Latency is an important parameter for many network applications. Pktgen provides a utility to compute packet latency. It records packet transmission time at the traffic generator and then packet reception time at the sink. The difference provides the packet latency. We use the case I setup for latency measurements. The test is conducted for a fixed amount of time (120 sec). A load of 600 kpps is offered and we make sure that all packets are received at the sink (i.e., no packet drop occurs here). Fig. 9 displays the average latency for each configuration. It can be seen that the IP forwarder and NAPI-macvlan virtualization have the same latency. However, the average latency is doubled for macvlan virtualization.

Fig. 9. Latency measurements for virtual setups

The reason for the higher average delay for the macvlan setup is that the macvlan uses the earlier mentioned Softnet API, incurring an overall processing delay. In case of both original IP forwarding and NAPI-macvlan, a packet is forwarded within a single SoftIRQ. This reduces the packet processing delay and results in a lower average latency.

Conclusion and Future Work

We have evaluated performance of virtual router platforms based on Linux Namespaces. The virtual routers were using the macvlan device (virtual interfaces) which is the part of the main stream Linux kernel 2.6. We analyzed the router's data plane and pointed out that backlog queuing can form a severe performance bottleneck. We proposed an alternative data plane by eliminating the backlog queue. To achieve this, we modified the macvlan device and introduced a variant denoted "NAPImacvlan". We compared the performance of macvlan and NAPI-macvlan based virtual routers. We achieved better forwarding rates using NAPI-macvlan, particularly in different kinds of overload situations. Furthermore, in contrast to macvlan, NAPImacvlan based routers proved superior when it comes to preserving isolation properties. It was also demonstrated that NAPI-macvlan based virtual routers improve the scaling properties. Finally, a considerable improvement in latency was also observed while using NAPI-macvlan. In our future work, we plan to evaluate NAPImacvlan based routers using multiple CPU cores and multi-queue NICs.

Fig. 6 .

 6 Fig. 6. Throughput vs. no. of virtual routers

Fig. 7 .

 7 Fig. 7. Throughput for 2, 512 VIFs.

Fig. 8 .

 8 Fig. 8. Throughput vs VIFs.

Fig.

  Fig.8, gives a more detailed picture of throughput versus the number of virtual interfaces. The number of IP destinations in the traffic flow is increased along with the number of virtual interfaces. The impact is minor for the NAPI-macvlan based router. However, throughput drops sharply for the macvlan case.

Table 1 .

 1 . Isolation between virtual routers.

	Setup		Packet rate (kpps)
		Offered load		Throughput
		VR1 VR2 Total	VR1 VR2 Total
	Macvlan	1000 300 1300	480 55	535
		1000 300 1300	350 300 650

Acknowledgments. We would like to thank Robert Olsson from TSLab KTH and Jens Laas from Uppsala University, for their valuable input during the work.


Vijay Mann
email: vijamann@in.ibm.com

Avinash Kumar
email: avinash.ee@student.iitd.ac.in

Partha Dutta
email: parthdut@in.ibm.com

Shivkumar Kalyanaraman
email: shivkumar-k@in.ibm.com

VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers

Keywords: networking aspects in cloud services, energy and power management, green networking, VM placement Core Switch Core Switch Core Switch Core Switch TOR

Networking costs play an important role in the overall costs of a modern data center. Network power, for example, has been estimated at 10-20% of the overall data center power consumption. Traditional power saving techniques in data centers focus on server power reduction through Virtual Machine (VM) migration and server consolidation, without taking into account the network topology and the current network traffic. On the other hand, recent techniques to save network power have not yet utilized the various degrees of freedom that current and future data centers will soon provide. These include VM migration capabilities across the entire data center network, on demand routing through programmable control planes, and high bisection bandwidth networks. This paper presents VMFlow: a framework for placement and migration of VMs that takes into account both the network topology as well as network traffic demands, to meet the objective of network power reduction while satisfying as many network demands as possible. We present network power aware VM placement and demand routing as an optimization problem. We show that the problem is NP-complete, and present a fast heuristic for the same. Next, we present the design of a simulator that implements this heuristic and simulates its executions over a data center network with a CLOS topology. Our simulation results using real data center traces demonstrate that, by applying an intelligent VM placement heuristic, VMFlow can achieve 15-20% additional savings in network power while satisfying 5-6 times more network demands as compared to recently proposed techniques for saving network power.

Introduction

In current data centers, networking costs contribute significantly to the overall expenditure. These include capital expenditure (CAPEX) costs such as cost of networking equipment which has been estimated at 15% of total costs in a data center [START_REF] Greenberg | The Cost of a Cloud: Research Problems in Data Center Networks[END_REF]. Other networking costs include operational expenditure (OPEX) such as power consumption by networking equipment. It has been estimated that network power comprise of 10-20% of the overall data center power consumption [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF]. For example, network power was 3 billion kWh in the US alone in 2006.

Traditionally, data center networks have comprised of single rooted tree network topologies which are ill-suited for large data centers, as the core of the network becomes highly oversubscribed leading to contention [START_REF] Greenberg | VL2: A Scalable and Flexible Data Center Network[END_REF]. To overcome some of these performance problems of traditional data center networks, such as poor bisection bandwidth and poor performance isolation, recent research in data center networks has proposed new network architectures such as VL2 [START_REF] Greenberg | VL2: A Scalable and Flexible Data Center Network[END_REF], Portland [START_REF] Mysore | PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric[END_REF], and BCube [START_REF] Guo | BCube: A High Performance, Server-centric Network Architecture for Modular Data Centers[END_REF]. Data centers are also increasingly adopting virtualization and comprise of physical machines with multiple Virtual Machines (VMs) provisioned on each physical machine. These VMs can be migrated at downtime or at runtime (live). Furthermore, emergence of programmable control plane in switches through standardized interfaces such as Openflow [START_REF]The OpenFlow Switch[END_REF], has enabled on demand changes in routing paths.

With the above recent advances, opportunities have emerged to save both network CAPEX and OPEX. Network CAPEX is being reduced through several measures such as increased utilization of networking devices, and a move towards cheaper and faster data plane implemented in merchant silicon, while all the intelligence lies in a separate sophisticated control plane [START_REF]The OpenFlow Switch[END_REF]. Components of OPEX, such as network power costs, are being reduced through techniques that switch off unutilized network devices as the data center architectures move to higher levels of redundancy in order to achieve higher bisection bandwidth. However, most of the recent techniques to save network power usage do not seem to utilize all the features that current and future data center will soon provide. For instance, recent techniques to save network power in [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF] exploit the time-varying property of network traffic and increased redundancy levels in modern network architectures, but do not consider VM migration. On the other hand, current VM placement and migration techniques such as [START_REF] Verma | pMapper: Power and migration cost aware application placement in virtualized systems[END_REF] mainly target server power reduction through server consolidation but do not take into account network topology and current network traffic. A recent work by Meng et. al [START_REF] Meng | Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement[END_REF] explored network traffic aware VM placement for various network architectures. However, their work did not focus on network power reduction.

There are multiple reasons why saving network power is increasingly becoming more important in modern data centers [START_REF] Mahadevan | Energy proportionality of an enterprise network[END_REF]. Larger data centers and new networking technologies will require more network switches, as well as switches with higher capacities, which in turn will consume more power. In addition, rapid advances in server consolidation are improving server power savings, and hence, network power is becoming a significant fraction of the total data center power. Also, server consolidation results in more idle servers and networking devices, providing more opportunity for turning off these devices. Finally, turning off switches results in less heat, thereby reducing the cooling costs.

In this context, this paper presents VMFlow: a framework for placement and migration of VMs that takes into account both the network topology as well as network traffic demands, to meet the objective of network power reduction while satisfying as many network demands as possible. We make the following contributions:

1. We formulate the VM placement and routing of traffic demands for reducing network power as an optimization problem. 2. We show that a decision version of the problem is NP-complete, and present a fast heuristic for the same. 3. We present the design of a simulator that implements this heuristic and simulates its runs over a data center network with a CLOS topology. 4. We validate our heuristic and compare it to other known techniques through extensive simulation. Our simulation uses real data center traces and the results demonstrate that, by applying an intelligent VM placement heuristic, VMFlow can achieve 15-20% additional savings in network power while satisfying 5-6 times more network demands as compared to recently proposed techniques for saving network power. 5. We extend our technique to handle server consolidation.

The rest of this paper is organized as follows. We give an overview of related research in Section 2. Section 3 presents the technical problem formulation. Section 4 describes our greedy heuristic. We describe the design and implementation of our simulation framework and demonstrate the efficacy of our approach through simulation experiments in Section 5. Section 6 extends our technique to handle server consolidation. Finally, we conclude the paper in Section 7.

Background and Related Work

Data center network architectures. Conventional data centers are typically organized in a multi-tiered network hierarchy [START_REF]Cisco: Data center: Load balancing data center services[END_REF]. Servers are organized in racks, where each rack has a Top-of-Rack (ToR) switch. ToRs connect to one (or two, for redundancy) aggregation switches. Aggregation switches connect to a few core switches in the top-tier. Such a hierarchical design faces multiple problems in scaling-up with number of servers, e..g, the network links in higher tiers become progressively over-subscribed with increasing number of servers. Recently, some new data center network architectures have been proposed to address these issues [START_REF] Greenberg | VL2: A Scalable and Flexible Data Center Network[END_REF][START_REF] Guo | BCube: A High Performance, Server-centric Network Architecture for Modular Data Centers[END_REF][START_REF] Mysore | PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric[END_REF].

VL2 [START_REF] Greenberg | VL2: A Scalable and Flexible Data Center Network[END_REF] is one such recently proposed data center network architecture (Figure 1), where the aggregation and the core switches are connected using a CLOS topology, i.e., the links between the two tiers form a complete bipartite graph. Network traffic flows are load balanced across the aggregation and core tier using Valiant Load Balancing (VLB), where the aggregation switch randomly chooses a core switch to route a given flow. VL2 architecture provides higher bisection bandwidth and more redundancy in the data center network.

Traffic-aware VM placement. VM placement has been extensively studied for resource provisioning of servers in a data center, including reducing server power usage [START_REF] Verma | pMapper: Power and migration cost aware application placement in virtualized systems[END_REF]. Some recent papers have studied VM placement for optimizing network traffic in data centers [START_REF] Korupolu | Coupled placement in modern data centers[END_REF][START_REF] Meng | Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement[END_REF]. These approaches differ from VMFlow in two important ways: (a) the techniques do not optimize for network power, and (b) their solutions do not specify the routing paths for the network demands. Network power optimization. Most of the recent research on data center energy efficiency has focused on reducing the two major components of data center power usage: servers and cooling [START_REF] Greenberg | The Cost of a Cloud: Research Problems in Data Center Networks[END_REF][START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF]. Recently, some papers have focussed on reducing the power consumed by networking elements (which we call, network power) in a data center [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF][START_REF] Mahadevan | Energy proportionality of an enterprise network[END_REF][START_REF] Shang | Energy-aware routing in data center network[END_REF]. In the ElasticTree approach presented in [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF], a network power manager dynamically turns on or off the network elements (switches and links), and routes the flows over the active network elements, based on the current network traffic demands. In the primary technique presented in Elas-ticTree, called greedy bin-packing, every demand is considered sequentially, and the demand is routed using the leftmost path that has sufficient capacity to route the demand. Here, a path is considered to be on the left of another path if, at each switch layer of a structured data center topology, the switch on the first path is either to the left or is identical to the switch on the second path. ElasticTree also proposes an topology-aware approach that improves upon the computation time as compared to greedy bin packing -however, it does not improve the network power in the solution. The VMFlow framework that we present in this paper fundamentally differs from ElasticTree [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF] and from the work in [START_REF] Mahadevan | Energy proportionality of an enterprise network[END_REF][START_REF] Shang | Energy-aware routing in data center network[END_REF] because we exploit the flexibility of VM placements that is available in the modern data centers. Also, for a given demand, we jointly perform the VM placement and flow routing by greedily selecting the VM placements as well as the routing paths that require minimum additional network power.

Network-Aware VM Placement Problem

In this section we present the Network-Aware Virtual Machine Placement (NAVP) Problem. Our problem formulation extends the ElasticTree formulation in [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF].

Input. The data center network is composed of network switches and links that connect the hosts (physical servers). The data center network topology is modeled using a weighted directed graph G = (V, E), where V are the set of vertices and the E ⊆ V × V is the set of directed edges. A link e = (u, v) has capacity (maximum supported rate) of C(e). There are three types of vertices in V : the switches, the hosts, and a special vertex v E . Vertex v E models the external clients that communicate with the data center. The edges represent the communication links between the switches, and between the switches and the hosts. (We use edges and links interchangeably in this paper.) Let there be n hosts H = {h 1 , . . . , h n }, and q switches W = {w 1 , . . . , w q }.

We consider a set of m Virtual Machines (VMs) M = {vm 1 , . . . , vm m }, where m ≤ n, and at most one VM can be placed on a host (we consider the case of multiple VMs per server in Section 6). The network traffic source or destination is one of the m VMs or an external client. We model the traffic to and from any external clients as traffic to and from v E , respectively. Let M be M ∪ {v E }. We are given a set of K demands (rates) among the nodes in M , where the j th demand requires a rate of r j from source s j ∈ M to destination d j ∈ M , and is denoted by (s j , d j , r j ).

When a switch w i or a link e is powered on, let P (w i ) and P (e) denote the power required to operate them, respectively. A VM placement is a (one-toone) mapping Π : M → H that specifies that the mapping of VM vm i to host h Π(vmi) . In addition, we assume that in all VM placements, v E is mapped to itself.

Constraints. We model the VM placement problem as a variant of the multicommodity flow problem [START_REF] Ahuja | Network Flows -Theory, Algorithms and Applications[END_REF]. A flow assignment specifies the amount of traffic flow on every edge for every source-destination demand. We say that a flow assignment on G satisfies a set of demands if the following three standard constraints holds for the flow assignment: edge capacity, flow conservation and demand satisfaction. (Please see [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF] for the detailed constraints.)

In addition, we consider another set of constraints that result from the power requirements: (1) a link can be assigned a non-zero flow only if it is powered on, and (2) a link can be powered on only if the switches that are the link's end nodes are powered on. Thus, the total (network) power required by a flow assignment is the sum of the power required for powering on all links with non-zero flow assignment, and the power required for powering on all switches that are end nodes of some link that has a non-zero flow assignment.

Due to adverse effect of packet reordering on TCP throughput, it is undesirable to split a traffic flow of a source-destination demand [START_REF] Kandula | Dynamic load balancing without packet reordering[END_REF]. Therefore, the NAVP problem requires that a demand must be satisfied using a network flow that uses only one path in the network graph (unsplittable flow constraint).

The optimization problem. Given the above-mentioned K demands among the nodes in M , we say that a given VM placement Π is feasible if there is a flow assignment on G that satisfies the following K demands among the hosts: the j th demands requires a rate of r j from source host Π(s j ) to destination host Π(d j ). Then the Network-Aware VM Placement (NAVP) problem is stated as follows: among all possible feasible VM placements, find a placement and an associated flow assignment that has the minimum total power.

Problem Complexity:

The following decision version of the NAVP problem is NP-complete: given a constant B, does there exist a feasible VM placement and an associated flow assignment that has total power less than or equal to B. We show the NP-completeness by reduction from the bin packing problem [START_REF] Vazirani | Approximation Algorithms[END_REF].

Theorem 1. The decision version of the Network-Aware VM Placement (NAVP) problem is NP-complete.

Please see [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF] for the proof.

Heuristic Design

We now present a greedy heuristic for the NAVP problem. The algorithm considers the demands one by one, and for each demand, the algorithm greedily chooses a VM placement and a flow assignment (on a path) that needs minimum increase in the total power of the network. We now describe the algorithm in more details. (The pseudocode is presented in Figure 2.) Primary variables. The algorithm maintains four primary variables: W on and E on which are the set of switches and edges that have been already powered on, respectively, the set H f ree of hosts that have not yet been occupied by a VM, and a function RC that gives the residual or free capacity of the edges. For each VM v, we assume that initially the placement Π(v) is set to ⊥.

In each iteration of the main loop (in function VMFlow), the algorithm selects a demand in the descending order of the demand rates, and tries to find a feasible VM placement. If a feasible VM placement is found, then the primary variables are updated accordingly; otherwise, the demand is skipped.

Residual graph. To find a feasible VM placement for a demand (s j , d j , r j ), the algorithm construct a residual graph G res . The residual graph contains all switches, and all hosts where VMs s j and d j can be possibly placed (sets Φ(s j ) and Φ(d j ), respectively). G res also contains every edge among these nodes that have at least r j residual capacity. Therefore, in G res , any path between two hosts has enough capacity to route the demand.

The algorithm next focuses on finding VM placements for s j and d j such that there is path between the VMs that requires minimum additional power. To that end, the nodes and edges in the residual graph are assigned weights equal to the amount of additional power required to power them on. Thus, the weight of a switch v is set to 0 if it already powered on, and set to P (v), otherwise. Edges are assigned weights in a similar manner. However, the weights of the hosts are set to ∞ so that they cannot be used as an intermediate node in a routing path. Next, the weight of a path in the residual graph (pathW t) is defined as the sum of the weights of all intermediate edges and nodes on the path (and excludes the weights of the end nodes of the path).

VM placement. In the residual graph G res , the algorithm considers all possible pairs of hosts for placing s j and d j (where the first element in the pair is from Φ(s j ) and the second element is from Φ(d j )). Among all such pairs of hosts, the algorithm selects a pair of hosts that has a minimum weight path. (A minimum weight path between the hosts is found using a variant of Dijkstra's shortest path algorithm whose description is omitted here due to lack of space.) The source and the destination VMs for the demand (s j and d j ) are placed at the selected hosts, and the flow assignment is done along a minimum weight path. Note that, sometimes G res may be disconnected and each hosts may lie in a distinct component of G res . (For instance, this scenario can occur when the residual edge capacities are such that no path can carry a flow of rate r j .) In this case, there is no path between any pair of hosts, and the algorithm is unable to find a feasible VM placement for this demand. Depending on the data center's service level objectives, the algorithm can either abort the placement algorithm, or continue by considering subsequent demands. {current residual capacity of edge e} 6: function VMFlow 7: select a demand (sj , dj , rj ) from the set of demands in the descending order of their rates 8:

if Π(sj ) = ⊥ then Φ(sj ) ← H f ree else Φ(sj ) ← {Π(sj )} 9: if Π(dj ) = ⊥ then Φ(dj ) ← H f ree else Φ(dj ) ← {Π(dj )} 10: Vres ← W ∪ Φ(sj ) ∪ Φ(dj )
{residual nodes} 11:

Eres ← {(u, v) ∈ E : (RC(e) ≥ rj ) ∧ (u, v ∈ Vres)} {residual edges} 12: Gres ← (Vres, Eres) {residual graph} 13: ∀v ∈ W , if v ∈ Won then W Tres(v) ← 0 else W Tres(v) ← P (v) {switch wt. in Gres} 14: ∀v ∈ Φ(sj ) ∪ Φ(dj ), W Tres(v) ← ∞ {host wt. in Gres} 15:
∀e ∈ Eres, if e ∈ Eon then W Tres(e) ← 0 else W Tres(e) ← P (e) {edge wt. in Gres} 16:

minW t ← M in{pathW t(Gres , u, v) : (u ∈ Φ(sj )) ∧ (v ∈ Φ(dj )) ∧ (u = v)} {see Sec. 4} 17: if (minW t < ∞) then
{found a routing for this demand} 18:

(Π(sj ), Π(dj )) ← any (u, v) s.t. (u ∈ Φ(sj )) ∧ (v ∈ Φ(dj )) ∧ (u = v) ∧ (pathW t(Gres, u, v) = minW t)

19:

assign the minimum weight path P from Π(sj ) to Π(dj ) to the flow for (sj , dj , rj )

20:

for all switches v on path P , Won ← Won ∪ {v}

21:

for all edges e on path P , Eon ← Eon ∪ {e}; RC(e) ← RC(e)rj

22:

H f ree ← H f ree \ {Π(sj ), Π(dj )}

23:

else 24:

skip demand (sj , dj , rj ) {cannot find a VM placement for this demand} Fig. 2. A greedy algorithm for NAVP It is easy to see that each iteration selects a placement and flow routing that require minimum increase in network power. Thus, although the heuristic is sub-optimal, each iteration selects a locally optimal placement and routing. Lemma 1. In each iteration, for a given traffic demand, the heuristic selects source and destination VM placements and a flow routing that need minimum increase in network power.

A practical simplification. We now present a simple observation to reduce the computation time of our heuristic. We observe that in most conventional and modern Data Center network architectures, multiple host are placed under a Top-of-the-Rack (ToR) switch. Thus, for a given demand, if a source (or destination) VM is placed on a host, then the parent ToR of the host needs to be turned on (if the ToR is not already on) to route the demand. Therefore, for VM placement, we first try to place both the source and destination VMs under the same ToR. If such a placement is possible, then only the common parent ToR needs to be turned on to route the demand. If no such ToR is available, then we compute a minimum weight path between all possible pairs of ToRs (where path weights include the end ToR weights), instead of computing minimum weight paths between all possible pairs of hosts. This simplification significantly reduces the computation time because the number of ToRs is much lower than the number of hosts.

Experimental Evaluation

We developed a simulator to evaluate the effectiveness of VMFlow algorithm. It simulates a network topology with VMs, switches and links as a discrete event simulation. Each server (also called host) is assumed to host at most one VM (the case of multiple VMs per host is discussed in Section 6). VMs run applications that generate network traffic to other VMs, and VMs can migrate from one node to the other. Switches have predefined power curves -most of the power is static power (i.e. power used to turn on the switch). At each time step, network traffic generated by VMs (denoted by an entry in the input traffic matrix) is read and the corresponding VMs are mapped to hosts as per the algorithm described in Section 4. The corresponding route between the hosts is also calculated based on the consumed network power, the network topology and available link capacities. At each time step of the simulation, we compute the total power consumed by the switches and the fraction of the total number of network demands that can be satisfied. A new input traffic matrix (described below), that represents the network traffic at that time stamp, is used at each time step of the simulation.

Network Topology: The simulator creates a network based on the given topology. Our network topology consisted of 3 layers of switches: the top-of-the-rack (ToR) switches which connect to a layer of aggregate switches which in turn connect to the core switches. Each ToR has 20 servers connected to it. At most one virtual machine (VM) can be mapped to a server (the case of multiple VMs per server is discussed in Section 6). We assume a total of 1000 servers (and VMs). There are 50 ToR switches, and each server connects to a ToR over a 1 Gbps link. Each ToR connects to two aggregate switches over 1 or 10 Gbps links. We assume a CLOS topology between the aggregate and core switches similar to VL2 [START_REF] Greenberg | VL2: A Scalable and Flexible Data Center Network[END_REF] with 1 or 10 Gbps links as shown in Figure 1. All switches are assumed to have a static power of 100 watts. This is because current networking devices are not energy proportional and even completely idle switches (0% utilization) consume 70-80% of their fully loaded power (100% utilization) [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF].

Our simulator has a topology generator component that generates the required links between servers and ToRs, ToRs and aggregate switches, and aggregate switches and core switches. It takes in as input the number of servers and the static power values for each kind of switch. It then generates the number of ToR switches (assuming 20 servers under 1 ToR) and the number of aggregate and core switches using the formulae given in [START_REF] Greenberg | VL2: A Scalable and Flexible Data Center Network[END_REF] for a CLOS topology.

For (d*d)/4 ToRs, the number of aggregate switches are d and the number of core switches are d/2. For 1000 servers and 50 ToRs, this results in around 15 aggregate switches and around 8 core switches.

Input Data: To drive the simulator, we needed a traffic matrix (i.e. which VM sends how much data to which VM). Such fine grained data is typically hard to obtain from real data centers [START_REF] Benson | Understanding Data Center Traffic Characteristics[END_REF][START_REF] Kandula | The Nature of Data Center Traffic: Measurements and Analysis[END_REF] because of the required server level instrumentation. We obtained data from a real data center with 17,000 VMs with aggregate incoming and outgoing network traffic from each VM. The data had snapshots of aggregate network traffic over 15 minute intervals spread over a duration of 5 days. To understand the variance in the data, we compared the discrete time differential (∆) with the standard deviation (σ) of the data. Data that satisfied the following condition was considered constant: -σ/2 ≤ ∆ ≤ +σ/2. A histogram of percentage of data that was constant for all VMs is given in Figure 3. It can be observed that most of the VMs have a very large percentage of data that is constant and does not show much variance. A very large variance can be bad for VMFlow, as it will mean too frequent VM migrations, whereas a low variance means that migration frequency can be kept low.

Our first task was to calculate a traffic matrix out of this aggregate per VM data. Given the huge data size, we chose data for a single day. Various methods have been proposed in literature for calculating traffic matrices. We used the simple gravity model [START_REF] Zhang | Fast accurate computation of large-scale IP traffic matrices from link loads[END_REF] to calculate the traffic matrices for all 17,000 VMs at each time stamp on the given day. Simple gravity model uses the following equation to calculate the network traffic from one VM to another:

D ij = (D out i * D in j )/(Σ k D in k ).
Here D out i is the total outgoing traffic at VM i, and D in j is the total incoming traffic at VM j. Although, existing literature [START_REF] Kandula | The Nature of Data Center Traffic: Measurements and Analysis[END_REF] points out that traffic matrices generated by simple gravity model tend to be too dense and those generated by sparsity maximization algorithms tend to be too sparse than real data center traffic matrices, simple gravity model is still widely used in literature to generate traffic matrices for data centers [START_REF] Meng | Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement[END_REF].

After generating the traffic matrices for each time stamp for the entire data center (17,000 VMs), we used the traffic matrices for the first 1000 VMs in order to reduce the simulation time required. Since gravity model tends to distribute all the traffic data observed over all the VMs in some proportion, it resulted in a large number of very low network demands. In order to make these demands significant, we used a scale-up factor of 50 for all the data (i.e. each entry in all the input traffic matrices was multiplied by 50).

Simulation Results: The simulator compares VMFlow approach with the Elas-ticTree's greedy bin-packing approach proposed by Heller et. al [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF] to save network power. Recall that the ElasticTree's bin-packing approach chooses the leftmost path in a given layer that satisfies the network demand out of all the possible paths in a deterministic left-to-right order. These paths are then used to calculate the total network power at that time instance. For placing VMs for the ElasticTree approach, we followed a strategy that placed the VMs on nodes that had the same id as their VM id.

We assume that all the network power comprise of power for turning on the switches, and the power required for turning on each network link (i.e., for ports on the end switches of the link) is zero. We calculated the total power consumed by the network and the proportion of network demands that were unsatisfied at a given time stamp for both VMFlow and ElasticTree approaches. In the first set of experiments, we simulated an oversubscribed network where the ToR-aggregate switch links and aggregate-core switch links had 1 Gbps capacity. This resulted in a 10:1 over subscription ratio in the ToR-aggregate switch link layer. The results for the oversubscribed network are shown in Figure 4(a) and Figure 4(b), respectively.

VMFlow outperforms the ElasticTree approach by a factor of around 15% and the baseline (i.e., all switches on) by around 20% in terms of network power at any given time instance. More importantly, one can see the effectiveness of VMFlow in the percentage of network demands that remain unsatisfied. VMFlow saves all the network power while satisfying 5-6 times more network demands as compared to ElasticTree approach. Since the input data had very little variation over time, we conducted an experiment to compare VMFlow with and without any migration after the first placement was done using the VMFlow algorithm. In order to simulate no migration, VMFlow simulator calculated an optimal placement of VMs based on the first input traffic matrix (representing the traffic for the first time stamp) and only calculated the route at each subsequent time step. Figure 4(a) and Figure 4(b) show the performance of VMFlow approach without any migration. One can note that even with low variance input data, VMFlow with migration outperforms VMFlow without migration slightly by a margin of 5% in terms of power. Both the approaches perform roughly the same with respect to percentage of unsatisfied network demands. This indicates that migration frequency has to be properly tuned keeping in mind the variance in network traffic. Each VM migration has a cost associated with it that depends on the size of VM, its current load, the nature of its workload and the Service Level Agreement (SLA) associated with it. We are currently working on a placement framework that will take into account this cost and the potential benefit a migration can achieve in terms of network power and network demand satisfaction. We also compared the effect of using various scale-up factors on the input network traffic data. In this set of experiments we used a single input traffic matrix (representing the traffic at the first time stamp) and simulated both an oversubscribed network (ToR-aggregate and aggregate-core switch links have 1 Gbps capacity) and a network with no over subscription(ToR-aggregate and aggregate-core switch links have 10 Gbps capacity). The results are shown in Figure 5(a) and Figure 5(b). VMFlow outperforms the ElasticTree approach consistently, both in terms of network power reduction as well as percentage unsatisfied demands in the oversubscribed network (1G). However, in the no over subscription case (10G) the performance difference between VMFlow and Elas-ticTree is relatively lower. This is along expected lines, since VMFlow is expected to outperform mainly in cases where the top network layers are oversubscribed.

Handling Server Consolidation

In the earlier sections, we have assumed that at most one VM can be mapped to a host; i.e., the VM placement mapping Π is one-to-one. It is, however, easy to modify our algorithm to handle the case when multiple VM are mapped to a host, i.e., in case of server consolidation. In modern data centers, server consolidation is often employed to save both on the capital expenditure (e.g., by consolidating several VMs onto a small number of powerful hosts), and operational expenditure (e..g, any unused host can be turned off to save power) [START_REF] Verma | pMapper: Power and migration cost aware application placement in virtualized systems[END_REF].

Although the basic idea of server consolidation is simple, deciding which VMs are co-located on a host is a complex exercise that depends on various factors such as fault and performance isolations, and application SLA. Thus, a group of VMs co-located during server consolidation may not be migrated to different hosts during network power optimization. Nevertheless, a group of VMs mapped to a single host can be migrated together to a different host, provided the new host has enough resources for that group of VMs. We now describe, how our greedy algorithm can be easily extended to handle server consolidation.

We assume that we have an initial server consolidation phase which maps zero, one or more VMs to each host. A set of VMs that is mapped to the same host during server consolidation is called a VMset. We make the following two assumptions: (1) while placing VMs on the host, the only resource constraint we need to satisfy is on the compute resource, and (2) a group of VMs consolidated on a host are not separated (i.e., migrated to different hosts) during the network power optimization phase. Now, our greedy algorithm requires two simple modifications to handle server consolidation. First, instead of mapping a VM to a host, the algorithm maps a VMset to a host, and the traffic demand between two VMsets is the sum of the demands of individual VMs comprising the two VMsets. Second, in each iteration for placing the source and destination VMset of a traffic demand, the set of possible hosts (Φ(s j ) and Φ(d j )) is defined as the set of free hosts that have equal or more compute resources than the respective VMsets. We omit details of these simple modifications from this paper.

We evaluated the performance of VMFlow in presence of server consolidation using the same simulation framework described in Section 5. Typically server consolidation is done based on the CPU and memory demands of the VMs and the individual host CPU and memory capacities. Since we did not have access to the CPU data for the 1000 VMs that were used in the earlier experiments, we generated synthetic CPU demands that were normally distributed with a given mean and standard deviation. We used the methodology given in [START_REF] Korupolu | Coupled placement in modern data centers[END_REF], to generate mean and standard deviation of the CPU demands. We assumed the servers to be IBM HS22v blades [START_REF]IBM BladeCenter HS22V[END_REF], that go into a Bladecenter H chassis (each chassis can host 14 blades). We simulated an oversubscribed network where the server-TOR links, the ToR-aggregate switch links and aggregate-core switch links had 1 Gbps capacity. We assumed 3 different configurations of HS22v blades and created a VM packing scheme based on CPU demands using first fit decreasing (FFD) bin-packing algorithm. Following 3 configurations of HS22v blades (with increasing CPU capacity) were used in the simulation: The input network traffic matrix was modified such that input and output network demands for VMs that were packed together to create a VMset, were added. VMsets resulting from the VM packing step were then used by the simulator to compare VMFlow and Elastic tree at various network traffic scale factors. Results for network power and percentage unsatisfied demands are shown in Figures 6(a) and 6(b),respectively. VMFlow continues to outperform Elastic tree even in presence of server consolidation. While the network power savings are consistently in the range of 13-20% at higher scale factors, the gains for percentage unsatisfied demands decrease (5x at 1.63 packing ratio, 3x at 3.76 packing ratio, and 2x at 8.39 packing ratio) as more VMs are packed into a single server and network traffic matrix becomes denser.

Future Work

This paper presented VMFlow, a framework for reducing power used by network elements in data centers. VMFlow uses the flexibility provided by VM placement and programmable flow-based routing, that are available in modern data centers, to reduce network power while satisfying a large fraction of the network traffic demands. We formulated the Network-Aware VM Placement as an optimization problem, proved that it is NP-Complete, and proposed a greedy heuristic for the problem. Our technique showed reasonable improvement (15-20%) in network power and significant improvement (5-6 times) in the fraction of satisfied demands as compared to previous network power optimization techniques.

Each VM migration in a data center has a cost associated with it. Similarly, the benefits that can be achieved by a VM migration in terms of network power reduction and meeting more network demands, depends on the variance in network traffic over time. In future, we plan to work on a placement framework that takes into account this cost and the potential benefit a migration can achieve in terms of network power and network demand satisfaction. We also plan to apply our technique to other network topologies and evaluate its benefits.

Fig. 1 .

 1 Fig. 1. CLOS network topology

Fig. 3 .

 3 Fig. 3. Histogram of number of VMs with their percentage constant data

Fig. 4 .

 4 Fig. 4. Comparison at different time steps in the simulation

Fig. 5 .

 5 Fig. 5. Comparison at various scale factors in the simulation

Fig. 6 .

 6 Fig. 6. Comparison at various scale factors and configurations in the server consolidation scenario simulation

1 :

 1 Input: described in input part of Section 3 2: function Initialization 3: Won ← ∅; Eon ← ∅ {set of switches and edges currently powered on} 4: H f ree ← H {set of hosts currently not occupied by a VM} 5: ∀e ∈ E, RC(e) ← C(e)

  1. 1 Intel Xeon E5503 with 2 cores at 2.0 GHz -assuming a mean of 1.6 GHz and std. dev of 0.6, 1000 VMs with normally distributed CPU demands were packed into 612 servers (a packing ratio of 1.63 VMs per server). This required a network with 44 TORs, 14 Aggregate and 7 Core switches. 2. 1 Intel Xeon X5570 with 4 cores at 2.93 GHz -assuming a mean of 2.34 Ghz and std. dev of 0.93, 1000 VMs with normally distributed CPU demands were packed into 265 servers (a packing ratio of 3.76 VMs per server). This required a network with 19 TORs, 9 Aggregate and 5 Core switches. 3. 2 Intel Xeon X5570 with 4 cores at 2.93 GHz -assuming a mean of 2.34 Ghz and std. dev of 0.93, 1000 VMs with normally distributed CPU demands were packed into 119 servers (a packing ratio of 8.39 VMs per server). This required a network with 9 TORs, 6 Aggregate and 3 Core switches.