This work addresses the problem of delay-sensitive job scheduling in cloud computing systems that offer two compute options: (i) low-cost, high-demand spot servers and (ii) high-cost on-demand servers. While prior research has focused on scheduling a single job, we consider a more practical scenario where a continuous stream of jobs, categorized into n different classes, must be managed. Each class i is characterized by an on-demand cost ki, an arrival rate λi, and an average delay constraint δi. With Poisson job arrivals and spot server availability modeled as an exponential service process, we optimize two key aspects: (i) the wait-time distribution for each job class and (ii) the precedence order for processing classes in case of scheduling conflicts. By modeling the system as a Markov chain, we formulate constrained optimization problems for two cases: (i) equal treatment of all job classes and (ii) priority-based scheduling, the latter introducing a combinatorial challenge. We propose algorithms to determine optimal wait-time distributions in both cases and demonstrate through numerical experiments that precedence-order optimization significantly improves performance, especially when delay constraints are not overly strict.

Motivated by important industrial automation use cases, such as closed loop motion control and autonomous mobile robots, we study wait-free scheduling of periodic flows with stringent delay and jitter requirements in time sensitive networks. The goal is to assign initial transmission time-slots to periodic flows so that network queuing delays are eliminated or are very small. We make use of Bézour's Identity to develop simple and fast scheduling algorithms for this NP-hard problem. Operating in an online mode, our algorithms can quickly allocate contention free start time-slots to new flows, without changing allocations of already scheduled flows. Our main results are greedy and random scheduling algorithms that can trade speed for solution quality. Our simulations on different network topologies show that these algorithms are computationally efficient and can easily schedule a large number of flows, thus meeting the requirements of many industrial automation use cases.

Segment Routing is a proposed IETF protocol to improve traffic engineering and online route selection in IP networks. The key idea in segment routing is to break up the routing path into segments in order to enable better network utilization. Segment routing also enables finer control of the routing paths and can be used to route traffic through middle boxes. This paper considers the problem of determining the optimal parameters for segment routing in the offline and online cases. We develop a traffic matrix oblivious algorithm for robust segment routing in the offline case and a competitive algorithm for online segment routing. We also show that both these algorithms work well in practice.

The rapid growth in multimedia traffic is straining mobile networks thus necessitating the need for efficient content delivery mechanisms. In this paper we present the design and analysis of a scheme for streaming non-live, pre-recorded content (e.g. Video on Demand) that opportunistically takes advantage of the “slow fading” variations in the wireless link quality. The proposed scheme works by selectively sending more content to sessions at times when they have better link quality while providing sufficient rate guarantees to keep their buffers from under-flowing. We establish analytically that the performance of such scheme is within two times that of any optimal scheme and that it results in throughput gains, per user and aggregate, that increase in proportion to the number of streaming users. Our performance evaluations indicate that by exploiting slow time-varying channels the streaming capacity can more than double with significant benefits to the users at the edge of the cell.

The consumer interest in mobile multimedia content is on the rise, driven by the higher bandwidth of 3G networks and by the availability of low-cost high-resolution mobile devices. However, providing a good user experience remains a challenge due to bandwidth bottlenecks at peak time, channel quality variations and high battery drain incurred by long data transmission times at lower bandwidths. Consequently high jitter, buffering delays and frequent network outages are ever so common for mobile multimedia services. The emerging mobile broadcast networks (e.g. BCMCS, MediaFLO, DVB-H) are well suited for efficient delivery of highly popular content but lack the on-demand, interactive and retransmission (for reliability) capabilities by virtue of being one-way. In addition, due to business reasons (e.g. MediaFLO) or technical reasons (e.g. BCMCS) service providers prefer to deliver only a limited number of popular channels over these networks. In this paper we propose a mobile content delivery architecture that takes wireless specifics into account to enhance the user experience with multimedia services. Our solution makes efficient use of the available bandwidth, does network and channel quality- aware content delivery on the unicast 3G network while at the same time efficiently and reliably schedules content delivery over the mobile broadcast network. In our solution the delivered content is pre-cached on the storage available on the mobile device. This provides a better user experience, reduces the peak load on the network, and reduces the battery drain on the mobile device. Motivated by the proposed architecture we study the problem of scheduling content over a hybrid unicast and broadcast mobile network and design efficient algorithms and heuristics for the problem.

