Efficient communication in Bluetooth networks requires design of intra and inter-piconet scheduling algorithms, and therefore, numerous algorithms have been proposed. However, due to complexities of the Bluetooth MAC, the performance of these algorithms has been analyzed mostly via simulation. We present analytic results regarding the exhaustive, gated, and limited (pure round robin) scheduling algorithms in piconets with bidirectional and unidirectional traffic. We show that a piconet operated according to the limited scheduling algorithm is equivalent to a 1-limited polling system and present exact results regarding symmetric piconets with bidirectional traffic. Then, the difficulties in analyzing the performance of the exhaustive and gated algorithms in a piconet with bidirectional traffic are demonstrated. In addition, we present exact analytic results for piconets with unidirectional traffic. We show that, surprisingly, in symmetrical piconets with only uplink traffic, the mean waiting time is the same for the exhaustive and limited algorithms. This observation results from the differences between piconets and traditional polling systems and can be extended for time-division-duplex systems with arbitrary packet lengths. Furthermore, we show that the mean waiting time in a piconet with only uplink traffic is significantly higher than its corresponding value in a piconet with only downlink traffic. Finally, we numerically compare the exact results to approximate results, presented in the past.

Efficient communication in Bluetooth networks requires design of intra and inter-piconet scheduling algorithms, and therefore numerous algorithms have been proposed. However, due to complexities of the Bluetooth MAC, the performance of these algorithms has been analyzed mostly via simulation. We present exact analytic results regarding the exhaustive, gated, and limited (pure round robin) scheduling algorithms in piconets with unidirectional traffic. We show that, surprisingly, in symmetrical piconets with only uplink traffic, the mean waiting time is the same for the exhaustive and limited algorithms. This observation is extended for time-division-duplex systems with arbitrary packet lengths. Furthermore, we show that the mean waiting time in a piconet with only uplink traffic is significantly higher than its corresponding value in a piconet with only downlink traffic. We then demonstrate the difficulties in analyzing the performance of the exhaustive and gated algorithms in a piconet with bi-directional traffic. Finally, we numerically compare the exact results to approximate results, presented in the past.

The terrorist attacks on September 11, 2001 have drawn attention to the use of wireless technology in order to locate survivors of structural collapse. We propose to construct an ad hoc network of wireless smart badges in order to acquire information from trapped survivors. We investigate the energy efficient routing problem that arises in such a network and show that since smart badges have very limited power sources and very low data rates, which may be inadequate in an emergency situation, the solution of the routing problem requires new protocols. The problem is formulated as an anycast routing problem in which the objective is to maximize the time until the first battery drains-out. We present iterative algorithms for obtaining the optimal solution of the problem. Then, we derive an upper bound on the network lifetime for specific topologies. Finally, a polynomial algorithm for obtaining the optimal solution in such topologies is described.

The paper introduces a protocol for rerouting calls in an ATM network, referred to as the flexible trerouting protocol (FRP). Failure of a VP triggers construction of an alternate VP out of VPs that are not in use, named stand-by VPs, by simple operations at the endpoints of the stand-by VPs. VC rerouting from the failed VP to the alternate VP is performed concurrently. FRP is designed to also allow recovery from repeated failures that may occur during the construction and rerouting process.

This paper shows that the memory overhead of distributed snapshots is unbounded. Several techniques are suggested for bounding it: bounded memory-overhead versions of distributed snapshots for specific problems, like termination detection and deadlock detection; use of alternative protocols; or use of synchronizers or schedulers in order to limit the photographed protocol to executions whose distributed snapshot requires bounded memory. Each solution is discussed in detail, and its memory overhead is analyzed. © 1999 John Wiley & Sons, Inc. Networks 34: 11–17, 1999

This paper describes an architecture for controlling a wavelength-routed optical network. The optical network provides reconfigurable connections that can be used to carry different types of data, at possibly different bit rates. A connection consists of a path in the network and a wavelength on each link in that path. This work focuses on the mechanisms for controlling the optical connections. Distributed control protocols are provided for setting up and taking down connections reliably. These protocols allow connection originators to obtain resources with high probability by minimizing reservation conflicts, allow connections to stay up even if controllers along the path in the network fail, ensure that controllers in the network have a consistent view of the state of each connection, and ensure that all resources taken up by a connection are released once the connection is taken down. Fast protocols are also proposed for handling link failures and wavelength failures on a link. These protocols are general in that they can be used in networks with: (1) different kinds of node architectures (electrical/optical switching, with or without wavelength conversion, etc.), (2) different route-computation algorithms that reflect the underlying constraints imposed by the nodes and the physical layer, and (3) any kind of underlying mechanism using which the network controllers can communicate with each other.

