Decomposition approximations in the past have been successfully applied to the performance analysis of preemptive priority based GSM/GPRS networks. In this paper, we propose a decomposition technique for the performance analysis of GSM/GPRS networks where GSM voice calls have non-preemptive priority over GPRS data packets. In other words, when demand exists for GSM circuit switched channels, the GPRS user can continue its transmission until the ending of packet transmission resulting in a delayed release of the channel. It is shown that such an approximation can be quite accurate in predicting both the impact of delayed release on GSM voice queuing as well as for comparison of immediate versus delayed release of channels on GPRS data queuing delays.

Decomposition approximations have recently been used in the performance evaluation of access networks such as GSM/GPRS and ATM based networks. In this paper we extend the analysis to a network possessing a hierarchy of traffic types, such as voice, data and broadband video. We look at different policies for the transmission of the traffic, and apply a hierarchical decomposition technique to the performance analysis of the network where necessary. We find that the decomposition technique is quite useful in predicting the performance of networks where video, voice and data have channel holding times which are each of different orders of magnitude in comparison to each other.

We have developed a linear programming procedure to partition bandwidth to voice and data connections in a wireless integrated system in order to minimize voice delay and maximize data throughput with voice packet loss constrained. Results show that the linear programming performance can be approached quite closely by a simple round-robin scheme with adaptive threshold. An analytical procedure is developed for the round-robin scheme in order to determine the threshold, based on the number of voice connections. Simulation results indicate that when the number of connections or state space is large, the threshold value can be approximated by extrapolating linearly with a slope which equals the average rate of a connection. The round- robin scheme with adaptive threshold is thus shown to be a well-performing and easily-implementable scheme.

We develop the notion of quality of service (QoS) for multimedia traffic in terms of maximum call dropping probabilities independent of system load and a predefined call blocking probability profile for the different traffic classes for wireless networks of arbitrary shape and dimension. We describe two distributed predictive admission control algorithms, independent multiclass one-step prediction (IMOSP-CS and IMOSP-RES), which provide each traffic class with a given call dropping probability and a desired call blocking probability profile. Both algorithms may be seen as extensions of the multimedia one-step prediction (MMOSPRED) algorithm previously reported, which uses prediction of the overload probability in the home and neighbor cells in deciding whether to admit new users into a multiclass cellular system. The two algorithms differ in their approach to handoff call admission. The first algorithm completely shares the bandwidth among the entering handoff users while the second implements a partition-based reservation scheme. In this paper, we additionally impose a call blocking criterion that ensures a system-imposed call priority independent of the traffic in the system and which adapts to changes in the offered load. In comparing these algorithms to each other, we focus on system throughput and class independence. Both algorithms provide appropriate throughput under both homogeneous and heterogeneous traffic loading conditions while maintaining steady call dropping probabilities for each traffic class.

The performance of two previously proposed asymptotically stable unicast flow control algorithms for high-speed networks is compared. We extend one of them to the multicast case. The multicast algorithm is modeled by a set of delay-differential equations. Despite the difficulties in analyzing the second order system with multiple different delays, the algorithm is analytically proven to be stable, and this is supported by extensive simulations. This work should prove useful in the design of multicast flow control algorithms.

There is an urgent need for effective multicast congestion control algorithms which enable reasonably fair share of network resources between multicast and unicast TCP traffic under the current Internet infrastructure. In this paper, we propose a quantitative definition of a type of bounded fairness between multicast and unicast best-effort traffic, termed "essentially fair". We also propose a window-based Random Listening Algorithm (RLA) for multicast congestion control. The algorithm is proven to be essentially fair to TCP connections under a restricted topology with equal round-trip times and with phase effects eliminated. The algorithm is also fair to multiple multicast sessions. This paper provides the theoretical proofs and some simulation results to demonstrate that the RLA achieves good performance under various network topologies. These include the performance of a generalization of the RLA algorithm for topologies with different round-trip times.

In this paper we develop a simple and accurate analytical technique to determine the loss probability at an access node to an asynchronous transfer mode (ATM) network. This is an important problem from the point of view of admission control and network design. The arrival processes we analyze are the Markov-modulated Poisson process (MMPP) and the Markov-modulated fluid (MMF) process. These arrival processes have been shown to model various traffic types, such as voice, video, and still images, that are expected to be transmitted by ATM networks. Our hybrid analytical technique combines results from large buffer theories and quasi-stationary approaches to analyze the loss probability of a finite-buffer queue being fed by Markov-modulated sources such as the MMPP and MMF. Our technique is shown to be valid for both heterogeneous and homogeneous sources. We also show that capacity allocation based on the popular effective-bandwidth scheme can lead to considerable under-utilization of the network and that allocating bandwidth based on our model can improve the utilization significantly. We provide numerical results for different types of traffic and validate our model via simulations.

A multipoint flow control framework for data traffic traversing both a wired and mobile wireless network is proposed. A Markov modulated fluid model is used for the receiver to capture the dynamics of the wireless links. We discover that the phase difference of the instantaneous throughput of the receivers is a distinctive feature of multicast connections. The objectives of the multicast flow control algorithms are to cope with the receiver phase difference cost-effectively in addition to the general goals such as maximizing throughput and minimizing delay. Three ad hoc algorithms have been studied: listen to slowest request (LSQ), source estimation (SE), and open loop control. A fluid analysis technique is applied to study the effect of receiver phase difference assuming zero delay. The effect of propagation delay is then discussed. Simulation results are presented to verify the analysis for the zero delay case and to compare the performance of the algorithms under non-negligible delay.

