Low overhead analysis of large distributed data sets is necessary for current data centers and for future sensor networks. In such systems, each node holds some data value, e.g., a local sensor read, and a concise picture of the global system state needs to be obtained. In resource-constrained environments like sensor networks, this needs to be done without collecting all the data at any location, i.e., in a distributed, manner. To this end, we define the distributed classification problem, in which numerous interconnected nodes compute a classification of their data, i.e., partition these values into multiple collections, and describe each collection concisely.

Celeste is a robust peer-to-peer object store built on top of a distributed hash table (DHT). Celeste is a working system, developed by Sun Microsystems Laboratories. During the development of Celeste, we faced the challenge of complete object deletion, and moreover, of deleting "files" composed of several different objects. This important problem is not solved by merely deleting meta-data, as there are scenarios in which all file contents must be deleted, e.g., due to a court order. Complete file deletion in a realistic peer-to-peer storage system has not been previously dealt with due to the intricacy of the problem - the system may experience high churn rates, nodes may crash or have intermittent connectivity, and the overlay network may become partitioned at times. We present an algorithm that eventually deletes all file content, data and meta-data, in the aforementioned complex scenarios. The algorithm is fully functional and has been successfully integrated into Celeste

Although many wireless channel-state dependent (CSD) schedulers have been proposed recently, their contributions lie in the design of the scheduling mechanism to meet some performance objectives. However, these objectives are often first-order statistics such as average or worst-case delay, which are insufficient to characterize the scheduler's performance. In this paper, we propose a matrix formulation to derive the delay probability density function for CSD schedulers over a Markovian wireless channel. Our analysis is then used to determine the admissibility of a wireless scheduler in terms of a minimum throughput requirement and a real-time QoS requirement. In addition, we evaluate the buffer size requirement of the wireless receiver and highlight the trade-off between buffer size requirements and channel efficiency.

Abstract In the last few years, wireless scheduling algorithms have been proposed by supplementing wireline scheduling algorithms with a wireless adaptation scheme. However, Quality of Service (QoS) bounds have either been derived for flows that perceive error‐free conditions or a static worst‐case channel condition. Such an assumption of the channel condition is unrealistic, since channel errors are known to be bursty in nature. Hence, these bounds are inadequate to characterize the scheduler's QoS performance. Our research focuses on performing an extensive analysis of wireless scheduling in order to derive statistical QoS performance bounds under realistic channel conditions. In this paper, we develop stochastic models for various wireless schedulers. Based on these models, we define and evaluate statistical QoS performance metrics in terms of throughput, delay and fairness under various channel conditions and over different time scales. Numerical results indicate that no single scheduler outperforms the others in terms of all the QoS metrics under all channel conditions. The choice of an optimal scheduling mechanism depends on the priority of QoS requirements as well as the channel conditions. Copyright © 2004 John Wiley & Sons, Ltd.

We develop Markov models for various schedulers in order to evaluate their performance tradeoffs at wireless links. While FIFO scheduling aggregates flows into a single flow just prior to the wireless link, channel-state dependent (or CSD) schedulers maintain a queue for each flow, and use predicted channel information to make scheduling decisions. We present results of tradeoffs in terms of overall throughput and per-flow QoS performance obtained with each scheduler under different channel conditions.

Cable networks have evolved from offering broadcast services to providing high rate two-way data services. In the next step, cable operators intend to use voice over IP (VoIP) to provide cable telephony services. In a cable network the users are connected to the headend through a cable modem. The headend is responsible for allocating upstream bandwidth to the various cable modems. Each cable modem has access to several upstream channels but can use only one upstream channel at any given time. The headend can direct a modem to switch from one upstream channel to another. We consider the problem of scheduling packet telephony calls in a cable network. We show that the scheduling problem is NP-hard even in the case where all the calls have the same characteristics. We then suggest several approximation algorithms for the problem and investigate their performance. We address the problem of maintaining the tolerated jitter when switching a modem from one channel to another and explore the effect of the tolerated jitter on the performance of the scheduling algorithms. We show that the ability to switch channels considerably improves the performance of the scheduling algorithms.

