bluuebunny/crossref_metadata_2025 huggingface dataset:
A simulation study of IP switching
Authors: Lin Steven , McKeown Nick
Published: October 2004

Recently there has been much interest in combining the speed of layer-2 switching with the features of layer-3 routing. This has been prompted by numerous proposals, including: IP Switching [1], Tag Switching [2], ARIS [3], CSR [4], and IP over ATM [5]. In this paper, we study IP Switching and evaluate the performance claims made by Newman et al in [1] and [6]. In particular, using ten network traces, we study how well IP Switching performs with traffic found in campus, corporate, and Internet Service Provider (ISP) environments. Our main finding is that IP Switching will lead to a high proportion of datagrams that are switched; over 75% in all of the environments we studied. We also investigate the effects that different flow classifiers and various timer values have on performance, and note that some choices can result in a large VC space requirement. Finally, we present recommendations for the flow classifier and timer values, as a function of the VC space of the switch and the network environment being served.
Scalable high speed IP routing lookups
Authors: Waldvogel Marcel , Varghese George , Turner Jon , Plattner Bernhard
Published: October 2004

Internet address lookup is a challenging problem because of increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP routing lookup requires computing the best matching prefix, for which standard solutions like hashing were believed to be inapplicable. The best existing solution we know of, BSD radix tries, scales badly as IP moves to 128 bit addresses. Our paper describes a new algorithm for best matching prefix using binary search on hash tables organized by prefix lengths. Our scheme scales very well as address and routing table sizes increase: independent of the table size, it requires a worst case time of log
2
(
address bits
) hash lookups. Thus only 5 hash lookups are needed for IPv4 and 7 for IPv6. We also introduce Mutating Binary Search and other optimizations that, for a typical IPv4 backbone router with over 33,000 entries, considerably reduce the average number of hashes to less than 2, of which one hash can be simplified to an indexed array access. We expect similar average case behavior for IPv6.
Solutions to hidden terminal problems in wireless networks
Authors: Fullmer Chane L. , Garcia-Luna-Aceves J. J.
Published: October 2004

The floor acquisition multiple access (FAMA) discipline is analyzed in networks with hidden terminals. According to FAMA, 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 collisions. The FAMA protocols described consist of non-persistent carrier or packet sensing, plus a collision-avoidance dialogue between a source and the intended receiver of a packet. Sufficient conditions under which these protocols provide correct floor acquisition are presented and verified for networks with hidden terminals; it is shown that FAMA protocols must use carrier sensing to support correct floor acquisition. The throughput of FAMA protocols is analyzed for single-channel networks with hidden terminals; it is shown that carrier-sensing FAMA protocols perform better than ALOHA and CSMA protocols in the presence of hidden terminals.
Trace-based mobile network emulation
Authors: Noble Brian D. , Satyanarayanan M. , Nguyen Giao T. , Katz Randy H.
Published: October 2004

Subjecting a mobile computing system to wireless network conditions that are realistic yet reproducible is a challenging problem. In this paper, we describe a technique called
trace modulation
that re-creates the observed end-to-end characteristics of a real wireless network in a controlled and repeatable manner. Trace modulation is transparent to applications and accounts for all network traffic sent or received by the system under test. We present results that show that it is indeed capable of reproducing wireless network performance faithfully.
Fair scheduling in wireless packet networks
Authors: Lu Songwu , Bharghavan Vaduvur , Srikant Rayadurgam
Published: October 2004

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair scheduling algorithms because of two unique characteristics of wireless media: (a) bursty channel errors, and (b) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however a base station has only a limited knowledge of the arrival processes of uplink flows.In this paper, we propose a new model for wireless fair scheduling based on an adaptation of fluid fair queueing to handle location-dependent error bursts. We describe an ideal wireless fair scheduling algorithm which provides a packetized implementation of the fluid model while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless fluid fair queueing model.
Automated packet trace analysis of TCP implementations
Authors: Paxson Vern
Published: October 2004

We describe tcpanaly, a tool for automatically analyzing a TCP implementation's behavior by inspecting packet traces of the TCP's activity. Doing so requires surmounting a number of hurdles, including detecting packet filter measurement errors, coping with ambiguities due to the distance between the measurement point and the TCP, and accommodating a surprisingly large range of behavior among different TCP implementations. We discuss why our efforts to develop a fully general tool failed, and detail a number of significant differences among 8 major TCP implementations, some of which, if ubiquitous, would devastate Internet performance. The most problematic TCPs were all independently written, suggesting that correct TCP implementation is fraught with difficulty. Consequently, it behooves the Internet community to develop testing programs and reference implementations.
Potential benefits of delta encoding and data compression for HTTP
Authors: Mogul Jeffrey C. , Douglis Fred , Feldmann Anja , Krishnamurthy Balachander
Published: October 2004

