bluuebunny/crossref_metadata_2025 huggingface dataset:
Accelerating multi-media processing by implementing memoing in multiplication and division units
Authors: Citron Daniel , Feitelson Dror , Rudolph Larry
Published: October 2004

This paper proposes a technique that enables performing multi-cycle (multiplication, division, square-root …) computations in a single cycle. The technique is based on the notion of memoing: saving the input and output of previous calculations and using the output if the input is encountered again. This technique is especially suitable for Multi-Media (MM) processing. In MM applications the local entropy of the data tends to be low which results in repeated operations on the same datum.The inputs and outputs of assembly level operations are stored in cache-like lookup tables and accessed in parallel to the conventional computation. A successful lookup gives the result of a multi-cycle computation in a single cycle, and a failed lookup doesn't necessitate a penalty in computation time.Results of simulations have shown that on the average, for a modestly sized memo-table, about 40% of the floating point multiplications and 50% of the floating point divisions, in Multi-Media applications, can be avoided by using the values within the memo-table, leading to an average computational speedup of more than 20%.
An empirical study of decentralized ILP execution models
Authors: Ranganathan Narayan , Franklin Manoj
Published: October 2004

Recent fascination for dynamic scheduling as a means for exploiting instruction-level parallelism has introduced significant interest in the scalability aspects of dynamic scheduling hardware. In order to overcome the scalability problems of centralized hardware schedulers, many decentralized execution models are being proposed and investigated recently. The crux of all these models is to split the instruction window across multiple processing elements (PEs) that do independent, scheduling of instructions. The decentralized execution models proposed so far can be grouped under 3 categories, based on the criterion used for assigning an instruction to a particular PE. They are: (i) execution unit dependence based decentralization (EDD), (ii) control dependence based decentralization (CDD), and (iii) data dependence based decentralization (DDD). This paper investigates the performance aspects of these three decentralization approaches. Using a suite of important benchmarks and realistic system parameters, we examine performance differences resulting from the type of partitioning as well as from specific implementation issues such as the type of PE interconnect.We found that with a ring-type PE interconnect, the DDD approach performs the best when the number of PEs is moderate, and that the CDD approach performs best when the number of PEs is large. The currently used approach---EDD---does not perform well for any configuration. With a realistic crossbar, performance does not increase with the number of PEs for any of the partitioning approaches. The results give insight into the best way to use the transistor budget available for implementing the instruction window.
Notes on the design of Euclid
Authors: Popek G. J. , Horning J. J. , Lampson B. W. , Mitchell J. G. , London R. L.
Published: October 2004

Euclid is a language for writing system programs that are to be verified. We believe that verification and reliability are closely related, because if it is hard to reason about programs using a language feature, it will be difficult to write programs that use it properly. This paper discusses a number of issues in the design of Euclid, including such topics as the scope of names, aliasing, modules, type-checking, and the confinement of machine dependencies; it gives some of the reasons for our expectation that programming in Euclid will be more reliable (and will produce more reliable programs) than programming in Pascal, on which Euclid is based.
Efficient implementation and optimization of run-time checking in PASCAL
Authors: Fischer Charles N. , LeBlanc Richard J.
Published: October 2004

Complete run-time checking of programs is an essential tool for the development of reliable software. A number of features of the programming language PASCAL (arrays, subranges, pointers, record variants (discriminated type unions), formal procedures, etc.) can require some checking at run-time as well as during compilation. The problem of efficiently implementing such checking is considered. Language modifications to simplify such checking are suggested. The possibility of optimizing such checking is discussed.
Towards the ideal programming language
Authors: Herriot Robert G.
Published: October 2004

A programming language with good features and notation can help the programmer represent his abstractions in the programming language, and can also help someone else understand the original abstraction. There have been numerous proposals for better features. In this paper we propose several new ideas to improve the notation. First we suggest that class instances be named with a sequence of identifiers consisting of the class name preceded by modifiers. Then we propose that prepositions be placed before procedure parameters to suggest their role. Finally, we suggest that applicative and imperative operations can be separated semantically, and then recombined syntactically through the use of the “which” and passive operators.
Static determination of dynamic properties of generalized type unions
Authors: Cousot Patrick , Cousot Radhia
Published: October 2004

The classical programming languages such as PASCAL or ALGOL 68 do not provide full data type security. Run-time errors are not precluded on basic operations. Type safety necessitates a refinement of the data type notion which allows subtypes. The compiler must also be able to ensure that basic operations are applicable. This verification consists in determining a local subtype of globally declared variables or constants. This may be achieved by improved compiler capabilities to analyze the program properties or by language constructs which permit the expression of these properties. Both approaches are discussed and illustrated by the problems of access to records via pointers, access to variants of record structures, determination of disjoint collections of linked records, and determination of integer subrange. Both approaches are complementary and a balance must be found between what must be specified by the programmer and what must be discovered by the compiler.
Software reliability
Authors: Melliar-Smith P. M. , Randell B.
Published: October 2004

