bluuebunny/crossref_metadata_2025 huggingface dataset:
A network management language for OSI networks
Authors: Warrier U. , Relan P. , Berry O. , Bannister J.
Published: October 2004

Managing the communications resources of a computer network is critical to the successful operation of the network. A network management system is expected to manage a large collection of network nodes remotely. There is an obvious need for sophisticated network management application software in this process. Previous network management systems have been designed without particular regard for the application programmer's interface requirements. We propose that such software be written in a specialized Network Management Language (NML) that provides the programmer with high-level abstractions rather than low-level communication primitives. The NML would help reduce development costs, promote portability and accommodate multiple standards. We propose an NML which is an extension to the SQL database standard. An implementation of the NML within the Open Systems Interconnection (OSI) systems management framework is discussed, and examples of its functionality and expressiveness are presented.
The design philosophy of the DARPA internet protocols
Authors: Clark D.
Published: October 2004

The Internet protocol suite, TCP/IP, was first proposed fifteen years ago. It was developed by the Defense Advanced Research Projects Agency (DARPA), and has been used widely in military and commercial systems. While there have been papers and specifications that describe how the protocols work, it is sometimes difficult to deduce from these why the protocol is as it is. For example, the Internet protocol is based on a connectionless or datagram mode of service. The motivation for this has been greatly misunderstood. This paper attempts to capture some of the early reasoning which shaped the Internet protocols.
Development of the domain name system
Authors: Mockapetris P. , Dunlap K. J.
Published: October 2004

The Domain Name System (DNS) provides name service for the DARPA Internet. It is one of the largest name services in operation today, serves a highly diverse community of hosts, users, and networks, and uses a unique combination of hierarchies, caching, and datagram access.

This paper examines the ideas behind the initial design of the DNS in 1983, discusses the evolution of these ideas into the current implementations and usages, notes conspicuous surprises, successes and shortcomings, and attempts to predict its future evolution.
A mesh/token ring hybrid-architecture LAN
Authors: Kang C. , Herzog J.
Published: October 2004

This paper presents a hybrid architecture for local area networks (LANs) which combines the advantages of token ring and mesh networks while remaining relatively simple. Each node may have two communication channels. The first is a token ring and is used for short or prioritized message data transmissions. The other consists of an arbitrary collection of data links, which are used for relatively high volume and low priority data messages. With this architecture, a LAN can be installed in the form of token ring and can be upgraded and “tuned” to its application environment by the insertion of node-to-node data links.

Simulation results indicate that even with rather simple network control and routing algorithms, performance is improved over token ring due to data transmission concurrency greater than one.
Tree LANs with collision avoidance: protocol, switch architecture, and simulated performance
Authors: Suda T. , Morris S. , Nguyen T.
Published: October 2004

Packet collisions and their resolution create a performance bottleneck in random access LANs. A hardware solution to this problem is to use collision avoidance switches. These switches allow the implementation of random access protocols without the penalty of collisions among packets. We describe the designs of some tree LANs that use collision avoidance switches. The collision avoidance LANs we describe are broadcast star and CAMB tree (Collision Avoidance Multiple Broadcast tree). We next present a possible implementation of a collision avoidance switch using currently available photonic devices. Finally, we show the performance of broadcast star and CAMB tree networks using simulations.
The VMP network adapter board (NAB): high-performance network communication for multiprocessors
Authors: Kanakia H. , Cheriton D.
Published: October 2004

High performance computer communication between multiprocessor nodes requires significant improvements over conventional host-to-network adapters. Current host-to-network adapter interfaces impose excessive processing, system bus and interrupt overhead on a multiprocessor host. Current network adapters are either limited in function, wasting key host resources such as the system bus and the processors, or else intelligent but too slow, because of complex transport protocols and because of an inadequate internal memory architecture. Conventional transport protocols are too complex for hardware implementation and too slow without it.

In this paper, we describe the design of a network adapter board for the VMP multiprocessor machine that addresses these issues. The adapter uses a host interface that is designed for minimal latency, minimal interrupt processing overhead and minimal system bus and memory access overhead. The network adapter itself has a novel internal memory and processing architecture that implements some of the key performance-critical transport layer functions in hardware. This design is integrated with VMTP, a new transport protocol specifically designed for efficient implementation on an intelligent high-performance network adapter. Although targeted for the VMP system, the design is applicable to other multiprocessors as well as uni-processors.
Circuit switching in multi-hop lightwave networks
Authors: Chlamtac I. , Ganz A. , Karmi G.
Published: October 2004

