bluuebunny/crossref_metadata_2025 huggingface dataset:
A Content Aware Integer Register File Organization
Authors: Gonzalez Gonzalez , Cristal Adrian , Ortega Daniel , Veidenbaum Alexander , Valero Mateo
Published: January 2005

A register file is a critical component of a modernsuperscalar processor.It has a large number of entriesand read/write ports in order to enable high levels ofinstruction parallelism.As a result, the register file'sarea, access time, and energy consumption increasedramatically, significantly affecting the overallsuperscalar processor's performance and energyconsumption.This is especially true in 64-bitprocessors.This paper presents a new integer register fileorganization, which reduces energy consumption,area, and access time of the register file with a minimal effect on overall IPC.This is accomplished byexpoiting a new concept, partial value locality, whichis defined as occurence of mutiple live valueinstances identical in a subset of their bits.A possibleimplementation of the new register file is describedand shown to obtain proposed optimized register filedesigns.Overall, an energy reduction of over 50%, a18% decreas in area, and a 15% reduction in the accesstime are achieved in the new register file.Theenergy and area savings are achieved with a 1.7%reduction in IPC for integer applications and anegligible 0.3% in numerical applications, assumingthe same clock frequency.A performance increase ofup to 13% is possible if the clcok frequency can beincreases due to a reduction in the register file accesstime.This approach enables other, very promisingoptimizations, three of which are outlined in the paper.
Physical Register Inlining
Authors: Lipasti Mikko H. , Mestan Brian R. , Gunadi Erika
Published: January 2005

Physical register access time increases the delaybetween scheduling and execution in modern out-of-orderprocessors. As the number of physical registers increases,this delay grows, forcing designers to employ register fileswith multicycle access. This paper advocates more efficientutilization of a fewer number of physical registers in orderto reduce the access time of the physical register file. Registervalues with few significant bits are stored in the renamemap using physical register inlining, a scheme analogous toinlining of operand fields in data structures. Specifically,whenever a register value can be expressed with fewer bitsthan the register map would need to specify a physical registernumber, the value is stored directly in the map, avoidingthe indirection, and saving space in the physical register file.Not surprisingly, we find that a significant portion of all registeroperands can be stored in the map in this fashion, anddescribe straightforward microarchitectural extensions thatcorrectly implement physical register inlining. We find thatphysical register inlining performs well, particularly in processorsthat are register-constrained.
A First-Order Superscalar Processor Model
Authors: Karkhanis Tejas S. , Smith James E.
Published: January 2005

A proposed performance model for superscalar processorsconsists of 1) a component that models the relationshipbetween instructions issued per cycle and the sizeof the instruction window under ideal conditions, and 2)methods for calculating transient performance penaltiesdue to branch mispredictions, instruction cache misses,and data cache misses.Using trace-derived data dependenceinformation, data and instruction cache miss rates,and branch miss-prediction rates as inputs, the model canarrive at performance estimates for a typical superscalarprocessor that are within 5.8% of detailed simulation onaverage and within 13% in the worst case. The modelalso provides insights into the workings of superscalarprocessors and long-term microarchitecture trends such aspipeline depths and issue widths.
Control Flow Modeling in Statistical Simulation for Accurate and Efficient Processor Design Studies
Authors: Eeckhout Lieven , Bell Jr. Robert H. , Stougie Bastiaan , De Bosschere Koen , John Lizy K.
Published: January 2005

Designing a new microprocessor is extremely time-consuming.One of the contributing reasons is that computerdesigners rely heavily on detailed architectural simulations,which are very time-consuming. Recent workhas focused on statistical simulation to address this issue.The basic idea of statistical simulation is to measurecharacteristics during program execution, generate asynthetic trace with those characteristics and then simulatethe synthetic trace. The statistically generated synthetictrace is orders of magnitude smaller than the original programsequence and hence results in significantly fastersimulation.This paper makes the following contributions to the statisticalsimulation methodology. First, we propose the useof a statistical flow graph to characterize the control flow ofa program execution. Second, we model delayed update ofbranch predictors while profiling program execution characteristics.Experimental results show that statistical simulationusing this improved control flow modeling attainssignificantly better accuracy than the previously proposedHLS system. We evaluate both the absolute and the relativeaccuracy of our approach for power/performance modelingof superscalar microarchitectures. The results showthat our statistical simulation framework can be used to efficientlyexplore processor design spaces.
Extended Split-Issue
Authors: Iyer Bharath , Srinivasan Sadagopan , Jacob Bruce
Published: January 2005

