Intelligent Transportation Systems (ITS) demand real-time collision prediction to ensure road safety and reduce accident severity. Conventional approaches rely on transmitting raw video or high-dimensional sensory data from roadside units (RSUs) to vehicles, which is impractical under vehicular communication bandwidth and latency constraints. In this work, we propose a semantic V2X framework in which RSU-mounted cameras generate spatiotemporal semantic embeddings of future frames using the Video Joint Embedding Predictive Architecture (V-JEPA). To evaluate the system, we construct a digital twin of an urban traffic environment enabling the generation of d verse traffic scenarios with both safe and collision events. These embeddings of the future frame, extracted from V-JEPA, capture task-relevant traffic dynamics and are transmitted via V2X links to vehicles, where a lightweight attentive probe and classifier decode them to predict imminent collisions. By transmitting only semantic embeddings instead of raw frames, the proposed system significantly reduces communication overhead while maintaining predictive accuracy. Experimental results demonstrate that the framework with an appropriate processing method achieves a 10% F1-score improvement for collision prediction while reducing transmission requirements by four orders of magnitude compared to raw video. This validates the potential of semantic V2X communication to enable cooperative, real-time collision prediction in ITS.

Industry 5.0 envisions a cyber-physical future where humans and robots collaborate harmoniously, empowered by 6G connectivity and intelligent automation. Central to this vision is the ability to autonomously configure complex production pipelines based on diverse and evolving human intents. Existing orchestration technologies exhibit critical shortcomings in terms of self-learning, validation, error diagnosis, and rectification capabilities. To this end, we propose an Agentic AI orchestration framework that interprets human intents and dynamically assembles optimal technology pipelines using a self-improving, retrieval-augmented Large Language Model (LLM) and a Bayesian contextual-bandit selector. This enables dynamic adaptation in unpredictable factory environments. Our solution is validated in a cyber-physical testbed integrating Digital Twins (DTs), distributed AI, robotics, and real-world network infrastructure. Compared to baseline LLMs, our system reduces orchestration iterations by over 94% for a given intent and by around 90% for an unseen intent, showing rapid convergence and strong generalization. Real-world deployments mirror DT results, confirming both the fidelity of the simulation and the practical value of intent-driven orchestration for human-centric manufacturing.

We consider a multi-user hybrid beamforming system, where the multiplexing gain is limited by the small number of RF chains employed at the base station (BS). To allow greater freedom for maximizing the multiplexing gain, it is better if the BS selects and serves some of the users at each scheduling instant, rather than serving all the users all the time. We adopt a two-timescale protocol that takes into account the mmWave characteristics, where at the long timescale an analog beam is chosen for each user, and at the short timescale users are selected for transmission based on the chosen analog beams. The goal of the user selection is to maximize the traditional Proportional Fair (PF) metric. However, this maximization is non-trivial due to interference between the analog beams for selected users. We first define a greedy algorithm and a “top-k” algorithm, and then propose a machine learning (ML)-based user selection algorithm to provide an efficient trade-off between the PF performance and the computation time. Through simulations, we analyze the performance of the ML-based algorithm under various metrics, and show that it gives an efficient trade-off in performance as compared to counterparts.

We study the training performance of ROS local planners based on Reinforcement Learning (RL), and the trajectories they produce on real-world robots. We show that recent enhancements to the Soft Actor Critic (SAC) algorithm such as RAD and DrQ achieve almost perfect training after only 10000 episodes. We also observe that on real-world robots the resulting SACPlanner is more reactive to obstacles than traditional ROS local planners such as DWA.

The standard beam management procedure in 5G requires the user equipment (UE) to periodically measure the received signal reference power (RSRP) on each of a set of beams proposed by the basestation (BS). It is prohibitively expensive to measure the RSRP on all beams and so the BS should propose a beamset that is large enough to allow a high-RSRP beam to be identified, but small enough to prevent excessive reporting overhead. Moreover, the beamset should evolve over time according to UE mobility. We address this fundamental performance/overhead trade-off via a Bayesian optimization technique that requires no or little training on historical data and is rooted on a low complexity algorithm for the beamset choice with theoretical guarantees. We show the benefits of our approach on 3GPP compliant simulation scenarios.

A Network Inventory Manager (NIM) is a software solution that scans, processes and records data about all devices in a network. We consider the problem faced by a NIM that can send out a limited number of probes to track changes in a large, dynamic network. The underlying change rate for the Network Elements (NEs) is unknown and may be highly non-uniform. The NIM should concentrate its probe budget on the NEs that change most frequently with the ultimate goal of minimizing the weighted Fraction of Stale Time (wFOST) of the inventory. However, the NIM cannot discover the change rate of a NE unless the NE is repeatedly probed.We develop and analyze two algorithms based on Reinforcement Learning to solve this exploration-vs-exploitation problem. The first is motivated by the Thompson Sampling method and the second is derived from the Robbins-Monro stochastic learning paradigm. We show that for a fixed probe budget, both of these algorithms produce a potentially unbounded improvement in terms of wFOST compared to the baseline algorithm that divides the probe budget equally between all NEs. Our simulations of practical scenarios show optimal performance in minimizing wFOST while discovering the change rate of the NEs.

Network slicing provides a key functionality in emerging 5G networks, and offers flexibility in creating customized virtual networks and supporting different services on a common physical infrastructure. This capability critically relies on a MAC scheduler to deliver performance targets in terms of aggregate rates or resource shares for the various slices. A crucial challenge is to enforce such guarantees and performance isolation while allowing flexible sharing to avoid resource fragmentation and fully harness channel variations. In the present paper we propose a MAC scheduler which meets these objectives and preserves the basic structure of utility-based schedulers such as the Proportional Fair algorithm in terms of per-user scheduling metrics. Specifically, the proposed scheme involves counters tracking the aggregate rate or resource allocations for the various slices against pre-specified targets, and computes offsets to the scheduling metrics accordingly. This design provides transparency with respect to other scheduling modules, such as link adaptation and beam-forming. We analytically establish that the proposed scheme achieves optimal overall throughput utility subject to the various slicing constraints. In addition, extensive 3GPP-compliant simulation experiments are conducted to assess the impact on best-effort applications and demonstrate substantial gains in overall throughput utility over baseline approaches.

We consider a virtualized RAN architecture for 5G networks where the Remote Units are connected to a central unit via a mid-haul. To support high data rates, the mid-haul is realized with a Passive Optical Network (PON). In this architecture, the data are stored at the central unit until the scheduler decides to transmit it through the mid-haul to an appropriate remote unit, and then over the air at the same slot. We study an optimal scheduling problem that arises in this context. This problem has two key features. First, multiple cells must be scheduled simultaneously for efficient operation. Second, the interplay between the time-varying wireless interface rates and the fixed capacity PON needs to be handled efficiently. In this paper, we take a comprehensive look at this resource allocation problem by formulating it as a utility-maximization problem. Using combinatorial techniques, we derive useful structural properties of the optimal allocation and utilize these results to design polynomial-time approximation algorithms and a pseudo- polynomial-time optimal algorithm. Finally, we numerically compare the performance of the proposed algorithms to heuristics which are natural generalizations of the ubiquitous Proportional Fair algorithm.

As the U.S. mobile data market matures, Internet service providers (ISPs) generally charge their users with some variation on a quota-based data plan with overage charges. Common variants include unlimited, prepaid, and usage-based data plans. However, despite a recent flurry of research on optimizing mobile data pricing, few works have considered how these data plans affect users' consumption behavior. In particular, while users with such plans have a strong incentive to plan their usage over the month, they also face uncertainty in their future data usage needs that would make such planning difficult. In this work, we develop a dynamic programming model of users' consumption decisions over the month that takes this uncertainty into account. We use this model to quantify which types of users would benefit from different types of data plans, using these conditions to extrapolate the optimal types of data plans that ISPs should offer. Our theoretical findings are complemented by numerical simulations on a dataset of user usage from a large U.S. ISP. The results help mobile users to choose data plans that maximize their utilities and ISPs to gain profit by understanding their user behavior while choosing what data plans to offer.

We compare the performance of heterogeneous networks (HetNets) with self backhauled small cells (SBSCs) relative to those with wired backhaul based small cells (WBSCs). The comparisons are made for a variety of SBSC based HetNets including: 1) when the HetNets employ omni antennas at the SBSCs and Uniform PF at the macro; 2) with directional antennas at the SBSCs and uniform PF at the macro; 3) with directional antennas at the SBSCs and weighted PF at the macro; and 4) with Directional antennas at the SBSCs and QoS-aware PF at the macro. The study catalogs our learning experiences with SBSC HetNets, leading the reader through the sequence of enhancements made to improve the performance of SBSC HetNets relative to WBSC HetNets.

