bluuebunny/crossref_metadata_2025 huggingface dataset:
Improving round-trip time estimates in reliable transport protocols
Authors: Karn P. , Partridge C.
Published: October 2004

As a reliable, end-to-end transport protocol, the ARPA Transmission Control Protocol (TCP) uses positive acknowledgements and retransmission to guarantee delivery. TCP implementations are expected to measure and adapt to changing network propagation delays so that its retransmission behavior balances user throughput and network efficiency. However, TCP suffers from a problem we call
retransmission ambiguity
: when an acknowledgement arrives for a segment that has been retransmitted, there is no indication which transmission is being acknowledged. Many existing TCP implementations do not handle this problem correctly.

This paper reviews the various approaches to retransmission and presents a novel and effective approach to the retransmission ambiguity problem.
Internet protocol implementation experiences in PC-NFS
Authors: Arnold G.
Published: October 2004

A team at Sun Microsystems East Coast Division has been engaged in developing and supporting a PC implementation of Sun's Network File System (NFS™) protocols. In the course of this work we were faced with the problem of implementing Internet protocol software within the PC environment. Our experiences revealed that there are some unique obstacles to be overcome in this kind of system, and indicate that further work is needed in the development of protocols to manage networks of low-end machines.
Researches in network development of JUNET
Authors: Murai J. , Kato A.
Published: October 2004

JUNET was developed in order to provide a testing environment for studies of computer networking and distributed processing by connecting a large number of computers and by providing actual services for the users. Research interests in development of the network have been focused on resource name managing, Japanese character handling and communication technologies.

For the name managements, the hierarchical domain concept is employed to construct a name space for the network, and a mechanism for text message exchange is implemented using the concept. An environment for text message exchange using Japanese characters is achieved as results of general discussions to handle 16-bit Kanji codes in computers. Efficient data transmissions with the high speed modems are achieved by a new UUCP protocol and the dial-up IP link mechanism developed with a tty driver which provides host-to-modem flow control mechanism.

As the result of researches described above, JUNET currently connects various types of organizations relating computer science which are 87 organizations with more than 250 computers in number. It connects universities and major research laboratories in Japan, and the protocols currently used are TCP/IP over leased lines as well as dial-up lines, and UUCP over dial-up lines. The services such as electronic mail and network news have been provided since the network was started, and special technologies for Japanese character handling, name servers, and multimedia mail supports have been developed.

In this paper, the current status of JUNET and its research results in development of the network are described.
A verified connection management protocol for the transport layer
Authors: Murphy S. L. , Shankar A. U.
Published: October 2004

We specify and verify a connection management protocol for use between entities connected by channels that can lose, reorder, and duplicate messages. The protocol is symmetric. Each entity is in one of the following states: closed, listen, open, active opening, passive opening, or closing. The first three are stable states to be exited only by user request, while the last three are transient states. Each entity maintains a local incarnation number at all times, and a remote incarnation number only when opening, open, and closing. Our protocol employs the 3-way handshake used in TCP and ISO Transport Protocol (Class 4).

We verify the safety property that when an entity is open, its remote incarnation number matches the remote entity's local incarnation number. This ensures that data messages from past connection instances are not delivered to the user. We verify the following progress properties: an actively opening entity will eventually establish a connection, provided that the remote entity is willing to communicate or is itself actively opening; the states of active opening, passive opening, and closing are transient; if the entities remain closed, the channels will eventually become empty, assuming messages have a maximum lifetime.

This protocol specification can be immediately combined with the data transfer protocol specifications presented in [SHAN1, SHAN2, SHAN3] to provide a transport layer protocol with the functions of connection management and two-way data transfer. The verifications too can be immediately combined to provide a hierarchical verification of the multi-function protocol. The specifications and verifications can be combined because the connection management and data transfer protocols are images of the multi-function protocol. This illustrates the power of protocol projections in constructing multi-function protocols.
New communication protocols from old
Authors: Bavel Z. , Gfrzymala-Busse J. W. , Hsia Y-T.
Published: October 2004

The power tier automaton (PTA) is introduced as a model of preference for representing and manipulating systems in general, computer architectures and, in particular, communication networks and their protocols. The PTA is superior to Petri nets, both in computing power (Turing machine power) and in ease and selectivity of representation. The tier automaton, a species of the PTA, is used to represent networks and protocols to a greater advantage than other existing models. Homomorphisms and reachable-domain (r.d.) homomorphisms on tier automata are introduced and used to
manipulate
two distinct protocols for reliable full-duplex transmission over half-duplex lines, both of whose images are the same familiar alternating-bit protocol.
The NSFNET backbone network
Authors: Mills D. L. , Braun H.
Published: October 2004