This paper presents an architecture and algorithms for optimizing the performance of Web services. For a given service, session-based admission control is combined with stage-wise request queuing, where the stages represent sub-tasks within sessions. The scheduling of requests is governed by generalized processor sharing. We present a performance model, relying on online estimation of parameters describing client-server interaction. A reward function corresponding to the service provider's objective is maximized using techniques for nonlinear optimization. In a case study, we model and optimize the resource sharing at a Web server hosting an electronic store. The performance advantages of our approach are quantified numerically, and the robustness to parameter estimation errors is assessed by sensitivity analysis.

We investigate a scheduling problem in a TDMA environment where packets may be fragmented. Our model of the problem is derived from a scheduling problem present in data over CATV networks, where a slotted TDMA channel is used to carry both real-time and best-effort traffic. Packets of real-time flows have high priority and are allocated in fixed, periodically located slots. Best-effort packets have lower priority and must therefore use the remaining slots. The scheduling problem tackles the assignment of variable size best-effort packets into the free slots which are left between successive allocation of real-time packets. One of the capabilities of the system is the ability to break a packet into several fragments. But, when a packet is fragmented, extra bits are added to the original packet to enable the reassembly of all the fragments. We transform the scheduling problem into a variant of bin packing where items may be fragmented. When an item is fragmented overhead units are added to the size of every fragment. The overhead associated with fragmentation renders the optimization problem NP-hard; therefore, an approximation algorithm is needed. We define a version of the well-known Next-Fit algorithm, capable of fragmenting items, and investigate its performance. We present both worst case and average case results and compare them to the case where fragmentation is not allowed.

The Data Over Cable Systems Interface Specification (DOCSIS) is the leading standard for data over cable networks. We consider the problem of scheduling constant bit rate (CBR) flows in a DOCSIS compliant cable network. CBR flows are required to support the delivery of voice and other real-time applications that generate fixed size data packets on a periodic basis. The primary application of CBR flows is voice over IP (VoIP) which cable operators intend to use in order to provide cable telephony services. DOCSIS 1.1 is enhanced with quality of service (QoS) capabilities; it defines the unsolicited grant service as the mechanism for supporting CBR flows. The scheduling algorithms, however, are not defined by the standard. We present the scheduling problem and examine several interesting special cases of it. We show that deciding whether a set of CBR flows can be legally scheduled is NP-complete whenever there are two or more different grant intervals. We model the scheduling problem as a variant of bin packing where bin sizes can be modified in a constrained manner This model enables the development of scheduling algorithms which are based on known algorithms for bin packing. We present an algorithm based on the next-fit algorithm and investigate its performance. We show that under certain assumptions which typically hold for VoIP and many other practical applications, a simple polynomial time scheduling algorithm is sufficient.

IP multicast is becoming the emerging infrastructure for mass delivery of information. We show that there are certain deterministic methods, namely the reactive window and the proactive window, that guarantee implosion avoidance and provide exposure control, without incurring the overhead of excessive state and timer-based maintenance associated with probabilistic schemes. In order to demonstrate their associated performance advantages, we use both methods for building a simple reliable multicast protocol termed SDMP (scalable dissemination multicast protocol) and compare its performance with PGM (pragmatic general multicast), a protocol that uses probabilistic methods of de-synchronization. Our protocol SDMP: (a) takes advantage of spatial and temporal correlation of network events to deterministically control feedback implosion; (b) uses unicast feedback and hybrid unicast/subcast retransmissions to control delivery accuracy and exposure, thus conserving network bandwidth; (c) provides shorter arrival and recovery latencies; (d) makes use of network-based processing to detect losses and react on behalf of affected receivers; (e) accommodates local-recovery extensions; (f) has formal proof of correctness.

