8829443
Exploring the trade-off between label size and stack depth in MPLS routing
Multiprotocol label switching or MPLS technology is being increasingly deployed by several of the largest Internet service providers to solve problems such as traffic engineering and to offer IP services like virtual private networks (VPNs). In MPLS, the analysis of the packet (network layer) header is performed just once, and each packet is assigned a stack of labels, which is examined by subsequent routers when making forwarding decisions. Despite the fact that MPLS is becoming widespread on the Internet, we know essentially very little about the performance one can achieve with it, and about the intrinsic trade-offs in its use of resources. In this paper, we undertake a comprehensive study of the label size versus stack depth trade-off for MPLS routing protocols on lines and trees. We show that in addition to LSP tunneling, label stacks can also be used to dramatically reduce the number of labels required for setting up MPLS LSPs in a network. Based on this observation, we develop routing algorithms and prove lower bounds for two basic problems: (1) fixed label routing: given a fixed number of labels, we want to minimize the stack depth, and (2) fixed stack routing: given a bound on the stack depth, we want to minimize the number of labels used. Our simulation results validate our approach, demonstrating that our novel protocols enable MPLS routing on large trees with few labels and small stack sizes. Thus, our MPLS routing algorithms are applicable to a number of practical scenarios involving the provisioning of VPNs and multicast trees.
206560175
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem
We present the first constant factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity buy-at-bulk network design in which there are two ways to install capacity on any given edge. Capacity can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. Recent work on buy-at-bulk network design has concentrated on the special case where all sinks are identical; existing constant factor approximation algorithms for this special case make crucial use of the assumption that all commodities ship flow to the same sink vertex and do not obviously extend to the multicommodity rent-or-buy problem. Prior to our work, the best heuristics for the multicommodity rent-or-buy problem achieved only logarithmic performance guarantees and relied on the machinery of relaxed metrical task systems or of metric embeddings. By contrast, we solve the network design problem directly via a novel primal-dual algorithm.
46840073
Better Algorithms for Minimizing Average Flow-Time on Related Machines
We consider the problem of minimising flow time on related machines and give an O(logP)-approximation algorithm for the offline case and an O(log2P)-competitive algorithm for the online version. This improves upon the previous best bound of O(log2P logS) on the competitive ratio. Here P is the ratio of the maximum to the minimum processing time of a job and S is the ratio of the maximum to the minimum speed of a machine.
995281
Deterministic wavelet thresholding for maximum-error metrics
Several studies have demonstrated the effectiveness of the wavelet, decomposition as a tool for reducing large amounts of data down to compact, wavelet synopses that can be used to obtain fast, accurate approximate answers to user queries. While conventional wavelet synopses are based on greedily minimizing the overall root-mean-squared (i.e., L2-norm) error in the data approximation, recent work has demonstrated that such synopses can suffer from important problems, including severe bias and wide variance in the quality of the data reconstruction, and lack of non-trivial guarantees for individual approximate answers. As a result, probabilistic thresholding schemes have been recently proposed as a means of building wavelet synopses that try to probabilistically control other approximation-error metrics, such as the maximum relative error in data-value reconstruction, which is arguably the most important for approximate query answers and meaningful error guarantees.One of the main open problems posed by this earlier work is whether it is possible to design efficient deterministic wavelet-thresholding algorithms for minimizing non-L2 error metrics that are relevant to approximate query processing systems, such as maximum relative or maximum absolute error. Obviously, such algorithms can guarantee better wavelet synopses and avoid the pitfalls of probabilistic techniques (e.g., "bad" coin-flip sequences) leading to poor solutions. In this paper, we address this problem and propose novel, computationally efficient schemes for deterministic wavelet thresholding with the objective of optimizing maximum-error metrics. We introduce an optimal low polynomial-time algorithm for one-dimensional wavelet thresholding--our algorithm is based on a new Dynamic-Programming (DP) formulation, and can be employed to minimize the maximum relative or absolute error in the data reconstruction. Unfortunately, directly extending our one-dimensional DP algorithm to multi-dimensional wavelets results in a super-exponential increase in time complexity with the data dimensionality. Thus, we also introduce novel, polynomial-time approximation schemes (with tunable approximation guarantees for the target maximum-error metric) for deterministic wavelet thresholding in multiple dimensions.
1501195
On a bidirected relaxation for the MULTIWAY CUT problem
In the MULTIWAY CUT problem, we are given an undirected edge-weighted graph G = (V, E) with ce denoting the cost (weight) of edge e. We are also given a subset S of V, of size k, called the terminals. The objective is to find a minimum cost set of edges whose removal ensures that the terminals are disconnected.In this paper, we study a bidirected linear programming relaxation of MULTIWAY CUT. We resolve an open problem posed by Vazirani [Approximation Algorithms, first ed., Springer, Berlin, Heidelberg, 2001], and show that the integrality gap of this relaxation is not better than that for a geometric linear programming relaxation given by Calinescu et al. [J. Comput. System Sci. 60(3) (2000) 564-574], and may be strictly worse on some instances.
8488383
Sorting and selection with structured costs
The study of the effect of priced information on basic algorithmic problems was initiated by M. Charikar et al. (2000). The authors continue the study of sorting and selection in the priced comparison model, i.e., when each comparison has an associated cost, and answer some of the open problems suggested by Charikar et al. If the comparison costs are allowed to be arbitrary, we show that one cannot get good approximation ratios. A different way to assign costs is based on the idea that one can distill out an intrinsic value for each item being compared, such that the cost of comparing two elements is some "well-behaved" or "structured" function of their values. We feel that most practical applications will have some structured cost property. The authors study the problems of sorting and selection (which includes finding the maximum and the median) in the structured cost model. We get a variety of approximation results for these problems, depending on the restrictions we put on the structured costs. We show that it is possible to get much improved results with the structured cost model than the case when we do not have any assumptions on comparison costs.
14590041
Designing Access Methods for Bitemporal Databases
By supporting the valid and transaction time dimensions, bitemporal databases represent reality more accurately than conventional databases. The authors examine the issues involved in designing efficient access methods for bitemporal databases, and propose the partial-persistence and the double-tree methodologies. The partial-persistence methodology reduces bitemporal queries to partial persistence problems for which an efficient access method is then designed. The double-tree methodology "sees" each bitemporal data object as consisting of two intervals (a valid-time and a transaction-time interval) and divides objects into two categories according to whether the right endpoint of the transaction time interval is already known. A common characteristic of both methodologies is that they take into account the properties of each time dimension. Their performance is compared with a straightforward approach that "sees" the intervals associated with a bitemporal object as composing one rectangle, which is stored in a single multidimensional access method. Given that some limited additional space is available, the experimental results show that the partial-persistence methodology provides the best overall performance, especially for transaction timeslice queries. For those applications that require ready, off-the-shelf, access methods, the double-tree methodology is a good alternative.
16196571
Dual-Vt design of FPGAs for subthreshold leakage tolerance
In this paper we propose a dual-Vt FPGA architecture for reduction of subthreshold leakage power. A CAD flow has been proposed based on the dual-Vt assignment algorithm and placement for realizing the dual-Vt FPGA architecture. Logic elements within the logic blocks are the candidates for dual-Vt assignment. We propose an architecture in which there are two kinds of logic blocks, one with all high-Vt logic elements and another with a fixed percentage of high-Vt logic elements. These two kinds of logic blocks are then placed in such a way that the FPGA architecture remains regular. Results indicate that in the ideal case of dual-Vt assignment, over 95% of the logic elements can be assigned high-Vt. Results show that leakage savings of 55% can be achieved. Design tradeoffs for various ratios of the two kinds of logic blocks are investigated. The dual-Vt FPGA CAD flow is intended for development and evaluation of dual-Vt FPGA architectures
10184291
Efficient and scalable query routing for unstructured peer-to-peer networks
Searching for content in peer-to-peer networks is an interesting and challenging problem. Queries in Gnutella-like unstructured systems that use flooding or random walk to search must visit O(n) nodes in a network of size n, thus consuming significant amounts of bandwidth. In this paper, we propose a query routing protocol that allows low bandwidth consumption during query forwarding using a low cost mechanism to create and maintain information about nearby objects. To achieve this, our protocol maintains a lightweight probabilistic routing table at each node that suggests the location of each object in the network. Following the corresponding routing table entries, a query can reach the destination in a small number of hops with high probability. However, maintaining routing tables in a large and highly dynamic network requires non-traditional mechanisms. We design a novel data structure called an exponentially decaying bloom filter (EDBF) that encodes such probabilistic routing tables in a highly compressed manner, and allows for efficient aggregation and propagation. The search primitives provided by our system can be used to search for single keys or multiple keywords with equal ease. Analytical modeling of our design predicts significant improvements in search efficiency, verified through extensive simulations in which we observed an order of magnitude reduction in query path length over previous proposals.
15446858
A new approach for asynchronous distributed rate control of elastic sessions in integrated packet networks
We develop a new class of asynchronous distributed algorithms for the explicit rate control of elastic sessions in an integrated packet network. Sessions can request for minimum guaranteed rate allocations (e.g., minimum cell rates in the ATM context), and, under this constraint, we seek to allocate the max-min fair rates to the sessions. We capture the integrated network context by permitting the link bandwidths available to elastic sessions to be stochastically time varying. The available capacity of each link is viewed as some statistic of this stochastic process [e.g., a fraction of the mean, or a large deviations-based equivalent service capacity (ESC)]. The ESC is obtained so as to satisfy an overflow probability constraint on the buffer length. For fixed available capacity at each link, we show that the vector of max-min fair rates can be computed from the root of a certain vector equation. A distributed asynchronous stochastic approximation technique is then used to develop a provably convergent distributed algorithm for obtaining the root of the equation, even when the link flows and the available capacities are obtained from on-line measurements. The switch algorithm does not require per connection monitoring, nor does it require per connection marking of control packets. A virtual buffer based approach for on-line estimation of the ESC is utilized. We also propose techniques for handling large variations in the available capacity owing to the arrivals or departures of CBR/VBR sessions. Finally, simulation results are provided to demonstrate the performance of this class of algorithms in the local and wide area network context.
2753181
Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data
A novel algorithm for managing replicated data is presented. The proposed method is based on organizing the copies of an object into a logical, multilevel hierarchy, and extending the quorum consensus algorithm to such an environment. Several properties of the method are derived and optimality conditions are given for minimizing the quorum size. It is shown that, given a collection of n copies of an object, the method allows a quorum to be formed with n/sup 0.63/ copies versus ((n+1)/2) copies in the case of the majority voting algorithm. Tradeoffs between the proposed method and three other quorum-based methods are discussed, and the main features of each method are highlighted. >