A multicast flow control framework for data traffic traversing both a wired and wireless network is proposed. Markov-modulated fluid (MMF) models are used for the receivers to capture the dynamics of the wireless links. Our study shows that the phase differences of the instantaneous throughput capabilities of the receivers are a distinctive feature of multicast connections. The objectives of the multicast flow control algorithms are to cope with the receiver phase differences (RPDs) cost effectively in addition to the general goals such as maximizing throughput and minimizing delay. Three ad hoc algorithms have been studied: listen to slowest request (LSQ), source estimation (SE), and open-loop control. A fluid-flow analysis technique is applied to study the effect of receiver phase differences assuming zero propagation delay. The effect of propagation delay in multicast connections is then discussed. Simulation results are presented to verify the analysis for the zero-delay case and to compare the performance of the algorithms under nonnegligible delays. It turns out that the zero-delay case reveals the characteristics of the multicast algorithms and provides good performance bounds for the cases with nonnegligible propagation delays.

In this paper we develop a simple and accurate analytical technique to determine the loss probability at an access node to an ATM network. This is an important problem from the point of view of admission control and network design. The arrival processes we analyze are the Markov modulated Poisson processes (MMPP) and the Markov modulated fluid (MMF) processes which are important in modeling various traffic types, such as voice, video, and still images. Our hybrid analytical technique combines results from large buffer theories and quasi-stationary approaches to analyze the loss probability of a finite buffer queue. Our technique is shown to be valid even for heterogeneous sources. We also show that capacity allocation based on the popular effective bandwidth scheme can lead to considerable underutilization of the network, and that allocating bandwidth based on our model can improve the utilization significantly. We provide numerical results for different types of traffic and validate our model via simulations.

The major focus of this paper is distributed call admission control in mobile/wireless networks, the purpose of which is to limit the call handoff dropping probability in loss systems or the cell overload probability in lossless systems. Handoff dropping or cell overload are consequences of congestion in wireless networks. Our call admission control algorithm takes into consideration the number of calls in adjacent cells, in addition to the number of calls in the cell where a new call request is made, in order to make a call admission decision. This is done by every base station in a distributed manner without the involvement of the network call processor. The admission condition is simple enough that the admission decision can be made in real time. Furthermore, we show that our distributed call admission control scheme limits the handoff dropping or the cell overload probability to a predefined level almost independent of load conditions. This is an important requirement of future wireless/mobile networks with quality-of-service (QoS) provisioning.

The multiparty conference management protocol (MCMP) is an end-to-end distributed session/transport level protocol intended for group management of desktop conferencing applications. This paper describes the MCMP conference setup algorithms and proves that they meet specified correctness properties. MCMP sets up control channels for use in exchanging control information while the conference is in progress. The logical topology used is a completely interconnected mesh, MCMP always provides best effort services in cases of failures. Correctness properties guaranteed upon termination of the protocol include connectivity, validity, uniqueness, and consistency of local views. Application control information that can be exchanged using the control channels include resource negotiation and subconferencing.

We analyze different retransmission (ARQ) schemes for error control in multicast protocols geared toward real-time, multimedia applications. We discuss why retransmission schemes are not inappropriate for such applications, but in fact can be quite effective. We present a quantitative analysis of such schemes, as well as simulation results, taking into account four different parameters (and not just the source throughput): (1) the probability of dropping a packet due to limited time for retransmissions; (2) the average time required to deliver a packet correctly to end receivers; (3) the number of times a packet will be retransmitted; and (4) the cost to the network, in terms of packet duplications, of retransmitting a packet. We reach the counter-intuitive conclusion that the optimum scheme, in terms of all four of the above parameters, in the most general scenarios (where several hosts with widely varying propagation delays and 'quality of connections' are participating in the session) is to immediately retransmit packets-preferably multicast-upon reception of a NACK from any receiver. We also demonstrate, again through quantitative analysis, the circumstances under which it would be beneficial (as well as those under which it would be counter-productive) to multicast control messages in the hope of suppressing duplicates and preventing the source from being overwhelmed by control messages.

The major focus of this paper is distributed call admission control in mobile/wireless networks the purpose of which is to limit the call hand-off dropping probability in loss systems or the cell overload probability in lossless systems. Hand-off dropping or cell overload are consequences of congestion in wireless networks. Our call admission control algorithm takes into consideration the number of calls in adjacent cells in addition to the number of calls in the cell where a new call request is made, in order to make a call admission decision. This is done by every base station in a distributed manner without the involvement of the network call processor. The admission rule is simple enough that the admission decision can be made in real time. Furthermore, we show that our distributed call admission control scheme limits the hand-off dropping or the cell overload probability to a predefined level almost independent of load conditions. This is an important requirement of future wireless/mobile networks with quality-of-service provisioning.

We have proposed a tree based virtual embedded network architecture to address the resource reallocation problem for mobile users connected to an arbitrary topology ATM backbone network. The approach helps us significantly reduce the resource reallocation rate on different links of the ATM network for both linear and two dimensional arrangements of access points. We show that the resource reallocation rate may be further reduced by very small over-allocation of resources. We have proposed and evaluated two specific schemes for a better understanding of this trade-off.

