bluuebunny/crossref_metadata_2025 huggingface dataset:
Selfish behavior and stability of the internet:
Authors: Akella Aditya , Seshan Srinivasan , Karp Richard , Shenker Scott , Papadimitriou Christos
Published: October 2004

For years, the conventional wisdom [7, 22] has been that the continued stability of the Internet depends on the widespread deployment of "socially responsible" congestion control. In this paper, we seek to answer the following fundamental question: If network end-points behaved in a selfish manner, would the stability of the Internet be endangered?.We evaluate the impact of greedy end-point behavior through a game-theoretic analysis of TCP. In this "TCP Game" each flowattempts to maximize the throughput it achieves by modifying its congestion control behavior. We use a combination of analysis and simulation to determine the Nash Equilibrium of this game. Our question then reduces to whether the network operates efficiently at these Nash equilibria.Our findings are twofold. First, in more traditional environments -- where end-points use TCP Reno-style loss recovery and routers use drop-tail queues -- the Nash Equilibria are reasonably efficient. However, when endpoints use more recent variations of TCP (e.g., SACK) and routers employ either RED or drop-tail queues, the Nash equilibria are very inefficient. This suggests that the Internet of the past could remain stable in the face of greedy end-user behavior, but the Internet of today is vulnerable to such behavior. Second, we find that restoring the efficiency of the Nash equilibria in these settings does not require heavy-weight packet scheduling techniques (e.g., Fair Queuing) but instead can be done with a very simple stateless mechanism based on CHOKe [21].
Measuring ISP topologies with rocketfuel
Authors: Spring Neil , Mahajan Ratul , Wetherall David
Published: October 2004

To date, realistic ISP topologies have not been accessible to the research community, leaving work that depends on topology on an uncertain footing. In this paper, we present new Internet mapping techniques that have enabled us to directly measure router-level ISP topologies. Our techniques reduce the number of required traces compared to a brute-force, all-to-all approach by three orders of magnitude without a significant loss in accuracy. They include the use of BGP routing tables to focus the measurements, exploiting properties of IP routing to eliminate redundant measurements, better alias resolution, and the use of DNS to divide each map into POPs and backbone. We collect maps from ten diverse ISPs using our techniques, and find that our maps are substantially more complete than those of earlier Internet mapping efforts. We also report on properties of these maps, including the size of POPs, distribution of router outdegree, and the inter-domain peering structure. As part of this work, we release our maps to the community.
Wave and equation based rate control using multicast round trip time
Authors: Luby Michael , Goyal Vivek K. , Skaria Simon , Horn Gavin B.
Published: October 2004

This paper introduces Wave and Equation Based Rate Control (WEBRC), the first multiple rate multicast congestion control protocol to be equation based. The equation-based approach enforces fairness to TCP with the benefit that fluctuations in the flow rate are small in comparison to TCP.This paper also introduces the multicast round trip time (MRTT), a multicast analogue of the unicast round trip time (RTT). The MRTT is fundamental to the equation-based protocol that each receiver uses to adjust its reception rate. Each receiver independently measures its own MRTT without placing any added messaging burden on the receiver, the sender or the intermediate network elements. Benefits provided by the MRTT include those that the RTT provides to TCP, e.g., reduced reception rates in reaction to buffer filling and fair sharing of bottleneck links. In addition, the use of MRTT is shown to synchronize and equalize the reception rates of proximate receivers and to cause reception rates to increase as the density of receivers increases.Another innovation of WEBRC is the idea of transmitting data with waves: the transmission rate on a channel is periodic, with an exponentially decreasing form during an active period followed by a quiescent period. Benefits of using waves include insensitivity to large IGMP leave latency; a frequency of joins and leaves by each receiver that is small and independent of the receiver reception rate; the use of a small number of multicast channels; fine-grained control over the receiver reception rate; and minimal, at times nonexistent, losses due to buffer overflow.
Scalable application layer multicast
Authors: Banerjee Suman , Bhattacharjee Bobby , Kommareddy Christopher
Published: October 2004

We describe a new scalable application-layer multicast protocol, specifically designed for low-bandwidth, data streaming applications with large receiver sets. Our scheme is based upon a hierarchical clustering of the application-layer multicast peers and can support a number of different data delivery trees with desirable properties.We present extensive simulations of both our protocol and the Narada application-layer multicast protocol over Internet-like topologies. Our results show that for groups of size 32 or more, our protocol has lower link stress (by about 25%), improved or similar end-to-end latencies and similar failure recovery properties. More importantly, it is able to achieve these results by using orders of magnitude lower control traffic.Finally, we present results from our wide-area testbed in which we experimented with 32-100 member groups distributed over 8 different sites. In our experiments, average group members established and maintained low-latency paths and incurred a maximum packet loss rate of less than 1% as members randomly joined and left the multicast group. The average control overhead during our experiments was less than 1 Kbps for groups of size 100.
Route oscillations in I-BGP with route reflection
Authors: Basu Anindya , Ong Chih-Hao Luke , Rasala April , Shepherd F. Bruce , Wilfong Gordon
Published: October 2004

