bluuebunny/crossref_metadata_2025 huggingface dataset:
Developing principles of GUI programming using views
Authors: Bishop Judith , Horspool Nigel
Published: January 2005

This paper proposes that GUI development is as important as other aspects of programming, such as a sound understanding of control structures and object orientation. Far less attention has been paid to the programming structures for GUIs and certainly there are few cross language principles to aid the programmer. We propose that principles of GUIs can be extracted and learnt, and that they do enhance good programming practice. These principles have been implemented in our Views system which features an XML-based GUI description notation coupled with an engine that shields the programmer from much of the intricate complexity associated with events, listeners and handlers. The system is programmed primarily in C# for .NET, but is available in various forms for Java and for other platforms which support .NET through the SSCLI.
Virtual trees for the byzantine generals algorithm
Authors: Tikvati Ahuva , Ben-Ari Mordechai , Kolikant Yifat Ben-David
Published: January 2005

The Byzantine Generals algorithm for achieving reliability in the presence of faults is a classic topic in distributed computation and operating systems, not the least because of its colorful story. We describe a concept called
virtual data structures
, which are concrete representations of global data structures that is not actually maintained by the nodes of a distributed system, but are required in order to understand the correctness of algorithms. We show that the use of virtual trees for the Byzantine Generals algorithm can improve the understanding of this algorithm, and we describe a visualization of the trees.
A practical access to the theory of parallel algorithms
Authors: Kessler Christoph
Published: January 2005

We describe a parallel programming environment that implements the PRAM (Parallel Random Access Machine) model. The programming environment consists of a C-based PRAM programming language called
FORK
with a compiler, libraries and tools, and a fast PRAM simulator. The software is freely available for Unix workstations. The programming environment and a systematic way of writing structured parallel programs for the PRAM model are described in a recent textbook.Even though the programming environment was originally developed for a hardware research project, we show that the system is also especially suited for complementing classical theory courses on PRAM algorithms by programming exercises that allow students to experiment with PRAM-style parallelism and actually implement the algorithms as they appear in the theory textbooks.We describe how the environment was used in a recent graduate-level course on parallel algorithms, and report on feedback that we got from the participants.
Designing and implementing a cyberwar laboratory exercise for a computer security course
Authors: Wagner Paul J. , Wudi Jason M.
Published: January 2005

The development of a cyberwar laboratory exercise for a computer security course raises many pedagogical and management issues relating to the structure of the laboratory, its network and the exercise itself. We have designed, implemented and given such an exercise, and faced many of these issues. Evaluation of this exercise leads to multiple insights about the proper goals, structure and implementation of such an exercise.
Teaching computer security at a small college
Authors: LeBlanc Cathie , Stiller Evelyn
Published: January 2005

Computer and network security are important topics for computer professionals in US companies today. An adequate education in these topics would probably involve several classes at the undergraduate level but many computer science curricula do not have room to have numerous required courses. In addition, most computer science faculty members have not taken classes covering these topics and have never worked as professionals dealing with these areas. Dealing with these difficult issues can be a challenge, especially in a small college environment. In this paper, we present our experiences teaching computer security topics in both a system administration course and a computer security course.
Digital media in computer science curricula
Authors: Wong Yue-Ling , Burg Jennifer , Strokanova Victoria
Published: January 2005

"Digital media" is one of those unfortunate terms that means different things in different contexts. This difficulty of definition -- along with its association with art, communication, architecture, and film -- puts digital media on the margins of traditional computer science curricula. This paper reviews the types of digital media programs current in higher education; proposes a curriculum model for digital media instruction that is firmly grounded in computer science at the same time that it interfaces easily with digital art; and describes specially-designed course material that serves the interdisciplinary need while preserving the rigor of the computer science discipline.
Web services as the foundation for learning complex software system development
Authors: Humphrey Marty
Published: January 2005

A significant challenge for Computer Science departments is how best to get new graduate students involved with their chosen research projects. Ideally, the incoming graduate students will as a whole have both a solid understanding of computing principles behind large-scale software development and a broad "skill set", e.g., for conducting systems-oriented research. This rarely occurs, due to the diversity of backgrounds of incoming students--even the most qualified applicant can have deficiencies. To address this problem, we have developed a first-year graduate course that balances and integrates practical considerations with basic principles of complex software system development. To make the discussions of designing, implementing, and evaluating complex software systems more concrete, we situate the core of the class in the context of Web Services. We are currently teaching this class for the second time, and, while there will always be open issues given the nature and scope of this class, we have received positive feedback from the students and the other members of the department. Students recognize the practicality of Web Services. Students also appreciate the research possibilities that arise while evaluating the state of the art with regard to Web Services.
Programming in context
Authors: Bennedsen Jens , Caspersen Michael E.
Published: January 2005