The NSFNET Backbone Network interconnects six supercomputer sites, several regional networks and ARPANET. It supports the DARPA Internet protocol suite and DCN subnet protocols, which provide delay-based routing and very accurate time-synchronization services. This paper describes the design and implementation of this network, with special emphasis on robustness issues and congestion-control mechanisms.
Extensions to communicating sequential processes to allow protocol performance specification
Authors: Zic J. J.
Published: October 2004

Formalisms based on Hoare's Communicating Sequential Processes (CSP) and Milner's Calculus of Communicating Systems (CCS) for verifying protocols are currently being used by the International Standard Organisation (ISO). However, these models need to be extended if protocol performance specification and verification is to be done, as neither of these models have timing information (other than sequencing) nor a way of specifying controlled loss of information.

This paper presents two extensions to Hoare's CSP that are felt by the author to provide suitable mechanisms for specifying protocol performance. Firstly, the effects of introducing time into CSP are presented, based on the work done by Reed and Roscoe. Secondly, the traces model is modified by associating probabilities with event sequences.

Finally, some example specifications are given using these two extensions.
A yellow-pages service for a local-area network
Authors: Peterson L. L.
Published: October 2004

We introduce a yellow-pages service that maps service names into server addresses. The service is novel in that it associates a set of attributes with each server. Clients specify the attributes the server should possess when requesting a service and the yellow-pages service determines what servers satisfy the request. In addition to describing the implementation of the yellow-pages service within a local-area network, we show how the service can be integrated with the available internet communication protocols to enable clients from throughout the internet to access local servers.
Resource management in a distributed internetwork environment
Authors: Skinner G. , Wrabetz J. M. , Schreir Louis
Published: October 2004

The resource management system is designed to support location-transparent access to resources and to improve performance in a distributed internetwork environment. In this environment, access to one of several machines that have a given resource is determined by the effective bandwidth and reliability of internetwork communications, the ability to interact with the machines offering the resources, and the load on those machines. Using these criteria, the resources management system enables applications to determine and obtain access to the “best” copy of a resource. Should the resource become unavailable from one machine, the resource management system can dynamically direct the applications to another machine known to offer the same resource. This paper discusses some of the problems that motivated the design, an implementation for a UNIX workstation environment, and future directions for the resource management system
.
Laboratory for emulation and study of integrated and coordinated media communication
Authors: Ludwig L. F. , Dunn D. F.
Published: October 2004

In future telecommunications networks, understanding the issues of user-network control, Customer Premise Equipment (CPE) technologies, services and user applications is as important as the classical network problems of channel structure, switching, and transmission. This paper discusses a Bell Communications Research facility, the Integrated Media Architecture Laboratory (IMAL), designed to flexibly emulate a wide range of current and future network and CPE environments with a focus on multiple media communications. IMAL combines off-the-shelf technologies to create an easily clonable emulation environment for studying, planning, demonstrating, and checking the feasibility of integrated media communications.

The IMAL project has assembled workstations which feature speech-synthesis/sampled-audio/telephony capabilities, local 1 MIP computation capacity, and a high-resolution color display integrating text/graphics/image/video under an expanded X Window display management system. (X Windows is an emerging windowing standard to provide high performance device-independent graphics.) The workstations may be augmented as needed by local image digitizers, video cameras, and color image printers producing paper and viewgraph hardcopies. Also, the workstations are interconnected with switches permitting access to one another as well as shared databases, temporary storage, intelligence, and information processing/conversion resources. Communications services are implemented under a distributed, real-time service primitive control scheme. This multiple-media service primitives scheme employs a threaded/dataflow-type architecture to support user-defined, network-defined, and vendor-defined services while including a wealth of flexible features for the study of network architecture, protocol, network management, and billing functions.
Telescience and advanced technologies
Authors: Leiner B. M.
Published: October 2004

Space Station and its associated laboratories, coupled with the availability of new computing and communications technologies, have the potential of significantly enhancing scientific research. Telescience involves the interaction of scientific researchers and equipment on earth with on-board personnel and equipment as well as with other researchers, remote ground-based resources, mission control personnel, and space station developers. To assure that this potential is met, scientists and managers associated with the Space Station project must gain significant experience with the use of these technologies for scientific research, and this experience must be fed into the development process for Space Station.