VLIW architecture based DSPs have become widespread due to thecombined benefits of simple hardware and compiler-extractedinstruction-level parallelism. However, the VLIW instruction setarchitecture and its hardware implementation are tightly coupled,especially so for Non-Unit Assumed Latency (NUAL) VLIWs. Theproblem of object code compatibility across processors having differentnumbers of functional units or hardware latencies has beenthe Achilles' heel of this otherwise powerful architecture. In thispaper, we propose eXtended Split-Issue (XSI), a novel mechanismthat breaks the instruction packet syntax of an NUAL VLIW compilerwithout violating the dataflow dependences. XSI provides a designerthe freedom of disassociating the hardware implementation of theNUAL VLIW processor from the instruction set architecture. Further,we investigate fairly radical (in the context of VLIW) changes to thehardware-like removing an adder, adding a multiplier, and incorporatingsimultaneous multithreading (SMT)-to show that ourtechnique works for a variety of hardware configurations withoutcompromising on performance. The technique can be used in bothsingle-threaded and multi-threaded architectures to achieve a levelof flexibility heretofore unavailable in the VLIW arena.
Evaluation of the Raw Microprocessor
Authors: Taylor Michael Bedford , Lee Walter , Miller Jason , Wentzlaff David , Bratt Ian , Greenwald Ben , Hoffmann Henry , Johnson Paul , Kim Jason , Psota James , Saraf Arvind , Shnidman Nathan , Strumpen Volker , Frank Matt , Amarasinghe Saman , Agarwal Anant
Published: January 2005

This paper evaluates the Raw microprocessor. Raw addresses thechallenge of building a general-purpose architecture that performswell on a larger class of stream and embedded computing applicationsthan existing microprocessors, while still running existingILP-based sequential programs with reasonable performance in theface of increasing wire delays. Raw approaches this challenge byimplementing plenty of on-chip resources - including logic, wires,and pins - in a tiled arrangement, and exposing them through a newISA, so that the software can take advantage of these resources forparallel applications. Raw supports both ILP and streams by routingoperands between architecturally-exposed functional units overa point-to-point scalar operand network. This network offers lowlatency for scalar data transport. Raw manages the effect of wiredelays by exposing the interconnect and using software to orchestrateboth scalar and stream data transport.We have implemented a prototype Raw microprocessor in IBM's180 nm, 6-layer copper, CMOS 7SF standard-cell ASIC process. Wehave also implemented ILP and stream compilers. Our evaluationattempts to determine the extent to which Raw succeeds in meetingits goal of serving as a more versatile, general-purpose processor.Central to achieving this goal is Raw's ability to exploit all formsof parallelism, including ILP, DLP, TLP, and Stream parallelism.Specifically, we evaluate the performance of Raw on a diverse setof codes including traditional sequential programs, streaming applications,server workloads and bit-level embedded computation.Our experimental methodology makes use of a cycle-accurate simulatorvalidated against our real hardware. Compared to a 180 nmPentium-III, using commodity PC memory system components, Rawperforms within a factor of 2x for sequential applications with a verylow degree of ILP, about 2x to 9x better for higher levels of ILP, and10x-100x better when highly parallel applications are coded in astream language or optimized by hand. The paper also proposes anew versatility metric and uses it to discuss the generality of Raw.
Evaluating the Imagine Stream Architecture
Authors: Ahn Jung Ho , Dally William J. , Khailany Brucek , Kapasi Ujval J. , Das Abhishek
Published: January 2005

This paper describes an experimental evaluation of theprototype Imagine stream processor. Imagine [Imagine: Media processing with streams] is a stream processor that employs a two-level register hierarchy with9.7 Kbytes of local register file capacity and 128 Kbytesof stream register file (SRF) capacity to capture producer-consumerlocality in stream applications. Parallelism is exploitedusing an array of 48 floating-point arithmetic unitsorganized as eight SIMD clusters with a 6-wide VLIW percluster. We evaluate the performance of each aspect ofthe Imagine architecture using a set of synthetic micro-benchmarks,key media processing kernels, and full applications.These micro-benchmarks show that the prototypehardware can attain 7.96 GFLOPS or 25.4 GOPS of arithmeticperformance, 12.7 Gbytes/s of SRF bandwidth, 1.58Gbytes/s of memory system bandwidth, and accept up to2 million stream processor instructions per second from ahost processor.On a set of media processing kernels, Imagine sustainedan average of 43% of peak arithmetic performance. Anevaluation of full applications provides a breakdown ofwhere execution time is spent. Over full applications, Imagineachieves 39.4% of peak performance, of the remainderon average 36.4% of time is lost due to load imbalancebetween arithmetic units in the VLIW clusters and limitedinstruction-level parallelism within kernel inner loops,10.6% is due to kernel startup and shutdown overhead becauseof short stream lengths, 7.6% is due to memory stalls,and the rest is due to insufficient host processor bandwidth.Further analysis included in the paper presents the impactof host instruction bandwidth on application performance,particularly on smaller datasets. In summary, the experimentalmeasurements described in this paper demonstratethe high performance and efficiency of stream processing:operating at 200 MHz, Imagine sustains 4.81 GFLOPS onQR decomposition while dissipating 7.42 Watts.
You Don’t Know Jack About VoIP
Authors: Sherburne Phil , Fitzgerald Cary
Published: January 2005