We study the problem faced by a wireless service provider (SP) when offering a “sponsored content” service to multiple content providers (CPs). Each CP specifies the value that it would obtain from additional content views together with estimates on the underlying demand for its content. The SP then determines which CPs should sponsor their content along with the price for doing so. This basic framework has been studied in a variety of different contexts in recent years. However, previous work typically assumes that the CP parameters are reported truthfully to the SP. Another common assumption is that each CP has an independent traffic stream, i.e. there is no notion of competition between CPs in similar markets. In this work we address both of these issues. We present a pricing scheme that optimizes SP profit subject to CPs being incentivized to reveal their valuation and number of potential views in a truthful manner. We also examine how the model is affected if CPs in the same market are vying to sponsor a common pool of content.

We consider a time-based model for quota trading in mobile data networks. In particular we present a dynamic program to characterize the behavior of mobile users when they have the option to trade data with other users during the month. The user will decide how much data to consume at each time period based on the utility that can be gained, the amount of quota remaining and the price available for trading. In contrast to past work on quota trading, our model explicitly takes into account the time remaining in the billing period when users make trading decisions. In addition, we utilize a VCG-based trading strategy to ensure that users truthfully reveal the value they assign to traded data. We present two variants of the model that differ based on how much foresight users are assumed to have with respect to future prices. We use our model of quota dynamics to estimate the gain in user utility when quota trading is introduced. This in turn translates into an increased price that the operator can charge for each level of quota. We also compare the utility benefits of quota trading with an alternative scheme in which the users buy and sell additional data from the operator rather than the other users.

We consider the problem of managing the sharing of data among multiple users in a mobile shared data plan. Such plans allow for quota to be shifted from a user with only small requests in a given month to a user with larger requests. However, in the long run we wish for this sharing to be done in a fair manner. We begin with an intra-month problem in which requests arrive online during a single month and we wish to maximize fairness by the end of the month. For this case we describe an algorithm for which each user receives at least an I/O (log n) fraction of its optimal allocation and we also present a matching lower bound. We next consider a month-by-month version of the problem in which each user has a single usage request for each month and we wish to allocate the group quota in a way that satisfies each request as much as possible while also achieving long-term fairness (as defined by a utility function). For stochastic requests we present an optimal algorithm derived from the theory of wireless scheduling. In contrast, for adversarial requests we show that for any algorithm there may be a user that only receives a 1/n fraction of its optimal allocation. We conclude with the combined problem in which the requests arrive online during the month but we wish to achieve fairness over a longer timescale. For this case we derive the subproblem that must be solved in each individual month and derive a dynamic programming based solution. Our simulations show that our approaches perform well compared to the optimal offline approach that knows the request sequences in advance.

Given a network, a set of demands, and a cost function $f(\cdot)$, the min-cost network design problem is to route all demands with the objective of minimizing $\sum_e f(\ell_e)$, where $\ell_e$ is the total traffic load under the routing. We focus on cost functions of the form $f(x)= \sigma + x^{\alpha}$ for $x > 0$, with $f(0) = 0$. For $\alpha \le 1$, $f(\cdot)$ is subadditive. This case corresponds to the well-studied buy-at-bulk network design problem and admits polylogarithmic approximation and hardness. In this paper, we focus on the less-studied scenario of $\alpha > 1$ with a positive start-up cost $\sigma > 0$. Now, the cost function $f(\cdot)$ is neither subadditive nor superadditive. It aims to model a range of computing and communication devices for which doubling processing speed more than doubles their power consumption. We begin by discussing why existing routing techniques such as randomized rounding and tree-metric embedding fail to generalize directly. We then present our main contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitated min-cost flow problem that we believe is interesting in its own right. Our approach for this problem builds upon the well-linked decomposition due to Chekuri, Khanna, and Shepherd [Proceedings of ACM STOC, ACM, New York, pp. 183--192], the construction of expanders via matchings due to Khandekar, Rao, and Vazirani [J. ACM, 56 (2009), 19], and edge-disjoint routing in well-connected graphs due to Rao and Zhou [SIAM J. Comput., 39 (2010), pp. 1856--1887]. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature.

A key problem in the control of packet-switched data networks is to schedule the data so that the queue sizes remain bounded over time. Scheduling policies have been developed in a number of different models that ensure network stability as long as no queue is inherently overloaded. However, this literature typically assumes that each server runs at a fixed maximum rate. Although this is optimal for clearing queue backlogs as fast as possible, it may be suboptimal in terms of energy consumption. Indeed, a lightly loaded server could operate at a lower rate, at least temporarily, to save energy. Within an energy-aware framework, a natural question is how stability and other performance measures such as delay are affected by the reduced processing rate of the servers. In this paper, we demonstrate the following results toward answering that question. Starting with the simplest case of a single server in isolation, we consider two types of rate adaptation policies that exhibit a tradeoff between queue size and energy usage. We also present a lower bound on the best such tradeoff that can possibly be achieved. Next, we study a general network environment and investigate the connectionless model for which connection paths can rapidly change over time. We propose a combination of the above rate adaptation policies with the standard Farthest-to-Go scheduling policy. This approach provides stability in the network setting while using an amount of energy that is within a bounded factor of the optimum.

In designing new service plans, network service providers need to understand how consumption of voice or data service will change in response to pricing signals. It is difficult to acquire such information from customer usage data because voice minutes and data bandwidth are typically sold in the form of large quotas. We address this issue by studying how end-users consume their quotas, both in a prepaid setting (where users pay in advance and refill as needed) and a postpaid setting (where users pay each month for a fixed amount of quota). Our presentation has three main parts. In the first we present data on quota usage for prepaid voice/text services and show that users reduce their voice usage when their balances become low. Moreover, when balances are low there is a tendency to shift from voice to SMS. In the second part, we provide descriptive models of both prepaid and postpaid services. The main feature of these models is that there is a background level of potential demand and the rate at which this potential demand is realized depends on the amount of quota balance available. In the third part, we propose utility maximizing models that can account for this type of behavior. In the prepaid case the main feature of the model is a discount function that represents the perceived cost to the user of a quota refill that will occur sometime in the future. In the postpaid case, where the end-user is attempting to get the maximum amount of utility from his monthly quota, we present a dynamic programming formulation in which utility functions are time varying and not known to the user in advance.

In this paper, we consider the Max-Weight protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process. Such an environment appears frequently in many practical wireless scenarios when the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper, we prove that even in the above adversarial setting, the Max-Weight protocol keeps the queues in the network stable (i.e., keeps the queue sizes bounded) whenever this is feasible by some routing and scheduling algorithm. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Our proof holds for any arbitrary interference relationships among edges. We also prove the same stability of ε-approximate Max-Weight under the adversarial model. We conclude the paper with a discussion of queue sizes in the adversarial model as well as a set of simulation results.

The interaction of a content provider with end users on an infrastructure platform built and maintained by a service provider can be viewed as a two-sided market. Content sponsoring, i.e., charging the content provider instead of viewers for resources consumed in viewing the content, can benefit all parties involved. Without being charged directly or having it counted against their monthly data quotas, end users will view more content, allowing the content provider to generate more advertising revenue, extracted by the service provider to subsidize its investment and operation of the network infrastructure. However, realizing such gains requires a proper contractual relationship between the service provider and content provider. We consider the determination of this contract through a Stackelberg game. The service provider sets a pricing schedule for sponsoring and the content provider responds by deciding how much content to sponsor. We analyze the best strategies for the content provider and service provider in the event that the underlying demand for the content is uncertain. Two separate settings are defined. In the first, end users can be charged for non-sponsored views on a per-byte basis. In the second we extend the model to the more common case in which end users purchase data quotas on a periodic basis. Our main conclusion is that a coordinating contract can be designed that maximizes total system profit. Moreover, the additional profit due to sponsoring can be split between the content provider and service provider in an arbitrary manner.