Caching in the World Wide Web currently follows a naive model, which assumes that resources are referenced many times between changes. The model also provides no way to update a cache entry if a resource does change, except by transferring the resource's entire new value. Several previous papers have proposed updating cache entries by transferring only the differences, or "delta," between the cached entry and the current value.In this paper, we make use of dynamic traces of the full contents of HTTP messages to quantify the potential benefits of delta-encoded responses. We show that delta encoding can provide remarkable improvements in response size and response delay for an important subset of HTTP content types. We also show the added benefit of data compression, and that the combination of delta encoding and data compression yields the best results.We propose specific extensions to the HTTP protocol for delta encoding and data compression. These extensions are compatible with existing implementations and specifications, yet allow efficient use of a variety of encoding techniques.
A flow-based approach to datagram security
Authors: Mittra Suvo , Woo Thomas Y. C.
Published: October 2004

Datagram services provide a simple, flexible, robust, and scalable communication abstraction; their usefulness has been well demonstrated by the success of IP, UDP, and RPC. Yet, the overwhelming majority of network security protocols that have been proposed are geared towards connection-oriented communications. The few that do cater to datagram communications tend to either rely on long term host-pair keying or impose a session-oriented (i.e., requiring connection setup) semantics.Separately, the concept of flows has received a great deal of attention recently, especially in the context of routing and QoS. A flow characterizes a sequence of datagrams sharing some pre-defined attributes. In this paper, we advocate the use of flows as a basis for structuring secure datagram communications. We support this by proposing a novel protocol for datagram security based on flows. Our protocol achieves zero-message keying, thus preserving the connectionless nature of datagram, and makes use of soft state, thus providing the per-packet processing efficiency of session-oriented schemes. We have implemented an instantiation for IP in the 4.4BSD kernel, and we provide a description of our implementation along with performance results.
A hierarchical fair service curve algorithm for link-sharing, real-time and priority services
Authors: Stoica Ion , Zhang Hui , Ng T. S. Eugene
Published: October 2004

In this paper, we study hierarchical resource management models and algorithms that support both link-sharing and guaranteed real-time services with decoupled delay (priority) and bandwidth allocation. We extend the service curve based QoS model, which defines both delay and bandwidth requirements of a class, to include fairness, which is important for the integration of real-time and hierarchical link-sharing services. The resulting
Fair Service Curve link-sharing
model formalizes the goals of link-sharing and real-time services and exposes the fundamental tradeoffs between these goals. In particular, with decoupled delay and band-width allocation, it is impossible to simultaneously provide guaranteed real-time service and achieve perfect link-sharing. We propose a novel scheduling algorithm called Hierarchical Fair Service Curve (H-FSC) that approximates the model closely and efficiently. The algorithm always guarantees the performance for leaf classes, thus ensures real-time services, while minimizing the discrepancy between the actual services provided to the interior classes and the services defined by the Fair Service Curve link-sharing model. We have implemented the H-FSC scheduler in the NetBSD environment. By performing simulation and measurement experiments, we evaluate the link-sharing and real-time performances of H-FSC, and determine the computation over-head.
Iolus
Authors: Mittra Suvo
Published: October 2004

As multicast applications are deployed for mainstream use, the need to secure multicast communications will become critical. Multicast, however, does not fit the point-to-point model of most network security protocols which were designed with unicast communications in mind. As we will show, securing multicast (or group) communications is fundamentally different from securing unicast (or paired) communications. In turn, these differences can result in scalability problems for many typical applications.In this paper, we examine and model the differences between unicast and multicast security and then propose Iolus: a novel framework for scalable secure multicasting. Protocols based on Iolus can be used to achieve a variety of security objectives and may be used either to directly secure multicast communications or to provide a separate group key management service to other "security-aware" applications. We describe the architecture and operation of Iolus in detail and also describe our experience with a protocol based on the Iolus framework.
Parity-based loss recovery for reliable multicast transmission
Authors: Nonnenmacher Jörg , Biersack Ernst , Towsley Don
Published: October 2004