Telecommunications worldwide has experienced a significant revolution over recent years. The long-held promise of network convergence is occurring at an increasing pace. This convergence of data, voice, and video using IP-based networks is delivering advanced services at lower cost across the spectrum, including residential users, business customers of varying sizes, and service providers.
Not Your Father’s PBX?
Authors: Coffman James E.
Published: January 2005

Perhaps no piece of office equipment is more taken for granted than the common business telephone. The technology behind this basic communication device, however, is in the midst of a major transformation. Businesses are now converging their voice and data networks in order to simplify their network operations and take advantage of the new functional benefits and capabilities that a converged network delivers from greater productivity and cost savings to enhanced mobility.
VoIP: What is it Good for?
Authors: Ahuja Sudhir R. , Ensor Robert
Published: January 2005

VoIP (voice over IP) technology is a rapidly expanding field. More and more VoIP components are being developed, while existing VoIP technology is being deployed at a rapid and still increasing pace. This growth is fueled by two goals: decreasing costs and increasing revenues.
VoIP Security: Not an Afterthought
Authors: Sicker Douglas C. , Lookabaugh Tom
Published: January 2005

Voice over IP (VoIP) promises to up-end a century-old model of voice telephony by breaking the traditional monolithic service model of the public switched telephone network (PSTN) and changing the point of control and provision from the central office switch to the end user’s device. Placing intelligence at the edge, in the Internet tradition, has a number of consequences: a wider community of developers - in particular the large community of Web service developers - can work on voice applications; open interfaces and decomposable functionality facilitate multi-vendor and homegrown solutions; and open source and nonproprietary software development can facilitate innovation and experimentation.
A Time and a Place for Standards
Authors: Bell Gordon
Published: January 2005

Over the next decade, we will encounter at least three major opportunities where success will hinge largely on our ability to define appropriate standards. That’s because intelligently crafted standards that surface at just the right time can do much to nurture nascent industries and encourage product development simply by creating a trusted and reliable basis for interoperability. From where I stand, the three specific areas I see as particularly promising are: (1) all telecommunications and computing capabilities that work together to facilitate collaborative work; (2) hybrid computing/home entertainment products providing for the online distribution of audio and/or video content; and (3) wireless sensor and network platforms (the sort that some hope the 802.15.4 and ZigBee Alliance standards will ultimately enable). No doubt there will be others, but for the purposes of this discussion, these should suffice.
From the Editors: Calling All Readers
Authors: Grossman Edward
Published: January 2005

OK, kidding aside, we’ve got a great VoIP (voice over IP) special report this month, and typically I’d use this space to tell you a little bit about how we came to the topic, how Lucy Sanders (a former R&D VP at VoIP powehouse Avaya) helped us identify the key areas - and authors - in this industry. Instead, however, I’ve decided to ask myself, and you (after all, there are more than 30,000 of you), if anyone really cares about all that.
Schizoid Classes
Authors: Bates Rodney
Published: January 2005

Smalltalk pays a high price elsewhere for taking object orientation to the extreme, notably in complete loss of static typing and serious runtime efficiency penalties. Special, one-instance forms of classes are, for many pro- gramming problems, not as good a conceptual match as modules. But at least it provides a single, consistent, and syntactically explicit call mechanism.
It's about time
Authors: Marcus Aaron
Published: January 2005

What is it about time that fascinates us so much? Perhaps we are challenged because time is not resident in any particular object that we can hold, but we can see its effects when we stare at the sweeping second hand, at leaves turning a color for another cycle of the seasons, or at the face of an old friend whom we have not seen in years. We become aware of time if we are forced to sit still, or look at speeded-up or slowed-down (time-lapse) photography, film, or video, but most often when we see the world in motion, dynamically evolving. Philosophers, poets, physicists, painters, and psychologists have spent their lives analyzing the etiology (causes and beginnings), ontology (essence), eschatology (end), and epistemology (what we can know) of time. Across most civilizations, cultures, and historic epochs, analysts and synthesizers (that is, designers) have tried to explore what we understand about time and how we can use this knowledge.
When good things happen to bad products
Authors: Jokela Timo
Published: January 2005

Consider the following three stories about usability and consumer appliances.