Most of the web traffic today uses the HyperText Transfer Protocol (HTTP), with Transmission Control Protocol (TCP) as the underlying transport protocol. Unfortunately, TCP is poorly suited for the short conversations that comprise a significant component of web traffic. The overhead of setting up and tearing down TCP state amortizes poorly for these small connections. Moreover, emerging modern web server systems employ HTTP redirection for server load-balancing and content distribution; such schemes require setting up (and tearing down) multiple TCP connections for servicing a single client request. We have designed and analyzed a hybrid scheme to address these issues. The scheme uses either TCP, or the User Datagram Protocol (UDP) as the underlying transport protocol for carrying web traffic. UDP is used for short transfers (including HTTP redirection), while TCP is used for all other transfers. In this manner, we avoid the extra TCP overhead for short connections, but still benefit from the reliable delivery and congestion control that TCP provides. We ran trace-based simulations to quantify the effects of various network parameters (i.e., packet loss rates) on the performance of the hybrid scheme. We observed performance gains exceeding 20-25% with HTTP/1.1-style persistent connections, and over 40-50% without persistent connections. These gains can be improved with further performance optimizations that we describe.

In connection-oriented networks, resource reservations must be made before data can be sent along a route. For short or bursty connections, a selected route must have the required resources to ensure appropriate communication with regard to desired quality-of-service (QoS). For example, in ATM networks, the route setup process considers only links with sufficient resources and reserves these resources while it advances toward the destination. The same concern for QoS routing appears in datagram networks such as the Internet, when applications with QoS requirements need to reserve resources along pinned routes. In this paper, we analyze the performance of multi-path routing algorithms and compare them to single-path reservation that might be persistent, i.e., retry after a failure. The analysis assumes that the routing process reserves resources while it advances toward the destination, thus there is a penalty associated with a reservation that cannot be used. Our analysis shows that while multi-path reservation algorithms perform comparably to single-path reservation algorithms, either persistent or not, the connection-establishment time for multi-path reservation is significantly lower. Thus, multi-path reservation becomes an attractive alternative for interactive applications such as World Wide Web browsing.

We propose and analyze a specific set of access rules, or "spectrum etiquette", for the 59-64 GHz unlicensed band to allow systems from different manufacturers with different physical and medium-access control protocols to co-exist, sharing the large available bandwidth without interference. The proposed etiquette is unique in that heterogeneous systems are able to co-exist with one another without monitoring the entire band by means of transmissions over a common, narrow band control channel used to establish collision-free transmission schedules over the channels allocated for data transmission within the 59-64 GHz band. Because no common physical layer can be assumed among different systems, the control channel is needed for the systems to schedule transmissions in the rest of the band, and the only means by which systems can communicate with one another over the control channel is the duration of each others' transmissions, which are perceived only as noise. A transmission encoding is defined based on this basic feedback to allow systems to ascertain which system can use which data channel at which time without interference. Analytical and simulation results are presented showing that the proposed etiquette is fair to all the co-existing systems, fully utilizes the spectrum, provides bounded delays for data-channel acquisition time by any given system, and provides minimum channel-use guarantees.

ATM networks are moving to a state where large production networks are deployed and require a universal, open and efficient ATM network control platform (NCP). The emerging PNNI (Private Network to Network Interface) standard introduces an internetworking architecture which can also be used as an intranetwork interface. However, PNNI fails in the latter due to performance limitations, limited functionality and the lack of open interfaces for functional extensions. OPENET is an open high-performance NCP based on performance and functional enhancements to PNNI. It addresses the issues of scalability, high performance and functionality. OPENET focuses on intranetworking and is fully compatible with PNNI in the internetwork environment. The major novelties of the OPENET architecture compared to PNNI is its focus on network control performance. A particular emphasis is given to the increase of the overall rate of connection handling, to the reduction of the call establishment latency and to the efficient utilization of the network resources. These performance enhancements are achieved by the use of a native ATM distribution tree for utilization updates, lightweight signalling and extensive use of caching and pre-calculation of routes. OPENET also extends PNNI functionality. It utilizes a new signalling paradigm that better supports fast reservation and multicast services, a control communication infrastructure which enables the development of augmented services such as directory, hand-off, billing, security etc. OPENET was implemented by the High-Speed Networking group at Sun Labs and is under operational tests.