Good clustering can provide critical insight into potential locations where congestion in a network may occur. A natural measure of congestion for a collection of nodes in a graph is its Cheeger ratio, defined as the ratio of the size of its boundary to its volume. Spectral methods provide effective means to estimate the smallest Cheeger ratio via the spectral gap of the graph Laplacian. Here, we compute the spectral gap of the truncated graph Laplacian, with the so-called Dirichlet boundary condition, for the graphs of a dozen communication networks at the IP-layer, which are subgraphs of the much larger global IP-layer network. We show that i) the Dirichlet spectral gap of these networks is substantially larger than the standard spectral gap and is therefore a better indicator of the true expansion properties of the graph, ii) unlike the standard spectral gap, the Dirichlet spectral gaps of progressively larger subgraphs converge to that of the global network, thus allowing properties of the global network to be efficiently obtained from them, and (iii) the (first two) eigenvectors of the Dirichlet graph Laplacian can be used for spectral clustering with arguably better results than standard spectral clustering. We first demonstrate these results analytically for finite regular trees. We then perform spectral clustering on the IP-layer networks using Dirichlet eigenvectors and show that it yields cuts near the network core, thus creating genuine single-component clusters. This is much better than traditional spectral clustering where several disjoint fragments near the network periphery are liable to be misleadingly classified as a single cluster. Since congestion in communication networks is known to peak at the core due to large-scale curvature and geometry, identification of core congestion and its localization are important steps in analysis and improved engineering of networks. Thus, spectral clustering with Dirichlet boundary condition is seen to be more effective at finding bona-fide bottlenecks and congestion than standard spectral clustering.

Abstract Energy conservation is drawing increasing attention in data networking. As networks are designed for peak traffic, network elements typically operate at full speed and consume maximum power even when carrying low traffic. One school of thought believes that a dominant amount of power saving comes from turning off network elements. The difficulty is that transitioning between the active and sleeping modes consumes considerable energy and time. This results in an obvious trade‐off between saving energy and provisioning performance guarantees such as end‐to‐end delays. We study the following routing and scheduling problem in a network in which each network element either operates in the full‐rate active mode or the zero‐rate sleeping mode. For a given network and traffic matrix, routing determines the path that each traffic stream traverses. For frame‐based periodic scheduling, a schedule determines the active period per element within each frame and prioritizes packets within each active period. For a line topology, we present a schedule with close‐to‐minimum delay for a minimum active period per element. For an arbitrary topology, we partition the network into a collection of lines and use the near‐optimal schedule along each line. Additional delay is incurred only when a path switches from one line to another. By minimizing the number of switchings via routing, we show a logarithmic approximation for both power consumption and end‐to‐end delays. If routing is given as input, we present two schedules one of which has active period proportional to the traffic load per network element, and the other has active period proportional to the maximum load over all elements. The end‐to‐end delay of the latter is much improved compared to the delay for the former. This demonstrates the trade‐off between power and delay. Finally, we provide simulation results to validate our algorithmic approaches. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

In this paper we consider the MAX-WEIGHT protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process. Such an environment appears frequently in many practical wireless scenarios when the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper we prove that even in the above adversarial setting, the MAX-WEIGHT protocol keeps the queues in the network stable (i.e. keeps the queue sizes bounded) whenever this is feasible by some routing and scheduling algorithm. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Our proof holds for any arbitrary interference relationships among edges. We also prove the stability of ε-approximate MAX-WEIGHT under the adversarial model. We conclude the paper with a discussion of queue sizes in the adversarial model as well as a set of simulation results.

We study network optimization that considers power minimization as an objective. Studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. Most existing research on speed scaling focuses on a single network element in isolation. We aim for a network-wide optimization. Specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing power consumption. Optimizing the routes critically relies on the characteristic of the speed–power curve$f(s)$, which is how power is consumed as a function of the processing speed$s$. If$f$is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. This contrasts with the well-known logarithmic approximation for subadditive functions. However, for common speed–power curves such as polynomials$f(s) = \mu s^{\alpha}$, we are able to show a constant approximation via a simple scheme of randomized rounding. We also generalize this rounding approach to handle the case in which a nonzero startup cost$\sigma$appears in the speed–power curve, i.e.,$f(s) = \cases{0, & if $s=0$\cr \sigma + \mu s^{\alpha},& if $s>0$.}$We present an$O((\sigma /\mu)^{1/\alpha})$-approximation, and we discuss why coming up with an approximation ratio independent of the startup cost may be hard. Finally, we provide simulation results to validate our algorithmic approaches.

A key problem in the control of packet-switched data networks is to schedule the data so that the queue sizes remain bounded over time. Scheduling algorithms have been developed in a number of different models that ensure network stability as long as no queue is inherently overloaded. However, this literature typically assumes that each server runs at a fixed maximum speed. Although this is optimal for clearing queue backlogs as fast as possible, it may be suboptimal in terms of energy consumption. Indeed, a lightly loaded server could operate at a lower rate, at least temporarily, to save energy. Within an energy-aware framework, a natural question arises: "What is the minimum energy that is required to keep the network stable?" In this paper, we demonstrate the following results towards answering that question. Starting with the simplest case of a single server in isolation, we consider three types of rate adaptation policies: a heuristic policy, which sets server speed depending on queue size only, and two more complex ones that exhibit a tradeoff between queue size and energy usage. We also present a lower bound on the best such tradeoff that can possibly be achieved. Next, we study a general network environment and investigate two scenarios. In a temporary sessions scenario, where connection paths can rapidly change over time, we propose a combination of the above rate adaptation policies with the standard Farthest-to Go scheduling algorithm. This approach provides stability in the network setting, while using an amount of energy that is within a bounded factor of the optimum. In a permanent sessions scenario, where connection paths are fixed, we examine an analogue of the well-known Weighted Fair Queueing scheduling policy and show how delay bounds are affected under rate adaptation.

We introduce Capacitated Metric Labeling. As in Metric Labeling, we are given a weighted graph G = (V, E), a label set L, a semimetric dL on this label set, and an assignment cost function ϕ : V × L → ℜ+. The goal in Metric Labeling is to find an assignment f : V → L that minimizes a particular two-cost function. Here we add the additional restriction that each label ti receive at most li nodes, and we refer to this problem as Capacitated Metric Labeling. Allowing the problem to specify capacities on each label allows the problem to more faithfully represent the classification problems that Metric Labeling is intended to model. Our main positive result is a polynomial-time, O(log |V|)-approximation algorithm when the number of labels is fixed, which is the most natural parameter range for classification problems. We also prove that it is impossible to approximate the value of an instance of Capacitated Metric Labeling to within any finite factor, if P ≠ NP. Yet this does not address the more interesting question of how hard Capacitated Metric Labeling is to approximate when we are allowed to violate capacities. To study this question, we introduce the notion of the “congestion” of an instance of Capacitated Metric Labeling. We prove that (under certain complexity assumptions) there is no polynomial-time approximation algorithm that can approximate the congestion to within O((log|L|)1/2–ε) (for any ε > 0) and this implies as a corollary that any polynomial-time approximation algorithm that achieves a finite approximation ratio must multiplicatively violate the label capacities by Ω((log |L|)1/2–ε). We also give a O(log |L|)-approximation algorithm for congestion.

We consider the problem of scheduling multicarrier wireless data in systems such as IEEE 802.16 (WiMAX). Each scheduling decision involves assigning carriers to users for each time slot, subject to the constraint that each carrier is assigned to at most one user, but multiple carriers can potentially be assigned to the same user. One important aspect of our problem is that a scheduler knows the channel rates across all users and all carriers whenever a scheduling decision is made. This “global” information may give a potential for enhancing performance via an optimized allocation of carriers to users. We analyze this problem in a situation where finite queues are fed by a data arrival process. The well-known MaxWeight algorithm for the single-carrier setting maximizes the product of queue size and service rate. We focus on how to adapt MaxWeight to the multicarrier setting. If the same objective is pursued, more service than needed may be assigned to drain a queue, thereby creating wastage. While a simple variant in the objective forbids this wastage, it turns an easy-to-compute old objective into an intractable new objective. We state the hardness of the new optimization problems and propose several extremely simple algorithms with provable performance bounds. We conclude with supporting simulation examples.

We study the Edge-Disjoint Paths with Congestion (EDPwC) problem in undirected networks in which we must integrally route a set of demands without causing large congestion on an edge. We present a (polylog(n),poly(log log n))approximation, which means that if there exists a solution that routes X demands integrally on edge-disjoint paths (i.e. with congestion 1), then the approximation algorithm can route X/polylog(n) demands with congestion poly(log log n). The best previous result for this problem was a (n1/β,β)approximation for β <; log n.

