Deep neural networks (DNNs) often need to be reduced in size for implementation in customized hardware for applications and products. The fact that DNNs are almost always significantly overparameterized means that there is much room to reduce the size of these networks without adversely impacting their overall performance for most tasks. In this paper, we study whether pruning of DNNs introduces bias in the classification task above and beyond the trained but unpruned model and if it does, when and how to eliminate it. We define bias as the relative classification error frequency of each class before and after pruning, as measured by a χ2homogeneity test. To illustrate our methodology, we focus on the image classification task using popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 using high-performance DNNs such as VGG11, AlexNet, Transformers, customized CNNs and fully-connected networks and compare the error frequencies before and after pruning using the categorical χ2test. We observe that standard pruning schemes, even when they maintain the overall accuracies of the full DNN, can introduce bias. We show that it is possible to reduce such bias to small and negligible values using the framework of a truncated lottery ticket scheme, which we introduce and evaluate.

New deep learning models are massively over-parametrized, e.g., GPT-3 and Turing-NLG exceed 100Bs of parameters. Naturally, model reduction techniques such as pruning, quantization, and distillation have been proposed and deployed. In the pruning literature, the Lottery Ticket Hypothesis (LTH) is amongst the most cited. LTH provides a recipe for reducing the free parameters of a deep network by eliminating a large fraction of its edges by 1) remembering and reusing only the edges on the highest-traffic input-output paths and 2) resetting remaining parameters to their initial values after each round of elimination. Here, we extend this idea two steps further. We add a random buildup phase, starting from a small percentage of parameters to reach a predefined accuracy, often needing fewer than 50% of the parameters of a full network. Then we eliminate parameters using an LTH-like procedure combined with a binary search. We demonstrate the efficiency of the proposed technique using three well-known image data sets by sparsifying three standard deep nets. We exceed the elimination power of LTH (over 98% pruned) and effectively match the performance of full networks. We conclude that for both reducing computation and maintaining a sparse network for inference, the proposed scheme is effective and practical.

Inference on location data has generated a great amount of interest and there are two data sources. GPS location data from GPS-based endpoint devices have high precision, but suffer from intermittent availability, small coverage of users and extra demand on devices' battery. Telecom mobility data, on the other hand, have the complementary advantages of continuous availability and complete coverage but generally with coarse location accuracy. The focus of this paper is on the development of a location insight system for activity labeling and user segment inference, based only on Telecom mobility data enriched with point-of-interest (POI) data. Specifically, we estimate activity patterns based on Bayesian techniques while infer user segments via a tree-based classification algorithm. We test the performance of our inference system via simulated mobility data and investigate the impact of important factors such as granularity of data. We conclude that imprecise location data, enriched with other source of information, can be used for the development of new generation activity inference models.

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.

Topology managers expose network information to applications to improve application-level resource management. An example for various ongoing standardization activities is Application-Layer Traffic Optimization (ALTO). Due to privacy and security constraints, exposed network information has to be filtered according to policies. As part of such policies, distance information can be abstracted by presenting coarser distances over pairs of clustered nodes rather than the precise distances between all node pairs. We refer to this process as distance sparsification. The contribution of this paper is two-fold, the first being a new policy system to enforce abstraction. The second and the main contribution addresses the algorithmic challenge. For the latter, we consider two types of distance sparsification algorithms. The first variant takes as input a matrix of pairwise distances. The sparsification algorithm produces a smaller distance matrix by clustering the nodes into clusters. The second variant instead collapses an edge-weighted graph. We measure the performance of the algorithms by the accuracy of the resulting sparsified distances, and we show that matrix sparsification outperforms graph sparsification. We further observe the trade-off between the accuracy and the size of the sparsified representation. In addition, we also extend our algorithms to handle labeled data, i. e., abstraction policies explicitly mark a number of destinations as reference points. Such additional information can improve the distance sparsification.

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.

Load-balanced switch fabrics offer the promise of very high capacity without the requirement of increased operating rates. We provide a novel solution to the well-known cell reordering problem, which arises in load-balanced switch fabrics if different paths through the switch fabric have different delays. We give a simple sorting circuit, easily implemented in hardware, that can be placed in the final stage of the fabric. This minimizes the delay through the fabric and removes any constraints on operation of the first stage. We show that the sorting circuit can be implemented to operate at a rate of one cell per cycle; we give a probabilistic analysis of required queue occupancies, both at the sorting circuit and at midstage elements; we also briefly discuss congestion control in load-balanced switch fabrics.

