bluuebunny/crossref_metadata_2025 huggingface dataset:
Some myths about famous mutual exclusion algorithms
Authors: Alagarsamy K.
Published: October 2004

Dekker's algorithm[9] is the historically first software solution to mutual exclusion problem for 2-process case. The first software solution for
n
-process case was subsequently proposed by Dijkstra[8]. These two algorithms have become de facto examples of mutual exclusion algorithms, for their historical importance. Since the publication of Dijkstra's algorithm, there have been many solutions proposed in the literature [24, 1, 2]. In that, Peterson's algorithm [21] is one among the very popular algorithms. Peterson's algorithm has been extensively analyzed for its elegance and compactness. This paper attempts to dispel the myths about some of the properties of these three remarkable algorithms, by a systematic analysis.
An associated object model for distributed systems
Authors: Hong Zhao , McCoy Wayne
Published: October 2004

As ISDNs develop, distributed applications on these networks will increase in number, scope and complexity. The distributed application environment will become more and more complicated. Distributed applications are as varied as application environments, requiring cooperations between them in different ways and to different extents. We describe here a new model that is designed to support distributed applications, called the
Associated Object Model
. In this model, multi-objects can communicate with each other through an abstract association, making it possible for application objects to cooperate in wider degree than was possible before. A mechanism supporting associations, broker, is introduced in this paper. By the mechanism, many associations between cooperating application objects can be established and maintained. The paper also includes some discussions about the description and implementation of the model and the mechanism.
The book review column
Authors: Gasarch William
Published: October 2004

In this column we review the books listed below. In addition there is a comment by Oded Goldreich on the review of his book
Foundations of Cryptography
.
F-RTO
Authors: Sarolahti Pasi , Kojo Markku , Raatikainen Kimmo
Published: October 2004

Spurious TCP retransmission timeouts (RTOs) have been reported to be a problem on network paths involving links that are prone to sudden delays due to various reasons. Especially many wireless network technologies contain such links. Spurious retransmission timeouts often cause unnecessary retransmission of several segments, which is harmful for TCP performance. Recent proposals for avoiding unnecessary retransmissions after a spurious RTO require use of TCP options which must be implemented and enabled at both ends of teh connection. We introduce a new TCP sender algorithm for recovery after a retransmission timeout and show that unnecessary retransmissions after a spurious retransmission timeout, improving the TCP performance considerably. The algorithm is friendly towards other TCP connections, because it follows the congestion control principles and injects packets to the network at same rate as a conventional TCP sender. We implemented the algorithm and compared its performance to conventional TCP and Eifel TCP when RTOs occurred either due to sudden delays or due to packet losses. The results show that our algorithm either improves performance or gives similar througput as the other TCP variants evaluated in different test cases.
Experience with an evolving overlay network testbed
Authors: Andersen David G. , Balakrishnan Hari , Kaashoek M. Frans , Morris Robert
Published: October 2004

The MIT RON testbed consists of 36 Internet-connected nodes at 31 different sities. It has been in operation for two years. This paper presents an overview of the testbed, summarizes some of the research for which it has proved useful, and presents the lessons we learned during its development. The testbed has been useful both for our own research and for that of external researchers becuase of its heterogeneous, diverse network connections; its homogenous hardware and software platform; its incremental, bottom-up development; and its easy configuration and management tools.
Web100
Authors: Mathis Matt , Heffner John , Reddy Raghu
Published: October 2004

TCP has become the dominant protocol for all network data transport because it presents a simple uniform data delivery service which is sufficient for most applications over all types of lower network layers. By its very nature, TCP's adaption and retransmission strategies hide all of the details of the lower layers from the application. For example the only symptom of spurious packet loss (or nearly any other network problem) is longer elapsed time and lower performance.This information hiding is fundamentally important to the growth of the Internet because it decouples the evolution of applications from the evolution of link layers. However it also hides valuable information from researchers, educators, network administrators, and other people who would benefit from insight into the inner workings of TCP and the lower layers.In this paper, we present an architecture and infrastructure that provides for per-connection TCP instrumentation to expose otherwise hidden protocol events. We show examples how the infrastructure can be used in support of research, education and advanced network diagnostic tools.Our work was motivated by the observation that since about 1985 network data rates for typical novice network users have fallen by about three orders of magnitude behind expert users (who have kept up with Moore's Law). We use the term "Wizard Gap" to describe this phenomenon. The Web100 and Net100 projects were formed as one step in closing the Wizard Gap.
Summary of minimal-total-processing-time drum and disk scheduling disciplines
Authors: Fuller Samuel H.
Published: October 2004