In this talk, a pilot program is described that is attempting to address this problem. University researchers are conducting rapid prototyping testbeds employing new telescience technologies and ideas. These testbeds are specific research experiments within the scientific discipline areas that will use Space Station laboratories. The experiments are being carried out in a coordinated manner to allow the critical questions to be answered by groups of scientists working with technologists in a rapid prototyping testbed environment.

The rapid prototyping testbeds are not like a typical testbed. Rather than being used to evaluate and integrate systems on the way to deployment, the rapid prototyping testbeds constitute a Technology Evaluation Environment (TEE), allowing users to interact with advanced technologies in the conduct of scientific research in order to develop the required base of experience to permit development and evaluation of requirements and specifications.
Models of a very large distributed database
Authors: Blakey M.
Published: October 2004

The problems inherent in managing a database distributed over a very large number of sites are considered. The applications of such databases to the provision of telecommunications and other public services are discussed. It is shown that the distribution and maintenance of the directory information describing object locations poses some fundamental problems. A new partially informed class of distributed databases is described which distributes the directory information on a “needs-to-know” basis. The class is described by models of the network topology, and by the knowledge available to each site. These proposals are sufficiently general to support the partitioning of data relations into distribution fragments, and for those fragments to be replicated at multiple sites.
A threaded/flow approach to reconfigurable distributed systems and service primitives architectures
Authors: Ludwig L. F.
Published: October 2004

This paper discusses a methodology for managing the assembly, control, and disassembly of large numbers of independent small-scale configurations within large-scale reconfigurable distributed systems. The approach is targeted at service primitives architectures for enhanced telecommunications networks, but can apply to more general settings such as multi-tasking supercomputers and network operations systems.
*
Study of the methods presented here was a key motivation in founding the Bell Communications Research
Integrated Media Architecture Laboratory (IMAL) [1]
.

The Threaded/Flow approach uses data-flow constructs to assemble higher level functions from other distributed functions and resources with arbitrary degrees of decentralization. Equivalence between
algorithms
and
hard and virtual resources
is accomplished via threaded-interpretive constructs. Function autonomy, concurrency, conditional branching, pipelining, and setup/execution interaction are implicitly supported. Some elementary performance comparisons are argued.

This work is motivated by telecommunications applications involving coordinated multiple-media in open architectures supporting large numbers of users and outside service vendors. In such networks it is desired that services may be flexibly constructed by the network, service vendors, or by users themselves from any meaningful combination of elementary primitives and previously defined services. Reliability, billing, call progress, real-time user control, and network management functions must be explicitly supported. These needs are handled with apparent high performance by the approach.
Resource management scheme in distributed environments
Authors: Nakamura O. , Saito N.
Published: October 2004

The user interface for distributed computing environment needs several kinds of transparency for resources which are distributed on many sites connected to the network. Access transparency and location transparency are general concept for distributed resources.

In distributed environment, there are many resources of the same functions in various sites. For example, cashed resources which are complete duplicated resources exist on many sites in order to realize high performance.

In this paper, the resource management scheme in the distributed environment is described. The sophisticated semantics transparency which is a general scheme for manipulating duplicated resources in distributed environment is provided. The specification language for the environment which provides semantics transparency is also discussed.
An Ethernet compatible low cost/high performance communication solution
Authors: Chlamtac I. , Herman A.
Published: October 2004

The LAN-HUB is a new local area network designed to combine the properties of several existing LAN standards to provide highly reliable communication at a relatively lower cost per station, improve network capacity/delay performance and increase the LAN user's flexibility in configuring his network. The LAN-HUB network is configured around the CODEX 4320 LAN-HUB communication controllers which allow up to eight Ethernet/IEEE 802.3 stations to transparently share one network transceiver or RF Modem. Each LAN-HUB controller executes a fair, collision free, arbitration among its
local
stations attached to its LAN ports, using a patented collision avoidance algorithm. The HUB's rear panel further provides a Network port which can be attached to a standard 802.3 transceiver, to another HUB or terminated in a loop back mode. The HUBs, thus, allow stations to be organized in a standalone star network, in a “cascading” star configuration, or as an integrated bus/star network. When organized as star or cascaded star networks, the HUB controllers provide highly reliable and controlled, collision free, bandwidth allocation suitable for applications such as CPU room clusters. Alternately, in a bus configuration the HUBs support an Ethernet type bus network, with random access channel control. In the latter configuration the HUBs provide a lower cost/higher performance solution for bursty traffic users, since they reduce cabling requirements, decrease cost by sharing each transceiver among several LAN stations and improve network throughput/delay performance by eliminating local collisions. The LAN-HUB is thus effective in creating a local communication solution with a significant degree of flexibility in choosing the network layout and the type of service, random or deterministic, provided to the network users.
A case for packet switching in high-performance wide-area networks
Authors: Haas Z. , Cheriton D. R.
Published: October 2004

