Hyunyong Lee

Akihiro Nakao
email: nakao@iii.u-tokyo.ac.jp

Efficient User-assisted Content Distribution over Information-centric Network

Keywords: Information-centric networking, user-assisted content distribution, P2P, incentive mechanism Outgoing interface 2. Request packet 5. Content packet 6. Content packet 3. Request packet

To solve the fundamental limitations of current Internet in supporting today's content-oriented services, information-centric networking (ICN) concept has been proposed. ICN has attractive features (e.g., name-based routing, in-network caching and multicast) supporting efficient content-oriented services. However, the attractive features may not be fully utilized by all existing contents due to the resources limitation, which means additional technique may be required for improving content-oriented services. In this paper, as one possible way for this, we examine P2P technique exploiting user resources in ICN. We first examine how P2P looks like in ICN. Then, we introduce the contributionaware ICN and corresponding incentive mechanism to utilize the user resources efficiently. We also show how the contribution-aware ICN can be implemented over the existing ICN architectures. Through simulations, we evaluate an effect of user participation on the content distribution performance in ICN. We also verify the feasibility of the contributionaware ICN in terms of resources utilization efficiency.

Introduction

Current Internet (supporting communications between any pair of machines identified with an IP address) has fundamental limitations in supporting today's content-oriented services (caring about the content itself rather than the IP address of content source). To fundamentally address the mismatch between the current Internet and the today's content-oriented services, ICN [START_REF] Koponen | A data-oriented (and beyond) network architecture[END_REF]- [START_REF]SAIL project[END_REF] has been proposed as one architecture for future Internet. As a revolutionary approach, ICN replaces addressed machines with named contents in the network level and includes some add-on functions of the current Internet (e.g., multicast and caching) as native in-network functions. For example, in ICN, a user just needs to specify a content name that it wants to download. Then, ICN satisfies the user request with data from any source storing a copy of the content, enabling efficient caching as part of the network service.

Even though ICN supporting attractive features is well suited for efficient content-oriented services, all existing contents may not be able to fully utilize the attractive features of ICN. For example, the in-network caching may be only useful for some popular contents due to the limited size of cache. Then, we may need additional approach for improving the content-oriented services in case of contents that cannot fully utilize the attractive features of ICN. As one possible way for this, in this paper, we focus on P2P technique exploiting user resources (i.e., user-assisted content distribution) with proper incentive mechanism. In particular, we argue that 1) P2P technique exploiting user resources will be still useful for content distribution in ICN as the case of current Internet and 2) existing ICN architecture needs to be extended to utilize the user resources efficiently.

To this end, we introduce the contribution-aware ICN (where the contributionrelated information is added to both users and contents) to utilize the user resources efficiently in ICN. A contribution of each user in terms of content distribution is managed by the contribution-aware ICN. In addition, the content is published with a required contribution level that needs to be satisfied by a user who wants to download the content. Therefore, a request of user with enough contribution is only handled so as to encourage the users to contribute their resources. Through simulations, we first show that the user participation has significant impact on the content distribution in ICN, especially when the content cannot fully benefit from the features of ICN (i.e., the in-network caching in our simulation). We also show that the contribution-aware ICN can utilize the user resources efficiently and improve the content distribution performance by using the explicit contribution-related information of users and contents.

This paper is organized as follows. In Section 2, we introduce main features of ICN and discuss its implications on challenging issues of current P2P content distribution. From this, we identify one important research issue in ICN: how to utilize the user resources efficiently. Then, we introduce the contribution-aware ICN in Section 3. We also discuss how the contribution-aware ICN can be implemented over existing ICN architectures. We discuss the incentive mechanism that can be used in the contribution-aware ICN in Section 4. After evaluating the feasibility of the contribution-aware ICN in Section 5, we conclude this paper in Section 6.

Contribution-aware ICN

In this Section, we introduce the contribution-aware ICN architecture to incentivize the user-assisted content distribution in ICN. The user resources will be still useful in ICN, because all existing contents may not be able to fully utilize the attractive features of ICN. For example, the in-network caching is strictly on an opportunistic basis. A cached content can be deleted at any time based on replacement policy such as Least Recently Used (LRU), since the cache size is limited. Due to this reason, only some popular contents can be cached. The native multicast support may be only meaningful for real-time streaming where users are watching same part of content at the same time. Then, the contents that cannot leverage the attractive features of ICN will be provided through a client-server model that is not so efficient in distributing contents unless additional resources (e.g., dedicated servers of CDN and user resources of P2P in the current Internet) are utilized. Therefore, we posit that the user resources can be utilized for improving the content distribution in ICN as P2P utilizes the user resources in the current Internet.

P2P Content Distribution in ICN

Before discussing the contribution-aware ICN trying to utilize the user resources in detail, we first identify one challenging research issue when the P2P technique exploiting the user resources is applied into ICN.

Features of ICN

Even though each existing ICN proposal has different details, there are common features characterizing ICN as follows (Fig. 1)1 :

-Content has an unique identifier decoupled from its location. When a user wants to download a content, the user just needs to issue a content request including the content name instead of its location (e.g., URL of the current Internet). The location-independent content identifier enables efficient caching as the in-network service. -Name-based (anycast) routing forwards the user request specifying the content name to the closest copy of the content with such a name based on the content identifier. In other words, in terms of routing, IP address of the current Internet is substituted by the content name in ICN. -Router supports native in-network caching. The in-network caching may be able to ensure efficient network utilization and improve content availability. -With content-based security [START_REF] Jacobson | Networking named content[END_REF] (i.e., protection and trust travel with the content, e.g., the content includes a digital signature of its publisher) or selfcertifying name [START_REF]PURSUIT project website[END_REF] (i.e., using the cryptographic digest of the content as its name), the user and even the router can examine an integrity of content. This feature is a critical enabler for the in-network caching. From now on, we use the content-based security as the representative term. -Native multicast is supported in a network level. Router manages a list of received content requests for efficient forwarding (i.e., pending interest table (PIT) in [START_REF] Jacobson | Networking named content[END_REF]). When the router receives the requested content, it forwards the content to all requesters, so realizing multicast.