Given a network, a set of demands and a cost function f(.), the min-cost network design problem is to route all demands with the objective of minimizing Σef(ℓe), where ℓeis the total traffic load under the routing. We focus on cost functions of the form f(x) = σ + xαfor x > 0, with f(0) = 0. For α ≤ 1 f(.) is subadditive and exhibits behavior consistent with economies of scale. This problem corresponds to the well-studied Buy-at-Bulk network design problem and admits polylogarithmic approximation and hardness. In this paper, we focus on the less studied scenario of α > 1 with a positive startup cost σ > 0. Now, the cost function f(.) is neither subadditive nor superadditive. This is motivated by minimizing network-wide energy consumption when supporting a set of traffic demands. It is commonly accepted that, for some computing and communication devices, doubling processing speed more than doubles the energy consumption. Hence, in Economics parlance, such a cost function reflects diseconomies of scale. We begin by discussing why existing routing techniques such as randomized rounding and tree-metric embedding fail to generalize directly. We then present our main contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitated min-cost flow problem that we believe is interesting in its own right. Our approach for this problem builds upon the well-linked decomposition due to Chekuri-Khanna-Shepherd, the construction of expanders via matchings due to KhandekarRao-Vazirani, and edge-disjoint routing in well-connected graphs due to Rao-Zhou. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature.

Energy conservation is drawing increasing attention in data networking. One school of thought believes that a dominant amount of energy saving comes from turning off network elements. The difficulty is that transitioning between the active and sleeping modes consumes considerable energy and time. This results in an obvious trade-off between saving energy and provisioning performance guarantees such as end-to-end delays. We study the following routing and scheduling problem in a network in which each network element either operates in the full-rate active mode or the zero-rate sleeping mode. For a given network and traffic matrix, routing determines the path along which each traffic stream traverses. For frame-based periodic scheduling, a schedule determines the active period per element within each frame and prioritizes packets within each active period. For a line topology, we present a schedule with close-to-minimum delay for a minimum active period per element. For an arbitrary topology, we partition the network into a collection of lines and utilize the near-optimal schedule along each line. Additional delay is incurred only when a path switches from one line to another. By minimizing the number of switchings via routing, we show a logarithmic approximation for both energy consumption and end-to-end delays. If routing is given as input, we present two schedules one of which has active period proportional to the traffic load per network element, and the other proportional to the maximum load over all elements. The end-to-end delay of the latter is much improved compared to the delay for the former. This demonstrates the trade-off between energy and delay.

We study network optimization that considers energy minimization as an objective. Studies have shown that mechanisms such as speed scaling can significantly reduce the power consumption of telecommunication networks by matching the consumption of each network element to the amount of processing required for its carried traffic. Most existing research on speed scaling focuses on a single network element in isolation. We aim for a network-wide optimization. Specifically, we study a routing problem with the objective of provisioning guaranteed speed/bandwidth for a given demand matrix while minimizing energy consumption. Optimizing the routes critically relies on the characteristic of the energy curve $f(s)$, which is how energy is consumed as a function of the processing speed $s$. If $f$ is superadditive, we show that there is no bounded approximation in general for integral routing, i.e., each traffic demand follows a single path. This contrasts with the well-known logarithmic approximation for subadditive functions. However, for common energy curves such as polynomials $f(s) = \mu s^{\alpha}$, we are able to show a constant approximation via a simple scheme of randomized ounding. The scenario is quite different when a non-zero tartup cost $\sigma$ ppears in the energy curve, e.g.\ $f(s) = \left\{ \begin{array}{ll} 0 & \mbox{ if } s=0\\sigma + \mu s^{\alpha}& \mbox{ if } s>0 \end{array}\right.$. For this case a constant approximation is no longer feasible. In fact, for any \alpha>1$, we show an $\Omega(\log^{\frac{1}{4}}N)$ hardness result under a common complexity assumption. Here $N$ is the size of the network.) On the positive side we present $O((\sigma/\mu)^{1/\alpha})$ and $O(K)$ approximations, where $K$ is the number of demands.

We study the end-to-end delay bounds that can be achieved in wireless networks using packet deadlines. We assume a set of flows in the network, for which flow i has burst parameter ¿i, injection rate ¿i, and path length Ki. It was already known that, in wireline networks, the Coordinated-Earliest-Deadline-First (CEDF) protocol can achieve and end-to-end delay of approximately (¿i/¿i)+Ki, whereas other schedulers such as Weighted Fair Queuing, have end-to-end delay bounds of the form (¿i+ Ki)/¿i. For the case of wireless networks of arbitrary topology, the focus has typically been more on throughput optimality than minimizing delay. In this paper, we study the delay bounds that can be achieved by combining wireless link scheduling algorithms with a CEDF packet scheduler. We first present a centralized scheduler that has an end-to-end delay of approximately O(¿/(¿i) + ¿¿¿piN/(r¿)), where r¿is the total rate of flows through link ¿, N is the number of links in the network, and piis the path followed by packets of flow i. We then show how to convert this into a distributed scheduler. We also study the extent to which results on the schedulability of packet deadlines can be carried over from the wireline to the wireless context. Lastly, we examine ways in which the theoretical schedulers considered in this paper can be transferred to a more practical random-access based setting. This work was supported by NSF contract CCF-0728980 and was performed while the first author was visiting Bell Labs in Summer, 2009.

In this paper we consider the problem of maximizing the number of supported connections in arbitrary wireless networks where a transmission is supported if and only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. The aim is to choose transmission powers for each connection so as to maximize the number of connections for which this threshold is met. We believe that analyzing this problem is important both in its own right and also because it arises as a subproblem in many other areas of wireless networking. We study both the complexity of the problem and also present some game theoretic results regarding capacity that is achieved by completely distributed algorithms. We also feel that this problem is intriguing since it involves both continuous aspects (i.e. choosing the transmission powers) as well as discrete aspects (i.e. which connections should be supported). Our results are: ldr We show that maximizing the number of supported connections is NP-hard, even when there is no background noise. This is in contrast to the problem of determining whether or not a given set of connections is feasible since that problem can be solved via linear programming. ldr We present a number of approximation algorithms for the problem. All of these approximation algorithms run in polynomial time and have an approximation ratio that is independent of the number of connections. ldr We examine a completely distributed algorithm and analyze it as a game in which a connection receives a positive payoff if it is successful and a negative payoff if it is unsuccessful while transmitting with nonzero power. We show that in this game there is not necessarily a pure Nash equilibrium but if such an equilibrium does exist the corresponding price of anarchy is independent of the number of connections. We also show that a mixed Nash equilibrium corresponds to a probabilistic transmission strategy and in this case such an equilibrium always exists and has a price of anarchy that is independent of the number of connections. This work was supported by NSF contract CCF-0728980 and was performed while the second author was visiting Bell Labs in Summer, 2008.

We consider a scheduling problem in which multiple servers are available to service multiple users in a time-slotted system. Each server has a time-dependent and user-dependent service rate for each user at each timeslot. A schedule specifies which server serves which user per timeslot, with a typical objective of maximizing the total rate that the users receive. The servers are numbered by a set of consecutive integers. A strict contiguity constraint enforces that each user is served by at most one contiguous interval of the servers. We show that a strict contiguity requirement makes the scheduling problem APX hard to solve, which means we cannot approximate an optimal schedule arbitrarily closely. On the positive side, we also offer two approximation algorithms, a simple one that guarantees a logarithmic approximation and a more complex one that guarantees a constant approximation. In addition, we also present a complete taxonomy of the scheduling variants that consider issues in the following dimensions, (i) Strict contiguity vs soft contiguity, where the latter allows multiple intervals of servers to serve the same user but imposes a penalty; (ii) Full buffer vs finite buffer, where the former assumes each user always has a large queue and for the latter the service a user receives is upper bounded by its queue size; (iii) slot-by-slot scheduling vs template scheduling, where the former creates a schedule for every timeslot and the latter creates a schedule for multiple timeslots at a time; (iv) Time-variant vs time-invariant service rates for template scheduling. For each variant, we present optimal algorithms if possible and approximation algorithms whenever NP-hardness prevails.

We show that for any r > 0, there is a network of First-In-First-Out servers and a fixed set of sessions such that: —The network load is r with respect to the permanent sessions model with bounded arrivals. —The network can be made unstable.

We study the problem of jointly performing scheduling and congestion control in mobile ad-hoc networks so that network queues remain bounded and the resulting flow rates satisfy an associated network utility maximization problem. In recent years a number of papers have presented theoretical solutions to this problem that are based on combining differential-backlog scheduling algorithms with utility-based congestion control. However, this work typically does not address a number of issues such as how signaling should be performed and how the new algorithms interact with other wireless protocols. In this paper we address such issues. In particular: ldr We define a specific network utility maximization problem that we believe is appropriate for mobile adhoc networks. ldr We describe a wireless greedy primal dual (wGPD) algorithm for combined congestion control and scheduling that aims to solve this problem. ldr We show how the wGPD algorithm and its associated signaling can be implemented in practice with minimal disruption to existing wireless protocols. ldr We show via OPNET simulation that wGPD significantly outperforms standard protocols such as 802.11 operating in conjunction with TCP. This work was supported by the DARPA CBMANET program.