The large capacity of optical fibers suggests that circuit-switching may become a more attractive switching method in future communication networks. We show, however, that under some reasonable assumptions the delays associated with circuit-switching make the technique inferior to packet-switching in a high-performance, distributed environment. A network design that demonstrates the feasibility of packet-switching in high-performance environment is also presented.

This work was sponsored in part by the Defense Advanced Research Projects Agency under contract N00039-86-K-0431, by the Digital Equipment Corporation, by ATT Information Systems and by Bell Northern Research.
Synchronization: Introduction by the session chairman
Authors: Lampson Butler
Published: October 2004

The discussion at this session centered around two aspects of the synchronization problem: abstract models, primarily of local synchronization; and synchronization in networks which have long delays, lost messages, duplication of messages, and crashes of the communicating parties. There were two presentations on abstract models (Belpaire and Chen) and one on network problems (Dalal), supported by several working papers for which there were no presentations during the session (Ekanadham, Akkoyunlu, Tomlinson).
Selecting sequence numbers
Authors: Tomlinson Raymond S.
Published: October 2004

This paper discusses techniques for selecting and synchronizing sequence numbers such that no errors will occur if certain network characteristics can be bounded and if adequate data error detection measures are taken. The discussion specifically focuses on the protocol described by Cerf and Kahn, (1) but the ideas are applicable to other similar protocols.
More on selecting sequence numbers
Authors: Dalal Yogen K.
Published: October 2004

This note serves to supplement and extend the ideas and issues raised in [TO74]. Tomlinson examines the problem of establishing a connection (association), and being able to detect delayed packets of an old incarnation of a connection, when it is being opened and closed in quick succesion, or when the connection breaks owing to some crash and is restarted later. No protocol can guarantee reliability of communication given certain types of crashes [SU74], [BE74]. This last issue is out of the scope of this note.

First the problem of establishing and closing a connection is further examined and the claim that a three way exchange is sufficient for single message transfer in [TO74] (even under conditions of a correctly functioning system) is refuted. Next the mechanism for implementing the “clock-driven” initial sequence number choice is examined in detail showing how various parameters interact, and the algorithms neccessary in order that it work. Finally alternative schemes to replace “resynchronization” are considered and the tradeoffs shown.
Representation of process synchronization
Authors: Chen Robert C.
Published: October 2004

There is presently no natural, convenient way to represent synchronization between communicating processes. Two dimensional graph models seem to offer the most natural representations, and of these the Petri net is perhaps the most basic. The author has been working on graph models similar to Petri nets, stressing the ease and convenience of the model as a descriptive device rather than attempting to prove properties such as liveness and safeness. It is shown that Petri nets are incapable of representing some simple and interesting synchronization problems such as reader-writer problems. Recent work has been directed towards the identification of modifications to graph models to overcome such dificiencies.
Formalisms for interprocess communication
Authors: Cerf Vinton
Published: October 2004

The literature is rich in examples of a variety of interprocess communication methods, some of which can be considered simple line control procedures (half duplex, full duplex, polled, etc.) and others which are more elaborate and deal with reordering, duplicate detection, stochastic delays, and so on.

Among the most poorly worked out areas of interprocess communication is a formal representation which permits proofs to be made of correct behavior under all circumstances. Some necessary conditions for correct behavior have been proposed in the papers in this Proceedings.
On data secure computer networks
Authors: Popek Gerald J.
Published: October 2004

Recent research activities concerned with computer network security have produced a number of proposals for secure network designs. If one considers only the data security problem, and a network's contribution to it, then the recent progress suggests that reasonable solutions will soon be available. These solutions will be economical and merge reasonably well with existing network practices.
Interprocess communication systems
Authors: Chen T. C.
Published: October 2004

This session dealt with distributed systems with proven “existence theorems”; their communications mechanisms must be a compromise between idealism and workability.

During the session Vic Lesser raised the question whether complex systems are necessarily hierarchical. This is the contention of the General System Theory school, out of which many books have appeared, the most accessible being
Beyond Reductionism
edited by A. Koestler and J.R. Smythies (Beacon Press, Boston, 1975).

Another discussion concerns the question of simultaneity in large systems.
Segment transfer protocols for a homogeneous computer network
Authors: Manning Eric , Peebles R. W.
Published: October 2004

