bluuebunny/crossref_metadata_2025 huggingface dataset:
Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
Authors: Even Guy , Levi Retsef , Rawitz Dror , Schieber Baruch , Shahar Shimon (Moni) , Sviridenko Maxim
Published: July 2008

In the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. In this article, we study the capacitated version of this problem in which the input includes an integral capacity for each line. The capacity of a line bounds the number of rectangles that the line can cover. We consider two versions of this problem. In the first, one is allowed to use only a single copy of each line (
hard capacities
), and in the second, one is allowed to use multiple copies of every line, but the multiplicities are counted in the size (or weight) of the solution (
soft capacities
).

We present an exact polynomial-time algorithm for the weighted one dimensional case with hard capacities that can be extended to the one dimensional weighted case with soft capacities. This algorithm is also extended to solve a certain capacitated multi-item
lot-sizing
inventory problem with joint set-up costs. For the case of
d
-dimensional rectangle stabbing with soft capacities, we present a 3
d
-approximation algorithm for the unweighted case. For
d
-dimensional rectangle stabbing problem with hard capacities, we present a bi-criteria algorithm that computes 4
d
-approximate solutions that use at most two copies of every line. Finally, we present hardness results for rectangle stabbing when the dimension is part of the input and for a two-dimensional weighted version with hard capacities.
Clustering, community partition and disjoint spanning trees
Authors: Zhang Cun-Quan , Ou Yongbin
Published: July 2008

Clustering method is one of the most important tools in statistics. In a graph theory model, clustering is the process of finding all dense subgraphs. A mathematically well-defined measure for graph density is introduced in this article as follows. Let
G
= (
V
,
E
) be a graph (or multi-graph) and
H
be a subgraph of
G
. The dynamic density of
H
is the greatest integer
k
such that min

∀
P

{|
E
(
H
/
P
)|/|
V
(
H
/
P
)| − 1} >
k
where the minimum is taken over all possible partitions
P
of the vertex set of
H
, and
H
/
P
is the graph obtained from
H
by contracting each part of
P
into a single vertex. A subgraph
H
of
G
is a level-
k
community if
H
is a maximal subgraph of
G
with dynamic density at least
k
. An algorithm is designed in this paper to detect all level-
h
communities of an input multi-graph
G
. The worst-case complexity of this algorithm is upper bounded by
O
(|
V
(
G
)|
2
h
2
). This new method is one of few available clustering methods that are mathematically well-defined, supported by rigorous mathematical proof and able to achieve the optimization goal with polynomial complexity. As a byproduct, this algorithm also can be applied for finding edge-disjoint spanning trees of a multi-graph. The worst-case complexity is lower than all known algorithms for multi-graphs.
Compact name-independent routing with minimum stretch
Authors: Abraham Ittai , Gavoille Cyril , Malkhi Dahlia , Nisan Noam , Thorup Mikkel
Published: July 2008

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a
Õ
(√n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is optimal in a very strong sense. It is known that no compact routing using
o
(
n
) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√
n
,)space per node.
Getting the best response for your erg
Authors: Pruhs Kirk , Uthaisombut Patchrawat , Woeginger Gerhard
Published: July 2008

We consider the speed scaling problem of minimizing the average response time of a collection of dynamically released jobs subject to a constraint
A
on energy used. We propose an algorithmic approach in which an energy optimal schedule is computed for a huge
A
, and then the energy optimal schedule is maintained as
A
decreases. We show that this approach yields an efficient algorithm for equi-work jobs. We note that the energy optimal schedule has the surprising feature that the job speeds are not monotone functions of the available energy. We then explain why this algorithmic approach is problematic for arbitrary work jobs. Finally, we explain how to use the algorithm for equi-work jobs to obtain an algorithm for arbitrary work jobs that is
O
(1)-approximate with respect to average response time, given an additional factor of (1 + ϵ) energy.
FEATUREImage search at the speed of thought
Authors: Mathan Santosh
Published: July 2008

Editors' Note: The ability to sense cognitive activity---ranging from information-processing load, attention levels, and perceptual judgments---using EEG sensors provides a basis for developing systems that adapt to users and exploit latent human capabilities. Santosh Mathan describes a neural interface being developed by Honeywell for searching through large image sets efficiently.
Linux ready for the desktop?
Authors: Weiss Aaron
Published: July 2008

If you want to start an online war without getting mixed up in national politics, go to a technology site like Slashdot or Digg and ask, "Is Linux ready for the desktop yet?" People love to argue about Linux, particularly how the desktop experience stacks up to Windows and Mac. Some of the people with strong opinions hardly even know what Linux is. Others know Linux almost too well, their minds stuck in a narrow and ideologically-driven rut.
Performance of random medium access control, an asymptotic approach
Authors: Bordenave Charles , McDonald David , Proutiere Alexandre
Published: July 2008