This article investigates the application of minimal-total-processing-time (MTPT) scheduling disciplines to rotating storage units when random arrival of requests is allowed. Fixed-head drum and moving-head disk storage units are considered and particular emphasis is placed on the relative merits of the MTPT scheduling discipline with respect to the shortest-latency-time-first (SLTF) scheduling discipline. The results of the simulation studies presented show that neither scheduling discipline is unconditionally superior to the other. For most fixed-head drum applications the SLTF discipline is preferable to MTPT, but for intra-cylinder disk scheduling the MTPT discipline offers a distinct advantage over the SLTF discipline. An implementation of the MTPT scheduling discipline is discussed and the computational requirements of the algorithm are shown to be comparable to SLTF algorithms. In both cases, the sorting procedure is the most time consuming phase of the algorithm.
A page allocation strategy for multiprogramming systems
Authors: Chamberlin Donald D. , Fulier Samuel H. , Liu Leonard Y.
Published: October 2004

In a multiprogramming, virtual-memory computing system, many processes compete simultaneously for system resources, which include CPU's, main memory page frames, and the transmission capacity of the paging drum. (We define a “process” here as a program with its own virtual memory, requiring an allocation of real memory and a CPU in order to execute). This paper studies ways of allocating resources to processes in order to maximize throughput in systems which are not CPU-bound.

As is customary, we define the multiprogramming “set” (MPS) as the set of processes eligible for allocation of resources at any given time. Each process in the MPS is allocated a certain number of page frames and allowed to execute, interrupted periodically by page faults. A process remains in the MPS until it finishes or exhausts its “time slice”, at which time it is demoted. We assume the existence of two resource managers within the operating system: The Paging Manager and the Scheduler. The function of the Paging Manager is to control the size of the MPS, and to allocate main storage page frames among those processes in the MPS. The function of the Scheduler is to assign time-slice lengths to the various processes, and to define a promotion order among those processes not currently in the MPS. The Scheduler must ensure that system responsiveness is adequate, while the Paging Manager is primarily concerned with throughput. This paper studies possible strategies for the Paging Manager. A strategy for the Scheduler is proposed in (2).
Polynomial complete scheduling problems
Authors: Ullman J. D.
Published: October 2004

We show that the problem of finding an optimal schedule for a set of jobs is polynomial complete even in the following two restricted cases.

(1) All jobs require one time unit.

(2) All jobs require one or two time units, and there are only two processors.

As a consequence, the general preemptive scheduling problem is also polynomial complete.

These results are tantamount to showing that the scheduling problems mentioned are intractable.
Bounds on scheduling with limited resources
Authors: Garey M. R. , Grehem R. L.
Published: October 2004

A number of authors (of. [12],[6], [7],[3],[11],[4],[5],[9]) have recently been concerned with scheduling problems associated with a certain model of an abstract multiprocessing system (to be described in the next section) and, in particular, with bounds on the worst-case behavior of this system as a function of the way in which the inputs are allowed to vary. In this paper, we introduce an additional element of realism into the model by postulating the existence of a set of “resources” with the property that at no time may the system use more than some predetermined amount of each resource. With this extra constraint taken into consideration, we derive a number of bounds on the behavior of this augmented system. It will be seen that this investigation leads to several interesting results in graph theory and analysis.
In their own words
Authors: Reich Blaize Horner , Nelson Kay M.
Published: October 2004

This research investigated CIOs'view of the changes driving and occurring in their in-house IT organizations. Results of interviews with 50 CIOs and IT leaders from 22 organizations in Canada and the U.S. suggest three main drivers of change for in-house IT organizations: rapid strategic business change, pervasive IT with an experienced user community, and e-business and technology complexity. These drivers are creating changes in all parts of the IT organization: structure and roles, application development, technology architectures, and skills and knowledge of IT practitioners. According to CIOs, their virtual, global IT organizations need to move even closer towards the strategic centre of the company, requiring increased business knowledge, improved ability to influence and negotiate, and a renewed focus on standardized architectures, metrics, and value creation.
Reaching agreement on an unknown network with partial graphic information
Authors: Wang S. C. , Yan K. Q. , Cheng C. F.
Published: October 2004

The Byzantine Agreement (BA) is an important topic in the reliable distributed system because the system can cope with the influences from faulty components when the agreement is achieved. In the literature concerned, the BA problem has been well formulated in a Fully Connected Network (FCN) and a Generalized Connected Network (GCN) under the assumption that each processor in the network has the common knowledge of the graphic information about the

entire

network structure. However, in the real world, each processor may not have the common knowledge of the graphic information about the

entire

network structure. That is, the processors may only have the

partial

