bluuebunny/crossref_metadata_2025 huggingface dataset:
Multicast routing in internetworks and extended LANs
Authors: Deering Stephen E.
Published: October 2004

Multicasting is used within local-area networks to make distributed applications more robust and more efficient. The growing need to distribute applications across multiple, interconnected networks, and the increasing availability of high-performance, high-capacity switching nodes and networks, lead us to consider providing LAN-style multicasting across an internetwork. In this paper, we propose extensions to two common internetwork routing algorithms---distance-vector routing and link-state routing---to support low-delay datagram multicasting. We also suggest modifications to the single-spanning-tree routing algorithm, commonly used by link-layer bridges, to reduce the costs of multicasting in large extended LANs. Finally, we show how different link-layer and network-layer multicast routing algorithms can be combined hierarchically to support multicasting across large, heterogeneous internetworks.
The design philosophy of the DARPA Internet Protocols
Authors: Clark David D.
Published: October 2004

The Internet protocol suite, TCP/IP, was first proposed fifteen years ago. It was developed by the Defense Advanced Research Projects Agency (DARPA), and has been used widely in military and commercial systems. While there have been papers and specifications that describe how the protocols work, it is sometimes difficult to deduce from these why the protocol is as it is. For example, the Internet protocol is based on a connectionless or datagram mode of service. The motivation for this has been greatly misunderstood. This paper attempts to capture some of the early reasoning which shaped the Internet protocols.
A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer
Authors: Ramakrishnan K. K. , Jain Raj
Published: October 2004

We propose a scheme for
congestion avoidance
in networks using a connectionless protocol at the network layer. The scheme uses feedback from the network to the users of the network. The interesting challenge for the scheme is to use a minimal amount of feedback (one bit in each packet) from the network to adjust the amount of traffic allowed into the network. The servers in the network detect congestion and set a
congestion indication
bit on packets flowing in the forward direction. The congestion indication is communicated back to the users through the transport level acknowledgement.

The scheme is distributed, adapts to the dynamic state of the network, converges to the optimal operating point, is quite simple to implement, and has low overhead while operational. The scheme also addresses a very important aspect of
fairness
in the service provided to the various sources utilizing the network. The scheme attempts to maintain fairness in service provided to multiple sources.

This paper presents the scheme and the analysis that went into the choice of the various decision mechanisms. We also address the performance of the scheme under transient changes in the network and for pathological conditions.
A control-theoretic approach to flow control
Authors: Keshav S.
Published: October 2004

This paper presents a control-theoretic approach to reactive flow control in networks that do not reserve bandwidth. We assume a round-robin-like queue service discipline in the output queues of the network's switches, and propose deterministic and stochastic models for a single conversation in a network of such switches. These models motivate the Packet-Pair rate probing technique, and a provably stable rate-based flow control scheme. A Kalman state estimator is derived from discrete-time state space analysis, but there are difficulties in using the estimator in practice. These difficulties are overcome by a novel estimation scheme based on fuzzy logic. We then present a technique to extract and use additional information from the system to develop a continuous-time system model. This is used to design a variant of the control law that is also provably stable, and, in addition, takes control action as rapidly as possible. Finally, practical issues such as correcting parameter drift and coordination with window flow control are described.
Measured performance of data transmission over cellular telephone networks
Authors: Alanko Timo , Kojo Markku , Laamanen Heimo , Liljeberg Mika , Moilanen Marko , Raatikainen Kimmo
Published: October 2004

Recent developments in mobile communication and personal computer technology have laid a new foundation for mobile computing. Performance of the data communication system as seen by an application program is a fundamental factor when communication infrastructure at the application layer is designed. This paper provides results of performance measurements of data transmission over two different cellular telephone networks, a digital GSM-network and an analogue NMT-network. Since our emphasis is on performance as seen by application programs, we use the standard TCP/IP protocols in the measurements. The performance is measured using three basic operations: establishment of a wireless dial-up connection, exchange of request-reply messages, and bulk data transfer. The external conditions under which the measurements were carried out present a normal office environment when the field strength of the cellular link is good or fairly good.
Can we trust in HDLC?
Authors: Fiorini D. , Chiani M. , Tralli V. , Salati C.
Published: October 2004

in spite of the theoretical error detecting capability of its CRC, the actual degree of data integrity provided by HDLC is quite low.The paper gives a quantitative assessment of HDLC's deficiencies and of their reasons, paying particular attention to actual applications of the HDLC family of standards.Finally, we look at some strategies that have been suggested to allow the use of HDLC in the most demanding applications.
Proposed icons for Ada 95
Authors: Crawford Bard S.
Published: October 2004