The recommendations of the Joint Task Force on Computing Curricula 2001 encompass suggestions for an object-first introductory programming course. We have identified conceptual modeling as a lacking perspective in the suggestions for CS1. Conceptual modeling is the defining characteristic of object-orientation and provides a unifying perspective and a pedagogical approach focusing upon the modelling aspects of object-orientation. Reinforcing conceptual modelling as a basis for CS1 provides an appealing course structure based on core elements from a conceptual framework for object-orientation as well as a systematic approach to programming; both of these are a big help to newcomers. The approach has a very positive impact on the number of students passing the course.
Research, teaching, and service
Authors: Sivilotti Paolo A. G. , Weide Bruce W.
Published: January 2005

Rarely are the three pillars of academia---research, teaching, and service---addressed together, within one intellectually cohesive context in the graduate curriculum. Such a context is important for exposing students to the inter-relationships among these facets.This paper presents our experience with structuring graduate research seminar courses around the model of a "miniconference". Throughout the quarter, students pursue original research projects in the discipline of the seminar course. At the end of the quarter, students write their findings as technical conference papers, then act as the miniconference program committee in reviewing each other's submissions. Finally, the selected papers are presented at the miniconference. In addition to the model itself, we describe some variations in instantiation and an assessment of the benefits of this general approach.
Memory Ordering
Authors: Cain Harold W. , Lipasti Mikko H.
Published: January 2005

Conventional out-of-order processors employ a multi-ported,fully-associative load queue to guarantee correctmemory reference order both within a single thread of executionand across threads in a multiprocessor system. Asimprovements in process technology and pipelining lead tohigher clock frequencies, scaling this complex structure toaccommodate a larger number of in-flight loads becomesdifficult if not impossible. Furthermore, each access to thiscomplex structure consumes excessive amounts of energy.In this paper, we solve the associative load queue scalabilityproblem by completely eliminating the associative loadqueue. Instead, data dependences and memory consistencyconstraints are enforced by simply re-executing loadinstructions in program order prior to retirement. Usingheuristics to filter the set of loads that must be re-executed,we show that our replay-based mechanism enables a simple,scalable, and energy-efficient FIFO load queue designwith no associative lookup functionality, while sacrificingonly a negligible amount of performance and cache bandwidth.
Transactional Memory Coherence and Consistency
Authors: Hammond Lance , Wong Vicky , Chen Mike , Carlstrom Brian D. , Davis John D. , Hertzberg Ben , Prabhu Manohar K. , Wijaya Honggo , Kozyrakis Christos , Olukotun Kunle
Published: January 2005

In this paper, we propos a new shared memory model: Transactionalmemory Coherence and Consistency (TCC).TCC providesa model in which atomic transactions are always the basicunit of parallel work, communication, memory coherence, andmemory reference consistency.TCC greatly simplifies parallelsoftware by eliminating the need for synchronization using conventionallocks and semaphores, along with their complexities.TCC hardware must combine all writes from each transaction regionin a program into a single packet and broadcast this packetto the permanent shared memory state atomically as a large block.This simplifies the coherence hardware because it reduces theneed for small, low-latency messages and completely eliminatesthe need for conventional snoopy cache coherence protocols, asmultiple speculatively written versions of a cache line may safelycoexist within the system.Meanwhile, automatic, hardware-controlledrollback of speculative transactions resolves any correctnessviolations that may occur when several processors attemptto read and write the same data simultaneously.The cost of thissimplified scheme is higher interprocessor bandwidth.To explore the costs and benefits of TCC, we study the characterisitcsof an optimal transaction-based memory system, and examinehow different design parameters could affect the performanceof real systems.Across a spectrum of applications, the TCC modelitself did not limit available parallelism.Most applications areeasily divided into transactions requiring only small write buffers,on the order of 4-8 KB.The broadcast requirements of TCCare high, but are well within the capabilities of CMPs and small-scaleSMPs with high-speed interconnects.
SMTp
Authors: Chaudhuri Mainak , Heinrich Mark
Published: January 2005

We introduce the SMTp architecture-an SMT processoraugmented with a coherence protocol thread context,that together with a standard integrated memory controllercan enable the design of (among other possibilities) scalablecache-coherent hardware distributed shared memory(DSM) machines from commodity nodes. We describe theminor changes needed to a conventional out-of-order multi-threadedcore to realize SMTp, discussing issues related toboth deadlock avoidance and performance. We then compareSMTp performance to that of various conventionalDSM machines with normal SMT processors both with andwithout integrated memory controllers. On configurationsfrom 1 to 32 nodes, with 1 to 4 application threads pernode, we find that SMTp delivers performance comparableto, and sometimes better than, machines with more complexintegrated DSM-specific memory controllers. Our resultsalso show that the protocol thread has extremely lowpipeline overhead. Given the simplicity and the flexibility ofthe SMTp mechanism, we argue that next-generation multi-threadedprocessors with integrated memory controllersshould adopt this mechanism as a way of building less complexhigh-performance DSM multiprocessors.
A Formal Approach to Frequent Energy Adaptations for Multimedia Applications
Authors: Hughes Christopher J. , Adve Sarita V.
Published: January 2005