This research is focussed on solving certain problems of distributed processing on a distributed data base, with emphasis on transaction processing. Many data bases exhibit
geographic locality of reference
; most of the transactions homing on a given component of the data base originate from a particular geographic region. At the same time there is a need to operate the collection of components as a single data base, to provide For occasional transactions which cross regional boundaries, and For managerial queries and information retrieval applications which span the entire data base. There are many examples of this associated with business and Industry; credit and inventory records for example. Finally, geographic locality of reference is only one of the reasons for creating logically unified but physically distributed data bases. If a data base contains information supplied by several agencies, each may Insist as a matter of policy that 'its' data be held in 'its' hardware located on 'its' premises, quite apart From technical efficiencies which may accrue.
On the efficiency of control procedures for computer communication networks
Authors: Opderbeck Holger
Published: October 2004

The last decade has seen an explosive growth in the area of computer communications and, in particular, computer networking. Similar to the early stages of the development of time sharing systems, the first studies in this new area concentrated on demonstrating the feasibility and building a theoretical foundation [CHU 69, DAVI 68, SCAN 68, HEAR 70, FRAN 70, KLEI 70, CARR 70]. While many theoretical questions remain unresolved [CHOU 74, KLEI 74a, OPDE 74a], the feasibility of these systems has clearly been established. The interest has recently shifted toward
efficient
and
secure
implementations of computer communication systems. In this paper we will comment on the efficiency of control procedures and report on the experience which we have gained with the operation of the ARPANET.
SIGACT news complexity theory column 36
Authors: Hemaspaandra Lane A.
Published: October 2004

This current issue's guest column is by Bill Gasarch, and reports on a poll he has conducted on the most famous open question in complexity theory: P=?NP. If Mitsunori Ogihara's prediction that P-vs-NP will not be resolved until the year 3000 is correct, my guess is more than a few students of the history of computer theory will be visiting, long after all the contributors are gone, Bill's column, which will provide a time capsule into the thoughts of many in the field. Who knows? Perhaps there will even be Ph.D. theses devoted to figuring out who these people all are, and just who the (as the students will know from their history of science books) then-Turing/Fields/Nobellaureate Bill Gasarch was making an exception of when he wrote below, "Almost all respondents are people whose opinions can be taken seriously," and great debates may rage over whether he actually meant, by "almost all," "all but a (large) constant number." In light of the fascinating opinions, though, I suspect that but little evidence will be found for that view---even by Ken Regan's Vegans. Surely some M.S. thesis will be written claiming that it was this column---and in particular the superfluous disjunct in Donald Knuth's claim that
x
≤ 2048 V
x
≤ 4096---that led, in the year 2
10
+ 2
11
, to Donald Knuth's Turing Award being posthumously rescinded and given to Bill Gasarch. However, the Knuth Cult will discover that Donald Knuth's words here are a numerical key that unlocks the secret of the Art of Computer Programming, which, it turns out, when decoded has nothing to do with computers but rather is a skillful telling of the life story of a Danish saint.Warmest thanks to Bill and the dozens of contributors for their time, analyses, and prognostications.Plugs for past and future issues: In 1996 and 1997, SIGACT News Complexity Theory Columns 14 and 15 collected various expert's opinions on the future of computational complexity. If you have not read those opinions already, they are worth a look. And coming in the next few issues we'll have Marcus Schaeffer and Chris Umans on completeness for higher polynomial hierarchy levels, Arfst Nickelsen and Till Tantau on partial information classes, and Ramamohan Paturi on the complexity of k-SAT.
Topology control and routing in ad hoc networks
Authors: Rajaraman Rajmohan
Published: October 2004