Several graphical icons, representing new features introduced during the Ada 95 language-update process, are proposed. Uses of the proposed icons, in combination with traditional forms already familiar to Ada developers, are illustrated in various contexts. The new forms and illustrated uses are offered in the hope that de-facto notational standards will emerge and provide assistance in documentation, teaching and the development of visual design and browsing tools.
A survey of current object-oriented databases
Authors: Zand Mansour , Collins Val , Caviness Dale
Published: October 2004

Object-oriented concepts form a good basis for the data models required for next-generation database applications such as CAD/CAE/CASE/CAM systems, knowledge-based systems, multimedia, etc. Many object-oriented databases are available commercially or are being developed by industry or academic research facilities. This paper attempts to compare some of these products using fourteen criteria. The selected criteria are major factors required for the successful design of an object-oriented database system. They are grouped into five different categories. The result of the survey is summarized in a table.
Business process redesign an information architecture
Authors: Teng James T. C. , Kettinger William J.
Published: October 2004

Business process redesign (BPR) and information architecture (IA) have been recognized as high priority agenda items in organizations during the 1990s. This paper explores the relationships between the two concepts. Specifically, this paper focuses on three main concerns: how IA supports BPR, how the lack of IA hinders BPR, and what approach to IA can facilitate BPR? The paper begins with a brief review of the development and implementation of each concept. This is followed by an examination of how IA and BPR are related to business processes, both existing and newly designed processes. This analysis, in conjunction with results from field research, provide the basis for nine propositions regarding the BPR and IA relationship. In support of BPR, IS professionals have the opportunity not only to contribute to a firm's business objectives, but also to begin to achieve IA's promise while avoiding some of IA's past implementation problems. It is hoped that further research based on these propositions will lead to more complete answers and perhaps more specific questions on the BPR/IA relationships.
The measurement of information systems effectiveness
Authors: Scott Judy E.
Published: October 2004

Information system effectiveness is an important phenomenon for both researchers and practitioners. Despite widespread interest, and the importance of the uses, there have been no efforts to validate
Computerworld's
Premier 100 rankings of information system effectiveness. This paper uses structural equation modeling in an attempt to validate the measuring instrument used to derive the
Computerworld
rankings.Alternative models for the measuring instrument are proposed. Using a reflective model, the findings raise doubts as to the reliability of the rankings, and both content validity and construct validity are also suspect. The reliability and validity are problematic because multiple indicators of the same construct must be homogeneous for it to make sense to combine them into a composite index. A solution to this problem is to represent information system effectiveness as a multidimensional construct, that is part of a causal model. Based on previous research in the area, suggestions are offered to improve the measuring instrument.
Refinement and extension of encrypted key exchange
Authors: Steiner Michael , Tsudik Gene , Waidner Michael
Published: October 2004

In their recent paper, "Encrypted Key Exchange: Password-based Protocols Secure Against Dictionary Attacks," Bellovin and Merritt propose a novel and elegant method for safeguarding weak passwords. This paper discusses a possible weakness in the proposed protocol, develops some enhancements and simplifications, and provides a security analysis of the resultantminimalEKE protocol. In addition, the basic 2-party EKE model is extended to the 3-party setting; this yields a protocol with some interesting properties. Most importantly, this paper illustrates, once again, the subtlety associated with designing password-based protocols.
A short note a small virtually-addressed control blocks
Authors: Liedtke Jochen
Published: October 2004

Being able to access task and thread control blocks in the virtual address space has some structuring and performance advantages, but using one page per control block is too expensive in some cases. This paper describes how to emulate smaller kernel pages though still using the hardware MMU.
The design of VIP-FS
Authors: Harry Michael , del Rosario Juan Miguel , Choudhary Alok
Published: October 2004

In the past couple of years, significant progress has been made in the development of message-passing libraries for parallel and distributed computing, and in the area of high-speed networking. Both technologies have evolved to the point where programmers and scientists are now porting many applications previously executed exclusively on parallel machines into distributed programs for execution on more readily available networks of workstations. Such advances in computing technology have also led to a tremendous increase in the amount of data being manipulated and produced by scientific and commercial application programs. Despite their popularity, message-passing libraries only provide part of the support necessary for most high performance distributed computing applications --- support for high speed parallel I/O is still lacking.In this paper, we provide an overview of the conceptual design of a parallel and distributed I/O file system, the Virtual Parallel File System (VIP-FS), and describe its implementation. VIP-FS makes use of message-passing libraries to provide a parallel and distributed file system which can execute over multiprocessor machines or heterogeneous network environments.
Semaphores revisited with MMS
Authors: Castori Pierre
Published: October 2004