Emerging high speed networks are using optical fibers employing time division synchronous communication. In these systems the use of optical switching is strongly advocated due to the bottleneck created by store and forward in electronic components. Switching solutions geared toward optical systems have been proposed so far only for packet switching networks.

This paper introduces a new circuit switching approach for the emerging time division controlled fiber optic networks based on the requirement to avoid store and forward at intermediate nodes. The approach, termed Fast Circuit Switching (FCS), is unique in several operational and performance aspects. In terms of the way time slots within each cycle are allocated, a circuit is guaranteed a transmission slot immediately upon arrival at every intermediate node. As a result, the proposed Fast Circuit Switching (FCS) can be implemented by pure optical switches. In terms of performance, FCS guarantees minimum data transmission delays, consisting only of the end to end propagation delay in the network. Lastly due to being based on fixed time allocation at intermediate nodes, the FCS controlled system is purely end to end controlled. These properties make FCS inherently suitable for efficiently implementing circuit switching in wide area fiber optic networks, particularly, for supporting real time communications.

The realization of slot assignments, which support the FCS solution, entails a novel graph oriented algorithmic approach. Several new algorithms for allocating circuits according to FCS are presented, dealing with fixed, as well as dynamic, circuit management. It is shown that, while providing unique operational and performance advantages as discussed above, the FCS is also bandwidth efficient, requiring only system bandwidth similar to conventional circuit switching methodologies.
Performance models for Noahnet
Authors: Parulkar G. M. , Sethi A. S. , Farber D. J.
Published: October 2004

Noahnet is an experimental flood local area network with features such as high reliability and high performance. Noahnet uses a randomly connected graph topology with four to five interconnections per node and a flooding protocol to route messages.

The purpose of this paper is to present two analytical performance models which we have designed to understand the load-throughput behavior of Noahnet. Both models assume slotted Noahnet operation and also assume that if
k
messages attempt transmission in a slot, the network gets divided into
k
partitions of arbitrary sizes - one partition for each message. First, we show that the average number of successful messages in a slot given
k
partitions of transmissions is (
M
-
k
)/(
N
- 1), where N is the number of nodes in the network and M is the number of nodes out of N that participate in the flooding of
k
messages. This is an interesting result and is used in both models to derive the load-throughput equations.

Each model is then presented using a set of assumptions, derivations of load-throughput equations, a set of plots, and the discussion of results. Models one and two differ in the way they account for retransmissions.
Specification and verification of collusion-free broadcast networks
Authors: Jain P. , Lam S. S.
Published: October 2004

For high-speed local area networks that offer integrated services for data, voice, and image traffic, a class of demand-assigned multiple-access protocols have been presented in the literature. These protocols exploit the directionality of signal propagation and enforce time constraints to achieve collision-freedom. A correct implementation of such a protocol requires a careful analysis of time-dependent interactions of event occurrences using a formal method. To date, most protocol verification methods are intended for the analysis of asynchronous communication over point-to-point channels.

We present a model for broadcast bus networks. The novel features of our model include the ability to specify broadcast channels and the specification of real-time behavior. The broadcast characteristics of cables or buses are captured by some simple axioms. Real time is modeled as a discrete quantity using clocks and time variables. Real-time properties are specified by safety assertions. To illustrate our model and analysis method, we present a specification of the Expressnet protocol. We found that to achieve collision-freedom, a small modification to the original Expressnet protocol is needed.
Some limitations of adjacency matrices in computer network analysis
Authors: Witzke E. L/ , Frese S. D.
Published: October 2004

Adjacency matrices have been used to analyze problems with communications in organizations. Although this same approach can be applied to computer communication networks to determine their connectivity, it does have its limitations. This analysis method and its limitations will be discussed in this paper.
ICE: information center expert: a consultation system for resource allocation
Authors: Heltne Mari M. , Vinze Ajay S. , Konsynski Benn R. , Nunamaker Jay F.
Published: October 2004