Power efficient operation is very critical in energy constrained multi-hop wireless networks. One important technique is to intelligently assign transmission powers to nodes while maintaining network connectivity. Previous work has focused on assigning a single transmission power to each node. This often leads to "power imbalance", where some nodes use much more power than other nodes. This can reduce network lifetime. In this paper, we investigate the problem of two power assignments where nodes alternate the use of these assigned powers. We rigorously formulate the problem of two power assignment under the constraint that the network connectivity is maintained. The objective here is to minimize the maximum average power used by the nodes. We show that, in general, the problem is not just NP-hard but also hard to approximate. We then propose a distributed localized heuristic to compute the two power assignments. We perform extensive simulations to show that the algorithm can reduce the average power significantly when compared with algorithms that assign a single power. By assuming some properties on radio propagation, we also present a centralized algorithm with bounded worst case guarantees for the two power assignment problem.

Multiple input multiple output (MIMO) antennas use sophisticated physical layer techniques to provide significant benefits over conventional antenna technology. Multiple independent data streams can be sent over the MIMO antenna elements. MIMO link can also suppress interference from neighboring links as long as the total useful streams and interfering streams are no greater than the number of receiving antenna elements. For these reasons MIMO antennas are increasingly being considered for use in interference limited wireless mesh networks and have been adopted by WLAN and WIMAX standards. However, the benefits of the MIMO technology in improving network performance are limited unless the higher layer protocols also exploit these capabilities. In this paper we are interested in characterizing the benefits of cross-layer optimizations in interference limited wireless mesh networks with MIMO links. We formulate a framework where data routing at the protocol layer, link scheduling at the MAC layer and stream control at the physical layer can be jointly optimized for throughput maximization in the presence of interference. We then develop an efficient algorithm to solve the resulting throughput optimization problem subject to fairness constraints.

Network QoS is essential for supporting real time interactive services such as VoIP. In the differentiated services framework QoS is provided by marking packets to receive preferential forwarding treatment, at each network node. This per hop forwarding treatment at each node may however be ineffective in providing the delay and jitter guarantees unless bounds are also imposed on the number of hops in the service routing paths. Interactive services also require minimal interruptions from network disruptions. Routing on hop limited paths may however have an adverse impact on the proportion of network capacity dedicated for protection to guarantee recovery from failures. In this paper we analyze this tradeoff in the context of MPLS fast reroute when protection capacities are pre-provisioned. We show that the underlying optimization problem is NP hard. We design almost best possible approximation algorithms for the problem and show that they work well in practice as well.

We consider the problem of joint routing, scheduling and transmission power assignment in multi-hop wireless mesh networks with unknown traffic. We assume the traffic is unknown, but the traffic matrix, which specifies the traffic load between every source-destination pair in the network, always lies inside a polytope defined by hose model constraints. The objective is to minimize the maximum of the total transmission power in the network over all traffic matrices in a given polytope. We propose efficient algorithms that compute a two-phase routing, schedule and power assignment, and prove the solution to be 3-approximation with respect to an optimal two-phase routing, scheduling and power assignment. We show via extensive simulations that the proposed algorithm has good performance at its worst operating traffic compared to an algorithm optimized for that traffic.

We study algorithmic problems that are motivated by bandwidth trading in next-generation networks. Typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed level of service for a specified time interval. The buyers (e.g., bandwidth brokers) are looking to procure bandwidth pipes to satisfy the reservation requests of end-users (e.g., Internet subscribers). Depending on what is available in the bandwidth exchange, the goal of a buyer is to either spend the least amount of money so as to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied.

Multihop infrastructure wireless mesh networks offer increased reliability, coverage, and reduced equipment costs over their single-hop counterpart, wireless local area networks. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network, and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds

In third generation (3G) wireless data networks, multicast throughput decreases with the increase in multicast group size, since a conservative strategy for the base station is to use the lowest data rate of all the receivers so that the receiver with the worst downlink channel condition can decode the transmission correctly. This paper proposes ICAM, integrated cellular and ad hoc multicast, to increase 3G multicast throughput through opportunistic use of ad hoc relays. In ICAM, a 3G base station delivers packets to proxy mobile devices with better 3G channel quality. The proxy then forwards the packets to the receivers through an IEEE 802.11-based ad hoc network. In this paper, we first propose a localized greedy algorithm that discovers for each multicast receiver the proxy with the highest 3G downlink channel rate. We discover that due to capacity limitations and interference of the ad hoc relay network, maximizing the 3G downlink data rate of each multicast receiver's proxy does not lead to maximum throughput for the multicast group. We then show that the optimal ICAM problem is NP-hard, and derive a polynomial-time 4-approximation algorithm for the construction of the multicast forest. This bound holds when the underlying wireless MAC supports broadcast or unicast, single rate or multiple rates (4(1 + /spl isin/) approximation scheme for the latter), and even when there are multiple simultaneous multicast sessions. Through both analysis and simulations, we show that our algorithms achieve throughput gains up to 840 percent for 3G downlink multicast with modest overhead on the 3G uplink.