We study the route oscillation problem [16, 19] in the Internal Border Gateway Protocol (I-BGP)[18] when route reflection is used. We propose a formal model of I-BGP and use it to show that even deciding whether an I-BGP configuration with route reflection can converge is an NP-Complete problem. We then propose a modification to I-BGP and show that route reflection cannot cause the modified protocol to diverge. Moreover, we show that the modified protocol converges to the same stable routing configuration regardless of the order in which messages are sent or received.
On the characteristics and origins of internet flow rates
Authors: Zhang Yin , Breslau Lee , Paxson Vern , Shenker Scott
Published: October 2004

This paper considers the distribution of the rates at which flows transmit data, and the causes of these rates. First, using packet level traces from several Internet links, and summary flow statistics from an ISP backbone, we examine Internet flow rates and the relationship between the rate and other flow characteristics such as size and duration. We find, as have others, that while the distribution of flow rates is skewed, it is not as highly skewed as the distribution of flow sizes. We also find that for large flows the size and rate are highly correlated. Second, we attempt to determine the cause of the rates at which flows transmit data by developing a tool, T-RAT, to analyze packet-level TCP dynamics. In our traces, the most frequent causes appear to be network congestion and receiver window limits.
An end-to-end approach to globally scalable network storage
Authors: Beck Micah , Moore Terry , Plank James S.
Published: October 2004

This paper discusses the application of end-to-end design principles, which are characteristic of the architecture of the Internet, to network storage. While putting storage into the network fabric may seem to contradict end-to-end arguments, we try to show not only that there is no contradiction, but also that adherence to such an approach is the key to achieving true scalability of shared network storage. After discussing end-to-end arguments with respect to several properties of network storage, we describe the Internet Backplane Protocol and the exNode, which are tools that have been designed to create a network storage substrate that adheres to these principles. The name for this approach is Logistical Networking, and we believe its use is fundamental to the future of truly scalable communication.
Virtual teams
Authors: Powell Anne , Piccoli Gabriele , Ives Blake
Published: October 2004

Information technology is providing the infrastructure necessary to support the development of new organizational forms. Virtual teams represent one such organizational form, one that could revolutionize the workplace and provide organizations with unprecedented levels of flexibility and responsiveness. As the technological infrastructure necessary to support virtual teams is now readily available, further research on the range of issues surrounding virtual teams is required if we are to learn how to manage them effectively. While the findings of team research in the traditional environment may provide useful pointers, the idiosyncratic structural and contextual issues surrounding virtual teams call for specific research attention.This article provides a review of previously published work and reports on the findings from early virtual team research in an effort to take stock of the current state of the art. The review is organized around the input - process - output model and categorizes the literature into issues pertaining to inputs, socio-emotional processes, task processes, and outputs. Building on this review we critically evaluate virtual team research and develop research questions that can guide future inquiry in this fertile are of inquiry.
Pancakes, puzzles, and polynomials
Authors: Frost Christopher , Peck Michael , Evans David
Published: October 2004

The Cracker Barrel peg game is a simple, one-player game commonly found on tables at pancake restaurants. In this paper, we consider the computational complexity of the Cracker Barrel problem. We show that a variation of a generalization of the problem is NP-complete.
Reverse engineering the Internet
Authors: Spring Neil , Wetherall David , Anderson Thomas
Published: October 2004

To provide insight into Internet operation and performance, recent efforts have measured various aspects of the Internet, developing and improving measurement tools in the process. In this paper, we argue that these independent advances present the community with a startling opportunity: the collaborative reverse-engineering of the Internet. By this, we mean annotating a map of the Internet with properties such as: client populations, features and workloads; network ownership, capacity, connectivity, geography and routing policies; patterns of loss, congestion, failure and growth; and so forth. This combination of properties it greater than the sum of its parts, and exposes the attributes of network design easily overlooked by simpler, uncorrelated models. We argue that reverse engineering the Internet is feasible based on continuing improvements in measurement techniques, the potential to infer new properties from external measurements, and an accounting of the resources required to complete the process.
Turning 802.11 inside-out
Authors: Bhagwat Pravin , Raman Bhaskaran , Sanghi Dheeraj
Published: October 2004