An ad hoc wireless network, or simply an
ad hoc network,
consists of a collection of geographically distributed nodes that communicate with one other over a wireless medium. An ad hoc network differs from cellular networks in that there is no wired infrastructure and the communication capabilities of the network are limited by the battery power of the network nodes. One of the original motivations for ad hoc networks is found in military applications. A classic example of ad hoc networking is network of war fighters and their mobile platforms in battlefields. Indeed, a wealth of early research in the area involved the development of packet-radio networks (PRNs) and survivable radio networks [16]. While military applications still dominate the research needs in ad hoc networking, the recent rapid advent of mobile telephony and plethora of personal digital assistants has brought to the fore a number of potential commercial applications of ad hoc networks. Examples are disaster relief, conferencing, home networking, sensor networks, personal area networks, and embedded computing applications [37].The lack of a fixed infrastructure in ad hoc networks implies that any computation on the network needs to be carried out in a decentralized manner. Thus, many of the important problems in ad hoc networking can be formulated as problems in distributed computing. However, there are certain characteristics of ad hoc networks that makes this study somewhat different than traditional work in distributed computing. In this article, we review some of the characteristic features of ad hoc networks, formulate problems and survey research work done in the area. We focus on two basic problem domains:
topology control,
the problem of computing and maintaining a connected topology among the network nodes, and
routing.
This article is not intended to be a comprehensive survey on ad hoc networking. The choice of the problems discussed in this article are somewhat biased by the research interests of the author.The remainder of this article is organized as follows. In Section 2, we describe various aspects relevant to modeling ad hoc networks. In Section 3, we discuss topology control. Since the nodes of an ad hoc network are often associated with points in 2-dimensional space, topology control is closely tied to computational geometry; we will briefly review this relationship and extant work in the area. In Section 4, we discuss routing protocols for ad hoc networks. After a brief overview of the many protocols that have been proposed, we discuss alternative approaches based on the adversarial network model.
Integrating object-oriented programming and protected objects in Ada 95
Authors: Wellings A. J. , Johnson B. , Sanden B. , Kienzle J. , Wolf T. , Michell S.
Published: October 2004

Integrating concurrent and object-oriented programming has been an active research topic since the late 1980's. There is now a plethora of methods for achieving this integration. The majority of approaches have taken a sequential object-oriented language and made it concurrent. A few approaches have taken a concurrent language and made it object-oriented. The most important of this latter class is the Ada 95 language, which is an extension to the object-based concurrent programming language Ada 83. Arguably, Ada 95 does not fully integrate its models of concurrency and object-oriented programming. For example, neither tasks nor protected objects are extensible. This article discusses ways in which protected objects can be made more extensible.
Context sensitivity in role-based access control
Authors: Kumar Arun , Karnik Neeran , Chafle Girish
Published: October 2004

This paper describes an extended role-based access control (RBAC) model, which makes RBAC sensitive to the
context
of an attempted operation. Traditional RBAC does not specify whether the permissions associated with a role enable access to a
particular
object, or to some
subset
of objects belonging to a class. We extend the model by introducing the notions of role context and context filters. Context filters are Boolean expressions based on the context of the user attempting the operation, as well as the context of the object upon which the operation is attempted. By supplying context filters during the definition of a role, a security administrator can easily limit the applicability of users' role memberships to particular subsets of the target objects. We also describe our implementation of the model in a web-services platform, to illustrate how this technique is particularly valuable when the data is hierarchically structured.
Review of
Data Structures and Algorithms in Java (2nd ed)
Authors: Masum Hassan
Published: October 2004

Data Structures
is a first book on algorithms and data structures, using an object- oriented approach. The target audience for the book is a second-year CS class introducing fundamental data structures and their associated algorithms. This second edition of the book has been corrected and revised, and is a substantial improvement over the first edition. A companion web site contains useful ancillary tools, including an excellent set of slides.Despite several minor errors and some questionable stylistic choices, I found this version of the book to be well-written. The problem sets are large, interesting, and thought-stimulating. In several places connections are drawn between the algorithm being discussed and important contemporary real-world problems (e.g. search engines, DNA sequence comparison, garbage collection), which students usually appreciate.
Review of
How to Solve It: Modern Heuristics
Authors: Masum Hassan
Published: October 2004

How to Solve It
is a friendly gem of a book which introduces the basic principles of traditional optimization, evolutionary optimization, neural nets, and fuzzy methods. In the spirit of Polya's classic of the same name, the authors emphasize the "how and why" of the problem-solving process, constantly prodding the reader to stop and solve subproblems, or come up with new heuristics, or indeed question whether or not the problem has been posed correctly in the first place.This book is clear, concise, and fun to read. It is not a handbook of heuristics, but rather an accessible high-level overview of the pros, cons, and applicability of the major categories of heuristic methods, with particular emphasis on optimization methods utilizing evolutionary computation. The presentation is lucid, and the authors do a good job of picking out key properties of algorithms and problem domains. The only prerequisites are basic mathematics and some problem-solving talent.
Computational geometry column 41
Authors: O'Rourke Joseph
Published: October 2004

The recent results that
n
congruent balls in ℝ

d

have at most 4 distinct geometric permutations is described.
An experimental assignment on random processes
Authors: Mitzenmacher Michael
Published: October 2004