An important feature of MPLS networks is local restoration where detour paths are set-up a priori. The detour is such that failed links or nodes can be bypassed locally from the first node that is upstream from the failures. This local bypass activation from the first detection point for failures permits much faster recovery than end-to-end path based mechanisms that require failure information to propagate to the network edges. However, local restoration of bandwidth guaranteed connections can be expensive in the additional network capacity needed. Hence, it is important to minimize and share restoration capacity. The problem of routing with local restoration requirements has been studied previously in a dynamic on-line setting. However, there are no satisfactory algorithms for the problem of pre-provisioning fast restorable connections when the aggregate traffic demands are known (as would be the case when a set of routers are to be interconnected over an optical network or for pre-provisioned ATM over MPLS overlays). The contribution of this paper is a fast combinatorial approximation algorithm for maximizing throughput when the routed traffic is required to be locally restorable. To the best of our knowledge, this is the first combinatorial algorithm for the problem with a performance guarantee. Our algorithm is a fully polynomial time approximation scheme (FPTAS), i.e., for any given /spl epsi/>0, it guarantees (1+/spl epsi/)-factor closeness to the optimal solution, and runs in time polynomial in the network size and 1//spl epsi/. We compare the throughput of locally restorable routing with that of unprotected routing and 1+1-dedicated path protection on representative ISP topologies.

Multi-hop infrastructure wireless mesh networks offer increased reliability, coverage and reduced equipment costs over their single-hop counterpart, wireless LANs. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds.

In this paper, we consider the multicast throughput optimization problem in multi-hop wireless networks. Given a source, and a set of receivers, we would like to find the set of multicast trees and a schedule such that the rate that the source can multicast to the receivers is maximized. We consider two transmission models: broadcast and unicast. In the broadcast model, a transmission is received by multiple downstream nodes in a multicast tree. In the unicast model, a separate transmission has to be sent to each downstream node. We consider the fundamental constraint that a node can not be involved in multiple communications at the same time. We consider two multicast models: a single multicast tree per session and multiple multicast tree per session. In the single multicast tree case, (1) for the unicast model, we show that the problem is NP-hard and it is not approximable to a factor better than 1.5; we then give a 1.5-approximation algorithm if all links have the same data rate, a 5-approximation algorithm if all nodes have the same transmission power and a 24-approximation algorithm for a realistic heterogeneous ad hoc network where nodes can have different transmission power. (2) for the broadcast model, we show that the problem is NP-hard and it is not approximable to a factor better than 2; we then give a simple 2-approximation algorithm to find the multicast tree and the transmission schedule. In the multiple multicast tree case, (1) for the unicast model, we show that the problem is APX-hard, and give a 1.5Ρ-approximation where Ρ is the best approximation ratio of the minimal cost Steiner tree problem; (2) for the broadcast model, our results indicate that the problem is hard, may not be approximable within a factor better than log(n) where n is the number of multicast receivers. Our evaluation shows that the throughput achieved by our algorithms is much better than both the throughput achieved by using pruned shortest path tree and by using optimal unicast.

Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Lately there has been a tremendous increase in management traffic due to the growing complexity and size of the data networks and the services provisioned on them. Traffic engineering for management flows is essential for the smooth functioning of these networks to avoid congestion, which can result in loss of critical data such as billing records, network alarms, etc. As is the case with most intra-domain routing protocols, the management flows in many of these networks are routed on shortest paths connecting the NOC with the service provider's POPs (points of presence). This collection of paths thus forms a "confluent" tree rooted at the gateway router connected to the NOC. The links close to the gateway router may form a bottleneck in this tree resulting in congestion. Typically this congestion is alleviated by adding layer two tunnels (virtual links) that offload the traffic from some links of this tree by routing it directly to the gateway router. The traffic engineering problem is then to minimize the number of virtual links needed for alleviating congestion. The traffic engineering problem described above also has applications to alleviating congestion resulting from focused overloads in VoIP networks and for dealing with congesting resulting from flash crowds in the world wide web.In this paper we formulate a traffic engineering problem motivated by the above mentioned applications. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which the underlying network is a tree, we design efficient algorithms. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general (non-tree) service provider network topologies.

