Cloud infrastructure providers and data center operators spend a major portion of their operations budget on the electric bills. We present RED-BL (Relocate Energy Demand to Better Locations), a framework for determining an optimal mapping of workload to an existing set of data centers while considering the cost of workload relocation. Within each workload mapping interval, RED-BL solution exploits the geo diversity in electricity price markets. The temporal diversity in those markets is simultaneously exploited by considering a planning window comprising several mapping intervals. Using workload traces from live Internet applications and electricity prices from the US markets, RED-BL can reduce the electric bill by as much as 81% from the case when the workload is equally distributed. Compared to a single data center deployment, an average reduction of 27% in electric bill can be achieved when RED-BL uses 10 or more data centers, a common case for most operators. When compared to existing workload relocation solutions, RED-BL achieves a further reduction of 13.63%, on average. While modest, this reduction can save millions of dollars for the operators. The cost of this saving is an inexpensive computation at the start of each planning window.

Monitoring transit traffic at one or more points in a network is of interest to network operators for reasons of traffic accounting, debugging or troubleshooting, forensics, and traffic engineering. Previous research in the area has focused on deriving a placement of monitors across the network toward the end of maximizing the monitoring utility of the network operator for a given traffic routing. However, both traffic characteristics and measurement objectives can dynamically change over time, rendering a previously optimal placement of monitors suboptimal. It is not feasible to dynamically redeploy/reconfigure measurement infrastructure to cater to such evolving measurement requirements. We address this problem by strategically routing traffic subpopulations over fixed monitors. We refer to this approach as MeasuRouting. The main challenge for MeasuRouting is to work within the constraints of existing intradomain traffic engineering operations that are geared for efficiently utilizing bandwidth resources, or meeting quality-of-service (QoS) constraints, or both. A fundamental feature of intradomain routing, which makes MeasuRouting feasible, is that intradomain routing is often specified for aggregate flows. MeasuRouting can therefore differentially route components of an aggregate flow while ensuring that the aggregate placement is compliant to original traffic engineering objectives. In this paper, we present a theoretical framework for MeasuRouting. Furthermore, as proofs of concept, we present synthetic and practical monitoring applications to showcase the utility enhancement achieved with MeasuRouting.

A significant fraction of network events (such as topology or route changes) and the resulting performance degradation stem from premeditated network management and operational tasks. This paper introduces a general class of Graceful Network State Migration (GNSM) problems, where the goal is to discover the optimal sequence of operations that progressively transition the network from its initial to a desired final state while minimizing the overall performance disruption. We investigate two specific GNSM problems: 1) Link Weight Reassignment Scheduling (LWRS) studies the optimal ordering of link weight updates to migrate from an existing to a new link weight assignment; and 2) Link Maintenance Scheduling (LMS) looks at how to schedule link deactivations and subsequent reactivations for maintenance purposes. LWRS and LMS are both combinatorial optimization problems. We use dynamic programming to find the optimal solutions when the problem size is small, and leverage ant colony optimization to get near-optimal solutions for large problem sizes. Our simulation study reveals that judiciously ordering network operations can achieve significant performance gains. Our GNSM solution framework is generic and applies to similar problems with different operational contexts, underlying network protocols or mechanisms, and performance metrics.

Monitoring transit traffic at one or more points in a network is of interest to network operators for reasons of traffic accounting, debugging or troubleshooting, forensics, and traffic engineering. Previous research in the area has focused on deriving a placement of monitors across the network towards the end of maximizing the monitoring utility of the network operator for a given traffic routing. However, both traffic characteristics and measurement objectives can dynamically change over time, rendering a previously optimal placement of monitors suboptimal. It is not feasible to dynamically redeploy/reconfigure measurement infrastructure to cater to such evolving measurement requirements. We address this problem by strategically routing traffic sub-populations over fixed monitors. We refer to this approach as MeasuRouting. The main challenge for MeasuRouting is to work within the constraints of existing intra-domain traffic engineering operations that are geared for efficiently utilizing bandwidth resources, or meeting Quality of Service (QoS) constraints, or both. A fundamental feature of intra-domain routing, that makes MeasuRouting feasible, is that intra-domain routing is often specified for aggregate flows. MeasuRouting, can therefore, differentially route components of an aggregate flow while ensuring that the aggregate placement is compliant to original traffic engineering objectives. In this paper we present a theoretical framework for MeasuRouting. Furthermore, as proofs-of-concept, we present synthetic and practical monitoring applications to showcase the utility enhancement achieved with MeasuRouting.