The objective of this article is to realize an in-depth study of MMS semaphores. This article is not a tutorial on MMS semaphores although it does explain to some extent how MMS semaphores behave and can be utilized. What we are trying to achieve is a definitive clarification of the MMS semaphore concept in order to make its use easier to MMS programmers and to encourage its adoption in the industrial applications and products. We compare MMS semaphores to Dijkstra's classical semaphores and show that real differences exist. Other mechanisms are also discussed (monitors, CSP). Examples are provided to illustrate our analysis and references to the semaphore mechanism of some operating systems are given to ease the comparison. We come to the conclusion that MMS semaphores are flexible but cannot be utilized to solve all kinds of problems classical semaphores usually cope with. We also explain why the two kinds of semaphores provided by MMS are redundant.
DGDBM
Authors: Franky Maria Consuelo
Published: October 2004

This paper describes a set of facilities for programming distributed transactions over replicated files which are accessed by primary key. The files are located on several computers communicated by a network. Each site has the set of GNU dbm (Gdbm) routines for local file management [15]. Above this platform we have built an interface and a set of services for distributed transaction programming. The resulting programming environment,"DGDBM", offers transparency in relation to data distribution and data replication, giving a centralized vision to the programmer. It assures the functions of management of distributed transactions like as failure recovery, mutual consistency between copies and concurrence control. DGDBM is an useful support for distributed application programming over replicated files in UNIX networks and it is available as an API (application programming interface) for the C programmer. This paper describes the services offered by DGDBM to the programmer, the architecture of the system, the adopted solutions for distributed transaction management, the general aspects of design and implementation and the perspectives and planned extensions for this project.
The information economy: A new perspective for effective information systems management
Authors: Zmud Robert W , Boynton Andrew C , Jacobs Gerry C
Published: October 2004

"The basic function of administration appears to be co-alignment, not merely of people in coalitions but of institutionalized action --- of technology and task environment into a viable domain, and of organizational design and structure appropriate to it. Administration, when it works well, keeps the organization at the nexus of several necessary streams of action" [13].
A survey of UNI signaling systems and protocols for ATM networks
Authors: Stiller Burkhard
Published: October 2004

The main aspect covered by signaling systems and protocols for ATM networks concerns the possibility to manage, maintain, and control a user-driven communication between arbitrary ATM end-systems connected to an ATM network. The tasks and procedures defined for, e.g., setting-up an ATM connection, are often very different concerning the rrelevant specifications of various working bodies (such as ITU-T or ATM-Forum) or certain vendors, although the basis to be done for maintaining ATM connections are always principally the same. The reason for this situation is, that the intentions of working bodies are different and each one of them follows specific strategies for certain scenarios (such as for point-to-point unicast or point-to-multipoint multicast). Nevertheless, various types of characteristics (such as addressing, multicast, or interworking) are requested from applications residing on top of ATM networks.

Therefore, this survey of signaling systems and protocols for ATM networks identifies for several of selected approaches (such as Q.2931, UNI 3.1, or CMAP) important characteristics and relevant scenarios. Furthermore, a table-based comparison of some approaches has been added
Rate-based congestion control for ATM networks
Authors: Ohsaki Hiroyuki , Murata Masayuki , Suzuki Hiroshi , Ikeda Chinatsu , Miyahara Hideo
Published: October 2004

Congestion control plays an important role in the effective and stable operation of ATM networks. This paper first gives a historical overview of rate-based congestion control algorithms developed in the ATM Forum, showing how the current ATM Forum standard regarding the traffic management control methods is exploited, by these algorithm. Then, analytical approach is used to quantitatively evaluate their performance and show the effectiveness of the rate-based approach. In presenting the numerical examples, we emphasize that appropriate control parameter settings are essential for proper traffic management in an ATM network environment.
Topology aggregation for hierarchical routing in ATM networks
Authors: Lee Whay C.
Published: October 2004

This paper provides a tutorial for topology arregation in large hierarchical communication networks. Specifically, it examines some issues of topology aggregation for hierarchical PNNI Routing in ATM networks, presents a complex node representation, and provides some guidelines for topology aggregation. There are two main reasons for topology aggregation. First, topology information must be compressed to avoid excessive complexity in topology adevertisement. Second, the internal topology of a network may have to be hidden for security reasons. A desirable topology aggregation method must adequately represent the topology of a given network for efficient routing and netowrk resource allocation, using a compact advertised topology.
Timed protocol verification for Estelle-specified protocols
Authors: Huang Chung-Ming , Lee Shiun-Wei
Published: October 2004