knowledge as to their own graphic information. In this paper, the Byzantine Agreement problem will be visited in an Unknown Network (UNet) to increase the capability of fault tolerance by allowing faulty processors with dual failure mode. The proposed protocols, the Unknown Agreement Protocol (UAP) and the Relay Channel (RC), use the minimum number of rounds of message exchange and can tolerate the maximum number of faulty processors allowed.
Static analysis of Ravenscar programs
Authors: Amey P. N. , Dobbing B. J.
Published: October 2004

The Ravenscar Profile provides support for deterministic, multi-tasking programming as an integral part of a standardized language. A key element in the exploitation of the advantages of the Profile within the critical systems market is its use with verification tools. An established static analysis tool for this market operates on sequential programs in the SPARK language, which is an annotated subset of Ada 95 that avoids ambiguity and allows all language rule violations to be detected prior to execution. The authors show how the principles of SPARK have been successfully extended to encompass the Profile, thereby realising the benefits of constructing multi-tasking programs with the same degree of rigour that is currently possible using sequential SPARK.
Guidelines for interdomain traffic engineering
Authors: Feamster Nick , Borkenhagen Jay , Rexford Jennifer
Published: October 2004

Network operators must have control over the flow of traffic into, out of, and across their networks. However, the Border Gateway Protocol (BGP) does not facilitate common traffic engineering tasks, such as balancing load across multiple links to a neighboring AS or directing traffic to a different neighbor. Solving these problems is difficult because the number of possible changes to routing policies is too large to exhaustively test all possibilities, some changes in routing policy can have an unpredictable effect on the flow of traffic, and the BGP decision process implemented by router vendors limits an operator's control over path selection.We proposefundamental objectivesfor interdomain traffic engineering and specific guidelines for achieving these objectiveswithin the context of BGP. Using routing and traffic data from the AT&T backbone we show how certain BGP policy changes can move traffic in a predictable fashion, despite limited knowledge about the routing policies in neighboring AS's. Then, we show how operators can gain greater flexibility by relaxing some steps in the BGP decision process and ensuring that neighboring AS's send consistent advertisements at each peering location. Finally, we show that an operator can manipulate traffic efficiently by changing the routes for a small number of prefixes (or groups of related prefixes) that consistently receive a large amount of traffic.
Link layer-based TCP optimisation for disconnecting networks
Authors: Scott James , Mapp Glenford
Published: October 2004

This paper discusses a link layer approach to improving TCP performance in the face of periodic network disconnections. Network disconnections are encountered in many scenarios, including being out-of-range in a wireless network, during network handoff, and also in the case of Networked Surfaces, a novel LAN technology which provides the motivation for this work.A "smart link layer" employing repetition of selected packets at reconnection time is shown to improve TCP's utilisation of a disconnecting network to nearly 100%. This solution is also demonstrated in the context of a Networked Surface prototype, improving TCP performance for both bulk transfers and interactive traffic.The smart link layer solution is lightweight, requiring little processing and buffering only one packet per TCP connection. It is therefore easily retro-fitted to existing TCP-capable devices, without modifying the internal operation of those devices.
Local networking and internetworking in the V-system
Authors: Cheriton David R.
Published: October 2004

Local networking can be treated as a subset of internetworking for remote terminal access and file transfer. However, a distributed operating system, such as the V-System uses a local network more as an
extended backplane
than a fast, minature long-haul network.

This paper describes the use of server-based “intelligent gateways” to provide internetworking using standard protocols in conjunction with an efficient light-weight protocol for V IPC on a local network. Besides providing good local network performance, this design allows a gateway to act as an access control mechanism, addressing some reliability and security issues that arise with local networks.
Architecture and protocols of STELLA
Authors: Celandroni N. , Ferro E. , Lenzini L. , Segal B. M. , Olofsson K. S.
Published: October 2004

STELLA (Satellite Transmission Experiment Linking Laboratories) is a European wide-band data transmission experiment. STELLA makes use of the European Orbital Test Satellite (OTS) which provides a 2 Mb/s broadcast data transmission channel. The first phase of the STELLA project (STELLA/I) is summarized. The more important design characteristics of an improved version (STELLA/II) of STELLA/I are emphasized. Collaboration between STELLA/II and UNIVERSE projects in the framework of COST-11Bis is then outlined.
Interconnection of broadband local area networks
Authors: Sunshine C. , Kaufman D. , Ennis G. , Biba K.
Published: October 2004