Random Medium-Access-Control (MAC) algorithms have played an increasingly important role in the development of wired and wireless Local Area Networks (LANs) and yet the performance of even the simplest of these algorithms, such as slotted-Aloha, are still not clearly understood. In this paper we provide a general and accurate method to analyze networks where interfering users share a resource using random MAC algorithms. We show that this method is asymptotically exact when the number of users grows large, and explain why it also provides extremely accurate performance estimates even for small systems. We apply this analysis to solve two open problems: (a) We address the stability region of non-adaptive Aloha-like systems. Specifically, we consider a fixed number of buffered users receiving packets from independent exogenous processes and accessing the resource using Aloha-like algorithms. We provide an explicit expression to approximate the stability region of this system, and prove its accuracy. (b) We outline how to apply the analysis to predict the performance of adaptive MAC algorithms, such as the exponential back-off algorithm, in a system where saturated users interact through interference. In general, our analysis may be used to quantify how far from optimality the simple MAC algorithms used in LANs today are, and to determine if more complicated (e.g. queue-based) algorithms proposed in the literature could provide significant improvement in performance.
Bound analysis of closed queueing networks with workload burstiness
Authors: Casale Giuliano , Mi Ningfang , Smirni Evgenia
Published: July 2008

Burstiness and temporal dependence in service processes are often found in multi-tier architectures and storage devices and must be captured accurately in capacity planning models as these features are responsible of significant performance degradations. However, existing models and approximations for networks of first-come first-served (FCFS) queues with general independent (GI) service are unable to predict performance of systems with temporal dependence in workloads.

To overcome this difficulty, we define and study a class of closed queueing networks where service times are represented by Markovian Arrival Processes (MAPs), a class of point processes that can model general distributions, but also temporal dependent features such as burstiness in service times. We call these models MAP queueing networks. We introduce provable upper and lower bounds for arbitrary performance indexes (e.g., throughput, response time, utilization) that we call Linear Reduction (LR) bounds. Numerical experiments indicate that LR bounds achieve a mean accuracy error of 2 percent.

The result promotes LR bounds as a versatile and reliable bounding methodology of the performance of modern computer systems.
Scheduling despite inexact job-size information
Authors: Wierman Adam , Nuyens Misja
Published: July 2008

Motivated by the optimality of Shortest Remaining Processing Time (SRPT) for mean response time, in recent years many computer systems have used the heuristic of "favoring small jobs" in order to dramatically reduce user response times. However, rarely do computer systems have knowledge of exact remaining sizes. In this paper, we introduce the class of ε-SMART policies, which formalizes the heuristic of "favoring small jobs" in a way that includes a wide range of policies that schedule using inexact job-size information. Examples of ε-SMART policies include (i) policies that use exact size information, e.g., SRPT and PSJF, (ii) policies that use job-size estimates, and (iii) policies that use a finite number of size-based priority levels.

For many ε-SMART policies, e.g., SRPT with inexact job-size information, there are no analytic results available in the literature. In this work, we prove four main results: we derive upper and lower bounds on the mean response time, the mean slowdown, the response-time tail, and the conditional response time of ε-SMART policies. In each case, the results explicitly characterize the tradeoff between the accuracy of the job-size information used to prioritize and the performance of the resulting policy. Thus, the results provide designers insight into how accurate job-size information must be in order to achieve desired performance guarantees.
Network externalities and the deployment of security features and protocols in the internet
Authors: Lelarge Marc , Bolot Jean
Published: July 2008

Getting new security features and protocols to be widely adopted and deployed in the Internet has been a continuing challenge. There are several reasons for this, in particular economic reasons arising from the presence of network externalities. Indeed, like the Internet itself, the technologies to secure it exhibit network effects: their value to individual users changes as other users decide to adopt them or not. In particular, the benefits felt by early adopters of security solutions might fall significantly below the cost of adoption, making it difficult for those solutions to gain attraction and get deployed at a large scale.

Our goal in this paper is to model and quantify the impact of such externalities on the adoptability and deployment of security features and protocols in the Internet. We study a network of interconnected agents, which are subject to epidemic risks such as those caused by propagating viruses and worms, and which can decide whether or not to invest some amount to deploy security solutions. Agents experience negative externalities from other agents, as the risks faced by an agent depend not only on the choices of that agent (whether or not to invest in self-protection), but also on those of the other agents. Expectations about choices made by other agents then influence investments in self-protection, resulting in a possibly suboptimal outcome overall.

