In computing, as in many aspects of life, changes incur cost. Many optimization problems are formulated as a one-time instance starting from scratch. However, a common case that arises is when we already have a set of prior assignments and must decide how to respond to a new set of constraints, given that each change from the current assignment comes at a price. That is, we would like to maximize the fitness or efficiency of our system, but we need to balance it with the changeout cost from the previous state. We provide a precise formulation for this tradeoff and analyze the resulting stable extensions of some fundamental problems in measurement and analytics. Our main technical contribution is a stable extension of Probability Proportional to Size (PPS) weighted random sampling, with applications to monitoring and anomaly detection problems. We also provide a general framework that applies to top- k , minimum spanning tree, and assignment. In both cases, we are able to provide exact solutions and discuss efficient incremental algorithms that can find new solutions as the input changes.

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, $\textnormal{\sc VarOptk}$, that dominates all previous schemes in terms of estimation quality. $\textnormal{\sc VarOptk}$ provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in $O(\log k)$ time. Finally, it is particularly well suited for combinations of samples from different streams in a distributed setting.

The reconvergence of routing protocols in response to changes in network topology can impact application performance. While improvements in protocol specification and implementation have significantly reduced reconvergence times, increasingly performance-sensitive applications continue to raise the bar for these protocols. As such, monitoring the performance of routing protocols remains a critical activity for network operators. We design tool{}, a tool based on passive data plane measurements that we use in conjunction with control plane monitors for offline debugging and analysis of forwarding table dynamics. We discuss practical constraints that affect tool{}, and show how they can be addressed in real deployment scenarios. As an application of tool{}, we study forwarding table updates by backbone routers at a tier-1 ISP. We detect interesting behavior such as delayed forwarding table updates and routing loops due to buggy routers -- confirmed by network operators -- that are not detectable using traditional control plane monitors.

Business and economic considerations are driving the extensive use of service differentiation in Virtual Private Networks (VPNs) operated for business enterprises today. The resulting Class of Service (CoS) designs embed complex policy decisions based on the described priorities of various applications, extent of bandwidth availability, and cost considerations. These inherently complex high-level policies are realized through low-level router configurations. The configuration process is tedious and error-prone given the highly intertwined nature of CoS configuration, the multiple router configurations over which the policies are instantiated, and the complex access control lists (ACLs) involved. Our contributions include (i) a formal approach to modeling CoS policies from router configuration files in a precise manner; (ii) a practical and computationally efficient tool that can determine the CoS treatment received by an arbitrary set of flows across multiple routers; and (iii) a validation of our approach in enabling applications such as troubleshooting, auditing, and visualization of network-wide CoS design, using router configuration data from a cross-section of 150 diverse enterprise VPNs. To our knowledge, this is the first effort aimed at modeling and analyzing CoS configurations.

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, VarOptk, that dominates all previous schemes in terms of estimation quality. VarOptk provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in O(log k) time, which is optimal even on the word RAM. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting.

Many data sets occur as unaggregated data sets , where multiple data points are associated with each key. In the aggregate view of the data, the weight of a key is the sum of the weights of data points associated with the key. Examples are measurements of IP packet header streams, distributed data streams produced by events registered by sensor networks, and Web page or multimedia requests to context distribution servers. We aim to combine sampling and aggregation to provide accurate and efficient summaries of the aggregate view. However, data points are scattered in time or across multiple servers and hence aggregation is subject to resource constraints on the size of summaries that can be stored or transmitted. We develop a summarization framework for unaggregated data where summarization is a scalable and composable operator, and as such, can be tailored to meet resource constraints. Our summaries support unbiased estimates of the weight of subpopulations of keys specified using arbitrary selection predicates. While we prove that under such scenarios there is no variance optimal scheme, our estimators have the desirable properties that the variance is progressively closer to the minimum possible when applied to a "more" aggregated data set. An extensive evaluation using synthetic and real data sets shows that our summarization framework outperforms all existing schemes for this fundamental problem, even for the special and well-studied case of data streams.