With over half a billion users, Online Social Networks (OSNs) are the major new applications on the Internet. Little information is available on the network impact of OSNs, although there is every expectation that the volume and diversity of traffic due to OSNs is set to explode. In this paper, we examine the specific role played by a key component of OSNs: the extremely popular and widespread set of third-party applications on some of the most popular OSNs. With over 81,000 third-party applications on Facebook alone, their impact is hard to predict and even harder to study.

A significant fraction of network events (such as topology or route changes) and the resulting performance degradation stem from premeditated network management and operational tasks. This paper introduces a general class of graceful network operation (GNO) problems, where the goal is to discover the optimal sequence of operations that progressively transition the network from its initial to a desired final state while minimizing the overall performance disruption. We investigate two specific GNO problems: (a) link weight reassignment scheduling (LWRS) studies the optimal ordering of link weight updates to migrate from an existing to a new link weight assignment, and (b) link maintenance scheduling (LMS) looks at how to schedule link deactivations and subsequent reactivations for maintenance purposes. LWRS and LMS are both combinatorial optimization problems. We use dynamic programming to find the optimal solutions when the problem size is small, and leverage ant colony optimization to get near-optimal solutions for large problem sizes. Our simulation study reveals that judiciously ordering network operations can achieve significant performance gains. Our GNO solution framework is generic and applies to similar problems with different operational contexts, underlying network protocols or mechanisms, and performance metrics.

Multimedia Broadcast/Multicast Service (MBMS) allows a common broadcast channel to be shared by users interested in identical content. We explore the problem of enhancing MBMS resilience by repairing packets lost during broadcast. Since MBMS broadcast consumes expensive 3G resources, we leverage the ubiquity of multi-homed mobile devices i.e., devices having both cellular and IEEE 802.11 wireless interfaces. We thus accomplish out-of-band repair of MBMS packet losses through an ad-hoc, peer-to-peer 802.11-based network. A fundamental challenge in scheduling repair transmissions is handling interference between distributed nodes. We present DiCoR, a fully distributed protocol for CPR. Our protocol does not assume any a priori knowledge of the network topology or peer losses, and is resilient to dynamic network changes due to node mobility or the continuous joining and leaving of peers. Detailed simulation experiments, under realistic loss models and network conditions, demonstrate that DiCoR presents a viable solution for timely out-of-band loss repair of MBMS real-time broadcast.

Cooperative Peer-to-Peer Repair (CPR) has been proposed to recover from packet losses incurred during 3G broadcast. CPR leverages the increasing presence of multi-homed mobile devices having both 3G cellular and IEEE 802.11 wireless interfaces. Mobile devices can, therefore, draw upon IEEE 802.11 peering links to cooperatively achieve out-of-band repair of 3G broadcasting losses. This paper considers the problem of employing Network Coding (NC) to exploit the broadcast nature of the wireless medium towards enhancing the efficiency of CPR. We show that the minimum latency scheduling problem for NC based CPR (NC-CPR) is NP-Hard. We present heuristics for NC-CPR that assume a priori topology and packet loss information. Insights gained from our heuristics are leveraged to propose NC-DCPR, a fully distributed protocol for NC-CPR. We conduct extensive simulation experiments under realistic network conditions. Our results show that employing network coding significantly improves the efficiency of CPR.