Much research has recently been done on adapting architecturalresources of general-purpose processors to saveenergy at the cost of increased execution time. This workexamines adaptation control algorithms for such processorsrunning real-time multimedia applications. The best previousalgorithms are mostly heuristics-based and ad hoc, requiringan impractically large amount of application- andresource-specific tuning.We take a more formal approach that does not require thelarge tuning effort of previous approaches, and yet obtainsaverage energy savings comparable to the best previous approach.We pose control algorithm design as a constrainedoptimization problem: what configuration should be used ateach point in the program to minimize energy for a targetedperformance given that each configuration has a differentenergy-performance tradeoff at each point? We solve thiswith the method of Lagrange multipliers, which assumesknowledge of the energy-performance tradeoffs. We developa technique to estimate these tradeoffs using properties ofmultimedia applications. Our technique is likely extendibleto other application domains.We compare our algorithm to the best previous algorithmfor real-time multimedia applications, which is heuristics-based.We demonstrate the practical difficulty of the tuningprocess for the previous algorithm. Compared to apainstakingly hand-tuned version of that algorithm, ournew algorithm provides similar energy savings through amore formal approach that does not need such heroic tuning,making it practical to implement.
Synchroscalar
Authors: Oliver John , Rao Ravishankar , Sultana Paul , Crandall Jedidiah , Czernikowski Erik , Jones IV Leslie W. , Franklin Diana , Akella Venkatesh , Chong Frederic T.
Published: January 2005

We present Synchroscalar, a tile-based architecture forembedded processing that is designed to provide the flexibilityof DSPs while approaching the power efficiency ofASICs. We achieve this goal by providing high parallelismand voltage scaling while minimizing control and communicationcosts. Specifically, Synchroscalar uses columnsof processor tiles organized into statically-assignedfrequency-voltage domains to minimize power consumption.Furthermore, while columns use SIMD control to minimizeoverhead, data-dependent computations can besupported by extremely flexible statically-scheduled communicationbetween columns.We provide a detailed evaluation of Synchroscalar includingSPICE simulation, wire and device models, synthesisof key components, cycle-level simulation, andcompiler- and hand-optimized signal processing applications.We find that the goal of meeting, not exceeding, performancetargets with data-parallel applications leads todesigns that depart significantly from our intuitions derivedfrom general-purpose microprocessor design. Inparticular, synchronous design and substantial global interconnectare desirable in the low-frequency, low-powerdomain. This global interconnect supports parallelizationand reduces processor idle time, which are critical to energyefficient implementations of high bandwidth signalprocessing. Overall, Synchroscalar provides programmabilitywhile achieving power efficiencies within 8-30X ofknown ASIC implementations, which is 10-60X better thanconventional DSPs. In addition, frequency-voltage scalingin Synchroscalar provides between 3-32% power savingsin our application suite.
iWatcher
Authors: Zhou Pin , Qin Feng , Liu Wei , Zhou Yuanyuan , Torrellas Josep
Published: January 2005

Recent impressive performance improvements in computer architecturehave not led to significant gains in ease of debugging.Software debugging often relies on inserting run-time softwarechecks. In many cases, however, it is hard to find the root causeof a bug. Moreover, program execution typically slows down significantly,often by 10-100 times.To address this problem, this paper introduces the IntelligentWatcher (iWatcher), novel architectural support to monitor dynamicexecution with minimal overhead, automatically, and flexibly.iWatcher associates program-specified monitoring functionswith memory locations. When any such location is accessed, themonitoring function is automatically triggered with low overhead.To further reduce overhead and support rollback, iWatcher canleverage Thread-Level Speculation (TLS). To test iWatcher, we useapplications with various bugs. Our results show that iWatcher detectsmany more software bugs than Valgrind, a well-known open-sourcebug detector. Moreover, iWatcher only induces a 4-80%execution overhead, which is orders of magnitude less than Valgrind.Even with 20% of the dynamic loads monitored in a program,iWatcher adds only 66-174% overhead. Finally, TLS is effective atreducing overheads for programs with substantial monitoring.
From Sequences of Dependent Instructions to Functions
Authors: Yehia Sami , Temam Olivier
Published: January 2005