We investigate how FEC (Forward Error Correction) can be combined with ARQ (Automatic Repeat Request) to achieve scalable reliable multicast transmission. We consider the two scenarios where FEC is introduced as a transparent layer underneath a reliable multicast layer that uses ARQ, and where FEC and ARQ are both integrated into a single layer that uses the retransmission of
parity
data to recover from the loss of original data packets.To evaluate the performance improvements due to FEC, we consider different types of loss behaviors (spatially or temporally correlated loss, homogeneous or heterogeneous loss) and loss rates for up to 10
6
receivers. Our results show that introducing FEC as a layer below ARQ can improve multicast transmission efficiency and scalability and that there are substantial additional improvements when the two are integrated.
Scheduling of multicast traffic in tunable-receiver WDM networks with non-negligible tuning latencies
Authors: Ortiz Zeydy , Rouskas George N. , Perros Harry G.
Published: October 2004

We consider the problem of supporting multipoint communication at the media access control (MAC) layer of broadcast-and-select WDM networks. We first show that bandwidth consumption and channel utilization arise as two conflicting objectives in the design of scheduling algorithms for multicast traffic in this environment. We then present a new technique for the transmission of multicast packets, based on the concept of a
virtual
receiver, a set of physical receivers which behave identically in terms of tuning. We also show that the number κ of virtual receivers naturally captures the tradeoff between channel utilization and bandwidth consumption. Our approach decouples the problem of determining the virtual receivers from the problem of scheduling packet transmissions, making it possible to employ existing scheduling algorithms that have been shown to successfully hide the effects of tuning latency. Consequently, we focus on the problem of optimally selecting the virtual receivers, and we prove that it is
NP
-complete. Finally, we present four heuristics of varying degrees of complexity for obtaining virtual receivers that provide a good balance between the two conflicting objectives.
Effective erasure codes for reliable computer communication protocols
Authors: Rizzo Luigi
Published: October 2004

Reliable communication protocols require that all the intended recipients of a message receive the message intact. Automatic Repeat reQuest (ARQ) techniques are used in unicast protocols, but they do not scale well to multicast protocols with large groups of receivers, since segment losses tend to become uncorrelated thus greatly reducing the effectiveness of retransmissions. In such cases, Forward Error Correction (FEC) techniques can be used, consisting in the transmission of redundant packets (based on error correcting codes) to allow the receivers to recover from independent packet losses.Despite the widespread use of error correcting codes in many fields of information processing, and a general consensus on the usefulness of FEC techniques within some of the Internet protocols, very few actual implementations exist of the latter. This probably derives from the different types of applications, and from concerns related to the complexity of implementing such codes in software. To fill this gap, in this paper we provide a very basic description of erasure codes, describe an implementation of a simple but very flexible erasure code to be used in network protocols, and discuss its performance and possible applications. Our code is based on Vandermonde matrices computed over
GF
(

p
r

), can be implemented very efficiently on common microprocessors, and is suited to a number of different applications, which are briefly discussed in the paper. An implementation of the erasure code shown in this paper is available from the author, and is able to encode/decode data at speeds up to several MB/s running on a Pentium 133.
Possibilities of using protocol converters for NIR system construction
Authors: Ubik Sven
Published: October 2004

Volumes of information available from network information services have been increasing considerably in recent years. Users' satisfaction with an information service depends very much on the quality of the network information retrieval (NIR) system used to retrieve information. The construction of such a system involves two major development areas: user interface design and the implementation of NIR protocols.In this paper we describe and discuss the possibilities of using formal methods of protocol converter design to construct the part of an NIR system client that deals with network communication. If this approach is practicable it can make implementation of NIR protocols more reliable and amenable to automation than traditional designs using general purpose programming languages. This will enable easy implementation of new NIR protocols custom-tailored to specialized NIR services, while the user interface remains the same for all these services.Based on a simple example of implementing the Gopher protocol client we conclude that the known formal methods of protocol converter design are generally not directly applicable for our approach. However, they could be used under certain circumstances when supplemented with other techniques which we propose in the discussion.
Performance interactions between P-HTTP and TCP implementations
Authors: Heidemann John
Published: October 2004

This document describes several performance problems resulting from interactions between implementations of persistent-HTTP (P-HTTP) and TCP. Two of these problems tie P-HTTP performance to TCP delayed-acknowledgments, thus adding up to 200ms to each P-HTTP transaction. A third results in multiple slow-starts per TCP connection. Unresolved, these problems result in P-HTTP transactions which are 14 times slower than standard HTTP and 20 times slower than potential P-HTTP over a 10 Mb/s Ethernet. We describe each problem and potential solutions. After implementing our solutions to two of the problems, we observe that P-HTTP performs better than HTTP on a local Ethernet. Although we observed these problems in specific implementations of HTTP and TCP (Apache-1.1b4 and SunOS 4.1.3, respectively), we believe that these problems occur more widely.
MASH
Authors: Rosenstein Adam , Li Jun , Tong Si Yuan
Published: October 2004