The paper discusses the basic concepts underlying the issue of software reliability, and argues that programmed exception handling is inappropriate for dealing with suspected software errors. Instead it is shown, using an example program, how exception handling can be combined with the recovery block structure. The result is to improve the effectiveness with which problems due to anticipated faulty input data, hardware components, etc., are dealt with, while continuing to provide means for recovering from unanticipated faults, including ones due to residual software design errors.
Exception handling in PL/I
Authors: MacLaren M. Donald
Published: October 2004

The PL/I language's facilities for handling exceptional conditions are analyzed. The description is based on the new PL/I standard. Special attention is given to fine points which are not well known. The analysis is generally critical. It emphasizes problems in regards to implementation and structured programming. A few suggestions for future language design are offered.
Process structuring, synchronization, and recovery using atomic actions
Authors: Lomet D. B.
Published: October 2004

This paper explores the notion of an atomic
action
as a method of process structuring. This notion, first introduced explicitly by Eswaren et al [6] in the context of data base systems, reduces the problem of coping with many processes to that of coping with a single process within the atomic
action
. A form of process synchronization, the
await
statement, is adapted to work naturally with atomic actions. System recovery is also considered and we show how atomic actions can be used to isolate recovery action to a single process. Explicit control of recovery is provided by a
reset
procedure that permits information from rejected control paths to be passed to subsequent alternative paths.
Early experience with Mesa
Authors: Geschke Charles M. , Morris James H. , Satterthwaite Edwin H.
Published: October 2004

The experiences of Mesa's first users—primarily its implementers—are discussed, and some implications for Mesa and similar programming languages are suggested. The specific topics addressed are:

module structure and its use in defining abstractions,

data-structuring facilities in Mesa,

equivalence algorithm for types and type coercions,

benefits of the type system and why it is breached occasionally,

difficulty of making the treatment of variant records safe.
An input/output subsystem for the Hawk operating system kernel
Authors: Harris David L.
Published: October 2004

This paper describes the input/output subsystem that is provided with the Hawk operating system kernel and the SANDAC V computer. Hawk and the SANDAC V were designed for embedded hard real-time applications. The IOS is a hierarchically organized set of modules t h a t can be configured to match the requirements of a specific real-time application. It was designed to interact with and control a variety of peripheral devices, some of which do not match traditional models. The subsystem executes concurrently with the application tasks in either an asynchronous or synchronous fashion.
Three reasons to avoid the use clause
Authors: Mendal G.
Published: October 2004

Ada's use clause is regarded by some as the nemesis of the language, and by others as the only reasonable mechanism of importing visibility from other program units. Many organizations have struggled with the problem of whether to allow their programmers to use the use clause. Often their decisions are based on erroneous, slanted, emotional, or political rationale. This paper shows by means of example why th e use clause should be avoided completely. It focuses solely on the technical aspects of systems which rely on the use clause.
International workshop on real-time Ada issues: summary report
Authors: Brosgol Benjamin
Published: October 2004

This workshop, sponsored by Ada U. K. in cooperation with ACM SIGAda, was held in Devon, England, during 13--15 May 1987. It comprised five main sessions on the broad and overlapping topics of Application Requirements, Tasking, Issues in Distributed Processing, Run-Time System Issues, and Design and Development Techniques. A summary session at the end established a set of conclusions and recommendations.Participants in the workshop were selected on the basis of submitted position papers. There were 37 attendees, with 16 representing organizations that are users/implementors of real-time software, 11 representing academic institutions or research laboratories, 6 representing vendors of Ada compilers, and 4 representing hardware manufacturers. The users were principally concerned with avionics and other "hard" real-time applications, as opposed to plant processing control or similar systems with "soft" real-time constraints. Partitioned by country, there were 20 from the U. S., 7 from the U. K., 4 from France, and 1 each from Denmark, Finland, Germany, Italy, Spain and Sweden. (Five from the U. S. were in fact natives of the U.K., so there were more British accents than might be apparent from these figures.)This paper is a summary of the three-day workshop. Complete proceedings including position papers by the participants have been published as a special issue of
Ada Letters
(Volume VII, Number 6, Fall 1987).
The applicability of Ada (R) to MIL-STD-1750A
Authors: Roast C.
Published: October 2004