A single fault in a large communication network may result in a large number of fault indications (alarms) making the isolation of the primary source of failure a difficult task. The problem becomes worse in cases of multiple faults. In this paper we present an approach for modelling the problem of fault diagnosis. We propose a graph based network model that takes into account the dependencies among the different objects in the telecommunication environment and a novel approach to estimate the domain of an alarm. Based on that model, we design an algorithm for fault diagnosis and analyze its performance with respect to the accuracy of the fault hypotheses it provides. We also propose and analyze a fault diagnosis algorithm suitable for systems for which an independent failure assumption is valid. Finally, we examine the importance of the information of dependency between objects for the fault diagnosis process.

Video traffic is expected to become increasingly important with the large scale deployment of broadband ISDN. In the literature, it suggested that smoothing variable bit rate (VBR) video traffic before transmitting it onto the network would help reduce the probability of packet loss. The authors show why deterministic smoothing at the source approximates the minimum achievable loss over the network end-to-end of all possible smoothing schemes. Furthermore, they develop a powerful yet simple analytical technique that can efficiently calculate the loss probability at any point in a network carrying video traffic. They validate the analytical results using traces of actual video segments. The results can be used for admission control and traffic management. They find that in the case of highly correlated traffic such as video, the way to control loss is to ensure that the fraction of time the arrival process exceeds the service process is small.>

The authors review the results of a two-level control framework for integrated video and image traffic in an ATM multiplexer. The framework gives priority to video traffic, and uses flow control on the image traffic in order to prevent congestion while improving its throughput. It functions on two levels, or time scales. Buffer management and scheduling are done at the level of cell arrivals and departures, or microsecond time scales, while flow control is done at the burst level, or millisecond time scales. The control framework guarantees upper bounds on cell loss rates for both video and image traffic over a defined control interval, with a specified probability.>

A closed-form decomposition approximation for finding the data performance in voice/data queuing systems is presented. The approximation is based on Courtois' (1977) decomposition/aggregation techniques and is applied to Senet hybrid multiplexing, movable boundary frame allocation schemes. The approximation is applied to both infinite and finite buffer systems. In the former case the approximation is valid only in the underload region and serves as an upper bound for the mean data queuing delay. In the finite buffer case it is valid for the whole data traffic range and is shown to improve as the number of channels increase, and deteriorates as the buffer size increases. For finite buffer systems upper and lower bounds for the decomposition approximation have also been derived. It is found that the lower bound is tight in the underload and low traffic region of the overload. In these same regions the decomposition approximation serves as a tight upper bound.>

The authors examine the data transfer phase of TCP (Transmission Control Protocol) to identify complex processing elements, where complexity is measured in terms of instruction counts. The objective is to reduce the complexity and improve the performance of TCP in a high speed networking environment, especially for bulk data transfer. It is found that most of the complexity is due to incomplete state information exchange with the peer, and to adapting to network dynamics using the current congestion control scheme. By partitioning of the protocol functionality into data and control information processing, along with the use of a rate based congestion control scheme, the complexity can be reduced by up to 67%. Performance can be further enhanced by running the new properly partitioned TCP in parallel as well as by simplifying the logic associated with some TCP timers.>

The performance of the multistream protocol (MSP), a feature-rich flexible transport designed to meet the needs of high-performance applications, is analyzed. The analysis is based on the processing complexity associated with performing certain protocol functions and it highlights the advantages and disadvantages of the implementation of several different protocol mechanisms, such as packet or block mode data transfer. The analysis shows that, if 10-MIPS processors are used to implement the protocol in a parallel architecture and block mode transmission is used, MSP may transfer data at a rate of over 150 Kpackets/s with a block size of 50 packets.>

A transport layer protocol designed to meet the wide-ranging needs of high-speed applications is described. A unique feature of this protocol is that its behavior, defined by a set of functions, may be modified dynamically over the life of a connection without loss of reliable data transfer. This property makes the protocol attractive for supporting applications, such as multimedia applications that require different protocol support for different portions of their traffic streams. The protocol has been verified to reliably deliver data and manage connections and to contain no deadlocks or loops. A parallel architecture for implementing the protocol has also been verified. Analysis of a skeleton implementation shows that the protocol has the potential to receive data at a rate of over 150 kpackets/s if 10-MIPS processors are used in the implementation.>

The authors present a maximum a posteriori method to identify faulty links in a communication network. A designated network node with management responsibilities determines a fault has occurred due to its inability to communicate with certain other nodes. Given this information as well as the information that it can communicate with another specified set of nodes, one would like to identify as quickly as possible a ranked list of the most probable failed network links. The authors also indicate how the method might be extended to the identification of most probable faulty network resources in a more abstract (higher level) model of a network, including, for example, an object-oriented model.>

The problem of minimum cost identification of a finite state machine (FSM) using a trace of its event history is addressed. The motivation is fault identification in communication systems, although other applications are possible as well. The event history used for the identification is partially observed, i.e., it is known to be a member of a regular language. Any string which belongs in this regular language is a possible trace of the FSM's event history. Furthermore, the event history is assumed to be corrupted with deletions, additions, and changes of symbols. The FSM to be estimated is related to a known FSM by performing an unknown number of additions and changes of arcs. An identification algorithm based on a fast algorithm that can correct corrupted data strings generated by a known finite state machine is developed. Examples of the method are provided, including one based on the IEEE 802.2 logical link control protocol.>