Interconnection of multiple broadband local area networks to form an integrated packet transport system presents several challenges. To take full advantage of broadband systems, assignment of nodes to channels must be dynamic, leading to the use of a flat address space. Combined with the desire to avoid reliance on a central server or complex routing in packet forwarders, this addressing scheme leads to adoption of a controlled flooding technique to “discover” the best path to a destination node. This discovery procedure sets up a path through internetwork forwarders for use by subsequent packets to the same destination. This paper describes the design and implementation of such a technique in Sytek's LocalNet(TM) systems along with several refinements which increase performance and keep the worst case load for route discovery below a few percent of network capacity.
Beyond videotex
Authors: Nugent W. , Harding J.
Published: October 2004

This paper arrived late and can be found published in full on pages 257-260 of this Proceedings.
Real-time packet video over satellite channels
Authors: Cohen Danny
Published: October 2004

The paper describes major issues and problems in the use of packet satellite channels for real-time video images and suggests some solutions. The DARPA Wide Band Communication Network provides the testbed for this activity.

The main idea in this paper is the automatic online tradeoff between the quality and the dynamics of the communicated images in order to optimally adapt to the changes of the channel performance and of the scene to be communicated.

The paper discusses the problems of real-time packet video, suggests several techniques to cope with them, and describes some new approaches to the encoding of real-time video communication. The paper describes in more detail several encoding schemes based on this approach, using the 2-dimensional Discrete Cosine Transform (DCT).

Section-C describes issues which are arise in the application of packet satellite channels for real-time video communication. Section-D discusses a general approach which addresses these issues. Section-E describes a general methodology for signal coding and compression, and Section-F describes a scheme for the communication of video images using DCT of the raw images in an absolute way, unlike the four differential schemes which are described in Section-G. Section-H describes a scheme which self-corrects the accumulated quantization errors introduced by the encoding and compression. Such errors are totally eliminated for static images.
Identification in computer networks
Authors: Su Zaw-Sing
Published: October 2004

To communicate across a network system, entities within the system need to be able to identify one another. An identifier usually takes the form of a name or an address. Conventions for the assignment of these identifiers and their resolution affect many aspects of network design. Identification is thus a crucial issue for network architecture and standardization. In this paper, our discussion is first devoted to the semantics of names, addresses, and routes, with emphasis on the relationships among them. We then examine the implications of layered network architecture, syntactic differences of identifiers, and broadcast communication. Finally, we turn our attention to naming and addressing in large dynamic networks.
Implementing the ISO-OSI reference model
Authors: Popescu-Zeletin R.
Published: October 2004

The ISO-OSI reference model was the design framework for the implementation of a heterogeneous network in a local environment. The HMINET-2 is a network based on standards in data communication. The paper focus on the OSI model feasability and outlines the encountered problems and the adopted solutions in the network design and implementation.
Controlling window protocols for time-constrained communication in a multiple access environment
Authors: Kurose James F. , Schwartz Mischa , Yemini Yechiam
Published: October 2004

For many time-constrained communication applications, such as packetized voice, a critical performance measure is the percentage of messages which are transmitted within a given amount of time after their arrival at a sending station. We examine the use of a group random access protocol based on time windows for achieving time-constrained communication in a multiple access environment. First, we formulate a policy for controlling protocol operation in order to minimize the percentage of messages with waiting times greater than some given bound. A semi-Markov decision model is then developed for protocol operation and three of the four optimal control elements of this policy are then determined.

Although the semi-Markov decision model can also be used to obtain performance results, the procedure is too computationally expensive to be of practical use. Thus, an alternate performance model based on a centralized queueing system with impatient customers is developed. Protocol performance under the optimal elements of the control policy shows significant improvements over cases in which the protocol is not controlled in this manner. Simulation results are also presented to corroborate the analytic results.
Access and communication controls in an accounting information system
Authors: Rushinek Avi , Rushinek Sara F.
Published: October 2004

This paper involves the exploration of two very important security controls in a computerized accounting information system: (1) access controls, and (2) communication controls. The various specific access and communication controls are examined, analyzing their roles in an accounting information system's computer network.

The growing use of computers in the accounting information systems of the business environment, along with the presence of growing computer fraud, necessitate managements to implement stricter access and communication controls.
Verification of a methodology for designing reliable communication protocols
Authors: Lin Huai-An , Liu Ming T. , Graff Charles J.
Published: October 2004

In this paper we present a new methodology for designing reliable communication protocols. This methodology enhances communicating processes with a synchronization mechanism so that they can detect and resolve the errors caused by collisions automatically. The major advantages of this new methodology include: (1) the “state explosion” problem involved in protocol validation is alleviated; and (2) the burden of handling errors due to collisions is removed from the protocol designer. There is a need to verify that this methodology is applicable to arbitrary protocols. In this paper we also discuss the application of a program verification technique to this methodology.
Analysis of reliable broadcast in local-area networks
Authors: Wong J. W. , Gopal G.
Published: October 2004