Contrary to recently publicized concern in some DoD sectors, Texas Instruments believes that Ada is a suitable higher order language for the generation of real-time avionics application software on MIL-STD-1750A compatible computers. The perceived problems with using Ada generated programs on the 1750A are not unique to Ada, but also apply to JOVIAL and other high-order languages as well. These perceived problems have been based primarily on subjective, worst-case application scenarios, with no real basis in quantitative, empirical data. Recent analysis internal to Texas Instruments and within the SAE/AE9-E industry/government forum on Computer Architecture Standards have not identified any major shortcomings of the 1750A instruction-set architecture which will present a unique problem for Ada applications. The 1750A architecture has proven to be adequate for many HOL (especially JOVIAL) applications thusfar. The same techniques which have proven successful for applying JOVIAL/1750A to real-time avionics applications will also apply to Ada. These techniques involve an appropriate implementation of the compiler's run-time support model and the observance and enforcement of certain "programming-style" or "coding" methodologies by the application software designer. Furthermore, there is no real evidence to suggest that the techniques which have made JOVIAL usable for past/present real-time avionic applications of 1750A will not continue to apply to foreseeable applications of Ada and 1750A as well.
MMAIM: a software development method for Ada
Authors: Carter J.
Published: October 2004

Traditional methods for software development fail to make use of Ada's unique features to support software engineering principles. Several methods have been proposed to overcome this problem, but shortcomings have been identified with all of them. A method for Ada software development is presented which avoids the shortcomings of existing methods. Further work required on the method is also discussed.
The Ada ASEET team
Authors: McDonald C.
Published: October 2004

The purpose of this paper is to acquaint the Ada software engineering community with the activities of the Ada Software Engineering Education and Training Team. This paper discusses the background of the Team, the present working groups, and future activities that will be sponsored by the Team. Questions concerning the Team may be addressed to any of the Team members listed at the end of this article.
Universal framework for information activities
Authors: Auramäki Esa , Leppanen Mauri , Savolainen Vesa
Published: October 2004

This paper defines a new fundamental, conceptual component of an information system. This component, together with the principles of systems-theoretical control structure and linguistic abstraction, is employed in constructing a universal hierarchical framework for the information activities in an organization. The framework lays the foundations for the analysis, modelling and evaluation of different kinds of informations systems, and their positions and relations of information activities in an organization. It thus offers a comprehensive model of information systems and a basis for research problem settings on all framework levels, e.g., on the information systems development (ISD) level and the ISD model construction level. The framework is shown to compete favorably with the earlier frameworks constructed by ANSI, ISO, Ives, et al., Nolan and Wetherbe, and Zahran.
A taxonomy of Ada packages
Authors: Sumate Ken , Nielsen Kjell
Published: October 2004

A taxonomy of Ada packages is presented to describe their use in designing large programs. The categories include application, communication, and helper packages. Helper packages are further subdivided into definitions, services, and data managers. Data managers are further divided into abstract data types and resources. An abstract data type can be of an open or a closed type. Each of the categories described as part of the taxonomy is illustrated with a coding example that shows both the package and how the package is used.
Using the VAX/VMS lock manager with Ada tasks
Authors: Maloney James J.
Published: October 2004

The VAX/VMS Lock Manager is a powerful, general purpose facility that provides various levels of granularity for concurrent access to shared resources. However, its support for the Ada language is limited, in that it cannot recognize situatio where Ada tasks (which are implemented as part of one process in VAX/VMS Ada) are competing for a resource. In such situations, t VAX/VMS Lock Manager is most likely to assume that there is a deadlock (within a process) on a resource.This paper presents a possible solution to this problem, developing, via stepwise refinement, a "Multi-Threaded Lock Package," which can be used by Ada programs using Ada tasks. The paper also presents some special problems when dealing with concurrency in general, and provides an example of how to use Ada tasks with families of entries.
The costs and limits of availability for replicated services
Authors: Yu Haifeng , Vahdat Amin
Published: October 2004

As raw system and network performance continues to improve at exponential rates, the utility of many services is increasingly limited by availability rather than performance. A key approach to improving availability involves replicating the service across multiple, wide-area sites. However, replication introduces well-known tradeoffs between service consistency and availability. Thus, this paper explores the benefits of dynamically trading consistency for availability using a
continuous consistency model
. In this model, applications specify a maximum deviation from strong consistency on a per-replica basis. In this paper, we: i) evaluate availability of a prototype replication system running across the Internet as a function of consistency level, consistency protocol, and failure characteristics, ii) demonstrate that simple optimizations to existing consistency protocols result in significant availability improvements (more than an order of magnitude in some scenarios), iii) use our experience with these optimizations to prove tight upper bounds on the availability of services, and iv) show that maximizing availability typically entails remaining as close to strong consistency as possible during times of good connectivity, resulting in a communication versus availability trade-off.
Information and control in gray-box systems
Authors: Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: October 2004