The past decade has seen communication revolution in the form of cellular telephony as well as the Internet, but much of it has been restricted to the developed world and metro pockets in the developing world. While the use of cellular technologies can cut down on the time to deploy access networks, the cost economics make this non-viable in growing telecom economies. In the Digital Gangetic Plains (DGP) project, we are exploring the use of 802.11 as a long-distance access technology. 802.11 is currently cost-priced due to competitive mass production and hence is attractive for low cost and rapid deployment in rural areas.We have built an extensive testbed in a rural setting consisting of multi-hop directional 802.11 links, the testbed spanning up to 80km at its longest. To our knowledge such a long-distance, multi-hop testbed based on 802.11 is unique thus far. While 802.11 is attractive in terms of cost economics, it was inherently designed for indoor use. Our novel use of the technology for outdoor, long-distance access links presents several challenges. Our experience with the testbed has brought several research as well as operational issues to the fore. In this paper, we describe the novel technical challenges that lie ahead in using 802.11 to bridge the digital divide.
Preventing Internet denial-of-service with capabilities
Authors: Anderson Tom , Roscoe Timothy , Wetherall David
Published: October 2004

In this paper, we propose a new approach to preventing and constraining denial-of-service (DoS) attacks. Instead of being able to send anything to anyone at any time, in our architecture, nodes must first obtain "permission to send" from the destination; a receiver provides tokens, or capabilities, to those senders whose traffic it agrees to accept. The senders then include these tokens in packets. This enables verification points distributed around the network to check that traffic has been certified as legitimate by both endpoints and the path in between, and to cleanly discard unauthorized traffic. We show that our approach addresses many of the limitations of the currently popular approaches to DoS based on anomaly detection, traceback, and pushback. Further, we argue that our approach can be readily implemented in today's technology, is suitable for incremental deployment, and requires no more of a security infrastructure than that already needed to fix BGP's security weaknesses. Finally, our proposal facilitates innovation in application and networking protocols, something increasingly curtailed by existing DoS measures.
Unveiling the transport
Authors: Mogul Jeffrey , Brakmo Lawrence , Lowell David E. , Subhraveti Dinesh , Moore Justin
Published: October 2004

Traditional application programming interfaces for transport protocols make a virtue of hiding most internal per-connection state. We argue that this information-hiding precludes many potentially useful application features and performance optimizations. We advocate a disciplined, portable, and secure interface that gives applications both "get" and "set" access to transport connection state.
Exposing resource tradeoffs in region-based communication abstractions for sensor networks
Authors: Welsh Matt
Published: October 2004

We argue that communication abstractions for wireless sensor networks should expose the tradeoff between accuracy and resource usage, allowing applications to adapt to changing network conditions and tune energy and bandwidth requirements. We describe
abstract regions
, a family of spatial operators that capture local communication with regions of the network, which may be defined in terms of radio connectivity, geographic location, or other properties of nodes. Abstract regions provide feedback on the quality of collective operations, and expose an interface for tuning resource consumption. We present the implementation of abstract regions in the TinyOS programming environment, as well as preliminary results demonstrating their use of building adaptive sensor network applications.
Coping with irregular spatio-temporal sampling in sensor networks
Authors: Ganesan Deepak , Ratnasamy Sylvia , Wang Hanbiao , Estrin Deborah
Published: October 2004