• A cellular phone with significant usability problems was launched. Still, the product was a great sales success and many users even seemed to have enjoyed using the product.

• A new generation game device was developed. It had usability problems that led to wide-spread user dissatisfaction and the reputation of the product was severely damaged.

• Some users of a new generation smart phone were happy with the product while others rejected it, finding its usability problems intolerable.
Calculation of confidence intervals for simulation output
Authors: Cheng R. C. H. , Holland W.
Published: January 2005

This article is concerned with the calculation of confidence intervals for simulation output that is dependent on two sources of variability. One, referred to as simulation variability, arises from the use of random numbers in the simulation itself; and the other, referred to as parameter variability, arises when the input parameters are unknown and have to be estimated from observed data. Three approaches to the calculation of confidence intervals are presented--the traditional asymptotic normality theory approach, a bootstrap approach and a new method which produces a conservative approximation based on performing just two simulation runs at carefully selected parameter settings. It is demonstrated that the traditional and bootstrap approaches provide similar degrees of accuracy and that whilst the new method may sometimes be very conservative, it can be calculated in a small fraction of the computational time of the exact methods.
An asynchronous integration and event detection algorithm for simulating multi-agent hybrid systems
Authors: Esposito Joel M. , Kumar Vijay
Published: January 2005

A simulation algorithm is presented for multi-agent hybrid systems---systems consisting of many sets of nonsmooth differential equations---such as systems involving multiple rigid bodies, vehicles, or airplanes. The differential equations are partitioned into coupled subsystems, called "agents"; and the conditions which trigger the discontinuities in the derivatives, called "events", may depend on the global state vector. Such systems normally require significant computational resources to simulate because a global time step is used to ensure the discontinuity is properly handled. When the number of systems is large, forcing all system to be simulated at the same rate creates a computational bottleneck, dramatically decreasing efficiency. By using a control systems approach for selecting integration step sizes, we avoid using a global time step. Each subsystem can be simulated asynchronously when the state is away from the event. As the state approaches the event, the simulation is able to synchronize each of the local time clocks in such a way that the discontinuities are properly handled without the need for "roll back". The algorithm's operation and utility is demonstrated on an example problem inspired by autonomous highway vehicles. Using a combination of stochastic modelling and numerical experiments we show that the algorithm requires significantly less computation time when compared with traditional simulation techniques for such problems, and scales more favorably with problem size.
Modeling of discrete event systems
Authors: Bobeanu Carmen-Veronica , Kerckhoffs Eugene J. H. , Landeghem Hendrik Van
Published: January 2005

In this article, the authors provide an alternative view on Petri nets modeling of discrete event systems. The proposed modeling procedure follows the Systems Specification guidelines underlying the well-known DEVS modeling formalism. The authors' endeavour is towards perfecting the design of reusable Petri nets-based models by searching for a good primitive for a modular model construction and the introduction of coupling templates as standardised means to couple building block components. Assuming that the real-world system to be modeled has been analyzed in depth beforehand through a suitable system analysis method (which itself is beyond the scope of the article), we present a systematic step-by-step approach to construct a model in the Petri nets domain together with its experimental frame. The construction adheres to well-defined rules, which enable computer-based model construction. The input for this systematic bottom-up construction of Petri nets-models is information (about, e.g., primitive system components, entity flows, routing constructs) gathered from the top-down system analysis. In the article, attention is also paid to the algebraic backgrounds underlying the proposed model construction. These provide the basis for formal correctness proofs, mapping Petri nets onto DEVS-models, and complexity reduction of the found Petri nets-models. By offering to the model builder the possibility to handle multiple abstraction levels and by addressing important issues related to the interfacing question of coupled models and model components described in Petri nets and DEVS formalism, the authors' work addresses two of the main research directions of Computer Automated Multi-Paradigm Modeling ([Mosterman and Vangheluwe 2002]): model abstraction and multiformalism modeling. The article concludes with an illustrative application example.
Visualization strategies and tools for enhancing customer relationship management
Authors: Ganapathy Shobha , Ranganathan C. , Sankaranarayanan Balaji
Published: January 2005

Web sites that make it too cumbersome for customers to search and purchase products online will never enjoy a competitive edge. Fortunately, there are many visualization tools and techniques available that may be just what the customers' ordered.
Remote repair, diagnostics, and maintenance
Authors: Biehl Markus , Prater Edmund , McIntyre John R.
Published: January 2005

An overview and comparison of the U.S., Japanese, and German machine tool industries.
What Americans like about being online
Authors: Stafford Thomas F. , Gonier Dennis
Published: January 2005