A performance analysis of the MultiStream Protocol (MSP), a feature-rich flexible transport protocol designed to meet the needs of high-performance applications, is presented. The analysis presents the advantages and disadvantages of the implementation of several different protocol mechanisms, such as packet or block mode data transfer. It is based on the processing complexity associated with executing each protocol function. Results show that a feature-rich transport protocol can be implemented in which the protocol control processing overhead is not prohibitive to providing high performance to an application. Instead, the benefits of a lean protocol are achieved because the protocol services better fit application requirements. Also, the primary bottleneck for data transfer is shown to be the complexity associated with error control, which can reduced through the technique of transmitting packets in blocks.>

The authors introduce a model based on arrival rate histograms for characterizing the behavior of an ATM buffer when it is carrying variable bit rate video traffic. Traffic smoothing on a frame-by-frame basis allows a quasistatic approximation that accurately predicts results such as buffer occupancy distributions and cell loss rates to be made. Convolving individual source histograms allow prediction of the queueing performance of a multiplexed stream. The approximation is investigated in more detail by modeling video as a Markov modulated Poisson process. It is shown that the multiplexer system is nearly completely decomposable (NCD). NCD systems have a well-known approximate solution, which is identical to the histogram approximation. Error bounds for the NCD approximation are also known and are reasonably tight. Results indicate that while the presence of strong correlations is an important characteristic of video traffic, the actual form of that correlation is not.>

There is a pressing need for network management systems capable of handling faults. The use of a set of independent observers to detect faults in communication systems that are modeled by finite-state machines is proposed. An algorithm for constructing these observers and a fast real-time fault detection mechanism used by each observer are given. Since these observers run in parallel and independently, one immediate benefit is that of graceful degradation-one failed observer will not cause collapse of the fault management system. In addition, each observer has a simpler structure than the original system and can be operated at higher speed. This approach has the potential to be incorporated into the fault management system for a high-speed communication system.>

The authors develop a model for characterizing the behavior of an asynchronous transfer mode (ATM) buffer when it is carrying variable-bit-rate video traffic. Traffic smoothing on a frame-by-frame basis allows the modeling of video sources as randomly modulated Poisson processes which are characterized by their bit rate histograms. An M/D/1/N approximation is used to accurately predict results such as buffer occupancy distributions and cell loss rates. Given the bit rate histograms of several individual video sources, a histogram for the aggregate arrival process can be found and the system behavior can be predicted. A new call admission control scheme and policing algorithm are developed based on the model. They can be used to prevent congestion in the network and to protect calls that adhere to parameters given at call setup.>

The authors propose to use a set of independent observers to detect faults in communication systems that are modeled by finite-state machines. An algorithm for constructing these observers and a fast real-time fault detection mechanism used by each observer are given. Since these observers run in parallel and independently, one immediate benefit is that of graceful degradation; one failed observer will not cause collapse of the fault management system. In addition, each observer has a simpler structure than the original system and can be operated at higher speed.>

This work provides a framework for approaching the problem of fault detection in communication processes. Communication processes are modeled as finite state machines (FSMs), and the authors' model consists of two FSMs, one observing part of the behavior of the other. The authors prove that specific classes of faults are detectable, and give a procedure for constructing detectors, but the design of the minimum alphabet detector is NP-complete. An example applicable to the 802.2 protocol is provided.>

A comparison of the MAC access protocols of the IEEE 802.6 DQDB MAN and FDDI standards is presented. The results are derived from simulation studies, and verified by analytical approximations. The comparison is based on average packet access delays of nodes on DQDB and FDDI networks. By setting the available bandwidth of the two networks to be equal, the authors draw broad conclusions regarding the relative strengths and weaknesses of each protocol. The results show the relative effect of varying various network parameters such as token rotation time, geographic size of the network, number of stations and total bandwidth on packet delay for the two protocols.>

The problem of minimum-cost correction of a corrupted set of data that has been generated by a known finite state machine (FSM) is examined. The Viterbi algorithm is modified to correct insertions and deletions as well as errors, still using a trellis diagram that has the same number of states as the FSM that generates the uncorrupted data. Two problems are examined. In the first problem the data is given in the traditional form of a string so the novel aspect is that insertions and deletions are now corrected. In the second problem, a unique string need not be given, but a regular language is given, and any string belonging to the regular language is a possible data string. Again, deletion addition, and changes of symbols are corrected. A direct generalization of the Viterbi decoding algorithm is thus proved to be an efficient technique for solving a much wider class of problems.>

The performances of centralized, fast packet switches based on the ShuffleNet and on multistage banyans are compared. Two cost criteria are used, viz., the number of crosspoints and the number of pin-limited ICs. The analytic comparison of the two networks built with arbitrary size infinite buffered nodes shows their cost performance to be similar. The analysis also provides the optimal node sizes for both the topologies. The best throughput per crosspoint is obtained with small nodes, but the best throughput per pin-limited IC is obtained with the largest possible nodes that can be built on an IC. With the IC criterion, for both the networks, small nodes are found to give small minimum delays (inside the network). With finite buffered nodes and a simple back-pressure flow control (like the one for the banyan network), the ShuffleNet based switch can have problems of congestion. It is also prone to deadlocks.>