This paper demonstrates the viability of a rule-based consultation system as a mechanism for effective resource management through integration of knowledge about users, business problems, and resources. The specific domain within which the expert system will be tested is the Information Center (IC), which deals with end-user computing resources. In the last decade, the information center concept has been proposed repeatedly as an organizational solution to resource management problems related to end user computing. The research hypothesis is that the knowledge and methodologies of IC consultants, as well as institutional policies, can be represented in a knowledge base. The system will then draw conclusions about appropriate software or training solutions based on the interaction of user and resource profiles with the problem definition. The output of the model should be identical to the situation which it is modeling.Currently, a rule-based ES is being developed at the University of Arizona Department of Management Information Systems. This paper will present methodologies for design and implementation of the system. The development approach for the IC environment is unique as compared to expert system development as discussed in the literature. First, the use of prototyping has been stressed for expert system development with the view of using it as a throw-away system. The prototyping of an ES for the IC environment, however, has to take into account the difference between two aspects of a prototype: user interface (dialogue) and system structures (knowledge representation, inferencing techniques). There needs to be iteration of the prototype until the user if comfortable with the dialogue. The prototype will be used to extract more knowledge form the experts as well as for enhancing user dialogue. The system structures will be changed only when the user dialogue has been settled.Second, because of changes in tool availability, resulting in a need for new descriptions of the tools available, the design of an expert system for ICs has to respond dynamically to unique flexibility, portability, and maintenance issues. The ability to transport such a system to similar, but not identical, ICs should be addressed in the design as well.An IC has been described as an organization specifically designed to produce guided services to help end users help themselves. A consultation expert system might be useful in reaching that goal.
Software configuration—an NP-complete problem
Authors: Calabaugh Jerry
Published: October 2004

Configuration Control File (CCF) production is very complex, thousands of code packages, data blocks and parameter values must be linked under many constraints including:*Common data and code less than 8192 bytes*Maximum of 5 registers per task*All systems data must have common capabilitiesNP-complete problems are commonly known as knapsack or bin packing problems. They have no known algorithm which solves them in a time period bounded by a polynominal function of the number of inputs. Rules-of-thumb, or heuristics are the only practical approach to their solution. CCF segmentation to meet constraints discussed above is an example of Expert System technology applied to a classic NP-complete problem.Heuristics developed with traditional data processing techniques initially performed satisfactorily. However, as program development proceeded, Central Processor Unit (CPU) time for (CCF) production became a concern, both from a commitment of CPU resources and lost productivity. Traditional techniques failed to improve the heuristics and the project began to slip. Projected time to produce the CCF for a fully developed program was totally unacceptable, and jeopardized the project.Clearly another approach was required. Because existing hueristics were based on a concept of rules, research indicated an expert system using rules and a knowledge based approach had the highest probability of success.The paper emphasizes the development process of a knowledge based system from the perspective of the responsible project manager. The methodology is also applicable to common business problems.
Caution on criteria: on the context dependency of selection criteria for expert systems projects
Authors: Krcmar Helmut
Published: October 2004

The growing interest in the use of expert systems (ES) necessitates procedures to determine when the use of ES-techniques is appropriate. This paper describes some recently suggested proposed criteria and reviews them in light of the use of ES in business. Here medium-size, embedded ES and not large, single purpose stand-alone ES dominate. Presently proposed criteria do not focus entirely on what is characteristic of ES in business. The paper then develops a classification for the situations in which ES-techniques can be used. Based upon this classification it recommends a situation based methodology to generate appropriate goals for the use of ES-techniques and suggests adapted criteria for evaluation.
The Kiewit network: a large AppleTalk internetwork
Authors: Brown R. E.
Published: October 2004

Dartmouth College's Kiewit Network connects nearly all of the computing resources on the campus: mainframes, minicomputers, personal computers, terminals, printers, and file servers. It is a large internetwork, based on the AppleTalk protocols. There are currently over 2900 AppleTalk outlets in 44 zones on campus. Over 90 minicomputers act as bridges between 177 AppleTalk twisted pair busses. This paper describes the extent and facilities of the current network; the extensions made to the AppleTalk protocols, including a stream protocol and an asynchronous link protocol; and current development projects, including an AppleTalk stream to TCP converter.

The Kiewit Network is a general purpose local data network. It serves as glue between all the host computers and nearly all the personal computers and terminals on campus. The network extends to the academic and administrative buildings, and the student residence halls, with network ports placed in almost all the offices and rooms. From these ports, users may access any of the host computers connected to the network. In addition, the hosts use network connections to communicate between themselves for electronic mail, file transfer, printer sharing, etc. The network also supports Apple Computer's AppleTalk® protocols. Departments and individuals can purchase standard devices which use AppleTalk (such as LaserWriters® and file servers), and connect them directly to the network.