In this article, we present an approach for improving the performance of sequences of dependent instructions. We observe that many sequences of instructionscan be interpreted as functions. Unlike sequences of instructions, functions can be translated into very fast butexponentially costly two-level combinational circuits. Wepresent an approach that exploits this principle, speeds upprograms thanks to circuit-level parallelism/redundancy,but avoids the exponential costs.We analyze the potential of this approach, and thenwe propose an implementation that consists of a superscalar processor with a large specific functional unit associated with specific back-end transformations. The performance of the SpecInt2000 benchmarks and selectedprograms from the Olden and MiBench benchmark suitesimproves on average from 2.4% to 12% depending on thelatency of the functional units, and up to 39.6%; moreprecisely, the performance of optimized code sections improves on average from 3.5% to 19%, and up to 49%.
Techniques to Reduce the Soft Error Rate of a High-Performance Microprocessor
Authors: Weaver Christopher , Emer Joel , Mukherjee Shubhendu S. , Reinhardt Steven K.
Published: January 2005

Transient faults due to neutron and alpha particle strikes posea significant obstacle to increasing processor transistor counts infuture technologies. Although fault rates of individual transistorsmay not rise significantly, incorporating more transistors into adevice makes that device more likely to encounter a fault. Hence,maintaining processor error rates at acceptable levels will requireincreasing design effort.This paper proposes two simple approaches to reduce errorrates and evaluates their application to a microprocessor instructionqueue. The first technique reduces the time instructions sit invulnerable storage structures by selectively squashing instructionswhen long delays are encountered. A fault is less likely to cause anerror if the structure it affects does not contain valid instructions.We introduce a new metric, MITF (Mean Instructions To Failure),to capture the trade-off between performance and reliability introducedby this approach.The second technique addresses false detected errors. In theabsence of a fault detection mechanism, such errors would nothave affected the final outcome of a program. For example, a faultaffecting the result of a dynamically dead instruction would notchange the final program output, but could still be flagged by thehardware as an error. To avoid signalling such false errors, wemodify a pipeline's error detection logic to mark affected instructionsand data as possibly incorrect rather than immediately signalingan error. Then, we signal an error only if we determine laterthat the possibly incorrect value could have affected the program'soutput.
Use-Based Register Caching with Decoupled Indexing
Authors: Butts J. Adam , Sohi Gurindar S.
Published: January 2005

Wide, deep pipelines need many physical registersto hold the results of in-flight instructions. Simultaneously,high clock frequencies prohibit using largeregister files and bypass networks without a significantperformance penalty. Previously proposed techniquesusing register caching to reduce this penalty sufferfrom several problems including poor insertion andreplacement decisions and the need for a fully-associativecache for good performance. We present novelmechanisms for managing and indexing register cachesthat address these problems using knowledge of thenumber of consumers of each register value.The insertion policy reduces pollution by not cachinga register value when all of its predicted consumersare satisfied by the bypass network. The replacementpolicy selects register cache entries with the fewestremaining uses (often zero), lowering the miss rate. Wealso introduce a new, general method of mapping physicalregisters to register cache sets that improves theperformance of set-associative cache organizations byreducing conflicts. Our results indicate that a 64-entry,two-way set associative cache using these techniquesoutperforms multi-cycle monolithic register files andpreviously proposed hierarchical register files.
A Complexity-Effective Approach to ALU Bandwidth Enhancement for Instruction-Level Temporal Redundancy
Authors: Parashar Angshuman , Gurumurthi Sudhanva , Sivasubramaniam Anand
Published: January 2005

Previous proposals for implementing instruction-level temporalredundancy in out-of-order cores have reported a performancedegradation of upto 45% in certain applications compared to anexecution which does not have any temporal redundancy. An importantcontributor to this problem is the insufficient number ofALUs for handling the amplified load injected into the core. At thesame time, increasing the number of ALUs can increase the complexityof the issue logic, which has been pointed out to be oneof the most timing critical components of the processor. This paperproposes a novel extension of a prior idea on instruction reuseto ease ALU bandwidth requirements in a complexity-effective wayby exploiting certain interesting properties of a dual (temporallyredundant) instruction stream. We present microarchitectural extensionsnecessary for implementing an instruction reuse buffer(IRB) and integrating this with the issue logic of a dual instructionstream superscalar core, and conduct extensive evaluationsto demonstrate how well it can alleviate the ALU bandwidth problem.We show that on the average we can gain back nearly 50%of the IPC loss that occurred due to ALU bandwidth limitationsfor an instruction-level temporally redundant superscalar execution,and 23% of the overall IPC loss.
Field-testing IMPACT EPIC research results in Itanium 2
Authors: Sias John W. , Ueng Sain-zee , Kent Geoff A. , Steiner Ian M. , Nystrom Erik M. , Hwu Wen-mei W.
Published: January 2005