Supporting fast restoration for general mesh topologies with minimal network over build is a technically challenging problem. Traditionally, ring based SONET networks have offered 50 ms restoration at the cost of requiring 100% over-build. Recently, fast (local) reroute has gained momentum in the context of MPLS networks. Fast reroute, when combined with preprovisioning of protection capacities and bypass tunnels, comes close to providing fast restoration for mesh networks. Preprovisioning has the additional advantage of greatly simplifying network routing and signaling. Thus even for protected connections, online routing can now be oblivious to the offered protection, and may only involve single shortest path computations. In this paper we are interested in the problem of reserving the least amount of the network capacity for protection, while guaranteeing fast restoration to all the supported connections. We show that the problem is NP-complete, and we present efficient approximation algorithms for the problem. These guarantees are provided even when the protection is for multiple link failures. In addition, the total amount of protection capacity reserved by these algorithms is just a small fraction of the amount reserved by existing ring-based schemes (e.g. SONET), especially on dense networks. The presented algorithms are computationally efficient, and can even be implemented on the network elements. Our simulation on some standard core networks, show that our algorithms work well in practice as well.

We present a framework for providing fair service and supporting QoS requirements in IEEE 802.11 networks with multiple access-points (APs). These issues becomes critical as IEEE 802.11 wireless LAN are widely deployed in nationwide networks, linking tens of thousands of "hot-spots" for providing both real-time (voice) and non real-time (data) services to a large population of mobile users. However, both fairness and QoS guarantees cannot he supported in the current 802.11 standard. Our system, termed MiFi, relies on centralized coordination of the APs. During any given time of the "contention-free" period only a set of non-interfering APs is activated while the others are silenced. Moreover the amount of service granted to an AP is proportional to its load and the system's performance is optimized by employing efficient scheduling algorithms. We show that such a system can be implemented without requiring any modification of the underlying MAC protocol standard or the behavior of the mobile stations and it guarantees to overcome the hidden node and the overlapping cell problems. Our simulations establish that the system supports fairness and hence can provide QoS guarantees for real-time traffic, while maintaining a relative high till throughput.

With increasing interest in energy constrained multi-hop wireless networks (Bambos, N. et al., 1991), a fundamental problem is one of determining energy efficient communication strategies over these multi-hop networks. The simplest problem is one where a given source node wants to communicate with a given destination, with a given rate over a multi-hop wireless network, using minimum power. Here the power refers to the total amount of power consumed over the entire network in order to achieve this rate between the source and the destination. There are three decisions that have to be made (jointly) in order to minimize the power requirement. (1) The path(s) that the data has to take between the source and the destination. (Routing). (2) The power with each link transmission is done. (Power Control). (3) Depending on the interference or the MAC characteristics, the time slots in which specific link transmissions have to take place. (Scheduling). (4) To the best of our knowledge, ours is the first attempt to derive a performance guaranteed polynomial time approximation algorithm for jointly solving these three problems. We formulate the overall problem as an optimization problem with non-linear objective function and non-linear constraints. We then derive a polynomial time 3-approximation algorithm to solve this problem. We also present a simple version of the algorithm, with the same performance bound, which involves solving only shortest path problems and which is quite efficient in practice. Our approach readily extends to the case where there are multiple source-destination pairs that have to communicate simultaneously over the multi-hop network.

Multi-disk systems, coupled with declustering schemes, have been widely used in various applications to improve I/O performance by enabling parallel disk accesses. A declustering scheme determines how data blocks should be placed among multiple disks to maximize the parallelism. We focus on the problem of declustering grid-structured multidimensional data with the objective of reducing the response time for range queries. Because of the combinatorial nature of the problem, it is not computationally feasible to perform an exhaustive search for the best scheme for large values of $M$ (the number of disks). In this paper, we present an efficient technique for building good-performance declustering schemes for large values of $M$, based on known good declustering schemes for small values of $M$. We analyze the performance of the declustering schemes generated by this hierarchical technique, giving tight bounds on their query response times. For example we show, in two dimensions, that using optimal declustering schemes for $M_1$ and $M_2$ disks we can construct a scheme for $M_1\times M_2$ disks whose response time, expressed in terms of the maximum number of data blocks to be retrieved from any of the disks, is at most five more than the optimal response time. Our technique generalizes to any value of $M$ in two dimensions and selected values of $M$ in higher dimensions. We also present simulation results to show the effectiveness of these schemes in practice.