This paper describes an architecture for adding an underlying wavelength-routed optical layer to a standard ATM network. The optical layer provides reconfigurable lightpaths that serve as links between electronic ATM switches. A lightpath is carried on a particular wavelength and path in the underlying optical wavelength-routed network. This work focuses on the mechanisms for controlling the optical layer. Distributed control protocols are provided for setting up and taking down lightpaths reliably and for updating the topology of the network, including the lightpaths. These protocols allow lightpath originators to obtain resources with high probability by minimizing reservation conflicts, allow lightpaths to stay up even if controllers along the path in the network fail, ensure that controllers in the network have a consistent view of the state of each lightpath, and ensure that all resources taken up by a lightpath are released once the lightpath is taken down.

Discusses methods for adjusting the layout of virtual paths in an ATM network, to the dynamics of changes in the usage of the network by its end-users. The authors first present a centralized algorithm for finding a better layout for the current traffic pattern, and for applying the change in the network, and discuss its drawbacks. They then present a distributed algorithm that emulates the centralized algorithm with a much lower overhead, and enhanced durability to faults. They prove that both algorithms produce identical layouts, thus showing the superiority of the latter algorithm. Both algorithms base the changes in the network on a new rerouting protocol, which does not cause any losses in data, nor changes in the FIFO order of cells.

This paper presents a new source routing technique for ring and multi-ring networks, which uses short address labels. The main objectives for having this new method are that in case of one or more failures a frame will be guaranteed: (1) to be removed from the ring-termination property, and (2) to be copied at most once and only by its destinations-safety property. The scheme is based on dividing the label address space of each ring into subspaces, such that the address subspaces are physically disjoint. More specifically, each ring, in a multi-ring network, is divided into two or more parts such that adjacent address subspaces are disjoint. The route of each frame is described by a sequence of short address labels in the frame's header. The current route of a frame is determined by the first address label in its header, and it can be used for routing over at most one subspace of the ring.>

A new message-delaying version of synchronizer /spl gamma/, named /spl zeta/, is presented. Synchronizer /spl zeta/ ensures that original-protocol messages received by a node from nodes in the same cluster are never early, and thus, no buffers for their temporary storage are necessary. Only original-protocol messages on edges leading to nodes of other clusters (external edges) may be early. The z-partition algorithm is introduced to reduce the number of external edges connected to each node, thus reducing the memory overhead of /spl zeta/. For an arbitrary z, this algorithm ensures that the external degree of each node is no more than [|V|/z]-1. The z-partition algorithm increases the time complexity of /spl zeta/ to O(z+log/sub k/ |V|) per pulse. The tradeoff between memory overhead and time complexity achieved by the z-partition algorithm is optimal.>

In ATM networks, two levels of connections are defined: virtual path connections and virtual channel connections. Virtual paths are the building blocks of the virtual channels. This hierarchy, known as "the virtual path concept", provides considerable advantages in the design of high-speed networks. In the paper the authors show that this concept has the advantage of providing a means of improving the survivability of virtual channels. To this end, they present a simple rerouting protocol, which can be invoked upon the failure of an intermediate link or node of a virtual path. This protocol reroutes all the affected virtual channels to an alternative virtual path. Due to the simplicity of the protocol, it can be completed rapidly, thus fulfilling an essential requirement of any rerouting scheme.>

This paper shows how to design an ATM network, for real-time traffic, such that under full network load (i) the maximum delay of a low-rate voice connection is minimized, (ii) the delay uncertainty or jitter is a fixed network parameter, and (iii) the required buffer sizes (inside the network) to ensure loss-free routing is minimized. In addition, this design does not exclude the integration of other classes of traffic, such as connectionless, which have lower priority. The isochronous timing information is used only for regulating and pacing the traffic forwarded inside the network rather than for routing as in traditional circuit switching networks. This means that an ATM cell is sent from one switch to another not at a very specific time but within a time frame of a relatively long duration as compared to the cell transmission time. The routing of cells of each connection is based on VCI and VPI, and as a result, timing errors do not affect the ATM routing. Analytical and simulation results are presented, which demonstrate the effectiveness of this switching approach.>