Numerous solutions have been proposed in the literature to eliminate reordering in load-balanced switch fabrics. A common approach involves uniform frames, in which every cell of a frame has the same destination. This can achieve 100% throughput with relatively small average traffic delay; however, the worst-case delay may be unbounded. We show that with a slight speedup in the switch fabric we can guarantee satisfactory worst-case delay bounds, without sacrificing other desirable properties. Furthermore, experimental results demonstrate that our scheme improves worst-case delay in realistic traffic scenarios, as compared to previous uniform-frame solutions.

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

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 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.

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 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 study traffic grooming in optical network design. The goal is to aggregate low-bandwidth traffic streams to efficiently utilize high-bandwidth media such as wavelength channels. More precisely, given traffic demands to be routed in a network, the design problem is to define a collection of light paths such that each demand can follow a sequence of consecutive light paths. Each light path has unit-wavelength bandwidth, and multiple sub-wavelength demands may share a common light path. Traffic must enter and depart from a light path at its two endpoints only. Most previous work on grooming focused on the ring topology and typically dealt only with uniform bandwidth demands, whereas we consider more general settings. We study two objectives. One is to minimize total equipment cost necessary to support the light paths; the other is simply to minimize the number of light paths. Even for the extremely restricted special case of a line topology and traffic demands that request half-wavelength bandwidth, we show that both objectives are APX-hard to optimize, which means we cannot approximate the optimum arbitrarily closely. On the other extreme of generality, for arbitrary network topologies and traffic demands that request arbitrary amounts of bandwidth, we show a logarithmic approximation for cost minimization and a 2-approximation for minimizing light path counts. Furthermore, we discover that the special case of half-wavelength demands has rich combinatorial properties, closely related to graph problems such as cycle packing and pattern matching problems such as interchange distance in strings. We show how to approximate both objectives up to small constant factors in this case, while similarly improving the approximation and hardness of the interchange distance problem as well.

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.

In recent years, numerous large-scale Wireless LANs (WLAN) have been deployed all over the world. However, the shortage of non-interfering channels makes it a challenge for WLANs to efficiently support real-time multicast services. We study the problem of efficient scheduling ofreal-timemulticastflows. For mitigating interferences, we allow access-points (APs) to transmit simultaneously only if they are mutually non-interfering and our objective is minimizing the fraction of time used by the APs for servicing the multicast flows. We introduce two multicast strategies, theassociationstrategyfor which each user is restricted to receive flows only from its associated AP and thenon-associationstrategy for which a user may also decode transmissions from other APs in its vicinity. Under both strategies, the scheduling problem of minimizing the multicast service time is NP-hard and we propose simple approximation algorithms with provable performance bounds. Our simulations clearly demonstrate that the proposed algorithms yield efficient multicast scheduling.

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.

Abstract We consider the master ring problem (MRP) which often arises in optical network design. Given a network which consists of a collection of interconnected rings R1,…,RK, with n1,…,nK distinct nodes, respectively, we need to find an ordering of the nodes in the network that respects the ordering of every individual ring, if one exists. We show that MRP is NP‐complete, and therefore, it is unlikely to be solvable by a polynomial time algorithm. Our main result is an algorithm which solves MRP in $ Q \cdot \Pi_{k=1}^{K} (n_{k}/\sqrt{2}) $ steps, for some polynomial Q, as the nk values become large. For the ring clearance problem, a special case of practical interest, our algorithm achieves this running time for rings of any size nk ≥ 2. This yields the first nontrivial improvement, by factor of $ (2\sqrt{2})^{K} \approx (2.82)^{K} $ , over the running time of the naive algorithm, which exhaustively enumerates all $ \Pi_{k=1}^{K} (2n_{k}) $ possible solutions. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We introduce a problem directly inspired by its application to DWDM ( dense wavelength division multiplexing ) network design. We are given a set of demands to be carried over a network. Our goal is to choose a route for each demand and to decompose the network into a collection of edge-disjoint simple paths. These paths are called optical line systems . The cost of routing one unit of demand is the number of line systems with which the demand route overlaps; our design objective is to minimize the total cost over all demands. This cost metric is motivated by the need to minimize O-E-O ( optical-electrical-optical ) conversions in optical transmission. For given line systems, it is easy to find the optimal demand routes. On the other hand, for given demand routes designing the optimal line systems can be NP-hard. We first present a 2-approximation for general network topologies. As optical networks often have low node degrees, we offer an algorithm that finds the optimal solution for the special case in which the node degree is at most 3. Our solution is based on a local greedy approach. If neither demand routes nor line systems are fixed, the situation becomes much harder. Even for a restricted scenario on a 3-regular Hamiltonian network, no efficient algorithm can guarantee a constant approximation better than 2. For general topologies, we offer a simple algorithm with an O (log K )- and an O (log n )-approximation, where K is the number of demands and n the number of nodes. This approximation ratio is almost tight. For rings, a common special topology, we offer a more complex 3/2-approximation algorithm.

We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against edge or node failures in the network. In practice, the most popular model used in high speed telecommunication networks for protection against failures, is the so-called 1+1 model. In this model, two edge or node-disjoint paths are provisioned for each demand pair. We obtain the first non-trivial approximation algorithms for buy-at-bulk network design in the 1+1 model for both edge and node-disjoint protection requirements. Our results are for the single-cable cost model, which is prevalent in optical networks. More specifically, we present a constant-factor approximation for the single-sink case, and an O(log3n) approximation for the multi-commodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems.