This paper presents a new model, which is named Timed Communicating State Machine (TCSM), for specifying protocols that incorporate timed properties as part of their specifications. The TCSM model is similar to the Extended Communicating Finite State Machine (ECFSM) model. The major extension is providing an additional mechanism, i.e., a time interval attribute, for describing the timed properties. We also propose the corresponding formal TCSM-based timed verification scheme, i.e., a new timed global state reachability analysis. In the new timed global state reachability analysis, the exploration is decided by the predicate, the time relationships, and/or the input event. Using the TCSM model and the timed verification scheme, an Estelle-based Timed Protocol Verification System (ETPVS) has been developed on SUN SPARC workstations. In this way, timed protocols can be formally specified in Estelle and can also be verified using ETPVS.
Protocol architecture for multimedia applications over ATM networks
Authors: Kandlur Dilip D. , Saha Debanjan , Willebeek-LeMair M.
Published: October 2004

At the data-link layer, ATM offers a number of features, such as high-bandwidth and per-connection quality of service (QoS) guarantees, making it particularly attractive to multimedia applications. Unfortunately, many of these features are not visible to applications because of the inadequacies of existing higher-level protocol architectures. Although a considerable effort is underway to tune these protocols for ATM networks, we believe that a new ATM specific protocol stack is essential to effectively exploit all the benefits of ATM. In this paper we describe the semantics of such a protocol stack, and discuss its advantages over traditional protocol architectures from the perspective of distributed multimedia applications. The performance impact of the new protocol architecture is experimentally demonstrated on a video conferencing testbed built around IBM RS/6000s equipped with prototype hardware for video/audio processing, and connected via ATM links.
Taming Xunet III
Authors: Aneroussis Nikos G. , Lazar Aurel A. , Pendarakis Dimitrios E.
Published: October 2004

An architecture for network management and control for emerging wide-area ATM networks is presented. The architecture was implemented on XUNET III, a nationwide ATM network deployed by AT&T. The Xunet network management system is based on the OSI standards and includes configuration, fault and performance management. An OSI agent resides at every switching node. Its capabilities include monitoring of cell level quality of service in real time and estimation of the schedulable region. The complexity and accuracy of real-time monitoring functionalities is investigated. To provide realistic traffic loads, distributed traffic generation systems both at the cell and call level have been implemented. In order to study the trade-off between the network transport and signalling system we have implemented a virtual path signalling capability. Our experiments show that the ability of a network to admit calls is limited by two distinct factors: the capacity of the network and the processing power of the signalling system. Depending on the bandwidth requirement of calls, the limit of one or the other will be first reached. This is a key observation, unique to broadband networks.
The (un)revised OSI reference model
Authors: Day John
Published: October 2004

In 1988, SC21, the ISO committee responsible for the Open Systems Interconnection (OSI) Reference Model, determined that it was time to undertake revising ISO 7498-1, The Basic OSI Reference Model. Since the model had been published in 1984, this was in accordance with ISO practice of reviewing and revising standards every five years, and there was good reason for considering the task. Over the intervening five years, the groups developing the OSI protocols had raised many questions about the architecture and these had been answered and documented in the Approved Commentaries [1994]. Many of these commentaries contained information that could be usefully incorporated into the Reference Model itself. In addition, the addendum describing connectionless mode, i.e. datagrams, had been completed several years before and needed to be incorporated. There was also considerable demand for interworking connection-mode and connectionless mode communication, something not supported by the Reference Model or any architecture. Also, when the original version of the Reference Model was frozen about 1983 some aspects of OSI such as the upper layers were not well understood and were only described in the most cursory manner. And while connection-mode and connectionless mode had been brought within OSI, there was no indication as to how broadcast and multicast were to be handled. Thus, the revision might be able to provide a more comprehensive description of these areas.This paper describes how the revision was carried out, describes the changes and additions that were made, considers the effect and contribution this revision has made to our understanding, and describes the outstanding issues that were not addressed by this revision.
Practical experiences in interconnecting LANs via satellite
Authors: Celandroni Nedo , Ferro Erina , Potortì Francesco , Bellini Alessandro , Pirri Franco
Published: October 2004

We present an experiment in interconnecting LANs via a satellite link and describe the individual components involved in the experiment. The project was developed in two phases: a) design and realisation of a satellite access scheme that supports real-time and non real-time traffic with a signal fading countermeasure, called FODA/IBEA-TDMA; b) interconnection of LANs where real-time and non real-time applications run. The experiment was presented the first time in June 1994 as a demo in which the Eutelsat satellite was used (in the 12/14 GHz band) to exchange data between two LANs in Pisa and Florence, while video and audio applications running on PCs connected the two sites. The demo was repeated a few weeks later and the Intelsat satellite was used in the 20/30 GHz band.
Design, implementation, and evaluation of a software-based real-time Ethernet protocol
Authors: Venkatramani Chitra , Chiueh Tzi-cker
Published: October 2004

