Network configurations are regularly updated in response to issues such as congestion, failures, network changes, and modifications to security policies. We present a simple distributed algorithm for network update that operates on the fly and in place, and guarantees strong route-consistency. Existing methods are either weakly consistent, or do not operate in place and require excessive memory.

Softwarization enables tremendous flexibility for networks as the use of software-defined networking (SDN) and programmable data planes (e.g. P4) together support dynamic reconfiguration of networks in real-time, in response to network conditions and new service requests. In such networks, it is imperative to ensure that end-to-end network services continue to satisfy SLAs, especially performance requirements. However, in the presence of unpredictable dynamics due to network reconfigurations, it is not possible to guarantee prior to deployment that a service will meet such SLAs. Run-time verification - in combination with programmable control and data plane monitoring - can provide a basis for detecting potential performance SLA violations, together with identifying and executing appropriate network mitigations. In this paper, we propose a verification transverse based on formal specifications, that spans performance SLAs across the distributed SDN control and programmable data planes, and can coordinate with both planes to execute dynamic reconfiguration that mitigate the detected issues. We demonstrate a proof-of-concept prototype based on an extension of the Aerial run-time verification tool, together with the Inband Network Telemetry (INT) capability, on a network running distributed ONOS controllers together with a P4 data plane.

The rapid growth in multimedia traffic is straining mobile networks thus necessitating the need for efficient content delivery mechanisms. In this paper we present the design and analysis of a scheme for streaming non-live, pre-recorded content (e.g. Video on Demand) that opportunistically takes advantage of the “slow fading” variations in the wireless link quality. The proposed scheme works by selectively sending more content to sessions at times when they have better link quality while providing sufficient rate guarantees to keep their buffers from under-flowing. We establish analytically that the performance of such scheme is within two times that of any optimal scheme and that it results in throughput gains, per user and aggregate, that increase in proportion to the number of streaming users. Our performance evaluations indicate that by exploiting slow time-varying channels the streaming capacity can more than double with significant benefits to the users at the edge of the cell.

Multicast is an efficient means of transmitting the same content to multiple receivers while minimizing network resource usage. Applications that can benefit from multicast such as multimedia streaming and download, are now being deployed over 3G wireless data networks. Existing multicast schemes transmit data at a fixed rate that can accommodate the farthest located users in a cell. However, users belonging to the same multicast group can have widely different channel conditions. Thus existing schemes are too conservative by limiting the throughput of users close to the base station. We propose two proportional fair multicast scheduling algorithms that can adapt to dynamic channel states in cellular data networks that use time division multiplexing: inter-group proportional fairness (IPF) and multicast proportional fairness (MPF). These scheduling algorithms take into account (1) reported data rate requests from users which dynamically change to match their link states to the base station, and (2) the average received throughput of each user inside its cell. This information is used by the base station to select an appropriate data rate for each group. We prove that IPF and MPF achieve proportional fairness among groups and among all users inside a cell respectively. Through extensive packet-level simulations, we demonstrate that these algorithms achieve good balance between throughput and fairness among users and groups.

Effective mechanisms for detecting and thwarting distributed denial-of-service (DDoS) attacks are becoming increasingly important to the success of today's Internet as a viable commercial and business tool. In this paper, we propose novel data-streaming algorithms for the robust, real-time detection of DDoS activity in large ISP networks. The key element of our solution is a new, hash-based synopsis data structure for network-data streams that allows us to efficiently track, in guaranteed small space and time, destination IP addresses in the underlying network that are "large" with respect to the number of distinct source IP addresses that have established potentially-malicious (e.g., "half-open") connections to them. Our work is the first to address the problem of efficiently tracking the top distinct-source frequencies over a general stream of updates (insertions and deletions) to the set of underlying network flows, thus enabling us to effectively distinguish between DDoS activity and flash crowds. Preliminary experimental results verify the effectiveness of our approach.