Networked applications generate messages that are segmented into smaller, fixed or variable size packets, before they are sent through the network. In high-speed networks, acknowledging individual packets is impractical; so when congestion builds up and packets have to be dropped, entire messages are lost. For a message to be useful, all packets comprising it must arrive successfully at the destination. The problem is therefore which packets to discard so that as many complete messages are delivered, and so that congestion is alleviated or avoided altogether. Selective discarding policies, as a means for congestion avoidance, are studied and compared to nondiscarding policies. The partial message discard policy discards packets of tails of corrupted messages. An improvement to this policy is the early message discard that drops entire messages and not just message tails. A common performance measure of network elements is the effective throughput which measures the utilization of the network links but which ignores the application altogether. We adopt a new performance measure-goodput-which reflects the utilization of the network from the application's point of view and thus better describes network behavior. We develop and analyze a model for systems which employ discarding policies. The analysis shows a remarkable performance improvement when any message-based discarding policy is applied, and that the early message discard policy performs better than the others, especially under high load. We compute the optimal parameter setting for maximum goodput at different input loads, and investigate the performance sensitivity to these parameters.

In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM networks is an example of an algorithm that does this using a sequential crank-back mechanism. We suggest the implementation of resource reservation along several routes in parallel. We present an analytical model that demonstrates that when there are several routes to the destination it pays to attempt reservation along more than a single route. Following this analytic observation, we present a family of algorithms that route and reserve resources along parallel subroutes. The algorithms of the family represent different trade-offs between the speed and the quality of the established route. The presented algorithms are simulated against several legacy algorithms, including the PNNI crank-back, and exhibit higher network utilization and faster connection set-up time.

Selective discarding policies, as a means for congestion avoidance, are studied and compared to non-discarding policies. The partial message discard policy discards the packets of the tails of corrupted messages. An improvement to this policy is the early message discard that drops entire messages and not just message-tails. A common performance measure of the network elements is the effective throughput which measures the utilization of the network links but which neglects the application altogether. We adopt a new performance measure, goodput, which reflects the utilization of the network from the application's point of view and thus better describes the network behavior. We develop and analyze a model for systems which employ discarding policies. The analysis shows a remarkable performance improvement when any message-based discarding policy is applied, and that the early message discard policy performs better, especially under high loads. We compute the optimal parameter setting for maximum goodput at different input loads and investigate the performance sensitivity to these parameters.

The packet fragmentation problem in computer networks is that of breaking a packet into smaller pieces (fragments) due to packet-size limitations along the packet's route. This is a typical internetworking problem. We show that the commonly used simplistic approach whereby the routing and fragmentation functions operate completely independently is far from being efficient and has adverse effects on network performance. This paper deals with the combined fragmentation-and-routing problem. We discuss several possible fragmentation machines and indicate their equivalence. This enables the formulation of a comprehensive yet tractable flows model, whose performance measure is total network delay. An analysis of this model leads to necessary and sufficient optimality conditions for the fragmentation-and-routing problem. The optimality conditions serve as a base line for devising several optimal algorithms, both centralized and distributed. To deal with minimum first derivative length algorithms, we generalize the concept of minimum first derivative paths in order to accommodate them into our environment. Several special cases of practical interest are discussed. We show how the problem size and the running time of the algorithms are considerably shortened in networks in which packet sizes come in a limited number of sizes. We also show how our approach can accommodate performance measures other than total delay. The case of networks with virtual circuits is also discussed. © 1997 John Wiley & Sons, Inc.