Explicitly-Parallel Instruction Computing (EPIC) providesarchitectural features, including predication and explicitcontrol speculation, intended to enhance the compiler'sability to expose instruction-level parallelism (ILP) incontrol-intensive programs. Aggressive structural transformationsusing these features, though described in theliterature, have not yet been fully characterized in completesystems. Using the Intel Itanium 2 microprocessor,the SPECint2000 benchmarks and the IMPACT Compilerfor IA-64, a research compiler competitive with thebest commercial compilers on the platform, we providean in situ evaluation of code generated using aggressive,EPIC-enabled techniques in a reality-constrained microarchitecture.Our work shows a 1.13 average speedup(up to 1.50) due to these compilation techniques, relativeto traditionally-optimized code at the same inlining andpointer analysis levels, and a 1.55 speedup (up to 2.30) relativeto GNU GCC, a solid traditional compiler. Detailedresults show that the structural compilation approach providesbenefits far beyond a decrease in branch mispredictionpenalties and that it both positively and negatively impactsinstruction cache performance. We also demonstratethe increasing significance of runtime effects, such as datacache and TLB, in determining end performance and theinteraction of these effects with control speculation.
A Conversation with Donald Peterson
Authors: Sanders Lucy
Published: January 2005

That light we see at the end of the tunnel is the convergence of voice and data communications with business applications. As chairman and chief executive officer of Avaya, Donald Peterson is in a position to help make that convergence happen sooner rather than later. Peterson has been with Avaya since it was spun off from Lucent in 2000. Prior to that he was chief financial officer of AT&T’s Communication Services Group and Lucent.
Longhorn Ties Platform Apps to Core Operating System
Authors: Wolfe Alexander
Published: January 2005

Call it all-tools-for-all-things-Microsoft. That’s the way I’m beginning to think about Longhorn, Microsoft’s next-generation operating system, expected in 2006. The operating system will herald more than just the transition of mainstream computing to 64 bits. It will mark the emergence of a new, multifaceted programming model. Breaking away from traditional computer science taxonomy, where operating systems stood barely removed from the hardware abstraction layer, Longhorn will be more like a multi-tentacled container for a wide range of administration and application tools.
Animated use sketches as design representations
Authors: Löwgren Jonas
Published: January 2005

Interaction design requires many forms of externalization. At certain points in the process, there is a need for design representations that (1) explore the intended use situation in some detail, and still (2) appear tentative enough to afford participation and engagement by intended users and other stakeholders. The designer's task is often to create ideas on the not-yet-existing. The envisioned use situations increasingly involve complicated technology, mobile use and demanding physical environments. Under these conditions, a third requirement on the representation technique is that it (3) allows for expression of ideas and use situations that would be impractical or impossible to create in conventional prototyping techniques. (An obvious example is the observation that lo-fi paper prototypes are of limited use for virtual reality design.)
Empirical performance of bias-reducing estimators for regenerative steady-state simulations
Authors: Hsieh Ming-Hua , Iglehart Donald L. , Glynn Peter W.
Published: January 2005

When simulating a stochastic system, simulationists often are interested in estimating various steady-state performance measures. The classical point estimator for such a measure involves simply taking the time average of an appropriate function of the process being simulated. Since the simulation can not be initiated with the (unknown) steady-state distribution, the classical point estimator is generally biased. In the context of regenerative steady-state simulation, a variety of other point estimators have been developed in an attempt to minimize the bias. In this paper, we provide an empirical comparison of these estimators in the context of four different continuous-time Markov chain models. The bias of the point estimators and the coverage probabilities of the associated confidence intervals are reported for the four models. Conclusions are drawn from this experimental work as to which methods are most effective in reducing bias.
The one-minute risk assessment tool
Authors: Tiwana Amrit , Keil Mark
Published: January 2005

An analysis of risks in software development, using data from senior IT managers, produced surprising results. Our one-minute assessment tool applies those results to assessing the risks of specific projects.
What leads to user acceptance of digital libraries?
Authors: Thong James Y.L. , Hong Weiyin , Tam Kar Yan
Published: January 2005

While millions of dollars have been spent building digital libraries, research indicates that millions of potential users may still be ignoring them.
Network laws
Authors: Denning Peter J.
Published: January 2005

Many networks, physical and social, are complex and scale-invariant. This has important implications from the spread of epidemics and innovations to protection from attack.
Introduction
Authors: Stewart Craig A.
Published: January 2005

Bioinformatics and computational biology will enable breakthroughs in basic biological research and improvements in the prevention, treatment, and cure of diseases.
Computational biology and high-performance computing
Authors: Bader David A.
Published: January 2005

Understanding evolution and the basic structure and function of proteins are two grand challenge problems in biology that can be solved only through the use of high-performance computing.
The SEED
Authors: Overbeek Ross , Disz Terry , Stevens Rick
Published: January 2005

This open source toolkit will help scientists interpret the vast body of genomic data now publicly available.
The emerging role of biogrids
Authors: Ellisman Mark , Brady Michael , Hart David , Lin Fang-Pang , Müller Matthias , Smarr Larry
Published: January 2005