Slot reuse is a simple method to improve the efficiency of MACs designed for the slotted, dual bus configuration. The authors propose several schemes for the assignment of throughput to stations in this configuration, taking into account slot reuse and assuming uniform traffic. The criteria for comparison of the schemes are throughput gain, worst message queueing and access delays at stations and the fraction of blocked messages. It turns out that the throughput gain in the scheme in which every station receives the same throughput is relatively low but it is the most attractive scheme is relation to the other criteria.>

No abstract available.

In computer networks with decentralized control, it is necessary to provide a distributed query mechanism, whereby a node can dynamically discover the location of a remote resource. The authors propose a query mechanism based on flooding with feedback, which uses no more than two messages over any link. They examine the fault tolerant aspects of this distributed query mechanism, operating in a network where links and nodes may fail and show that, under certain conditions, the resource is indeed found. They then construct enhancements to this mechanism, where the conditions under which the resource is found are substantially relaxed, at the cost of some increase in message complexity.>

Source routing requires that the source station knows a route to the destination. The paper presents a new bridge protocol for route discovery in multiple-ring networks, where several token-rings are connected by bridges. The protocol gives to the source station an indication of the availability of a route to the destination. If such a route exists, the source is supplied with a description/spl mdash/a list of ring and bridge identities/spl mdash/of the route that is fastest at the time of protocol execution. The main advantage of the new route discovery protocol over the existing one is its communication efficiency: the number of frames used is the sum of the number of rings and number of bridges in the network, as opposed to the exponential function required in the existing protocol. Another advantage of the new protocol is its option that allows determining routes to multiple destinations, thus supporting efficient multicast source routing.>

A new MAC protocol for route discovery in multiple-ring network, called the FTRD-protocol, was introduced in Part I. The present paper shows how the FTRD-protocol can find a description of a tree that spans a group of destinations. By placing such a description in the header of its frame, a source station can efficiently multicast the frame to the destination group. This requires no change in the operation of the source routing bridges. Another issue addressed in the paper is the recovery of the FTRD-protocol from error and failure conditions. When a bridge or the source suspects that the protocol is dead-locked, it initiates an independent recovery protocol that clears the network and prepares it for a new execution of the FTRD-protocol. The last issue addressed in the paper is the execution of the FTRD-protocol in a network with high-speed rings. The problem in such a network is that the bridges do not have sufficient time, after recognizing the route identity, to look in the local table and decide whether the relevant fields in the received frame need to be altered.>

Describes a new media access control protocol, the multiple-token protocol, for high-speed ring networks. The purpose of this protocol is to increase the throughput of a token-ring under heavy load, and to decrease the access delay under light load. The protocol maintains several logical token-rings in the single physical ring. The number of logical rings can be changed dynamically by the ring stations according to the ring load. Each logical ring has its own token, and its operation is close to a token ring with early-token-release and destination removal. Multiple tokens enable multiple simultaneous transmissions of new frames by different stations and decrease the waiting for a token delay. However, the integration of several token rings in a single media is not straightforward since they interfere with the operation of each other. The present protocol is not the first to enable multiple simultaneous transmissions of frames to a ring network. However, unlike previous protocols, that use the buffer insertion concept combined with some fairness mechanism, the new one uses tokens in order to regulate the access to the ring and to ensure fairness. Unlike buffer insertion rings where data-frames may experience a delay of one data-frame at every intermediate station, in the new protocol the delay in the intermediate stations does not depend on the number of such stations. Moreover, this delay can be reduced even to 0, if needed. The new protocol ensures the removal of a data-frame even if both the destination and the source of the frame fail to remove it from the ring.>

In a token-ring local area network it is important to have minimum delay at each station. One-bit-delay is the minimum possible delay a ring station may have. It can be achieved only if every received bit is transmitted with no change or its outgoing value is determined independently of its incoming value and the incoming values of subsequent bits. The paper introduces the distributed priority mechanism for token-rings as approved by the IEEE-802.5 standard. In this scheme, the token is accompanied by a priority field P and a reservation field R, that work together in an attempt to match the service priority of the ring to that of the most urgent waiting message. It is shown that due to the computation restrictions imposed by the one-bit-delay requirements, the scheme may require up to 7 round-trips in order to reduce P to R. This may lead to loss of bandwidth and starvation at stations with low priority data. The paper presents a new priority mechanism and proves its correctness. The new mechanism retains the desired properties of the standard protocol: it ensures fairness and can be executed by the stations with one-bit-delay. In the new mechanism at most one round-trip is required in order to reduce P to R. This increases the ring throughput and enables low-priority PDUs to get service when PDUs with higher priorities do not exist.>