Multicast is an efficient means of transmitting the same content to multiple receivers while minimizing network resource usage. Applications that can benefit from multicast such as multimedia streaming and download, are now being deployed over 3G wireless data networks. Existing multicast schemes transmit data at a fixed rate that can accommodate the farthest located users in a cell. However, users belonging to the same multicast group can have widely different channel conditions. Thus existing schemes are too conservative by limiting the throughput of users close to the base station. We propose two proportional fair multicast scheduling algorithms that can adapt to dynamic channel states in cellular data networks that use time division multiplexing: Inter-group Proportional Fairness (IPF) and multicast proportional fairness (MPF). These scheduling algorithms take into account (1) reported data rate requests from users which dynamically change to match their link states to the base station, and (2) the average received throughput of each user inside its cell. This information is used by the base station to select an appropriate data rate for each group. We prove that IPF and MPF achieve proportional fairness among groups and among all users in a group inside a cell respectively. Through extensive packet-level simulations, we demonstrate that these algorithms achieve good balance between throughput and fairness among users and groups.

Border gateway protocol (BGP) is the de facto standard used for interdomain routing. Since packet forwarding may not be possible until stable routes are learned, it is not only critical for BGP to converge but it is important that the convergence be rapid. The distributed and asynchronous nature of BGP in conjunction with local policies makes it difficult to analyze with respect to convergence behavior. We present a novel model which, to our knowledge, is the first one to permit analysis of convergence in the aggregate (i.e., over all message exchange orders between routers regarding route advertisements), rather than worst case behavior. We introduce the notion of probabilistic safety as requiring the probability of convergence to be 1. We provide a necessary and sufficient condition characterizing probabilistic safety that shows that probabilistic safety accommodates BGP configurations whose potential divergence stems solely from pathological message sequences. More generally, we show how to compute for any BGP configuration its probability of convergence. For probabilistically safe configurations, we present procedures for computing their expected time to converge as well as the probability distribution on their convergence times. The ability to compute these quantitative characteristics makes our work "constructive" and provides the basis for further understanding and deriving procedures for optimizing network characteristics. Finally, we simulate several network examples and verify the consistency between our analysis and the simulations

With the popularity of services like push-to-talk, the need for "always on" services is becoming important for service providers. The paper addresses the problem of supporting always on services in existing and new network architectures. It defines the requirements of always on service, identifies the problems in supporting such a service, and proposes an overlay network based solution to make always on service a reality. Some results from initial prototyping and experimentation are also presented to demonstrate the feasibility of deploying such services.

We consider a variation of a constrained Steiner minimal tree problem that is applicable for multicast conferencing. We assume a network having a cost and delay values associated with each edge. Then, we find an optimal shared tree with minimal cost subject to the constraint that the delay between any two nodes of the tree must be bounded by some maximal value. Such a constraint on the delay is appropriate for an application such as a multicast conference that uses a shared tree. We consider a new heuristic algorithm for solving this problem. Our approach is inspired by Lagrangian relaxation techniques. We first develop a novel distance metric on trees, termed delta diameter. Using this metric, our algorithm then uses a Prim-like labeling algorithm coupled with the Takahashi Matsuyama Steiner tree algorithm. Simulation results show how cost and delay can be traded off smoothly. Using simulation, we also compare our heuristic with the optimal achievable. We believe that our approach is practical for dynamically building shared trees to support applications such as real-time video conferencing with delay constraints.

This paper presents Aurora, a software toolkit that dramatically reduces the effort required to develop configurable, reliable, and scalable wireless applications. The toolkit consists of software libraries, code generation tools, and executable software components that provide initialization and fault tolerance support typically needed by these applications. Aurora has been used in several experimental wireless systems at Lucent Technologies. Empirical results show that it provides 35% to 75% of the software used in these systems, excluding operating system and third party class library software. These results indicate huge savings in reduced development effort, lowering development costs and shortening time to market, over systems that do not use Aurora.