A study of AOL users finds they are particularly gratified using the Net as a source of information, communication, and socializing---results that may be helpful to ISPs in their efforts to attract and retain users.
Is this a revolutionary idea, or not?
Authors: Glass Robert L.
Published: January 2005

Assembling the individual pieces to form an integrated component architecture.
Globalization and the American IT worker
Authors: Matloff Norman
Published: January 2005

Exporting IT jobs and importing IT workers not only harms U.S. IT workers, it also harms U.S. firms and the broader economy.
Nanoscience fact versus fiction
Authors: Donaldson Ken , Stone Vicki
Published: January 2005

With all the excitement over the potential of nanotechnology, has any research addressed the potential toxicity nanoparticles may have on our health and environment?
Teaching key topics in computer science and information systems through a web search engine project
Authors: Chau Michael , Huang Zan , Chen Hsinchun
Published: January 2005

Advances in computer and Internet technologies have made it more and more important for information technology professionals to acquire experience in a variety of aspects, including new technologies, system integration, database administration, and project management. To provide students with a chance to acquire such skills, we designed a project called "Build Your Search Engine in 90 Days," in which students were required to build a domain-specific Web search engine in a semester. In this paper we review the tools and resources available to students and report our experiences in having students to work on this project in a course at the University of Arizona. We also review two tools, called AI Spider and AI Indexer, we developed for students in this project. We highlight a few search engines that were created by the students and suggest some future directions in improving the tools and expanding the project.
Vivaldi
Authors: Dabek Frank , Cox Russ , Kaashoek Frans , Morris Robert
Published: January 2005

Large-scale Internet applications can benefit from an ability to predict round-trip times to other hosts without having to contact them first. Explicit measurements are often unattractive because the cost of measurement can outweigh the benefits of exploiting proximity information. Vivaldi is a simple, light-weight algorithm that assigns synthetic coordinates to hosts such that the distance between the coordinates of two hosts accurately predicts the communication latency between the hosts. Vivaldi is fully distributed, requiring no fixed network infrastructure and no distinguished hosts. It is also efficient: a new host can compute good coordinates for itself after collecting latency information from only a few other hosts. Because it requires little com-munication, Vivaldi can piggy-back on the communication patterns of the application using it and scale to a large number of hosts. An evaluation of Vivaldi using a simulated network whose latencies are based on measurements among 1740 Internet hosts shows that a 2-dimensional Euclidean model with
height vectors
embeds these hosts with low error (the median relative error in round-trip time prediction is 11 percent).
Routing design in operational networks
Authors: Maltz David A. , Xie Geoffrey , Zhan Jibin , Zhang Hui , Hjálmtýsson Gísli , Greenberg Albert
Published: January 2005

In any IP network, routing protocols provide the intelligence that takes a collection of physical links and transforms them into a network that enables packets to travel from one host to another. Though routing design is arguably the single most important design task for large IP networks, there has been very little systematic investigation into how routing protocols are actually used in production networks to implement the goals of network architects. We have developed a methodology for reverse engineering a coherent global view of a network's routing design from the static analysis of dumps of the local configuration state of each router. Starting with a set of 8,035 configuration files, we have applied this method to 31 production networks. In this paper we present a detailed examination of how routing protocols are used in operational networks. In particular, the results show the conventional model of "interior" and "exterior" gateway protocols is insufficient to describe the diverse set of mechanisms used by architects, and we provide examples of the more unusual designs and examine their trade-offs. We discuss the strengths and weaknesses of our methodology, and argue that it opens paths towards new understandings of network behavior and design.
An algebraic approach to practical and scalable overlay network monitoring
Authors: Chen Yan , Bindel David , Song Hanhee , Katz Randy H.
Published: January 2005

Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with
n
end hosts, existing systems either require
O
(
n
2
) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Our earlier extended abstract [1] briefly proposes an algebraic approach that selectively monitors
k
linearly independent paths that can fully describe all the
O
(
n
2
) paths. The loss rates and latency of these
k
paths can be used to estimate the loss rates and latency of all other paths. Our scheme only assumes knowledge of the underlying IP topology, with links dynamically varying between lossy and normal.In this paper, we improve, implement and extensively evaluate such a monitoring system. We further make the following contributions: i) scalability analysis indicating that for reasonably large
n
(
e.g.
, 100), the growth of
k
is bounded as
O
(
n
log
n
), ii) efficient adaptation algorithms for topology changes, such as the addition or removal of end hosts and routing changes, iii) measurement load balancing schemes, and iv) topology measurement error handling. Both simulation and Internet experiments demonstrate we obtain highly accurate path loss rate estimation while adapting to topology changes within seconds and handling topology errors.
CapProbe
Authors: Kapoor Rohit , Chen Ling-Jyh , Lao Li , Gerla Mario , Sanadidi M. Y.
Published: January 2005

