bluuebunny/crossref_metadata_2025 huggingface dataset:
A digital fountain approach to reliable distribution of bulk data
Authors: Byers John W. , Luby Michael , Mitzenmacher Michael , Rege Ashutosh
Published: October 2004

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal, fully scalable protocol for these applications that we call a digital fountain. A digital fountain allows any number of heterogeneous clients to acquire bulk data with optimal efficiency at times of their choosing. Moreover, no feedback channels are needed to ensure reliable delivery, even in the face of high loss rates.We develop a protocol that closely approximates a digital fountain using a new class of erasure codes that for large block sizes are orders of magnitude faster than standard erasure codes. We provide performance measurements that demonstrate the feasibility of our approach and discuss the design, implementation and performance of an experimental system.
Session directories and scalable Internet multicast address allocation
Authors: Handley Mark
Published: October 2004

A multicast session directory is a mechanism by which users can discover the existence of multicast sessions. In the Mbone, session announcements have also served as multicast address reservations - a dual purpose that is efficient, but which may cause some side-affects as session directories scale.In this paper we examine the scaling of multicast address allocation when it is performed by such a multicast session directory. Despite our best efforts to make such an approach scale, this analysis ultimately reveals significant scaling problems, and suggests a new approach to multicast address allocation in the Internet environment.
QoSMIC
Authors: Faloutsos Michalis , Banerjea Anindo , Pankaj Rajesh
Published: October 2004

In this paper, we present, QoSMIC, a multicast protocol for the Internet that supports QoS-sensitive routing, and minimizes the importance of
a priori configuration
decisions (such as
core
selection). The protocol is resource-efficient, robust, flexible, and scalable. In addition, our protocol is provably loop-free.Our protocol starts with a resources-saving tree (Shared Tree) and individual receivers switch to a QoS-competitive tree (Source-Based Tree) when necessary. In both trees, the new destination is able to choose the most promising among several paths. An innovation is that we use dynamic routing information without relying on a link state exchange protocol to provide it. Our protocol limits the effect of pre-configuration decisions drastically, by separating the management from the data transfer functions; administrative routers are not necessarily part of the tree. This separation increases the robustness, and flexibility of the protocol. Furthermore, QoSMIC is able to adapt dynamically to the conditions of the network.The QoSMIC protocol introduces several new ideas that make it more flexible than other protocols proposed to date. In fact, many of the other protocols, (such as YAM, PIMSM, BGMP, CBT) can be seen as special cases of QoSMIC. This paper presents the motivation behind, and the design of QoSMIC, and provides both analytical and experimental results to support our claims.
An active service framework and its application to real-time multimedia transcoding
Authors: Amir Elan , McCanne Steven , Katz Randy
Published: October 2004

Several recent proposals for an "active networks" architecture advocate the placement of user-defined computation within the network as a key mechanism to enable a wide range of new applications and protocols, including reliable multicast transports, mechanisms to foil denial of service attacks, intra-network real-time signal transcoding, and so forth. This laudable goal, however, creates a number of very difficult research problems, and although a number of pioneering research efforts in active networks have solved some of the preliminary small-scale problems, a large number of wide open problems remain. In this paper, we propose an alternative to active networks that addresses a restricted and more tractable subset of the active-networks design space. Our approach, which we (and others) call "active services", advocates the placement of user-defined computation within the network as with active networks, but unlike active networks preserves all of the routing and forwarding semantics of current Internet architecture by restricting the computation environment to the application layer. Because active services do not require changes to the Internet architecture, they can be deployed incrementally in today's Internet.We believe that many of the applications and protocols targeted by the active networks initiative can be solved with active services and, toward this end, we propose herein a specific architecture for an active service and develop one such service in detail --- the Media Gateway (MeGa) service --- that exploits this architecture. In defining our active service, we encountered six key problems --- service location, service control, service management, service attachment, service composition, and the definition of the service environment --- and have crafted solutions for these problems in the context of the MeGa service. To verify our design, we implemented and fielded MeGa on the UC Berkeley campus, where it has been used regularly for several months by real users who connect via ISDN to an "on-line classroom". Our initial experience indicates that our active services prototype provides a very flexible and programmable platform for intra-network computation that strikes a good balance between the flexibility of the active networks architecture and the practical constraints of incremental deployment in the current Internet.
Improving end-to-end performance of the Web using server volumes and proxy filters
Authors: Cohen Edith , Krishnamurthy Balachander , Rexford Jennifer
Published: October 2004