Wireless sensor networks have attracted attention from a diverse set of researchers, due to the unique combination of distributed, resource and data processing constraints. However, until now, the lack of real sensor network deployments have resulted in ad-hoc assumptions on a wide range of issues including topology characteristics and data distribution. As deployments of sensor networks become more widespread [1, 2], many of these assumptions need to be revisited.This paper deals with the fundamental issue of spatio-temporal irregularity in sensor networks We make the case for the existence of such irregular spatio-temporal sampling, and show that it impacts many performance issues in sensor networks. For instance, data aggregation schemes provide inaccurate results, compression efficiency is dramatically reduced, data storage skews storage load among nodes and incurs significantly greater routing overhead. To mitigate the impact of irregularity, we outline a spectrum of solutions. For data aggregation and compression, we propose the use of spatial interpolation of data (first suggested by Ganeriwal et al in [3] and temporal signal segmentation followed by alignment. To reduce the cost of data-centric storage and routing, we propose the use of virtualization, and boundary detection.
Cryptanalysis of a user authentication scheme using hash functions
Authors: Lee Sung-Woon , Kim Hyun-Sung , Yoo Kee-Young
Published: October 2004

Recently, Lee et al. proposed an improved scheme, called LLH scheme, to solve a security problem of guessing attack in the Peyravian-Zunic password scheme. The scheme comprises a password authentication protocol and a password change protocol. However, we discuss that the LLH scheme has several security problems: the scheme is still vulnerable to the guessing attack; the scheme cannot also prevent the stolen-verifier attack; the password change protocol in scheme is vulnerable to a denial of service attack.
An approach to the formal verification of the three-principal cryptographic protocols
Authors: Zhang Yuqing , Liu Xiuying
Published: October 2004

Based on the model checking theory, we derive the Running-Mode Analysis of three-principal cryptographic protocols from the Running-Mode Analysis of two-principal cryptographic protocols. To test this method, we analyze the Davis Swick protocol and successfully prove the security this protocol. Therefore, we can draw a conclusion that Running-Mode Analysis of three-principal cryptographic protocol is available.
Data abstraction
Authors: Yehudai Amiram
Published: October 2004

Abstract data types and abstract data objects are examined and contrasted in the context of Ada(*) and in general. Guidelines for the use of these two concepts are suggested with special emphasis on objects.
Parallel Quicksort
Authors: Cohen Norman H.
Published: October 2004

We develop an Ada Quicksort program which sorts disjoint subsections of an array concurrently. This exercise reveals pitfalls which Ada programmers using tasks must strive to avoid.
Using Ada for commercial software
Authors: Gardner Michael R.
Published: October 2004

One of the principal concerns of the U .S . Department of Defense in sponsoring the design of Ada was that the new language should be suitable for use in embedded military computer systems. However, Ada's designers included many features which make the language especially useful for a much wider class of software projects--specifically, large-scale systems of programs. lntellimac 's experience over the past year with two such projects, a payroll system and a system of order--entry with inventory control, illustrates the great advantages of Ada for such standard commercial applications. I shall discuss our experiences with packages, strong typing, enumeration types , attributes, and exceptions.
The middle way approach for Ada based PDL syntax
Authors: Gabber Eran
Published: October 2004

This note presents a middle way approach in Ada based PDL syntax. The proposed PDL syntax allows simple syntactic entities like TRW's PDL [1, 2], fully formed constructs like IBM's PDL and any degree of design details between these two extremes.This PDL represents missing design parts in a natural and consistent way by adding the 'not defined yet' lexical element to Ada syntax. This new lexical element consists of any free text enclosed in curly brackets and can replace almost any Ada language construct.
The Department of Defense Software Initiative
Authors: Emery David E.
Published: October 2004

The Department of Defense Software Initiative, announced at the Ada Conference, is summarized. The initiative is a seven year plan designed to increase productivity through improving personnel resources, improving the power of tools and increasing tool use.
Ada design, Jovial implementation
Authors: Bein Edward
Published: October 2004

Although the Department of Defense has not yet awarded contracts for embedded systems implemented in Ada, it has begun to award contracts that specify Ada as the design language. Ford Aerospace and Communications Corporation is already at work on one such contract, designing a system in Ada which it will implement in Jovial (J73) and assembly language. When work began, the Ada Technology Project at Ford Aerospace was asked to prepare an Ada style guide for system designers. The purpose of the guide was to promote the creation of system designs in Ada that would have straightforward Jovial implementations.This article presents the style guide in revised form.
Ada packages and the user's conceptual model
Authors: Mac an Airchinnign Mícheál
Published: October 2004

The private type mechanism of Ada is used to hide the details of the structure of the type from the user (as programmer). Thus, it is possible to build Ada packages that are correct implementations of abstract data types whereby the only operations available on the data type are precisely those made externally available to the user in the visible part of the package specification. To be able to use such a package, the semantics of the operations in the visible part must be unambiguously conveyed to the user. I propose a formal specification and classification of the user of such Ada packages. Associated with each user is an appropriate UCM (user's conceptual model) of the application domain corresponding to which there exists the respective Ada package(s). Such a UCM would incorporate the necessary set of semantics for understanding the visible part of the package(s). In an APSE (Ada programming support environment) it is envisaged that one of the key tools will be an Ada-oriented UIMS (user interface management system) which will perform a function for Ada programmers much like that which a DBMS (data base management system) currently performs for users of a data base. The specification and implementation of the (abstract) data type "complex number" as an Ada package is used as an example.
The simplest?
Authors: Agerberg Jonas
Published: October 2004

The problem with the dining philosophers is one of the pet models for illustration of the various problems (deadlock, starvation etc) that may occur when concurrent tasks have conflicting interests.Various solutions have been presented in textbooks on Ada, most of them correct but usually more clumsy than necessary. The solution presented here is based upon one single and simple strategy which leads to a clean and simple program structure.
KAPSE implementation strategies
Authors: Wilder William L.
Published: October 2004

This paper discusses the strategies for KAPSE implementations by defining the KAPSE that must be supported from the users' point of view and by providing hardware and software criteria against which any KAPSE implementation strategy must be judged. The users' view of the KAPSE is really their view of the MAPSE (or APSE) which is supported by the KAPSE. Any KAPSE implementation strategy can be described as either an implementation of the KAPSE on a bare machine or an implementation of the KAPSE in conjunction with the host machine's operating system. The concerns for the bare machine KAPSE implementation strategy are centered around the hardware criteria of the bare machine's Instruction Set Architecture and hardware configuraton for the bare machine. Examples from the ALS and AIE are supplied in this discussion.The operating systems KAPSE implementation strategies address the situations where the KAPSE is implemented on top of or beside the host machine's operating system. The concerns for the operating system KAPSE implementation strategy are centered around the software criteria of program execution, I/O support, and the KAPSE database for the KAPSE software. Program execution, I/O support, and the KAPSE database includes: process execution and communication: Ada I/O support and virtual terminals; and the KAPSE database access software, respectively. As before, examples from the ALS, AIE, and UNIX are supplied in this discussion. Finally, the KAPSE implementation strategies are summarized in terms of the users' view of the KAPSE, the hardware criteria of the bare machine's ISA and hardware configuration, and the software criteria of program execution, I/O support, and the KAPSE database.
On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition
Authors: Galil Zvi
Published: October 2004

We give a sufficient condition when an on-line algorithm can be transformed into a real-time algorithm. We use this condition to construct real-time algorithms for string-matching and palindrome recognition problems by random access machines and by Turing machines.
Decomposition of a relation scheme into Boyce-Codd Normal Form
Authors: Tsou Don-Min , Fischer Patrick C.
Published: October 2004

Decomposition into Boyce-Codd Normal Form (BCNF) with a lossless join and preservation of dependencies is desired in the design of a relational database scheme. However, there may be no decomposition of a relation scheme into BCNF that is dependency preserving, and the known algorithms for lossless join decomposition into BCNF require exponential time and space. In this paper we give an efficient algorithm for lossless join decomposition and show that the problem of deciding whether a relation scheme has a dependency-preserving decomposition into BCNF is NP-hard. The algorithm and the proof assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.
A clique problem equivalent to graph isomorphism
Authors: Kozen Dexter
Published: October 2004

A class of graphs called
M-graphs
is defined. It is shown thati) the problem of determining whether a given M-graph of order n
2
has a clique of order n is logspace equivalent to graph isomorphism, andii) for any fixed but arbitrarily small e, the problem of determining whether a given M-graph of order n
2
has a clique of order (1-e)n is NP complete.
Pessimal algorithms and simplexity analysis
Authors: Broder Andrei , Stolfi Jorge
Published: October 2004