Modern fast packet switching networks are being forced to rethink the routing schemes that are used in more traditional networks. The reexamination is necessitated because in these fast networks switches on the message's route can afford to make only minimal and simple operations. For example, examining a table of a size proportional to the network size is out of the question. We examine routing strategies for such networks based on flooding and predefined routes. Our concern is to get both efficient routing and an even (balanced) use of network resources. We present efficient algorithms for assigning weights to edges in a controlled flooding scheme but show that the flooding scheme is not likely to yield a balanced use of the resources. We then present efficient algorithms for choosing routes along: bfs trees and shortest paths. We show that in both cases a balanced use of network resources can be guaranteed.

Multicasting is a communication mode in which a given source communicates with a subset of the entire network user population. Previous work in this area concentrated on the multicast problem of a single source that always communicates with the same destination group. In this paper we investigate a more natural case of multicast communication where a single source communicates with several different destination groups. Specially, we focus on the design and analysis of multicast data link protocols for this environment. Straightforward implementations of such protocols are inappropriate in the case of a large destination population, as a source will have to store a large amount of state information even if it maintains only a single variable per destination. In most typical applications, though. The total destination population is large, the number of destinations that any given source is in conversation with, is typically small. We propose a framework for adapting protocols so that memory requirement does not grow with the total destination population but depends upon the number of destinations actually in communication with the source. The savings in memory are achieved by slightly increasing the amount of communication. We address the performance of such a protocol in an environment of a broadcast channel. We analyze several strategies and control techniques and demonstrate the tradeoff between throughput and the amount of memory.>

The capacity of the M-user binary adder channel, subjected to various restrictions of physical nature, is investigated. The underlying propagation media considered are (i) fiber-optic, with lossless coupling and Poisson statistics, (ii) radio, under Rayleigh fading, and (iii) radio with constant amplitudes and random phases. Whereas the capacity of the unrestricted (ideal) model for the binary adder channel is known to increase without limit with the number of users, it is shown in the present paper that, for each of these cases, the total capacity is upper-bounded by a constant independent of the number of users: in case (i) by 1.7Q/sub T/ bits per channel use, where Q/sub T/ is the parameter of the Poisson process, in case (ii) by 4.33 bits per channel use, and in case (iii) by 4.27 bits per channel use.>

The combined fragmentation-and-routing problem is addressed. Several possible fragmentation machines are discussed, and their equivalence is indicated. This allows the formulation of a comprehensive yet tractable flow model, whose performance measure is total delay. An analysis of this model leads to necessary and sufficient optimality conditions for the fragmentation-and-routing problem. The optimality conditions serve as a baseline for devising several optimal algorithms, both centralized and distributed. In order to deal with minimum first derivative length algorithms, the concept of minimum first derivative paths is generalized in order to accommodate them in the environment used. Several special cases of practical interest are discussed. It is shown the problem size and the running time of the algorithms are considerably shortened in networks in which packet sizes come in a limited number of sizes. The approach can accommodate performance measures other than total delay.>

A communication network shared by several selfish users is considered. Each user seeks to optimize its own performance by controlling the routing of its given flow demand, giving rise to a noncooperative game. The Nash equilibrium of such systems is investigated. For a two-node multiple-link system, the uniqueness of the Nash equilibrium is proved under reasonable convexity conditions. It is shown that this Nash equilibrium point possesses interesting monotonicity properties. For general networks, the uniqueness of the Nash equilibrium is established under various assumptions.>

Consider M-Choose-T communications: T users or less, out of M potential users, are chosen at random to simultaneously transmit binary data over a common channel. A method for constructing codes that achieve error-free M-Choose-T communication over the noiseless adder channel (AC), at a nominal rate of 1/T bits per channel symbol per active user, is described and an efficient decoding procedure is presented. The use of such codes is referred to as forward collision resolution (FCR), as it enables correct decoding of collided messages without retransmissions. For any given T a code is available that yields a stable throughput arbitrarily close to 1 message/slot. Furthermore, if the occurrence of collisions is made known to the transmitters, such a throughput can be maintained for arbitrary T,T>