In modern systems, developers are often unable to modify the underlying operating system. To build services in such an environment, we advocate the use of
gray-box
techniques. When treating the operating system as a gray-box, one recognizes that not changing the OS restricts, but does not completely obviate, both the
information
one can acquire about the internal state of the OS and the
control
one can impose on the OS. In this paper, we develop and investigate three gray-box Information and Control Layers (ICLs) for determining the contents of the file-cache, controlling the layout of files across local disk, and limiting process execution based on available memory. A gray-box ICL sits between a client and the OS and uses a combination of algorithmic knowledge, observations, and inferences to garner information about or control the behavior of a gray-box system. We summarize a set of techniques that are helpful in building gray-box ICLs and have begun to organize a "gray toolbox" to ease the construction of ICLs. Through our case studies, we demonstrate the utility of gray-box techniques, by implementing three useful "OS-like" services without the modification of a single line of OS source code.
Real-time dynamic voltage scaling for low-power embedded operating systems
Authors: Pillai Padmanabhan , Shin Kang G.
Published: October 2004

In recent years, there has been a rapid and wide spread of non-traditional computing platforms, especially mobile and portable computing devices. As applications become increasingly sophisticated and processing power increases, the most serious limitation on these devices is the available battery life. Dynamic Voltage Scaling (DVS) has been a key technique in exploiting the hardware characteristics of processors to reduce energy dissipation by lowering the supply voltage and operating frequency. The DVS algorithms are shown to be able to make dramatic energy savings while providing the necessary peak computation power in general-purpose systems. However, for a large class of applications in embedded real-time systems like cellular phones and camcorders, the variable operating frequency interferes with their deadline guarantee mechanisms, and DVS in this context, despite its growing importance, is largely overlooked/under-developed. To provide real-time guarantees, DVS must consider deadlines and periodicity of real-time tasks, requiring integration with the real-time scheduler. In this paper, we present a class of novel algorithms called
real-time DVS
(RT-DVS) that modify the OS's real-time scheduler and task management service to provide significant energy savings while maintaining real-time deadline guarantees. We show through simulations and a working prototype implementation that these RT-DVS algorithms closely approach the theoretical lower bound on energy consumption, and can easily reduce energy consumption 20% to 40% in an embedded real-time system.
Resilient overlay networks
Authors: Andersen David , Balakrishnan Hari , Kaashoek Frans , Morris Robert
Published: October 2004

A Resilient Overlay Network (RON) is an architecture that allows distributed Internet applications to detect and recover from path outages and periods of degraded performance within several seconds, improving over today's wide-area routing protocols that take at least several minutes to recover. A RON is an application-layer overlay on top of the existing Internet routing substrate. The RON nodes monitor the functioning and quality of the Internet paths among themselves, and use this information to decide whether to route packets directly over the Internet or by way of other RON nodes, optimizing application-specific routing metrics.Results from two sets of measurements of a working RON deployed at sites scattered across the Internet demonstrate the benefits of our architecture. For instance, over a 64-hour sampling period in March 2001 across a twelve-node RON, there were 32 significant outages, each lasting over thirty minutes, over the 132 measured paths. RON's routing mechanism was able to detect, recover, and route around
all
of them, in less than twenty seconds on average, showing that its methods for fault detection and recovery work well at discovering alternate paths in the Internet. Furthermore, RON was able to improve the loss rate, latency, or throughput perceived by data transfers; for example, about 5% of the transfers doubled their TCP throughput and 5% of our transfers saw their loss probability reduced by 0.05. We found that forwarding packets via at most one intermediate RON node is sufficient to overcome faults and improve performance in most cases. These improvements, particularly in the area of fault detection and recovery, demonstrate the benefits of moving some of the control over routing into the hands of end-systems.
Building efficient wireless sensor networks with low-level naming
Authors: Heidemann John , Silva Fabio , Intanagonwiwat Chalermek , Govindan Ramesh , Estrin Deborah , Ganesan Deepak
Published: October 2004

In most distributed systems, naming of nodes for low-level communication leverages topological location (such as node addresses) and is independent of any application. In this paper, we investigate an emerging class of distributed systems where low-level communication does not rely on network topological location. Rather, low-level communication is based on attributes that are
external
to the network topology and
relevant
to the application. When combined with dense deployment of nodes, this kind of named data enables
in-network processing
for data aggregation, collaborative signal processing, and similar problems. These approaches are essential for emerging applications such as sensor networks where resources such as bandwidth and energy are limited. This paper is the first description of the software architecture that supports named data and in-network processing in an operational, multi-application sensor-network. We show that approaches such as in-network aggregation and nested queries can significantly affect network traffic. In one experiment aggregation reduces traffic by up to 42% and nested queries reduce loss rates by 30%. Although aggregation has been previously studied in simulation, this paper demonstrates nested queries as another form of in-network processing, and it presents the first evaluation of these approaches over an operational testbed.
A low-bandwidth network file system
Authors: Muthitacharoen Athicha , Chen Benjie , Mazières David
Published: October 2004