The twin disciplines of Pessimal Algorithm Design and Simplexity Analysis are introduced and illustrated by means of representative problems
A comparison of the Linux and Windows device driver architectures
Authors: Tsegaye Melekam , Foss Richard
Published: October 2004

In this paper the device driver architectures currently used by two of the most popular operating systems, Linux and Microsoft's Windows, are examined. Driver components required when implementing device drivers for each operating system are presented and compared. The process of implementing a driver, for each operating system, that performs I/O to a kernel buffer is also presented. The paper concludes by examining the device driver development environments and facilities provided to developers by each operating system.
Cryptanalysis of an ID-based password authentication scheme using smart cards and fingerprints
Authors: Scott Michael
Published: October 2004

In a paper recently published in the ACM Operating Systems Review, Kim, Lee and Yoo [1] describe two ID-based password authentication schemes for logging onto a remote network server using smart cards, passwords and fingerprints. Various claims are made regarding the security of the schemes, but no proof is offered. Here we show how a passive eavesdropper, without access to any smart card, password or fingerprint, and after passively eavesdropping only one legitimate log-on, can subsequently log-on to the server claiming any identity.
Experiences in developing a typical web/database application
Authors: Rosen J.-P.
Published: October 2004

This paper describes Gesem, an application developed internally by Adalog for managing the registration to its training sessions. The application features a Web interface that uses AWS, an interface to the MySQL DBMS (over ODBC), and a local interface that uses GTK. The project explored various solutions, and identified a number of design patterns that made the development of new functionalities very straightforward. The experience gained in this project can be reused for any development in a similar environment.
The case for Ada at the USAF academy
Authors: Sward Ricky E. , Carlisle Martin C. , Fagin Barry S. , Gibson David S.
Published: October 2004

