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.

We consider the problem of minimizing the power consumption of IP core networks by means of power aware configuration of the Points of Presence (PoPs), given general traffic demands on the links. Although the problem is in general NP-complete, we give an optimal algorithm for an important variant where the number of ports on each line-card chassis is 2. For the general problem, we design two approximation algorithms with respective P/2 and 2lnN approximation ratios, where P is the number of ports on each line-card chassis, and N is the number of chassis within the PoP. When the traffic demands are correlated, we prove that our algorithms are optimal. Extensive simulations demonstrate that our PoP configuration algorithms significantly outperform existing design solutions over a wide range of traffic instances.

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.

A major concern in IP networks is to ensure that any topology changes, whether planned or unplanned, do not disrupt network performance. IP Fast Reroute (IP FRR) is a general approach to address this issue by promptly forwarding an IP packet to a predetermined alternate next-hop as soon as the primary next-hop to the destination becomes unavailable. Among the numerous IP FRR schemes proposed to date, the simplest ones do not guarantee protection against every component failure, while more sophisticated ones tend to be difficult to implement due to various inherent complexities, such as nontrivial modifications of IP packets or high resource requirements. This paper presents a simple and efficient IP FRR scheme called DisPath, which leverages several fundamental properties of minimum-cost node-disjoint paths for determining the alternate next-hop toward a given destination. We show that DisPath ensures full coverage, meaning protection against all single link or node failures, with low computational overhead and without the practical complications encountered by other schemes that offer the same level of protection. Our simulations on several realistic instances reveal that DisPath usually creates shorter (and, at worst, not much longer) alternative paths than existing solutions adopted by the industry. Combined with the aforementioned protection guarantee and simplicity of implementation, these results provide strong evidence that DisPath is a most compelling choice of IP FRR scheme.

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.

We consider the problem of minimizing the power consumption of IP core networks by means of power-aware design and auto-configuration of the Points of Presence (PoPs), given general traffic demands on the links. Although the problem is in general NP-complete, we give an optimal algorithm for an important variant in which the number of ports on each line-card chassis is 2. For the general problem, we design two approximation algorithms with respective P=2 and 2 lnN approximation ratios, where P is the number of ports on each line-card chassis, and N is the number of chassis within the PoP. When the traffic demands are correlated, we prove that our algorithms are optimal. Extensive simulations demonstrate that our PoP design and auto-configuration algorithms significantly outperform existing design solutions over a wide range of traffic instances.

A major concern in IP networks is to ensure that any topology changes, whether planned or unplanned, do not disrupt network performance. IP Fast Reroute (IP FRR) is a general approach to address this issue, by promptly forwarding an IP packet to a predetermined alternate next hop as soon as the primary next hop to the destination becomes unavailable. Among the numerous IP FRR schemes proposed to date, the simplest ones do not guarantee protection against every component failure, while more sophisticated ones tend to be difficult to implement due to various inherent complexities, such as nontrivial modifications of IP packets or high resource requirements.

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.

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.

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 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 study the leader election problem on n players in the asynchronous full-information model. Our main contention is that the most commonly used performance measure for leader-election protocols, called resilience, is unable to discern whether a small number of players can exercise disproportionate influence on the outcome of a protocol, or not. As a remedy we propose a new quantity, named cheaters' edge, which roughly describes by what multiplicative factor malicious players may increase, through cheating, their probability of getting elected. Arguably, a good protocol must have bounded cheaters' edge.We present polynomial-time constructions of new leader-election protocols that are fast, in terms of the rounds required (5, 5 log n, and log n rounds, respectively), but moreover exhibit bounded cheaters' edge under progressively looser restrictions on the number t of malicious players: t < Θn / log n, t < Θn / √log n log log n, and, eventually, no restriction at all---without relying on any a priori knowledge of t. The latter of these three protocols constitutes the first constructive solution to a problem posed by Alon and Naor more than a decade ago.