We consider the problem of scheduling in a multi- hop packet network so as to satisfy a set of arbitrary end-to-end delay requirements. A number of scheduling protocols are known for which end-to-end delay bounds can be derived. However, it is often the case that these end-to-end delay bounds are large for flows with small rate. This is clearly inappropriate for traffic types such as VoIP for which tight delay bounds are required but session rates are typically small. In this paper we study the problem of satisfying an arbitrary set of end-to-delay requirements. For a single server in isolation, precise conditions on whether or not a set of delay requirements can be satisfied are known. In contrast, for sessions in a multihop network, we show that deciding whether or not a set of delay requirements can be met is NP-hard. However, if the delay requirements satisfy a simple set of per-server and per- session conditions necessary for schedulability, we show that our proposed protocol can meet all the requirements up to some logarithmic factor. On the negative side, we construct examples in which some delay bound must be violated by a logarithmic factor even if the necessary conditions hold. We further demonstrate through simulation the advantage of our protocol against a counterpart that does not take delay requirements into consideration. We conclude the paper by extending our results to the problem of satisfying arbitrary delay bounds in an input-queued switch.

We consider the problem of creating template-based schedules for multi-carrier frame-based wireless data systems such as 802.16 (Wimax). A template consists of an assignment of carriers to users over a fixed set of time slots. This schedule can then be repeated multiple times. The aim is to assign the (time slot, carrier) pairs to the users in such a way that the service to each user is as smooth as possible. This in turn ensures that the users experience low delay. A number of elegant template scheduling algorithms exist for the single-carrier case. However, the case of multi-carrier systems where the channel rates can be different on different carriers has received much less attention. We present a general framework for studying the delay performance of a multi-carrier template. We then describe a number of deterministic and randomized scheduling algorithms for template creation and study their delay performance via analysis and simulation. We also show that the delay bounds can sometimes be improved by randomly shifting the schedule on each carrier and by scheduling in a hierarchical manner.

Given a set of demands in a directed graph, the directed congestion minimization problem is to route every demand with the objective of minimizing the heaviest load over all edges. We show that for any constant ε > 0, there is no Ω(log 1−ε M )-approximation algorithm on networks of size M unless NP ⊆ ZPTIME ( n polylog n ). This bound is almost tight given the O (log M /log log M )-approximation via randomized rounding due to Raghavan and Thompson.

Recent research has demonstrated that by utilizing channel state information at the transmitter, the physical layer can be optimized to provide higher link capacity and throughput, more efficiently share the channel with multiple users, increase range by exploiting diversity due to spatial and frequency selectivity, and simplify multi-user receivers through known interference cancellation. Unfortunately, acquiring channel state information at the transmitter is difficult. In most systems, the only opportunity for the transmitter to learn about the channel is through a feedback control channel. Because feedback information is control overhead, the rate of the feedback channel is limited. This motivates the study of limited feedback techniques where only partial or quantized information from the receiver is conveyed back to the transmitter.

It is now well known that employing channel adaptive signaling in wireless communication systems can yield large improvements in almost any performance metric. Unfortunately, many kinds of channel adaptive techniques have been deemed impractical in the past because of the problem of obtaining channel knowledge at the transmitter. The transmitter in many systems (such as those using frequency division duplexing) can not leverage techniques such as training to obtain channel state information. Over the last few years, research has repeatedly shown that allowing the receiver to send a small number of information bits about the channel conditions to the transmitter can allow near optimal channel adaptation. These practical systems, which are commonly referred to as limited or finite-rate feedback systems, supply benefits nearly identical to unrealizable perfect transmitter channel knowledge systems when they are judiciously designed. In this tutorial, we provide a broad look at the field of limited feedback wireless communications. We review work in systems using various combinations of single antenna, multiple antenna, narrowband, broadband, single-user, and multiuser technology. We also provide a synopsis of the role of limited feedback in the standardization of next generation wireless systems.

We study the problem of routing traffic in the Internet with strict delay constraints. This problem arises in the context of routing delay-sensitive traffic such as Voice-over-IP. We consider a set of demands that can be routed along a candidate set of paths. Each demand must be split among its paths in such a way that the total delay experienced by any of the traffic is less than a fixed threshold. In this paper we analyze the complexity of the problem and also present experimental results for heuristics that can be implemented in practice. In contrast to some other recent work on network optimization, our problem has a combinatorial aspect since we only enforce the delay bound on paths that have non-zero traffic. Our main theoretical result is that this causes the problem to be computationally hard, even if we only wish to approximately meet the delay bounds. We also discuss the limitations of online algorithms.

We consider the problem of scheduling wireless data in systems such as 802.16 (WIMAX). Each scheduling decision involves constructing a frame of one or more time slots. Within each time slot multiple carriers must be assigned to users. The important aspect of our problem is that a scheduler knows the channel rates across all users and all carriers whenever a scheduling decision is made. Hence there is no need to treat each carrier in complete isolation. This gives a potential for enhancing performance by allocating multiple carriers simultaneously.

We study the stability of the max-weight protocol for combined routingand scheduling in communication networks. Previous work has shownthat this protocol is stable for adversarial multicommodity trafficin subcritically loaded static networks and for single-commoditytraffic in critically loaded dynamic networks. We show: The max-weight protocol is stable for adversarial multicommodity traffic in adversarial dynamic networks whenever the network is subcriticallyloaded. The max-weight protocol is stable for fixed multicommodity trafficin fixed networks even if the network is critically loaded.

We show that there is no $\gamma\log\log M/\log\log\log M$‐approximation for the undirected congestion minimization problem unless $NP \subseteq ZPTIME(n^{{\rm polylog} n})$, where M is the size of the graph and γ is some positive constant.

We study routing and scheduling in multihop wireless networks . When data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. The data transmission is node constrained , that is, every node can transmit data to at most one neighboring node per time step. The transmission rates are time varying as a result of changing wireless channel conditions. In this article, we assume that data arrivals and transmission rates are governed by an adversary . The power of the adversary is limited by an admissibility condition which forbids the adversary from overloading any wireless node a priori. The node-constrained transmission and time-varying nature of the transmission rates make our model different from and harder than the standard adversarial queueing model which relates to wireline networks. For the case in which the adversary specifies the paths that the data must follow, we design scheduling algorithms that ensure network stability. These algorithms try to give priority to the data that is closest to its source node. However, at each time step only a subset of the data queued at a node is eligible for scheduling. One of our algorithms is fully distributed . For the case in which the adversary does not dictate the data paths, we show how to route data so that the admissibility condition is satisfied. We can then schedule data along the chosen paths using our stable scheduling algorithms.

Abstract — We consider a set of flows passing through a set of servers. The injection rate into each flow is governed by a flow control that increases the injection rate when all the servers on the flow’s path are empty and decreases the injection rate when some server is congested. We show that if each server’s congestion is governed by the arriving traffic at the server then the system can oscillate. This is in contrast to previous work on flow control where congestion was modeled as a function of the flow injection rates and the system was shown to converge to a steady state that maximizes an overall network utility.

We study the complexity of a set of design problems for optical networks. Under wavelength division multiplexing (WDM) technology, demands sharing a common fiber are transported on distinct wavelengths. Multiple fibers may be deployed on a physical link. Our basic goal is to design networks of minimum cost, minimum congestion and maximum throughput. This translates to three variants in the design objectives: 1) MIN-SUMFIBER: minimizing the total cost of fibers deployed to carry all demands; 2) MIN-MAXFIBER: minimizing the maximum number of fibers per link to carry all demands; and 3) MAX-THROUGHPUT: maximizing the carried demands using a given set of fibers. We also have two variants in the design constraints: 1) CHOOSEROUTE: Here we need to specify both a routing path and a wavelength for each demand; 2) FIXEDROUTE: Here we are given demand routes and we need to specify wavelengths only. The FIXEDROUTE variant allows us to study wavelength assignment in isolation. Combining these variants, we have six design problems. Previously we have shown that general instances of the problems MIN-SUMFIBER-CHOOSEROUTE and MIN-MAXFIBER-FIXEDROUTE have no constant-approximation algorithms. In this paper, we prove that a similar statement holds for all four other problems. Our main result shows that MIN-SUMFIBER-FIXEDROUTE cannot be approximated within any constant factor unless NP-hard problems have efficient algorithms. This, together with the previous hardness result of MIN-MAXFIBER-FIXEDROUTE, shows that the problem of wavelength assignment is inherently hard by itself. We also study the complexity of problems that arise when multiple demands can be time-multiplexed onto a single wavelength (as in time-domain wavelength interleaved networking (TWIN) networks) and when wavelength converters can be placed along the path of a demand.