We present a new capacity estimation technique, called CapProbe. CapProbe combines delay as well as dispersion measurements of packet pairs to filter out samples distorted by cross-traffic. CapProbe algorithms include convergence tests and convergence speed-up techniques by varying probing parameters. Our study of CapProbe includes a probability analysis to determine the time it takes CapProbe to converge on the average. Through simulations and measurements, we found CapProbe to be quick and accurate across a wide range of traffic scenarios. We also compared CapProbe with two previous well-known techniques, pathchar and pathrate. We found CapProbe to be much more accurate than pathchar and similar in accuracy to pathrate, while providing faster estimation than both. Another advantage of CapProbe is its lower computation cost, since no statistical post processing of probing data is required.
Routing in a delay tolerant network
Authors: Jain Sushant , Fall Kevin , Patra Rabin
Published: January 2005

We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.
A system for authenticated policy-compliant routing
Authors: Raghavan Barath , Snoeren Alex C.
Published: January 2005

Internet end users and ISPs alike have little control over how packets are routed outside of their own AS, restricting their ability to achieve levels of performance, reliability, and utility that might otherwise be attained. While researchers have proposed a number of source-routing techniques to combat this limitation, there has thus far been no way for independent ASes to ensure that such traffic does not circumvent local traffic policies, nor to accurately determine the correct party to charge for forwarding the traffic.We present Platypus, an authenticated source routing system built around the concept of network capabilities. Network capabilities allow for accountable, fine-grained path selection by cryptographically attesting to policy compliance at each hop along a source route. Capabilities can be composed to construct routes through multiple ASes and can be delegated to third parties. Platypus caters to the needs of both end users and ISPs: users gain the ability to pool their resources and select routes other than the default, while ISPs maintain control over where, when, and whose packets traverse their networks. We describe how Platypus can be used to address several well-known issues in wide-area routing at both the edge and the core, and evaluate its performance, security, and interactions with existing protocols. Our results show that incremental deployment of Platypus can achieve immediate gains.
Locating internet routing instabilities
Authors: Feldmann Anja , Maennel Olaf , Mao Z. Morley , Berger Arthur , Maggs Bruce
Published: January 2005

This paper presents a methodology for identifying the autonomous system (or systems) responsible when a routing change is observed and propagated by BGP. The origin of such a routing instability is deduced by examining and correlating BGP updates for many prefixes gathered at many observation points. Although interpreting BGP updates can be perplexing, we find that we can pinpoint the origin to either a single AS or a session between two ASes in most cases. We verify our methodology in two phases. First, we perform simulations on an AS topology derived from actual BGP updates using routing policies that are compatible with inferred peering/customer/provider relationships. In these simulations, in which network and router behavior are "ideal", we inject inter-AS link failures and demonstrate that our methodology can effectively identify most origins of instability. We then develop several heuristics to cope with the limitations of the actual BGP update propagation process and monitoring infrastructure, and apply our methodology and evaluation techniques to actual BGP updates gathered at hundreds of observation points. This approach of relying on data from BGP simulations as well as from measurements enables us to evaluate the inference quality achieved by our approach under ideal situations and how it is correlated with the actual quality and the number of observation points.
Diagnosing network-wide traffic anomalies
Authors: Lakhina Anukool , Crovella Mark , Diot Christophe
Published: January 2005

Anomalies are unusual and significant changes in a network's traffic levels, which can often span multiple links. Diagnosing anomalies is critical for both network operators and end users. It is a difficult problem because one must extract and interpret anomalous patterns from large amounts of high-dimensional, noisy data.In this paper we propose a general method to diagnose anomalies. This method is based on a separation of the high-dimensional space occupied by a set of network traffic measurements into disjoint subspaces corresponding to normal and anomalous network conditions. We show that this separation can be performed effectively by Principal Component Analysis.Using only simple traffic measurements from links, we study volume anomalies and show that the method can: (1) accurately detect when a volume anomaly is occurring; (2) correctly identify the underlying origin-destination (OD) flow which is the source of the anomaly; and (3) accurately estimate the amount of traffic involved in the anomalous OD flow.We evaluate the method's ability to diagnose (
i.e.,
detect, identify, and quantify) both existing and synthetically injected volume anomalies in real traffic from two backbone networks. Our method consistently diagnoses the largest volume anomalies, and does so with a very low false alarm rate.
Building a better NetFlow
Authors: Estan Cristian , Keys Ken , Moore David , Varghese George
Published: January 2005