We present and solve an analytical model where the agents are connected according to a variety of network topologies. Borrowing ideas and techniques used in statistical physics, we derive analytic solutions for sparse random graphs, for which we obtain asymptotic results. We show that we can explicitly identify the impact of network externalities on the adoptability and deployment of security features. In other words, we identify both the economic and network properties that determine the adoption of security technologies. Therefore, we expect our results to provide useful guidance for the design of new economic mechanisms and for the development of network protocols likely to be deployed at a large scale.
The delay-friendliness of TCP
Authors: Brosh Eli , Baset Salman Abdul , Rubenstein Dan , Schulzrinne Henning
Published: July 2008

TCP has traditionally been considered unfriendly for real-time applications. Nonetheless, popular applications such as Skype use TCP since UDP packets cannot pass through many NATs and firewalls. Motivated by this observation, we study the delay performance of TCP for real-time media flows. We develop an analytical performance model for the delay of TCP. We use extensive experiments to validate the model and to evaluate the impact of various TCP mechanisms on its delay performance. Based on our results, we derive the working region for VoIP and live video streaming applications and provide guidelines for delay-friendly TCP settings. Our research indicates that simple application-level schemes, such as packet splitting and parallel connections, can reduce the delay of real-time TCP flows by as much as 30% and 90%, respectively.
Hierarchical routing over dynamic wireless networks
Authors: Tschopp Dominique , Diggavi Suhas , Grossglauser Matthias
Published: July 2008

In dynamic networks the topology evolves and routes are maintained by frequent updates, consuming throughput available for data transmission. We ask whether there exist low-overhead schemes for these networks, that produce routes that are within a small constant factor (stretch) of the optimal route-length. This is studied by using the underlying geometric properties of the connectivity graph in wireless networks. For a class of models for wireless network that fulfill some mild conditions on the connectivity and on mobility over the time of interest, we can design distributed routing algorithm that maintain the routes over a changing topology. This scheme needs only node identities and integrates location service along with routing, therefore accounting for the complete overhead. We analyze the worst-case (conservative) overhead and route-quality (stretch) performance of this algorithm for the aforementioned class of models. Our algorithm allows constant stretch routing with a network wide control traffic overhead of
O
(
n
log
2
n
) bits per mobility time step (time-scale of topology change) translating to
O
(log
2
n
) overhead per node (with high probability for wireless networks with such mobility model). We can reduce the maximum overhead per node by using a load-balancing technique at the cost of a slightly higher average overhead. Numerics show that these bounds are quite conservative.
Loss-aware network coding for unicast wireless sessions
Authors: Rayanchu Shravan , Sen Sayandeep , Wu Jianming , Banerjee Suman , Sengupta Sudipta
Published: July 2008

Local network coding is growing in prominence as a technique to facilitate greater capacity utilization in multi-hop wireless networks. A specific objective of such local network coding techniques has been to explicitly minimize the total number of transmissions needed to carry packets across each wireless hop. While such a strategy is certainly useful, we argue that in lossy wireless environments, a better use of local network coding is to provide higher levels of redundancy even at the cost of increasing the number of transmissions required to communicate the same information. In this paper we show that the design space for effective redundancy in local network coding is quite large, which makes optimal formulations of the problem hard to realize in practice. We present a detailed exploration of this design space and propose a suite of algorithms, called CLONE, that can lead to further throughput gains in multi-hop wireless scenarios. Through careful analysis, simulations, and detailed implementation on a real testbed, we show that some of our simplest CLONE algorithms can be efficiently implemented in today's wireless hardware to provide a factor of two improvement in throughput for example scenarios, while other, more effective, CLONE algorithms require additional advances in hardware processing speeds to be deployable in practice.
Exploiting manufacturing variations for compensating environment-induced clock drift in time synchronization
Authors: Schmid Thomas , Charbiwala Zainul , Friedman Jonathan , Cho Young H. , Srivastava Mani B.
Published: July 2008