The authors consider the problem of traveling with least expected delay in networks whose link delays change probabilistically according to Markov chains. This is a typical routing problem in dynamic computer communication networks. Several optimization problems, posed on infinite and finite horizons, are formulated, and they are considered with and without using memory in the decision-making process. It is proved that all these problems are, in general, intractable. However, for networks with nodal stochastic delays, a simple polynomial optimal solution is presented. This is typical of high-speed networks, in which the dominant delays are incurred by the nodes. For more general networks, a tractable in -optimal solution is presented.>

The authors consider a communication network shared by several selfish users. Each user seeks to optimize its own performance by controlling the routing of its given flow demand, giving rise to a noncooperative game. They investigate the Nash equilibrium of such systems. For a two-node multiple links system, uniqueness of the Nash equilibrium is proven under reasonable convexity conditions. It is shown that this Nash equilibrium point possesses interesting monotonicity properties. For general networks, these convexity conditions are not sufficient for guaranteeing uniqueness, and a counterexample is presented. Nonetheless, uniqueness of the Nash equilibrium for general topologies is established under various assumptions.>

The authors examine routing strategies for fast packet switching networks based on flooding and predefined routes. The concern is to get both efficient routing and an even balanced use of network resources. They present efficient algorithms for assigning weights to edges in a controlled flooding scheme but show that the flooding scheme is not likely to yield a balanced use of the resources. Efficient algorithms are presented for choosing routes along breadth-first search trees and shortest paths. It is shown that in both cases a balanced use of network resources can be guaranteed.>

IP is the basic protocol in the Internet. The authors explore a variety of possibilities to adapt the wireless environment to that of IP. They describe the requirements and show how these can be accommodated by using the existing IP. At the heart of the problem is the lack of a capability in the current IP routing services to track topological changes. Several alternatives are described, each making use of a different combination of the addressing and routing features offered by IP. The alternatives are compared. The tradeoffs among these alternatives are explored.>

The authors consider the problem of traveling with least expected delay in networks whose link delays change probabilistically according to Markov chains. This is a typical routing problem in dynamic computer communication networks. They formulate several optimization problems, posed on infinite and finite horizons, and consider them with and without using memory in the decision making process. It is proved that all these problems are, in general, intractable. However, for networks with nodal stochastic delays, a simple polynomial optimal solution is presented. This is typical of high-speed networks, in which the dominant delays are incurred by the nodes. For more general networks, a tractable epsilon -optimal solution is presented. The performance of a regular shortest-path algorithm in such an environment is considered.>

Abstract We investigate the minimum weight path problem in networks whose link weights and link delays are both functions of time. We demonstrate that, in general, there exist cases in which no finite path is optimal leading us to define an infinite path (naturally, containing loops) in such a way that the minimum weight problem always has a solution. We also characterize the structure of an infinite optimal path. In many practical cases, finite optimal paths do exist. We formulate a criterion that guarantees the existence of a finite optimal path and develop an algorithm to find such a path. Some special cases, e.g., optimal loopless paths, are also discussed.

A family of automatic repeat request (ARQ) protocols that can be implemented through relatively simple hardware (one or more first in, first out, or FIFO, buffers and some limited state information) is considered. With a single FIFO buffer, the protocol is identical to a regular go-back-N. By increasing the number of FIFO buffers, a full selective repeat can be reached. The main result is to show that, for typical error rates, performance close to selective repeat can be obtained with two or three FIFO buffers. The family of protocols is described in detail, and the throughput is analyzed. For the two-buffer case, a closed-form solution is obtained, while for other cases, simulation results are given.>

In this paper the shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered. Algorithms for finding the shortest path and minimum delay under various waiting constraints are presented and the properties of the derived path are investigated. It is shown that if departure time from the source node is unrestricted, then a shortest path can be found that is simple and achieves a delay as short as the most unrestricted path. In the case of restricted transit, it is shown that there exist cases in which the minimum delay is finite, but the path that achieves it is infinite.