The performance characteristics of a reliable broadcast protocol in a local-area network environment are analyzed. This protocol involves a source broadcasting a message to all destinations and collecting replies from these destinations. Reliability is achieved by using Send-and-Wait protocols for transmitting broadcast and reply messages. A queueing model is developed and results on the throughput and delay of the broadcast operation are obtained by approximate analysis. Numerical results showing the effect of model parameters on throughput are provided.
A decomposition method for the analysis and design of finite state protocols
Authors: Choi Tat Y. , Miller Raymond E.
Published: October 2004

Finite state automata have been applied with success to the modeling of Computer Network Protocols. The interaction of finite state machines can be very complex especially if the protocol involves a large number of states. To counteract the complexity of analysis and design, we propose an approach of decomposition. Through this approach, the protocol graph can be partitioned into subgraphs each having a unique entry node and zero or more exit nodes. The exit nodes of one subgraph can be connected only to the entry nodes of other subgraphs. From the standpoint of protocol analysis, the correctness of the entire protocol graph can be inferred from the correctness of individual protocol subgraphs. From the standpoint of protocol design, the individual protocol subgraphs can be designed to correspond to different phases of the protocol. If the individual protocol subgraphs are designed correctly and the connections between subgraphs conform to the structure discussed above, then we show that the entire protocol graph will operate correctly.
Dynamic selection of a performance-effective transmission sequence for token-passing networks with mobile nodes
Authors: Gold Yaron I. , Moran Shlomo
Published: October 2004

We describe a distributed method for keeping down “token-passing” overhead in a mobile multi-access network, by performing local corrections in the token-passing sequence as they become necessary due to changes in node spatial configuration. These corrections involve only a subset of the nodes in the network, thus reducing the required computational effort. The method consists of three distributed protocols. The first is for detecting deterioration and identifying a subset of nodes that constitutes a “problem area”, the second is to provide each node with the distances (propagation delays) to all other nodes, and the third is to use this topological information to construct a minimal spanning tree, from which a good “token passing” sequence can be derived. The second and third protocols may also have applications other than the one described here, such as position location, routing and broadcasting.
Graceful preemption for multi-link link layer protocols
Authors: Beckner M. Wm. , Starr T. J. J.
Published: October 2004

This paper discusses a powerful priority mechanism that can be used on a physical communication medium supporting multiple, independent, logical data links. This scheme allows a high priority message to immediately interrupt a lower priority message which is in the process of being transmitted, and yet will not require the retransmission of the first part of the lower priority message; hence, the term
graceful
preemption. Graceful preemption may be extended to furnish multiple priority levels similar to existing processor interrupt structures which implement multiple levels. This protocol may serve a single processor which handles several different processes, or several independent stations that share a common bus. Hence, priority levels can be enforced without the need for a centralized bus “master” or “arbitrator” unit. As an example, the application of graceful preemption to the Integrated Services Digital Network (ISDN) link access procedure, LAPD, is discussed.
Filing and printing services on a local-area network
Authors: Janson P. , Svobodova L. , Maehle E.
Published: October 2004

This paper describes the design and implementation of filing and printing services in a distributed system based on a token-ring local-area network. The main emphasis is put on the communication aspects of the client/server scenario: roles of a client and a server in a communication protocol, and the integration of communication protocols with applications.
Resource management in a distributed system
Authors: Yudkin Mark
Published: October 2004

In the Cambridge Distributed System, developed at the Computer Laboratory. Cambridge, terminals, machines and peripherals are separated by a ring network. A problem that arises is the establishment and control of suitable connexions between the individual components, so that users may use machines, machines may use peripherals or other machines, etc. in a secure manner.

This paper describes an experimental mechanism used to control the connexions and provide security in our particular system. The solution is not restricted to the Cambridge ring, although a different architecture may suggest alternative solutions more suited to its specific features. Some possibilities are discussed.
Interfaces between protocol layers on a multiprocessor system
Authors: Colon-Castro Wilfredo A. , Kirkman Deborah A.
Published: October 2004

A multi-layer, X.25 based protocol has been implemented on a multiprocessor system. The higher layer protocol resides in the system processor while the lower level protocol (X.25 levels 2 and 3) runs on a peripheral processor. This paper focuses on the boundary between the system and peripheral processors. It discusses how flow control is done, how control information is passed across the boundary, and the synchronization problems that arose. In addition, it describes effects on performance resulting from splitting the protocol across the two processors.
Hash-based IP traceback
Authors: Snoeren Alex C. , Partridge Craig , Sanchez Luis A. , Jones Christine E. , Tchakountio Fabrice , Kent Stephen T. , Strayer W. Timothy
Published: October 2004