Four biomedically oriented grid systems, ranging from SARS diagnosis to arthropod evolution, demonstrate the promise of grid computing in medical practice and biological science.
Beyond power
Authors: Javahery Homa , Seffah Ahmed , Radhakrishnan Thiruvengadam
Published: January 2005

User-centered design techniques can broaden the appeal, use, and effectiveness of Web-based bioinformatics tools.
Biomedical computing and visualization software environments
Authors: Johnson Chris R. , MacLeod Rob , Parker Steven G. , Weinstein David
Published: January 2005

Problem-solving environments and advanced visualization take on the complexity of biomedical computing, improving its utility to scientists and clinicians alike.
Improving student performance by evaluating how well students test their own programs
Authors: Edwards Stephen H.
Published: January 2005

Students need to learn more software testing skills. This paper presents an approach to teaching software testing in a way that will encourage students to practice testing skills in many classes and give them concrete feedback on their testing performance, without requiring a new course, any new faculty resources, or a significant number of lecture hours in each course where testing will be practiced. The strategy is to give students basic exposure to test-driven development, and then provide an automated tool that will assess student submissions on-demand and provide feedback for improvement. This approach has been demonstrated in an undergraduate programming languages course using a prototype tool. The results have been positive, with students expressing appreciation for the practical benefits of test-driven development on programming assignments. Experimental analysis of student programs shows a 28% reduction in defects per thousand lines of code.
A first-principles approach to understanding the internet's router-level topology
Authors: Li Lun , Alderson David , Willinger Walter , Doyle John
Published: January 2005

A detailed understanding of the many facets of the Internet's topological structure is critical for evaluating the performance of networking protocols, for assessing the effectiveness of proposed techniques to protect the network from nefarious intrusions and attacks, or for developing improved designs for resource provisioning. Previous studies of topology have focused on interpreting measurements or on phenomenological descriptions and evaluation of graph-theoretic properties of topology generators. We propose a complementary approach of combining a more subtle use of statistics and graph theory with a first-principles theory of router-level topology that reflects practical constraints and tradeoffs. While there is an inevitable tradeoff between model complexity and fidelity, a challenge is to distill from the seemingly endless list of potentially relevant technological and economic issues the features that are most essential to a solid understanding of the intrinsic fundamentals of network topology. We claim that very simple models that incorporate hard technological constraints on router and link bandwidth and connectivity, together with abstract models of user demand and network performance, can successfully address this challenge and further resolve much of the confusion and controversy that has surrounded topology generation and evaluation.
Locating internet bottlenecks
Authors: Hu Ningning , Li Li (Erran) , Mao Zhuoqing Morley , Steenkiste Peter , Wang Jia
Published: January 2005

The ability to locate network bottlenecks along end-to-end paths on the Internet is of great interest to both network operators and researchers. For example, knowing where bottleneck links are, network operators can apply traffic engineering either at the interdomain or intradomain level to improve routing. Existing tools either fail to identify the
location
of bottlenecks, or generate a large amount of probing packets. In addition, they often require access to both end points. In this paper we present
Pathneck
, a tool that allows end users to efficiently and accurately locate the bottleneck link on an Internet path. Pathneck is based on a novel probing technique called Recursive Packet Train (RPT) and does not require access to the destination. We evaluate Pathneck using wide area Internet experiments and trace-driven emulation. In addition, we present the results of an extensive study on bottlenecks in the Internet using carefully selected, geographically diverse probing sources and destinations. We found that Pathneck can successfully detect bottlenecks for almost 80% of the Internet paths we probed. We also report our success in using the bottleneck location and bandwidth bounds provided by Pathneck to infer bottlenecks and to avoid bottlenecks in multihoming and overlay routing.
Optimizing cost and performance for multihoming
Authors: Goldenberg David K. , Qiuy Lili , Xie Haiyong , Yang Yang Richard , Zhang Yin
Published: January 2005

Multihoming is often used by large enterprises and stub ISPs to connect to the Internet. In this paper, we design a series of novel
smart routing
algorithms to optimize cost and performance for multihomed users. We evaluate our algorithms through both analysis and extensive simulations based on realistic charging models, traffic demands, performance data, and network topologies. Our results suggest that these algorithms are very effective in minimizing cost and at the same time improving performance. We further examine the equilibrium performance of smart routing in a global setting and show that a smart routing user can improve its performance without adversely affecting other users.
A comparison of overlay routing and multihoming route control
Authors: Akella Aditya , Pang Jeffrey , Maggs Bruce , Seshan Srinivasan , Shaikh Anees
Published: January 2005

