bluuebunny/crossref_metadata_2025_split huggingface dataset:
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.
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.
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.
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.
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.
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.
Characterizing multiparty voice communication for multiplayer games
Authors: Papp Gabor , GauthierDickey Chris 
Published: July 2008

Over the last few years, the number of game players using voice communication to talk to each other while playing games has increased dramatically. In fact, many modern games and game consoles have added voice support instead of expecting third-party companies to provide this technology. Unlike traditional voice-over-IP technology, where most conversations are between two people, voice communication in games often has 5 or more people talking together as they play.
We present the first measurement study on the characteristics of multiparty voice communications. Over a 3 month period, we measured over 7,000 sessions on an active multi-party voice communication server to quantify the characteristics of communication generated by game players, including overall server traffic, group sizes, sessions characteristics, and speaking (and silence) durations.
Stability and fairness of explicit congestion control with small buffers
Authors: Kelly Frank , Raina Gaurav , Voice Thomas 
Published: July 2008

Rate control protocols that utilise explicit feedback from routers are able to achieve fast convergence to an equilibrium which approximates processor-sharing on a single bottleneck link, and hence such protocols allow short flows to complete quickly. For a network, however, processor-sharing is not uniquely defined but corresponds with a choice of fairness criteria, and proportional fairness has a reasonable claim to be the network generalization of processor-sharing.
In this paper, we develop a variant of RCP (rate control protocol) that achieves α-fairness when buffers are small, including proportional fairness as the case α = 1. At the level of theoretical abstraction treated, our model incorporates a general network topology, and heterogeneous propagation delays. For our variant of the RCP algorithm, we establish a simple decentralized sufficient condition for local stability.
An outstanding question for explicit congestion control is whether the presence of feedback based on queue size is helpful or not, given the presence of feedback based on rate mismatch. We show that, for the variant of RCP considered here, feedback based on queue size may cause the queue to be less accurately controlled.
A further outstanding question for explicit congestion control is the scale of the step-change in rate that is necessary at a resource to accommodate a new flow. We show that, for the variant of RCP considered here, this can be estimated from the aggregate flow through the resource, without knowledge of individual flow rates.
Applications of Fixed Point Theorems in the Theory of Generalized IFS
Authors: Mihail Alexandru , Miculescu Radu 
Published: July 2008

AbstractWe introduce the notion of a generalized iterated function system (GIFS), which is a finite family of functions "Equation missing", where "Equation missing" is a metric space and "Equation missing". In case that "Equation missing" is a compact metric space and the functions "Equation missing" are contractions, using some fixed point theorems for contractions from "Equation missing" to "Equation missing", we prove the existence of the attractor of such a GIFS and its continuous dependence in the "Equation missing"'s.
The Contribution of Ex–Tropical Cyclone Gert (1999) toward the Weakening of a Midlatitude Cyclogenesis Event
Authors: Agustí-Panareda Anna 
Published: July 2008

Abstract
Tropical Cyclone Gert (1999) experienced an extratropical transition while it merged with an extratropical cyclone upstream. The upstream extratropical cyclone had started to intensify before it merged with the transitioning tropical cyclone, and it continued intensifying afterward (12 hPa in 12 h, according to the Met Office analysis). The question addressed in this paper is the following: what was the impact of the transitioning tropical cyclone on this intensification of the upstream extratropical cyclone? Until now, in the literature, tropical cyclones that experience extratropical transition have been found to have either no impact or a positive impact on the development of extratropical cyclogenesis events. The positive impact involves either a triggering of the development of the extratropical cyclone or simply a contribution to its deepening. However, the case studied here proves to have a negative impact on the developing extratropical cyclone upstream by diminishing its intensification. Forecasts are performed with and without the tropical cyclone in the initial conditions. They show that when Gert is not present in the initial conditions, the peak intensity of the cyclone upstream occurs 9 h earlier and it is 10 hPa deeper than when Gert is present. Thus, Gert acts to weaken the development by contributing to the filling of the extratropical surface low upstream. Quasigeostropic (QG) diagnostics show that the negative impact on the extratropical development is linked to the fact that the transitioning tropical cyclone interacts with a warm front inducing a negative QG vertical velocity over the developing extratropical low upstream. This interpretation is consistent with other contrasting cases in which the transitioning tropical cyclone interacts with a cold front and induces a positive QG vertical velocity over the developing low upstream, thus enhancing its development. The results are also in agreement with idealized experiments in the literature that are aimed at studying the predictability of extratropical storms. These idealized experiments yielded similar results using synoptic-scale and mesoscale vortices as perturbations on warm and cold fronts.
Contributions of Mixed Physics versus Perturbed Initial/Lateral Boundary Conditions to Ensemble-Based Precipitation Forecast Skill
Authors: Clark Adam J. , Gallus William A. , Chen Tsing-Chang 
Published: July 2008