Time synchronization is an essential service in distributed computing and control systems. It is used to enable tasks such as synchronized data sampling and accurate time-of-flight estimation, which can be used to locate nodes. The deviation in nodes' knowledge of time and inter-node resynchronization rate are affected by three sources of time stamping errors: network wireless communication delays, platform hardware and software delays, and environment-dependent frequency drift characteristics of the clock source. The focus of this work is on the last source of error, the clock source, which becomes a bottleneck when either required time accuracy or available energy budget and bandwidth (and thus feasible resynchronization rate) are too stringent. Traditionally, this has required the use of expensive clock sources (such as temperature compensation using precise sensors and calibration models) that are not cost-effective in low-end wireless sensor nodes. Since the frequency of a crystal is a product of manufacturing and environmental parameters, we describe an approach that exploits the subtle manufacturing variation between a pair of inexpensive oscillators placed in close proximity to algorithmically compensate for the drift produced by the environment. The algorithm effectively uses the oscillators themselves as a sensor that can detect changes in frequency caused by a variety of environmental factors. We analyze the performance of our approach using behavioral models of crystal oscillators in our algorithm simulation. Then we apply the algorithm to an actual temperature dataset collected at the James Wildlife Reserve in Riverside County, California, and test the algorithms on a waveform generator based testbed. The result of our experiments show that the technique can effectively improve the frequency stability of an inexpensive uncompensated crystal 5 times with the potential for even higher gains in future implementations.
Confident estimation for multistage measurement sampling and aggregation
Authors: Cohen Edith , Duffield Nick , Lund Carsten , Thorup Mikkel
Published: July 2008

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.

This motivates our paper, in which we establish Chernoff bounds on the likelihood of estimation error in a general multistage combination of measurement sampling and aggregation. We derive the scale against which errors are measured, in terms of the constituent sampling and aggregation operations. In particular this enables us to obtain rigorous confidence intervals around any given estimate. We apply our method to a number of sampling schemes both in the literature and currently deployed, including sampling of packet sampled NetFlow records, Sample and Hold, and Flow Slicing. We obtain one particularly striking result in the first case: that for a range of parameterizations, packet sampling has no additional impact on the estimator confidence derived from our bound, beyond that already imposed by flow sampling.
Tracking in a spaghetti bowl
Authors: Anandkumar Animashree , Bisdikian Chatschik , Agrawal Dakshi
Published: July 2008

The problem of tracking end-to-end service-level transactions in the absence of instrumentation support is considered. The transaction instances progress through a state-transition model and generate time-stamped footprints on entering each state in the model. The goal is to track individual transactions using these footprints even when the footprints may not contain any tokens uniquely identifying the transaction instances that generated them. Assuming a semi-Markov process model for state transitions, the transaction instances are tracked probabilistically by matching them to the available footprints according to the maximum likelihood (ML) criterion. Under the ML-rule, for a two-state system, it is shown that the probability that all the instances are matched correctly is minimized when the transition times are i.i.d. exponentially distributed. When the transition times are i.i.d. distributed, the ML-rule reduces to a minimum weight bipartite matching and reduces further to a first-in first-out match for a special class of distributions. For a multi-state model with an acyclic state transition digraph, a constructive proof shows that the ML-rule reduces to splicing the results of independent matching of many bipartite systems.
Optimal sampling in state space models with applications to network monitoring
Authors: Singhal Harsh , Michailidis George
Published: July 2008

Advances in networking technology have enabled network engineers to use sampled data from routers to estimate network flow volumes and track them over time. However, low sampling rates result in large noise in traffic volume estimates. We propose to combine data on individual flows obtained from sampling with highly aggregate data obtained from SNMP measurements (similar to those used in network tomography) for the tracking problem at hand. Specifically, we introduce a linearized state space model for the estimation of network traffic flow volumes from combined SNMP and sampled data. Further, we formulate the problem of obtaining optimal sampling rates under router resource constraints as an experiment design problem. Theoretically it corresponds to the problem of optimal design for estimation of conditional means for state space models and we present the associated convex programs for a simple approach to it. The usefulness of the approach in the context of network monitoring is illustrated through an extensive numerical study.
On the design of hybrid peer-to-peer systems
Authors: Ioannidis Stratis , Marbach Peter
Published: July 2008

In this paper, we consider hybrid peer-to-peer systems where users form an unstructured peer-to-peer network with the purpose of assisting a server in the distribution of data. We present a mathematical model that we use to analyze the scalability of hybrid peer-to-peer systems under two query propagation mechanisms: the random walk and the expanding ring. In particular, we characterize how the query load at the server, the load at peers as well as the query response time scale as the number of users in the peer-to-peer network increases. We show that, under a properly designed random walk propagation mechanism, hybrid peer-to-peer systems can support an unbounded number of users while requiring only bounded resources both at the server and at individual peers. This important result shows that hybrid peer-to-peer systems have excellent scalability properties. To the best of our knowledge, this is the first time that a theoretical study characterizing the scalability of such hybrid peer-to-peer systems has been presented. We illustrate our results through numerical studies.
Utility maximization in peer-to-peer systems
Authors: Chen Minghua , Ponec Miroslav , Sengupta Sudipta , Li Jin , Chou Philip A.
Published: July 2008