We show that for any constant ε > 0, there is no Ω(log1-εM)-approximation algorithm for the directed congestion minimization problem on networks of size M unless NP ⊆ ZPTIME(npolylog n). This bound is almost tight given the O(log M/ log log M)-approximation via randomized rounding due to Raghavan and Thompson.

We show that there is no log ⅓ − ε M approximation for the undirected Edge-Disjoint Paths problem unless NP ⊆ ZPTIME ( n polylog( n ) ), where M is the size of the graph and ε is any positive constant. This hardness result also applies to the undirected All-or-Nothing Multicommodity Flow problem and the undirected Node-Disjoint Paths problem.

In the edge-disjoint paths problem with congestion (EDPwC), we are given a graph with n nodes, a set of terminal pairs and an integer c. The objective is to route as many terminal pairs as possible, subject to the constraint that at most c demands can be routed through any edge in the graph. When c = 1, the problem is simply referred to as the edge-disjoint paths (EDP) problem. In this paper, we study the hardness of EDPwC in undirected graphs. We obtain an improved hardness result for EDP, and also show the first polylogarithmic integrality gaps and hardness of approximation results for EDPwC. Specifically, we prove that EDP is (log/sup 1/2 - /spl epsiv// n)-hard to approximate for any constant /spl epsiv/ > 0, unless NP /spl sube/ ZPTIME(n/sup polylog n/). We also show that for any congestion c = o(log log n/log log log n), there is no (log/sup (1-/spl epsiv/)/(c+1)/ n) approximation algorithm for EDPwC, unless NP /spl sube/ ZPTIME(n/sup polylog n/). For larger congestion, where c /spl les/ /spl eta/ log log n/log log log n for some constant /spl eta/, we obtain superconstant inapproximability ratios. All of our hardness results can be converted into integrality gaps for the multicommodity flow relaxation. We also present a separate elementary direct proof of this integrality gap result. Finally, we note that similar results can be obtained for the all-or-nothing flow (ANF) problem, a relaxation of EDP, in which the flow unit routed between the source-sink pairs does not have follow a single path, so the resulting flow is not necessarily integral. Using standard transformations, our results also extend to the node-disjoint versions of these problems as well as to the directed setting.

We consider the problem of scheduling data in overloaded networks. We wish to maximize the total profit of data that is served. We first consider a single server that has to schedule data over time-varying channels. This model is motivated by scheduling in wireless networks. Our objective is to maximize the total amount of data scheduled to user by time. In contrast to most previous work we assume that the channel conditions are defined by an adversary rather than a stationary, stochastic process. We give lower bounds on how competitive an online algorithm can be and show that the hounds are nearly matched by a simple randomized algorithm. We also consider a situation in which packets with associated profits are injected into a network of servers. We wish to schedule the packets in the network and maximize the profit of data that reaches its destination. We show that if the servers are allowed to exchange control packets that inform each other of the congestion in the network then we can approximate the optimum profit arbitrarily closely. We also show that without these control packets this is not possible. Our results are motivated by recent work on primal-dual algorithms for flow control in networks. The key difference between our approach and this previous work is that we take into account the scheduling dynamics in the network.

We consider the problem of scheduling multiple users sharing a time-varying wireless channel. (As an example, this is a model of scheduling in 3G wireless technologies, such as CDMA2000 3G1xEV-DO downlink scheduling.) We introduce an algorithm which seeks to optimize a concave utility function /spl Sigma//sub i/H/sub i/(R/sub i/) of the user throughputs R/sub i/, subject to certain lower and upper throughput bounds: R/sub i//sup min//spl les/R/sub i//spl les/R/sub i//sup max/. The algorithm, which we call the gradient algorithm with minimum/maximum rate constraints (GMR) uses a token counter mechanism, which modifies an algorithm solving the corresponding unconstrained problem, to produce the algorithm solving the problem with throughput constraints. Two important special cases of the utility functions are /spl Sigma//sub i/log R/sub i/ and /spl Sigma//sub i/R/sub i/, corresponding to the common proportional fairness and throughput maximization objectives. We study the dynamics of user throughputs under GMR algorithm, and show that GMR is asymptotically optimal in the following sense. If, under an appropriate scaling, the throughput vector R(t) converges to a fixed vector R/sup +/ as time t/spl rarr//spl infin/ then R/sup +/ is an optimal solution to the optimization problem described above. We also present simulation results showing the algorithm performance.

We consider the problem of minimizing the amount of deployed fiber in optical networks in which each fiber carries a fixed number of wavelengths. We are given a network of general topology to carry a set of demands. For each demand we wish to choose a route and a wavelength. Since only distinct wavelengths can be carried on the same fiber, each link e requires max/spl lambda/ Fe(/spl lambda/) fibers where Fe(/spl lambda/) is the number of demands along e that are assigned wavelength /spl lambda/. We wish to minimize the total amount of fiber deployed in order to carry all the demands. Most past work either assumed an unlimited number of wavelengths or else was restricted to specific topologies such as lines, rings and trees. We show that for general topologies the problem is hard to approximate. In particular, for a family of networks of size N, we show that there is no O(log/sup 1/4-/spl epsi//N) approximation algorithm for any /spl epsi/ > 0 unless all problems in NP can be solved by randomized algorithms with expected running time O(n/sup polylog n/). On the positive side we describe methods to choose routes and wavelengths in order to obtain a logarithmic approximation ratio. Lastly we present heuristics that have close-to-optimal performance on example problems on several US backbone networks.

We show that there is no log 1 over 3-ε M approximation for the undirected Edge-Disjoint Paths problem unless NP ⊆ ZPTIME(npolylog(n), where M is the size of the graph and ε is any positive constant. This hardness result also applies to the undirected All-or-Nothing Multicommodity Flow problem and the undirected Node-Disjoint Paths problem.

We show that there is no (log log M)1-ε approximation for the undirected congestion minimization problem unless NP ⊆ ZPTIME(npolylogn), where M is the size of the graph and ε is any positive constant.

We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms.When the paths are known (either given by the adversary or computed as above), our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this article, we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet.Finally, we discuss the effects of combining routing with scheduling. We first show that some unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.

In a wireless network, a basestation transmits data to mobiles at time-varying, mobile-dependent rates due to the ever changing nature of the communication channels. In this article, we consider a wireless system in which the channel conditions and data arrival processes are governed by an adversary . We first consider a single server and a set of users. At each time step t , the server can only transmit data to one user. If user i is chosen, the transmission rate is r i ( t ). We say that the system is ( w , ε)- admissible if in any window of w time steps the adversary can schedule the users so that the total data arriving to each user is at most 1−ε times the total service it receives.Our objective is to design online scheduling algorithms to ensure stability in an admissible system. We first show, somewhat surprisingly, that the admissibility condition alone does not guarantee the existence of a stable online algorithm, even in a subcritical system (i.e., ε > 0). For example, if the nonzero rates in an infinite rate set can be arbitrarily small, then a subcritical system can be unstable for any deterministic online algorithm.On a positive note, we present a tracking algorithm that attempts to mimic the behavior of the adversary. This algorithm ensures stability for all ( w , ε)-admissible systems that are not excluded by our instability results. As a special case, if the rate set is finite, then the tracking algorithm is stable even for a critical system (i.e., ε = 0). Moreover, the queue sizes are independent of ε. For subcritical systems, we also show that a simpler max weight algorithm is stable as long as the user rates are bounded away from zero.The offline version of our problem resembles the problem of scheduling unrelated machines and can be modeled by an integer program. We present a rounding algorithm for its linear relaxation and prove that the rounding technique cannot be substantially improved.

We consider the buy-at-bulk network design problem in which we wish to design a network for carrying multicommodity demands from a set of source nodes to a set of destination nodes. The key feature of the problem is that the cost of capacity on each edge is concave and hence exhibits economies of scale. If the cost of capacity per unit length can be different on different edges then, we say that the problem is non-uniform. The problem is uniform otherwise. We show that for any constant /spl gamma/, if NP /spl nsube/ ZPTIME(n/sup polylog n/), then there is no O(log/sup 1/2 - /spl gamma//N)-approximation algorithm for non-uniform buy-at-bulk network design and there is no O(log/sup 1/4 - /spl gamma//N)-approximation algorithm for the uniform problem.

We consider a wireless basestation transmitting high-speed data to multiple mobile users in a cell. The channel conditions between the basestation and the users are time-varying and user-dependent. We wish to define which user to schedule at each time step. Previous work on this problem has typically assumed that the channel conditions are governed by a stationary stochastic process. In this setting a popular algorithm known as Max-Weight has been shown to have good performance. However, the stationarity assumption is not always reasonable. In this paper we study a more general worst-case model in which the channel conditions are governed by an adversary and are not necessarily stationary. In this model, we show that the nonstationarities can cause Max-Weight to have extremely poor performance. In particular, even if the set of possible transmission rates is finite, as in the CDMA 1timesEV-DO system, Max-Weight can produce queues size that are exponential in the number of users. On the positive side, we describe a set of tracking algorithms that aim to track the performance of a schedule maintained by the adversary. For one of these tracking algorithms the queue sizes are only quadratic. We discuss a number of practical issues associated with the tracking algorithms. We also illustrate the performance of Max-Weight and the tracking algorithms using simulation

We consider a packet network, in which packets are injected in sessions along fixed paths. Packet movement is restricted by link bandwidth. In case of contention, a contention resolution protocol determines which packets proceed. In the permanent session model, a fixed set of connections is present in the network at all times. In the temporary session model, connections come and go over time. In this paper we compare network performance in these two models in terms of stability and end-to-end delay. We provide the first separation of the two models in terms of stability. In particular, we show that generalized processor sharing (GPS) can be unstable with temporary sessions, whereas GPS is known to be stable and have polynomial delay bounds with permanent sessions. We also observe that the relative performance of protocols can differ in the two models. For example, in the temporary session model the protocol farthest-to-go (FTG) is known to be stable and therefore outperforms GPS. However, in the permanent session model we show that FTG can suffer exponential delays and is therefore outperformed by GPS. Although polynomial delay bounds are easy to obtain for permanent sessions, this is not the case when sessions can be temporary. We show that a common framework for bounding delays can only lead to superpolynomial bounds in the temporary session model. We also construct superpolynomial lower bounds on delay for a large class of deterministic, distributed protocols that includes the longest-in-system protocol.

In this letter, we study the Proportional Fair scheduler that has been proposed for scheduling in the high data rate (HDR) wireless data system. We consider a single basestation transmitting to a set of mobile users. In each time slot, the scheduler has to decide on a mobile to which it will transmit data. The decision is based on information that the basestation receives about the time-varying channels between itself and the mobiles. We focus on deciding whether or not Proportional Fair is stable in a situation with finite queues and a data arrival process. That is, we wish to decide if Proportional Fair keeps all queues bounded whenever this is feasible. There are, in fact, multiple versions of Proportional Fair, depending on how it treats small queues. In this letter, we consider six different versions and show that all are unstable for one simple example.

We consider the problem of providing delay bounds to reserved traffic in high-speed input-queued switches. We assume that the matrix of bandwidth demands is known and we use the now standard approach of decomposing this matrix into a convex combination of permutation matrices. Our problem therefore reduces to the problem of constructing a schedule for these permutation matrices. In this paper we derive delay bounds for four algorithms that are based on probabilistic techniques. For each algorithm we first place tokens randomly in continuous time for each permutation matrix. If the nth token that appears corresponds to permutation matrix M/sub k/ then we schedule matrix M/sub k/ in the nth time slot. The algorithms differ in how the random token processes are defined. For two of the algorithms we are able to perform a derandomization so as to obtain deterministic schedules. We show through numerical computation that in many situations the resulting delay bounds are smaller than the previously best-known delay bounds of Chang, Chen, and Huang (1999).

We consider the problem of providing delay bounds to reserved traffic in high-speed input-queued switches. We assume that the matrix of bandwidth demands is known, and we use the now standard approach of decomposing this matrix into a convex combination of permutation matrices. Our problem, therefore, reduces to the problem of constructing a schedule for these permutation matrices. We derive delay bounds for four algorithms that are based on probabilistic techniques. For each algorithm, we first place tokens randomly in continuous time for each permutation matrix. If the nth token that appears corresponds to permutation matrix M/sub k/, then we schedule matrix M/sub k/ in the nth time slot. The algorithms differ in how the random token processes are defined. For two of the algorithms, we are able to perform a derandomization so as to obtain deterministic schedules. We show through numerical computation that in many situations the resulting delay bounds are smaller than the previously best-known delay bounds of Chang et al. (see Proc. IEEE IWQoS, London, U.K., 1999 and Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar 2000).

Research has generated many interesting results on scheduling input-queued switches. However, most of this work focuses on a single switch in isolation. We study the problem of scheduling a network of input-queued switches. We consider the longest-queue-first and longest-port-first scheduling policies that are stable for a single switch, and show that they can be unstable even for a fixed traffic pattern in a simple network of eight input-queued switches. Moreover, this result holds regardless of how the traffic sharing the same port-pair is scheduled at each switch. On the positive side, we present a policy, longest-in-network, that is stable in networks of input-queued switches. This result holds even if the traffic pattern is allowed to change over time.

In a wireless network, a basestation transmits data to mobiles at time-varying, mobile-dependent rates due to the ever changing nature of the communication channels. In this paper we consider a wireless system in which the channel conditions and data arrival processes are governed by an adversary. We first consider a single server and a set of users. At each time step t the server can only transmit data to one user. If user i is chosen the transmission rate is r/sub i/(t). We say that the system is (/spl omega/, /spl epsiv/)-admissible if in any window of /spl omega/ time steps the adversary can schedule the users so that the total data arriving to each user is at most 1 - /spl epsiv/ times the total service it receives. Our objective is to design on-line scheduling algorithms to ensure stability in an admissible system. We first show, somewhat surprisingly, that the admissibility condition alone does not guarantee the existence of a stable online algorithm, even in a subcritical system (i.e. /spl epsiv/ > 0). For example, if the nonzero rates in an infinite rate set can be arbitrarily small, then a subcritical system can be unstable for any deterministic online algorithm. On a positive note, we present a tracking algorithm that attempts to mimic the behavior of the adversary. This algorithm ensures stability for all (/spl omega/, /spl epsiv/)-admissible systems that are not excluded by our instability results. As a special case, if the rate set is finite, then the tracking algorithm is stable even for a critical system (i.e. /spl epsiv/ = 0). Moreover, the queue sizes are independent of e. For subcritical systems, we also show that a simpler max weight algorithm is stable as long as the user rates are bounded away from zero. The offline version of our problem resembles the problem of scheduling unrelated machines and can be modeled by an integer program. We present a rounding algorithm for its linear relaxation and prove that the rounding technique cannot be substantially improved. We conclude by discussing the extension of our model to the network setting.

We consider the problem of client assignment in a distributed system of content servers. We present a system called Webmapper for clustering IP addresses and assigning each cluster to an optimal content server. The system is passive in that the only information it uses comes from monitoring the TCP connections between the clients and the servers. It is also flexible in that it makes no a priori assumptions about network topology and server placement and it can react quickly to changing network conditions. We present experimental results to evaluate the performance of Webmapper.

We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms. When the paths are known (either given by the adversary or computed as above) our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this paper we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet. Finally, we discuss the effects of combining routing with scheduling. We first show that some, unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.

Recent research has generated many interesting results on scheduling input-queued switches. However, most of this work focuses on a single switch in isolation. In this paper we study the problem of scheduling a network of input-queued switches. We consider the longest-queue-first and longest-port-first protocols that are stable for a single switch and show that they can be unstable even for a fixed traffic pattern in a simple network of eight input-queued switches. Moreover, this result holds regardless of how the traffic sharing the same port-pair is scheduled at each switch. On the positive side we present a protocol, longest-in-network, that is stable in networks of input-queued switches. This result holds even if the traffic pattern is allowed to change over time.

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of stability —will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n -node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n ). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay. Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

We analyze the earliest-deadline-first (EDF) scheduling discipline within the framework of statistical multiplexing. We derive techniques for bounding the probability of delay violations when the session injections are independent. This enables us to determine whether a given set of sessions can all meet their delay bounds with the required violation probability. These techniques can be used by a connection admission control (CAC) scheme to decide whether to admit a new session. Our analysis applies to both the single node problem and the network problem in which the sessions have multiple hops. We also give extensive numerical results to illustrate how our bounds may be calculated and to compare the results with estimates that have been derived for generalized processor sharing (GPS). In addition we show that by altering the deadlines for EDF we can match the desired violation probabilities more closely.

A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as voice and video. The most critical performance parameter to bound is the delay experienced by a packet as it travels from its source to its destination. We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r i to follow a predetermined path of length d i . Due to limited bandwidth, only one packet at a time may advance on an edge (link). Session paths may overlap subject to the constraint that the total rate of sessions using any particular edge is at most $1-\varepsilon$ for any constant $\varepsilon \in (0,1)$. We address the problem of scheduling the sessions at each switch, so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of a periodic schedule that achieves a delay bound of O(1/r i +d i ) with only constant-size queues at the switches. This bound is asymptotically optimal for periodic schedules. A consequence of this result is an asymptotically optimal schedule for the static routing problem, wherein all packets are present at the outset. We obtain a delay bound of O(c i + d i ) for packets on path P i , where d i is the number of edges in P i and c i is the maximum congestion along edges in P i . This improves upon the previous known bound of O(c + d), where d = max i d i and c = max i c i . We also present a simple distributed algorithm that, with high probability, delivers every session-i packet to its destination within O(1/r i +d i \log(m/r min )) steps of its injection, where r min is the minimum session rate and m is the number of edges in the network. Our results can be generalized to (leaky-bucket constrained) bursty traffic, where session i tolerates a burst size of b i . In this case, our delay bounds become O(b i /r i + d i ) and O(b i /r i +d i \log(m/r min )), respectively.

We consider the problem of scheduling packets in an input-queued switch when both unicast and multicast traffic is present. In contrast to current approaches which mostly isolate unicast from multicast, we propose an integrated scheduling procedure that packs unicast cells into idle slots left by the multicast schedule. While the optimal integrated schedule can be shown to be NP-hard to obtain, we propose both off-line and on-line algorithms with strong theoretical guarantees to perform integration efficiently, Simulations suggest significant improvement in switch throughput using the integrated schedule. To further reinforce the importance of performing integration, we study the multicast scheduling problem with and without fanout splitting. Again, we prove hardness of the problem and several of its variants, and propose competitive algorithms. The hardness of multicast scheduling hence emphasizes the importance of integrated scheduling for switch performance.

We study the problem of providing end-to-end delay guarantees in connection-oriented networks. In this environment, multiple-hop sessions coexist and interfere with one another. Parekh and Gallager (1993, 1994) showed that the weighted fair queueing (WFQ) scheduling discipline provides a worst-case delay guarantee comparable to 1/(/spl rho/i)/spl times/K/sub i/ for a session with rate /spl rho//sub i/ and K/sub i/ hops. Such delays can occur since a session-i packet can wait for time 1/(/spl rho/i) at every hop. We describe a work-conserving scheme that guarantees an additive delay bound of approximately 1/(/spl rho/i)+K/sub i/. This bound is smaller than the multiplicative bound 1/(/spl rho/i)/spl times/K/sub i/ of WFQ, especially when the hop count K/sub i/ is large. We call our scheme coordinated-earliest-deadline-first (CEDF) since it uses an earliest deadline-first approach in which simple coordination is applied to the deadlines for consecutive hops of a session. The key to the bound is that once a packet has passed through its first server, it can pass through all its subsequent servers quickly. We conduct simulations to compare the delays actually produced by the two scheduling disciplines. In many cases, these actual delays are comparable to their analytical worst-case bounds, implying that CEDF outperforms WFQ.

We study the problem of scheduling packets to meet an arbitrary set of delay requirements.Consider a connectionoriented network in which a set of sessions is defined.Each

In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks. For example, given any "dataflow" type of algorithm that runs in T steps on an n-node ring with unit link delays, we show how to run the algorithm in O(T) steps on any n-node bounded-degree connected network with average link delay O(1). This is a significant improvement over prior approaches to latency hiding, which require slowdowns proportional to the maximum link delay. In the case when the network has average link delay $\dave$, our simulation runs in $O(\sqrt{\dave} T)$ steps using $n/\sqrt{\dave}$ processors, thereby preserving efficiency. We also show how to efficiently simulate an n X n array with unit link delays using slowdown $\tilde O(\dave^{2/3})$ on a two-dimensional array with average link delay $\dave$. Last, we present results for the case in which large local databases are involved in the computation.

We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. A set of trunks of K differing types are available for leasing or buying. Some trunk-types have a high initial overhead cost but a low cost per unit bandwidth. Others have a low overhead cost but a high cost per unit bandwidth. When the central core is given, we show how to construct an access network whose cost is within O(K/sup 2/) of optimal, under weak assumptions on the cost structure. In contrast with previous bounds, this bound is independent of the network and the traffic. Typically, the value of K is small. Our approach uses a linear programming relaxation and is motivated by a rounding technique of Shmoys, Tardos and Aardal (1997). Our techniques extend to a more complex situation in which the core is not given a priori. In this case we aim to minimize the switch cost of the core in addition to the trunk cost of the access network. We provide the same performance bound.

We study network stability in the presence of both input blocking and output blocking.In this setting, two packets can cross a switch simultaneously only if they do not share an input link and they do not share an output link.We adopt the adversarial model of packet injections introduced hy Borodin et al, [S], Previous work in thii injection model assumed the existence of output blocking only.We dcmonotrate that providing network stability is more difllcult when the extra constraint of input blocking is present.For example, some natural analogues of many protocols that were stable in the output blocking model become unstable.Furthermore, instability can be achieved on simple acyclic networks, Our main contribution is a construction of distributed protocols that are stable for all networks.Our approach lo motivated by the LONQEST-IN-SYSTEM protocol for the output blocking model.A similar approach applied to other protocols leads to instability.The assumption of both input and output blocking is common in switching theory.To the best of our knowledge, the effect of input blocking on nettuorhstabiity has not been explored.

A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support read-time traffic such as voice and video. The most critical performance parameter to bound is the delay experienced by a packet as it travels from its source to its destination. We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r/sub i/ to follow a predetermined path of length d/sub i/. Due to limited bandwidth, only one packet at a time may advance on an edge. Session paths may overlap subject to the constraint that the total rate of sessions using any particular edge is less than 1. We address the problem of scheduling the sessions at each switch, so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of an asymptotically-optimal schedule that achieves a delay bound of O(1/r/sub i/+d/sub i/) with only constant-size queues at the switches. We also present a simple distributed algorithm that, with high probability, delivers every session-i packet to its destination within O(1/r/sub i/+d/sub i/ log(m/r/sub min/)) steps of its injection, where r/sub min/ is the minimum session rate, and m is the number of edges in the network. Our results can be generalized to (leaky-bucket constrained) bursty traffic, where session i tolerates a burst size of b/sub i/. In this case, our delay bounds become O(b/sub i//r/sub i/+d/sub i/) and O(b/sub i//r/sub i/+d/sub i/ log(m/r/sub min/)), respectively.

In this paper we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic adversarial model of packet generation and path determination for which the time-averaged injection rate of packets requiring the use of any edge is limited to be less than 1. A crucial issue that arises in such a setting is that of stability-will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly-used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size. Our results resolve several questions posed by Borodin et al. and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/O performance will become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function which determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 3/2-approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-/spl Delta/) in which all distances are either 0 or some constant /spl alpha/. We show how to find the optimal tour in polynomial time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly-distributed requests arrive over time. We present an algorithm (related to the above ATSP-/spl Delta/) that appears to give higher throughput than previously existing head scheduling algorithms.

) Matthew Andrews Tom Leighton y P. Takis Metaxas z Lisa Zhang x Abstract In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks. Our approach is similar in spirit to the "complementary slackness" method of latency hiding, but has the advantage that the slackness does not need to be provided by the programmer, and that large slowdowns are not needed in order to hide the latency. Our approach is also similar in spirit to the latency hiding methods of [2], but is not restricted to memoryless dataflow types of programs. Most of our analysis is centered on the simulation of unit-delay rings on networks of workstations (NOWs) with arbitrary delays on the links. For example, given any collection of operations (including updates of large local memories or databases) that runs in t steps on a ring of n workstations with unit link delays, we show how to perform the same collection of operations in ...

In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks.Our approach is similar in spirit to the "complementary slackness" technique for latency hiding but has the advantage that the slackness does not need to be provided by the programmer and that large slowdowns are not needed in order to hide the latency.For example, given any algorithm that runs in T steps on an n-node ring with unit link delays, we show how to run the algorithm in O(T) steps on any n-node bounded-degree connected network with average link delay 0(1 ).This is a significant improvement over prior approaches to latency hiding, which require slowdowns proportional to the maximum link delay (which can be quite large in comparison to the average delay).In the case when the network has average link delay L&, our simulation runs in O(&Z') steps using n/G processors, thereby preserving efficiency.We also show how to simulate an n x n array with unit link delays using slowdown O(df& log513 n) Q '2/3 log-sla n)-nodearray with average link on an (n dave delay d~ve.We anticipate that our results wilf be of interest in the context of parallel and distributed computing on networks of workstations (N OWS).NOWS typically