We study congestion control for one-to-many multicast applications in the Internet and establish a three-way relationship between the choice of regulation parameter (i.e., rate or window size), the requirement to estimate receiver round trip times, and the type of fairness that may be accomplished. In particular, we show that in order to provide TCP-compatible fairness in rate-based regulation, receiver round trip times must be known. However, such a requirement does not exist in window-based regulation. We further show that measurement of receiver round-trip times in multicast communication, is fundamentally different and more complex than unicast communication, in order to avoid implosion of acknowledgments at the source. A major part of the paper deals with extending window-based regulation to multicast communications. We show that window-based regulation using a common window-size for the whole session leads to unnecessary restrictions on the throughput. To alleviate this problem, we propose a multicast window scheme using a distinct window size for each receiver, and enforcing it as the limit on the number of outstanding packets to that receiver. The complexity of window-based regulation can be defused by a receiver-driven implementation and by consolidation of receiver feedback in successive stages, e.g., using a hierarchical architecture. This hierarchical approach is also useful for scalable consolidation of receiver feedback in the case of rate-based regulation, and for distributed estimation of receiver round trip times, when such estimation is necessary.

Mobile phones are quickly becoming one of the most ubiquitous wireless consumer devices. Separately, Internet services are growing by leaps and bounds. Thus, an interesting area of research is to see if and how the two can be married together to provide wireless ubiquitous access to the ever-growing Internet services. We highlight the challenges and issues in providing Internet services to mobile phones. As an example, we describe and examine a research prototype called Wireless Data Server, which provides, among other services, wireless email service to mobile phone users.

An important aspect of network management is fault management-determining, locating, isolating and correcting faults in the network. The paper deals with the algorithms for detecting faults, i.e., behavior of the network different from specifications. It is important for communication networks to detect faults "in-process" i.e., while the network is in its normal operation. Thus, we detect faults by examining the input-output behavior without forcing the system to specialized inputs explicitly for testing. Such testing is commonly called passive testing. We model the network as a finite state machine and develop procedures for passive testing including the required data structure, efficient implementations and the complexity of our procedures. We start with fully observable and deterministic machines and then study more realistic models: partially observable and nondeterministic machines. We also discuss extensions to communicating finite state machines and machines extended with parameters and variables. We apply our techniques to management of a signaling network operating under the Signaling System 7 (SS7) and report experimental results, which show the feasibility of applying passive testing to practical systems.

Wireless messaging, in the form of two-way paging, is an integral part of universal Personal Communications Services (PCS). Basic wireless messaging services include providing reliable (acknowledged) message delivery, reply capabilities, and message origination from a messaging device. Many more advanced services can also be envisioned. Wireless networks and end devices impose many limitations on system design. To overcome the problems caused by such an environment, we have introduced network based proxies, called user agents, to assist simple end devices, and a novel way to define messages, called flexible messages, so that advanced messaging services may be offered. In this paper, we describe how user agents and flexible messages assist in providing messaging services in the Pigeon two-way messaging research prototype at Bell Laboratories.

This paper presents the design, implementation, and performance of a reliable multicast transport protocol (RMTP). The RMTP is based on a hierarchical structure in which receivers are grouped into local regions or domains and in each domain there is a special receiver called a designated receiver (DR) which is responsible for sending acknowledgments periodically to the sender, for processing acknowledgment from receivers in its domain, and for retransmitting lost packets to the corresponding receivers. Since lost packets are recovered by local retransmissions as opposed to retransmissions from the original sender, end-to-end latency is significantly reduced, and the overall throughput is improved as well. Also, since only the DRs send their acknowledgments to the sender, instead of all receivers sending their acknowledgments to the sender, a single acknowledgment is generated per local region, and this prevents acknowledgment implosion. Receivers in RMTP send their acknowledgments to the DRs periodically, thereby simplifying error recovery. In addition, lost packets are recovered by selective repeat retransmissions, leading to improved throughput at the cost of minimal additional buffering at the receivers. This paper also describes the implementation of RMTP and its performance on the Internet.