Measurement, collection, and interpretation of network usage data commonly involves multiple stage of sampling and aggregation. Examples include sampling packets, aggregating them into flow statistics at a router, sampling and aggregation of usage records in a network data repository for reporting, query and archiving. Although unbiased estimates of packet, bytes and flows usage can be formed for each sampling operation, for many applications it is crucial to know the inherent estimation error. Previous work in this area has been limited mainly to analyzing the estimator variance for particular methods, e.g., independent packet sampling. However, the variance is of limited use for more general sampling methods, where the estimate may not be well approximated by a Gaussian distribution.

Enterprise customers are increasingly adopting MPLS (Multiprotocol Label Switching) VPN (Virtual Private Network) service that offers direct any-to-any reachability among the customer sites via a provider network. Unfortunately this direct reachability model makes the service provider's routing tables grow very large as the number of VPNs and the number of routes per customer increase. As a result, router memory in the provider's network has become a key bottleneck in provisioning new customers. This paper proposes Relaying, a scalable VPN routing architecture that the provider can implement simply by modifying the configuration of routers in the provider network, without requiring changes to the router hardware and software. Relaying substantially reduces the memory footprint of VPNs by choosing a small number of hub routers in each VPN that maintain full reachability information, and by allowing non-hub routers to reach other routers through a hub. Deploying Relaying in practice, however, poses a challenging optimization problem that involves minimizing router memory usage by having as few hubs as possible, while limiting the additional latency due to indirect delivery via a hub. We first investigate the fundamental tension between the two objectives and then develop algorithms to solve the optimization problem by leveraging some unique properties of VPNs, such as sparsity of traffic matrices and spatial locality of customer sites. Extensive evaluations using real traffic matrices, routing configurations, and VPN topologies demonstrate that Relaying is very promising and can reduce routing-table usage by up to 90%, while increasing the additional distances traversed by traffic by only a few hundred miles, and the backbone bandwidth usage by less than 10%.

Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on the traffic of arbitrary subpopulations of flows. It is therefore of great importance to collect the most accurate and informative summaries given the router's resource constraints. Cisco's sampled NetFlow, based on aggregating a sampled packet stream into flows, is the most widely deployed such system.

IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing, anomaly detection, inferring traffic demands, configuring packet filters and routing protocols, and more. While queries are posed over the set of flows, the summarization algorithmis applied to the stream of packets. Aggregation of traffic into flows before summarization requires storage of per-flow counters, which is often infeasible. Therefore, the summary has to be produced over the unaggregated stream.