In this paper, we study the problem of utility maximization in P2P systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. This may be understood as extending Kelly's seminal framework from single-path unicast over general topology to multi-path multicast over P2P topology, with network coding allowed. For certain classes of popular P2P topologies, we show that routing along a linear number of trees per source can achieve the largest rate region that can be possibly obtained by (multi-source) network coding. This simplification result allows us to develop a new multi-tree routing formulation for the problem. Despite of the negative results in literature on applying Primal-dual algorithms to maximize utility under multi-path settings, we have been able to develop a Primal-dual distributed algorithm to maximize the aggregate utility under the multi-path routing environments. Utilizing our proposed sufficient condition, we show global exponential convergence of the Primal-dual algorithm to the optimal solution under different P2P communication scenarios we study. The algorithm can be implemented by utilizing only end-to-end delay measurements between P2P nodes; hence, it can be readily deployed on today's Internet. To support this claim, we have implemented the Primal-dual algorithm for use in a peer-assisted multi-party conferencing system and evaluated its performance through actual experiments on a LAN testbed and the Internet.
A queueing system for modeling a file sharing principle
Authors: Simatos Florian , Robert Philippe , Guillemin Fabrice
Published: July 2008

We investigate in this paper the performance of a simple file sharing principle. For this purpose, we consider a system composed of N peers becoming active at exponential random times; the system is initiated with only one server offering the desired file and the other peers after becoming active try to download it. Once the file has been downloaded by a peer, this one immediately becomes a server. To investigate the transient behavior of this file sharing system, we study the instant when the system shifts from a congested state where all servers available are saturated by incoming demands to a state where a growing number of servers are idle. In spite of its apparent simplicity, this queueing model (with a random number of servers) turns out to be quite difficult to analyze. A formulation in terms of an urn and ball model is proposed and corresponding scaling results are derived. These asymptotic results are then compared against simulations.
Path-quality monitoring in the presence of adversaries
Authors: Goldberg Sharon , Xiao David , Tromer Eran , Barak Boaz , Rexford Jennifer
Published: July 2008

Edge networks connected to the Internet need effective monitoring techniques to drive routing decisions and detect violations of Service Level Agreements (SLAs). However, existing measurement tools, like ping, traceroute, and trajectory sampling, are vulnerable to attacks that can make a path look better than it really is. In this paper, we design and analyze path-quality monitoring protocols that reliably raise an alarm when the packet-loss rate and delay exceed a threshold, even when an adversary tries to bias monitoring results by selectively delaying, dropping, modifying, injecting, or preferentially treating packets.

Despite the strong threat model we consider in this paper, our protocols are efficient enough to run at line rate on high-speed routers. We present a secure sketching protocol for identifying when packet loss and delay degrade beyond a threshold. This protocol is extremely lightweight, requiring only 250-600 bytes of storage and periodic transmission of a comparably sized IP packet to monitor billions of packets. We also present secure sampling protocols that provide faster feedback and accurate round-trip delay estimates, at the expense of somewhat higher storage and communication costs. We prove that all our protocols satisfy a precise definition of secure path-quality monitoring and derive analytic expressions for the trade-off between statistical accuracy and system overhead. We also compare how our protocols perform in the client-server setting, when paths are asymmetric, and when packet marking is not permitted.
In search of the elusive ground truth
Authors: Oliveira Ricardo V. , Pei Dan , Willinger Walter , Zhang Beichuan , Zhang Lixia
Published: July 2008

Despite significant efforts to obtain an accurate picture of the Internet's actual connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper we assess the quality of the inferred Internet maps through case studies of a set of ASes. These case studies allow us to establish the ground truth of AS-level Internet connectivity between the set of ASes and their directly connected neighbors. They also enable a direct comparison between the ground truth and inferred topology maps and yield new insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, and which parts are missing and why. This information is critical in assessing for what kinds of real-world networking problems the use of currently inferred AS maps or proposed AS topology models are, or are not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.
Ironmodel
Authors: Thereska Eno , Ganger Gregory R.
Published: July 2008

Traditional performance models are too brittle to be relied on for continuous capacity planning and performance debugging in many computer systems. Simply put, a brittle model is often inaccurate and incorrect. We find two types of reasons why a model's prediction might diverge from the reality: (1) the underlying system might be misconfigured or buggy or (2) the model's assumptions might be incorrect. The extra effort of manually finding and fixing the source of these discrepancies, continuously, in both the system and model, is one reason why many system designers and administrators avoid using mathematical models altogether. Instead, they opt for simple, but often inaccurate, "rules-of-thumb".