Wireless messaging is an integral component of universal personal communication services (PCSs). Its growth is likely to be further fueled by the availability of new data capabilities in the new PCS air interfaces. Our research focuses on high-level issues such as new messaging functionalities, high-layer protocols, and overall system design. Pigeon is our proposal of a wireless two-way messaging system. The novelty of our system lies in: (1) the techniques used in mitigating the wireless media and end device constraints, (2) the functionalities provided, and (3) its modular architecture. Examples of (1) include the use of asymmetric protocols and the introduction of user agents. Examples of (2) include group addressing, transaction support, and flexible messages. The modularity of Pigeon allows its individual components to be adopted by specific systems, A prototype of Pigeon has been implemented, and is operational at Bell Laboratories. We describe the motivation, design, and functionality of Pigeon. We also present, as an example, a mapping of Pigeon to a standard cellular/PCS messaging system.

A new class of wireless messaging service, called two-way paging, is emerging. Current research on wireless messaging has mostly been concerned with low-level physical layer transmission issues, e.g., modulation and access. Few efforts have addressed high-level issues such as new messaging functionalities, high layer protocols, and overall system design. Most existing wireless messaging systems are built as monolithic entities in a centralized manner. We contend that the current designs lack flexibility required to meet the demand of next generation messaging needs. Pigeon is our proposal of a two-way messaging system. The novelty of our system lies in (1) the techniques used in mitigating the wireless media and end device constraints, (2) the functionalities provided, and (3) its modular architecture. Examples of (1) include the use of asymmetric protocols and the introduction of user agents. Examples of (2) include group addressing, transaction support and flexible messages. The modularity of Pigeon is especially important when it is mapped onto a specific platform, in which case the components of Pigeon, as opposed to the system as is, may be individually adopted. A prototype of Pigeon has been implemented and is operational at Bell Laboratories. We describe the design of Pigeon. We pay particular attention to motivate its service and system concepts. We also present, as an example, a mapping of Pigeon to cellular messaging.

We present a new approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs). Our approach uses a guided random walk procedure. This procedure attempts to cover all transitions in the component FSMs. We also introduce the concept of observers that check some aspect of protocol behavior. We present the result of applying our method to two example protocols: full-duplex alternating bit protocol and the ATM-adaptation-layer-convergence protocol. Applying our procedure to the ATM adaptation layer, 99% of component FSMs edges can be covered in a test with 11692 input steps. Previous approaches cannot do conformance test generation for standard protocols (such as asynchronous transfer mode (ATM) adaptation layer) specified as a collection of communicating FSMs.

A communication system uses a precise set of rules called a protocol, to define interactions among its entities. With advancing computer transmission and switching technology, communication systems are providing sophisticated services demanded by users over a wide area. Protocol standards include a very, large number of options to take care of different service possibilities and to please all the people involved in the Standards Committees. Consequently, protocols have become large and complex, and, therefore their design and analysis have become a formidable task. To cope with this problem, a variety of approaches to simplify the protocols have been proposed in the published literature, such as protocol projection, homomorphism, selective resolution, and many others. We have recently developed a new technique called protocol pruning. It reduces the complexity of the protocols by pruning them to keep only that part which is required for a specified subset of services. More importantly, it takes polynomial (rather than exponential) time and space in the size of the protocol specification. This makes the algorithm feasible for engineers to use for practical problems involving large and complex protocols. We describe the technique and discuss applications to synthesis of protocol converters/gateways, protocol conformance testing, and thinning for lightweight and high performance protocols. The technique could also be useful for protocol implementation, synthesis, validation, and verification.>

We present an elegant protocol for reliably transmitting data messages from a sender to a receiver over a highspeed network that may reorder, lose, or corrupt messages. The protocol is based on a new principle that calls for the periodic exchange of state information between the sender and receiver. Our formal definition of the protocol is abstract and does not include explicit timing information such as the rate of sending state information. The abstract definition makes our formal verification of the protocol simple and based solely on well-established concepts: invariants, well-foundedness, and action fairness. We use the formal definition of the protocol and its proof of correctness to deduce the required timing information. In particular, we show that the rate of sending state information is at most (m-1)/2T where m is a measure of the memory size in the sender, and T is an upper bound on the required time for one message to be sent, propagated, and received between the sender and receiver.>