Distributed multimedia applications require performance guarantees from the underlying network subsystem. Ethernet has been the dominant local area network architecture in the last decade, and we believe that it will remain popular because of its cost-effectiveness and the availability of higher-bandwidth Ethernets. We present the design, implementation and evaluation of a software-based timed-token protocol called RETHER that provides real-time performance guarantees to multimedia applications without requiring any modifications to existing Ethernet hardware. RETHER features a hybrid mode of operation to reduce the performance impact on non-real-time network traffic, a race-condition-free distributed admission control mechanism, and an efficient token-passing scheme that protects the network against token loss due to node failures or otherwise. To our knowledge, this is the first software implementation of a real-time protocol over existing Ethernet hardware. Performance measurements from experiments on a 10 Mbps Ethernet indicate that up to 60% of the raw bandwidth can be reserved without deteriorating the performance of non-real-time traffic. Additional simulations for high bandwidth networks and faster workstation hardware indicate that the protocol allows reservation of a greater percentage of the available bandwidth.
Pipelined memory shared buffer for VLSI switches
Authors: Katevenis Manolis , Vatsolaki Panagiota , Efthymiou Aristides
Published: October 2004

Switch chips are building blocks for computer and communication systems. Switches need internal buffering, because of output contention; shared buffering is known to perform better than multiple input queues or buffers, and the VLSI implementation of the former is
not
more expensive than the latter. We present a new organization for a shared buffer with its associated switching and cut-through functions. It is simpler and smaller than wide or interleaved organizations, and it is particularly suitable for VLSI technologies. It is based on multiple memory banks, addressed in a pipelined fashion. The first word of a packet is transferred to/from the first bank, followed by a "wave" of similar operations for the remaining words in the remaining banks. An FPGA-based prototype is operational, while standard-cell and full-custom chips are being submitted for fabrication. Simulation of the full-custom version indicates that, even in a conservative 1-micron CMOS technology, a 64 Kbit central buffer for an 8×8 switch operates at 1 Gbps/link (worst case) and fits in 45
mm
2
including crossbar and cut-through.
a
I
t
P
m
Authors: Parulkar Guru , Schmidt Douglas C. , Turner Jonathan S.
Published: October 2004

This paper describes research on new methods and architectures that enable the synergistic combination of
IP
and
ATM
technologies. We have designed a highly scalable gigabit
IP
router based on an
ATM
core and a set of tightly coupled general-purpose processors. This a
I
t
P
m (pronounced "
IP
on
ATM
" or, if you prefer, "ip-attem") architecture provides flexibility in congestion control, routing, resource management, and packet scheduling.The a
I
t
P
m architecture is designed to allow experimentation with, and fine tuning of, the protocols and algorithms that are expected to form the core of the next generation
IP
in the context of a gigabit environment. The underlying multi-
CPU
embedded system will ensure that there are enough
CPU
and memory cycles to perform all
IP
packet processing at gigabit rates. We believe that the a
I
t
P
m architecture will not only lead to a scalable high-performance gigabit
IP
router technology, but will also demonstrate that
IP
and
ATM
technologies can be mutually supportive.
Hierarchical distance-vector multicast routing for the MBone
Authors: Thyagarajan Ajit S. , Deering Stephen E.
Published: October 2004

The exponential growth of the Multicast Back-bone (MBone) has resulted in increased routing overhead and processing costs. In this paper we propose a two-level hierarchical routing model as a solution to this problem. This approach involves partitioning the MBone into non-overlapping regions using DVMRP as the inter-region routing protocol; intra-region routing may be accomplished by any of a number of existing multicast protocols. Our design is flexible enough to accommodate additional levels of hierarchy, and protocols other than DVMRP at the higher levels. The unique feature of this approach is the independence of the higher level routing protocol from the subnet addresses, which allows for easy incremental deployment with small changes to existing intra-region protocols.
Performance analysis of MD5
Authors: Touch Joseph D.
Published: October 2004

MD5 is an authentication algorithm proposed as the required implementation of the authentication option in IPv6. This paper presents an analysis of the speed at which MD5 can be implemented in software and hardware, and discusses whether its use interferes with high bandwidth networking. The analysis indicates that MD5 software currently runs at 85 Mbps on a 190 Mhz RISC architecture, a rate that cannot be improved more than 20-40%. Because MD5 processes the entire body of a packet, this data rate is insufficient for current high bandwidth networks, including HiPPI and FiberChannel. Further analysis indicates that a 300 Mhz custom VLSI CMOS hardware implementation of MD5 may run as fast as 256 Mbps. The hardware rate cannot support existing IPv4 data rates on high bandwidth links (800 Mbps HiPPI). The use of MD5 as the default required authentication algorithm in IPv6 should therefore be reconsidered, and an alternative should be proposed. This paper includes a brief description of the properties of such an alternative, including a sample alternate hash algorithm.
Self-similarity through high-variability
Authors: Willinger Walter , Taqqu Murad S. , Sherman Robert , Wilson Daniel V.
Published: October 2004

A number of recent empirical studies of traffic measurements from a variety of working packet networks have convincingly demonstrated that actual network traffic is
self-similar
or
long-range dependent
in nature (i.e., bursty over a wide range of time scales) - in sharp contrast to commonly made traffic modeling assumptions. In this paper, we provide a plausible physical explanation for the occurrence of self-similarity in high-speed network traffic. Our explanation is based on convergence results for processes that exhibit
high variability
(i.e., infinite variance) and is supported by detailed statistical analyses of real-time traffic measurements from Ethernet LAN's at the level of individual sources.Our key mathematical result states that the superposition of many ON/OFF sources (also known as
packet trains
) whose ON-periods and OFF-periods exhibit the
Noah Effect
(i.e., have high variability or infinite variance) produces aggregate network traffic that features the
Joseph Effect
(i.e., is self-similar or long-range dependent). There is, moreover, a simple relation between the parameters describing the intensities of the Noah Effect (high variability) and the Joseph Effect (self-similarity). An extensive statistical analysis of two sets of high time-resolution traffic measurements from two Ethernet LAN's (involving a few hundred active source-destination pairs) confirms that the data at the level of individual sources or source-destination pairs are consistent with the Noah Effect. We also discuss implications of this simple physical explanation for the presence of self-similar traffic patterns in modern high-speed network traffic for (i) parsimonious traffic modeling (ii) efficient synthetic generation of realistic traffic patterns, and (iii) relevant network performance and protocol analysis.
Protocol implementation using integrated layer processing
Authors: Braun Torsten , Diot Christophe
Published: October 2004