The limitations of BGP routing in the Internet are often blamed for poor end-to-end performance and prolonged connectivity interruptions. Recent work advocates using overlays to effectively bypass BGP's path selection in order to improve performance and fault tolerance. In this paper, we explore the possibility that intelligent control of BGP routes, coupled with ISP multihoming, can provide competitive end-to-end performance and reliability. Using extensive measurements of paths between nodes in a large content distribution network, we compare the relative benefits of overlay routing and multihoming route control in terms of round-trip latency, TCP connection throughput, and path availability. We observe that the performance achieved by route control together with multihoming to three ISPs (3-multihoming), is within 5-15% of overlay routing employed in conjunction 3-multihoming, in terms of both end-to-end RTT and throughput. We also show that while multihoming cannot offer the nearly perfect resilience of overlays, it can eliminate almost all failures experienced by a singly-homed end-network. Our results demonstrate that, by leveraging the capability of multihoming route control, it is not necessary to circumvent BGP routing to extract good wide-area performance and availability from the existing routing system.
Link-level measurements from an 802.11b mesh network
Authors: Aguayo Daniel , Bicket John , Biswas Sanjit , Judd Glenn , Morris Robert
Published: January 2005

This paper analyzes the causes of packet loss in a 38-node urban multi-hop 802.11b network. The patterns and causes of loss are important in the design of routing and error-correction protocols, as well as in network planning.The paper makes the following observations. The distribution of inter-node loss rates is relatively uniform over the whole range of loss rates; there is no clear threshold separating "in range" and "out of range." Most links have relatively stable loss rates from one second to the next, though a small minority have very bursty losses at that time scale. Signal-to-noise ratio and distance have little predictive value for loss rate. The large number of links with intermediate loss rates is probably due to multi-path fading rather than attenuation or interference.The phenomena discussed here are all well-known. The contributions of this paper are an understanding of their relative importance, of how they interact, and of the implications for MAC and routing protocol design.
Comparison of routing metrics for static multi-hop wireless networks
Authors: Draves Richard , Padhye Jitendra , Zill Brian
Published: January 2005

Routing protocols for wireless ad hoc networks have traditionally focused on finding paths with minimum hop count. However, such paths can include slow or lossy links, leading to poor throughput. A routing algorithm can select better paths by explicitly taking the quality of the wireless links into account. In this paper, we conduct a detailed, empirical evaluation of the performance of three link-quality metrics---ETX, per-hop RTT, and per-hop packet pair---and compare them against minimum hop count. We study these metrics using a DSR-based routing protocol running in a wireless testbed. We find that the ETX metric has the best performance when all nodes are stationary. We also find that the per-hop RTT and per-hop packet-pair metrics perform poorly due to self-interference. Interestingly, the hop-count metric outperforms all of the link-quality metrics in a scenario where the sender is mobile.
SPV
Authors: Hu Yih-Chun , Perrig Adrian , Sirbu Marvin
Published: January 2005

As our economy and critical infrastructure increasingly relies on the Internet, the insecurity of the underlying border gateway routing protocol (BGP) stands out as the Achilles heel. Recent misconfigurations and attacks have demonstrated the brittleness of BGP. Securing BGP has become a priority.In this paper, we focus on a viable deployment path to secure BGP. We analyze security requirements, and consider tradeoffs of mechanisms that achieve the requirements. In particular, we study how to secure BGP update messages against attacks. We design an efficient cryptographic mechanism that relies only on symmetric cryptographic primitives to guard an ASPATH from alteration, and propose the
Secure Path Vector
(SPV) protocol. In contrast to the previously proposed S-BGP protocol, SPV is around 22 times faster. With the current effort to secure BGP, we anticipate that SPV will contribute several alternative mechanisms to secure BGP, especially for the case of incremental deployments.
Shield
Authors: Wang Helen J. , Guo Chuanxiong , Simon Daniel R. , Zugenmaier Alf
Published: January 2005

Software patching has not been effective as a first-line defense against large-scale worm attacks, even when patches have long been available for their corresponding vulnerabilities. Generally, people have been reluctant to patch their systems immediately, because patches are perceived to be unreliable and disruptive to apply. To address this problem, we propose a first-line worm defense in the network stack, using
shields
-- vulnerability-specific, exploit-generic network filters installed in end systems once a vulnerability is discovered, but before a patch is applied. These filters examine the incoming or outgoing traffic of vulnerable applications, and correct traffic that exploits vulnerabilities. Shields are less disruptive to install and uninstall, easier to test for bad side effects, and hence more reliable than traditional software patches. Further, shields are resilient to polymorphic or metamorphic variations of exploits [43].In this paper, we show that this concept is feasible by describing a prototype Shield framework implementation that filters traffic above the transport layer. We have designed a safe and restrictive language to describe vulnerabilities as partial state machines of the vulnerable application. The expressiveness of the language has been verified by encoding the signatures of several known vulnerabilites. Our evaluation provides evidence of Shield's low false positive rate and small impact on application throughput. An examination of a sample set of known vulnerabilities suggests that Shield could be used to prevent exploitation of a substantial fraction of the most dangerous ones.
Network sensitivity to hot-potato disruptions
Authors: Teixeira Renata , Shaikh Aman , Griffin Tim , Voelker Geoffrey M.
Published: January 2005