This paper describes IRONModel, a robust performance modeling architecture. Through studying performance anomalies encountered in an experimental cluster-based storage system, we analyze why and how models and actual system implementations get out-of-sync. Lessons learned from that study are incorporated into IRONModel. IRONModel leverages the redundancy of high-level system specifications described through models and low-level system implementation to localize many types of system-model inconsistencies. IRONModel can guide designers to the potential source of the discrepancy, and, if appropriate, can semi-automatically evolve the models to handle unanticipated inputs.
QDSL
Authors: Chaitanya Shiva , Urgaonkar Bhuvan , Sivasubramaniam Anand
Published: July 2008

A feature exhibited by many modern computing systems is their ability to improve the quality of output they generate for a given input by spending more computing resources on processing it. Often this improvement comes at the price of degraded performance in the form of reduced throughput or increased response time. We formulate QDSL, a class of constrained optimization problems defined in the context of a queueing server equipped with multiple levels of service. Solutions to QDSL provide rules for dynamically varying the service level to achieve desired trade-offs between output quality and performance. Our approach involves reducing restricted versions of such systems to Markov Decision Processes. We find two variants of such systems worth studying: (i) VarSL, in which a single request may be serviced using a combination of multiple levels during its lifetime and (ii) FixSL in which the service level may not change during the lifetime of a request. Our modeling indicates that optimal service level selection policies in these systems correspond to very simple rules that can be implemented very efficiently in realistic, online systems. We find our policies to be useful in two response-time-sensitive real-world systems: (i) qSecStore, an iSCSI-based secure storage system that has access to multiple encryption functions, and (ii) qPowServer, a server with DVFS-capable processor. As a representative result, in an instance of qSecStore serving disk requests derived from the well-regarded TPC-H traces, we are able to improve the fraction of requests using more reliable encryption functions by 40-60%, while meeting performance targets. In a simulation of qPowServer employing realistic DVFS parameters, we are able to improve response times significantly while only violating specified server-wide power budgets by less than 5W.
Performance bounds for peer-assisted live streaming
Authors: Liu Shao , Zhang-Shen Rui , Jiang Wenjie , Rexford Jennifer , Chiang Mung
Published: July 2008

Peer-assisted streaming is a promising way for service providers to offer high-quality IPTV to consumers at reasonable cost. In peer-assisted streaming, the peers exchange video chunks with one another, and receive additional data from the central server as needed. In this paper, we analyze how to provision resources for the streaming system, in terms of the server capacity, the video quality, and the depth of the distribution trees that deliver the content. We derive the performance bounds for minimum server load, maximum streaming rate, and minimum tree depth under different peer selection constraints. Furthermore, we show that our performance bounds are actually tight, by presenting algorithms for constructing trees that achieve our bounds.
Software thermal management of dram memory for multicore systems
Authors: Lin Jiang , Zheng Hongzhong , Zhu Zhichun , Gorbatov Eugene , David Howard , Zhang Zhao
Published: July 2008

Thermal management of DRAM memory has become a critical issue for server systems. We have done, to our best knowledge, the first study of software thermal management for memory subsystem on real machines. Two recently proposed DTM (Dynamic Thermal Management) policies have been improved and implemented in Linux OS and evaluated on two multicore servers, a Dell PowerEdge 1950 server and a customized Intel SR1500AL server testbed. The experimental results first confirm that a system-level memory DTM policy may significantly improve system performance and power efficiency, compared with existing memory bandwidth throttling scheme. A policy called DTM-ACG (Adaptive Core Gating) shows performance improvement comparable to that reported previously. The average performance improvements are 13.3% and 7.2% on the PowerEdge 1950 and the SR1500AL (vs. 16.3% from the previous simulation-based study), respectively. We also have surprising findings that reveal the weakness of the previous study: the CPU heat dissipation and its impact on DRAM memories, which were ignored, are significant factors. We have observed that the second policy, called DTM-CDVFS (Coordinated Dynamic Voltage and Frequency Scaling), has much better performance than previously reported for this reason. The average improvements are 10.8% and 15.3% on the two machines (vs. 3.4% from the previous study), respectively. It also significantly reduces the processor power by 15.5% and energy by 22.7% on average.
Interaction-aware energy management for wireless network cards
Authors: Crk Igor , Bi Mingsong , Gniady Chris
Published: July 2008