The multiple-access problem is addressed from the combined standpoint of both coding and scheduling to arrive at a stable, highly efficient access scheme for the binary adder channel. The authors define a system model that includes the channel and the coding mechanism and explain the M-choose-T communication mode which is fundamental to their method. They then address the system's performance and show that high throughput (arbitrarily close to 1) is achieved while the access remains stable. They also investigate the average message delay.>

A single-facility dynamic-network location problem with a continuous (rather than discrete) time domain is considered. It is assumed that the network state changes constantly and thus at each moment a different point may be the best choice for facility location. The cost of switching the facility from one node to another is taken into account because this switching consumes resources (although switching does not necessarily involve physical relocation, the cost results from the need to relocate the function). These costs are assumed to be time-dependent.>

The authors consider the shortest-path problem in networks in which the length (or weight) of the edges change with time according to arbitrary functions. They present algorithms for finding the shortest-path and minimum-delay under various waiting constraints and investigate the quality of the derived path. They also show that if departure time from the source node is unrestricted and delay functions are continuous then a shortest path can be found that is simple and achieves a delay as short as the most unrestricted strategy. The optimal waiting time for such cases is also computed. In more restricted transit, it is shown that there exist cases where the minimum delay is finite yet the path that achieves it is infinite.>

Multihoming in networks, i.e. attaching a subscriber to more than a single access point in the network, is a mechanism used to improve performance. The authors take the topological design view and address the problem of finding optimal multihoming configurations for several topological design criteria. They analyze the problem and demonstrate that except for dual homing, multihoming is algorithmically complex. Optimal algorithms based on maximum matching in graphs and 0-1 integer programming are given for all cases.>

A distributed algorithm to reconfigure a double-loop token-ring local area network following topological changes is presented. Each node, upon detection of a broken link, attempts to use another link, and when this is not possible it connects its input and output lines to form a loopback. The nodes communicate only with their neighbors and base their actions on the messages they receive and on their local observations. The algorithm guarantees that at all times the network is organized to provide maximum possible connectivity among the nodes-either one loop that encompasses all nodes in the network or several subloops, each of which operates as a separate token-ring network. Tokens are generated or eliminated as necessary to result in one and only one token in each (sub)loop. The algorithm is formally specified and its properties are verified.>

Packet duplication is discussed as a means of increasing network reliability in an environment where packet loss exists. Several methods of routing the duplicates are presented, one of which-the st-numbering-is shown to have the combined advantage of using disjoint paths and more even utilization of network resources. An additional mechanism, deliberate packet elimination, is introduced as a means of controlling congestion that may result, in part, from the duplication. A comprehensive model is defined encompassing the process of packet duplication together with both forms of packet elimination. Within this model, a cost function based on average packet delay is defined. A quasi-static distributed algorithm is developed that is optimal, deadlock free, and loop free. Extension of the model to include packet retransmission is considered.>

End-to-end protocols in computer networks in which the topology changes with time are investigated. A protocol that delivers all packets ordered, without duplication, and which uses a window is presented. Using a precise model of the network correctness of the protocol is proven. The use of the window for flow control is also addressed.

This paper describes distributed algorithms enabling subscribers of a cable network to determine their relative position on the cable.As a side effect, these algorithms can be used to compute the number of subscribers.Knowledge of both the number and order of subscribers can be used to enhance network performance.

The number of n-bit words with a given longest run of 1's is computed. A relation between these numbers and the Fibonacci numbers is outlined and investigated.

Host-to-host protocols capable of supporting internetworking and reliable transmission have been under development for several years. This paper discusses problems and techniques related to one type of reliable protocol, which features end-to-end positive acknowledgement, retransmission, internetwork addressing capabilities, and ordered delivery.

Cepstral analysis has been used in speech processing for some time, but in the field of image processing very little attention has been paid to it. Some properties of the two-dimensional cepstrum (especially those absent in the one-dimensional) appear to make it an important tool in image processing. In this correspondence these properties are summarized. Applications to image deblurring (blur identifying) and image classification are mentioned as some possible uses.