29625431
Building Edge-Failure Resilient Networks
We consider the design of resilient networks that are fault tolerant against single link failures. Resilience against single link failures can be built into the network by providing backup paths, which are used when an edge failure occurs on a primary path. We consider several network design problems in this context: the goal is to provision primary and backup bandwidth while minimizing cost. Our models are motivated by current high speed optical networks and we provide approximation algorithms for the problems below.The main problem we consider is that of backup allocation. In this problem, we are given an already provisioned (primary) network, and we want to reserve backup capacity on the edges of the underlying network so that all the demand can be routed even in the case of a single edge failure. We also consider a variant where the primary network has a tree topology and it is required that the restored network retains the tree topology. We then address the problem of simultaneous primary and backup allocation, in which we are given specifications of the traffic to be handled, and we want to both provision the primary as well as the backup network. We also investigate the online model where the primary network is not known in advance. Demands between source-sink pairs arrive online and the goal is to provide a primary path and set of backup edges that can be used for restoring a failure of any of the primary edges.
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.
47268289
Optimal configuration of OSPF aggregates
Open Shortest Path First (OSPF) is a popular protocol for routing within an autonomous system (AS) domain. In order to scale for large networks containing hundreds and thousands of subnets, OSPF supports a two-level hierarchical routing scheme through the use of OSPF areas. Subnet addresses within an area are aggregated, and this aggregation is a crucial requirement for scaling OSPF to large AS domains, as it results in significant reductions in routing table sizes, smaller link-state databases, and less network traffic to synchronize the router link-state databases. On the other hand, address aggregation also implies loss of information about the length of the shortest path to each subnet, which in turn, can lead to suboptimal routing.In this paper, we address the important practical problem of configuring OSPF aggregates to minimize the error in OSPF shortest-path computations due to subnet aggregation. We first develop an optimal dynamic programming algorithm that, given an upper bound k on the number of aggregates to be advertised and a weight assignment function for the aggregates, computes the k aggregates that result in the minimum cumulative error in the shortest-path computations for all source-destination subnet pairs. Subsequently, we tackle the problem of assigning weights to OSPF aggregates such that the cumulative error in the computed shortest paths is minimized. We demonstrate that, while for certain special cases (e.g., unweighted cumulative error) efficient optimal algorithms for the weight assignment problem can be devised, the general problem itself is NP-hard. Consequently, we have to rely on search heuristics to solve the weight assignment problem. To the best of our knowledge, our work is the first to address the algorithmic issues underlying the configuration of OSPF aggregates and to propose efficient configuration algorithms that are provably optimal for many practical scenarios.
46145059
Primal-Dual Algorithms for Connected Facility Location Problems
We consider the Connected Facility Location problem. We are given a graph G = (V, E) with cost ce on edge e, a set of facilities F ? V, and a set of demands D ? V. We are also given a parameter M ? 1. A solution opens some facilities, say F, assigns each demand j to an open facility i(j), and connects the open facilities by a Steiner tree T. The cost incurred is ?i?F fi + ?j?D djci(j)j + M ?e?T ce. We want a solution of minimum cost. A special case is when all opening costs are 0 and facilities may be opened anywhere, i.e., F = V. If we know a facility v that is open, then this problem reduces to the rent-or-buy problem. We give the first primal-dual algorithms for these problems and achieve the best known approximation guarantees. We give a 9-approximation algorithm for connected facility location and a 5-approximation for the rent-or-buy problem. Our algorithm integrates the primal-dual approaches for facility location [7] and Steiner trees [1,2]. We also consider the connected k-median problem and give a constant-factor approximation by using our primal-dual algorithm for connected facility location. We generalize our results to an edge capacitated version of these problems.
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.
16012186
A fine-grained, controllable, user-to-user delegation method in RBAC
This paper addresses the issues surrounding user-to-user delegation in RBAC. We show how delegations can be incorporated into the RBAC model in a simple and straightforward manner. A special feature of the model is that it allows fine-grained control over what rights a user wishes to delegate as opposed to delegation at the role level where all the rights of a role must be delegated. In addition, the model provides a rich set of controls regarding further delegations of a right, generic constraints that further control delegations, and an innovative model for revocations. Properties of both delegation and revocation are discussed, and our work is compared with other related research.
14897390
Meta workflows as a control and coordination mechanism for exception handling in workflow systems
A higher level control and coordination mechanism is required for exception handling in workflow systems. This paper describes such a framework based on events, states, and a new kind of process called a meta workflow. Meta workflows have five kinds of meta activities and facilitate control over base workflows. We describe the framework and illustrate it with examples to show its features. The paper gives an architecture for incorporating it into existing workflows and also provides a formal semantics of execution. This framework can be used in Web services, supply chains, and inter-organizational applications where coordination requirements are complex, and flexible and adaptable workflows are needed. It is also useful for handling not just failure recovery but also various kinds of special situations, which arise frequently in web-based applications.
16105375
Stochastic models for throughput analysis of randomly arriving elastic flows in the Internet
This paper is about analytical models for calculating the average bandwidth shares obtained by TCP controlled finite file transfers that arrive randomly and share a single (bottleneck) link. Owing to the complex nature of the TCP congestion control algorithm, a single model does not work well for all combinations of network parameters (i.e., mean file size, link capacity, and propagation delay). We propose two models, develop their analyses, and identify the regions of their applicability. One model is obtained from a detailed analysis of TCP's AIMD adaptive window mechanism; the analysis accounts for session arrivals and departures, and finite link buffers. It is essentially a processor sharing (PS) model with time varying service rate; hence we call it TCP-PS. The other model is a simple modification of the PS model that accounts for large propagation delays; we call this model rate limited-PS (RL-PS). The TCP-PS model analysis accommodates a general file size distribution by approximating it with a mixture of exponentials. The RL-PS model can be used for general file size distributions. We show that the TCP-PS model converges to the standard PS model as the propagation delay approaches zero. We also observe that the PS model provides very poor estimates of throughput unless the propagation delay is very small. We observe that the key parameters affecting the throughput are the bandwidth delay product (BDP), file size distribution, the link buffer and the traffic intensity. Several numerical comparisons between analytical and simulation results are provided. We observe that the TCP-PS model is accurate when the BDP is small compared to the mean file size, and the RL-PS model works well when the BDP is large compared to the mean file size.
1151748
Scalable and Efficient Data Streaming Algorithms for Detecting Common Content in Internet Traffic
Recent research on data streaming algorithms has provided powerful tools to efficiently monitor various characteristics of traffic passing through a single network link or node. However, it is often desirable to perform data streaming analysis on the traffic aggregated over hundreds or even thousands of links/nodes, which will provide network operators with a holistic view of the network operation. Shipping raw traffic data to a centralized location (i.e., “raw aggregation”) for streaming analysis is clearly not a feasible approach for a large network. In this paper, we propose a set of novel distributed data streaming algorithms that allow scalable and efficient monitoring of aggregated traffic without the need for raw aggregation. Our algorithms target the specific network monitoring problem of finding common content in the Internet traffic traversing several nodes/links, which has applications in network-wide intrusion detection, early warning for fast propagating worms, and detection of hot objects and spam traffic. We evaluate our algorithms through extensive simulations and experiments on traffic traces collected from a tier-1 ISP. The experimental results demonstrate that our algorithms can effectively detect common content in the traffic traversing across a large network.
31048080
Advertising data analysis using rough sets model
This study explores the use of rough-set methods for marketing decision support systems in the retail business. A tutorial presentation of Rough Set Data Analysis (RSDA) in the context of knowledge discovery from time series databases is given. We show how an RSDA model can be used to develop a marketing decision support system which can capture the complex relationships between marketing factors, such as advertising and promotion, and the total impact on sales levels in order to find influential advertising strategies. This information is used by the business manager to make faster and better strategy decisions for the business to survive in the rapidly changing and competitive environments. The data set used for RSDA application example contains weekly investments in different media categories: TV, radio, cinema, morning press, evening press, popular press, special interest press, and outdoor posters; for seven makes of cars in the Swedish market.