This paper proposes an architecture for accomplishing transport protocol processing at Gbps rates. The limitations of currently used transport protocols have been analyzed extensively in recent literature. Several benchmark studies have established the achievable throughput of ISO TP4 and TCP to be in the low Mbps range; several new protocols and implementation techniques have been proposed to achieve 100 Mbps and higher throughput rates. We briefly review some of these protocols and establish the need for a radically different approach to meet our objective. An estimate of the aggregate processing power required for Gbps throughput is developed. It is proposed that a cost effective and practical solution to the processing requirements could be based on a multi-processor system. The opportunities for parallel processing in a typical transport protocol are examined. Several alternate parallel processing approaches are examined and arguments are advanced for selecting a favored approach. A corresponding parallel processing architecture is described. Data structures used to preserve packet ordering and techniques for reducing contention in a multi-processing environment are discussed. An implementation methodology for conventional transport protocols (e.g. TP4) is outlined. Some suggestions are made for improving efficiency by making modifications to the protocol that do not compromise functionality. The performance achievable with this modified architecture is analyzed and some suggestions for further work are presented.

Scheduling of voice traffic on broadcast-bus local area networks is considered. A voice scheduling scheme is proposed and evaluated. In this scheme, active voice calls are organized using a distributed global queue. Access scheduling overhead is reduced by voice packet arrival anticipation. To guarantee fairness and to reduce variance of the waiting time, the voice packet build-up during the overhead period is fairly shared among all calls by a round-robin service discipline. Three different voice packet service cases, namely nonexhaustive, exhaustive, and no-queueing, are evaluated. Simple closed-form approximation formulas have been proposed which show good agreement with simulation. The proposed scheme is shown to have performance approaching that of the centralized system.>

Two flow control schemes are investigated. In Scheme A, messages are allowed into the gateway buffer until it reaches its capacity, at which point they are blocked and made to wait at their respective input buffers. When capacity becomes available at the output buffer, the messages are allowed into the output again on a first-come-first-serve basis. Scheme B is based on an optimal throughput scheme which is derived using a process involving linear programming. In this scheme, the output buffer reserves its spaces for those input buffers that have a temporarily higher demand for spaces than their own buffers can offer. Simulation results confirm that Scheme B produces a better throughput performance than Scheme A. However, this is obtained at the expense of a higher delay. A constraint on the delay can be introduced when deriving Scheme B, but this is expected to lower the maximum throughput achievable.>

Random access scheduling schemes for broadcast-bus-type local area networks are considered. It is found that a good access scheduling scheme not only has information about the number of packets to be scheduled, but which, more importantly controls the average of this number, which can be achieved by properly choosing the scheduling interval. Furthermore, this scheduling interval is updated in such a way that adjacent intervals overlap, which by correlation gives a better estimate for the number of packets to be scheduled. The scheduling schemes developed using such concepts provide significant performance improvement over schemes using other scheduling approaches previously reported in the literature.>

The authors examine the use of a group random-access protocol based on time windows for supporting time-constrained communication applications in a multiple-access network. First they formulate a policy for controlling protocol operation to minimize the percentage of messages with waiting times greater than some given bound. A semi-Markov decision model is then developed for protocol operation, and three of the four optimal control elements of this policy are determined. Although the semiMarkov decision model can also be used to obtain performance results, the procedure is to computationally expensive to be of practical use. Thus, an alternate performance model based on a queuing system with impatient customers is developed. Protocol performance under the optimal elements of the control policy shows significant improvements over cases in which the protocol is not controlled in this manner. Simulation results are presented to corroborate the analytic results.>

To be fully integrated, the Integrated Service Digital Network (ISDN) arena is preparing an evolution from its current narrowband structure (at basic and primary access rates) to a futuristic wideband structure where access rates will be capable of supporting services beyond 100 Mbits/s. A wideband channel structure for ISDN, supplementing the narrowband channel standards, is thus needed. This paper presents a channel structure in which the access bandwidth is organized in a hierarchy of channels of increasing speeds. Channels at a given speed level accommodate services with specific bandwidth and holding time requirements. However, to improve performance, the access interface uses a control strategy whereby a service request at a given level can overflow to a lower level for access at lower bit rate. The performance, in terms of access delay and access throughput, of this access scheme is analyzed. Numerical results are provided for the special case of an interface with two levels of channels. These results show that a significant improvement in access performance can be obtained with the overflow mechanism of the access control discipline used.

It is shown in [13] that different types of routing procedures for circuit-switched traffic in a nonhierarchical network exhibit various performance tradeoffs. It is, however, not clear if the network is also allowed to carried packet-switched traffic, how the packet-switched traffic will be affected by using different routing procedures for the circuit-switched traffic. In this paper, we examine the average time delay of the packet-switched traffic assuming that the network uses a movable boundary scheme to allocate bandwidth dynamically

In this paper, we compare the use of different types of routing procedures for circuit-switched traffic in nonhierarchical networks. The main performance criterion used is the end-to-end blocking probability. The results show that if the network traffic is light, alternate routing performs better than nonalternate routing, but if the network traffic is heavy, the situation is reversed. To improve the performance of networks using alternate routing, different types of strategies varying from fixed control to dynamic control are introduced. A comparison based on numerical examples shows the improvement in performance attained by using a dynamic control strategy compared to fixed control. Good control techniques result in nonalternate routing under heavy traffic loads; nonalternate routing is the most viable alternative in nonhierarchical networks under heavy traffic conditions.