The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet. Even in the absence of any deliberate attempt to disguise a packet's origin, wide-spread packet forwarding techniques such as NAT and encapsulation may obscure the packet's true source. Techniques have been developed to determine the source of large packet flows, but, to date, no system has been presented to track individual packets in an efficient, scalable fashion.We present a hash-based technique for IP traceback that generates audit trails for traffic within the network, and can trace the origin of a
single
IP packet delivered by the network in the recent past. We demonstrate that the system is effective, space-efficient (requiring approximately 0.5% of the link capacity per unit time in storage), and implementable in current or next-generation routing hardware. We present both analytic and simulation results showing the system's effectiveness.
Reliable group rekeying
Authors: Yang Yang Richard , Li X. Steve , Zhang X. Brian , Lam Simon S.
Published: October 2004

In secure group communications, users of a group share a common group key. A key server sends the group key to authorized new users as well as performs group rekeying for group users whenever the key changes. In this paper, we investigate scalability issues of reliable group rekeying, and provide a performance analysis of our group key management system (called keygem) based upon the use of key trees. Instead of rekeying after each join or leave, we use periodic batch rekeying to improve scalability and alleviate out-of-sync problems among rekey messages as well as between rekey and data messages. Our analyses show that batch rekeying can achieve large performance gains. We then investigate reliable multicast of rekey messages using proactive FEC. We observe that rekey transport has an eventual reliability and a soft real-time requirement, and that the rekey workload has a sparseness property, that is, each group user only needs to receive a small fraction of the packets that carry a rekey message sent by the key server. We also investigate tradeoffs between server and receiver bandwidth requirements versus group rekey interval, and show how to determine the maximum number of group users a key server can support.
Aging through cascaded caches
Authors: Cohen Edith , Kaplan Haim
Published: October 2004

The Web is a distributed system, where data is stored and disseminated from both
origin
servers and
caches
. Origin servers provide the most up-to-date copy whereas caches store and serve copies that had been cached for a while. Origin servers do not maintain per-client state, and weak-consistency of cached copies is maintained by the origin server attaching to each copy an expiration time. Typically, the lifetime-duration of an object is fixed, and as a result, a copy fetched directly from its origin server has maximum time-to-live (TTL) whereas a copy obtained through a cache has a shorter TTL since its
age
(elapsed time since fetched from the origin) is deducted from its lifetime duration. Thus, a cache that is served from a cache would incur a higher miss-rate than a cache served from origin servers. Similarly, a high-level cache would receive more requests from the same client population than an origin server would have received. As Web caches are often served from other caches (e.g., proxy and reverse-proxy caches), age emerges as a performance factor. Guided by a formal model and analysis, we use different inter-request time distributions and trace-based simulations to explore the effect of age for different cache settings and configurations. We also evaluate the effectiveness of frequent pre-term refreshes by higher-level caches as a means to decrease client misses. Beyond Web content distribution, our conclusions generally apply to systems of caches deploying expiration-based consistency.
IPNL
Authors: Francis Paul , Gummadi Ramakrishna
Published: October 2004

This paper presents and analyzes IPNL (for IP Next Layer), a NAT-extended Internet protocol architecture designed to scalably solve the address depletion problem of IPv4. A NAT-extended architecture is one where only hosts and NAT boxes are modified. IPv4 routers and support protocols remain untouched. IPNL attempts to maintain all of the original characteristics of IPv4, most notably address prefix location independence. IPNL provides true site isolation (no renumbering), and allows sites to be multi-homed without polluting the default-free routing zone with per-site prefixes. We discuss IPNL's architectural benefits and drawbacks, and show that it comes acceptably close to achieving its goals.
Scalable on-demand media streaming with packet loss recovery
Authors: Mahanti Anirban , Eager Derek L. , Vernon Mary K. , Sundaram-Stukel David
Published: October 2004

Inspired by recent techniques for reliable bulk data distribution, this paper develops scalable protocols for reliable on-demand delivery of streaming media. Models are developed that quantify the best possible scalability for given client characteristics. The results of the models are used to guide the design and assess the performance of the proposed streaming techniques. The new protocols, RPB and RBS, are relatively simple to implement and achieve nearly the best possible scalability and efficiency for a given set of client characteristics and desirable/feasible media quality.
Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management
Authors: Kunniyur Srisankar , Srikant R.
Published: October 2004