Integrated Layer Processing (ILP) is an implementation concept which "permit[s] the implementor the option of performing all the [data] manipulation steps in one or two integrated processing loops" [1]. To estimate the achievable benefits of
ILP
a file transfer application with an encryption function on top of a user-level TCP has been implemented and the performance of the application in terms of throughput and packet processing times has been measured. The results show that it is possible to obtain performance benefits by integrating marshalling, encryption and TCP checksum calculation. They also show that the benefits are smaller than in simple experiments, where ILP effects have not been evaluated in a complete protocol environment. Simulations of memory access and cache hit rate show that the main benefit of ILP is reduced memory accesses rather than an improved cache hit rate. The results further show that data manipulation characteristics may significantly influence the cache behavior and the achievable performance gain of ILP.
Trading packet headers for packet processing
Authors: Chandranmenon Girish P. , Varghese George
Published: October 2004

In high speed networks, packet processing is relatively expensive while bandwidth is cheap. Thus it pays to add information to packet headers to make packet processing easier. While this is an old idea, we describe several specific new mechanisms based on this principle. We describe a new technique,
source hashing
, which can provide
O
(1) lookup costs at the Data Link, Routing, and Transport layers. Source hashing is especially powerful when combined with the old idea of a
flow ID
; the flow identifier allows packet processing information to be cached, and source hashing allows efficient cache lookups. Unlike Virtual Circuit Identifiers (VCIs), source hashing does not require a round trip delay for set up. In an experiment with the BSD Packet Filter implementation, we found that adding a flow ID and a source hash improved packet processing costs by a factor of 7. We also found a 45% improvement when we conducted a similar experiment with IP packet forwarding. We also describe two other new techniques:
threaded indices
, which allows fast VCI-like lookups for datagram protocols like IP; and a
Data Manipulation Layer
, which compiles out all the information needed for Integrated Layer Processing into an easily accessible portion of each packet.
An automatic trace analysis tool generator for Estelle specifications
Authors: Ezust S. Alan , v. Bochmann Gregor
Published: October 2004

This paper describes the development of Tango, an automatic generator of backtracking trace analysis tools for single-process specifications written in the formal description language, Estelle. A tool generated by Tango automatically checks the validity of any execution trace against the given specification, and supports a number of checking options. The approach taken was to modify an Estelle-to-C++ compiler. Discussion about nondeterministic specifications, multiple observation points, and on-line trace analysis follow. Trace analyzers for the protocols LAPD and TP0 have been tested and performance results are evaluated. Issues in the analysis of partial traces are also discussed.
Authentication protocols for personal communication systems
Authors: Lin Hung-Yu , Harn Lein
Published: October 2004

Masquerading and eavesdropping are major threats to the security of wireless communications. To provide proper protection for the communication of the wireless link, contents of the communication should be enciphered and mutual authentication should be conducted between the subscriber and the serving network. Several protocols have been proposed by standards bodies and independent researchers in recent years to counteract these threats. However, the strength of these protocols is usually weakened in the roaming environment where the security breach of a visited network could lead to persistent damages to subscribers who visit. The subscriber's identity is not well protected in most protocols, and appropriate mechanisms solving disputes on roaming bills are not supported either. To solve these problems, new authentication protocols are proposed in this paper with new security features that have not been fully explored before.
Floor acquisition multiple access (FAMA) for packet-radio networks
Authors: Fullmer Chane L. , Garcia-Luna-Aceves J. J.
Published: October 2004