A common digital transmission facility in a wide-band integrated service digital network (ISDN) provides shared access to a community of heterogeneous users. Traffic demands from these users vary in their arrival rate, their service time, and their bit rate. In order for this type of communication system to handle its traffic demands with high efficiency and flexibility, a close control of access to the shared bandwidth is required. We model the system by a general multiserver queueing system where customers demand service from a random number of servers. If no waiting is allowed, this queueing model is readily analyzed, and various server allocation strategies can be studied. If the various access requests are queued for service, then the system calls for efficient strategies for allocating servers to waiting customers. In this case, exact analysis of the underlying queueing model becomes quite difficult. For this case, we present some analytic and simulation results of the performance of the system under several server allocation policies.

The service quality of a circuit-switched network is usually measured in terms of probability of rejecting a call and the delay encountered by the customers in accessing the common resources. In this paper, a simplen-dimensional birth-death steady-state traffic model is used to evaluate the blocking probability experienced byndifferent classes of customers in a two-way interactive distributed community antenna television (CATV) communication system. In the computation of the end-to-end blocking probability, we have assumed that the links between the call's originating node and the destination node are statistically independent. It is assumed, without loss of generality, that the number of channels (servers) is the same for all the links. In addition to the closed-form solution obtained for different cases, a simple recursive formula that simplifies the computational complexity is presented.

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.

Most of tile present approaches to two-way interactive CATV focus on the centralized approach, in which all traffic must travel to the CATV head end. In this paper, we present a distributed approach, in which intelligent store-and-forward packet switches are to be installed at various locations on the cable. The analysis emphasizes three main criteria: the maximum traffic flow on the cable, the throughput of each switch, and the average message delay. Two possible schemes are compared. In one, the switches appear on the main trunk only. In the second, switches are used at branch locations as well.

A common digital transmission facility provides service to a community of heterogeneous users generating traffic with differing intensity, message length, and bit rate. In order for this type of integrated communication system to handle its traffic demands with high efficiency and flexibility, close control of access and switching at the input node is required. We propose, analyze, and compare two different strategies for managing the access of two types of traffic, a blockable wide-band (WB) type of traffic and a queueable narrow-band (NB) type of traffic, sharing the transmission resource dynamically. The first strategy assigns preemptive priority to the WB traffic over the NB traffic, whereas the second strategy employs a wide-band to narrow-band bit rate compression mechanism. Exact analytic models are developed, and solution methods are presented and implemented. It is shown that the best combined performance is obtained when the two strategies are adaptively combined according to the offered load.

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.

For many time-constrained communication applications, such as packetized voice, a critical performance measure is the percentage of messages which are transmitted within a given amount of time after their arrival at a sending station. We examine the use of a group random access protocol based on time windows for achieving time-constrained communication in a multiple access environment. First, we formulate a policy for controlling protocol operation in order to minimize the percentage of messages with waiting times greater than some given bound. A semi-Markov decision model is then developed for protocol operation and three of the four optimal control elements of this policy are then determined.

In this paper the authors provide a model and analysis of the IBM SNA virtual route pacing control used to control congestion in SNA networks. The model is appropriate to single virtual routes only. The analysis uses a Norton equivalent of the virtual route queueing model. Similar analyses of two other end-to-end window control mechanisms are carried out; one a sliding window with each message individually acknowledged, the other a fixed window control with the final message in the window only producing an acknowledgement, enabling comparisons to be made between all three. The SNA pacing control procedure, in which the first message in a given window induces an acknowledgement, is found to perform within 4 percent of the sliding window mechanism. Simulation results validate the analysis and performance curves obtained. The third window scheme, with the final message in the window generating an acknowledgement, is found to result in considerable reduction in throughput, as expected.

Recently, emphasis has been placed on integrated communication facilities capable of handling both line-switching and packet-switch-ing digital traffic. The problem of dynamically allocating the bandwidth of a trunk to both types of traffic is formulated as a Markovian decision process. Line switching is modeled as a time division multiplexing loss scheme over a varying portion of a fixed time frame. Packet-switching traffic is served through the remaining portion of the frame and requires queueing at the multiplexer-concentrator. Two different cost criteria are examined involving probability of blocking for line switching and average queueing delay for packets. The corresponding optimization problems are presented under reasonable simplifying assumptions. The movable boundary scheme suggested for commercial implementation of integrated multi-plexers is shown to offer optimal or near-optimal performance.

A scheme which multiplexes long messages and single packets using a time-varying frame is presented. Long messages, generated from a fixed number of terminals, immediately access a main trunk, sharing a dynamically dedicated subchannel in a roundrobin fashion. Fixed size packets arrive with Poisson statistics in a FIFO queue and are served through the same trunk, using the remaining capacity. The two traffic categories share an integrated variable length frame. The frame length is determined by the volume of the increasing traffic at the beginning of the frame and cannot exceed a maximum value. Analysis of the performance of the system is carried out using finite population round-robin processor sharing andM/G/Nqueueing techniques. Simplifying modeling assumptions are checked with simulation. A comparison with fixed frame schemes demonstrates the superiority of the variable frame, in terms of more efficient bandwidth utilization.

A routing rule similar in nature to delta-routing [8] is studied in this paper. The approach is to superimpose, local adaptivity on top of a fixed traffic flow distribution. The fixed flow distribution we choose is obtained from the best stochastic (BS) rule [3]. The adaptive part is called the join-biased-queue (JBQ) rule. The resultant JBQ-BS rule is analyzed on small networks and is shown to provide 10-27 percent delay improvement over the BS rule.