The Benefits of Employing P2P on ICN. Now, we discuss how the P2P looks like over ICN by examining potential implications of ICN features on the challenging issues of current P2P content distribution. User-driven dynamics of user participation, or churn (i.e., user's unexpected join and leave) [START_REF] Stutzbach | Understanding churn in peer-to-peer networks[END_REF] is one of the major obstacles for building stable P2P system, since it degrades P2P system performance by making content source unstable. This problem can be mitigated by the name-based routing and the innetwork caching. ICN router routes the content request to the copy of content as long as the content exists. The cached contents at ICN router may improve the content availability.

Most P2P applications are network-oblivious and thus build an underlying topology-unaware overlay network. Network-oblivious user matching results in extensive inter-domain traffic, causing expensive operational cost to the network operators [START_REF] Karagiannis | Should internet service providers fear peer-assisted content distribution?[END_REF]. Furthermore, to reduce the inter-domain P2P traffic, the network operators often utilize various traffic shaping devices that can degrade P2P networking performance. The issues caused by the network-obliviousness can be solved by the name-based routing that is network-aware.

Open and anonymous nature of P2P (i.e., no control by central authority) attracts large number of users including malicious users [START_REF] Hoffman | A survey of attack and defense techniques for reputation systems[END_REF]. Malicious users interfere with normal content distribution (e.g., by uploading inauthentic file). This problem can be mitigated with the name-based routing and the contentbased security. A user may satisfy as long as the received content is authentic regardless of content source and transfer channel. Since ICN router can check an integrity of content based on the content-based security, the inauthentic file cannot be easily distributed by the malicious users.

Open and anonymous nature also introduces another type of non-honest user, free rider [START_REF] Karakaya | Free riding in peer-to-peer networks[END_REF]. Free riders degrade the content distribution performance by only consuming the resources without contributing any resources. To encourage the users to contribute their resources, incentive mechanisms (e.g., tit-for-tat of BitTorrent [START_REF]BitTorrent[END_REF]) are required. Unlike other challenging issues that can be mitigated by the ICN features, the free riding problem may get worse in ICN if there is no proper incentive mechanism. In the current Internet, each user determines its communication partners based on contribution information of neighboring users. Therefore, the user usually has to upload its content to download a content from other users. On the other hand, in ICN, ICN router matches a content publisher and a content requester based on the name-based routing protocol. In other words, a user can download a content regardless of its contribution by simply specifying the content name. Then, most users may try to exploit the name-based routing while not contributing their resources, which can lead to the tragedy of digital commons. Therefore, in this paper, we propose the contribution-aware ICN to utilize the user resources efficiently in ICN by mitigating the potential free riding problem of P2P over ICN.

Approach

We first discuss main features of the contribution-aware ICN. Then, we will show how the contribution-aware ICN can be implemented over existing ICN architectures. Unlike current P2P applications where each user usually manages contribution information of its neighboring users and determines whom to upload, the user cannot do the same job in ICN, since a matching between a publisher and a requester is done by ICN router. Because the users cannot manage the information of other users, even existence of other users, the management of user information for incentivizing user contribution needs to be done not by the user itself but by a network side. For this purpose, we propose followings (Fig. 2(b) and Fig. 3(b)).

Management of user contribution. We introduce one additional entity, called content distribution manger (CDM) to manage contribution history of users in terms of content distribution. The contribution history can include content name, transfer time, publisher ID, and requester ID. Here, we assume that each user has unique ID. ICN router can generate the contribution history after checking the integrity of transferred content and report it to CDM. CDM generates a contribution level (CL) for each user according to corresponding contribution history when it receives a user request for CL. CL can include target content name, CL value, expiration time, and target user ID. CL shows how much each user contributes to the content distribution. For example, CL can be calculated as a ratio of uploaded content to downloaded content. The content publisher can encourage the user contribution by manipulating CL calculation. For example, CL can be generated based on only publisher ID to foster persistent contribution incentives by recognizing and rewarding contributions made by a user across various contents and time. CDM signs CL with its private key to prevent the users from generating false CL if it needs to return CL to users. The content provider can deploy CDM for their content distribution service. Each CDM has an unique identifier so that the user request for CL can be routed to appropriate CDM based on the name-based routing. Here, we assume that the user can download a metadata file including a name of corresponding CDM through a search engine before requesting the content.

Content publication with required CL. Basic approach for incentivizing user-assisted content distribution is to allow a user to download a content only when the user uploads a content. For this, the content publisher specifies a required contribution level (RCL) that needs to be satisfied by the requester's CL to download the content when it publishes the content.

Contribution-aware routing. ICN router compares the content name and CL of the requester with the name and corresponding RCL of routing in the routing table (e.g., no entry for the requested content, lower CL than RCL, or an expiration time of CL is over), ICN router drops the user request or returns an error to the requester. For this, the routing table of ICN router needs to be extended to include RCL of published content.

Implementation of Contribution-aware ICN

Here, we discuss how the contribution-aware ICN can be implemented over existing ICN architectures. For this purpose, we choose content centric networking (CCN) [START_REF] Jacobson | Networking named content[END_REF] and publish-subscribe internet routing paradigm (PSIRP) [START_REF]PSIRP project website[END_REF] as representative existing ICN architectures. Contribution-aware ICN over CCN. The main concept of CCN is to route a content request towards a location where the content has been published (Fig. 2(a)). Once an instance of content is located, it is delivered to the requester along the path the request came from. All the nodes along that path may cache the content in case they have more requests for it. The contribution-aware ICN can be implemented over CCN as follows (Fig. 2(b)). CDM can be deployed as a separate entity. When the requester wants to download a content, it first acquires its CL from CDM. CDM calculates CL of the requester according to a policy given by a content publisher and returns CL to the requester. Then, the requester issues a content request together with its CL. The content request is routed to a copy of content and the content is delivered to the requester if the requester's CL is higher than RCL of the requested content. When ICN router forwards the content to the requester, it generates the contribution history and reports it to CDM.

Contribution-aware ICN over PSIRP. In PSIRP, content is published into the network (Fig. 3(a)). Then, requesters can subscribe to the published content. The publication and the subscription are matched by a rendezvous system. The matching procedure returns a transport ID that can be used for routing of content through a forwarding network. In PSIRP, the contributionaware ICN can be implemented as follows (Fig. 3

(b)). CDM can be deployed

Requester2

Requester1

Publisher Router at the rendezvous system. When a requester wants to download a content, it sends a content request to the rendezvous system. Then, the rendezvous system first calculates CL of the requester. If CL of the requester is higher than RCL of the requested content, the rendezvous system matches the requester and the publisher. After processing the user request, the rendezvous system returns a transport ID to the requester who has enough CL. The rendezvous system also updates the contribution history of the matched requester and the publisher. A connection for content forwarding is setup based on the returned transport ID and the content is delivered to the requester.

Contribution-aware Content Distribution

Now, we turn our attention to an incentive mechanism to encourage the userassisted content distribution over the contribution-aware ICN. The incentive mechanism over the contribution-aware ICN can be achieved by CL generation policy and RCL assignment policy. Two policies can be managed by one entity (i.e., a content provider or a user) or different entities (e.g., a user can publish a content with its own RCL assignment policy through public CDM that has pre-defined policy for CL generation set by a content provider). According to a content distribution policy of the publisher, various policies for CL generation and RCL assignment are possible. In this paper, we introduce our choices for a file sharing as a starting point of our research while leaving other possible approaches for future work. In this paper, we assume that RCL of original content publisher is used for re-publication of downloaded content by users. We also assume that a content is divided into segments and each segment is named together with its content name (e.g., ContentName.SegmentID). The original content publisher publishes its content with RCL incrementally increasing. For example, in case of content consisting of 300 segments, first 100 segments have 0 RCL, next 100 segments have 0.1 RCL, and remaining 100 segments have 0.2 RCL. For bootstrapping of newly joining users, some segments are published with zero RCL (i.e., no CL requirement for download). The newly joining peers need some segments to upload, since they need to increase their CL by uploading the content. By downloading and uploading the segments with 0 RCL, the newly joining user may be able to increase its CL enough to download the segments with non-zero RCL. The incrementally increasing RCL may encourage the users to keep uploading the downloaded segments to increase CL enough to satisfy RCL of remaining segments requiring higher RCL than the downloaded segments. CDM generates CL according to a pre-defined method when it receives a request from a user. As a basic form, in this paper including the evaluation part, CL is calculated as a ratio of the uploaded content to the downloaded content. CL is valid for 10 seconds. Due to some reasons, a user may do not have chance to upload its content even though they willingly want to contribute their resources. In this case, CDM generates free pass CL (FPCL) that can be used to download some segments without satisfying RCL. For example, when there is only one requester or when other users already have segments that the requester has, the requester cannot upload to anybody. When only one requester exists, FPCL for all segments is generated. When the requester does not have segments to upload, FPCL for rare segments is generated so that the requester can have a chance to upload the downloaded rare segments. To prevent the free riders from receiving FPCL from CDM, CDM generates FPCL only for users who publish every downloaded segment under an assumption that the user who publishes the content willingly uploads the content when it receives the content request. For this, in CCN case, the router needs to report the content publication by users to CDM. Please note that CDM can know when what user downloads what content based on the contribution history.

Evaluation

Using ns-2 [START_REF]The Network Simulator ns-2[END_REF], we evaluate (1) an effect of user participation on content download performance in ICN and (2) a feasibility of the contribution-aware ICN and the incentive mechanism in terms of resources utilization efficiency. We use PSIRP architecture as the existing ICN architecture for our simulation. We build the simulation topology by using transit-stub model. Our topology includes 1 transit and 10 stub networks connected to the transit domain. In our simulation, a performance bottleneck is user link capacity. For link capacity of users, we set 120KB/s and 40KB/s for downlink and uplink capacity. We use 1,000 users including one initial content publisher. 100MB-sized content is divided into 400 256KB-sized segments. To study an effect of different user types in terms of participation in the content distribution, we divide users into three types: free rider (no content upload), altruistic user (upload the downloaded segments regardless of its CL), and rational user (upload the downloaded segments to increase its CL just enough to download remaining segments). In addition, to study an effect of RCL assignment policy, we assign increasing RCL (0, 0.1, 0.2, and 0.3 for each 100 segments) or flat RCL (0 for 100 segments and 0.1 for remaining 300 segments) for the content. For comparison purpose, we conduct simulations with the existing ICN and the contribution-aware ICN. In the existing ICN, every user downloads the content regardless of its contribution, since there is no RCL. On the other hand, in the contribution-aware ICN, only user who satisfies RCL can download a content.

Effect of User Participation

Through simulations, we find that the user participation has noticeable effect on download performance in ICN (including the existing ICN and the contribution-aware ICN). In the existing ICN (Fig. 4) and the contributionaware ICN (Fig. 5)2 , the download performance improves linearly as the cache hit ratio increases. On the other hand, the download performance improves significantly as a number of altruistic users increases. Even though the free riders download the content without corresponding contributions in the existing ICN, more number of altruistic users leads to better performance by providing more upload capacity. Due to the same reason (except that the free riders can only download the segments with 0 RCL), in the contribution-aware ICN, the download performance improves as a number of altruistic users increases. This result shows that the user participation has significant impact on the content distribution performance, especially when the cache hit ratio is low. This also means that the download performance can be improved through the user participation even though the content is not popular enough to be cached by ICN router.

We have interesting observations from the contribution-aware ICN with rational users (Fig. 6(a)). When the cache hit ratio is low (less than 40% in our simulation), more number of rational users leads to worse content distribution performance. In case of the free riders, they cannot download segments with non-zeo RCL while freely downloading the segments with 0 RCL. On the other hand, the rational users can continue to download the segments as long as they have enough CL. However, the rational users stop their contributions when they have enough CL to download the segments with non-zero RCL. In other words, amount of upload capacity provided by the rational users is not guaranteed while total amount of required download capacity is fixed. Due to a shortage of upload capacity, some content requests of rational users who have enough CL cannot be handled rapidly and thus this leads to poor performance. However, if the cache hit ratio is high enough to complement the shortage of upload capacity, more number of rational users leads to better performance.

Effect of RCL

From the comparison between the existing ICN (Fig. 4) and the contributionaware ICN with the altruistic users (Fig. 5), we find that the free riders degrade the content distribution performance by consuming system resources (i.e., upload capacity of publisher and non-free riders) without contribution. Please note that a comparison between the existing ICN and the contribution-aware ICN with rational users is meaningless, since the non-free riders in the existing ICN are the altruistic users. In the existing ICN, the free riders and the non-free riders show similar download performance, since they download the content regardless of their upload contributions. This result shows that there should be proper incentive mechanism to prevent the free riders from exploiting the system resources for efficient utilization of system resources in ICN.

In the existing ICN, the portion of system resources utilized by the non-free riders increases linearly as a number of the non-free riders increases, since the free riders and the non-free riders compete with each other to download the content regardless of their contributions. On the other hand, in the contribution-aware ICN (regardless of types of non-free riders), more portion of system resources is utilized by the non-free riders (Fig. 7). Remaining portion of the system resources are used by the free riders to download the segments with zero RCL. Thus, that portion decreases as a number of non-free riders increases. Even though the download performance of contribution-aware ICN with rational users is not as good as the case of the contribution-aware ICN with altruistic users due to the unwillingness of user participation in content distribution, most portion of the system resources is utilized by the non-free riders. Above results show that the contribution-aware ICN can utilize the system resources efficiently by preventing the free riders based on the contribution-related information (i.e., RCL, CL, and contribution-aware routing). It also means that the download performance of the contribution-aware ICN can be further improved with a proper incentive mechanism (i.e., RCL assignment and CL calculation policy). We will study this later as future work. Now, we examine an effect of two RCL assignment policies on the download performance: increasing RCL and flat RCL. The contribution-aware ICN with altruistic users show similar download performance with both the increasing RCL (Fig. 5(a)) and the flat RCL (Fig. 5(b)), since the altruistic users continue to contribute regardless of their CL. On the other hand, in case of the contributionaware ICN with rational users, the increasing RCL (Fig. 6(a)) is more effective than the flat RCL (Fig. 6(b)) to encourage the rational users to contribute their resources. This result shows that the increasing RCL can encourage the rational users to keep uploading the downloaded segments to increase CL enough to satisfy RCL of remaining segments.

Conclusion

In this paper, we introduce the contribution-aware ICN to utilize the user resources for efficient content distribution by mitigating the free-riding issue. The contribution-aware ICN utilizes the centralized entity to manage the user contribution and the content is published with the required contribution level so that the users with enough contribution only can request the content. Through simulation, we show that the contribution-aware ICN encourages the users to contribute their resources. We also show that the content download performance improves significantly as the number of users contributing the resources increases. We are currently focusing on efficient utilization of given user resources and effective incentive mechanism when there are various types of users publishing content with different RCL.

Fig. 1 .

 1 Fig. 1. Conceptual illustration of ICN.

Fig. 4 .

 4 Fig. 4. Existing ICN without RCL.

Fig. 5 .

 5 Fig. 5. Contribution-aware ICN with altruistic users.

Fig. 6 .

 6 Fig. 6. Contribution-aware ICN with rational users.

Fig. 7 .

 7 Fig. 7. % of resources utilized by non-free riders.

  table. If there is matched one, it forwards the user request. If there is no matched entry

	Requester1		Requester1
	Router 3. Request 6. Content	1. Publish	2. CL (0.5) CDM 8. Co ntr ibu tio n his tor y	Router 4. Request (with CL 0.5) 7. Content	1. Publish (with RCL 0.4)
	Router		3. CL (0.2)	Router
	Requester2	Publisher	Requester2		Publisher
	(a) CCN		(b) Contribution-aware ICN
	Fig. 2. Contribution-aware ICN over CCN.

For the purpose of illustration, we use CCN[START_REF] Jacobson | Networking named content[END_REF] as a basic design example.

In the figures, numbers of figure legend indicate % of non-free riders among 1000 users. In the existing ICN, the non-free riders are altruistic users, since there is no RCL.


Vijay Mann
email: vijamann@in.ibm.com

Akanksha Gupta
email: akguptal@in.ibm.com

Partha Dutta
email: parthdut@in.ibm.com

Anilkumar Vishnoi
email: avishnoi@in.ibm.com

Parantapa Bhattacharya
email: parantapa@cse.iitkgp.ernet.in

Rishabh Poddar
email: rishabh.pdr@gmail.com

Aakash Iyer
email: aakiyer1@in.ibm.com

Remedy: Network-aware Steady State VM Management for Data Centers

Keywords:

Steady state VM management in data centers should be network-aware so that VM migrations do not degrade network performance of other flows in the network, and if required, a VM migration can be intelligently orchestrated to decongest a network hotspot. Recent research in network-aware management of VMs has focused mainly on an optimal network-aware initial placement of VMs and has largely ignored steady state management. In this context, we present the design and implementation of Remedy. Remedy ranks target hosts for a VM migration based on the associated cost of migration, available bandwidth for migration and the network bandwidth balance achieved by a migration. It models the cost of migration in terms of additional network traffic generated during migration. We have implemented Remedy as an OpenFlow controller application that detects the most congested links in the network and migrates a set of VMs in a networkaware manner to decongest these links. Our choice of target hosts ensures that neither the migration traffic nor the flows that get rerouted as a result of migration cause congestion in any part of the network. We validate our cost of migration model on a virtual software testbed using real VM migrations. Our simulation results using real data center traffic data demonstrate that selective network aware VM migrations can help reduce unsatisfied bandwidth by up to 80-100%.

Introduction

As more and more data centers embrace end host virtualization and virtual machine (VM) mobility becomes commonplace, it is important to explore its implications on data center networks. VM migration is known to be an expensive operation because of the additional network traffic generated during a migration, which can impact the network performance of other applications in the network, and because of the downtime that applications running on a migrating VM may experience. Most of the existing work on virtual machine management has focused on CPU and memory as the primary resource bottlenecks while optimizing VM placement for server consolidation, dynamic workload balance, or disaster recovery [START_REF]VMware Server Consolidation[END_REF][START_REF] Jung | Mistral: Dynamically managing power, performance, and adaptation cost in cloud infrastructures[END_REF][START_REF] Verma | pMapper: Power and migration cost aware application placement in virtualized systems[END_REF]. They do not take into account network topology and current network traffic. However, steady state management of VMs should be network-aware so that migrations do not degrade network performance of other flows in the network, and if required, a VM migration can be intelligently orchestrated to decongest a network hotspot. If the trigger to migrate one or more VMs comes from the network itself, it should ensure that the number of VM migrations are kept low. Recent research [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF] [7] [START_REF] Sonnek | Starling: Minimizing communication overhead in virtualized computing platforms using decentralized affinity-aware migration[END_REF] [START_REF] Meng | Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement[END_REF] in network-aware VM management has focused mainly on an optimal network-aware initial placement of VMs and has largely ignored steady state management.

In this context, we present the design and implementation of Remedy: a system for network-aware steady state management of VMs. To the best of our knowledge, Remedy is the first system to perform network-aware management of VMs so as to minimize the cost of VM migration over a long-term. We make the following contributions in this paper:

-We model the cost of VM migration in terms of total traffic generated due to migration. -We present a target selection heuristic (TSH) that ranks target hosts for a VM migration based on the associated cost of migration, available bandwidth for migration and the network bandwidth balance achieved by a migration. -We implement Remedy as an OpenFlow [START_REF] Mckeon | OpenFlow: Enabling Innovation in Campus Networks[END_REF] controller application that can detect the most congested links in a data center network, identify the flows that pass through those links, and select the best flows to be rerouted that can resolve network congestion. 3 It then uses an intelligent VM selector heuristic (VSH) to select VMs that are part of these flows based on their relative cost of migration and then migrates these VMs in a network-aware manner to decongest these links. Our target selection heuristic (TSH) ensures that neither the migration traffic nor the flows that get rerouted as a result of migration cause congestion in any part of the network. -We also implement our prototype in the VMFlow simulation framework [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF] from our earlier work. Our simulation results using real traffic data from a data center demonstrate that selective network aware VM migrations can help reduce unsatisfied bandwidth by up to 80-100%. -We evaluate the Remedy OpenFlow prototype on a virtual software testbed. Our results validate our cost of migration model.

The rest of this paper is organized as follows. Section 2 presents a description of the problem and describes our cost of migration model. Section 3 describes the design and architecture of Remedy. We provide an experimental evaluation of various aspects of Remedy in Section 4. An overview of related research is presented in Section 5. Finally, we conclude the paper in Section 6.

Context:

The data center network is modeled as a directed graph G(V, E), where each link e in E has a capacity C(e). There are two types of vertices in V : the hosts and the network switches. The edges represent the communication links. Each host has a processing capacity. 4 A network demand is defined by the three parameters, its source, destination and its rate.

Configuration: At any given point of time, the configuration of the system consists of the set of VMs (with their current processing requirement), the set of existing demands (with their current rate), the placement Π that maps VM to hosts, and the routing RT that maps demands to paths (in G). (A flow consists of a demand along with its routing path.) The routing is unsplittable, i.e., all the traffic for a demand is sent using a single flow over a single path. Note that multiple VMs can be mapped to a single host.

The load of a link is the sum of the rates of all flows that are routed over that link. The utilization (also called congestion) of a link is defined as the ratio of the load on the link to its capacity. We say that network has α-utilization in a configuration, if the utilization of every link is at most α.

Constraints:

A configuration should satisfy the capacities of all the hosts and the links. In other words, the sum of the processing requirements of all VMs that are placed on a host should be less than or equal to the capacity of the host, and the sum of the rates of all flows routed over a link should be less than or equal to the capacity the link.

Migration Cost: Migrating a VM generates network traffic between the source and the destination hosts of the migration, where the amount of traffic depends on the VMs image size, its page dirty rate, the migration completion deadline and the available bandwidth. We model the cost of a migration as the total traffic generated due to the migration. In this paper, we model the migration cost of VMware vMotion [3]. Note that, even though the model presented in this paper is for VMware vMotion, our techniques are generic enough to be applicable for most live migration systems that are based on iterative pre-copy technique. In particular, the model presented in this work can be extended by making minor modifications to the stop conditions that vary across different hypervisors.

VMware vMotion5 is a pre-copy live migration technique. The conditions for stopping the pre-copy cycle are as follows:

1. The current dirty memory can be transmitted in T milliseconds (i.e., dirty memory is small enough to start a stop-copy of at most T millisecond). Here, T is a user setting, and it is called the switchover goal time. 2. vMotion did not make enough progress in the previous pre-copy cycle. vMotion measures the progress of a migration by the difference in dirty memory before and after a pre-copy cycle. This difference should at least be X MBs, where X is a user setting. We call X the minimum required progress amount.

In case vMotion did not make enough progress, and the current dirty memory cannot be transmitted in 100 seconds, the migration fails. In the following Theorem, we derive the equations for the number of pre-copy cycles, and for the total traffic generated during a migration, under the assumption that the following parameters are given constants: [START_REF]Mininet: Rapid prototyping for software defined networks[END_REF] the memory size M of a VM, (2) the page dirty rate R of a VM and (3) the bandwidth of the link used for migration L.

Theorem 1. The number of pre-copy cycles n = min log R/L T •L M , log R/L X•R M•(L-R)
, and the total traffic generated by the

migration N = M • 1-(R/L) n+1
1-(R/L) . Proof. Let N i denote the traffic on the i th pre-copy cycle. Taking into account the page dirty rate R and the bandwidth L used for migration, we see that the first iteration will result in migration traffic equal to the entire memory size N 0 = M , and time M L . During that time, M R L amount of memory becomes dirty, and hence, the second iteration results in N 2 = M R L amount of traffic. Extending this argument it is easy to see that

N i = M R L i-1 for i ≥ 1.
Thus if there are n pre-copy cycles and one final stop-copy cycle, the total traffic generated by the migration is

N = n+1 i=1 N i = M • 1-(R/L) n+1 1-(R/L)
. We now derive an equation for n.

Suppose that the pre-copy stops after n cycles. Then one of the following two conditions must hold true, at the end of cycle n. (1) From the first pre-copy stopping condition we have,

M R L n < T • L, which in turn implies n < log R/L T •L M . (2) From the sec- ond pre-copy stopping condition we have, M R L n-1 -M R L n < X, which in turn implies n < log R/L X•R M•(L-R) .
Thus, from the above two conditions, the number of pre-copy cycles n = min log R/L

T •L M , log R/L X•R M•(L-R)
. We also note that the time W (L) spent on the stop-copy transfer for a given migration bandwidth L, is given by W

(L) = M L • R L n .
We now describe the online problem that we address to perform network-aware steady state VM management.

Problem: Due to possibly under-provisioned links and time-varying demands, the network utilization may exceed a desired threshold over time. In this problem, we aim to reduce the network utilization by migrating VMs while incurring minimum migration cost. More specifically, we define the online α-Minimum Migration Cost Network Utilization (α-MCNU) problem as follows.

During the data center operation, if there is a change in the demands (in particular, if some demand is created, terminated, or its rate is changed significantly), then the system may introduce one or more VM migrations. Each migration has an upper bound on its completion time. In the α-MCNU problem, given an initial configuration (placement and routing), and the arrival, departure and change of demands over time (which is not known in advance), we need to select a sequence of VM migrations such that the network utilization remains at most α, except during the period of a migration, while ensuring that the cost of migration is minimized. Even the offline version of MCNU problem, where all demand changes are known in advance, is NP-Hard. We present our heuristics for the MCNU problem in section 3.2.

Architecture and Design

In this section we present the architecture and design of Remedy, a system for networkaware steady state VM management (refer Figure 1(a)). Remedy has been implemented in Python as a NOX [START_REF] Gude | NOX: Towards an Operating System for Networks[END_REF] module, which is one of the popular OpenFlow controllers currently available. An OpenFlow controller is connected to all OpenFlow enabled switches and routers and communicates with these switches through a control channel using the OpenFlow control protocol. Remedy has three main components: (1) Bandwidth Monitor, (2) VM and Target Selector and (3) VM Memory Monitor. We now describe each of the above components in detail in the following subsections.

Bandwidth Monitor

OpenFlow provides flow monitoring capabilities in the form of per flow, per port and per queue statistics (using OFPST FLOW, OFPST PORT and OFPST QUEUE request types, respectively as per OpenFlow 1.1 specification). Remedy Bandwidth Monitor first detects all links by using the "discovery" module in NOX. Each link is represented as a 4 tuple: <Start SwitchID,Start PortNumber,End SwitchID,End PortNumber>.

Remedy controller polls for flows statistics and port statistics by periodically sending flowStats (OFPST FLOW) and portStats (OFPST PORT) requests to all the switches in the network. It uses the port statistics to find out the transmitted bytes from each port on each switch in the current polling interval and sorts this list in decreasing order to find the most busy ports in the network. For each port in the busy ports list, it then uses the flow statistics to find out the number of bytes recorded for each flow on that 1: function VSH 2: rank VMs in increasing order of their approx migration cost = 120% of VM size 3: rank VMs in the increasing order of their number of communicating neighbor 4: rank VMs in the increasing order of their total input/output traffic 5: return VM with lowest sum of the three ranks port in the current monitoring interval. Note that a flow represents a network demand and is uniquely identified through source and destination IP addresses (we ignore port numbers since our eventual goal is to find VMs that contribute the most to a link's utilization). This list of flows on each port is also sorted in decreasing order to find the heaviest flows on each port in the network. Since a port may appear on either end of a link, the list of busy ports is used to calculate the traffic on each link and a list of busy links is created. Similarly, the list of heaviest flows on a port is used to calculate the heaviest flows on each link, and their contribution to the overall link utilization is calculated.

Remedy uses an input headroom value to determine a link utilization value beyond which a link is considered congested. For example, if the input headroom value is 20, then a link is considered congested when its utilization crosses 80%. Since a VM may be part of multiple flows either as a source or a destination, the sorted list of heaviest flows on each congested link is used to determine the VMs which are top contributors to a link's utilization. This list of VMs is passed on to the VM and Target Host Selector.

VM and Target Host Selector

The VM and Target Host Selector uses two methods, the VM selector heuristic (VSH) and the target selector heuristic (TSH), to select a VM and the target host for migrating the selected VM, in order to control network utilization. These two heuristics together addresses the MCNU problem with α = 1 (as defined in Section 2). In the case where the VM to be migrated is already provided as input (either by a user or by an existing VM placement engines which consider CPU and memory statistics to migrate a VM for server consolidation, workload balance or fail-over), Remedy uses only the TSH. We now describe these two heuristics in detail. (See Figure 2 for pseudocode.) VM Selector Heuristic (VSH): VM selector heuristic uses the list of top contributor VMs for each congested edge and selects the VMs to be migrated based on number of communicating neighbors of a VM, total input/output traffic of a VM and an approximate cost of migrating a VM. As discussed in section 2, the cost of migrating a VM (in terms of additional network traffic generated) depends on the memory size of the VM, its page dirty rate, the available bandwidth for migration, and some other hypervisor specific constants. Since, the available bandwidth for migration can be known only when the target host for a migration has already been determined, we use 120% of memory size of a VM as a rough indicator of the additional network traffic that would be generated on migrating a particular VM. VMs are first sorted in increasing order by this approximate cost of migration and then by their number of communicating neighbors (in increasing order) and finally by their total input/output traffic. The rank of each VM in these three sorted lists is noted and added together. The VM which has the lowest sum of ranks is selected as the VM to be migrated.

Target Selector Heuristic (TSH): Given a VM to migrate, target selector heuristic ranks target hosts for that VM based on the associated cost of migration, available bandwidth for migration and the network bandwidth balance achieved by a migration. In a typical data center, a physical host has many VMs running on it, which are connected to physical network interfaces through a virtual switch (or vSwitch) inside the hypervisor. Physical hosts are directly connected to a ToR switch, which in turn is connected to one or more aggregate switches. The aggregate switches then connect to a layer of core switches. In some data centers, the aggregate and core switches may form a single layer. TSH evaluates all end hosts that have free CPU capacity. For all such hosts, it finds the path from the current host and evaluates the available bandwidth. Note that, Remedy directly calculates the available bandwidth on a path using the flow statistics collected by Bandwidth Monitor from all switches. Thus, Remedy does not need to use any available bandwidth estimation tools. Based on the observed bandwidth, Remedy calculates the cost of migration as per the cost of migration model described in Section 2 (which is in terms of additional network traffic that will be generated during migration). This additional network traffic is added to existing traffic on the chosen path and the resultant available bandwidth is calculated to ensure that migration is feasible. If migration is feasible, TSH then calculates the available bandwidth for all network demands or flows that this VM is a part of and which will get rerouted as a result of this migration. TSH calculates a normalized weighted sum of these available bandwidths (each demand from a VM is first normalized with respect to the largest demand for that VM, and then multiplied by the available bandwidth on its path -this step is repeated for all demands for a given VM, and these are added up across all network demands of that VM). This normalized weighted sum of available bandwidths is used to create a ranked list of all destination hosts to which a migration is feasible. Intuitively, this normalized weighted sum of available bandwidths favors large flows over small flows and the heuristic attempts to create the best possible available bandwidth balance after migration. The Remedy System tries to migrate the selected VM to the destination host one by one, according to the above ranked list, until a migration is successful.

VM Memory Monitor

VM Memory Monitor fetches the memory size and the current average page dirty rate for each VM. The settings for memory size are usually exposed by the virtualization manager. We use VMware ESXi hypervisor as our virtualization platform that support live VM migration in the form of VMware "vMotion". VMware ESXi hypervisor has a remote command line interface (RCLI) [START_REF]VMWare vSphere command line interface[END_REF], that has commands to fetch memory size and also to initiate a migration. However, it does not expose a direct metric to measure page dirty rate. We currently rely on VMware ESXi logs to find out page dirty rates.

Experimental Evaluation

We first validated the correctness of our system on an innovative virtual software environment that leverages nested system virtualization and software switches. In order to analyze the effects of VM selector and target selector heuristics at scale, we implemented these heuristics in the VMFlow simulation framework from our earlier work [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF] and conducted simulations using traffic data from a real data center. We now describe these experiments in detail.

Validating Remedy in an OpenFlow Network

Virtual Software Testbed: We created an innovative virtual emulation environment that gave us full control over the network as well as VM mobility across hosts. We leveraged nested server virtualization in VMware ESXi server [START_REF]VMware vSphere Hypervisor[END_REF] to create VMs that run hypervisor software within a single physical machine. Our virtual testbed that emulates two hosts (each with two VMs) inside a single physical blade server is shown in Figure 1(b). The various VMs that run the hypervisor software (we refer to them as virtual hypervisors) represent multiple virtual hosts. Virtual hypervisor or virtual hosts are connected to each other through an OpenFlow software switch (version 1.1) or a Mininet [START_REF]Mininet: Rapid prototyping for software defined networks[END_REF] data center network with multiple OpenFlow software switches running inside a VM. Mininet uses process-based virtualization and network namespaces to rapidly prototype OpenFlow networks. Simulated hosts (as well as OpenFlow switches) are created as processes in separate network namespaces. Connectivity between hosts and switches, and between switches is obtained using virtual interfaces and each host, switch and the controller has a virtual interface (half of a "veth" pair). We connect two real hosts (in this case, the virtual ESXi hosts) on two interfaces of the Mininet VM such that they are connected to the data center network created inside the Mininet VM. We run the Remedy controller on top of NOX as a remote controller inside another VM and this is also connected to the Mininet data center network. Shared storage for these virtual hosts is provided by shared NFS service also running inside a VM and connected to the Mininet data center network. Virtualization manager (VMware vCenter) runs inside another VM. Direct wire connectivity between these various VMs (OpenFlow or Mininet VM, Controller VM, NFS VM, vCenter VM and Virtual Hypervisor VMs) is achieved through various vSwitches on the base hypervisor. We also created VMs on top of the virtual hypervisors (or virtual hosts) that can be migrated across various hosts. While, the virtual testbed provides only an emulation environment and can not be used for any scalability or absolute performance comparison, it still proves to be a valuable tool to verify the correctness of our system using real VM migrations on VMware ESXi hypervisor, and OpenFlow capable software switches.

Results:

In order to validate our cost of migration model described in section 2, we developed a simple page modification microbenchmark. This microbenchmark, first allocates large chunks of page aligned memory. It then randomly writes to different pages in a loop and executes busy loop for a predetermined count based on the specified page dirty rate. The page modification benchmark is executed with different page dirty rates on one of the VMs hosted on the virtual ESXi server. The two virtual ESXi servers were connected via an OpenFlow switch VM for this experiment. This VM was then migrated to another virtual ESXi at different link bandwidths. To create different link bandwidths, a queue was created on the output port of the OpenFlow switch and the minimum rate on that queue was set to the desired value. Remedy controller installed a rule to enqueue all migration traffic (identified through TCP port numbers used by "vMotion") to this queue and all other traffic was sent through the default queue. The total migration traffic was monitored inside the Remedy Controller, as well as verified through VMware ESXi logs. The page dirty rates were also verified through VMware ESXi logs. The results are shown in Figure 3 for two VM sizes -512 MB and 1024 MB.

In both the cases, our model predicts the total migration traffic to within 97% accuracy for all page dirty rates and link bandwidths.

Validating the effectiveness of VM and target selector heuristics at scale through simulations

In this section we evaluate the VM selector and target selector heuristics at scale through simulations in the VMFlow simulation framework [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF]. Note that in all these simulations, the cost of migration was assumed to be 1.2 times the memory size of a VM as mentioned in section 3. Deadline for migration completion time was assumed to be equal to the monitoring interval for our input traffic matrices (15 minutes). The memory sizes for all VMs were assumed to be normally distributed with a mean of 1 GB and standard deviation of 512 MB. With these settings, the goal of the simulation experiments is to evaluate the effectiveness of VM and target selector heuristics at scale in achieving network balance and their ability to satisfy bandwidth demand. Results from VMFlow simulator with 1000 VMs and 1:1 host to VM mapping using data from a real data center over a 12 hour period: Results illustrate benefits of using network-aware steady state VM management -unsatisfied bandwidth reduces up to 100% at some time-steps in the simulation, adding migration cost-awareness to the heuristics reduce the total number of migrations required to achieve this benefit from 17 to 11

VMFlow Simulator: VMFlow simulator simulates a network topology with VMs, switches and links as a discrete event simulation. Each host is assumed to contain one or more VMs. VMs are either randomly mapped to all hosts (in case of 1:1 host to VM mapping) or they are mapped based on their CPU requirements (in case 1:N host to VM mapping). VMs run applications that generate network traffic to other VMs, and VMs can migrate from one node to the other. At each time step, network traffic generated by VMs (denoted by an entry in the input traffic matrix) is read and the simulator attempts to satisfy these demands in decreasing order (largest demands are satisfied first). For a given demand, it calculates the corresponding route between the hosts based on an already used path or the shortest path in the network topology, while ensuring that available link capacities can satisfy the given network demand. In order to simulate congestion, we modified the simulator so that it can take more demands than available link capacities. For the results in this paper, we simulated 20% congestion where each link can take 20% more traffic than its rated capacity. The simulator then executes an ongoing optimization step in which it detects congestion, finds the set of VMs to migrate to decongest the network using VM selector heuristic (VSH) and selects the appropriate set of destinations for each VM using the target selector heuristic (TSH). At each time step of the simulation, we compute the total bandwidth demand that can not be satisfied, the number of migrations required and link utilizations. A new input traffic matrix that represents the network traffic at that time instance, is used at each time step of the simulation.

Network Topology and Input Traffic Matrices:

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 40 hosts connected to it. We assume a total of 1000 VMs and 1100 hosts for the 1:1 VM to host mapping scenario, and 640 hosts for 1:N host to VM mapping scenario. The topology used for these simulations is shown in Figure 4(a).

To drive the simulator, we needed a traffic matrix (i.e. which VM sends how much data to which VM). 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. Our first task was to calculate a traffic matrix out of this aggregate per VM data. Given (b) After 1 network-aware migration Fig. 6. Agg-Core layer link utilizations from VMFlow simulator with 1000 VMs and 1:1 host to VM mapping using data from a real data center at time step 2 (point 2 in Figure 5(a)). Results illustrate benefits of a single network-aware VM migration -links that were congested and hence could not take on additional bandwidth demands (in the no migration case) get decongested through 1 network-aware VM migration the huge data size, we chose data for a single day. We used the simple gravity model to create a traffic matrix out of this aggregate per VM data (as described in [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF]). As noted in [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF], these traffic matrices did not show much variation over time. Note that traffic matrices generated by simple gravity model tend to be dense and traffic is distributed over all the VMs in some proportion. This results in a large number of very low network demands. In order to make these demands significant so that they can cause congestion in the network, we used a scale-up factor of 50 (i.e. each entry in the input traffic matrix was multiplied by 50) for the traffic matrices used in 1:1 host to VM mapping experiment and scale up factors of 75 and 125 for the traffic matrices used in 1:N host to VM mapping experiments. A distribution of network demands for one of the traffic matrices (used for one time step in simulation) after applying a scale factor of 50 is shown in Figure 4(b). This matrix had 1 million total demands out of which only 20% are zero demands. Maximum demand size was 65.91 MB/s and the mean demand size was 13 KB/s.

1:1 host to VM mapping simulation results:

We first ran the simulation for 1:1 host to VM mapping. Since, the input traffic matrices are already dense (much more than a real data center traffic matrix), 1:1 host to VM mapping is useful to show the benefits of our heuristics. We conducted two sets of simulations:

-The first set of simulations, assumed that VM migrations were of 0 cost and the only objective was to decongest a given edge (with the constraint that only two migrations were allowed per congested edge). -During our second set of simulations, we assigned a cost of VM migration based on the cost of migration model given in section 2 that uses memory size of a VM, its page dirty rate, and link bandwidth to predict the additional traffic generated on the network.

Simulation results for 1:1 host to VM mapping are shown in Figure 5(a) and in Figure 5(b). Results illustrate benefits of using network-aware steady state VM management. Unsatisfied bandwidth reduces up to 100% at some time-steps in the simulation (refer Figure 5(a)) while adding migration cost-awareness to the heuristics reduces the total number of migrations required to achieve this benefit from 17 to 11 (refer Figure 5(b). Link utilizations for the aggregate-core layer for one of the time steps (time step 2 in Figure 5) are given in Figure 6(a) for the no migration base case, and in Figure 6 for the 0 cost network aware migration case. Note that the links that were congested (marked by circles) and hence could not take on additional bandwidth demands (in the no migration case) get decongested through a single network-aware VM migration.

1:N host to VM mapping simulation results:

In this section, we present the simulation results for 1:N host to VM mapping scenario. We assumed a fixed host CPU capacity of 4 GHz and generated normally distributed random CPU demands for each VM with a mean demand of 1.6 GHz and standard deviation of 0.6 GHz.

VMs are mapped based on their CPU requirements. 1000 VMs were mapped onto 574 hosts and the remaining hosts remained idle. While, choosing the best host for a VM under a given ToR switch, the host with the maximum available link bandwidth to the ToR switch is chosen, provided that the host has enough spare CPU capacity to host the VM. Traffic matrices were scaled up by a factor of 75.

In this case again we conducted two sets of simulations -one which assumed a 0 migration cost, and the other that calculated a cost of migration in terms of additional network traffic generated as per our cost of migration model. Simulation results for 1:N host to VM mapping are shown in Figure 7(a). Unsatisfied bandwidth reduces by up to 15% at some time steps in the simulation. However, the gains here are modest, as compared to 1:1 mapping scenario, since the traffic matrix is already dense and as more VMs are packed into a single host, the network traffic matrix becomes denser, reducing the ability to move VMs freely. However, real data center traffic matrices are much less dense (as compared to the traffic matrices generated by simple gravity model that we used), and hence we expect the gains to be much higher in real data centers. To verify this, we generated sparse matrices by randomly making half of the demands zero, while increasing the scale factor for traffic matrices from 75 to 125. Simulation results for the sparse matrices are given in Figure 7(b). Unsatisfied bandwidth now reduces by up to 75%. Adding migration cost-awareness to the heuristics reduces the total number of migrations required in both the scenarios (from 11 to 8 in the dense communication matrix, and from 15 to 13 in the sparse communication matrix scenario). Note that at one time step in dense communication matrices, the unsatisfied bandwidth increases resulting in negative reduction value. We believe this also happened primarily due to a dense traffic matrix, where the added congestion in the network resulted in the simulator trying to satisfy larger demands and failing, when it could have satisfied smaller demands.

Background and Related Work

Recently there has been significant amount of work on VM placement and migration. The related research work can be broadly classified as follows.

Network-aware placement of VMs

Our prior work on network-aware initial placement of VMs -VMFlow [START_REF] Mann | VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[END_REF], proposed a greedy heuristic for initial placement of VMs to save network power while satisfying more network demands. As one of the contributions of this paper, VMFlow simulator has been enhanced with the VM selector heuristic (VSH) and TOR selector heuristic (TSH) to incorporate network-aware steady state management.

The online minimum congestion mapping problem studied in [START_REF] Bansal | Minimum congestion mapping in a cloud[END_REF] by Bansal et al. is close to our work: it considers placing a workload consisting of network traffic demands and processing demands on an underlying network graph (substrate) while trying to minimize the utilization over all links and nodes. The paper [START_REF] Bansal | Minimum congestion mapping in a cloud[END_REF], however, differs from our work in two crucial aspects. First, in [START_REF] Bansal | Minimum congestion mapping in a cloud[END_REF], once a workload is placed (i.e., its node and link assignment are finalized by the algorithm), this assignment cannot be changed during placement of subsequent workloads. On the other hand, migrating the source and destination of a network demand (which corresponds to VMs in our setting) is the primary technique used in this paper. Second, we consider the cost of VM migration, and ensure that the migration is completed in a timely manner, which are not considered in [START_REF] Bansal | Minimum congestion mapping in a cloud[END_REF]. Sonnek et al. [START_REF] Sonnek | Starling: Minimizing communication overhead in virtualized computing platforms using decentralized affinity-aware migration[END_REF] propose a technique that monitors network affinity between pairs of VMs and uses a distributed bartering algorithm coupled with migration to dynamically adjust VM placement such that communication overhead is minimized. Meng et al. [START_REF] Meng | Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement[END_REF] consider heuristics for VM placement in a data center to optimize network traffic while minimizing the cost of VM migration. Although their primary algorithm is presented in an offline setting, it can be executed periodically to modify the VM placements according to the time-varying network demands. However, unlike our paper, their placement algorithm does not consider minimizing the cost over a sequence of network demand changes, but only tries to minimize the cost of each individual step. Moreover, the solution presented by [START_REF] Meng | Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement[END_REF] does not specify the routing path for the traffic demands, which is handled by our work. Finally, compared to [START_REF] Meng | Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement[END_REF], our solution uses a more detailed model for the cost and time required for the VM migrations.

Cost-aware migration of VMs and prediction of migration performance

Most of the existing research [10] [8] [6] on cost-aware migration of VM analyzes the impact of a live VM migration on the workload that is executing on the migrating VM itself. Breitgand et al. [START_REF] Breitgand | Cost-aware live migration of services in the cloud[END_REF] model the total cost of live in-band migration, and present an optimal bandwidth allocation algorithm for in-band live migration such that the cost of migrating a VM, in terms of the down time experienced by the migrating VM, is minimum. However, in a shared data center network, a VM migration also affects the performance of other hosts in the network, which is the focus of our work. Jung et al. [START_REF] Jung | Mistral: Dynamically managing power, performance, and adaptation cost in cloud infrastructures[END_REF] present a holistic optimization system that considers various costs of migration, such as, application performance degradation of the migrating VM and power trade offs. Sherif et al. [START_REF] Akoush | Predicting the performance of virtual machine migration[END_REF] present two simulation models that are able to predict migration time to within 90% accuracy for both synthetic and real-world benchmarks running on Xen hypervisor. Stage et al. [START_REF] Stage | Network-aware migration control and scheduling of differentiated virtual machine workloads[END_REF] propose a complementary scheme in which network topology aware scheduling models are used for scheduling live VM migrations such that effect of VM migrations on other nodes in the network is reduced.

Conclusion

In this paper, we presented the design and implementation of Remedy -a system for network aware steady state VM management that ranks target hosts for a VM migration based on the associated cost of migration, available bandwidth for migration and the network bandwidth balance achieved by a migration. Our simulation results using real data center traffic data demonstrated that selective network aware VM migrations, as proposed in Remedy, can help reduce unsatisfied bandwidth by up to 80-100%.

As part of ongoing and future work, we are currently working on implementing Remedy in a real data center with state-of-the-art network equipment. Future extensions to Remedy include a decentralized design for monitoring and an analysis engine to analyze network demands and link utilizations using auto regressive moving average model to verify whether a given demand or link utilization is stable or a transient spike. This will help us make more informed decisions to tackle long term congestion. Finally, we also plan to work on extending the cost of migration model to other hypervisors such as Xen and KVM.

Fig. 1 . 2 .

 12 Fig. 1. Remedy Architecture and Virtual Emulation Environment Theorem 2. The offline version of MCNU problem is NP-Hard.

6 : 11 :Fig. 2 .

 6112 Fig. 2. Pseudocode for VSH and TSH

Fig. 3 .

 3 Cost of migration model predicts migration traffic to within 97% accuracy

Fig. 4 .

 4 Fig. 4. VMFlow simulations to evaluate the VM selector and Target selector heuristics

  Fig.5. Results from VMFlow simulator with 1000 VMs and 1:1 host to VM mapping using data from a real data center over a 12 hour period: Results illustrate benefits of using network-aware steady state VM management -unsatisfied bandwidth reduces up to 100% at some time-steps in the simulation, adding migration cost-awareness to the heuristics reduce the total number of migrations required to achieve this benefit from 17 to 11

Fig. 7 .

 7 Fig.7. Results from VMFlow simulator with 1000 VMs and 640 hosts (1:N host to VM mapping, 1000 VMs were mapped to 574 hosts using CPU data) using data from a real data center over a 12 hour period: Reduction in unsatisfied bandwidth is lower (up to 15%) for dense communication matrix generated by simple gravity model and goes up to 75% for a sparse matrix.

6 Virtualization Manager VMware vCenter Remedy Controller (NOX Module)

			VM Memory Size
			VM Page Dirty
			Rate
			VM Migration
			Commands
		Manage
	VM VM VM	VM VM VM	VM VM VM	VM VM VM
	Hypervisor	Hypervisor	Hypervisor	Hypervisor
	VMware ESXi	VMware ESXi	VMware ESXi	VMware ESXi

ToR Switch Core Switch ToR Switch ToR Switch ToR Switch Bandwidth Monitor VM Memory Monitor Bandwidth Monitor VM and Target Host Selector

Although, storage and memory requirements/capacities of the VMs and the hosts are not considered in this paper, our solution can be extended for these requirements.

[START_REF]VMware vSphere Hypervisor[END_REF] For ease of presentation, we use the terms vMotion and VM migration interchangeably.