Online social networking sites such as Facebook and MySpace have become increasingly popular, with close to 500 million users as of August 2008. The introduction of the Facebook Developer Platform and OpenSocial allows third-party developers to launch their own applications for the existing massive user base. The viral growth of these social applications can potentially influence how content is produced and consumed in the future Internet.

This paper explores how to leverage IEEE802.11-based cooperative peer-to-peer repair (CPR) to enhance the reliability of wireless multimedia broadcasting. We first formulate the CPR problem and present an algorithm that assumes global state information to optimally schedule CPR transmissions. Based on insights gained from the optimal algorithm, we propose a fully distributed CPR (DCPR) protocol. Simulation results demonstrate that the DCPR protocol can effectively enhance the reliability of wireless broadcast services with a repair latency comparable to that of optimal scheduling.

In label-switched networks such as MPLS, protection routing involves computing and setting up the backup paths at the same time when the primary paths are routed. It has previously been shown that two or more backup paths may share bandwidth along common links if such backup paths will never be activated simultaneously. Such sharing between the backup paths leads to reduced bandwidth reservations and, hence improved performance in terms of number of path requests that can be accommodated on the network (Aslam et al., 2005). We present a novel idea that backup paths may also share bandwidth with certain primary paths, thereby further reducing the overall bandwidth reservations on the network. This results in even more path requests being accommodated on the network. Sharing with primary paths is possible with any protection routing framework. To demonstrate this sharing, we use the NPP protection routing framework as an example (Aslam et al., 2005). We provide the enhancements to the NPP framework needed to exploit sharing with the primary paths. For the enhanced NPP framework, simulation results on various networks confirm that sharing with primary paths indeed results in better network utilization. This increased performance is achieved with bounded local state information and without requiring any additional routing or signaling overhead.

We investigate the problem of distributed online routing of bandwidth guaranteed paths with local restoration. A unified model is proposed that captures the bandwidth sharing characteristic of backup paths that provision local restoration, corresponding to different fault models. We apply the model to describe bandwidth sharing on backup paths for varying degrees of network state information. The extent of backup bandwidth sharing depends on the amount of network state information made available through routing protocols. A key design criterion for traffic engineering schemes is to maximize the sharing between backup paths, while minimizing this protocol overhead. M.S. Kodialam and T.V. Lakshman (see Proc. Infocom, p.376-85, 2001) demonstrated that propagating a constant amount of aggregated information per link leads to cost effective bandwidth sharing. We propose oAIS, a new aggregate information scenario, in which we judiciously select the propagated information, such that the protocol overhead is identical to that of Kodialam and Lakshman. Simulations show that oAIS outperforms other information scenarios with comparable protocol overheads.

We present AMOR, a new scheme for on-demand routing in wireless ad hoc networks. In ad hoc networks, mobile nodes are connected to each other such that the connection pattern changes dynamically with the mobility of nodes. Therefore, classical table driven routing algorithms necessitate updated network state information to be periodically disseminated, and incur significant costs in terms of network utilization, memory, and associated update-processing. In contrast, on-demand routing algorithms do not maintain pre-computed routes and real time route discovery ensues when data traffic needs to be transmitted between a source-destination pair. AMOR employs a modified version of the Dynamic Source Routing protocol to discover multiple node-disjoint paths between a source-destination pair. A key feature of AMOR is that instead of computing minimum-hop paths, it computes paths such that a measure of the 'transmission reliability', namely ETX, between the source-destination pair is optimized. Furthermore, AMOR employs a real time loading algorithm that optimally load balances traffic across multiple paths. The control traffic overhead in AMOR is comparable to that of single-path on-demand protocols. We present analytical throughput results in a simplified AMOR model of a network of multi-radio nodes. We also conduct simulation experiments to study the throughput performance of the AMOR scheme in a network of single-radio nodes. Our results show that AMOR outperforms the traditional dynamic source routing algorithm.