Users rarely consider running network file systems over slow or wide-area networks, as the performance would be unacceptable and the bandwidth consumption too high. Nonetheless, efficient remote file access would often be desirable over such networks---particularly when high latency makes remote login sessions unresponsive. Rather than run interactive programs such as editors remotely, users could run the programs locally and manipulate remote files through the file system. To do so, however, would require a network file system that consumes less bandwidth than most current file systems.This paper presents LBFS, a network file system designed for low-bandwidth networks. LBFS exploits similarities between files or versions of the same file to save bandwidth. It avoids sending data over the network when the same data can already be found in the server's file system or the client's cache. Using this technique in conjunction with conventional compression and caching, LBFS consumes over an order of magnitude less bandwidth than traditional network file systems on common workloads.
Building a robust software-based router using network processors
Authors: Spalink Tammo , Karlin Scott , Peterson Larry , Gottlieb Yitzchak
Published: October 2004

Recent efforts to add new services to the Internet have increased interest in software-based routers that are easy to extend and evolve. This paper describes our experiences using emerging network processors---in particular, the Intel IXP1200---to implement a router. We show it is possible to combine an IXP1200 development board and a PC to build an inexpensive router that forwards minimum-sized packets at a rate of 3.47Mpps. This is nearly an order of magnitude faster than existing pure PC-based routers, and sufficient to support 1.77Gbps of aggregate link bandwidth. At lesser aggregate line speeds, our design also allows the excess resources available on the IXP1200 to be used robustly for extra packet processing. For example, with 8 × 100Mbps links, 240 register operations and 96 bytes of state storage are available for each 64-byte packet. Using a hierarchical architecture we can guarantee line-speed forwarding rates for simple packets with the IXP1200, and still have extra capacity to process exceptional packets with the Pentium. Up to 310Kpps of the traffic can be routed through the Pentium to receive 1510 cycles of extra per-packet processing.
SIGACT News complexity theory column 32
Authors: Hemaspaandra Lane A.
Published: October 2004

We describe some recent or not-so-recent results in the model of learning known as exact learning from queries. Some results are chosen because they led to a result in complexity theory, and others are chosen because they seem to indicate an interesting line of research at the common ground of learning and complexity. More precisely, we survey: (1) an improvement of the Karp-Lipton collapse that stemmed from a learning algorithm for Boolean circuits, (2) recent advances in distinguishing information-theoretic from complexity-theoretic difficulty of learning, and (3) recent results on learning small-depth circuits with modular gates that call for a systematic study of the expressive power of so-called Multiplicity Automata.
On the cost of fault-tolerant consensus when there are no faults
Authors: Keidar Idit , Rajsbaum Sergio
Published: October 2004

We consider the consensus problem in an asynchronous model enriched with unreliable failure detectors and in the partial synchrony model. We consider algorithms that solve consensus and tolerate crash failures and/or message omissions. We prove tight lower bounds on the number of communication steps performed by such algorithms in failure-free executions. We present in a unified framework a number of related lower bound results. Thus, we shed light on the relationships among different known lower and upper bounds, and at the same time, illustrate a general technique for obtaining simple and elegant lower bound proofs. We also illustrate matching upper bounds: we algorithms that achieve the lower bound.
An ECN probe-based connection acceptance control
Authors: Kelly Tom
Published: October 2004

Connection acceptance control is a mechanism which can be used to moderate the load placed on a network by turning away connection requests during times of overload. Traditionally these mechanisms have been implemented by setting up state within a network using signalling protocols, such as the IETF's Resource Reservation Protocol. There have been recent proposals for admission control based on end-systems probing the network to infer network load. These distributed algorithms often have less router state and hence scale more easily. This paper discusses an ECN (Explicit Congestion Notification) probe-based admission control protocol that is fast, scalable and robust. The protocol's performance is then studied through simulation. It is concluded that probe-based admission control is viable in both partitioned and integrated networks, but more research is needed to understand the implications for network policy control.
Voice over IP performance monitoring
Authors: Cole R. G. , Rosenbluth J. H.
Published: October 2004