The Kiewit Network is not part of the telephone, energy control, or security systems of the College. While there can be benefits from combining them, separating these systems has simplified our design in many ways. A network failure doesn't interrupt these other services. We can also schedule experimental time for testing new software at our convenience.

Dartmouth College started its campus network with General Electric Datanet 30 computers acting as front ends for the Dartmouth College Time Sharing (DCTS) system. In 1978, as the requirement for ports grew, Honeywell 716 minicomputers replaced the Datanet machines. In the same time period, two factors forced a change in perspective away from a front-end function toward a networked approach. New hosts began to arrive on campus. These new machines required enhancements to the network. Second, off-campus sites demanded more ports than the existing phone lines could supply. We served these remote users by using Prime P200 minicomputers as statistical multiplexors. In 1980, we implemented the DCTS terminal handling protocols on a less expensive minicomputer, and began to place these network nodes in the basements of buildings across the campus.

When the College recommended that the freshmen entering in the fall of 1984 purchase a Macintosh™ computer, funds were appropriated for three major network enhancements: installation of a network port for each undergraduate in the residence halls; conversion of the network to the AppleTalk protocols; and creation of a terminal emulation program to exploit the enhanced network capabilities.
Supercomputers on the internet: a case study
Authors: Kline C.
Published: October 2004

This paper will discuss the design of a TCP/IP implementation and its upper level protocols on the University of Illinois supercomputer. We will also discuss some of the issues peculiar to TCP communication with a supercomputer, and some of the special problems encountered while writing and debugging under CTSS, which is not an environment particularly conducive to network development.
Performance of priorities on an 802.5 token ring
Authors: Peden J. H. , Weaver A. C.
Published: October 2004

The IEEE 802.5 token ring allows the user to define multiple message priorities. The priority mechanism is implemented using a reservation scheme whereby packets attempt to reserve the token. We present an analytic model that predicts mean delay for each priority level. We show that operation of the priority mechanism is not free; that is, there is a well-defined cost (measured in terms of increased average message delay) associated with its implementation, and that in general there is minimal discrimination made between the various priority levels. We also show that the cost of the priority mechanism is an easily computable function of various network parameters. One of the circumstances where the priority mechanism results in a large discrimination between priorities is when service is limited to a single packet per received token. We show that single-packet-per-token service is necessary (but not sufficient) to gain maximum benefit from priority operation. Our main conclusion is that the network user will not, in general, receive much benefit from the priority mechanism since the priority mechanism can in fact
increase
slightly the delay for all priorities. The exception to this statement occurs when the network is operating under fairly extreme conditions which are well defined, and which we believe are unlikely in most installations.
Computer networking for large computers in Universities
Authors: Matsukata J.
Published: October 2004

N-1 protocol was developed for construction of a computer network which connects universities in Japan. N-1 protocol has been adopted by Inter-University Computer Network and University Library Network.

NACSIS has started the construction of Science Information Network which will provide an infrastructure for digital communication for universities in Japan. High speed digital lines has been leased from NTT for that purpose.

A local area network was constructed at the Faculty of Engineering at the University of Tokyo. The network consists of an optical fiber backbone network and many IEEE802.3 10Mbps baseband networks connected to the backbone. Connection to large computers was one of the key issues in the planning of that network.
Protocol verification using reachability analysis: the state space explosion problem and relief strategies
Authors: Lin F. J. , Chu P. M. , Liu M. T.
Published: October 2004

Reachability analysis has proved to be one of the most effective methods in verifying correctness of communication protocols based on the state transition model. Consequently, many protocol verification tools have been built based on the method of reachability analysis. Nevertheless, it is also well known that state space explosion is the most severe limitation to the applicability of this method. Although researchers in the field have proposed various strategies to relieve this intricate problem when building the tools, a survey and evaluation of these strategies has not been done in the literature. In searching for an appropriate approach to tackling such a problem for a grammar-based validation tool, we have collected and evaluated these relief strategies, and have decided to develop our own from yet another but more systematic approach. The results of our research are now reported in this paper. Essentially, the paper is to serve two purposes: first, to give a survey and evaluation of existing relief strategies; second, to propose a new strategy, called PROVAT (PROtocol VAlidation Testing), which is inspired by the heuristic search techniques in Artificial Intelligence. Preliminary results of incorporating the PROVAT strategy into our validation tool are reviewed in the paper. These results show the empirical evidence of the effectiveness of the PROVAT strategy.
An exercise in deriving a protocol conversion
Authors: Calvert K. L. , Lam S. S.
Published: October 2004