Consider the following optimization problem that arises from optical network design. We are given a network topology representing the fiber connectivity and a demand matrix to be carried over the network. A demand can either be unprotected, for which a single routing path is required, or protected, for which two disjoint paths are needed. Moreover, a demand may request a large bandwidth in multiples of a wavelength or a small bandwidth in the order of a fraction of a wavelength. Our objective is to route all demands while minimizing the cost of optical components necessary to carry the traffic. This paper has two aspects: modeling and effective heuristics. First, we define edge cost using subadditive functions and reason why they closely model the optical component cost. Second, we present shortest-path based heuristics to choose demand routes, where the choice of edge weights drives the optimization. One natural candidate for edge weight is the marginal cost incurred when carrying an additional demand. We observe good performance of this approach in combination with iterative rerouting and random orderings of demands. For heavy traffic, we note further improvement if we gradually approximate the original cost function with a set of more sophisticated piecewise strongly concave functions. Our heuristics are simple, scalable and find close-to-optimal solutions in many real instances.

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 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.

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.

As wireless access technologies improve in data rates, the problem focus is shifting towards providing adequate backhaul from the wireless access points to the Internet. Existing wired backhaul technologies such as copper wires running at DSL, T1, or T3 speeds can be expensive to install or lease, and are becoming a performance bottleneck as wireless access speeds increase. Longhaul, non-line-of-sight wireless technologies such as WiMAX (802.16) hold the promise of enabling a high speed wireless backhaul as a cost-effective alternative. However, the biggest challenge in building a wireless backhaul is achieving guaranteed performance (throughput and delay) that is typically provided by a wired backhaul. This paper explores the problem of efficiently designing a multihop wireless backhaul to connect multiple wireless access points to a wired gateway. In particular, we provide a generalized link activation framework for scheduling packets over this wireless backhaul, such that any existing wireline scheduling policy can be implemented locally at each node of the wireless backhaul. We also present techniques for determining good interference-free routes within our scheduling framework, given the link rates and cross-link interference information. When a multihop wireline scheduler with worst case delay bounds (such as WFQ or Coordinated EDF) is implemented over the wireless backhaul, we show that our scheduling and routing framework guarantees approximately twice the delay of the corresponding wireline topology. Finally, we present simulation results to demonstrate the low delays achieved using our framework.

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.

Despite improvements in wireless access technologies such as 3G or 802.11x, ubiquitous data access has remained a challenge, mainly due to the lack of inexpensive, pervasive backhaul connections from access points to the Internet. With the recent WiMAX standard for high-speed, non-line-of-sight fixed wireless links, multihop wireless backhauls might now overcome this bottleneck. However an important remaining challenge is to provide rate and delay guarantees for customer connections similar to wired backhauls. We provide several schemes for performing admission control for connections with QoS requirements over a multihop wireless backhaul. This is the first work to address both rate and delay requirements for connections. Our admission control algorithms first construct appropriate tree-based topologies connecting wireless backhaul nodes to a wired gateway and then admit the best subset of connections while respecting their rate and delay requirements. Alternately, we admit all the connections with appropriate degradation of their QoS requirements

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 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 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.

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 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.

We study a network model in which each network link is associated with a set of delays and costs. These costs are a function of the delays and reflect the prices paid in return for delay guarantees. Such a cost structure can model a setting in which the service provider provides multiple service classes with a different price and delay guarantee for each class. We are given a source node s, a sink node t, and an end-to-end delay constraint D. Our aim is to choose an s-t path and determine a set of per link delay guarantees along this path so as to satisfy the constraint D while minimizing the total cost incurred. In the case where the s-t path is known, we aim to optimally partition the end-to-end delay constraint into link constraints along the path. We present approximation algorithms for both problems, since they are known to be NP-hard. Our algorithms guarantee to produce solutions that are within a factor 1+/spl epsiv/ of the optimal, where /spl epsiv/ is a parameter of our choice. The run times are polynomial in the input size and 1//spl epsiv/. We also provide a number of heuristics for the second problem and present simulation results. Previous work on related problems either focused on optimal solutions for special cost functions or on heuristics that have no performance guarantees. In contrast, we present provably good approximation algorithms and heuristics which apply to general cost functions.

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 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.

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 ...

We consider the problem of asynchronous execution of parallel programs. We assume that the original program is designed for a synchronous system, whereas the actual system may be asynchronous. We seek an automatic execution scheme, which allows the asynchronous system to execute the synchronous program. Previous execution schemes provide solutions only for the case where the original program is deterministic. Here, we provide the first solution for the more general case where the original program can be nondeterministic (e.g. randomized). Our scheme is based on a novel agreement protocol for the asynchronous parallel setting. Our protocol allows n asynchronous processors to agree on n word-sized values in O(n log n log log n) total work. Total work is defined to be the summation of the number of steps performed by all processors (including steps from busy waiting). 1 Introduction Motivation. Parallel programs are frequently designed assuming tightly-coupled processors, operating 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