Virtual Queue-based marking schemes have been recently proposed for AQM (Active Queue Management) in Internet routers. We consider a particular scheme, which we call the Adaptive Virtual Queue (AVQ), and study its following properties: stability in the presence of feedback delays, its ability to maintain small queue lengths and its robustness in the presence of extremely short flows (the so-called
web mice
). Using a mathematical tool motivated by the earlier work of Hollot et al, we present a simple rule to design the parameters of the AVQ algorithm. We then compare its performance through simulation with several well-known AQM schemes such as RED, REM, PI controller and a non-adaptive virtual queue algorithm. With a view towards implementation, we show that AVQ can be implemented as a simple token bucket using only a few lines of code.
An investigation of geographic mapping techniques for internet hosts
Authors: Padmanabhan Venkata N. , Subramanian Lakshminarayanan
Published: October 2004

In this paper, we ask whether it is possible to build an IP address to geographic location mapping service for Internet hosts. Such a service would enable a large and interesting class of location-aware applications. This is a challenging problem because an IP address does not inherently contain an indication of location.We present and evaluate three distinct techniques, collectively referred to as
IP2Geo
, for determining the geographic location of Internet hosts. The first technique,
Geo Track
, infers location based on the DNS names of the target host or other nearby network nodes. The second technique,
GeoPing
, uses network delay measurements from geographically distributed locations to deduce the coordinates of the target host. The third technique,
GeoCluster
, combines partial (and possibly inaccurate) host-to-location mapping information and BGP prefix information to infer the location of the target host. Using extensive and varied data sets, we evaluate the performance of these techniques and identify fundamental challenges in deducing geographic location from the IP address of an Internet host.
Fair queuing for aggregated multiple links
Authors: Blanquer Josep M. , Özden Banu
Published: October 2004

Provisioning of a shared server with guarantees is an important scheduling task that has led to significant work in a number of areas including link scheduling. Fair Queuing algorithms provide a method for proportionally sharing a single server among competing flows, however, they do not address the problem of sharing multiple servers. Multiserver systems arise in a number of applications including link aggregation, multiprocessors and multi-path storage I/O. In this paper we introduce a new service discipline for multi-server systems that provides guarantees for competing flows. We prove that this new service discipline is a close approximation of the idealized Generalized Processor Sharing (GPS) discipline. We calculate its maximum packet delay and service discrepancy with respect to GPS. We also discuss its relevance to several applications, in particular, Ethernet link aggregation.
Scalable packet classification
Authors: Baboescu Florin , Varghese George
Published: October 2004

Packet classification is important for applications such as firewalls, intrusion detection, and differentiated services. Existing algorithms for packet classification reported in the literature scale poorly in either time or space as filter databases grow in size. Hardware solutions such as TCAMs do not scale to large classifiers. However, even for large classifiers (say 100,000 rules), any packet is likely to match a few (say 10) rules. Our paper seeks to exploit this observation to produce a scalable packet classification scheme called Aggregated Bit Vector (ABV). Our paper takes the bit vector search algorithm (BV) described in [11] (which takes linear time) and adds two new ideas, recursive aggregation of bit maps and filter rearrangement, to create ABV (which can take logarithmic time for many databases). We show that ABV outperforms BV by an order of magnitude using simulations on both industrial firewall databases and synthetically generated databases.
Hop by hop multicast routing protocol
Authors: Costa Lu Henrique M. K. , Fdida Serge , Duarte Otto
Published: October 2004

IP Multicast is facing a slow take-off although it is a hotly debated topic since more than a decade. Many reasons are responsible for this status. Hence, the Internet is likely to be organized with both unicast and multicast enabled networks. Thus, it is of utmost importance to design protocols that allow the progressive deployment of the multicast service by supporting unicast clouds. This paper proposes HBH (Hop-By-Hop multicast routing protocol). HBH adopts the source-specific channel abstraction to simplify address allocation and implements data distribution using recursive unicast trees, which allow the transparent support of unicast-only routers. Additionally, HBH is original because its tree construction algorithm takes into account the unicast routing asymmetries. As most multicast routing protocols rely on the unicast infrastructure, these asymmetries impact the structure of the multicast trees. We show through simulation that HBH outperforms other multicast routing protocols in terms of the delay experienced by the receivers and the bandwidth consumption of the multicast trees.
Extending equation-based congestion control to multicast applications
Authors: Widmer Jörg , Handley Mark
Published: October 2004