We describe a method for monitoring Voice over IP (VoIP) applications based upon a reduction of the ITU-T's E-Model to transport level, measurable quantities. In the process, 1) we identify the relevant transport level quantities, 2) we discuss the tradeoffs between placing the monitors within the VoIP gateways versus placement of the monitors within the transport path, and 3) we identify several areas where further work and consensus within the industry are required. We discover that the relevant transport level quantities are the delay, network packet loss and the decoder's de-jitter buffer packet loss. We find that an in-path monitor requires the definition of a reference de-jitter buffer implementation to estimate voice quality based upon observed transport measurements. Finally, we suggest that more studies are required, which evaluate the quality of various VoIP codecs in the presence of representative packet loss patterns.
Some guidelines for non-repudiation protocols
Authors: Louridas Panagiotis
Published: October 2004

Non-repudiation protocols aim at preventing parties in a communication from falsely denying having taken part in that communication; for example, a non-repudiation protocol for digital certified mail should ensure that neither the sender can deny sending the message, nor the receiver can deny receiving it. We identify some guidelines for non-repudiation protocols. The guidelines are derived by examining a series of non-repudiation protocols that descend from a single ancestor.
Decentralized optimal traffic engineering in the internet
Authors: Lagoa Constantino , Che Hao
Published: October 2004

Distributed optimal traffic engineering in the presence of multiple paths has been found to be a difficult problem to solve. In this paper, we introduce a new approach in an attempt to tackle this problem. This approach has its basis in nonlinear control theory. More precisely, it relies on the concept of Sliding Modes. We develop a family of control laws, each of them having the property that the steady-state network resource allocation yields the maximum of the given utility function, subject to the network resource constraints. These control laws not only allow each ingress node to independently adjust its traffic sending rate but also provide a scheme for optimal traffic load redistribution among multiple paths. The only nonlocal information needed is binary feedback from each congested node in the path. Moreover, the algorithms presented are applicable to a large class of utility functions, namely, utility functions that can be expressed as the sum of concave functions of the sending rates. We show that the technique can be applied not only to rate adaptive traffic with multiple paths, but also to assured service traffic with multiple paths. Preliminary case studies show that this technique is potentially very useful for optimal traffic engineering in a multiple-class-of-service and multiple-path enabled Internet, e.g., differentiated services enabled multi-protocol label switching networks.
The breadcrumb forwarding service
Authors: Yano Koichi , McCanne Steven
Published: October 2004

If ubiquitously deployed, IP Multicast promises to provide an efficient datagram service for an arbitrary sending host to reach an arbitrary and dynamic set of destination hosts anywhere in the Internet. Unfortunately, two very difficult problems ---interdomain multicast routing and viable end-to-end multicast transport--- have yet to be solved and deployed satisfactorily.This paper proposes that two existing but independent network mechanisms--- the EXPRESS service model and the network component of the Pragmatic Multicast protocol (PGM)--- be synthesized in a scheme we call the
Breadcrumb Forwarding Service
(BCFS) to simultaneously tackle the problems of interdomain multicast routing and end-to-end reliable multicast. Like EXPRESS, BCFS utilizes explicit-source group join and like PGM, enhances the network forwarding architecture with finer-grained group control. In this paper, we detail BCFS service model and router mechanisms to support the service. To demonstrate the flexibility and efficiency of BCFS, we describe the application examples built on this service model, which can accommodate not only PGM and also a novel reliable multicast transport protocol.
Distributed core multicast (DCM)
Authors: Blazević Ljubica , Le Boudec Jean-Yves
Published: October 2004

We present a multicast routing protocol called Distributed Core Multicast (DCM). It is intended for use within a large single Internet domain network with a very large number of multicast groups with a small number of receivers. Such a case occurs, for example, when multicast addresses are allocated to mobile hosts, as a mechanism to manage Internet host mobility or in large distributed simulations. For such cases, existing dense or sparse mode multicast routing algorithms do not scale well with the number of multicast groups. DCM is based on an extension of the centre-based tree approach. It uses several core routers, called Distributed Core Routers (DCRs) and a special control protocol among them. DCM aims: (1) avoiding multicast group state information in backbone routers, (2) avoiding triangular routing across expensive backbone links, (3) scaling well with the number of multicast groups. We evaluate the performance of DCM and compare it to an existing sparse mode routing protocol when there is a large number of small multicast groups. We also analyse the behaviour of DCM when the number of receivers per group is not a small number.
BGP scaling techniques revisited
Authors: Scudder John G. , Dube Rohit
Published: October 2004

This note adds definitions and clarification to "A Comparison of Scaling Techniques for BGP" [1], corrects some minor errors and clarifies points which may not have been clear in the original paper. It also adds a new analysis of the scaling properties of route-reflectors and confederations, leading to a new conclusion that route-reflection and confederations scale equally well in the general case and that the choice of the scaling technique employed by a network needs to be made on a basis other than the scalability metric we have analyzed.
ESW4
Authors: Hadjiefthymiades Stathes , Merakos Lazaros
Published: October 2004