A family of medium access control protocols for single-channel packet radio networks is specified and analyzed. These protocols are based on a new channel access discipline called floor acquisition multiple access (FAMA), which consists of both carrier sensing and a collision-avoidance dialogue between a source and the intended receiver of a packet. Control of the channel (the floor) is assigned to at most one station in the network at any given time, and this station is guaranteed to be able to transmit one or more data packets to different destinations with no collision with transmissions from other stations. The minimum length needed in control packets to acquire the floor is specified as a function of the channel propagation time. The medium access collision avoidance (MACA) protocol proposed by Karn and variants of CSMA based on collision avoidance are shown to be variants of FAMA protocols when control packets last long enough compared to the channel propagation delay. The throughput of FAMA protocols is analyzed and compared with the throughput of non-persistent CSMA. This analysis shows that using carrier sensing as an integral part of the floor acquisition strategy provides the benefits of MACA in the presence of hidden terminals, and can provide a throughput comparable to, or better than, that of non-persistent CSMA when no hidden terminals exist.
The conference control channel protocol (CCCP)
Authors: Handley Mark , Wakeman Ian , Crowcroft Jon
Published: October 2004

This paper presents the Conference Control Channel Protocol (CCCP), a new scheme intended for controlling conferences ranging from small, tightly coupled meetings, to extremely large loosely coupled seminars. We describe the requirements of such a scheme, and present a framework for building systems that connect together new and existing applications.
Log-based receiver-reliable multicast for distributed interactive simulation
Authors: Holbrook Hugh W. , Singhal Sandeep K. , Cheriton David R.
Published: October 2004

Reliable multicast communication is important in large-scale distributed applications. For example, reliable multicast is used to transmit terrain and environmental updates in distributed simulations. To date, proposed protocols have not supported these applications' requirements, which include wide-area data distribution, low-latency packet loss detection and recovery, and minimal data and management over-head within fine-grained multicast groups, each containing a single data source.In this paper, we introduce the notion of
Log-Based Receiver-reliable Multicast
(LBRM) communication, and we describe and evaluate a collection of log-based receiver reliable multicast optimizations that provide an efficient, scalable protocol for high-performance simulation applications. We argue that these techniques provide value to a broader range of applications and that the receiver-reliable model is an appropriate one for communication in general.
A brief survey of current work on network attached peripherals (extended abstract)
Authors: Van Meter Rodney
Published: October 2004

Work on network-attached peripherals (NAPs) can be divided into essentially three areas --- device interfaces and protocols, multimedia use and mass storage use. This paper is an extended abstract reviewing some of the current work and provides references and WWW pointers to many of the projects. The impact of this technological advance on operating systems is discussed. The primary purpose of this paper is to broaden understanding of the advantages and pitfalls of NAPs and encourage further research in the design and use of network-attached peripherals and NAP-capable systems. An expanded form of this document is available on the web or from the author.
Architectural principles and techniques for distributed multimedia application support in operating systems
Authors: Coulson Geoff , Blair Gordon
Published: October 2004

We propose some architectural principles we have found useful for the support of continuous media applications in a microkernel environment. In particular, we discuss i) the principle of upcall-driven application structuring whereby communications events are system rather than application initiated, ii) the principle of split-level system structuring whereby key system functions are carried out co-operatively between kernel and user level components and iii) the principle of decoupling of control transfer and data transfer. Under these general headings a number of particular mechanisms and techniques are discussed. Our suggestions arise from experiences in implementing a Chorus based real-time and multimedia support infrastructure within the SUMO project.
Virtual address translation for wide-address architectures
Authors: Shyu Ing-Jye , Shieh Shiuh-Pyng
Published: October 2004

Operating systems employ virtual memory mechanism to provide large address space for programs. The efficiency of the virtual address translation plays an important role in determining system performance. In conventional virtual memory management systems, both the forward-mapped page table scheme and inverted page table scheme are widely used to organize the page tables that record translation data. These two schemes work well for 32-bit architectures, but not for wide address (64-bit) architectures. These two schemes either needs long translation time or incurs large memory overhead when translating wide virtual address. To cope with this problem, we propose a hybrid scheme to accelerate wide virtual address translation.
A survey of power management techniques in mobile computing operating systems
Authors: Welch Gregory F.
Published: October 2004