Slot reuse is a simple method to improve the efficiency of MACs designed for the slotted, dual bus configuration. The authors propose several schemes for the assignment of throughput to stations in this configuration, taking into account slot reuse and assuming uniform source destination distribution. The criteria for comparison of the schemes are throughput gain, worst averages of message queueing and access delays at stations and the fraction of blocked messages. On the average, it turns out that the scheme in which every station receives the same throughput is very attractive.>

Several schemes for slot reuse in CRMA are studied. A major challenge in CRMA is to incorporate slot reuse together with continuous message transmissions, i.e., to ensure that every message is transmitted in a stream of contiguous slots on the bus. Schemes based on the ideas of erasure nodes and destination release are developed and simulation results are presented.>

A media access control protocol, called the multiple token protocol, for high-speed ring networks is described. Its purpose is to increase the throughput under a heavy load and to decrease the access delay under a light load of the token-ring protocol. The protocol maintains several logical token rings in the single physical ring. The number of logical rings can be changed dynamically by the ring stations according to the actual ring load. Each logical ring has its own token, and its operation is close to a token ring with early-token-release and destination removal. Multiple tokens enable multiple simultaneous transmissions of new frames by different stations and decrease the waiting for a token delay.>

A multilink system consists of several full-duplex parallel links that carry data between two nodes. The authors construct a protocol-the multilink protocol (MLP)-that simulates a single full-duplex link system. They show that the multilink protocol proposed by the existing standard is not reliable, and they define a new multilink protocol that is proved to be reliable.>

Protocols for establishing, maintaining, and terminating connections in packet-switched networks have been studied, and numerous standards have been developed to address this problem. The authors reexamine connection establishment in the context of a high-speed packet network, introduce a protocol for connection establishment/takedown that is appropriate for such a network, and explain its advantages over previously proposed protocols. The main features of the proposed protocol are: fast bandwidth reservation in order to avoid as much as possible reservation conflicts, guaranteed release of the reserved bandwidth even under modal and link failures, and soft recovery from processor failures, which allows the maintenance of existing connections under processor failure provided the switch and links do not fail. The underlying model that is used is the PARIS/plaNET network, but the protocol can be adapted to other fast packet networking architectures as well.>

A simple scheme for slot reuse without latency for the dual bus configuration is studied. The scheme relies on information read in the previous slot and will be referred to as previous slot information (PSI) slot reuse. The scheme requires a minimal addition to the station hardware and its reliability is high. The efficiency of PSI is checked over a wide range of parameters and is found to be almost as good as destination release. The scheme can be implemented with or without the addition of erasure nodes.>

A protocol for setting up a tree connection for the purpose of multicast communication over a high-speed packet switched network is presented. The tree connection is based on the use of local identifiers, which are swapped at every intermediate node of the tree. Local identifiers are simple to manage, provide fast access to the routing tables, and are very efficient in terms of the size of the resulting routing space. The authors consider a high-speed network in which the local label swapping on data messages is performed in hardware by the switching subsystem, while the connection set-up is done in software by the switch control subsystem. A reliable protocol for setting up the tree connection is presented, and its correctness is formally proved. The protocol ensures the integrity of the tree and when failures occur, it is gracefully degraded into a smaller tree.>

The paper deals with the issue of station delay in token-ring networks. It explains why one-bit-delay is the minimum possible delay at every station and shows that the station delay depends on the distributed computations performed in the ring. Then, the paper introduces the distributed priority mechanism for token-rings, as approved by the IEEE-802.5 standard. This mechanism attaches to the token, that circulates around the ring and controls the access to the shared medium, a priority field P and a reservation field R. These two fields work together in an attempt to match the service priority of the ring to the highest priority message that is waiting to be sent.It is shown that due to the computation restrictions imposed by the one-bit-delay requirements, this priority mechanism has a grave deficiency as follows. When the token priority is higher than the maximum reservation (P > R), the token should make up to P round-trips, where P is the number of priority levels, before P is reduced to R. During this time period, no station may seize the token and send a message. This leads to loss of bandwidth.The paper presents a new priority mechanism that retains the desired properties of the standard. However, in the new protocol when P > R holds, P is reduced to R in at most 1 round-trip rather than in up to P round-trips.