This paper presents the design and analysis of three reliable multicast transport protocols for high speed networks. The novelty of these protocols lies in the technique used in combining the acknowledgments of individual destinations along the underlying multicast tree to prevent acknowledgement implosion and in the technique used in preventing unnecessary retransmission by performing local multicasts. These protocols use the periodic exchange of complete state information between the source and the destinations and a block-based Selective Repeat retransmission scheme to improve the overall performance in a high speed networking environment. Performance of each protocol is analyzed in terms of throughput, end-to-end delay, buffer requirement, acknowledgment traffic and retransmission traffic. Based on this analysis and the complexity of implementation, one of the three protocols is recommended for reliable multicasting in high speed networks.>

The protocol VLSI engine (PROVE) is programmable VLSI chipset which can be used to implement several standard communication protocols. The protocol to be implemented is described in a formal specification language called the augmented protocol specification language (APSL). From these formal descriptions, a compiler generates microcode for PROVE. PROVE can process 50000 packets/s for standard protocols such as LAPD and LLC Class 2. It consists of a message parser (MP), message assembler (MA), central controller unit (CCU), and interface with the upper layer. It supports efficient multiplexing operation with zero-overhead context-switching and support for timer maintenance. The paper describes the architectural features of the CCU, the MP, and the MA. A typical protocol implementation using the PROVE chipset is also described. The authors also compare it with other proposals for protocol engines. The first generation of the PROVE chipset has been built and tested.>

The authors study the problem of locating the differences between a protocol specification and its implementation. They give an exact procedure for solving this problem. If there is only one difference between the implementation and the specification, then the algorithm will locate the difference and therefore identify the implementation machine. Otherwise, it will detect that the implementation machine has more than one change. The run time of the algorithm is a low-degree polynomial in the number of states and inputs of the machine. Both a brute-force version of the algorithm with a cost O(pn/sup 5/), where n is the number of states of the specification machine and p is the number of inputs, and a fast algorithm with a cost O(pn/sup 3/ log n) are described. An improvement for which the cost on the average is O(pn/sup 2/ log n) is also given. A heuristic procedure that uses a test of comparable length to a conformance test sequence which has been used successfully in practice is described.>

An approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs) with two parts, pruning and a guided random walk procedure, is presented. First the protocol is pruned to various sets of machines; each set provides only one service. This significantly reduces the test sequence length. Then a guided random walk procedure that attempts to cover all transitions in the component FSMs is used. The results of applying the procedure to the full-duplex alternating bit protocol and the asynchronous transfer mode (ATM) adaptation layer convergence protocol are presented. For the ATM adaptation layer, 99% of component FSMs' edges can be covered in a test with 11692 input steps. Previous approaches cannot generate conformance tests for standard protocols (such as ATM adaptation layer) specified as a collection of communicating FSMs.>

The performance of the SNR protocol of A. N. Netravali et al. (1990) is studied when it is implemented for end-to-end flow and error control. Using a combination of analysis and simulation, the efficiency with which this protocol uses the network bandwidth and its achievable throughput is evaluated as a function of certain network and protocol parameters. The protocol is enhanced by introducing two windows to decouple the two functions of receiver flow control and network congestion control. This enhancement and the original protocol are compared with go-back-N (GBN) and one-at-a-time-selective-repeat (OSR) retransmission procedures, are shown to have significantly higher throughput for a wide range of network conditions. As an example, for a virtual circuit with 60-ms roundtrip delay and 10/sup -8/ bit error rate, in order to deliver 500 Mb/s throughput, both the GBN and OSR require a raw transmission bandwidth of approximately 800 Mb/s, whereas SNR with two windows needs slightly higher than 500 Mb/s raw bandwidth. Periodic exchange of state can also provide a variety of measures for congestion control in a timely and accurate fashion.>