Although I still generally use standard problem sets in my theory classes, I find myself experimenting more and more with alternatives, including more open-ended assignments. One big motivation for this change is to put some
science
back in my computer science class, by making assignments more like laboratory exercises in chemistry and biology: students have to experiment to find an answer. One of the great things about studying randomness is that the results sometimes lend themselves quite naturally to experimental assignments, as is the case for the assignment I describe here. Before going on, I will present the assignment.
Computational geometry column 35
Authors: O'Rourke Joseph
Published: October 2004

The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.
Endpoint admission control with delay variation measurements for QoS in IP networks
Authors: Bianchi G. , Borgonovo F. , Capone A. , Fratta L. , Petrioli C.
Published: October 2004

In this paper we describe a novel Endpoint Admission Control scheme (EAC) for IP telephony. EAC mechanisms are driven by independent measurements taken by the edge nodes on a flow of packets injected in the network to probe the source to destination path. Our scheme is characterized by two fundamental features. First, it does not rely on any additional procedure in internal network routers other than the capability to apply different service priorities to probing and data packets. Second, the connection admission decision is based on the analysis of the probing flow delay variation statistics. Simulation results, which focus on a IP telephony scenario, show that, despite the lack of core routers cooperation, toll-quality performance figures (99th delay percentiles not greater than few ms per router) can be obtained even in severe overload conditions. Finally, a comparison with an EAC scheme driven by probe losses only, shows that the use of delay variation statistics as endpoint decision criterion is a key factor for EAC effectiveness.
Retransmission schemes for streaming internet multimedia
Authors: Loguinov Dmitri , Radha Hayder
Published: October 2004

This paper presents a trace-driven simulation study of two classes of retransmission timeout (RTO) estimators in the context of real-time streaming over the Internet. We explore the viability of employing retransmission timeouts in NACK-based (i.e., rate-based) streaming applications to support multiple retransmission attempts per lost packet. The first part of our simulation is based on trace data collected during a number of real-time streaming tests between dialup clients in all 50 states in the U.S. (including 653 major U.S. cities) and a backbone video server. The second part of the study is based on streaming tests over DSL and ISDN access links. First, we define a generic performance measure for assessing the accuracy of hypothetical RTO estimators based on the samples of the round-trip delay (RTT) recorded in the trace data. Second, using this performance measure, we evaluate the class of TCP-like estimators and find the optimal estimator given our performance measure. Third, we introduce a new class of estimators based on delay jitter and show that they significantly outperform TCP-like estimators in NACK-based applications with
low-frequency
RTT sampling. Finally, we show that high-frequency sampling of the RTT completely changes the situation and makes the class of TCP-like estimators as accurate as the class of delay-jitter estimators.
Implementing exceptions in open multithreaded transactions based on Ada 95 exceptions
Authors: Kienzle Jörg , Romanovsky Alexander
Published: October 2004

This position paper shows how Ada 95 exceptions have been used in a prototype implementation of a transaction support in order to provide more elaborate exception handling. The paper summarizes the open multithreaded transaction model, which is a transaction model suitable for concurrent programming languages, reviews in detail its elaborate exception handling features, and analyzes the exception mechanism provided by the Ada 95 programming language. Different interfaces to the transaction support for the application programmer are presented, and the problems encountered during implementation of the prototype with respect to exception handling are discussed
Exception support for the ravenscar profile
Authors: Ruiz José , de la Puente Juan A. , Zamorano Juan , Fernández-Marina Ramón
Published: October 2004

The GNAT/ORK cross-compilation system was designed to support the Ravenscar profile semantics in a simple and efficient way. The implementation of the underlying kernel support for the exception handling was not difficult, but it raised two main issues. First, the handling of certain exceptions (namely task termination and elaboration) is undefined in the Ravenscar profile. Second, the kernel mechanism required to support Ada exceptions (using the GNAT runtime) is very simple if we do not adhere to the complex POSIX signal approach.
Omega
Authors: Liang Xianzhong , Wang Zhenyu
Published: October 2004

Ada provides full capacities of supporting object-orientation, but multiplex object patterns introduced by Ada are so complex that it is difficult for novices to master them. Investigating object patterns implemented by package, protected and task units, this paper presents a uniform object model (Omega), so as to simplify object-orientation with Ada. And exploiting Ada95's capacities, an approach of an Omega pre-processor is also made in confirmation of the model, which rationally hides from the complexity.
From the Chair
Authors: Sipior Janice C. , Schatzberg Laurie , Leidner Dorothy , Niederman Fred , Pendharkar Parag C.
Published: October 2004