Network operators need to determine the composition of the traffic mix on links when looking for dominant applications, users, or estimating traffic matrices. Cisco's NetFlow has evolved into a solution that satisfies this need by reporting flow records that summarize a sample of the traffic traversing the link. But sampled NetFlow has shortcomings that hinder the collection and analysis of traffic data. First, during flooding attacks router memory and network bandwidth consumed by flow records can increase beyond what is available; second, selecting the right static sampling rate is difficult because no single rate gives the right tradeoff of memory use versus accuracy for all traffic mixes; third, the heuristics routers use to decide when a flow is reported are a poor match to most applications that work with time bins; finally, it is impossible to estimate without bias the number of active flows for aggregates with non-TCP traffic.In this paper we propose Adaptive NetFlow, deployable through an update to router software, which addresses many shortcomings of NetFlow by dynamically adapting the sampling rate to achieve robustness without sacrificing accuracy. To enable counting of non-TCP flows, we propose an optional Flow Counting Extension that requires augmenting existing hardware at routers. Both our proposed solutions readily provide descriptions of the traffic of progressively smaller sizes. Transmitting these at progressively higher levels of reliability allows graceful degradation of the accuracy of traffic reports in response to network congestion on the reporting path.
Exact GPS simulation with logarithmic complexity, and its application to an optimally fair scheduler
Authors: Valente Paolo
Published: January 2005

Generalized Processor Sharing (GPS) is a fluid scheduling policy providing perfect fairness. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one packet size. To the best of our knowledge, the only packet scheduler guaranteeing such minimum deviation is Worst-case Fair Weighted Fair Queueing (WF
2
Q), that requires on-line GPS simulation. Existing algorithms to perform GPS simulation have
O
(
N
) complexity per packet transmission (
N
being the number of competing flows). Hence WF
2
Q has been charged for
O
(
N
) complexity too. Schedulers with lower complexity have been devised, but at the price of at least
O
(
N
) deviation from the GPS service, which has been shown to be detrimental for real-time adaptive applications and feedback based applications. Furthermore, it has been proven that the lower bound complexity to guarantee
O
(1) deviation is Ω(log
N
), yet a scheduler achieving such result has remained elusive so far.In this paper we present an algorithm that performs exact GPS simulation with
O
(log
N
) worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. In particular, using our algorithm within WF
2
Q, we achieve the minimum deviation from the GPS service with
O
(log
N
) complexity, thus matching the aforementioned lower bound. Furthermore, we assess the effectiveness of the proposed solution by simulating real-world scenarios.
Sizing router buffers
Authors: Appenzeller Guido , Keslassy Isaac , McKeown Nick
Published: January 2005