Abstract
An experiment is described that is designed to examine the contributions of model, initial condition (IC), and lateral boundary condition (LBC) errors to the spread and skill of precipitation forecasts from two regional eight-member 15-km grid-spacing Weather Research and Forecasting (WRF) ensembles covering a 1575 km × 1800 km domain. It is widely recognized that a skillful ensemble [i.e., an ensemble with a probability distribution function (PDF) that generates forecast probabilities with high resolution and reliability] should account for both error sources. Previous work suggests that model errors make a larger contribution than IC and LBC errors to forecast uncertainty in the short range before synoptic-scale error growth becomes nonlinear. However, in a regional model with unperturbed LBCs, the infiltration of the lateral boundaries will negate increasing spread. To obtain a better understanding of the contributions to the forecast errors in precipitation and to examine the window of forecast lead time before unperturbed ICs and LBCs begin to cause degradation in ensemble forecast skill, the “perfect model” assumption is made in an ensemble that uses perturbed ICs and LBCs (PILB ensemble), and the “perfect analysis” assumption is made in another ensemble that uses mixed physics–dynamic cores (MP ensemble), thus isolating the error contributions. For the domain and time period used in this study, unperturbed ICs and LBCs in the MP ensemble begin to negate increasing spread around forecast hour 24, and ensemble forecast skill as measured by relative operating characteristic curves (ROC scores) becomes lower in the MP ensemble than in the PILB ensemble, with statistical significance beginning after forecast hour 69. However, degradation in forecast skill in the MP ensemble relative to the PILB ensemble is not observed in an analysis of deterministic forecasts calculated from each ensemble using the probability matching method. Both ensembles were found to lack statistical consistency (i.e., to be underdispersive), with the PILB ensemble (MP ensemble) exhibiting more (less) statistical consistency with respect to forecast lead time. Spread ratios in the PILB ensemble are greater than those in the MP ensemble at all forecast lead times and thresholds examined; however, ensemble variance in the MP ensemble is greater than that in the PILB ensemble during the first 24 h of the forecast. This discrepancy in spread measures likely results from greater bias in the MP ensemble leading to an increase in ensemble variance and decrease in spread ratio relative to the PILB ensemble.
Analysis of the Wind Field Evolution Associated with the Extratropical Transition of Bonnie (1998)
Authors: Evans Clark , Hart Robert E. 
Published: July 2008

Abstract
Extratropical transition brings about a number of environmentally induced structural changes within a transitioning tropical cyclone. Of particular interest among these changes is the acceleration of the wind field away from the cyclone’s center of circulation along with the outward movement of the radial wind maximum, together termed wind field expansion. Previous informal hypotheses aimed at understanding this evolution do not entirely capture the observed expansion, while a review of the literature shows no formal work done upon the topic beyond analyzing its occurrence. This study seeks to analyze the physical and dynamical mechanisms behind the wind field expansion using model simulations of a representative transition case, North Atlantic Tropical Cyclone Bonnie of 1998. The acceleration of the wind field along the outer periphery of the cyclone is found to be a function of the net import of absolute angular momentum within the cyclone’s environment along inflowing trajectories. This evolution is shown to be a natural outgrowth of the development of isentropic conveyor belts and asymmetries associated with extratropical cyclones. Asymmetries in the outer-core wind field manifest themselves via the tightening and development of height and temperature gradients within the cyclone’s environment. Outward movement of the radial wind maximum occurs coincident with integrated net cooling found inside the radius of maximum winds. Tests using a secondary circulation balance model show the radial wind maximum evolution to be similar yet opposite to the response noted for intensifying tropical cyclones with contracting eyewalls.
Assimilation of Simulated Polarimetric Radar Data for a Convective Storm Using the Ensemble Kalman Filter. Part I: Observation Operators for Reflectivity and Polarimetric Variables
Authors: Jung Youngsun , Zhang Guifu , Xue Ming 
Published: July 2008

Abstract
A radar simulator for polarimetric radar variables, including reflectivities at horizontal and vertical polarizations, the differential reflectivity, and the specific differential phase, has been developed. This simulator serves as a test bed for developing and testing forward observation operators of polarimetric radar variables that are needed when directly assimilating these variables into storm-scale numerical weather prediction (NWP) models, using either variational or ensemble-based assimilation methods. The simulator takes as input the results of high-resolution NWP model simulations with ice microphysics and produces simulated polarimetric radar data that may also contain simulated errors. It is developed based on calculations of electromagnetic wave propagation and scattering at the S band of wavelength 10.7 cm in a hydrometeor-containing atmosphere. The T-matrix method is used for the scattering calculation of raindrops and the Rayleigh scattering approximation is applied to snow and hail particles. The polarimetric variables are expressed as functions of the hydrometeor mixing ratios as well as their corresponding drop size distribution parameters and densities. The presence of wet snow and wet hail in the melting layer is accounted for by using a new, relatively simple melting model that defines the water fraction in the melting snow or hail. The effect of varying density due to the melting snow or hail is also included. Vertical cross sections and profiles of the polarimetric variables for a simulated mature multicellular squall-line system and a supercell storm show that polarimetric signatures of the bright band in the stratiform region and those associated with deep convection are well captured by the simulator.