The authors consider a special case of multilink protocol, namely, a system consisting of two half-duplex parallel links that carry data in opposite directions between two nodes. They construct a protocol that simulates a full-duplex reliable link between the two nodes. Synchronization is achieved without resorting to the use of serial numbers. A validation proof of the protocol is provided. The design of the protocol exhibits an instance of the value of correctness proofs in the design process, as several successive protocols, discussed in the paper, were only found to be incorrect through the effort to prove them otherwise.>

A new scheme is presented that allows dynamic maintenance, allocation, and release of the isochronous bandwidth in integrated rings. The scheme is flexible since it permits the stations to bundle together several low-speed isochronous channels to form one high-speed isochronous channel. Acquiring isochronous channels by ring stations and releasing them are decentralized, cheap, fast, and simple processes. The overhead bandwidth required by the scheme is negligible. The allocation rate is not affected by the actual load in the ring. The main principle behind the new scheme is to divide the isochronous bandwidth into fixed length slots and to maintain the available channels in each slot as a linked list.>

The authors present a reliable protocol for setting up a tree connection for the purpose of multicast communication over a high-speed packet switched network. The tree connection is based on the use of local identifiers that are swapped at every intermediate node of the tree. Local identifiers are simple to manage, provide fast access to the routing tables, and are very efficient in terms of the size of the resulting routing space. The context of the present work is a high-speed network in which the local label swapping on data messages is performed in hardware by the switching subsystem, while the connection setup is done in software by the switch control subsystem. The correctness of the protocol is formally proved. The protocol ensures the integrity of the tree, and, when failures occur, the tree is gracefully degraded into a smaller tree.>

The problem of atomic commitment of a transaction in a distributed database is considered. This is a variant of the famous gossiping problem. Given a set of communication costs between pairs of participant sites, it is established that the necessary communication cost for any atomic commitment algorithm is twice the cost of a certain minimum spanning tree. This paper establishes the necessary communication time for any atomic commitment algorithm, given a set of communication delays between pairs of participant sites, and the time at which each participant completes its subtransaction. Then, it is determined that both lower bounds are also upper bounds in the following sense. There is an efficient (i.e., polynomial-time) algorithm that, in the absence of failures, has a minimum communication cost. There is another efficient algorithm that, in the absence of failures, has a minimum communication time. However, unless P = NP, there is no efficient algorithm which has a minimum communication complexity, namely, one for which the product of communication cost and communication time is minimum. Next, a simple, linear time, distributed algorithm, called TREE-COMMIT, whose communication complexity is not worse than p times the minimum complexity, where p is the number of participants, is presented. Finally, it is demonstrated that TREE-COMMIT is superior to the existing variants of the two-phase commit protocol.

The problem of slotted- and token-ring recovery from livelocks and deadlocks induced by transmission errors and station failures is discussed. The RE-protocol, an access protocol for slotted-rings that recovers from any combination of transmission errors and station failures in at most five ring revolutions, is presented. It is shown that the protocol requires no information about the current topology of the ring, like the number of stations or the ring revolution propagation time, it uses only two frame bits for access control, and it achieves minimum delay at the ring stations.>

The issue of routing in multiple-ring networks is considered. A new bridge protocol for route determination in a multiple-ring network is introduced. Its main advantage is its communication efficiency: the number of frames used is the number of rings plus the number of bridges in the network, as opposed to the exponential function needed by the existing protocol. Some extensions of the protocol are given. The correctness proof for the new protocol is presented.>

Protocols for establishing, maintaining and terminating connections in packet switched networks have been studied in the literature and numerous standards have been developed to address this problem. In this paper, we reexamine connection establishment in the context of a fast packet network with an integrated traffic load, explain why previously proposed solutions are inadequate and develop a protocol for connection establishment/takedown that is appropriate for such a network. The underlying model that we use is the recently developed PARIS network, though our ideas are sufficiently general to cover many other fast packet networking architectures.

The authors consider distributed algorithms that achieve transaction commitment at minimal communication cost but differ in the time it takes them to reach consensus. Based on this criterion, the authors define a 'better than' partial ranking of minimal-communication-cost algorithms. They also discuss alternatives of a simple, minimal-communication-cost algorithm introduced previously, called TREE-COMMIT.>