All Internet routers contain buffers to hold packets during times of congestion. Today, the size of the buffers is determined by the dynamics of TCP's congestion control algorithm. In particular, the goal is to make sure that when a link is congested, it is busy 100% of the time; which is equivalent to making sure its buffer never goes empty. A widely used rule-of-thumb states that each link needs a buffer of size
B
= overline
RTT
x
C
, where overline
RTT
is the average round-trip time of a flow passing across the link, and
C
is the data rate of the link. For example, a 10Gb/s router linecard needs approximately 250ms x 10Gb/s = 2.5Gbits of buffers; and the amount of buffering grows linearly with the line-rate. Such large buffers are challenging for router manufacturers, who must use large, slow, off-chip DRAMs. And queueing delays can be long, have high variance, and may destabilize the congestion control algorithms. In this paper we argue that the rule-of-thumb (
B
= (overline
RTT
x
C
) is now outdated and incorrect for backbone routers. This is because of the large number of flows (TCP connections) multiplexed together on a single backbone link. Using theory, simulation and experiments on a network of real routers, we show that a link with
n
flows requires no more than
B
= (overline
RTT
x
C
) √
n
, for long-lived or short-lived TCP flows. The consequences on router design are enormous: A 2.5Gb/s link carrying 10,000 flows could reduce its buffers by 99% with negligible difference in throughput; and a 10Gb/s link carrying 50,000 flows requires only 10Mbits of buffering, which can easily be implemented using fast, on-chip SRAM.
Impact of configuration errors on DNS robustness
Authors: Pappas Vasileios , Xu Zhiguo , Lu Songwu , Massey Daniel , Terzis Andreas , Zhang Lixia
Published: January 2005

During the past twenty years the Domain Name System (DNS) has sustained phenomenal growth while maintaining satisfactory performance. However, the original design focused mainly on system robustness against physical failures, and neglected the impact of operational errors such as misconfigurations. Our recent measurement effort revealed three specific types of misconfigurations in DNS today: lame delegation, diminished server redundancy, and cyclic zone dependency. Zones with configuration errors suffer from reduced availability and increased query delays up to an order of magnitude. Furthermore, while the original DNS design assumed that redundant DNS servers fail independently, our measurements show that operational choices made at individual zones can severely affect the availability of other zones. We found that, left unchecked, DNS configuration errors are widespread, with lame delegation affecting 15% of the DNS zones, diminished server redundancy being even more prevalent, and cyclic dependency appearing in 2% of the zones. We also noted that the degrees of misconfiguration vary from zone to zone, with most popular zones having the lowest percentage of errors. Our results indicate that DNS, as well as any other truly robust large-scale system, must include systematic checking mechanisms to cope with operational errors.
A layered naming architecture for the internet
Authors: Balakrishnan Hari , Lakshminarayanan Karthik , Ratnasamy Sylvia , Shenker Scott , Stoica Ion , Walfish Michael
Published: January 2005

Currently the Internet has only one level of name resolution, DNS, which converts user-level domain names into IP addresses. In this paper we borrow liberally from the literature to argue that there should be three levels of name resolution: from user-level descriptors to service identifiers; from service identifiers to endpoint identifiers; and from endpoint identifiers to IP addresses. These additional levels of naming and resolution (1) allow services and data to be first class Internet objects (in that they can be directly and persistently named), (2) seamlessly accommodate mobility and multi-homing and (3) integrate middleboxes (such as NATs and firewalls) into the Internet architecture. We further argue that flat names are a natural choice for the service and endpoint identifiers. Hence, this architecture requires scalable resolution of flat names, a capability that distributed hash tables (DHTs) can provide.
A scalable distributed information management system
Authors: Yalagandula Praveen , Dahlin Mike
Published: January 2005

We present a Scalable Distributed Information Management System (SDIMS) that
aggregates
information about large-scale networked systems and that can serve as a basic building block for a broad range of large-scale distributed applications by providing detailed views of nearby information and summary views of global information. To serve as a basic building block, a SDIMS should have four properties: scalability to many nodes and attributes, flexibility to accommodate a broad range of applications, administrative isolation for security and availability, and robustness to node and network failures. We design, implement and evaluate a SDIMS that (1) leverages Distributed Hash Tables (DHT) to create scalable aggregation trees, (2) provides flexibility through a simple API that lets applications control propagation of reads and writes, (3) provides administrative isolation through simple extensions to current DHT algorithms, and (4) achieves robustness to node and network reconfigurations through lazy reaggregation, on-demand reaggregation, and tunable spatial replication. Through extensive simulations and micro-benchmark experiments, we observe that our system is an order of magnitude more scalable than existing approaches, achieves isolation properties at the cost of modestly increased read latency in comparison to flat DHTs, and gracefully handles failures.
Topical web crawlers
Authors: Menczer Filippo , Pant Gautam , Srinivasan Padmini
Published: January 2005

Topical crawlers are increasingly seen as a way to address the scalability limitations of universal search engines, by distributing the crawling process across users, queries, or even client computers. The context available to such crawlers can guide the navigation of links with the goal of efficiently locating highly relevant target pages. We developed a framework to fairly evaluate topical crawling algorithms under a number of performance metrics. Such a framework is employed here to evaluate different algorithms that have proven highly competitive among those proposed in the literature and in our own previous research. In particular we focus on the tradeoff between exploration and exploitation of the cues available to a crawler, and on adaptive crawlers that use machine learning techniques to guide their search. We find that the best performance is achieved by a novel combination of explorative and exploitative bias, and introduce an evolutionary crawler that surpasses the performance of the best nonadaptive crawler after sufficiently long crawls. We also analyze the computational complexity of the various crawlers and discuss how performance and complexity scale with available resources. Evolutionary crawlers achieve high efficiency and scalability by distributing the work across concurrent agents, resulting in the best performance/cost ratio.
Distributed scheduling policies in networks of input-queued packet switches
Authors: Bauer Claus
Published: January 2005

Scheduling algorithms for input-queued packet switches have been widely researched. It has been shown that various classes of scheduling algorithms provide guarantees on stability and on average delay for single switches. However, recent research has demonstrated that most of these scheduling algorithms do not guarantee stability for networks of switches.

Most of the research that treats networks of switches proposes switching policies that require coordination among the single switches. The problem to find distributed scheduling policies that guarantee the stability of a network of switches has so far only been investigated for a policy based on a computationally very complex maximum weight matching algorithm.

In this paper, we investigate distributed scheduling algorithms of low complexity that belong to the classes of maximal weight matching algorithms, p-maximal weight matching algorithms for switch architectures based on a space-division multiplexing extension, and MNCM algorithms. For these scheduling algorithms, we prove the stability of networks of input-queued switches where all switches deploy the same scheduling policy. We also show that networks of input-queued switches in which specific classes of different switching policies are deployed simultaneously at different switches are stable.