The
archie
[1] system is a replicated, centralized directory server for all Anonymous FTP sites in the Internet. This centralized approach has not scaled well. The
march
[2] system provides an alternate solution, using IP Multicast to distribute directory queries directly to FTP hosts.
march
suffers from highly redundant broadcast messages during expanding-disc search. We propose a solution to the problem of multicast flooding during expanding-disc searches by utilizing an automatically-configured hierarchy of query servers. This system, dubbed
MASH
, confines the multicast flooding primarily to those nodes at the frontier of each new search radius. We provide a mechanism and protocol for building a self-organizing, two-level hierarchy of
MASH
servers. We also provide an experimental implementation built on
march
[5].
Decentralised approaches for network management
Authors: Kahani Mohsen , Beadle H. W. Peter
Published: October 2004

Centralised network management has shown inadequacy for efficient management of large heterogenous networks. As a result, several distributed approaches have been adapted to overcome the problem. This paper is a review of decentralised network management techniques and technologies. We explain distributed architectures for network management, and discuss some of the most important implemented distributed network management systems. A comparison is made between these approaches to show the pitfalls and merits of each.
Adaptive feedback compensation for distributed load-based routing systems in datagram packet-switched communications networks
Authors: Olsen Arthur S.
Published: October 2004

Routing systems for datagram packet-switched networks' iteratively applying Shortest Path First (SPF) algorithms on load-based link cost metrics exhibit poor stabilization and convergence properties at moderate traffic loads without the addition of experimentally determined Bertsekas Additive Bias Factors to aid in damping undesirable oscillations. Routing systems which iteratively apply SPF Algorithms on load-varying link costs implicitly assume routing assignments can be independently modified without affecting the validity of cost estimates on other links. Even under stationary offered loads, this assumption is less accurate as the load increases due to nonlinear dynamical interactions among traffic flows. Failure to compensate for this independence assumption in iterative SPF computations leads to dynamical instabilities above moderate offered loads. Unfortunately, while Bertsekas Additive Bias Factors improve stability, they also reduce the sensitivity of the routing system to network congestion. As alleviation of traffic congestion is often an important service requirement for a routing system, this is a serious drawback. This paper is motivated by a search for techniques to improve the convergence of routing systems upon near-optimum sets of routing assignments for current traffic conditions, without introducing a loss of congestion sensitivity. Due to the limitations of Markov Chain Models of packet-switching networks for our application, a network simulation is developed which provides a more accurate reflection of network dynamics, as it incorporates bounded queue and minimum interarrival time constraints. Utilizing this simulation, it is demonstrated that a Genetic Algorithm which estimates the near-optimal number of routing assignment changes allowed by the Dijkstra SPF Algorithm during each routing update interval, enables substantial performance advantages for networks operated at or above moderate offered loads. This adaptive feedback compensation technique achieves these performance improvements by avoiding the Kauffman and Eigen Catastrophes, although additional processing and slight increases in routing update packet lengths are required. In a broader context, the technology of adaptive feedback compensation should prove a relevant to a variety of real-time distributed adaptive control applications.
Report on the 5
th
IFIP international workshop on quality of service (IWQOS'97)
Authors: Angin Oguz , Campbell Andrew T. , Cheok Lai-Tee , Liao Raymond R-F , Lim Koon-Seng , Nahrstedt Klara
Published: October 2004

This paper presents a summary of the fifth International Workshop on Quality of Service (IWQOS) which was held at Columbia University in May 1997. The goal of this three-day meeting was to foster interaction between researchers active in the area of Quality of Service(QOS) research, to reflect on past experiences and lessons learnt, and to discuss future QOS challenges. To reflect this goal, this year's workshop included a hot program made up of (i) a keynote address on "Programming Telecommunications Networks"; (ii) panels addressing "QOS for Distributed Object Computing Middleware --- Fact or Fiction?" and "Reservations about Reservations"; (iii) a workshop invited paper entitled, "Quality of Service --- Where are we?" and (iv) ten technical sessions that included new topics for IWQOS such as mobile communications, QOS routing and QOS-based transport systems. This report summarizes the technical program and captures the main themes and major areas of discussion that emerged during IWQOS'97.
Bibliography of recent publications on computer communication
Authors: Crowcroft Jon
Published: October 2004

Due to an error in the simulation used to conduct removal policy experiments, one of the primary conclusions from our SIGCOMM'96 paper is in error. We present here the corrections, and some new results. The conclusion "sorting by SIZE is the best policy to maximize hit rate," is correct. However, the other primary conclusion "sorting by SIZE is the best policy to maximize weighted hit rate," is
incorrect
. In fact, sorting by SIZE was found to be the
worst
policy. A brief description of changes in each of the four experiments conducted follows. The text of the revised paper can be found at
http:-//www.cs.vt.edu/~chitra/docs/96sigcomm/
.
Is there anything “time-honored” in the field of software?
Authors: Glass Robert L.
Published: October 2004

Step right up, ladies and gentlemen, and take a gander at the latest in software life cycles! We're displaying here the brand-new 1997 model, folks. It's lower and longer and - what's even more important - it guarantees you that your next software project will come in under budget, on schedule, and with more quality than you had ever hoped for!
China's movement toward a national information infrastructure
Authors: Chismar William G.
Published: October 2004

Since implementing economic reforms in 1979, China's economy, spurred by foreign investment, has been growing at an average annual rate of ten percent. Unfortunately for companies doing business in China, reliable connections to telecommunications and computer networks have only recently become available in the major cities and are non-existent in most of the country. In response, the Chinese government has made the development of an information infrastructure a high priority, but its efforts have been hindered by conflicting political and business interests. In this paper we look at two aspects of the development of an information infrastructure in China: telecommunications development and the internet. Currently the central government maintains tight control over telecommunications development, but this control is quickly breaking down. The internet in China has been developing in a totally separate environment, largely out of the control of the central government; but recent policy changes have brought strict controls over the Internet. This paper presents at China's progress toward a national information infrastructure in light of the political and economic conflict.
Individual characteristics associated with World Wide Web use
Authors: Atkinson MaryAnne , Kydd Christine
Published: October 2004

This study examines the influence of the individual characteristic of playfulness on the use of the World Wide Web (WWW). Previous research suggests that microcomputer playfulness has an effect on computer usage in general, and we found support for a similar relationship in WWW use. Two samples of students were surveyed in this study; one consisting of undergraduate students and the other comprised of graduate students. Our findings also suggest that both intrinsic and extrinsic factors affect WWW use differentially for entertainment purposes and for course work purposes. Our study confirms previous research in that we found that ability to use the computer has a positive effect on WWW usage.
Examining the relationship between computer cartoons and factors in information systems use, success, and failure
Authors: Kendall Julie E.
Published: October 2004

Computer cartoons express the inevitable discrepancies in expectations among systems analysts, users, and managers regarding the systems development processes and information systems products. Computer cartoons also address gaps between ideal and actual information systems, or intended versus actual systems. No one sets out to design a system that fails, or a system that is seldom or incorrectly used. It is hypothesized here that the expectations of users, analysts, and managers are apparent in popular computer cartoons that are widely published, circulated, posted, and shared. Eight broad critical success factors were identified through the CSF literature, and cartoons from the world's largest computerized cartoon database were examined for their existence. Factors identified concerning the IS process include: 1. management support, 2. capable systems analysts, and 3. proper systems development methods. Critical success factors that concern the IS product include whether the information system: 4. works 5. is technically elegant, 6. is easy to use, 7. is a good fit with natural incentives found in the organization, and 8. is a good fit with motivations of users.Illustrative evidence of the eight factors was found in the computer cartoons reviewed and examples of each are presented in this paper. Since cartoons are emblematic expressions of an idea that can be shared, computer cartoons can help users and analysts express their feelings, attitudes, and opinions about information systems development and implementation. It is hoped that the contribution of this study is to bring together the knowledge of critical success factors with the use of computer cartoons to permit analysts and users access to a particularly revealing source of information which spotlights the gap existing between actual and intended information systems processes and products. Many researchers have commented on the desirability of using humor in the workplace; however, this paper is innovative in specifically recommending that using and interpreting computer cartoons can assist in assessing expectations surrounding critical success factors whose attainment shapes the design, implementation, and use of information systems in organizations.
Concurrent objects in Ada 95
Authors: Loeper Hans , Khattab Amro , Neubert Peter
Published: October 2004

Although implicit parallelism is one of the most important advantages besides methodological and software engineering aspects of the object-oriented paradigm, only a few papers are directly dedicated object-oriented concurrency. Based on [Boyd87], [Clark87], [Collard89], and [Baker91], each of which appeared in the ACM Ada Letters, this paper addresses the implementation of concurrent object classes using Ada 95. It offers a uniform template of the structure of concurrent object subclasses leading to polymorphic methods. Finally, a brief remark is made on the importance of generic object classes.
ASIS-based code analysis automation
Authors: Cooper C. Daniel
Published: October 2004

The Ada Semantic Interface Specification (ASIS) is an interface between an Ada environment and any tool requiring information from it. An Ada environment comprises valuable semantic and syntactic information that can be exploited for automated code analysis. ASIS provides an open and published callable interface that gives access to this information; further, ASIS has been designed to be independent of underlying Ada environment implementations, thus supporting portability of code analysis tools while relieving tool developers from needing to understand the complexities of an Ada environment's proprietary and evolving internal representation.
M-TCP
Authors: Brown Kevin , Singh Suresh
Published: October 2004

Transport connections set up over wireless links are frequently plagued by problems such as - high bit error rate (BER), frequent disconnections of the mobile user, and low wireless bandwidth that may change dynamically. In this paper, we study the effects of frequent disconnections and low variable bandwidth on TCP throughput and propose a protocol that addresses this problem. We discuss the implementation (in NetBSD) of our protocol called M-TCP and compare its performance against other mobile TCP implementations. We show that M-TCP has two significant advantages over other solutions: (1) it maintains
end-to-end
TCP semantics and, (2) it delivers excellent performance for environments where the mobile encounters periods of disconnection.
Analysis methodology for simulation of distributed adaptive routing systems
Authors: Olsen Arthur S.
Published: October 2004

In network simulations, complex dynamical behavior is Previous analysis has identified limitations associated with Markov Chain Models and has established a need for the analysis of network dynamics through bound-queue/minimum-interarrival-time simulation models. In network simulations, complex dynamical behavior is observed even for simplistic stationary offered loads. An important contributor to the complexity of the network dynamics is the routing system. When a network consists of a large number of nodes, a routing system is applied in order to route traffic in an efficient manner between the nodes. The routing system has an important effect on the resulting network dynamics. This paper will discuss the complex dynamical behavior observed in networks controlled by distributed adaptive routing systems. This methodology can be applied during stability analyses of routing systems and is useful in system-level simulation verification.
Authentication services for computer networks and electronic messaging systems
Authors: Auyong Keok , Chee Chye-Lin
Published: October 2004

The paper surveys the authentication services used by modern computer systems and presents the major operational authentication services employed by commercial companies, banking as well as government departments. As distributed system services are susceptible to a variety of threats mounted by intruders as well as legitimate users of the system, password-based authentication is not suitable for use on computer networks.
A message-based real-time model by object-oriented technique
Authors: Hou Jianmin , Li Xuandong , Fan Xiaocong , Zheng Guoliang
Published: October 2004

This paper presents the motivation for using object-oriented technique to construct a message-based model for real-time operating systems. It introduces the components of the model and its running mechanism. This model chooses the preempt schedule policy and encapsulates priority with message transmitted between objects. The model is priority-driven and can avoid priority inversion.
Making computation count
Authors: Allender Eric
Published: October 2004

This issue's expert guest column is by Eric Allender, who has just taken over the Structural Complexity Column in the
Bulletin of the EATCS.
Regarding "Journals to Die For" (
SIGACT News
Complexity Theory Column 16), Joachim von zur Gathen, the editor-in-chief of
computational complexity,
has written me pointing out, quite correctly, that I cheated his journal of a point. His journal, in the issue checked, does include the email address of each author. I apologize for the missing point. Joachim also asked me to mention that, while the journal does not
require
the "alpha" citation style, it does strongly advise authors to use that style.
Review of Isomorphisms of Types:
Authors: League Christopher
Published: October 2004

The λ-calculus is an elegant computational model used
extensively in the formal semantics of programming languages. It
was first described by Alonzo Church in 1932, as a foundation of
mathematics based not on
sets,
but directly on
functions.
λ-calculus was, in part, the inspiration
for the programming language Lisp, and its typed versions have
become the foundation for a family of modern type-safe languages
that includes Haskell and ML.

In its original untyped form, the λ-calculus is an
extremely simple rewrite system with the concise syntax
e
::
x
|
e
1
e
2
|λ
x.e,
where
x
ranges over
variable names,
e
1
e
2
is called
an
application,
and λ
x.e
is called an
abstraction.
An abstraction is analogous to a
function;
x
is the
formal parameter
and
e
is the
body.
Effectively, there is just one rewrite rule, called
β-reduction: (λ
x.e
1
)
e
2
→β
e
1
[
e
2/
x
], where
e
1
[
e
2
/
x
] means that we
substitute e
2
for occurrences of
x
in the
expression
e
1
Voilà---Turing
equivalence.

Actually, there are a few technicalities we are glossing over,
having to do with renaming bound variables and such. And in modern
usage we generally augment the system with natural numbers,
arithmetic, and boolean logic as primitives, although these can be
completely encoded in the raw calculus.

This book is about
types
(a familiar notion in both
mathematical logic and programming languages) and a family of
typed
λ-
calculi.
Armed with these formalisms,
Di Cosmo explores various
isomorphisms
of types, which then
prove useful in building a software engineering tool to classify
and retrieve software components! Specifically,

" Chapters 1-3 present a quick introduction to the various typed
λ-calculi, sketch some isomorphisms, and then prove
important results about confluence, decidability, and
normalization.

" Chapters 4-5 contain the meat of the theoretical contribution
of this work, presenting complete theories for first- and
second-order isomorphic types.

" Chapters 6-7 demonstrate the utility of these isomorphisms in
a software engineering application, and sketch other potential
applications and extensions.
Adaptive parallelism
Authors: Ledru Pascal
Published: October 2004

For years, scientists have dreamed of software programs that, given a very large task, could borrow any kind and number of unused machines available and speed up the job by distributing it around. The need to support some form of adaptive parallelism (AP) is the main property of these programs. As a program may temporarily access machines when their owners do not use them, it is also necessary to return these machines when their owners begin to work again. And as the number of machines allocated to a program expand and contract during its execution, adaptive parallelism allows the program to adjust to this dynamically changing set of machines. For example, a program can start on ten machines, then temporarily use twenty, and finish on five. Numerous projects have attempted to develop such programs. Initial attempts have been undertaken on Local Area Networks (LAN). Most recently, due mainly to the Java language and platform which solve problems such as security, heterogeneity, and portability, several attempts have targeted the Internet. This paper gives a brief overview of some AP systems. Then presents a prototype of an AP system, called ObjectSpace, based on Java Remote Method Invocation (RMI).
BFXM
Authors: Li Qun , Jing Jie , Xie Li
Published: October 2004

This paper proposes a parallel file system model under NOWs (network of workstations) environment. According to the features of NOWs, the system incorporates the mechanism of distributed shared memory, particularly the mechanism of COMA (cache only memory access). It links the memory of all nodes into a large cache; each node aggressively uses not only the local memory but also the remote memory of other nodes, which expedites the data accesses dramatically. It also accesses disks in parallel to improve I/O performance. Furthermore, in our model, data are shared naturally and conveniently among nodes as opposed to the traditional parallel file systems. The architecture of the parallel file system and its detailed implementation, such as file read and write, data replacement, file data dissipation, parallel file read and write are presented in this paper.
An interaction of coherence protocols and memory consistency models in DSM systems
Authors: Shi Weisong , Hu Weiwu , Tang Zhimin
Published: October 2004

Coherence protocols and memory consistency models are two improtant issues in hardware coherent shared memory multiprocessors and softare distributed shared memory(DSM) systems. Over the years, many researchers have made extensive study on these two issues repectively. However, the interaction between them has not been studied in the literature. In this paper, we study the coherence protocols and memory consistency models used by hardware and software DSM systems in detail. Based on our analysis, we draw a general definition for memory consistency model, i.e., memory consistency model is the logical sum of the ordering of events in each processor and coherence protocol. We also point that in hardware DSM system the emphasis of memory consistency model is relaxing the restriction of event ordering, while in software DSM system, memory consistency model focuses mainly on relaxing coherence protocol. Taking Lazy Release Consistency(LRC) as an example, we analyze the relationship between coherence protocols and memory consistency models in software DSM systems, and find that whether the advantages of LRC can be exploited or not depends greatly on it's corresponding protocol. We draw the conclusion that the more relaxed consistency model is, the more relaxed coherence protocol needed to support it. This conclusion is very useful when we design a new consistency model. Furthermore, we make some improvements on traditional multiple writer protocol, and as far as we aware, we describe the complex state transition for multiple writer protocol for the first time. In the end, we list the main research directions for memory consistency models in hardware and software DSM systems.
A new checkpoint mechanism for real time operating systems
Authors: Rodríquez Santiago , Pérez Antonio , Méndez Rafael
Published: October 2004

This paper presents an overview of a proposed protocol to provide application---transparent fault tolerant services in a Real Time Operating system. Fault tolerance is achieved by saving checkpoints of the processes belonging to a real time application. This approach proposes the extension of some real time system calls in order to save a recovery point when the user invokes them. This protocol allows a real time application designer to know the temporal specifications of every system call. Current real time applications are composed of several Real Time processes and they have to share data by using interprocess communication facilities provided by the operating system. The operating system has to take into account these interactions to ensure the consistency of checkpoints. This is done by tracking the communications performed since the last checkpoint and forcing dependent processes to perform a checkpoint at the same time.
On distribution of coordinated atomic actions
Authors: Romanovsky A. , Zorzo A. F.
Published: October 2004

The concept of coordinated atomic (CA) actions was introduced about two years ago. Since then this research has addressed many new problems and, in particular, problems of CA action distribution and implementation. Recently we have gained some experience in implementing different schemes in Ada 95 and Java. Our intention within this paper is to discuss how distributed CA action schemes can be realised. In particular, we outline different ways of action component distribution, trade-offs, applications for which these schemes are applicable. We discuss a wide range of schemes (some of them have not yet been implemented) based on a classification of various approaches to CA action distribution; to do this we analyse all possible ways of different action component distribution. We believe that this general discussion should help to better understand the current state of CA action implementation and is important for future research in CA actions.
Organizing UNIX directories as lattices
Authors: Ponder Carl
Published: October 2004

UNIX supports tree-structured directories. However, an alternative lattice-structure can be built within the UNIX conventions, using symbolic-links, shell functionality, and the semantics of the
ls
command. An extension of the ".." convention distinguishes between parent-directories.
Restricted tasking models
Authors: Burns A. , Wellings A. J.
Published: October 2004

High-integrity systems rarely make use of high-level language features such as Ada tasking. In this paper, simple language profiles (of Ada 95 concurrency features) are developed that are appropriate for various levels of integrity. A level-0 model (collection of Ada95 features) defines a minimal language profile and delivers deterministic (non-preemptive) behaviour. Scheduling is undertaken as part of the application and can thus be inspected and verified. Five other models are also presented that give different levels of expressive power. The motivation for this paper is to try and define models that would become de facto standards and that would be directly supported by kernel vendors and other tool suppliers.
Communication and distribution tools for embedded distributed applications
Authors: Dissaux Pierre , Pautet Laurent , Björnfot Lars , Kermarrec Yvon , LeCampion Dominique
Published: October 2004

This short paper describes one of our current activities around distribution and real-time systems. The work presented is still in progress and therefore technical issues and solutions might change. We are combining the various elements we shall describe in this paper and testing their integration. The interested reader will find a description of our work and our recent papers on our web pages: http://www-info.enstbretagne.fr/~kermarre and http://www.enst.fr/~pautet/.
Implementing robot controllers under real-time POSIX and Ada
Authors: González Harbour M. , Drake Moyano J. M. , Aldea Rivas M. , García Fernández J.
Published: October 2004

In this paper we present our experience in the development of real-time controllers for special robots, designed to perform maintenance operations in nuclear power plants. The evolution of computer hardware and software technology has made the requirements of the embedded robot controllers to also evolve. In addition to the usual concurrent software and real-time constraints, today our robots require advanced features such as network communications, file systems, and graphical user interfaces. To meet all these requirements we not only need a reliable concurrent programming language such as Ada, but we also need to use services provided by real-time operating systems. In this paper we want to present our successful experience in the development of robot controllers using the Ada language and a POSIX real-time operating system.
Benchmarking of hard real-time distributed systems with Ada 95
Authors: Ujvary Brian G. , Kamenoff Nick I. , Diaz-Herrera Jorge L.
Published: October 2004

This paper presents an approach for the implementation of the Hartstone Distributed Benchmark (HDB) for Hard Real-Time Distributed Systems with Ada 95. From the series of experiments as defined in the original HDB paper, six experiments have been implemented for the sender-receiver (two node) version of experiments.The main idea behind the HDB is the definition of a number of (host processor) tasks on each node, where these tasks exchange messages with corresponding tasks on the other nodes. The stopping criteria for each experiment is the missing of a message before the deadline of a receiving task. The variables in the HDB experiments are: the number of tasks sending and/or receiving messages, the number of messages sent and/or received per task period, the length of messages sent and/or received per task period, and the number of nodes participating in the experiments.From the real-time scheduling point of view, the HDB experiments integrate the host processor scheduling domain (tasks' priorities), the communication scheduling domain (messages' priorities) both located on each node, and the inter-nodes communication domain (priority ordering among physical nodes). The host domain in the presented experiments is implemented by using the Ada 95 Tasking System. For the implementation of the communication exchange of messages, the Ada 95 Remote Procedure Call is used. The Network Time Protocol is used to provide the global time synchronization as required by HDB.The paper presents the design solutions, the actual implementation for the two nodes version, and the analysis of the results obtained with the current testbed. Design considerations for the implementation of the HDB experiments in the multi-node version, problems which can arise by using the Ada 95 Remote Procedure Call, as well as suggested solutions, are discussed.The results of the implemented experiments show a high level of repeatability and stability of the testbed setting used.