This paper describes our experience with selecting Ada as the primary programming language for Computer Science and Computer Engineering majors at the USAF Academy. We have decided to teach Ada in the first three courses of these majors for the next few years. Our criteria for selecting Ada are based on features of the language (such as strong typing, lack of single-character errors, and case insensitivity), features of the compiler, (such as error messages and warnings), and features of the overall development experience (such as development environments, availability of textbooks, GUI development support, and industry acceptance). We compared Ada with Java, C++, and C#.
Quantum search algorithms
Authors: Ambainis A.
Published: October 2004

We review some of quantum algorithms for search problems: Grover's search algorithm, its generalization to amplitude amplification, the applications of amplitude amplification to various problems and the recent quantum algorithms based on quantum walks.
A pleasant stroll through the land of infinitely many creatures
Authors: Aguilera Marcos K.
Published: October 2004

Many distributed algorithms are designed for a system with a fixed set of
n
processes. However, some systems may dynamically change and expand over time,so that the number of processes may grow to infinity as time tends to infinity. This paper considers such systems, and gives algorithms that are new and simple (but not necessarily efficient) for common problems. The reason for simplicity is to better expose some of the algorithmic techniques for dealing with infinitely many processes. A brief summary of existing work in the subject is also provided.
Computational geometry column 45
Authors: O'Rourke Joseph
Published: October 2004

The algorithm of Edelsbrunner for surface reconstruction by "wrapping" a set of points in ℝ
3
is described.
Random drop congestion control
Authors: Mankin A.
Published: October 2004

Gateways in very high speed internets will need to have low processing requirements and rapid responses to congestion. This has prompted a study of the performance of the Random Drop algorithm for congestion recovery. It was measured in experiments involving local and long distance traffic using multiple gateways. For the most part, Random Drop did not improve the congestion recovery behavior of the gateways A surprising result was that its performance was worse in a topology with a single gateway bottleneck than in those with multiple bottlenecks. The experiments also showed that local traffic is affected by events at distant gateways.
Machnet: a simple access protocol for high speed or long haul communications
Authors: Jacquet P. , Muhlethaler P.
Published: October 2004

In high-speed networks, the ratio of the end-to-end propagation delay to the transmission delay may exceed one. Under these conditions, neither token-passing nor conventional CSMA/CD schemes can work efficiently. Previous work on access protocols for high-speed networks is generally based on round-robin service and can only operate on unidirectional media. This paper introduces new high-speed access protocols which can work on various LAN's topologies (star, tree, unidirectional media) and also on satellite networks. Based on a tree algorithm with deferred collision detection, this protocol includes mechanisms which reduce collisions and increase throughput. The maximum channel utilization can reach 100% whatever the propagation delay and the total connected population may be.
Mechanisms for integrated voice and data conferencing
Authors: Ziegler C. , Weiss G.
Published: October 2004

A distributed control mechanism for managing a multi-party, packet switched voice conference connection has been previously presented [Weis88, Weis90, Zieg89]. The principal concept introduced was to view a conference connection as a logical ring of participants. Alternate methods for implementing voice conferencing on both multicast-capable and non-multicast-capable networks were discussed and analyzed. The mechanisms were shown applicable to both intranet and internet conferences. This paper extends those results to allow for multi-party, integrated voice and data conferences. The paper introduces the technique developed and then presents experimental benchmark performance measures with respect to station and gateway workloads.
Link access blocking in very large multi-media networks
Authors: Labourdette Jean-François , Hart G.
Published: October 2004

This paper is concerned with performance models and approximations for very large, multi-media networks. Blocking is the traditional performance measure in circuit-switched networks, and will remain as such in multi-rate circuit-switched networks. It is also considered a likely performance measure candidate for resource management and dimensioning in broadband fast packet-switched networks, operated under virtual circuit mode.

To gain some insight into network-wide blocking phenomena, we study in this paper the basic building block of any network, a single link. Multi-media traffic calls with Poisson arrivals, arbitrarily distributed service times, and different bandwidth requirements (in number of circuits), are offered to a system (link) of finite capacity. A call is rejected when the sharing policy doesn't allow it to be accommodated by the system.

Under complete sharing policy, an aggregate state describing the number of occupied circuits is shown to exhibit a product form solution in steady state, when the capacity and traffic intensities become very large asymptotically. This structural property leads to the main result of this paper, an approximation which reduces the computation of the blocking probabilities for the different classes of traffic to the evaluation of a single Erlang formula and the determination of the root of a monotonous polynomial function.

We provide comparison curves of the exact blocking probabilities and the approximations for some examples with 3 classes of traffic.
Protocol conformance test generation using multiple UIO sequences with overlapping
Authors: Yang B. , Ural H.
Published: October 2004