In computer networks with decentralized control, it is necessary to provide a directory service which enables users to discover dynamically the location of other users. The authors examine the protocols for maintaining consistent directory information for casually connected users that can connect and disconnect from the network at will. They propose protocols for both hierarchical and nonhierarchical directory systems. The protocols do not rely on sequence numbers and consequently do not require 'safe store' at the user.>

It is known that HDLC (high-level data link control) and other bit-oriented DLC procedures ensure data transmission reliability across noisy transmission media, provided that all frame errors are detected and the link processes are synchronized at initialization. It is shown that the HDLC initialization procedure does not ensure synchronization and allows inadvertent loss of data. Several link initialization procedures are proposed and it is proved that they do ensure synchronization.>

We consider the communication protocol for transaction commitment in a distributed database. Specifically, the connection between the structure of communication among the participating sites, and the communication network topology is investigated. In order to do so, the cost of transaction commitment is defined as the number of network hops that messages of the protocol must traverse. We establish the necessary cost for transaction commitment, and show that it is also sufficient. A simple distributed algorithm is presented to prove sufficiency. Our algorithm is also time-efficient, and in order to prove that we show that the timing of our algorithm is optimal within a natural class of commit-protocols.

In this paper we consider the problem of dynamically assigning addresses to stations attached to a broadcast network. We present a distributed protocol which guarantees that a new station will eventually be assigned an address if one is free, and furthermore, that no two stations on the network will have the same address. We show how the protocol can be simplified in certain specific environments.

The paper introduces a reliable distributed procedure for establishing and cancelling routes in a circuit-switched data network that uses local path identifiers (LPID). The procedure ensures that the route is set up properly unless a failure is encountered, data messages are delivered to their destinations unless they encounter a cancellation process and the route is cancelled, and all LPID entries are released after a failure or session completion.

In computer communication networks, routing is often accomplished by maintaining copies of the network topology and dynamic performance characteristics in various network nodes. The present paper describes an algorithm that allows complete flexibility in the placement of the topology information. In particular, we assume that an arbitrary subset of network nodes are capable of maintaining the topology. In this environment, protocols are defined to allow automatic updates to flow between these more capable nodes. In addition, protocols are defined to allow less capable nodes to report their topology data to the major nodes, and acquire route information from them.

A two-node packet-radio network with infinite buffers at the nodes is considered. The two nodes transmit data packets to a common station through a shared radio channel. One of the two nodes is granted full access rights to the channel, while the other node bases its decisions whether to transmit or not on the acknowledgments it receives about its transmissions. For this acknowledgment-based access scheme and for general arrival processes, we derive the joint generating function of the queue contents in steady state, as well as the condition for steady state. From the generating function, any moment can be derived, as well as average time delays. Numerical results are presented for independent Bernoulli arrival processes.

A two-hop packet radio network consisting of three nodes is considered. The three nodes have infinite buffers and share a common radio channel for transmitting their packets. Two of the nodes forward their packets to a third node that acts as a source of data as well as a relay that forwards all the packets entering the network to a main station. We assume that two of the nodes are granted full rights in accessing the channel while the third node uses a random access scheme. For this network we derive the condition for steady state and the generating function of the joint queue length distribution at the nodes in steady state. We also give several numerical examples and compare the performance of the network with and without a relay node.

Broadcast in a communication network is the delivery of copies of messages to all nodes. A broadcast protocol is reliable if all messages reach all nodes in finite time, in the correct order and with no duplicates. The present paper presents an efficient reliable broadcast protocol.

We consider several classes of interfering queues that appear in packet-radio networks. We analyze the class of systems where one of the queues is given full priority and obtain an expression for the joint probability distribution of the queue lengths. For ALOHA-type systems with two symmetric queues we calculate the average packet waiting time and queue lengths, and for symmetric systems with an arbitrary number of subscribers we develop a method to approximate these quantities. The approximation turns out to be close to the analysis and simulation results.

A unified approach to the formal description and validation of several distributed protocols is presented. After introducing two basic protocols, a series of known and new protocols for connectivity test, shortest path, and path updating are described and validated. All protocols are extended to networks with changing topology.

Abstract This article presents three protocols for obtaining maximum flow in a network by using distributed computation. Each node in the network has memory and processing capabilities and coordinates the algorithm with its neighbors by means of control messages. In the order presented, each protocol employs less communication than the previous one, but requires more time and node computation.