DSI (digital speech interpolation) is a technique for increasing the utilization of telephone transmission facilities by allocating transmission channels during intervals of active speech (talkspurts) only. The use of DSI for tandem connections, where DSI links are connected in cascade via circuit switching, poses a problem, however, since the voice-quality degradation that is inevitable in each DSI link can be accumulated to an unacceptable level as the number of DSI links in an end-to-end call connection increases. To cope with this problem, we propose the use of a priority channel assignment technique. An example of such a technique is one that provides preference in channel assignment at each DSI process in a network to calls that have passed through at least one prior DSI link. We evaluate the performance of priority assignment schemes for TASI-type DSI analytically and show that the overall voice-quality degradation of a multi-DSI link call can be improved significantly through the use of priority assignment.

An overview is provided in this paper of the routing procedures used in a number of operating networks, as well as in two commercial network architectures. The networks include TYMNET, ARPANET, and TRANSPAC. The network architectures discussed are the IBM SNA and the DEC DNA. The routing algorithms all tend to fall in the shortest path class. In the introductory sections, routing procedures in general are discussed, with specialization to shortest path algorithms. Two shortest path algorithms, one appropriate for centralized computation, the other for distributed computation, are described. These algorithms, in somewhat modified form, provide the basis for the algorithms actually used in the networks discussed.

The time delay-throughput characteristic of a two-processor system serving two Poisson-arriving job classes through a common queue configuration is investigated and compared to that of a two-processor system, with each processor dedicated to one of the job classes. To carry out the queueing analysis of the common queue scheme an approximate yet accurate expression for the waiting time is introduced. Considerable throughput improvement is found using the common queue model, as would be expected, at the expense of increased waiting time for the shorter job class.

In the multiaccess protocol described in this paper, users are each assigned specific slots of time in which to listen to the channel and determine if the channel is busy or idle. If the channel is idle, a ready user may transmit a fixed length message, or packet; otherwise he must wait a random time and try again. When two or more users transmit simultaneously, none are successful and each must retry after a random time. Though we have considered random slot assignment in general, in this paper we treat only fixed assignment. An interesting special case is when only one user is assigned to each sensing slot. Then there can be no collision and none of the channel capacity is wasted on retransmissions; that is, the channel is conflictfree. Delay-throughput performance curves are presented and compared with some other current multiaccess schemes of interest. Stability considerations are also discussed.

This paper discusses a technique of sharing extra storage buffers among a number of nodes (for example concentrators) or among a number of output lines in a single node (for example, in a message switching center). Buffer sharing can be used to reduce the probability that a message is blocked, while at the same time buffer storage cells can be conserved. In addition, buffer sharing reduces sensitivity to variations in traffic. Although the improvement increases as the size and complexity of the buffer sharing system increases, significant improvement is possible even for relatively simple systems. In modeling these systems, a precise model would use data unit storage. However, a simpler model using message storage is easier to analyze. A linear relationship can be used for converting message storage into data unit storage.

Various algorithms have been proposed for determining the routing paths designed to minimize the average overall message time delay in message-switched networks. In this paper we describe the application of the gradient projection algorithm to this problem. This algorithm is a gradient-type search procedure designed to handle constrained optimization problems, into which category the routing problem falls. Calculations of the computational complexity of this algorithm indicate that it is particularly well-suited to networks with a limited number of commodities or source-destination pairs. The algorithm is applied to a representative group of distributed-type networks, of varying complexity. Execution times for this algorithm are compared with those obtained using the flow deviation routing algorithm. These agree roughly with the results of the computational requirement calculations; i.e., this algorithm generally requires less execution time for networks with a relatively small number of commodities than does the flow deviation method. (The actual running time depends significantly on the choice of the initial flows or routing paths, however.) For those networks in which all network nodes may be expected to communicate with all other nodes, however, the flow deviation method would be expected to be superior.

This paper discusses the problem of congestion in message-switched data communication networks. This condition occurs when more traffic enters a network than can reasonably be served. Two types of techniques employed to control congestion in already existing national networks are identified. A queueing model which can be used to analyze and compare these control schemes for a simple tandem link network is developed. Finally, analytic results are presented which describe the behavior of the simple network using the two control schemes, and which should be useful in the design of more general networks as well.

This paper presents the results of an attempt to develop a rational approach to the design of a practical digital data compression system. The system analyzed is buffer controlled and compresses data by use of a zero-order floating aperture predictor algorithm. For simplicity of analysis and ease in calculation the data to be compressed is modeled as uniformly distributed Markov data. The approach indicated can be extended to other data sources as well. The optimized system selects a set of compressor thresholds or aperture levels, which minimize the mean-squared error between the transmitter input and reconstructed receiver output data. The optimal policy, for this system, is shown to be a function of the present and past contents of the transmitter's buffer, the buffer length, the number of bits of amplitude resolution, the normalized autocorrelation coefficient of the data, and the transmission ratio. The necessary buffer contents for determination of the optimal policy are the queue length and amplitude of the present and past words in the buffer. After making tradeoffs between mean-squared error and buffer size, the optimized system can be implemented with low hardware cost due to the small buffer lengths required.

This paper examines the transmission of binary data signals over channels which contain quadratic nonlinearities and additive Gaussian noise. We consider the case where the channel is nonlinear with memory and where the signal is passed through an input receiver filter and sampled once every signaling interval. The samples are represented by a discrete Volterra series and a special case where the received sample contains a single quadratic distortion term is examined. The optimum (maximum-likelihood) receiver (processor) is derived and upper and lower performance bounds obtained. The performance of a practical, suboptimum receiver is examined by means of computer simulation and is shown to be very close to the lower bound of the optimum receiver. Next we examine the case where the received sample contains two quadratic distortion terms. Again, upper and lower performance bounds are obtained. The performance of a suboptimum receiver which uses nonlinear decision feedback is evaluated by computer simulation. Its performance is shown to be superior to an optimum linear receiver.