This paper describes an optimization method for reducing the length of protocol conformance test sequences by overlapping test subsequences obtained using UIO sequences. It is shown that test sequences generated by this method are substantially shorter than those generated by other methods employing UIO sequences.
Protocol implementation on the Nectar Communication Processor
Authors: Cooper E. C. , Steenkiste P. A. , Sansom R. D. , Zill B. D.
Published: October 2004

We have built a high-speed local-area network called Nectar that uses programmable communication processors as host interfaces. In contrast to most protocol engines, our communication processors have a flexible runtime system that supports multiple transport protocols as well as application-specific activities. In particular, we have implemented the TCP/IP protocol suite and Nectar-specific communication protocols on the communication processor. The Nectar network currently has 25 hosts and has been in use for over a year.

The flexibility of our communication processor design does not compromise its performance. The latency of a remote procedure call between application tasks executing on two Nectar hosts is less than 500 μsec. The same tasks can obtain a throughput of 28 Mbit/sec using either TCP/IP or Nectar-specific transport protocols. This throughput is limited by the VME bus that connects a host and its communication processor. Application tasks executing on two communication processors can obtain 90 Mbit/sec of the possible 100 Mbit/sec physical bandwidth using Nectar-specific transport protocols.
Shortest path first with emergency exits
Authors: Wang Z. , Crowcroft J.
Published: October 2004

Under heavy and dynamic traffic, the SPF routing algorithm often suffers from wild oscillation and severe congestion, and results in degradation of the network performance. In this paper, we present a new routing algorithm (SPF-EE) which attempts to eliminate the problems associated with the SPF algorithm by providing alternate paths as emergency exits. With the SPF-EE algorithm, traffic is routed along the shortest-paths under normal condition. However, in the presence of congestion and resource failures, the traffic can be dispersed temporarily to alternate paths without route re-computation. Simulation experiments show that the SPF-EE algorithm achieves grater throughput, higher responsiveness, better congestion control and fault tolerance, and substantially improves the performance of routing in a dynamic environment.
Fast connection establishment in high speed networks
Authors: Cidon I. , Gopal I. , Segall A.
Published: October 2004

Protocols for establishing, maintaining and terminating connections in packet switched networks have been studied in the literature and numerous standards have been developed to address this problem. In this paper, we reexamine connection establishment in the context of a fast packet network with an integrated traffic load, explain why previously proposed solutions are inadequate and develop a protocol for connection establishment/takedown that is appropriate for such a network. The underlying model that we use is the recently developed PARIS network, though our ideas are sufficiently general to cover many other fast packet networking architectures.
Beware of BGP attacks
Authors: Nordström Ola , Dovrolis Constantinos
Published: October 2004

This note attempts to raise awareness within the network research community about the security of the interdomain routing infrastructure. We identify several attack objectives and mechanisms, assuming that one or more BGP routers have been compromised. Then, we review the existing and proposed countermeasures, showing that they are either generally ineffective (route filtering), or probably too heavyweight to deploy (S-BGP). We also review several recent proposals, and conclude by arguing that a significant research effort is urgently needed in the area of routing security.
Performance evaluation and comparison of Westwood+, New Reno, and Vegas TCP congestion control
Authors: Grieco Luigi A. , Mascolo Saverio
Published: October 2004

TCP congestion control has been designed to ensure Internet stability along with fair and efficient allocation of the network bandwidth. During the last decade, many congestion control algorithms have been proposed to improve the classic Tahoe/Reno TCP congestion control. This paper aims at evaluating and comparing three control algorithms, which are Westwood+, New Reno and Vegas TCP, using both Ns-2 simulations and live Internet measurements. Simulation scenarios are carefully designed in order to investigate goodput, fairness and friendliness provided by each of the algorithms. Results show that Westwood+ TCP is friendly towards New Reno TCP and improves fairness in bandwidth allocation whereas Vegas TCP is fair but it is not able to grab its bandwidth share when coexisting with Reno or in the presence of reverse traffic because of its RTT-based congestion detection mechanism. Finally results show that Westwood+ remarkably improves utilization of wireless links that are affected by losses not due to congestion.
A taxonomy of DDoS attack and DDoS defense mechanisms
Authors: Mirkovic Jelena , Reiher Peter
Published: October 2004

Distributed denial-of-service (DDoS) is a rapidly growing problem. The multitude and variety of both the attacks and the defense approaches is overwhelming. This paper presents two taxonomies for classifying attacks and defenses, and thus provides researchers with a better understanding of the problem and the current solution space. The attack classification criteria was selected to highlight commonalities and important features of attack strategies, that define challenges and dictate the design of countermeasures. The defense taxonomy classifies the body of existing DDoS defenses based on their design decisions; it then shows how these decisions dictate the advantages and deficiencies of proposed solutions.
Tree bitmap
Authors: Eatherton Will , Varghese George , Dittia Zubin
Published: October 2004