Two new versions of a distributed protocol for establishing and maintaining loop-free routing tables for communication networks with changing topology are presented. The protocols here possess significant advantages over previous versions in terms of complexity of the node algorithm and of the validation procedure, as well as the communication and storage needs. In addition, we present a procedure for establishing new and disrupted calls in a virtual or physical circuit-switched network, and for canceling existing calls, such that each call is loop-free and is established according to the routing tables provided by the protocol.

Previous distributed routing protocols in data-communication networks that achieve minimum average delay are extended to take into consideration topological changes in the network.

An algorithm for constructing and adaptively maintaining routing tables in communication networks is presented. The algorithm can be employed in message as well as circuit switching networks, uses distributed computation, provides routing tables that are loop-free for each destination at all times, adapts to changes in network flows, and is completely failsafe. The latter means that after arbitrary failures and additions, the network recovers in finite time in the sense of providing routing paths between all physically connected nodes. For each destination, the routes are independently updated by an update cycle triggered by the destination.

An algorithm that provides minimum delay routing in a data communication network using virtual line-switching is presented. The algorithm uses distributed computation in the sense that the nodes of the network update their information in an orderly fashion based on messages received from their neighbors. Receipt of these messages also triggers the various steps of the update and rerouting, so that these operations are performed in appropriate sequencing. For stationary input requirements and fixed topology the algorithm reduces network delay at each step and provides loop-free routing in the network. The method also provides an algorithm for quasi-static routing, when the input flows are slowly changing.

Basic analytical models for problems of dynamic and quasi-static routing in data-communication networks are introduced. The models are intended to handle the quantities of interest in an algorithmic form, and as such require only a minimal number of assumptions. Control and estimation methods are used to construct algorithms for the solution of the routing problem.

This paper considers the problem of efficient transmission of vector sources over a digital noiseless channel. It treats the problem of optimal allocation of the total number of available bits to the components of a memoryless stationary vector source with independent components. This allocation is applied to various encoding schemes, such as minimum mean-square error, sample-by-sample quantization, or entropy quantization. We also give the optimally decorrelating scheme for a source whose components are dependent and treat the problems of selecting the optimum characteristic of the encoding scheme such that the overall mean-squared error is minimized. Several examples of encoding schemes, including the ideal encoder that achieves the rated istortion bound, and of sources related to a practical problem are discussed.

We describe the role of various stochastic processes, especially martingales and related concepts, in estimation theory. It is shown, in the simplest context, that in nonlinear estimation theory martingales play the same fundamental role as uncorrelation and white noise do in linear estimation.

The paper presents models for discrete-time point processes (DTPP) and schemes for recursive estimation of signals randomly influencing their rates. Although the models are similar to the better known models of signals in additive Gaussian noise, DTPP differ from these in that it is possible for DTPP's to find recursive representations for the nonlinear filters. If the signal can be modeled as a finite state Markov process, then these representations reduce to explicit recursive finite-dimensional filters. The derivation of the estimation schemes, as well as the filters themselves, present a surprising similarity to the Kalman filters for signals in Gaussian noise. We present finally an application of the estimation schemes derived in the paper to the estimation of the state of a random time-division multiple access (ALOHA-type) computer network.

In analogy with the Wiener-Itô theory of multiple integrals and orthogonal polynominals, a set of functionals of general square-integrable martingales is presented which, in the case of independent-increments processes, is orthogonal and complete in the sense that everyL^{2}-functional of the independent-increment process can be represented as an infinite sum of these elementary functionals. The functionals are iterated integrals of the basic martingales, similar to the multiple iterated integrals of Itô and can be also thought of as being the analogs of the powers1,x,x^{2}, \cdotsof the usual calculus. The analogy is made even clearer by observing that expanding the Doleans-Dade formula for the exponential of the process in a Taylor-like series leads again to the above elementary functionals. A recursive formula for these functionals in terms of the basic martingale and of lower order functionals is given, and several connections with the theory of reproducing kernel Hilbert spaces associated with independent-increment processes are obtained.

We apply some recent results in martingale theory and the innovations method to obtain the evolution of the conditional mean and conditional density of a process that modulates the rate of a counting process.

We treat the problem of modeling events happening randomly in time at a rate determined by some other random "signal" process. It is shown that a martingale model includes all previously proposed models for such problems and also covers the difficult case of "past-dependent" signals that arises in feedback communication and control problems. It turns out that this model is very similar to the well-known signal-in-additive-white-Gaussian-noise model, so that it can be used conveniently in solving problems of detection of signals in jump processes and estimation of signals from jump processes.