In a recent paper [1] we reported on a new mean-square error automatic equalizer utilizing Rosen's gradient projection theorem to optimize parameters in the discrete frequency domain. Here we develop another projection method to optimize the discrete frequency parameters. The algorithm converges (in the mean) for any channel, even in the presence of noise. It is shown that for the channels considered, convergence is equivalent to comparable time domain equalizers. The method makes use of fast Fourier transform (FFT) algorithms for computation of the iteration matrix, the gradient, and the projection operation. Use of the FFT for parameter iterations reduces the necessary computations per parameter to a number proportional tolog_{2} Mcompared toMfor a time domain equalizer, whereMis the number of equalizer parameters. The method results in fewer computations per parameter for each iteration, but a somewhat slower rate of convergence than the method employing Rosen's gradient projection.

A new mean-square-error automatic equalizer for synchronous data transmission is developed. It utilizes Rosen's gradient-projection method to optimize parameters in the discrete frequency domain. The algorithm converges (in the mean) for any channel even in the presence of noise. It is shown that for the channels considered, convergence is faster (in a bounded sense) than for comparable time-domain equalizers.

The use of an information-feedback procedure, called "feedback averaging," is applied to anM-ary polarization-modulated laser communication system. The systems with and without feedback, which are limited by photon fluctuation, are considered and compared. A significant improvement in error rate of a system with feedback is demonstrated over a one-way system for a quarternary system subject to intensity constraint.

This paper concerns itself with the design of an algorithm that will shorten the training period and adaptation time of an adaptive equalizer. Time-invariant or slowly varying channels with white additive Gaussian noise are considered. An adaptive equalizer in the form of a nonrecursive transversal filter reduces the intersymbol interference. The training period consists of the transmission of isolated pulses between which the equalizer is adjusted. The algorithm uses a minimum mean-squared error criterion with a variable step size on each iteration. A fixed number of iterations is allowed for the error to be minimized. A constraint related to the average excess mean-squared error is included, and the set of step sizes is determined by invoking the principle of optimality in dynamic programming. The resulting algorithm is compared to the popular fixed step-size algorithm. Predicted and experimental results are given. A fairly well conditioned and a poorly conditioned channel are considered. Results show that the new algorithm has a faster adaptation time. It is more complex than the fixed step-size algorithm, but for long transversal filters requires little additional computation time.

Currently used adaptive equalizers for the minimization of mean-square error in digital communications commonly employ a fixed-step-size gradient-search procedure. The algorithm to be described here employs variable step sizes designed to minimize the error after a specified number of iterations. The resultant convergence rate provides considerable improvement over the fixed-step-size approach. Bounds on the variance, valid for large signal-to-noise ratios, indicate that the new algorithm not only converges faster, but also has a smaller variance asymptotically than the present algorithm for moderate intersymbol interference and the same variance asymptotically for large intersymbol interference. Computer simulation studies have verified these results.

This paper is concerned with the design of second-order algorithms for an equalizer in a training or a tracking mode. The algorithms govern the iterative adjustment of the equalizer parameters for the minimization of the mean-squared error. On the basis of estimated bounds for the eigenvalues of the signal plus noise correlation matrix, an optimal second-order algorithm is derived. The resultant convergence is considerably faster than the commonly used first-order fixed-size gradient-search procedure. The variance of the optimal algorithm is shown to have a slightly larger bound than the present first-order fixed-step algorithm. However, a computer simulation for an input signal-to-noise ratio of 30 dB shows that for large intersymbol interference the improvement in the convergence of the mean more than compensates for the small increase in variance. For moderate intersymbol interference the simulation shows no variance increase. Suboptimum second-order algorithms with smaller improvement in the convergence rate and smaller increase in the variance bound are also considered. The results indicate that, on the average, the new algorithms lead to faster tracking of changes in the channel characteristics and thereby result in a smaller error rate.

The concepts of abstract vector spaces are summarized and applied to such problems as the detection of binary signals in additive Gaussian noise and the maximum a posteriori estimation of analog signals transmitted over random fading media. Although the results obtained are in most cases well known in the literature, it is felt that the abstract vector approach provides notational and manipulative simplicity that warrants its extension to other problems in detection and estimation theory.

The Neyman-Pearson statistical theory on testing hypotheses has in previous work been applied to the problem of the detection of nonfluctuating constant-amplitude signals embedded in noise. This work is extended in this paper to the case of signal power fluctuating according to a prescribed probability distribution. The effect on system performance of possible correlation between successive signal pulses is taken into account. The introduction of signal fluctuation leads in general to some loss in system performance as compared to the case of nonfluctuating signals. This loss is most pronounced when there is complete correlation between successive signals, and is quite small when successive signals are independent of one another.

A coincidence method of detecting signal in the presence of noise is compared to the statistically optimum Neyman-Pearson procedure utilizing signal integration and threshold detection. In this coincidence procedure a specified number of the fixed group of successive pulses are required to exceed a voltage threshold level. The analysis is carried out for the case of constant-amplitude signals only and the results indicate that the best possible coincidence method requires about 1.4dbmore power than the Neyman-Pearson method.