In this paper we introduce TFMCC, an equation-based multicast congestion control mechanism that extends the TCP-friendly TFRC protocol from the unicast to the multicast domain. The key challenges in the design of TFMCC lie in scalable round-trip time measurements, appropriate feedback suppression, and in ensuring that feedback delays in the control loop do not adversely affect fairness towards competing flows. A major contribution is the feedback mechanism, the key component of end-to-end multicast congestion control schemes. We improve upon the well-known approach of using exponentially weighted random timers by biasing feedback in favor of low-rate receivers while still preventing a response implosion. We evaluate the design using simulation, and demonstrate that TFMCC is both TCP-friendly and scales well to multicast groups with thousands of receivers. We also investigate TFMCC's weaknesses and scaling limits to provide guidance as to application domains for which it is well suited.
Understanding BGP misconfiguration
Authors: Mahajan Ratul , Wetherall David , Anderson Tom
Published: October 2004

It is well-known that simple, accidental BGP configuration errors can disrupt Internet connectivity. Yet little is known about the frequency of misconfiguration or its causes, except for the few spectacular incidents of widespread outages. In this paper, we present the first quantitative study of BGP misconfiguration. Over a three week period, we analyzed routing table advertisements from 23 vantage points across the Internet backbone to detect incidents of misconfiguration. For each incident we polled the ISP operators involved to verify whether it was a misconfiguration, and to learn the cause of the incident. We also actively probed the Internet to determine the impact of misconfiguration on connectivity.Surprisingly, we find that configuration errors are pervasive, with 200-1200 prefixes (0.2-1.0% of the BGP table size) suffering from misconfiguration each day. Close to 3 in 4 of all new prefix advertisements were results of misconfiguration. Fortunately, the connectivity seen by end users is surprisingly robust to misconfigurations. While misconfigurations can substantially increase the update load on routers, only one in twenty five affects connectivity. While the causes of misconfiguration are diverse, we argue that most could be prevented through better router design.
Realistic BGP traffic for test labs
Authors: Maennel Olaf , Feldmann Anja
Published: October 2004

This paper examines the possibility of generating realistic routing tables of arbitrary size along with realistic BGP updates of arbitrary frequencies via an automated tool deployable in a small-scale test lab. Such a tool provides the necessary foundations to study such questions as: the limits of BGP scalability, the reasons behind routing instability, and the extent to which routing instability influences the forwarding performance of a router.We find that the answer is affirmative. In this paper we identify important characteristics/metrics of routing tables and updates which provide the foundation of the proposed BGP workload model. Based on the insights of an extensive characterization of BGP traffic according to such metrics as prefix length distributions, fanout, amount of nesting of routing table prefixes, AS path length, number and times between BGP update bursts and number and times between BGP session resets, etc., we introduce our prototype tool, rtg. rtg realizes the workload model and is capable of generating realistic BGP traffic. Through its flexibility and parameterization rtg enables us to study the sensibilities of test systems in a repeatable and consistent manner while still providing the possibility of capturing the different characteristics from different vantage points in the network.
SOS
Authors: Keromytis Angelos D. , Misra Vishal , Rubenstein Dan
Published: October 2004

Denial of service (DoS) attacks continue to threaten the reliability of networking systems. Previous approaches for protecting networks from DoS attacks are reactive in that they wait for an attack to be launched before taking appropriate measures to protect the network. This leaves the door open for other attacks that use more sophisticated methods to mask their traffic.We propose an architecture called Secure Overlay Services (SOS) that proactively prevents DoS attacks, geared toward supporting Emergency Services or similar types of communication. The architecture is constructed using a combination of secure overlay tunneling, routing via consistent hashing, and filtering. We reduce the probability of successful attacks by (i) performing intensive filtering near protected network edges, pushing the attack point perimeter into the core of the network, where high-speed routers can handle the volume of attack traffic, and (ii) introducing randomness and anonymity into the architecture, making it difficult for an attacker to target nodes along the path to a specific SOS-protected destination.Using simple analytical models, we evaluate the likelihood that an attacker can successfully launch a DoS attack against an SOS-protected network. Our analysis demonstrates that such an architecture reduces the likelihood of a successful attack to minuscule levels.
Internet indirection infrastructure
Authors: Stoica Ion , Adkins Daniel , Zhuang Shelley , Shenker Scott , Surana Sonesh
Published: October 2004

Attempts to generalize the Internet's point-to-point communication abstraction to provide services like multicast, anycast, and mobility have faced challenging technical problems and deployment barriers. To ease the deployment of such services, this paper proposes an overlay-based Internet Indirection Infrastructure ( I3) that offers a rendezvous-based communication abstraction. Instead of explicitly sending a packet to a destination, each packet is associated with an identifier; this identifier is then used by the receiver to obtain delivery of the packet. This level of indirection decouples the act of sending from the act of receiving, and allows I3 to efficiently support a wide variety of fundamental communication services. To demonstrate the feasibility of this approach, we have designed and built a prototype based on the Chord lookup protocol.