The vote count for the proposed merger of SIGMIS and SIGCPR (Special Interest Group on Computer Personnel Research) has been completed. The merger received overwhelming approval. On behalf of SIGMIS, I would like to extend a warm welcome to the members of SIGCPR to SIGMIS. Thank you for your vote of approval for the merger!Please join me in welcoming Fred Niederman, past Chair of SIGCPR, as the newly appointed CPR Committee Chair for SIGMIS. Fred has graciously agreed to facilitate the strengthening of the bond between SIGMIS and SIGCPR.I would like to encourage everyone to strengthen the bond between these two groups by getting involved in the annual conference. The next conference is scheduled for April 2003 in Philadelphia, PA USA, with a broadened set of topics to include general areas of interest to the MIS community. Take my word for it, you will find springtime in Philadelphia is quite pleasant. Please plan to get involved!
SIGAda 2001 workshop, "creating a symbiotic relationship between XML and Ada"
Authors: Leif Robert C.
Published: October 2004

The purpose of the workshop was to organize the Ada community to take advantage of the opportunity to create Ada applications that are operating systems independent because they are based on a web technology, XML, Extensible Markup Language. The commercial use of the Internet is the driving force behind XML. Four elements of XML, which together are sufficient to build a web application, and all employ the same syntax were described. These are XML; its schema; the Extensible Stylesheet Language, XSL; and the XML mechanism for forms, XForms. XML concerns the data objects that are included on the web page and their order of presentation. The schema contains the information on the types and objects for XML. Schemas are roughly equivalent to an Ada specification without the subprograms.Fortunately, the programing language that has the best fit with XML is Ada. XML has visibility and scoping rules, which are similar to Ada. XML has strong typing and has single inheritance similar to Ada. A mutually beneficial symbiosis requires the creation of applications in Ada that use and support XML, as well as, the use of XML to create Ada environments including XML based tools. These applications include: automated translation of Ada data types and objects in a specification to an XML schema; and conversely, automated translation of the data types and elements in an XML Schema to an Ada specification.
A game-theoretic approach towards congestion control in communication networks
Authors: Garg Rahul , Kamra Abhinav , Khurana Varun
Published: October 2004

Most of the end-to-end congestion control schemes are "voluntary" in nature and critically depend on end-user cooperation. We show that in the presence of selfish users, all such schemes will inevitably lead to a congestion collapse. Router and switch mechanisms such as service disciplines and buffer management policies determine the sharing of resources during congestion. We show, using a game-theoretic approach, that all currently proposed mechanisms, either encourage the behaviour that leads to congestion or are oblivious to it.We propose a class of service disciplines called the Diminishing Weight Schedulers (DWS) that punish misbehaving users and reward congestion avoiding well behaved users. We also propose a sample service discipline called the Rate Inverse Scheduling (RIS) from the class of DWS schedulers. With DWS schedulers deployed in the network, max-min fair rates constitute a unique Nash and Stackelberg Equilibrium. We show that RIS solves the problems of excessive congestion due to unresponsive flows, aggressive versions of TCP, multiple parallel connections and is also fair to TCP.
A remote user authentication scheme using hash functions
Authors: Lee Cheng-Chi , Li Li-Hua , Hwang Min-Shiang
Published: October 2004

Recently, Peyravian and Zunic proposed a simple but efficient password authentication system. Their scheme is based on the collision-resistant hash function, such as SHA-1. Their scheme did not use any cryptosystems (such as DES, RSA, etc.). However, their scheme is vulnerable to guess attack. An attacker can easily obtain a user's password by guessing attack and then impersonate the user to login and access resources in the server. To overcome the vulnerability of their scheme, we propose an improved scheme to enhance security of their scheme in this article.
Pipeline
Authors: YAO Nian-Min , ZHENG Ming-Yang , JU Jiu-Bin
Published: October 2004

Architectures of existing Web servers are analyzed in this paper. A new taxonomy of the architectures of servers and a kind of new architecture (pipeline) are given. We also present an implementation and performance evaluation of a pipeline server prototype for concept proven. The results indicate that the pipeline servers can have high performance.
Experiences report on the implementation of EPTs for GNAT
Authors: García Rodrigo García , Strohmeier Alfred
Published: October 2004

Extensible Protected Types were devised to integrate concurrent and object-oriented features of Ada 95. This paper reports on a feasibility study based on implementing Extensible Protected Types for the GNAT compiler.
Practical implementations of embedded software using the Ravenscar Profile
Authors: Michell Stephen
Published: October 2004

There is significant industry interest in the use of the Ravenscar Tasking profile for high performance and high integrity systems. This paper takes one such design paradigm, the single writer and multiple readers problem, shows why it is difficult to implement using Ravenscar, and provides an effective Ravenscar implementation.