Mobile computing is considered of major importance to the computing industry for the forthcoming years due to the progress in the wireless communications domain. In this paper, we present a proxy-based architecture, called ESW4, which manages to accelerate Web browsing in wireless CPNs. Proxy caches, maintained in base stations, are constantly relocated to accompany the roaming user. We discuss a cache management scheme involving the relocation of full caches to the most candidate cells but also percentages of the cache to less likely neighbors. Relocation is performed according to the output of a movement prediction algorithm based on a learning automaton. The simulation of ESW4 shows substantial benefits for the end user.
On the effective evaluation of TCP
Authors: Allman Mark , Falk Aaron
Published: October 2004

Understanding the performance of the Internet's Transmission Control Protocol (TCP) is important because it is the dominant protocol used in the Internet today. Various testing methods exist to evaluate TCP performance, however all have pitfalls that need to be understood prior to obtaining useful results. Simulating TCP is difficult because of the wide range of variables, environments, and implementations available. Testing TCP modifications in the global Internet may not be the answer either: testing new protocols on real networks endangers other people's traffic and, if not done correctly, may also yield inaccurate or misleading results. In order for TCP research to be independently evaluated in the Internet research community there is a set of questions that researchers should try to answer. This paper attempts to list some of those questions and make recommendations as to how TCP testing can be structured to provide useful answers.
TCP byte counting refinements
Authors: Allman Mark
Published: October 2004

TCP's delayed acknowledgment algorithm has been shown to hurt TCP performance. One method of gaining the performance lost by reducing the number of acknowledgments sent is to use a
limited byte counting
algorithm. However, we show that as outlined in [All98], limited byte counting is too aggressive in some situations. This paper defines an
appropriate byte counting
algorithm to fix this aggressiveness. This paper shows that appropriate byte counting is a better overall algorithm. In addition, a scaled version of the appropriate byte counting algorithm, which provides finer-grained control over the aggressiveness of the algorithm, is outlined. In addition, unlike previous work this paper considers the impact of byte counting flows on competing traffic and shows that it is not fundamentally unfair to competing flows that do not use the new algorithm.
A RED discard strategy for ATM networks and its performance evaluation with TCP/IP traffic
Authors: Rosolen Vincent , Bonaventure Olivier , Leduc Guy
Published: October 2004

In ATM UBR networks supporting TCP traffic, optimal efficiency can only be envisaged if switches adopt a discard mechanism that operates at the packet level rather than the cell level. In this paper, we define a variant of the RED discard strategy suitable for ATM switches. An interesting feature of this ATM-RED is that it has a similar per-VC implementation complexity as the Early Packet Discard (EPD) algorithm. To study the efficiency of the ATM-RED discard strategy, we compare its performance with plain the UBR, EPD and Fair Buffer Acceptance (FBA) discard strategies by means of simulation with TCP/IP traffic. We give comparative results with respect to different performance criteria such as goodput and fairness in various environments, such as end-to-end ATM networks and IP-based networks with an ATM backbone, in both single-bottlenecked and GFC topologies.
A comparison of scaling techniques for BGP
Authors: Dube Rohit
Published: October 2004

BGP is
the
inter-domain routing protocol used in the Internet today. During the course of its evolution, the Internet has gone from being a simple and small network to one that is run at its core by large service providers constantly battling with bigger and bigger topologies forcing the routing community to invent ways of scaling both interior and exterior routing protocols.
Route-reflectors
and
confederations
have turned out to be the weapons of choice in scaling BGP to these large topologies. This paper takes a close look at these two mechanisms and seeks to compare them.
Automatic VLAN creation based on on-line measurement
Authors: Rooney Sean , Hörtnagl Christian , Krause Jens
Published: October 2004

Virtual LANs (VLANs) permit hosts connected to a LAN switch to be grouped together into logical groups as a function of some management policy rather than simply of their physical location. Commercial LAN switches support a variety of policies based on either physical or logical addresses, protocol types, tagged frames, or user defined rules. The objective of these policies is the same: to reduce the amount of traffic that needs to be routed by grouping together hosts which are likely to communicate with each other into the same virtual LAN. This paper proposes a novel and more direct approach, it shows how VLANs can be created and removed dynamically as a function of the
measured
traffic patterns across the network. This is both simpler than configuring many static rules and permits the VLAN configuration to adapt to the evolution in the traffic patterns. The latter point is especially important in future LANs supporting peer-to-peer continuous media services, such as IP telephony or video-conferencing, in which clusters of hosts come together to communicate with each other intensively for relatively short periods of time and then form into new clusters.
A survey of programmable networks
Authors: Campbell Andrew T. , De Meer Herman G. , Kounavis Michael E. , Miki Kazuho , Vicente John B. , Villela Daniel
Published: October 2004