From a high-volume stream of weighted items, we want to create a generic sample of a certain limited size that we can later use to estimate the total weight of arbitrary subsets. Applied to Internet traffic analysis, the items could be records summarizing the flows of packets streaming by a router. Subsets could be flow records from different time intervals of a worm attack whose signature is later determined. The samples taken in the past thus allow us to trace the history of the attack even though the worm was unknown at the time of sampling. Estimation from the samples must be accurate even with heavy-tailed distributions where most of the weight is concentrated on a few heavy items. We want the sample to be weight sensitive, giving priority to heavy items. At the same time, we want sampling without replacement in order to avoid selecting heavy items multiple times. To fulfill these requirements we introduce priority sampling, which is the first weight-sensitive sampling scheme without replacement that works in a streaming context and is suitable for estimating subset sums. Testing priority sampling on Internet traffic analysis, we found it to perform an order of magnitude better than previous schemes. Priority sampling is simple to define and implement: we consider a steam of items i = 0,…, n − 1 with weights w i . For each item i , we generate a random number α i ∈ (0,1] and create a priority q i = w i /α i . The sample S consists of the k highest priority items. Let τ be the ( k + 1)th highest priority. Each sampled item i in S gets a weight estimate ŵ i = max{ w i , τ}, while nonsampled items get weight estimate ŵ i = 0. Magically, it turns out that the weight estimates are unbiased, that is, E[ ŵ i ] = w i , and by linearity of expectation, we get unbiased estimators over any subset sum simply by adding the sampled weight estimates from the subset. Also, we can estimate the variance of the estimates, and find, surprisingly, that the covariance between estimates ŵ i and ŵ j of different weights is zero. Finally, we conjecture an extremely strong near-optimality; namely that for any weight sequence, there exists no specialized scheme for sampling k items with unbiased weight estimators that gets smaller variance sum than priority sampling with k + 1 items. Szegedy settled this conjecture at STOC'06.

Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random priority depending on its weight. Suppose we want to estimate the sum of an arbitrary subset I ⊆ T. For any q > 2, considering only the q highest priority items from I, we obtain an unbiased estimator of the sum whose relative standard deviation is O(1/√q). Thus to get an expected approximation factor of 1 ± ε, it suffices to consider O(1/±ε2) items from I. Our estimator needs no knowledge of the number of items in the subset I, but we can also estimate that number if we want to estimate averages.The above scheme performs the same role as the on-line aggregation of Hellerstein et al. (SIGMOD'97) but it has the advantage of having expected good performance for any possible sequence of weights. In particular, the performance does not deteriorate in the common case of heavy-tailed weight distributions. This point is illustrated experimentally both with real and synthetic data.We will also show that our approach can be used to improve Cohen's size estimation framework (FOCS'94).

Packet classification, although extensively studied, is an evolving problem. Growing and changing needs necessitate the use of larger filters with more complex rules. The increased complexity and size pose implementation challenges on current hardware solutions and drive the development of software classifiers, in particular, decision-tree based classifiers. Important performance measures for these classifiers are time and memory due to required high throughput and use of limited fast memory.We analyze Tier 1 ISP data that includes filters and corresponding traffic from over a hundred edge routers and thousands of interfaces. We provide a comprehensive view on packet classification in an operational network and glean insights that help us design more effective classification algorithms.We propose and evaluate decision tree classifiers with common branches. These classifiers have linear worst-case memory bounds and require much less memory than standard decision tree classifiers, but nonetheless, we show that on our data have similar average and worst-case time performance. We argue that common-branches exploit structure that is present in real-life data sets.We observe a strong Zipf-like pattern in the usage of rules in a classifier, where a very small number of rules resolves the bulk of traffic and most rules are essentially never used. Inspired by this observation, we propose traffic-aware classifiers that obtain superior average-case and bounded worst-case performance. Good average-case can boost performance of software classifiers that can be used in small to medium sized routers and are also important for traffic analysis and traffic engineering.

This paper deals with sampling objects from a large stream. Each object possesses a size, and the aim is to be able to estimate the total size of an arbitrary subset of objects whose composition is not known at the time of sampling. This problem is motivated from network measurements in which the objects are flow records exported by routers and the sizes are the number of packet or bytes reported in the record. Subsets of interest could be flows from a certain customer or flows from a worm attack. This paper introduces threshold sampling as a sampling scheme that optimally controls the expected volume of samples and the variance of estimators over any classification of flows. It provides algorithms for dynamic control of sample volumes and evaluates them on flow data gathered from a commercial Internet Protocol (IP) network. The algorithms are simple to implement and robust to variation in network conditions. The work reported here has been applied in the measurement infrastructure of the commercial IP network. To not have employed sampling would have entailed an order of magnitude greater capital expenditure to accommodate the measurement traffic and its processing.

Passive traffic measurement increasingly employs sampling at the packet level. Many high-end routers form flow statistics from a sampled substream of packets. Sampling controls the consumption of resources by the measurement operations. However, knowledge of the statistics of flows in the unsampled stream remains useful, for understanding both characteristics of source traffic, and consumption of resources in the network. This paper provides methods that use flow statistics formed from sampled packet stream to infer the frequencies of the number of packets per flow in the unsampled stream. A key task is to infer the properties of flows of original traffic that evaded sampling altogether. We achieve this through statistical inference, and by exploiting protocol level detail reported in flow records. We investigate the impact on our results of different versions of packet sampling.

Traffic matrices are required inputs for many IP network management tasks, such as capacity planning, traffic engineering, and network reliability analysis. However, it is difficult to measure these matrices directly in large operational IP networks, so there has been recent interest in inferring traffic matrices from link measurements and other more easily measured data. Typically, this inference problem is ill-posed, as it involves significantly more unknowns than data. Experience in many scientific and engineering fields has shown that it is essential to approach such ill-posed problems via "regularization". This paper presents a new approach to traffic matrix estimation using a regularization based on "entropy penalization". Our solution chooses the traffic matrix consistent with the measured data that is information-theoretically closest to a model in which source/destination pairs are stochastically independent. It applies to both point-to-point and point-to-multipoint traffic matrix estimation. We use fast algorithms based on modern convex optimization theory to solve for our traffic matrices. We evaluate our algorithm with real backbone traffic and routing data, and demonstrate that it is fast, accurate, robust, and flexible.

In traffic monitoring, accounting, and network anomaly detection, it is often important to be able to detect high-volume traffic clusters in near real-time. Such heavy-hitter traffic clusters are often hierarchical (ie, they may occur at different aggregation levels like ranges of IP addresses) and possibly multidimensional (ie, they may involve the combination of different IP header fields like IP addresses, port numbers, and protocol). Without prior knowledge about the precise structures of such traffic clusters, a naive approach would require the monitoring system to examine all possible ombinations of aggregates in order to detect the heavy hitters, which can be proohibitive in terms of computation resources.

Many network management applications use as their data traffic volumes differentiated by attributes such as IP address or port number. IP flow records are commonly collected for this purpose: these enable determination of fine-grained usage of network resources. However, the increasingly large volumes of flow statistics incur concomitant costs in the resources of the measurement infrastructure. This motivates sampling of flow records.This paper addresses sampling strategy for flow records. Recent work has shown that non-uniform sampling is necessary in order to control estimation variance arising from the observed heavy-tailed distribution of flow lengths. However, while this approach controls estimator variance, it does not place hard limits on the number of flows sampled. Such limits are often required during arbitrary downstream sampling, resampling and aggregation operations employed in analysis of the data.This paper proposes a correlated sampling strategy that is able to select an arbitrarily small number of the "best" representatives of a set of flows. We show that usage estimates arising from such selection are unbiased, and show how to estimate their variance, both offline for modeling purposes, and online during the sampling itself. The selection algorithm can be implemented in a queue-like data structure in which memory usage is uniformly bounded during measurement. Finally, we compare the complexity and performance of our scheme with other potential approaches.

This paper describes a measurement infrastructure used to collect detailed IP traffic measurements from an IP backbone. Usage, i.e, bytes transmitted, is determined from raw NetFlow records generated by the backbone routers. The amount of raw data is immense. Two types of data sampling in order to manage data volumes: (i) (packet) sampled NetFlow in the routers; (ii) sizedependent sampling of NetFlow records. Furthermore, dropping of NetFlow records in transmission can be regarded as an uncontrolled form of sampling.

Passive traffic measurement increasingly employs sampling at the packet level. Many high-end routers form flow statistics from a sampled substream of packets. Sampling is necessary in order to control the consumption of resources by the measurement operations. However, knowledge of the statistics of flows in the unsampled stream remains useful, for understanding both characteristics of source traffic, and consumption of resources in the network.This paper provide methods that use flow statistics formed from sampled packet stream to infer the absolute frequencies of lengths of flows in the unsampled stream. A key part of our work is inferring the numbers and lengths of flows of original traffic that evaded sampling altogether. We achieve this through statistical inference, and by exploiting protocol level detail reported in flow records. The method has applications to detection and characterization of network attacks: we show how to estimate, from sampled flow statistics, the number of compromised hosts that are sending attack traffic past the measurement point. We also investigate the impact on our results of different implementations of packet sampling.

Traffic matrices are required inputs for many IP network management tasks: for instance, capacity planning, traffic engineering and network reliability analysis. However, it is difficult to measure these matrices directly, and so there has been recent interest in inferring traffic matrices from link measurements and other more easily measured data. Typically, this inference problem is ill-posed, as it involves significantly more unknowns than data. Experience in many scientific and engineering fields has shown that it is essential to approach such ill-posed problems via "regularization". This paper presents a new approach to traffic matrix estimation using a regularization based on "entropy penalization". Our solution chooses the traffic matrix consistent with the measured data that is information-theoretically closest to a model in which source/destination pairs are stochastically independent. We use fast algorithms based on modern convex optimization theory to solve for our traffic matrices. We evaluate the algorithm with real backbone traffic and routing data, and demonstrate that it is fast, accurate, robust, and flexible.

Many routers can generate and export statistics on flows of packets that traverse them. Increasingly, high end routers form flow statistics from only a sampled packet stream in order to manage resource consumption involved.This paper addresses three questions. Firstly: what are the downstream consequences for the measurement infrastructure? Long traffic flows will be split up if the time between sampled packets exceeds the flow timeout. Using packet header traces we show that flows generated by increasingly prevalent peer-to-peer applicalions are vulnerable to this effect.Secondly: can the volume of packet-sampled flow statistics be easily determined? We develop a simple model that predicts both the export rate of flow packet-sampled flow statistics and the number of active flows. It uses unsampled flow statistics---those commonly currently collected--as its data, i.e., it does not rely on having packet header traces available.Thirdly: what properties of the original traffic stream can be inferred from the packet sampled flow statistics? We show that as well as estimating total bytes and packets, one can also infer more detail, specifically the number and average length of flows in the unsampled traffic stream, even though some flows will have no packets sampled. We believe that this information is useful, both for understanding source traffic, e.g. the dependence of flow lengths on application type, and also monitoring changes in the composition of the traffic, e.g., a flood of short flows during a DoS attack. In all cases, we evaluate our approach using packet header traces gathered in backbone and campus networks.

Engineering a large IP backbone network without an accurate network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network elements can result in significant (and sudden) fluctuations in load. We present a model of traffic demands to support traffic engineering and performance debugging of large Internet service provider networks. By defining a traffic demand as a volume of load originating from an ingress link and destined to a set of egress links, we can capture and predict how routing affects the traffic traveling between domains. To infer the traffic demands, we propose a measurement methodology that combines flow-level measurements collected at all ingress links with reachability information about all egress links. We discuss how to cope with situations where practical considerations limit the amount and quality of the necessary data. Specifically, we show how to infer interdomain traffic demands using measurements collected at a smaller number of edge links-the peering links connecting to neighboring providers. We report on our experiences in deriving the traffic demands in the AT&T IP Backbone, by collecting, validating, and joining very large and diverse sets of usage, configuration, and routing data over extended periods of time. The paper concludes with a preliminary analysis of the observed dynamics of the traffic demands and a discussion of the practical implications for traffic engineering.

Engineering a large IP backbone network without an accurate, network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network elements can result in significant (and sudden) fluctuations in load. In this paper, we present a model of traffic demands to support traffic engineering and performance debugging of large Internet Service Provider networks. By defining a traffic demand as a volume of load originating from an ingress link and destined to a set of egress links, we can capture and predict how routing affects the traffic traveling between domains. To infer the traffic demands, we propose a measurement methodology that combines flow-level measurements collected at all ingress links with reachability information about all egress links. We discuss how to cope with situations where practical considerations limit the amount and quality of the necessary data. Specifically, we show how to infer interdomain traffic demands using measurements collected at a smaller number of edge links --- the peering links connecting to neighboring providers. We report on our experiences in deriving the traffic demands in the AT&T IP Backbone, by collecting, validating, and joining very large and diverse sets of usage, configuration, and routing data over extended periods of time. The paper concludes with a preliminary analysis of the observed dynamics of the traffic demands and a discussion of the practical implications for traffic engineering.

Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by various processors in the network. The goal is to minimize the communication costs incurred in serving a sequence of such requests. Distributed data management on important classes of networks---trees and bus-based networks---are studied. Optimal algorithms with constant competitive ratios and matching lower bounds are obtained. Our algorithms use different interesting techniques, such as work functions [Chrobak and Larmore, Proc. DIMACS Workshop on On-Line Algorithms, AMS, 1991, pp. 11--64] and "factoring."

We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided “proof” with probability at least 1/2. Our result builds upon and improves a recent result of Arora and Safra [1998] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length). As a consequence, we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP = P. The class MAX SNP was defined by Papadimitriou and Yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show that there exists a positive ε such that approximating the maximum clique size in an N -vertex graph to within a factor of N ε is NP-hard.

This paper investigates the computational complexity of approximating several \NP-optimization problems using the number of queries to an \NP\ oracle as a complexity measure. The results show a tradeoff between the closeness of the approximation and the number of queries required. For an approximation factor $k(n)$, $\log \log_{k(n)} n$ queries to an \NP\ oracle can be used to approximate the maximum clique size of a graph within a factor of $k(n)$. However, this approximation cannot be achieved using fewer than $\log \log_{k(n)} n - c$ queries to any oracle unless $\Pe = \NP$, where c is a constant that does not depend on k. These results hold for approximation factors $k(n) \geq 2$ that belong to a class of functions which includes any integer constant function, $\log n$, $\log^{a} n$, and $n^{1/a}$. Similar results are obtained for Graph Coloring, Set Cover, and other \NP-optimization problems.

A probabilistically checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who claims that the input x is in L, and Player 0, who claims that the input x is not in L. It is known that there is a PCDS for L in which V flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE [A. Condon, J. Feigenbaum, C. Lund, and P. Shor, Chicago J. Theoret. Comput. Sci., 1995, No. 4]. In this paper, we restrict attention to RPCDSs, which are PCDSs in which Player 0 follows a very simple strategy: On each turn, Player 0 chooses uniformly at random from the set of legal moves. We prove the following result. Theorem. L has an RPCDS in which the verifier flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE. This new characterization of PSPACE is used to show that certain stochastic PSPACE-hard functions are as hard to approximate closely as they are to compute exactly. Examples of such functions include optimization versions of Dynamic Graph Reliability, Stochastic Satisfiability, Mah-Jongg, Stochastic Generalized Geography, and other "games against nature" of the type introduced in [C. Papadimitriou, J. Comput. System Sci., 31 (1985), pp. 288--301].

Next generation wide area networks will be connection-oriented, with data-link layer connectivity being provided by asynchronous transfer mode (ATM). For the huge existing investment in current IP networks such as the Internet to remain useful, one must devise mechanisms to carry IP traffic over ATM networks. A fundamental issue is to devise holding policies for virtual circuits carrying datagrams. The authors consider two pricing schemes, the first is a likely pricing scheme of future ATM networks, while the second is based on characteristics of current networks. For each pricing scheme, the authors devise a simple holding policy that adapts to the characteristics of the IP traffic. The authors simulate their policies on actual network traffic and find that they perform significantly better than previous policies.

When carrying Internet protocol (IP) traffic over an asynchronous transfer mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP datagram. We present a formal statement of the problem and carry out a detailed empirical examination of various holding time policies taking into account the issue of network pricing. We offer solutions for two natural pricing models, the first being a likely pricing model of future ATM networks, while the second is based on characteristics of current networks. For each pricing model, we study a variety of simple nonadaptive policies as well as easy to implement policies that adapt to the characteristics of the IP traffic. We simulate our policies on actual network traffic, and find that policies based on least recently used (LRU) perform well, although the best adaptive policies provide a significant improvement over LRU.>

Next generation wide area network are very likely to use connection-oriented protocols such as Asynchronous Transfer Mode (ATM). For the huge existing investment in current IP networks such as the Internet to remain useful, me must devise mechanisms to carry IP traffic over connection-oriented networks. A basic issue is to devise holding policies for virtual circuits carrying datagrams. In this paper we consider two variants of the paging problem that arise in the design of such holding policies. In the IP-paging problem the page inter-request times are chosen according to independent distributions. For this model we construct a very simple deterministic algorithm whose page fault rate is at most 5 times that of the best online algorithm (that knows the inter-request time distributions). We also show that some natural algorithms for this problem do not have constant competitive ratio. In distributional paging the inter-request time distributions may be dependent, and hence any probabilistic model of page request sequences can be represented. We construct a simple randomized algorithm whose page fault rate is at most 4 times that of the best online algorithm.>

No abstract available.

We prove results indicating that it is hard to compute efficiently good approximate solutions to the Graph Coloring, Set Covering and other related minimization problems.Specifically, there is an E > 0 such that Graph Coloring cannot be approximated with ratio n' unless P = NP.Set Covering cannot be approximated with ratio c log n for any c < l/4 unless NP is contained in DTIME(nP"Y'"~").Similar results follow for related problems such as Clique Cover, Fractional Chromatic Number, Dominating Set, and others.