Hot-potato routing
is a mechanism employed when there are multiple (equally good) interdomain routes available for a given destination. In this scenario, the Border Gateway Protocol (BGP) selects the interdomain route associated with the closest egress point based upon intradomain path costs. Consequently, intradomain routing changes can impact interdomain routing and cause abrupt swings of external routes, which we call
hot-potato disruptions
. Recent work has shown that hot-potato disruptions can have a substantial impact on large ISP backbones and thereby jeopardize the network robustness. As a result, there is a need for guidelines and tools to assist in the design of networks that minimize hot-potato disruptions. However, developing these tools is challenging due to the complex and subtle nature of the interactions between exterior and interior routing. In this paper, we address these challenges using an analytic model of hot-potato routing that incorporates metrics to evaluate network sensitivity to hot-potato disruptions. We then present a methodology for computing these metrics using measurements of real ISP networks. We demonstrate the utility of our model by analyzing the sensitivity of a large AS in a tier~1 ISP network.
Work-conserving distributed schedulers for Terabit routers
Authors: Pappu Prashanth , Turner Jonathan , Wong Ken
Published: January 2005

Buffered multistage interconnection networks offer one of the most scalable and cost-effective approaches to building high capacity routers. Unfortunately, the performance of such systems has been difficult to predict in the presence of the extreme traffic conditions that can arise in the Internet. Recent work introduced distributed scheduling, to regulate the flow of traffic in such systems. This work demonstrated, using simulation and experimental measurements, that distributed scheduling can deliver robust performance for extreme traffic. Here, we show that distributed schedulers can be provably
work-conserving
for speedups of 2 or more. Two of the three schedulers we describe were inspired by previously published crossbar schedulers. The third has no direct counterpart in crossbar scheduling. In our analysis, we show that distributed schedulers based on
blocking flows
in small-depth acyclic flow graphs can be work-conserving, just as certain crossbar schedulers based on maximal bipartite matchings have been shown to be work-conserving. We also study the performance of practical variants of these schedulers when the speedup is less than 2, using simulation.
A wavelet-based approach to detect shared congestion
Authors: Kim Min Sik , Kim Taekhyun , Shin YongJune , Lam Simon S. , Powers Edward J.
Published: January 2005

Per-flow congestion control helps endpoints fairly and efficiently share network resources. Better utilization of network resources can be achieved, however, if congestion management algorithms can determine when two different flows share a congested link. Such knowledge can be used to implement cooperative congestion control or improve the overlay topology of a P2P system. Previous techniques to detect shared congestion either assume a common source or destination node, drop-tail queueing, or a single point of congestion. We propose in this paper a novel technique, applicable to any pair of paths on the Internet, without such limitations. Our technique employs a signal processing method, wavelet denoising, to separate queueing delay caused by network congestion from various other delay variations. Our wavelet-based technique is evaluated through both simulations and Internet experiments. We show that, when detecting shared congestion of paths with a common endpoint, our technique provides faster convergence and higher accuracy while using fewer packets than previous techniques, and that it also accurately determines when there is no shared congestion. Furthermore, we show that our technique is robust and accurate for paths without a common endpoint or synchronized clocks; more specifically, it can tolerate a synchronization offset of up to one second between two packet flows.
Delayed stability and performance of distributed congestion control
Authors: Zhang Yueping , Kang Seong-Ryong , Loguinov Dmitri
Published: January 2005

Recent research efforts to design better Internet transport protocols combined with scalable Active Queue Management (AQM) have led to significant advances in congestion control. One of the hottest topics in this area is the design of discrete congestion control algorithms that are asymptotically stable under heterogeneous feedback delay and whose control equations do not explicitly depend on the RTTs of end-flows. In this paper, we show that max-min fair congestion control methods with a stable
symmetric
Jacobian remain stable under arbitrary feedback delay (including heterogeneous directional delays) and that the stability condition of such methods does
not
involve any of the delays. To demonstrate the practicality of the obtained result, we change the original controller in Kelly's work [14] to become robust under random feedback delay and fixed constants of the control equation. We call the resulting framework
Max-min Kelly Control
(MKC) and show that it offers smooth sending rate, exponential convergence to efficiency, and fast convergence to fairness, all of which make it appealing for future high-speed networks.
Modeling and performance analysis of BitTorrent-like peer-to-peer networks
Authors: Qiu Dongyu , Srikant R.
Published: January 2005

In this paper, we develop simple models to study the performance of BitTorrent, a second generation peer-to-peer (P2P) application. We first present a simple fluid model and study the scalability, performance and efficiency of such a file-sharing mechanism. We then consider the built-in incentive mechanism of BitTorrent and study its effect on network performance. We also provide numerical results based on both simulations and real traces obtained from the Internet.