Many factors have contributed to the birth and continued growth of mobile computing, including recent advances in hardware and communications technology. With this new paradigm however come new challenges in computer operating systems development. These challenges include heretofore relatively unusual items such as frequent network disconnections, communications bandwidth limitations, resource restrictions, and power limitations. It is the last of these challenges that we shall explore in this paper---that is the question of what techniques can be employed in mobile computer operating systems that can reduce the power consumption of today's mobile computing devices.
Is your computing environment secure?
Authors: Hu Ping , Christianson Bruce
Published: October 2004

In an open distributed system, resources must be shared among various users. Security is one of the major issues in designing such a system. When a computer system is connected to a network, it is very important to ensure that the computer has the ability to manage its local resources securely. In this position paper, we will demonstrate that current computer architectures do give malicious users ways to penetrate computer systems and hence access the system or other user's secrets which are supposed to be well protected. We also propose some possible solutions to counterattack such security threats either at hardware or software level. The impacts of our countermeasures to system hardware and software are also discussed.
Worlds to die for
Authors: Hemaspaandra Lane A. , Ramachandran Ajit , Zimand Marius
Published: October 2004

We last had an "open problems" column eighteen months ago [Hem94]. It contained seven problems. Of the seven, one has since been resolved (at least insofar as one can resolve the problem without outright collapsing complexity classes) in an exciting FOCS paper by Cai and Sivakumar ([CS95], see also [Ogi95b,CNS95]), and for another I received a proof via email unfortunately followed quickly by another email retracting the proof. Overall score:Mysteries of Complexity Theory: 6.Theoretical Computer Scientists:1.If you go to Atlantic City, you know which side to bet on! But be of good cheer. This issue's column contains a new list of open problems (though some favorites from the old list have stowed away here too). And to stack the deck in favor of theoretical computer scientists, the problems are posed quite obliquely. Rather than asking you to prove "X," many of the problems (e.g., Problems 2, 4, 5, 6, and 7) just ask you to show that "In
some
oracle world, X." Sound easy? Dig in! And if your attempt to find a world where X holds becomes too frustrating, don't hesitate to go for the real glory --- by proving that X fails in the real world (and every relativized world)!
Teaching algorithms
Authors: Baeza-Yates Ricardo A.
Published: October 2004

In this paper we propose and discuss how to teach algorithms, including contents, methodologies, textbooks, and computer labs. We use the ACM/IEEE curricula as a starting point and compare our proposal to theirs. We raise several issues, but we do not provide definite answers. Our main proposal is a paradigm driven methodology for the main algorithmic course, as well as some paradigms and problems not usually covered. An ultimate teaching algorithm is still an open problem.
Helping programmers understand computer programs
Authors: Shaft Teresa M.
Published: October 2004

A large portion of computer programmers' efforts to maintain, test, and debug computer programs is spent understanding, or comprehending, the existing program. Current theories of program comprehension have not considered the circumstances that cause programmers to use different approaches to understanding programs. Metacognition may provide some insight into the comprehension process. Metacognition is a psychological terms that refers to "one's knowledge concerning one's own cognitive processes" (Flavell, 1976) and influences the execution of cognitive tasks. Through metacognition, a person confronting a cognitive task can select a strategy, and then monitor and regulate their progress on a task.This study investigates the use of metacognition by programmers to purposefully (deliberately) choose a comprehension strategy. The results of this study support the view that programmers use metacognition when studying computer programs. Specifically, two-thirds of the programmers indicated that, in general, they purposefully choose a comprehension strategy. When studying a computer program from an unfamiliar application domain, however, programmers who generally use metacognition had lower levels of comprehension than when working in a familiar domain or when compared to those programmers who do not use metacognition.These results suggest that programmers use metacognition during computer program comprehension and that the use of metacognition influences how well they understand a program. That metacognition reduces comprehension, but only in certain circumstances, leads to the speculation that programmers' metacognitive heuristics may be too general and that programmers need to develop more specific metacognitive heuristics to aid comprehension in a wider range of circumstances.
An Ada-like separate compilation style in C
Authors: Khrabrov Alexy V.
Published: October 2004

The Ada programming language's modularity allows for stepwise refinement in software engineering. Effective separate compilation is crucial in most large systems, including those written in C. An approach to implementing effective modularity in C, modeled after Ada, is explored. The concept of language-independent modularity, and the possibility of implementing it in a given "entry level" language is introduced. An example, a simple sentence parser, is developed in C using this concept. The technique, called A/SC2, may easily be extended to other programming systems and languages. Modeling modularity is a useful design tool.
A naming convention for classes in Ada 9X
Authors: Rosen J.-P.
Published: October 2004

This paper discusses a problem encountered when using generics for faceted OOP in Ada 9X, and proposes a general naming scheme for classes that provides a convenient and readable solution to this problem.