The rapid growth of the World Wide Web has caused serious performance degradation on the Internet. This paper offers an end-to-end approach to improving Web performance by collectively examining the Web components --- clients, proxies, servers, and the network. Our goal is to reduce user-perceived latency and the number of TCP connections, improve cache coherency and cache replacement, and enable prefetching of resources that are likely to be accessed in the near future. In our scheme, server response messages include
piggybacked
information customized to the requesting proxy. Our enhancement to the existing request-response protocol does not require per-proxy state at a server, and a very small amount of transient per-server state at the proxy, and can be implemented without changes to HTTP 1.1. The server groups related resources into
volumes
(based on access patterns and the file system's directory structure) and applies a proxy-generated
filter
(indicating the type of information of interest to the proxy) to tailor the piggyback information. We present efficient data structures for constructing server volumes and applying proxy filters, and a transparent way to perform volume maintenance and piggyback generation at a router along the path between the proxy and the server. We demonstrate the effectiveness of our end-to-end approach by evaluating various volume construction and filtering techniques across a collection of large client and server logs.
Scoped hybrid automatic repeat reQuest with forward error correction (SHARQFEC)
Authors: Kermode Roger G.
Published: October 2004

Reliable multicast protocols scale only as well as their ability to localize traffic. This is true for repair requests, repairs, and the session traffic that enables receivers to suppress extraneous requests and repairs. We propose a new reliable multicast traffic localization technique called Scoped Hybrid Automatic Repeat reQuest with Forward Error Correction (SHARQFEC). SHARQFEC operates in an end-to-end fashion and localizes traffic using a hierarchy of administratively scoped regions. Session traffic is further reduced through the use of a novel method for indirectly determining the distances between session members. For large sessions, this mechanism reduces the amount of session traffic by several orders of magnitude over non-scoped protocols such as Scalable Reliable Multicast (SRM). Forward Error Correction is selectively added to regions which are experiencing greater loss, thereby reducing the volume of repair traffic and recovery times. Receivers request additional repairs as necessary. Simulations show that SHARQFEC out performs both SRM and non-scoped hybrid Automatic Repeat reQuest / Forward Error Correction protocols. Assuming the widespread deployment of administrative scoping, SHARQFEC could conceivably provide scalable reliable delivery to tens of millions of receivers without huge increases in network bandwidth.
Automatic TCP buffer tuning
Authors: Semke Jeffrey , Mahdavi Jamshid , Mathis Matthew
Published: October 2004

With the growth of high performance networking, a single host may have simultaneous connections that vary in bandwidth by as many as six orders of magnitude. We identify requirements for an automatically-tuning TCP to achieve maximum throughput across all connections simultaneously within the resource limits of the sender. Our auto-tuning TCP implementation makes use of several existing technologies and adds dynamically adjusting socket buffers to achieve maximum transfer rates on each connection without manual configuration.Our implementation involved slight modifications to a BSD-based socket interface and TCP stack. With these modifications, we achieved drastic improvements in performance over large bandwidth delay paths compared to the default system configuration, and significant reductions in memory usage compared to hand-tuned connections, allowing servers to support at least twice as many simultaneous connections.
Solving incomplete and incorrect information problems using conditional planning, execution monitoring, and situated planning agents
Authors: Lupton William , Stojkovic Vojislav
Published: October 2004

The world is not a neat and well-ordered place. Incomplete and incorrect information is receiving each moment. Incompleteness arises because the world is inaccessible. Incorrectness arises because the world does not match its model. Complete and correct information is crucial in many situations where the success or failure of an operation depends of the quality of information. When the unexpected or unknown occurs, conditional planning, execution monitoring, or situated planning can help system to recover and get back on the right track. This paper shows how incomplete and incorrect information problems can be solved using conditional planning, execution monitoring and situated planning agents - intelligent knowledge-based software agents.
LPL++
Authors: Toroslu Ismail H.
Published: October 2004

In this paper, an object logic programming language is proposed that captures all of the basic object-oriented concepts in standard logic programming environment. This paper combines and extends two previously proposed models, namely Conery's technique (1988) which uses first-order logic to model objects including all of the basic object-oriented concepts except inheritance, and the LOGIN language of Ait-Kaci and Nasr (1986) which embeds inheritance into unification using typed logic.In this paper, Conery's proposal is extended by redefining the representation of the objects in a more formal way and by adding inheritance through an extended unification similar to the one proposed by Ait-Kaci and Nasr (1986). We have also changed the type concept of Ait-Kaci and Nasr (1986) by adding types directly to the first-order terms rather than using terms as types. The extended logic language, LPL++, has all the basic object-oriented concepts, namely objects, instances, classes, methods, inheritance, with the availability of update operations on objects in methods. A prototype interpreter also has been developed for the language LPL++.
Computational geometry
Authors: Agarwal Pankaj K. , O'Rourke Joseph
Published: October 2004

Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.
Fixing a problem in the Helsinki protocol
Authors: Mitchell Chris J. , Yeun Chan Yeob
Published: October 2004

We consider a recently described attack on a key establishment protocol contained in a draft international standard. Based on an observation as to why the attack is possible, we propose a simple modification to the protocol which avoids the attack.
Controlling cgi programs
Authors: Wagner Bernhard
Published: October 2004

In the beginning the World Wide Web contained mostly hypertext documents, but since then, a growing number of applications have required cgi programs. Therefore, a web designer should be able to provide a cgi program for web use as easily as HTML documents are provided. Cgi programs, however, are executed by the web server process, with all its permissions and capabilities enabled. To avoid this most undesirable situation we propose a program,
chuid,
which changes the webmaster's userid to that of the cgi program provider before that cgi program is executed. In order to use the
chuid
program, the URL's of all cgi programs have to be slightly changed.
Chuid
may be used in all Unix-based web servers. The source code of
chuid
written in C is available via the World Wide Web.
Introducing empirical investigation in undergraduate operating systems
Authors: Robbins Steven
Published: October 2004

The undergraduate operating systems course can provide students with a valuable introduction to empirical testing and experimentation. This paper announces the availability of a process scheduling simulator designed to develop student empirical skills while they are learning part of the standard operating systems curriculum. The simulator is written in Java and available for direct experimentation via the World Wide Web. By accessing the remote URL through an appletviewer, students can permanently save input test data and simulator results generated in HTML format. Students are asked to test specified hypotheses about process scheduling and to develop their own hypotheses about the influence of different parameters on behavior. In order to devise experiments that make sense, students must understand how factors such as burst time and variability influence behavior. Interested faculty are invited to try the simulator and support materials in their operating systems classes.
How to find the best approximation results
Authors: Crescenzi Pierluigi , Kann Viggo
Published: October 2004

A compendium of NP optimization problems, containing the best approximation results known for each problem, is available on the world wide web at http://www.nada.kth.se/~viggo/problemlist/In this paper we describe the compendium, and specify how the compendium is consultable as well as modifiable on the web. We also give statistics for the use of the compendium.
Uniform characterizations of complexity classes
Authors: Vollmer Heribert
Published: October 2004

In the past few years, generalized operators (a. k. a. leaf languages) in the context of polynomial-time machines, and gates computing arbitrary groupoidal functions in the context of Boolean circuits, have raised much interest. We survey results from both areas, point out connections between them, and present relationships to a generalized quantifier concept from finite model theory.
Evaluation of Java thread performance on two different multithreaded kernels
Authors: Gu Yan , Lee B. S. , Cai Wentong
Published: October 2004

Modern programming languages and operating systems encourage the use of threads to exploit concurrency and simplify program structure. An integral and important part of the Java language is its multithreading capability. Despite the portability of Java threads across almost all platforms, the performance of Java threads varies according to the multithreading support of the underlying operating system and the way Java Virtual Machine maps Java threads to the native system threads. In this paper, a well-known compute-intensive benchmark, the EP benchmark, was used to examine various performance issues involved in the execution of threads on two different multithreaded platforms: Windows NT and Solaris. Experiments were carried out to investigate thread creation and computation behavior under different system loads, and to explore execution features under certain extreme situations such as the concurrent execution of very large number of Java threads. Some of the experimental results obtained from threads were compared with a similar implementation using processes. These results show that the performance of Java threads differs depending on the various mechanisms used to map Java threads to native system threads, as well as on the scheduling policies for these native threads. Thus, this paper provides important insights into the behavior and performance of Java threads on these two platforms, and highlights the pitfalls that may be encountered when developing multithreaded Java programs.
Ada 95 conformity assessment - Phil Brashear
Authors: Brukardt Randall , Deller Steven , Tokar Joyce L.
Published: October 2004

On September 30, 1998, the Ada Resource Association (ARA) accepted responsibility to continue the activities of the Ada Joint Program Office (AIPO), as part of transitioning Ada support from government to private industry. The ARA is promoting Ada in a variety of areas. One primary responsibility is the continuation of the Ada compiler validation process.The ARA considered it necessary to distance the vendors that comprise the ARA from the validation process itself. Consequently, the ARA is supporting the activities of the Ada Working Group (JTC1/SC22/WG9) within the International Organization for Standards (ISO) to standardize the existing validation processes. To become a standard, the Ada validation terminology must be changed to match ISO terminology (for example, validation is replaced with conformance assessment). The actual validation procedures supported by the ARA are largely unchanged from those under the AJPO, with a few minor changes to reduce bureaucracy, improve reproducibility, and more easily integrate language maintenance. A number of independent organizations will work together to perform and oversee validations.The revised procedures are in use while waiting for the actual ISO approval. To date, seven conformity assessments by two vendors have been performed using the new procedures and organization.
An empirical validation of a contingency model for information require-ments determination
Authors: El Louadi Mohammed , Galletta Dennis F. , Sampler Jeffrey L.
Published: October 2004

A contingency model for system development was subjected to several conceptual and operational adjustments and empirical tests. According to the model, there should be a degree of fit between development project uncertainty and the strategy for determining information requirements, ranging from accepting initial requirements statements to experimenting with prototypes to discover requirements. This study introduced a new IRD strategy construct that focused on the extent of interaction between users and developers. The study also differentiated between perceptual and evidential outcomes, between process and product outcomes, and between users' and developers' points of view. The hypotheses predicted that the degree of fit between project uncertainty and the IRD strategy would account for perceptual and evidential project outcomes from both the user's and developer's points of view. Results indicated that only by relying on the new extent of interaction construct, was support found. From the developers' standpoint, the degree of fit appeared to be related to perceptual assessments of the process and product. From the user's standpoint, the degree of fit was only related to perceptual assessments of the process. There was no support for the hypothesized impact of fit on evidential outcomes.
SimDS
Authors: Chaturvedi Alok R. , Gupta Samir , Bandyopadhyay Subhajyoti
Published: October 2004

Design of a distributed transaction processing system is a complex process. The paper describes the design and implementation of a general purpose scalable simulation environment (SimDS) for designing and evaluating the performance of distributed transaction processing systems. SimDS is a distributed simulation system where each data server is implemented as a separate process that communicates with each other through user datagram protocol. The paper describes the features of SimDS including various design policies that can be modeled by the system. It also discusses different design issues that one needs to consider in the implementation of a distributed simulation environment. The paper concludes with some test examples where SimDS was used to simulate different configurations of a real-time transaction processing system.
Present and future directions in data warehousing
Authors: Gray Paul , Watson Hugh J.
Published: October 2004

Many large organizations have developed data warehouses to support decision making. The data in a warehouse are subject oriented, integrated, time variant, and nonvolatile. A data warehouse contains five types of data: current detail data, older detail data, lightly summarized data, highly summarized data, and metadata. The architecture of a data warehouse includes a backend process (the extraction of data from source systems), the warehouse, and the front-end use (the accessing of data from the warehouse). A data mart is a smaller version of a data warehouse that supports the narrower set of requirements of a single business unit. Data marts should be developed in an integrated manner in order to avoid repeating the "silos of information" problem.An operational data store is a database for transaction processing systems that uses the data warehouse approach to provide clean data. Data warehousing is constantly changing, with the associated opportunities for practice and research, such as the potential for knowledge management using the warehouse.
The impact of multicast layering on network fairness
Authors: Rubenstein Dan , Kurose Jim , Towsley Don
Published: October 2004

Many definitions of fairness for multicast networks assume that sessions are single-rate, requiring that each multicast session transmits data to all of its receivers at the same rate. These definitions do not account for multi-rate approaches, such as layering, that permit receiving rates within a session to be chosen independently. We identify four desirable fairness properties for multicast networks, derived from properties that hold within the max-min fair allocations of unicast networks. We extend the definition of multicast max-min fairness to networks that contain multi-rate sessions, and show that all four fairness properties hold in a multi-rate max-min fair allocation, but need not hold in a single-rate max-min fair allocation. We then show that multi-rate max-min fair rate allocations can be achieved via intra-session coordinated joins and leaves of multicast groups. However, in the absence of coordination, the resulting max-min fair rate allocation uses link bandwidth inefficiently, and does not exhibit some of the desirable fairness properties. We evaluate this inefficiency for several layered multi-rate congestion control schemes, and find that, in a protocol where the sender coordinates joins, this inefficiency has minimal impact on desirable fairness properties. Our results indicate that sender-coordinated layered protocols show promise for achieving desirable fairness properties for allocations in large-scale multicast networks.
Scaling of multicast trees
Authors: Phillips Graham , Shenker Scott , Tangmunarunkit Hongsuda
Published: October 2004

One of the many benefits of multicast, when compared to traditional unicast, is that multicast reduces the overall network load. While the importance of multicast is beyond dispute, there have been surprisingly few attempts to quantify multicast's reduction in overall network load. The only substantial and quantitative effort we are aware of is that of Chuang and Sirbu [3]. They calculate the number of links
L
in a multicast delivery tree connecting a random source to
m
random and distinct network sites; extensive simulations over a range of networks suggest that
L(m) ∝ m
0.8
. In this paper we examine the function
L(m)
in more detail and derive the asymptotic form for
L(m)
in k-ary trees. These results suggest one possible explanation for the universality of the Chuang-Sirbu scaling behavior.
BPF+
Authors: Begel Andrew , McCanne Steven , Graham Susan L.
Published: October 2004

A
packet filter
is a programmable selection criterion for classifying or selecting packets from a packet stream in a generic, reusable fashion. Previous work on packet filters falls roughly into two categories, namely those efforts that investigate flexible and extensible filter abstractions but sacrifice performance, and those that focus on low-level, optimized filtering representations but sacrifice flexibility. Applications like network monitoring and intrusion detection, however, require both high-level expressiveness and raw performance. In this paper, we propose a fully general packet filter framework that affords both a high degree of flexibility
and
good performance. In our framework, a packet filter is expressed in a high-level language that is compiled into a highly efficient native implementation. The optimization phase of the compiler uses a flowgraph set relation called
edge dominators
and the novel application of an optimization technique that we call "redundant predicate elimination," in which we interleave partial redundancy elimination, predicate assertion propagation, and flowgraph edge elimination to carry out the filter predicate optimization. Our resulting packet-filtering framework, which we call BPF+, derives from the BSD packet filter (BPF), and includes a filter program translator, a byte code optimizer, a byte code safety verifier to allow code to migrate across protection boundaries, and a just-in-time assembler to convert byte codes to efficient native code. Despite the high degree of flexibility afforded by our generalized framework, our performance measurements show that our system achieves performance comparable to state-of-the-art packet filter architectures and better than hand-coded filters written in C.
Packet classification using tuple space search
Authors: Srinivasan V. , Suri S. , Varghese G.
Published: October 2004

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and QoS routing. Packet classification requires matching each packet against a database of filters (or rules), and forwarding the packet according to the highest priority filter. Existing filter schemes with fast lookup time do not scale to large filter databases. Other more scalable schemes work for 2-dimensional filters, but their lookup times degrade quickly with each additional dimension. While there exist good hardware solutions, our new schemes are geared towards software implementation.We introduce a generic packet classification algorithm, called
Tuple Space Search (TSS)
. Because real databases typically use only a small number of distinct field lengths, by mapping filters to tuples even a simple linear search of the tuple space can provide significant speedup over naive linear search over the filters. Each tuple is maintained as a hash table that can be searched in one memory access. We then introduce techniques for further refining the search of the tuple space, and demonstrate their effectiveness on some firewall databases. For example, a real database of 278 filters had a tuple space of 41 which our algorithm prunes to 11 tuples. Even as we increased the filter database size from 1K to 100K (using a random two-dimensional filter generation model), the number of tuples grew from 53 to only 186, and the pruned tuples only grew from 1 to 4. Our Pruned Tuple Space search is also the only scheme known to us that allows
fast updates
and fast search times. We also show a lower bound on the general tuple space search problem, and describe an optimal algorithm, called
Rectangle Search
, for two-dimensional filters.
Quality adaptation for congestion controlled video playback over the Internet
Authors: Rejaie Reza , Handley Mark , Estrin Deborah
Published: October 2004

Streaming audio and video applications are becoming increasingly popular on the Internet, and the lack of effective congestion control in such applications is now a cause for significant concern. The problem is one of adapting the compression without requiring video-servers to re-encode the data, and fitting the resulting stream into the rapidly varying available bandwidth. At the same time, rapid fluctuations in quality will be disturbing to the users and should be avoided.In this paper we present a mechanism for using layered video in the context of unicast congestion control. This quality adaptation mechanism adds and drops layers of the video stream to perform long-term coarse-grain adaptation, while using a TCP-friendly congestion control mechanism to react to congestion on very short timescales. The mismatches between the two timescales are absorbed using buffering at the receiver. We present an efficient-scheme for the distribution of buffering among the active layers. Our scheme allows the server to trade short-term improvement for long-term smoothing of quality. We discuss the issues involved in implementing and tuning such a mechanism, and present our simulation results.
Load-sensitive routing of long-lived IP flows
Authors: Shaikh Anees , Rexford Jennifer , Shin Kang G.
Published: October 2004

Internet service providers face a daunting challenge in provisioning network resources, due to the rapid growth of the Internet and wide fluctuations in the underlying traffic patterns. The ability of dynamic routing to circumvent congested links and improve application performance makes it a valuable traffic engineering tool. However, deployment of load-sensitive routing is hampered by the overheads imposed by link-state update propagation, path selection, and signaling. Under reasonable protocol and computational overheads, traditional approaches to load-sensitive routing of IP traffic are ineffective, and can introduce significant route flapping, since paths are selected based on out-of-date link-state information. Although stability is improved by performing load-sensitive routing at the flow level, flapping still occurs, because most IP flows have a short duration relative to the desired frequency of link-state updates. To address the efficiency and stability challenges of load-sensitive routing, we introduce a new hybrid approach that performs dynamic routing of long-lived flows, while forwarding short-lived flows on static preprovisioned paths. By relating the detection of long-lived flows to the timescale of link-state update messages in the routing protocol, route stability is considerably improved. Through simulation experiments using a one-week ISP packet trace, we show that our hybrid approach significantly outperforms traditional static and dynamic routing schemes, by reacting to fluctuations in network load without introducing route flapping.
A simple approximation to minimum-delay routing
Authors: Vutukury Srinivas , Garcia-Luna-Aceves J. J.
Published: October 2004

The conventional approach to routing in computer networks consists of using a heuristic to compute a single shortest path from a source to a destination. Single-path routing is very responsive to topological and link-cost changes; however, except under light traffic loads, the delays obtained with this type of routing are far from optimal. Furthermore, if link costs are associated with delays, single-path routing exhibits oscillatory behavior and becomes unstable as traffic loads increase. On the other hand, minimum-delay routing approaches can minimize delays only when traffic is stationary or very slowly changing.We present a "near-optimal" routing framework that offers delays comparable to those of optimal routing and that is as flexible and responsive as single-path routing protocols proposed to date. First, an approximation to the Gallager's minimum-delay routing problem is derived, and then algorithms that implement the approximation scheme are presented and verified. We introduce the first routing algorithm based on link-state information that provides multiple paths of unequal cost to each destination that are loop-free at every instant. We show through simulations that the delays obtained in our framework are comparable to those obtained using the Gallager's minimum-delay routing. Also, we show that our framework renders far smaller delays and makes better use of resources than traditional single-path routing.
On power-law relationships of the Internet topology
Authors: Faloutsos Michalis , Faloutsos Petros , Faloutsos Christos
Published: October 2004

Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher.Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.
Dynamics of IP traffic
Authors: Feldmann Anja , Gilbert Anna C. , Huang Polly , Willinger Walter
Published: October 2004

Using the
ns-2
-simulator to experiment with different aspects of user- or session-behaviors and network configurations and focusing on the qualitative aspects of a wavelet-based scaling analysis, we present a systematic investigation into how and why variability and feedback-control contribute to the intriguing scaling properties observed in actual Internet traces (as our benchmark data, we use measured Internet traffic from an ISP). We illustrate how variability of both user aspects and network environments (i) causes self-similar scaling behavior over large time scales, (ii) determines a more or less pronounced change in scaling behavior around a specific time scale, and (iii) sets the stage for the emergence of surprisingly rich scaling dynamics over small time scales; i.e., multifractal scaling. Moreover, our scaling analyses indicate whether or not open-loop controls such as UDP or closed-loop controls such as TCP impact the local or small-scale behavior of the traffic and how they contribute to the observed multifractal nature of measured Internet traffic. In fact, our findings suggest an initial physical explanation for why measured Internet traffic over small time scales is highly complex and suggest novel ways for detecting and identifying, for example, performance bottlenecks.This paper focuses on the qualitative aspects of a wavelet-based scaling analysis rather than on the quantitative use for which it was originally designed. We demonstrate how the presented techniques can be used for analyzing a wide range of different kinds of network-related measurements in ways that were not previously feasible. We show that scaling analysis has the ability to extract relevant information about the time-scale dynamics of Internet traffic, thereby, we hope, making these techniques available to a larger segment of the networking research community.
An internodal protocol for packet switched data networks
Authors: Drynan D. , Baker D.
Published: October 2004

This paper describes a proprietary data transmission protocol developed for internodal trunks on the Northern Telecom SL-10™ Packet Switched Data Network. The protocol has been implemented and tested in the new Universal Trunk Processor. Two separate market forces dictated the protocol requirements. The first was a demand for high speed trunks in the T1 (1.54 Mb/s) and above range to cost effectively serve future networks. The second market force was the emergence of satellite data technology with its attendant high bandwidth and lower cost. A protocol with a large sequence number range and the ability to selectively retransmit more than one packet in error without impacting the flow of correctly received packets was required. None of the standard data protocols met these requirements.
A new technique for generating protocol test
Authors: Sabnani Krishan , Dahbura Anton
Published: October 2004

A novel procedure presented here generates test sequences for checking the conformity of protocol implementations to their specifications. The test sequences generated by this procedure only detect the presence of many faults, but they do not locate the faults. It can always detect the problem in an implementation with a single fault.

A protocol entity is specified as a finite state machine (FSM). It typically has two interfaces: an interface with the user and with the lower-layer protocol. The inputs from both interfaces are merged into a single set I and the outputs from both interfaces are merged into a single set O. The implementation is assumed to be a black box.

The key idea in this procedure is to tour all states and state transitions and to check a unique signature for each state, called the Unique Input/Output (UIO) sequence. A UIO sequence for a state is an I/O behavior that is not exhibited by any other state.
Domain names (panel session, abstract only)
Authors: Peterson Larry L.
Published: October 2004

The DARPA domain name project raises several interesting questions about the underlying assumptions and issues involved in providing a hierarchical naming scheme in an environment the size of the Internet. For example, the project was motivated by the growth of the Internet. However, because the proliferation of hosts took place within the sites belonging to the Internet (due in part to an increase in the number of workstations and other small machines), and not necessarily in the number of sites, a less general solution that maintained a centralized and fully distributed
site
table, with each site running a name server for its hosts, would have been sufficient.

In addition, the distributed implementation of the name to address database uncovered several fundamental naming and addressing issues that had been ignore by the original centralized approach. For example, name servers and resolvers must be able to select a reasonable Internet address for hosts connected to the Internet at multiple points. The decentralized solution also raises questions about authority over host names.
Datapac (panel session, abstract only)
Authors: Dobson A.
Published: October 2004

Packet Switched Networks are well accepted and provide cost-effective data communications for a wide range of applications. This paper will examine the growth of packet switching by profiling Telecom Canada's Packet Switched Network, Datapac. It will focus on the following:

the emergence of applications by new users of data communications,

development of new applications by existing users,

migration to packet switching networks from dedicated leased line networks,

the development and introduction of new service features to continue the phenomenal growth rates achieved in earlier years.
Technology for managing large packet switching networks (panel session, abstract only)
Authors: Jeannes D.
Published: October 2004

The evolution of packet switching network technology over the past ten years has been strongly influenced by the dramatic growth of these networks. The ability to control and manage large networks has required many innovations and has been most successful where the growing network itself has provided the mechanisms needed for network management.

This discussion will cover the increasing use of decentralization and parallel operation of functions required to monitor the network, to remotely test and maintain subscriber facilities, to collect billing and statistical data, and to distribute and install new software. Specific problems which require special attention in large network management will be covered; these include time synchronization, routing optimization, and network security.

The SL-10 packet switching system from Northern Telecom is referenced through this discussion as an example of a system which has built on the facilities and technology of the network switching equipment to provide the management function. Since all of the attributes of capacity, availability, reliable communication, configuration flexibility, and security are the same for both packet switching subscribers and network management, using a common base provides real advantages.

The discussion will show how the exclusive use of network terminal interfaces, virtual circuits, and X.25 host interfaces for all management data transfer functions provides the required function with virtually unlimited growth potential. Support of both packet switching and management functions on the same base of processor, storage devices, and software, further extends the benefits of commonality.
Window selection in flow controlled networks
Authors: Geria Mario , Chan H. W.
Published: October 2004

The end-to-end window scheme is a popular mechanism for flow and congestion control in packet switched networks. The window scheme may be implemented in the transport layer protocol (like in TCP), or in the source-to-destination protocol(like in ARPANET), or in the network layer protocol (like X.25). In many implementations, the window size is chosen at connection set up time.

In this paper, we provide guidelines for window selection. Specifically, we show that if the network becomes overloaded, that is, the offered load exceeds network capacity, then the selection of user windows has a critical impact on individual user throughputs. Thus, user windows should be chosen judiciously, so as to satisfy a well defined “fairness” criterion.

We formulate the optimal window assignment as a mathematical programming problem, and show that the exact solution is computationally impractical because of the combinatorial nature of the problem and the complexity of the underlying multiple chain, closed network of queue model. We then develop a heuristic approach which is computationally very efficient and provides nearly optimal solutions. Numerical results are provided to illustrate and validate the method.
Integrating satellite links into a land-based packet network
Authors: Chu M. , Drynan D. , Benning L. R.
Published: October 2004

It is becoming apparent that communication via satellite links will play an increasing role in data networks. The challenge is to integrate this new communications option into an existing land-based network such that users can realize its full benefits. This paper discusses that solutions for the SL-10
*
Packet Network. The design criteria and performance objectives are also examined.
An integrated test center for SL-10 packet networks
Authors: Hornbeek M. W. A.
Published: October 2004

The sheer scale and complexity of large data networks makes testing them a daunting task. System commissioning, release acceptance, network troubleshooting, performance testing, host conformance testing, and certification are all operational activities that involve testing. Packet switching systems typically provide built-in features to help with hardware level test operations such as modem loopback commands, system failure alarms and system selftests. However, testing system and protocol level functions still required the use of separate tool boxes. Typical data product test tools are designed to test single data lines, not multiline distributed networks (1,2,3). Considering all of the above, the SL-10 test tools group set out to develop network tools (4). Tools have been implemented which are well-integrated into the SL-10 product. The same tools can be used alone, independent of the SL-10 network. This tool set makes the job of network testing more manageable for developer, manufacturer and network operator alike. Terminals and host computers, as well as total networks, can now be tested for conformance and performance automatically, instead of manually. As a result, major productivity improvements and quality gains have been observed since the tools were introduced.

The tool set consists of four tools: an interactive protocol tester (IPT) for checking protocol implementations against specifications; the network load test system (NLTS) which generates simulated traffic and measures the network's performance; the network process monitor (NPM) which examines operating software at the module level; and the network test system (NTS) Driver which is an automatic or interactive test sequencer for coordinating and controlling distributed network testing. Each tool can be operated individually using a standard data terminal. The IPT, NLTS and NPM tools run on SL-10 RAPID
*
network processors and can be operated remotely via the network or the NTS Driver. Using these tools in combination, a fully integrated and automatic operational test center can be realized, and the need for separate tool boxes can be eliminated.

The design and capabilities of each of these tools are described. This paper describes how these tools meet the special needs of network test operations.
Design of an integrated services
packet
network
Authors: Turner Jonathan S.
Published: October 2004

The Integrated Services Digital Network (ISDN) has been proposed as a way of providing integrated voice and data communications services on a universal or near-universal basis. In this paper, I argue that the evolutionary approach inherent in current ISDN proposals is unlikely to provide an effective long term solution and advocate a more revolutionary approach, based on the use of advanced packet switching technology. The bulk of this paper is devoted to a detailed description of an Integrated Services Pocket Network (ISPN), which I offer as an alternative to current ISDN proposals.
ALPHA transport
Authors: Enshayan Bahram
Published: October 2004

The control of the resources of a packet switching network is a very difficult problem to solve.
1
Past attempts to solve this problem have been handicapped primarily by lack of an adequate means to quantify the user demands and then assign distributed resources to the demands in a globally coherent way.

This paper presents a new approach to control the resources of packet switching networks. The key to this control is a new network transport scheme called alpha transport. Alpha transport combines the TDM circuit switching concept and packet switching technology. It is easy to implement and particularly cost effective to carry the subnet traffic of meshed packet switching networks. Alpha transport is robust, enables high utilization of the subnet bandwidth, reduces the subnet delay, and provides fairness.
Interfacing Ada 95 to Microsoft COM and DCOM technologies
Authors: Botton David
Published: October 2004

COM, the Component Object Model, and DCOM, Distributed COM, were introduced as the underlying technologies of Microsoft's second version of OLE, but have since proven their utility as powerful model for distributed systems. This paper intends to introduce COM and DCOM to the Ada community and demonstrate how to create and use objects that conform to these models.
CORBA and CORBA services for DSA
Authors: Pautet Laurent , Quinot Thomas , Tardieu Samuel
Published: October 2004

Comparing CORBA and the Ada 95 Distributed Systems Annex shows that an advantage of CORBA is its Common Object Services, providing standard, frequently-used components for distributed application development. This paper presents our implementation of similar services for the DSA. We also introduce new developments of our team that aim at providing close interaction between CORBA and Ada applications. Part of the work presented here was accomplished by the AdaBroker team: Fabien Azavant, Emmanuel Chavane, Jean-Marie Cottin, Tristan Gingold, Laurent Kübler, Vincent Niebel, and Sébastien Ponce.