Wireless Network Interface Cards (WNICs) are part of every portable device, where efficient energy management plays a significant role in extending the device's battery life. The goal of efficient energy management is to match the performance of the WNIC to the network activity shaped by a running application. In the case of interactive applications on mobile systems, network I/O is largely driven by user interactions. Current solutions either require application modifications or lack a sufficient context of execution that is crucial in making accurate and timely predictions. This paper proposes a range of user-interaction-aware mechanisms that utilize a novel approach of monitoring a user's interaction with applications through the capture and classification of mouse events. This approach yields considerable improvements in energy savings and delay reductions of the WNIC, while significantly improving the accuracy, timeliness, and computational overhead of predictions when compared to existing state-of-the-art solutions.
Optimal delay scheduling in networks with arbitrary constraints
Authors: Jagabathula Srikanth , Shah Devavrat
Published: July 2008

We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that - for networks operating under primary interference constraints - guarantees a per-flow end-to-end packet delay bound of

5
d

j
/(1-

ρ
j

), at a factor 5 loss of throughput, where

d
j

is the path length (number of hops) of flow
j
and ρ

j

is the effective loading along the route of flow
j
. Clearly,

d
j

is a universal lower bound on end-to-end packet delay for flow
j
. Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of
O
(# of hops) in a constrained network.

Designing such a scheme comprises two related subproblems: Global Scheduling and Local Scheduling. Global Scheduling involves determining the set of links that will be simultaneously active, without violating the scheduling constraints. While local scheduling involves determining the packets that will be transferred across active edges. We design a local scheduling scheme by adapting the Preemptive Last-In-First-Out (PL) scheme, applied for quasi-reversible continuous time networks, to an unconstrained discrete-time network. A global scheduling scheme will be obtained by using stable marriage algorithms to emulate the unconstrained network with the constrained wireless network.

Our scheme can be easily extended to a network operating under general scheduling constraints, such as secondary interference constraints, with the same delay bound and a loss of throughput that depends on scheduling constraints through an intriguing "sub-graph covering" property.
Network distance estimation with dynamic landmark triangles
Authors: Wen Zhihua , Rabinovich Michael
Published: July 2008

This paper describes an efficient and accurate approach to estimate the network distance between arbitrary Internet hosts. We use three landmark hosts forming a triangle in two-dimensional space to estimate the distance between arbitrary hosts with simple trigonometrical calculations. To improve the accuracy of estimation, we dynamically choose the "best" triangle for a given pair of hosts using a heuristic algorithm. Our experiments show that this approach achieves both lower computational and network probing cost over the classic landmarks-based approach while producing more accurate estimates.
Class-of-service in ip backbones
Authors: Yuksel Murat , Ramakrishnan Kadangode K. , Kalyanaraman Shivkumar , Houle Joseph D. , Sadhvani Rita
Published: July 2008

The benefit of Class-of-Service (CoS) is an important topic in the "Network Neutrality" debate. Proponents of network neutrality suggest that over-provisioning is a viable alternative to CoS. We quantify the extra capacity requirement for an over-provisioned classless (i.e., best-effort) network compared to a CoS network providing the same delay or loss performance for premium traffic. We first develop a link model that quantifies this Required Extra Capacity (REC). For bursty and realistic traffic distributions, we find the REC using ns-2 simulation comparisons of the CoS and classless link cases. We use these link models to quantify the REC for realistic network topologies. We show that REC can be significant even when the proportion of premium traffic is small, a situation often considered benign for the over-provisioning alternative.
Predicting the resource consumption of network intrusion detection systems
Authors: Dreger Holger , Feldmann Anja , Paxson Vern , Sommer Robin
Published: July 2008

When installing network intrusion detection systems (NIDSs), operators are faced with a large number of parameters and analysis options for tuning trade-offs between detection accuracy versus resource requirements. In this work we set out to assist this process by understanding and predicting the CPU and memory consumption of such systems.
Combined intra- and inter-domain traffic engineering using hot-potato aware link weights optimization
Authors: Balon Simon , Leduc Guy
Published: July 2008

A well-known approach to intradomain traffic engineering consists in finding the set of link weights that minimizes a network-wide objective function for a given intradomain traffic matrix. This approach is inadequate because it ignores a potential impact on interdomain routing due to hot-potato routing policies. This may result in changes in the intradomain traffic matrix that have not been anticipated by the link weights optimizer, possibly leading to degraded network performance.

We propose a BGP-aware link weights optimization method that takes these hot-potato effects into account. This method uses the interdomain traffic matrix and other available BGP data, to extend the intradomain topology with external virtual nodes and links, on which all the well-tuned heuristics of a classical link weights optimizer can be applied. Our method can also optimize the traffic on the interdomain peering links.
Durability of replicated distributed storage systems
Authors: Ramabhadran Sriram , Pasquale Joseph
Published: July 2008

We study the problem of guaranteeing data durability [2] in distributed storage systems based on replication. Our work is motivated by several several recent efforts [3, 5, 1] to build such systems in a peer-to-peer environment. The key features of this environment which make achieving durability difficult are (1) data lifetimes may be several orders of magnitude larger than the lifetimes of individual storage units, and (2) the system may have little or no control over the participation of these storage units in the system. We use a model-based approach to develop engineering principles for designing automated replication and repair mechanisms to implement durability in such systems.
Implementation and evaluation of a migration-based NUCA design for chip multiprocessors
Authors: Li Feihui , Kandemir Mahmut , Irwin Mary J.
Published: July 2008

Chip Multiprocessors (CMPs) and Non-Uniform Cache Architectures (NUCAs) represent two emerging trends in computer architecture. Targeting future CMP based systems with NUCA type L2 caches, this paper proposes a novel data migration algorithm for parallel applications and evaluates it. The goal of this migration scheme is to determine a suitable location for each data block within a large L2 space at any given point during execution. A unique characteristic of the proposed scheme is that it models the problem of optimal data placement in the L2 cache space as a two dimensional post office placement problem, presents a practical architectural implementation of this model, and gives an evaluation of the proposed implementation.
Managing inter-domain traffic in the presence of bittorrent file-sharing
Authors: Seetharaman Srinivasan , Ammar Mostafa H.
Published: July 2008

Overlay routing operating in a selfish manner is known to cause undesired instability when it interacts with native layer routing. We observe similar selfish behavior with the BitTorrent protocol, where its performance-awareness causes it to constantly alter the routing decisions (peer and piece selection). This causes fluctuations in the load experienced by the underlying native network. By using real BitTorrent traces and a comprehensive simulation with different network characteristics, we show that BitTorrent systems easily disrupt the load balance across inter-domain links. Further, we find that existing native layer traffic management schemes suffer from several downsides and are not conducive to deployment. To resolve this dilemma, we propose two BitTorrent strategies that are effective in resolving the cross-layer conflict.
Scheduling with queue length guarantees for shared resource systems
Authors: Gupta Gagan R. , Shroff Ness B.
Published: July 2008

We develop a class of schemes called GMWM that guarantee optimal throughput for queuing systems with arbitrary constraints on the set of jobs that can be served simultaneously. We obtain an analytical upper bound on the expected queue length. To further tighten the upper bound, we formulate it as a convex optimization problem. We also show that whenever the arrival process is stabilizable, the scheme is guaranteed to achieve an expected queue length that is no larger than the expected queue length of any stationary randomized policy.
Estimating cardinality distributions in network traffic
Authors: Chen Aiyou , Li Li , Cao Jin
Published: July 2008

Information on network host connectivity patterns are important for network monitoring and traffic engineering. In this paper, an efficient streaming algorithm is proposed to estimate cardinality distributions including connectivity distributions, e.g. percent of hosts with any given number of distinct communicating peers or flows.
Weighted fair sharing for dynamic virtual clusters
Authors: Grit Laura E. , Chase Jeffrey S.
Published: July 2008

In a shared server infrastructure, a scheduler controls how quantities of resources are shared over time in a fair manner across multiple, competing consumers. It should support wide (parallel) requests for variable-sized pool of resources, provide assurance of minimum resource allotment on demand, and give predictable assignments. Our approach integrates a fair queuing algorithm with a calendar scheduler. We present WINKS, a proportional share allocation policy that addresses the needs of shared server environments. It extends start-time fair queuing to support wide requests with backfill, advance reservations, dynamic cluster sizing, dynamic request sizing, and intra-flow request prioritization. It also preserves fairness properties across queue transformations and calendar operations needed to implement these extensions.
Exploring the throughput-fairness tradeoff of deadline scheduling in heterogeneous computing environments
Authors: Sundaram Vasumathi , Chandra Abhishek , Weissman Jon
Published: July 2008

The scalability and computing power of large-scale computational platforms has made them attractive for hosting compute-intensive time-critical applications. Many of these applications are composed of computational tasks that require specific deadlines to be met for successful completion. In this paper, we show that combining redundant scheduling with deadline-based scheduling in these systems leads to a fundamental tradeoff between throughput and fairness. We propose a new scheduling algorithm called Limited Resource Earliest Deadline (LRED) that couples redundant scheduling with deadline-driven scheduling in a flexible way by using a simple tunable parameter to exploit this tradeoff. Our evaluation of LRED shows that LRED provides a powerful mechanism to achieve desired throughput or fairness under high loads and low timeliness environments.