A systematic procedure that takes exponential time to synthesize protocol converters from formal specifications is presented. The algorithm proceeds in two steps: compute the largest common subset of services provided by the two mismatched protocols, and reduce the converter, retaining common services, without traversing the entire machine that represents the composition of the two mismatched protocols. In a number of cases, the converter can be constructed by a memoryless translation of messages from one protocol to another. Conditions under which such stateless conversion is possible are given. Two examples are presented to illustrate the techniques. In the first example, a converter that interconnects a half-duplex protocol with a full-duplex protocol from their formal specifications is computed. In the second example, the polynomial procedure is applied to computation of a converter for interconnecting the SNR and TCP protocols.>

The four major methods of conformance test generation reported in the literature are reviewed: transition tours; distinguishing sequences; characterizing sequences; and unique input/output sequences. These methods are used to test the control portion of a protocol specification. The conformance testing concepts developed in the standards world are summarized. Their relationship with the four formal methods is discussed.>

The design, analysis, and implementation of an end-to-end transport protocol that is capable of high throughput consistent with the evolving high-speed physical networks based on fiber-optic transmission lines and high-capacity switches are presented. Unlike current transport protocols in which changes in control/state information are exchanged between the two communicating entities only when some significant event occurs, this protocol exchanges relevant and full state information periodically and frequently. It is shown that this reduces the complexity of protocol processing by removing many of the procedures required to recover from network inadequacies such as bit errors, packet loss, and out-of-sequence packets and makes it more amenable to parallel processing. Also, to increase channel utilization in the presence of high-speed, long-latency networks and to support diagrams, and efficient implementation of the selective repeat method of error control is incorporated in the protocol. An implementation using a Motorola 68030-based multiprocessor as a front-end processor is described. The current implementation can comfortably handle 10-15 kpackets/s.>

We present a design and preliminary analysis of an end-to-end transport protocol that is capable of high throughput consistent with the evolving wideband physical networks based on fiber optic transmission lines and high capacity switches. Unlike the current transport protocols in which changes in control state information are exchanged between the two communicating entities only when some significant event occurs, our protocol exchanges relevant and full state information periodically, routinely and frequently. We show that this results in reducing the complexity of protocol processing by removing many of the procedures required to recover from the inadequacies of the network such as bit-errors, packet loss, out of sequence packets and makes it more amenable to parallel processing. Also, to increase channel utilization in the presence of high speed, long latency networks, and to support datagrams, we propose an efficient implementation of selective repeat method of error control used in our protocol. Thus, we utilize small extra bandwidth to simplify protocol processing; a trade-off that appears proper since electronic speeds for protocol processing are far slower than fiber transmission rates. Our preliminary estimates indicate that 20,000 packets/second can be handled in a completely software implementation on a 10 MIP microprocessor using 8% of its cycles.

Several protocol controllers for the IEEE 802 local area networks are surveyed and some characteristics for classifying them are given. Some case studies from these controllers are given as illustrations. Two new developments-the protocol engine and the programmable protocol engine-are also described. The protocol engine, currently under development, implements a new protocol called XTP which performs the functions of both the network and transport layers. The programmable protocol engine can implement several connection-oriented protocols by changing contents of a programmable random access memory.>

A technique for detecting and diagnosing faults at the processor level in a multiprocessor system is described. A process is assigned whenever possible to two processors: the processor to which it would normally be assigned (primarily) and an additional processor that would otherwise be idle (secondary). Two strategies are described and analyzed: one that is preemptive and another that is nonpreemptive. It is shown that, for moderately loaded systems, a sufficient percentage of processes can be performed redundantly using the system's spare capacity to provide a basis for fault detection and diagnosis with virtually no degradation of response time. A multiprocessor that uses the approach for detecting faults at the processor loads is described.>