This paper demonstrates formal techniques useful in solving and reasoning about protocol conversion problems. A simple example problem is solved and the resulting conversion system is shown to have certain desired properties, using the
projection paradigm
. The example problem is representative of some real-world problems in that the protocols involved are similar in function, and even in structure, but have fundamental differences that render them incompatible in the absence of an active translation entity (protocol converter). The use of mappings, as well as images and inverse images of properties, in comparing semantics of protocols is discussed and illustrated.
Modeling, analysis, and optimal routing of flow-controlled communication networks
Authors: Lam S. S. , Hsieh:0S2:0E C.-T.
Published: October 2004

Closed queueing networks have been advocated by several authors to be a more desirable model than open queueing networks (Kleinrock's model) for network design. We compare open and closed network models and demonstrate the accuracy of a particular closed network model with experimental results. The proportional approximation method (PAM) is presented for evaluating performance measures of closed queueing networks. PAM algorithms have computational time and space requirements of
O(KM)
, where
M
denotes the number of queues and
K
denotes the number of virtual channels in the network. Thus, PAM is the first (and only) method that can be used for solving industrial-strength network design problems using a closed network model.

We formulate the following optimal routing problem: Find a route for a new virtual channel to be added to a network with existing flow-controlled virtual channels. A fast heuristic algorithm is presented. The algorithm uses PAM and exploits the following empirical observation: The route that maximizes the individual throughput of a virtual channel coincides in most cases with the route that maximizes the total network throughput (this is not true in general). We present statistical results from studies of 100 randomly generated networks to demonstrate the accuracy of PAM algorithms and the effectiveness of the optimal routing algorithm. (Exact solutions obtained by the tree convolution algorithm were used as benchmarks in our statistical studies.)
An architecture for network-layer routing in OSI
Authors: Tsuchiya P. F.
Published: October 2004

Work on the standardization of routing protocols for OSI is in progress. The envisioned set of routing protocols is expected to work in nearly all of the environments which constitute OSI networks. Behind these routing protocols is an architecture which outlines problems and goals, establishes a framework upon which to base the development of protocols, and provides a conceptual baseline for continued work on unsolved problems. This architecture defines routing in the OSI network layer, functionally partitions the problem into its components, defines a routing hierarchy and an address hierarchy and discusses their relationship, and discusses arms-length routing relationships between differently administered networks. This paper presents that architecture, and discusses problems which remain to be solved as work progresses towards a global OSI network.
Algorithms for the reduction of timed finite state graphs
Authors: Masapati G. H. , White G. M.
Published: October 2004

A set of algorithms to reduce the size of timed finite state graphs are presented. In particular, we develop a more general algorithm for vertex folding than those presently existing. It is based on the law of conservation of transition time. We demonstrate the application of these reduction algorithms to a version of the stop-and-wait protocol.

We have also developed a graph reduction software package incorporating all these algorithms which can be used in automated performance prediction. Graph reduction software tools such as these are important and form an integral part of automated protocol performance prediction tools[RUD 83].
Distributed shared memory in a loosely coupled distributed system
Authors: Fleisch B. D.
Published: October 2004

This work outlines the development and performance validation of an architecture for distributed shared memory in a loosely coupled distributed computing environment. This distributed shared memory may be used for communication and data exchange between communicants on different computing sites; the mechanism will operate transparently and in a
distributed
manner. This paper describes the architecture of this mechanism and metrics which will be used to measure its performance. We also discuss a number of issues related to the overall design and what research contribution such an implementation can provide to the computer science field.
A reliable and efficient multicast for broadband broadcast networks
Authors: Erramilli A. , Singh R. P.
Published: October 2004

A reliable and efficient data transfer protocol is proposed for multicast applications in broadband broadcast networks. The protocol is based on negative acknowledgements, with several enhancements so that it matches most of the functionality of a positive acknowledgement based protocol. The protocol makes the best use of resources in the broadband network environment by conserving processing and trading off transmission and storage resources. The performance of this protocol is compared with the positive acknowledgement based protocol on the basis of maximum throughput as a function of group size for lecture and conference applications.
Transparent interconnection of incompatible local area networks using bridges
Authors: Perlman R. , Varghese G.
Published: October 2004

No single LAN technology is sufficient to interconnect all the computers in a given plant, campus, or site. Thus it is desirable to combine different types of LANs, using a device called a Bridge, to produce an Extended LAN. Some LANs in the Extended LAN may have incompatible Data Link formats. Thus a bridge may need to encapsulate a frame originating on LAN A inside the Data Link header of another (incompatible) LAN B in order to allow the type A frame to travel over LAN B. In general, frames sent between any pair of LANs in the Extended LAN must be encapsulated across every incompatible LAN in the path between the LANs.

Bridges learn their routing information from information contained in frames they forward. Besides the problems of distinguishing various kinds of encapsulated and unencapsulated frames, the encapsulating protocol used by bridges must also solve the learning problem. This leads to a new set of considerations and solutions. We begin with a rough solution, and refine it using informal arguments and examples to lead to the final description. The stages in the description roughly mimic the design process.
Communication protocols and error recovery procedures
Authors: Bochmann Gregor V.
Published: October 2004

The design of multiple computer systems and computer networks poses some interesting new problems and shows some older problems in the light of a new context. We are interested in the problems which are related to the design of communication protocols and error recovery procedures. In the design of computer systems, error recovery procedures have often not received very much attention, although they are essential for the reliable operation of most systems. In the case of multiple computer systems, appropriate error recovery procedures can be used to obtain a very much increased availability of the system services. This is also an advantage of computer networks. Whereas single computer systems can sometimes function to a certain extent without elaborate error recovery procedures, data communication protocols, on the other hand, normally have to contain explicit error recovery procedures, since the underlying communication line is normally not very reliable. Therefore, approaches that have been used for the design of protocols in computer networks could also be useful in the design of local multiple computer systems for obtaining higher reliability and availability.
Recoverability of modular systems
Authors: Merlin Philip M. , Farber David J.
Published: October 2004

In [1] GOSTELOW-VAN WEERT, it was shown that processes can be described by Petri-nets (PN). In this note we will demonstrate a way of designing programs using Petri-nets as a way of describing the desired behavior. This approach makes it possible to utilize all the theoretic knowledge developed for PN and thus provides a powerful tool for program design. In an example of this approach we show how to design a recoverable program. This design is based on a study of recoverable PN's presented in [2], [3], [4] and [5].

In this note, we will not deal with the code itself, but with the structural organization of the programs. Our approach is based on an hierarchical, top-bottom, modular design. At each level a description of the desired system behavior is given. This description is then modeled by a PN and analyzed using the theory developed for PN's.

This analysis allows one to check for, among other things, properties of the systems such as recoverability, proper termination, etc. These properties are inherently structural and not dependent on internal module semantics.
Protection
Authors: Gaines R. Stockton
Published: October 2004

The discussion during this session primarily centered around the paper “On Data Secure Computer Networks” by G.J. Popek. Popek suggested that the main security problems in computer networks involved the security of the host computers in the network and that techniques for securing general communications networks are satisfactory for dealing with the communication aspects of computer networks. The main problems which need to be addressed are the problems of authenticating processes in different computer systems in the network to each other and of providing the required degree of security in the computer systems in the network. There was no real dispute of Popek's claims by the attendees at the workshop.
Performance
Authors: Chu Wesley
Published: October 2004

Interprocess Communications play an important role in system performance in the throughput as well as in its reliability. McQuillan and Walden describe such design considerations as buffering and pipelining, error control, multiplexing and addressing, and flow control in interprocess communications. Danthine and Bremer proposed a model for representing protocols which can be used to verify the definition of the protocol and evaluate its system performance. Opderbeck presents measurement esults on performance of control procedures of the ARPA Network, which reveals that efficiency of the current protocol can be as low as 20% of line efficiency. While using a new host-to-host protocol an average of 30-40% efficiency can be achieved.

In order to reduce the overhead in interprocess communications, much thought must be given on the efficient implementation and use of protocols, rather than only on their feasibility. Much more work is needed to be done in this area.
Communication protocols in a network context
Authors: Danthine André A.S. , Bremer Joseph
Published: October 2004

In a distributed computers network based on a packet-swltched communication subnet, it is possible to describe the system as a hierarchical structure. We will consider here only three levels:

-level 0: communication between nodes of the subnets.

-level 1: communication between hosts connected to the net.

-level 2: communication between users processes (subscribers) in different hosts.

At each level, the communication is based on a protocol and the data structures to be exchanged are different. For instance the data structure exchanged at level 2 may be a sequential file. As there is no direct support of communication at this level, it is through the mechanisms of level 1 and 0 that the transfer will take place with data structure at each level not directly related to the upper level one. The complete definition of the system will therefore required not only the level 0, 1 and 2 protocols, but also inter-level protocols.

In the following, we will concentrate on the level 1 protocol. It is the basic communication protocol of a network since it will be used by user processes in different hosts and it will use the subnet as a communication support. This level 1 entity is called a “TS” (transport station) in CYCLADES [13] and a “TCP” (transmission control program] in [2].
Review of
Combinatorial Optimization - Theory and Algorithms
Authors: Ivanov Ivelin
Published: October 2004

Rarely do mathematical disciplines have so direct practical relevance as combinatorial optimizations, which is why it is one of the most active areas of discrete mathematics. It became a subject in its own right only about 50 years ago, which makes it one of the youngest also.This book covers most of the important results and algorithms achieved in the field to date. Most of the problems are formulated in terms of graphs and linear programs. The book starts with reviewing basic graph theory and linear and integer programming. Next, the classical topics in the field are studied: minimum spanning trees, shortest paths, network flows, matching and matroids.Most of the problems in Chapters 6-14 have polynomial time (efficient) algorithms, while most of the problems studied in Chapters 15-21 are NP-hard, i.e. polynomial time algorithm is unlikely to exist. Although in many cases approximation algorithms are offered which at least have guaranteed performance.Some of the topics include areas which have developed very recently, and which have not appeared in a book before. Examples are algorithms for multicommodity flows, network design problems and the traveling salesman problem. The book also contains some new results and new proofs for previously known results.The authors have an unique approach in the presentation of the topics. They provided detailed proofs for almost all results, including deep classical theorems (e.g. weighted matching algorithm and Karmarkar-Karp bin-packing algorithm) whose proofs are usually sketched in previous works.
Review of
Introduction to Distributed Algorithms
Authors: Mavronicolas Marios
Published: October 2004

This book presents a view of several important topics in the modern field of distributed algorithms. The book is intended to provide useful background and reference information for professional engineers dealing with distributed systems, and for entering researchers who wish to develop a sufficient background in distributed algorithms. In addition, the book is suitable for providing a textbook-style introduction to distributed algorithms for advanced undergraduates or early graduate students who are taking a relevant course or consider pursuing research in the field.The reference sources for this book incluude mainly research papers on the modern theory of Distributed Computing that routinely appear in conferences such as the ACM Symposium on Principles of Distributed Computing (PODC), or the International Symposium on DIStributed Computing (DISC). Fundamental milestones of this theory include also research papers from other major conferences of Theoretical Computer Science that are of wider interest, such as the ACM Symposium on Theory of Computing (STOC), or from leading theory journals, such as the Journal of the ACM or SIAM Journal on Computing.
Reprints from Computing Reviews
Authors: Seiferas Joel
Published: October 2004

As a service to our readers,
SIGACT News
has an agreement with
Computing Reviews
to reprint reviews of books and articles of interest to the theoretical computer science community.
Computing Reviews
is a monthly journal that publishes critical reviews on a broad range of computing subjects, including models of computation, formal languages, computational complexity theory, analysis of algorithms, and logics and semantics of programs. ACM members can receive a subscription to
Computing Reviews
for $48 per year by writing to ACM headquarters.
ACM SIGACT news distributed computing column 7
Authors: Rajsbaum Sergio
Published: October 2004

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, internet, and the web.This issue consists of some PODC announcements followed by two papers:• Announcements about PODC 2002, 2003, 2004 and 2005 by Gil Neiger• "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" by Seth Gilbert and Nancy Lynch• "Topology Control and Routing in Ad hoc Networks: a Survey" by Rajmohan RajaramanMany thanks to Gil, Rajmohan, Seth and Nancy for contributing to this issue.
Computing variance for interval data is NP-hard
Authors: Ferson Scott , Ginzburg Lev , Kreinovich Vladik , Longpré Luc , Aviles Monica
Published: October 2004

When we have only interval ranges [

x
i
,

x
i

] of sample values
x
1
,…,

x
n
,

what is the interval [
V, V
] of possible values for the variance
V
of these values? We prove that the problem of computing the upper bound
V
is NP-hard. We provide a feasible (quadratic time) algorithm for computing the lower bound
V
on the variance of interval data. We also provide a feasible algorithm that computes
V
under reasonable easily verifiable conditions.
A cooperative asynchronous write mechanism for NAS
Authors: Jun Lu , Xianliang Lu , Hong Han , Qingsong Wei
Published: October 2004

Network Attached Storage (NAS) is the high performance storage appliance that provides shared data to clients and other servers in a Local Area Network (LAN). The existing NAS products provide file services by themselves. They can not cooperate with each other to improve performance. This paper presents an automatically cooperative asynchronous write mechanism for NAS: ACAWM. ACAWM is a set of pure software mechanisms which provide both the reliability of synchronous write operations and the performance of asynchronous write operations. ACAWM contains two parts: automatically cooperative mechanism and asynchronous write mechanism. The automatically cooperative mechanism of ACAWM can make all NAS in a LAN to cooperate with each other without artificial configuration. Basing on the automatically cooperative mechanism, asynchronous write mechanism of ACAWM can allow a NAS to use the free RAM of the cooperative NAS to realize asynchronous write in the file system of NAS. The data of asynchronous write in ACAWM are saved on both of the two cooperative NAS before being written to disk, thus ACAWM can ensure the security of data. The design of ACAWM fully considers the usability of NAS and has no special requirement for the system software of clients. The experiments in this paper prove that ACAWM can greatly improve the performance of NAS.
An efficient distributed method for allocating resources based on an unobstructed squeezing technique
Authors: Wada Yutaka , Cheng Zixue
Published: October 2004

The distributed resource allocation problem is one of important problems in distributed environment. In some applications where a resource is required by many processes at a time, some kinds of resources, such as a memory, a disk, or a communication channel can be divided into many units, which can be allocated to more than one process in the same time according to their requested amounts for the resource. In this paper, in order to use such kind of resources efficiently, we propose a new method for allocating the resources, by employing a "unobstructed squeezing" technique. By this method, a process with lower priority may acquire requested units, before another process with higher priority, if this allocation to the latter will not be delayed. A simulation shows that the performance of our method will be about 30% better than the traditional method for h-out-of-k problem (without squeezing), when each resource has large number of units and the number of requests for the resource is large enough.
A flexible remote user authentication scheme using smart cards
Authors: Lee Cheng-Chi , Hwang Min-Shiang , Yang Wei-Peng
Published: October 2004

In 1999, Hwang and Li proposed a new user authentication scheme using smart cards. The scheme does not need any password or verification table. Later, Sun proposed an efficient remote use authentication scheme to improve the efficiency of the Hwang-Li scheme. However, these two schemes do not allow users to freely choose and change their passwords. In this article, we shall propose a simple and efficient remote user authentication scheme that allows users to freely choose and change their passwords without significantly increasing the computation cost.
SIGACT news complexity theory column 34
Authors: Hemaspaandra Lane A.
Published: October 2004

This issue's guest columnists are angels. The column was faced with a last-minute cancellation, and they prepared on very short notice a wonderful column. And I'm sure that many readers of the column will want to learn even more by, for example, reading their monograph
Complexity Classifications of Boolean Constraint Satisfaction Problems
[7].Future complexity columns include Holzer/McKenzie on a familiar complexity class turning up in a surprising context, Gasarch (and a host of contributors) on the future of NP, Schaeffer/Umans on completeness for higher levels of the polynomial hierarchy, Nickelsen/Tantau on partial information classes, and Paturi on the complexity of
k
-SAT,Regarding the Schaeffer/Umans column, their 2-part column will be in part a kind of Garey and Johnson for completeness results for ∑

i

p

and π

i

p

,
i
≥ 2. You can help their project by, if you have proven natural sets complete for NP
NP
, coNP
NP
, NP

NP
NP

, coNP

NP
NP

, etc., letting them (MSchaefer@cti.depaul.edu and umans@microsoft.com) know of your result and its best citation location. Thanks!
ACM SIGACT news distributed computing column 5
Authors: Rajsbaum Sergio
Published: October 2004

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification internet, and the web.This issue consists of four parts:• a survey of SIROCCO'01 by Pierre Fraigniaud,• a survey of POMC'01 by Rui Fan,• a survey of PODC'01 by myself,• the paper "Paxos Made Simple" by Leslie Lamport.This year was the 20-th anniversary of PODC, and included a special celebration honoring the work of Leslie Lamport, on the occasion of his 60th birthday, and was collocated with the Workshop on Principles of Mobile Computing (POMC). I briefly describe the PODC conference, and reproduce the toast by Fred Schneider in the honor of Leslie. The Business Meeting report is by Gil Neiger. Finally, there is Leslie's paper on his own algorithm which was discussed in a few of the PODC lectures. I am very grateful to the many people contributing to this issue.