This work is motivated by the problem of placing pressure-meters in fluid networks. The problem is formally defined in graph-theoretic terms as follows. Given a graph, find a cotree (complement of a tree) incident upon the minimum number of vertices. We show that this problem is NP-hard and MAX SNP-hard. We design an algorithm with an approximation factor of $2 + \epsilon$ for this problem for any fixed $\epsilon >0$. This approximation bound comes from the analysis of a local search heuristic, a common practical optimization technique that does not often allow formal worst-case analysis. The algorithm is made very efficient by finding restrictive definitions of the local neighborhoods to be searched. We also exhibit a polynomial time approximation scheme for this problem when the input is restricted to planar graphs.

We propose a new declustering scheme for allocating uniform multidimensional data among parallel disks. The scheme, aimed at reducing disk access time for range queries, is based on Golden Ratio Sequences for two dimensions and Kronecker Sequences for higher dimensions. Using exhaustive simulation, we show that, in two dimensions, the worst-case (additive) deviation of the scheme from the optimal response time for any range query is one when the number of disks (M) is at most 22; its worst-case deviation is two when M /spl les/ 94; and its worst-case deviation is four when M /spl les/ 550. In two dimensions, we prove that whenever M is a Fibonacci number, the average performance of the scheme is within 14 percent of the (generally, unachievable) strictly optimal scheme and its worst-case response time is within a multiplicative factor three of the optimal response time for any query, and within a factor 1.5 of the optimal for large queries. We also present comprehensive simulation results, on two-dimensional as well as on higher-dimensional data, that compare and demonstrate the advantages of our scheme over some recently proposed schemes in the literature.

Declustering schemes enable parallel data retrieval by placing data blocks across multiple disk devices. Various declustering schemes have been proposed for multidimensional data to reduce the response time of range queries. However, efficient schemes, which must be easy to compute and provide good performance, are only known for a restricted number of disks and dimensions. In this paper, we propose a novel technique to construct efficient multidimensional declustering schemes, for any number of disks and dimensions. Simulation results show that the new schemes outperform the best previously-known non-exhaustive search-based multidimensional declustering schemes.

We propose a new data declustering scheme for range queries. Our scheme is based on Golden Ratio Sequences (GRS), which have found applications in broadcast disks, hashing, packet routing, etc. We show by analysis and simulation that GRS is nearly the best possible scheme for 2-dimensional range queries. Specifically, it is the best possible scheme when the number of disks (M) is at most 22; has response time at most one more than that of the best possible scheme for M/spl les/94; and has response time at most three more than that of the best possible scheme for M/spl les/550. We also show that it outperforms the cyclic declustering scheme-a recently proposed scheme that was shown to have better performance than previously known schemes for this problem. We give some analytical results to suggest that the average performance of our scheme is within 14 percent of the optimal scheme. Our analytical results also suggest a worst case response time within a factor 3 of the optimal for any query, and within a factor 1.5 of the optimal for large queries. We also give a multidimensional extension of our scheme, which has better performance than the multidimensional generalization of the cyclic declustering scheme.

Policies are increasingly being used to manage complex communication networks. In this paper we present our work on a "policy server" which is being used to provide centralized administration of packet voice gateways and "soft switches" in next generation circuit and packet telephony networks. The policies running in the policy server are specified using a domain independent policy description language (PDL). This paper is motivated by the problem of evaluating policies specified in PDL. We present an algorithm for evaluating policies and study both its theoretical and empirical behavior. We show that the problem of evaluating policies is quite intractable. However we note that the hard instances of the policy evaluation problem are quite rare in real world networks. Under some very realistic assumptions we are able to show that our policy evaluation algorithm is quite efficient and is well suited for enforcing policies in complex networks. These results constitute the first attempt to develop a formal framework to study the informal concepts of policy based network management.

The full-degree spanning tree problem is defined as follows: Given a connected graph G = (V, E), find a spanning tree T to maximize the number of vertices whose degree in T is the same as G (are called vertices of “full” degree). This problem is NP-hard. We present almost-optimal approximation algorithms for it assuming that coR ≠ NP. For the case of general graphs, our approximation factor is . Using Håstad's result on the hardness of an approximating clique, we can show that if there is a polynomial time approximation algorithm for our problem with a factor of O(n1/2−ϵ) then coR = NP. Additionally, we present two algorithms for optimally solving small instances of the general problem and experimental results comparing our algorithm to the optimal solution and the previous heuristic used for this problem. © 2000 John Wiley & Sons, Inc.

In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines, query optimization in databases, and in other artificial intelligence applications. We give the first non-trivial approximation algorithm for this problem. We also prove non-trivial lower bounds on best possible approximation ratios for these problems. These improve on the non-approximability results that are implied by the non-approximability results for the shortest common supersequence problem. We use the same algorithmic technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines, and for the weighted shortest common supersequence problem.