Article Free Access Share on Efficient probabilistically checkable proofs and applications to approximations Authors: M. Bellare View Profile , S. Goldwasser View Profile , C. Lund View Profile , A. Russell View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 294–304https://doi.org/10.1145/167088.167174Published:01 June 1993Publication History 182citation659DownloadsMetricsTotal Citations182Total Downloads659Last 12 Months70Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions Share on Authors: Anne Condon View Profile , Joan Feigenbaum View Profile , Carsten Lund View Profile , Peter Shor View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 305–314https://doi.org/10.1145/167088.167190Online:01 June 1993Publication History 21citation326DownloadsMetricsTotal Citations21Total Downloads326Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We prove results indicating that it is hard to compute efficiently good approximate solutions to the Graph Coloring, Set Covering and other related minimization problems.Specifically, there is an c >0 such that Graph Coloring cannot be approximated with ratio n' unless P=NP.Set Covering cannot be approximated with ratio clog n for any c < 1/4 unless NP is contained in DTIME[nPOIY log ~].Similar results follow for related problems such as Clique Cover, Fractional Chromatic Number, Dominating Set and others. 1

Pratt [Internat. J. Parallel Programming, 15 (1986), pp. 33–7.1] introduced POMSETs (partially ordered multisets) to describe and analyze concurrent systems. A POMSET P gives a set of temporal constraints that any correct execution of a given oncurrent system must satisfy. Let $L ( P )$ (the language ofP) denote the set of all system executions that satisfy the constraints given by P. This paper shows the following for finite POMSETs P, Q, and system execution x: • The POMSET language membership problem (given x and P, is $x \in L( P )$?) is NP-complete. • The POMSET language containment problem (given P and Q, is $L ( P ) \subseteq L ( Q )$?) is $\prod _2^p $-complete. • The POMSET language equality problem (given P and Q, is $L( P ) = L ( Q )$?) is at least as hard as the graph-isomorphism problem. • The POMSET language size problem (given P, how many x are in $L( P )$?) is span-P-complete.

The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e.g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP.>

We study the complexity of computing the permanent on random inputs. We consider matrices drawn randomly from the space of n by n matrices with integer values between 0 and p–1, for any large enough prime p. We show that any polynomial time algorithm which computes the permanent correctly on even an exponentially small fraction of these matrices, implies the collapse of the polynomial-time hierarchy to its second level.

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].

The exact power of two-prover interactive proof systems (MIP) introduced by M. Ben-Or et al. (Proc. 20th Symp. on Theory of Computing, 1988, p.113-31) is determined. In this system, two all-powerful noncommunicating provers convince a randomizing polynomial-time verifier in polynomial time that the input x belongs to the language L. It was previously suspected (and proved in a relativized sense) that coNP-complete languages do not admit such proof systems. In sharp contrast, it is shown that the class of languages having two-prover interactive proof systems is computable in nondeterministic exponential time (NEXP). This represents a further step demonstrating the unexpectedly immense power for randomization and interaction in efficient provability.>

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction.>