In this paper we present a programmable networking model that provides a common framework for understanding the state-of-the-art in programmable networks. A number of projects are reviewed and discussed against a set of programmable network characteristics. We believe that a number of important innovations are creating a paradigm shift in networking leading to higher levels of network programmability. These innovations include the separation between transmission hardware and control software, availability of open programmable network interfaces, accelerated virtualization of networking infrastructure, rapid creation and deployment of new network services and environments for resource partitioning and coexistence of multiple distinct network architectures. We present a simple qualitative comparison of the surveyed work and make a number of observations about the direction of the field.
YESSIR
Authors: Pan Ping , Schulzrinne Henning
Published: October 2004

RSVP has been designed to support resource reservation in the Internet. However, it has two major problems: complexity and scalability. The former results in large message processing overhead at end systems and routers, and inefficient firewall processing at the edge of the network. The latter implies that in a backbone environment, the amount of bandwidth consumed by refresh messages and the storage space that is needed to support a large number of flows at a router are too large. We have developed a new reservation mechanism that simplifies the process of establishing reserved flows while preserving many unique features introduced by RSVP. Simplicity is measured in terms of control message processing, data packet processing, and user-level flexibility. Features such as robustness, advertising network service availability and resource sharing among multiple senders are also supported in the proposal.The proposed mechanism, YESSIR (YEt another Sender Session Internet Reservations) generates reservation requests by senders to reduce the processing overhead, builds on top of RTCP, uses
soft state
to maintain reservation states, supports shared reservation and associated flow merging and is compatible with the IETF Integrated Services models.YESSIR extends the all-or-nothing reservation model to support partial reservations that improve over the duration of the session.To address the scalability issue, we investigate the possibility of using YESSIR for per-stream reservation and RSVP for aggregate reservation.
Effect of traffic knowledge on the efficiency of admission-control policies
Authors: Trajković Ljiljana , Neidhardt Arnie
Published: October 2004

We investigate the importance of understanding traffic characteristics for admission-control policies in packet networks. We compare the network utilization achieved with admission policies based on a partial knowledge of admitted traffic against the utilization that could be achieved with complete knowledge of traffic characteristics. Our quantitative study demonstrates that for realistic traffic traces the level of traffic knowledge dramatically affects admission control and improves network utilization. Indeed, the knowledge of only a few elementary traffic characteristics can produce substantial improvement. Yet, at least for one trace, this improvement based on elementary traffic knowledge is modest in comparison with the improvement that could be produced with additional traffic knowledge and if traffic characterization on more than one time scale were available.
Experience with a commercial Java implementation of group communication using reliable multicast
Authors: Oestreicher Dan
Published: October 2004

Tantus Reliable Multicast is an implementation of a set of group communication primitives for use by a particular local area network application. The system provides resilience against any single point of failure in the network, total sequencing of messages and events, and automatic notification of loss of group members. It has been designed to be used by a trading room system, or by any similar systems that have strong requirements for secure recording of transactions and immediate notification of data changes to multiple interested clients. Both the API and the daemon, in their latest implementations, have been written in Java.This paper describes the considerations that have gone into the design decisions for the product, and experience in developing and testing the product.The product has been developed for Tantus plc, (tantus.co.uk) and provides some of the underlying software for that company's commercial trading room and distributed database systems. The product and all its source code, documentation, etc., are the property of Tantus plc, whom I thank for permission to publish this paper.
Three-party encrypted key exchange
Authors: Lin Chun-Li , Sun Hung-Min , Hwang Tzonelih
Published: October 2004

Password-based mechanism is the widely used method for authentication since it allows people to choose their own passwords without any assistant device to generate or store. However, people are used to choose easy-to-remember passwords such that guessing attacks could succeed. In 1992, Bellovin and Merritt proposed
Encrypted Key Exchange
(EKE) protocols for preventing guessing attacks, in which two communication parties
A
and
B
securely share a possibly weak password in advance. In large communication environments, it is inconvenient in key management that every two communication parties mutually share a secret. Three-party EKE protocols, in which all parties (clients) share their secrets with a trusted server only, are more suitable for large communication environments. In 1995, Steiner, Tsudik and Waidner proposed a realization of three-party EKE protocol which is later demonstrated that it is vulnerable to undetectable on-line guessing attacks. In this paper, We will show a new off-line guessing attack on Steiner, Tsudik and Waidners' protocol. Besides, we will also propose a new three-party EKE protocol which not only is secure against both the off-line guessing attack and undetectable on-line guessing attacks but also satisfies the security properties of perfect forward secrecy and known-key security.