Even with the significant focus on IP address lookup in the published literature as well as focus on this market by commercial semiconductor vendors, there is still a challenge for router architects to find solutions that simultaneously meet 3 criteria: scaling in terms of lookup speeds as well as table sizes, the ability to perform high speed updates, and the ability to fit into the overall memory architecture of an Level 3 forwarding engine or packet processor with low systems cost overhead. In this paper, we describe a scheme that meets all three criteria. By contrast, published and commercial semiconductor solutions meet some but not all of these three criteria.For example, many approaches that provide dense tables have poor update times; others require large amounts of expensive high speed memory dedicated to this application. Many IP address lookup approaches do not take into account the flexibility of ASICs or the structure of modern high speed memory technologies such as RLDRAM[1] and FCRAM[2]. In this paper, we present a family of IP lookup schemes using a data structure that compactly encodes large prefix tables in order to address the criteria listed above. We also present a series of optimizations to the core algorithm that allows the memory access width of the algorithm to be reduced at the cost of memory references or allocated memory. Such flexibility in performance versus density is an important feature for the lookup engine of routers that may be deployed in different networks with varying requirements on address lookup length and table density (e.g. global IPv4 networks, global v6, VPN based v4 networks, MPLS, and IP tunneling encapsulation points).
End-to-end congestion control for TCP-friendly flows with variable packet size
Authors: Widmer Jörg , Boutremans Catherine , Boudec Jean-Yves Le
Published: October 2004

Current TCP-friendly congestion control mechanisms adjust the packet rate in order to adapt to network conditions and obtain a throughput not exceeding that of a TCP connection operating under the same conditions. In an environment where the bottleneck resource is packet processing, this is the correct behavior. However, if the bottleneck resource is bandwidth, and flows may use packets of different size, resource sharing depends on packet size and is no longer fair. For some applications, such as Internet telephony, it is more natural to adjust the packet size, while keeping the packet rate as constant as possible. In this paper we study the impact of variations in packet size on equation-based congestion control and propose methods to remove the resulting throughput bias. We investigate the design space in detail and propose a number of possible designs. We evaluate these designs through simulation and conclude with some concrete proposals. Our findings can be used to design a TCP-friendly congestion control mechanism for applications that adjust packet size rather than packet rate, or applications that are forced to use a small packet size.
Ada®for design
Authors: Hart Hal
Published: October 2004

DoD requirements to use DoD's new programming language Ada by the mid-1980's will create challenges to developers of military software in a) retraining large populations of experienced software practitioners to use Ada and b) achieving potential productivity and quality gains cited as Ada's life-cycle objectives. Many organizations are planning to use Ada as a software design language to achieve early experience and results in both the training and quality-improvement areas. A common approach in using Ada for software design is to use full-syntax Ada to represent design, although most Ada design methods omit low-level features of Ada from the set of constructs used in design; some advocates are using Ada as a vehicle to teach a single, favored methodology for software development. This paper offers an alternative approach, in which syntax is simplified, but the design language does, in a methodology-independent manner, include all the features which support important early design activities. The rationale for the simpler design language is that, with no net sacrifice of software engineering aids, it is a more palatable evolution from prevailing design practices in large software organizations.
On the type concept of Ada
Authors: Bach Iván
Published: October 2004

The different solutions for type-equivalence are investigated. The consequence of the generalized type concept and need for derivation mechanism. Inconsequences and dangers in the syntax and semantics of derivation. The drawbacks of the present private type declaration. Mixed operations do not fit into the philosophy of the language.
Interfacing with real environments from Ada programs
Authors: Fantechi A.
Published: October 2004

The features provided by the Ada language to interface objects belonging to non-Ada real environments are summarized and discussed. Some suggestions are given towards the proper use of these features in real environments.
On unlimited types and reliability of Ada programs
Authors: Llamosí Albert , Botella Pere , Orejas Fernando
Published: October 2004

The decision to mix two such different concepts as assignment and test for equality in the same feature of Ada language is submitted to criticism. Its consequences on reliability and modifiability of programs are considered and some methodological conclusions are drawn out.
Object-oriented design and ballistics software
Authors: Temte Mark
Published: October 2004

The object-oriented design methodology is applied to the problem of designing ballistics software. This problem is sufficiently large and complex that the methodology must be iterated at successively lower levels of abstraction. The manner in which the design unfolds is illustrated.
A proposal for standard basic functions in Ada
Authors: Kok J. , Symm G. T.
Published: October 2004

This paper contains a proposal for a standard basic mathematica l functions package for scientific computation in Ada. The package is transportable to machines with different floating-point types and its availability will enhance the portability of numerical software.