A procedure for checking safety properties of communication protocols is presented. A protocol is specified as a collection of communicating finite-state machines (FSMs). Two novel algorithms used in this procedure are described. The first algorithm does incremental composition and reduction of FSMs. It uses three heuristic rules which reduce the number of states in the global FSM by one to two orders of magnitude while maintaining its observational equivalence. The second algorithm checks whether the behavior of one FSM is a subset of another FSM's behavior. This procedure has been applied to the ISDN Q.931 and alternating bit protocols.>

A description is given of an experience in estimating fault coverage of a test sequence designed to test the control portion of a protocol. The control portion of this protocol is modeled as a finite-state machine. This study uses Monte Carlo simulation and introduces a novel notion of machine equivalence. An algorithm given checks for this notion of machine equivalence.>

We present two protocols for information exchange between multiple identical senders and a single receiver. At each instant, every sender sends one bit, and the bits from all of senders are or-ed together into one bit before being received by the receiver. If a sender has a data message to send, it sends the message bits one by one; otherwise it sends zero bits. Clearly, if the sending of two messages by two senders overlap, then the resulting “collision” can result in a corrupted message, i.e., one that was not sent by either sender. The function of the protocol is to deliver those and only those messages that are not corrupted by collision. (In other words, the receiver acts as a discriminating seine that catches and delivers only uncorrupted messages; hence the title.) The two protocols presented here are based on Manchester codes and general balanced codes, respectively.

An algorithmic procedure for protocol verification is presented. A protocol is described as a collection of processes interacting with one another using CSP-type input/output operations. The safety properties of each process are described by a finite-state machine and the liveliness properties of each process by a collection of temporal logic formulas. The required behavior of the protocol is then specified in the same formalism, and the verification procedure can check the description of the protocol for correctness. An experimental implementation of the verification algorithm has been applied to the alternating-bit protocol.>

A technique is described for detecting and diagnosing faults at the processor level in a multiprocessor system. In this method, a process is assigned whenever possible to two processors: the processor that it would normally be assigned to (primary) and an additional processor which would otherwise be idle (secondary). Two strategies will be described and analyzed: one which is preemptive and another which is non-preemptive. It is shown that for moderately loaded systems, a sufficient percentage of processes can be performed redundantly using the system's spare capacity to provide a basis for fault detection and diagnosis with virtually no degradation of response time.

In this correspondence a system-level, comparison-based strategy for identifying faulty processors in a multiprocessor system is described. Unlike other strategies which have been proposed in the literature, the comparison approach is more efficient and relies on more realistic assumptions about the system under consideration. The new strategy is shown to correctly identify the set of faulty processors with a remarkably high probability, making it an attractive and viable addition or alternative to present fault diagnosis techniques.

A new connection establishment procedure for point-to-multipoint data transfer, the multiple attempts in one shot (MAOS) procedure, is proposed. The MAOS procedure is shown to have substantially lower connection establishment time compared to the conventional procedure used in protocols such as HDLC.

A novel procedure presented here generates test sequences for checking the conformity of protocol implementations to their specifications. The test sequences generated by this procedure only detect the presence of many faults, but they do not locate the faults. It can always detect the problem in an implementation with a single fault.

Two retransmission procedures, the go-back-N(GBN) scheme and the selective repeat (SR) scheme, have been analyzed for data transfer from one transmitter to many receivers. We consider transfer of error-controlled bulk data over a satellite broadcast channel. Two retransmission strategies, the dynamic retransmission group reduction (DRGR) technique and the fixed retransmission group (FRG) technique, are proposed. We study the GBN and SR schemes for both strategies. Analytic expressions are derived for the throughput performance of the GBN scheme and of the SR scheme with infinite resources, while discrete event simulation is used to estimate the throughput of the selective repeat scheme with finite resources. Only the SR scheme using the DRGR technique provides acceptable performance for high-speed bulk data transfer. For the DRGR technique, the throughput falls logarithmically with an increase in the number of receivers. In contrast, the throughput for the FRG technique falls exponentially with an increase in the number of receivers.