A prediction-based spectrum access for cognitive radio (CR) is considered. In a typical scenario, CR accesses the communication channels as a secondary user (SU), under the requirement for collisions avoidance with the primary users (PU). In order to meet this requirement, CR frequently senses the communication channels and estimates their availability. Generally, sensing and transmission processes are mutually exclusive, which turns the sensing time into an overhead. Therefore, CR has a strong incentive to predict the future availability of the channels. Consequently, by sensing less, CR is able to increase the proportion of time allocated for the transmissions. We propose a novel analytical model of CR which consists of communication processes and cognitive components. The communication processes include packet arrivals, queueing and transmissions, while the cognitive components include sensing, estimation, multi-step ahead prediction of the channels' states and a component of decision-making. The prediction based policies show a significant improvement in the performance measures of throughput and delay compared to the reactive behavior.

VoIP is rapidly growing and widely used real-time voice service. On the path through the packet-switched networks, the regularity of VoIP stream is impaired by routing, queuing, scheduling and serialization effects, consequently resulting in loss and delay jitter of packets. Achieving high quality real-time voice requires smoothing the delay jitter at the receiver which is generally done by means of jitter buffer mechanism. Although being an important VoIP element, the exact analysis of the jitter buffer is rather rare. In this paper we model the jitter buffer mechanism and carry out the analysis of its performance. The relations between such quantities as initial playout delay, delay jitter and loss are established. Then, these relations are used together with the voice quality evaluation methodologies MOS and E-model, to optimally choose the controlling parameters of the jitter buffer, in order to increase the perceived quality of the voice. The analytic results developed in this work are applicable for incorporation in playout algorithms to achieve better voice quality.

The emergence of network convergence emphasizes the need to support distributed synchronous servers such as TDMoIP (pseudo-wire) and 3G cellular gateways over a packet switched infrastructure. Conse-quently, we formalize the problem of network wide clock frequency synchronization and introduce novel and efficient algorithms to synchronize the frequency among all the clocks in the network with respect to a single frequency. The common thread of our solutions is that they take a network-wide view that accounts for all the clocks in the network and measurements taken over all links to estimate the frequency difference of each clock with respect to the reference clock. The various presented algorithms introduce different trade-offs between the accuracy and the computation complexity. While all our schemes are global, they employ simple pair-wise measurements between neighboring nodes. Consequently, all the algorithms presented in the paper, are simple, easy to implement and require a modest amount of measurement and control traffic. I.

We present a novel approach for the estimation of one-way delays between network nodes without any time synchronization in the network. It is based on conducting multiple and simple one-way measurements among pairs of nodes, and estimating the one-way delays by optimizing the value of a global objective function that is affected by the overall network topology and not just by individual measurements. We examine two objective functions. The first intuitive choice is the least square error (LSE). Using a novel concept of delay-induced link probabilities, we develop a second objective function that is based on the maximum-entropy (ME) principle. Extensive numerical experiments show that both functions considerably outperform the common method of halving the round-trip delays. They also show that ME outperforms the commonly used LSE.

Time synchronization is critical in distributed environments. A variety of network protocols, middleware and business applications rely on proper time synchronization across the computational infrastructure and depend on the clock accuracy. The ''network time protocol" (NTP) is the current widely accepted standard for synchronizing clocks over the Internet. NTP uses a hierarchical scheme in order to synchronize the clocks in the network. In this paper we present a novel non-hierarchical peer-to-peer approach for tune synchronization termed CTP - classless time protocol. This approach exploits convex optimization theory in order to evaluate the impact of each clock offset on the overall objective function. We define the clock offset problem as an optimization problem and derive its optimal solution. Based on the solution we develop a distributed protocol that can be implemented over a communication network and prove its convergence to the optimal clock offsets. For compatibility, the CTP may use the exact format and number of messages used by NTP. We also present methodology and numerical results for evaluating and comparing the accuracy of time synchronization schemes. We show that the CTP substantially outperforms hierarchical schemes such as NTP in the sense of clock accuracy with respect to a universal clock, without increasing complexity.

Several recent studies have proposed methods to accelerate the receipt of a file by downloading its parts from different servers in parallel. This paper formulates models for an approach based on receiving only one copy of each of the data packets in a file, while different packets may be obtained from different sources. This approach guarantees faster downloads with lower network use. However, out-of-order arrivals at the receiving side are unavoidable. We present methods to keep out-of-order low to insure more regulated flow of packets to the application. Recent papers indicate that out-of-order arrivals have many unfavorable consequences. A good indicator to the severeness of out-of-order arrival is the resequencing-buffer occupancy. The paper focuses on the analysis of the resequencing-buffer occupancy distribution and on the analysis of the methods used to reduce the occupancy of the buffer.

In this paper we present a novel approach for the estimation of one-way delays from cyclic-path delay measurements that does not require any kind of synchronization among the nodes of the network. Furthermore, this approach takes into account the asymmetric nature of the network, and the fact that traffic flows are not necessarily the same in both directions. Our approach is based on cyclic-path delay measurements, each of which is extracted using a single (source) clock and therefore is accurate. The basic idea of the approach is to express the cyclic-path delays in terms of one-way delay variables. If there were enough independent cyclic-path delay measurements, then one could solve explicitly for the one-way delays. We show that the maximal number of independent measurements that can be taken is smaller hence a procedure for estimating the one-way delay is proposed.

Mobile agent technology (MAT) seems to promising approach for achieving flexible and decentralised network management. A system independent mobile agent platform is used in order to control the roaming and downloading of the required management code, in the form of mobile agents, onto the network devices. A management task such as the configuration or monitoring of a specific QoS parameter related to a particular application may require that a mobile agent (MA) or a set of MAs should visit several network nodes. We present an approach for enhancing the performance of a mobile agent based network management system by monitoring and controlling the communication paths between the network management applications and the mobile agents. In particular we show that when a mobile agent should act on a set of nodes, the time required to perform a management task is decreased if for the sequence by which the nodes will be visited we take into account the workload on them, i.e. at any time to try to visit the less loaded ones.

The probability distribution of the number of lost packets within a block of consecutive packet arrivals into a finite buffer is an important quantity in various networking problems. In a previous paper, Cidon, Khamisy and Sidi (1993) introduced a recursive scheme to derive this distribution. In this paper, we derive explicit expressions for this distribution using various versions of the powerful ballot theorem. The expressions are derived for a single source M/M/1/K queue.

A network calculus is developed for processes whose burstiness is stochastically bounded by general decreasing functions. This calculus is useful for a large class of input processes, including important processes exhibiting "subexponentially bounded burstiness" such as fractional Brownian motion. Moreover, it allows judicious capture of the salient features of real-time traffic, such as the "cell" and "burst" characteristics of multiplexed traffic. This accurate characterization is achieved by setting the bounding function as a sum of exponentials.

We develop a network calculus for processes whose burstiness is stochastically bounded by general decreasing functions. This calculus enables one to prove the stability of feedforward networks and obtain statistical upper bounds on interesting performance measures such as delay, at each buffer in the network. The bounding methodology is useful for a large class of input processes, including important processes exhibiting "subexponentially bounded burstiness" such as fractional Brownian motion. Moreover, it generalizes previous approaches and provides much better bounds for common models of real-time traffic, like Markov modulated processes and other multiple time-scale processes. We expect that this new calculus will be of particular interest in the implementation of services providing statistical guarantees.

This paper deals with the sizing of end buffers in ATM networks for sessions subject to constant bit rate (CBR) traffic. Our objective is to predict the cell-loss rate at the end buffer as a function of the system parameters. We introduce the D+G/D/1 queue as a generic model to represent exit buffers in telecommunications networks under constant rate traffic, and use it to model the end buffer. This is a queue whose arrival rate is equal to its service rate and whose arrivals are generated at regular intervals and materialize after a generally distributed random amount of time. We reveal that under the infinite buffer assumption, the system possesses rather intriguing properties: on the one hand, the system is unstable in the sense that the buffer content is monotonically nondecreasing as a function of time. On the other hand, the likelihood that the buffer contents will exceed certain level B by time t diminishes with B. Improper simulation of such systems may therefore lead to false results. We turn to analyze this system under finite buffer assumption and derive bounds on the cell-loss rates. The bounds are expressed in terms of simple formulae of the system parameters. We carry out the analysis for two major types of networks: (1) datagram networks, where the packets (cells) traverse the network via independent paths and (2) virtual circuit networks, where all cells of a connection traverse the same path. Numerical, examination of ATM-like examples show that the bounds are very good for practical prediction of cell loss and the selection of buffer size.

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

This paper deals with the sizing of end buffers in ATM networks for sessions subject to constant bit rate (CBR) traffic. Our objective is to predict the cell loss rate at the end buffer as a function of the system parameters. We introduce the D+G/D/1 queue as a generic model to represent exit buffers in telecommunications networks under constant rate traffic and use it to model the end buffer. This is a queue whose arrival rate is equal to its service rate and whose arrivals are generated at regular intervals and materialize after generally distributed random amount of time. We reveal that under the infinite buffer assumption the system possesses rather intriguing properties. On the one hand it is unstable, so that the "steady state" contents of the buffer may exceed any value. On the other hand, in practice, the likelihood of the buffer exceeding even small values is very small. Improper simulation of such systems may therefore lead to false results. We analyze this system under finite buffer assumption and derive bounds on the cell loss rates. The bounds are expressed in terms of simple formulae of the system parameters. We carry out the analysis for two major types of networks: (1) datagram networks, where the packets (cells) traverse the network via independent paths, and (2) virtual circuit networks, where all cells of a connection traverse the same path. Numerical examination of ATM-like examples show that the bounds are very good for practical prediction of cell loss and the selection of buffer size.

This paper introduces a novel method, called the mobilizer, of executing synchronous communication protocols in a cellular mobile environment. First, we present a distributed protocol, called mobile propagation of information (MPI), for broadcasting over a mobile environment. Then, we present the mobile propagation of information with feedback (MPIF) protocol, which can be used to implement this mobilizer, that is, enable synchronous protocols to run over distributed networks with mobile users. The additional message complexity overhead, induced due to the mobilizer, is linear with the number of users' movements.

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

Current high-speed packet switching systems, ATM in particular, have large port buffering requirements. The use of highly integrated ASIC technology for implementing high-degree and high-speed switch fabrics is facing a technology mismatch in the sense that today's chip technology does not allow to integrate on-chip the high-speed switching fabric with the large buffering requirements. Consequently, many designs are based on the principles of queueing displacement, i.e., they attempt to move the queueing point off-chip. This is usually done by considerably speeding-up the on-chip switch output ports and placing a second external stage of buffering between the switch fabric and the outgoing link circuitry. Such designs are very popular and are used by many current ATM switch vendors. While such schemes are widely used, no rigourous analysis has so far been offered to evaluate the design trade-offs and to quantify the design points. The model we use to analyze the performance of the above system is a two-node tandem queueing system. The first node in the tandem corresponds to the internal buffer while the second node in the tandem corresponds to the external buffer. It is assumed that the internal buffer is able to transfer c/sub 1/ cells per time unit to the external buffer, while the external buffer is served at a lower rate of c/sub 2/ cells per time unit.

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

In cellular networks, blocking occurs when a base station has no free channel to allocate to a mobile user. One distinguishes between two kinds of blocking, the first is called new call blocking and refers to blocking of new calls, the second is called handoff blocking and refers to blocking of ongoing calls due to the mobility of the users. We first provide explicit analytic expressions for the two kinds of blocking probabilities in two asymptotic regimes, i.e., for very slow mobile users and for very fast mobile users, and show the fundamental differences between these blocking probabilities. Next, an approximation is introduced in order to capture the system behavior for moderate mobility. The approximation is based on the idea of isolating a set of cells and having a simplifying assumption regarding the handoff traffic into this set of cells, while keeping the exact behavior of the traffic between cells in the set. It is shown that a group of 3 cells is enough to capture the difference between the blocking probabilities of handoff call attempts and new call attempts.

In this paper, we describe an algorithm for designing local-area networks (LANs) with the objective of minimizing the average network delay. The topology design includes issues such as determination of the number of segments in the network, allocating the users to the different segments, and determining the interconnections and routing among the segments. The determination of the optimal LAN topology is a very complicated combinatorial optimization problem. Therefore, a heuristic algorithm that is based on genetic ideas is used. Numerical examples are provided and the quality of the designs obtained by using the algorithm is compared with lower bounds on the average network delay that are developed.

Continually growing number of users have to exchange increasing amounts of information. Local area networks (LANs) are commonly used as the communication infrastructure that meets the demands of the users in the local environment. These networks typically consist of several LAN segments connected together via bridges. The authors describe an algorithm for designing LANs with the objective of minimizing the average network delay. The topology design includes issues such as determination of the number of segments in the network, allocating the users to the different segments and determining the interconnections and routing among the segments. The determination of the optimal LAN topology is a complicated combinatorial optimisation problem. Therefore, a heuristic algorithm which is based on genetic ideas is used. Numerical examples are provided and the quality of the designs obtained by using the algorithm is compared with lower bounds on the average network delay that are developed.

Consider a switching component in a packet-switching network, where messages from several incoming channels arrive and are routed to appropriate outgoing ports according to a service policy. One requirement in the design of such a system is to determine the buffer storage necessary at the input of each channel and the policy for serving these buffers that will prevent buffer overflow and the corresponding loss of messages. In this paper, a class of buffer service policies, called Least Time to Reach Bound (LTRB), is introduced that guarantees no overflow, and for which the buffer size required at each input channel is independent of the number of channels and their relative speeds. Further, the storage requirement is only twice the maximal length of a message in all cases, and as a consequence the class is shown to be optimal in the sense that any nonoverflowing policy requires at least as much storage as LTRB.

Tracking strategies for mobile users in wireless networks are studied. In order to save the cost of using the wireless links mobile users should not update their location whenever they cross boundaries of adjacent cells. The paper focuses on three natural strategies in which the mobile users make the decisions when and where to update: the time-based strategy, the number of movements-based strategy, and the distance-based strategy. The authors consider both memoryless movement patterns and movements with Markovian memory along a topology of cells arranged as a ring. They analyze the performance of each one of the three strategies under such movements, and show the performance differences between the strategies.>

The authors study discrete-time, single server queueing systems, with messages that consist of blocks of consecutive cells. They focus on the model of dispersed cell generation processes which naturally arises in packet switched networks such as ATM. Several important performance measures are considered. These are the message delay process, the maximum delay of a cell in a message and the number of cells in a message whose delays exceed a pre-specified time threshold. The latter two quantities are important for proper design of playback algorithms and time-out mechanisms. They present a new analytical approach that yields efficient recursions for the computation of the probability distribution of each quantity. Numerical examples are provided to compare this distribution with the distribution obtained by using an independence assumption on the cell delays. These examples show that the correlation between cell delays of the same message has a strong effect on each of these quantities.>

Considers virtual circuit packet switching communication networks that employ processor sharing type service disciplines and studies their stability when the offered traffic to the network has exponentially bounded burstiness (EBB). The authors employ an exponential characterization (EBB) introduced in a previous work to analyze this type of system in a stochastic setting. They first examine the GPS and PGPS servers in isolation, and demonstrate their superiority to a general server in the stochastic environment. They then show that a network of servers, that are all either GPS or PGPS, is stable whenever the service rate of each node is larger than the total arrival rate to it. In addition, they provide exponential upper bounds to the traffic flows within the network links, and to the backlogs of each session in the various nodes on its path.>

Provides an analysis of a rate-based access control scheme in high speed environments based on a buffered leaky bucket algorithm. The analysis is carried out in discrete time which is representative of an ATM environment. For the cell arrivals to the leaky bucket the authors consider a general discrete Markovian arrival process which models bursty and modulated sources. The key of the analysis is the introduction of the deficit junction that allows the reduction of the original problem to a more standard discrete time queueing system with the same arrival process. As an important special case, the detailed analysis of the binary Markov source throttled by such rate-based access control schemes is presented. Along with explicit recursions for computation of state probabilities and simple characterisation of the asymptotic behavior of the queue build up, some guidelines for the parameter selection of these schemes are provided. The results indicate that for sources with relatively large active periods, for an acceptable grade-of-service at the input queue, the token generation rate should be chosen to be close to the peak rate of the source, and increasing the bucket size of the leaky bucket does not improve substantially the performance at the input queue.>

A synchronizer is a compiler that transforms a program designed to run in a synchronous network into a program that runs in an asynchronous network. The behavior of a simple synchronizer, which also represents a basic mechanism for distributed computing and for the analysis of marked graphs, was studied by S. Even and S. Rajsbaum (1990) under the assumption that message transmission delays and processing times are constant. We study the behavior of the simple synchronizer when processing times and transmission delays are random. The main performance measure is the rate of a network, i.e., the average number of computational steps executed by a processor in the network per unit time. We analyze the effect of the topology and the probability distributions of the random variables on the behavior of the network. For random variables with exponential distribution, we provide tight (i.e., attainable) bounds and study the effect of a bottleneck processor on the rate.>

A family of queues for which the service time B/sub n/ of customer n depends on the interarrival time I/sub n/ between customers n-1 and n and the random variables I/sub n/ and B/sub n/ exhibit a proportionality relation is studied. In particular, the focus is on dependencies that arise naturally in communication systems, where the finite speed of the communication links constrains the amount of data that can be received in a given time interval. The simple case of a deterministic proportionality relation between the service time of a customer and its preceding interarrival time is considered and extended to allow the addition of an independent, generally distributed overhead to the service time. Several models that capture the on-off behavior of communication links in packet networks are then addressed. In all cases, expressions for the delay experienced by a packet in the system and illustrative numerical examples are provided.>

A family of queuing systems in which the interarrival time I/sub n+1/ between customers n and n+1 depends on the service time B/sub n/ of customer n is considered. Specifically, cases where the dependency between I/sub n+1/ and B/sub n/ is a proportionally relation and B/sub n/ is an exponentially distributed random variable is considered. Such dependencies arise in the context of packet-switched networks from employing rate policing functions which regulate the amount of data that can arrive at a link within any given time interval. The models developed and the associated solutions are, however, of independent interest and potentially applicable to other environments. Several scenarios that consist of adding an independent random variable to the interarrival time, allowing the proportionality to be random, and the combination of the two are considered. Numerical results are compared to those for an equivalent system without dependencies.>

The authors study the message queuing delays in a node of a communication system, where a message consists of a block of consecutive packets. Two types of message generation process are distinguished. The message can be generated as a batch or it can be dispersed over time. The authors focus on the dispersed generation model. The main difficulty in the analysis is due to the correlation between the system states observed by different packets of the same message. A technique for analyzing the message delay in such systems for different arrival models is introduced, and it is shown that the correlation has a strong effect on the performance of the system. For an M/M/1 system with variable size messages, an explicit expression for the Laplace-Stieltjes transform (LST) of the message delay is obtained. It is shown that the commonly used independence assumption can lead to wrong conclusions.>

A way to calculate the performance of packet switching communication networks under a fixed (session-based) routing strategy, based on properly bounding the probability distribution functions of the system input processes, is proposed. The bounds suggested, which are decaying exponentials, posses three convenient properties. When the inputs to an isolated network element are all bounded, they result in bounded outputs and ensure that the delays and queues in this element have exponentially decaying distribution. In some network settings, the bounded inputs result in bounded outputs. Finally, natural traffic processes can be shown to satisfy such bounds. These properties enable the calculation of upper bounds for all the interesting parameters of network performance, in a variety of settings.>

An approach to congestion control based on open-loop regulation of the input is investigated. The input rate regulation schemes are studied from the viewpoint of their smoothing and regulating effects on the incoming traffic. The smoothing effect is characterized by the variance of the interdeparture time of the packet departure process from the input rate regulation mechanism. Under the assumption of Poisson arrivals the characteristics of this departure process are explicitly derived in terms of the particular scheme's parameters, and the tradeoff between the smoothness of the departure process and packet waiting time is studied. Results for both finite- and infinite-buffer pool sizes are presented.>

A family of queues is studied for which the service time B/sub n/ of customer n and the interarrival time I/sub n/ between customers n-1 and n exhibit some sort of proportionality. The focus is on dependencies that arise naturally in the context of communication systems, where the finite speed of the communication links constrains the amount of data that can be received in a given time interval. The simple case of a deterministic proportionality relation between the service time of a customer and its preceding interarrival time is considered. This is extended to allow the addition of an independent, generally distributed overhead to the service time of each customer. Several models that capture the ON-OFF behavior of communication links in packet networks are considered. In all cases, expressions for the delay experienced by a packet in the system are provided. Numerical examples illustrate the impact of dependencies through comparison with less accurate models. The results should be of relevance to environments other than communication as well.>

The packet loss process in a single-server queueing system with a finite buffer capacity is analyzed. The model used addresses the packet loss probabilities for packets within a block of a consecutive sequence of packets. An analytical approach is presented that yields efficient recursions for the computation of the distribution of the number of lost packets within a block of packets of fixed or variable size for several arrival models and several numbers of sessions. Numerical examples are provided to compare the distribution obtained with that obtained using the independence assumption to compute the loss probabilities of packets within a block. The results show that forward error correction schemes become less efficient due to the bursty nature of the packet loss processes; real-time traffic might be more sensitive to network congestion than was previously assumed; and the retransmission probability of ATM messages has been overestimated by the use of the independence assumption.>

A class of binary trees that grow in a random environment, where the state of the environment can change at every vertex of the trees, is studied. The trees considered are single-type and two-type binary trees that grow in a two-state Markovian environment. For each kind of tree, the conditions on the environment process for extinction of the tree are determined, and the problem of calculating the expected number of vertices of the tree is addressed. Different ways of growing the trees are compared.>

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

A method for evaluating the performance of packet switching communication networks under a fixed, session-based, routing strategy is proposed. The approach is based on properly bounding the probability distribution functions of the system input processes. The suggested bounds which are decaying exponentials, possess three convenient properties. When the inputs to an isolated network element are all bounded, they result in bounded outputs and assure that the delays and queues in this element have exponentially decaying distributions. In some network settings, bounded inputs result in bounded outputs. Natural traffic processes can be shown to satisfy such bounds. Consequently, this method enables the analysis of various previously intractable setups. Sufficient conditions are provided for the stability of such networks, and derive upper bounds for the parameters of network performance are derived.>

An efficient recursive computation methodology is introduced to obtain the exact distribution of the number of lost packets in a block of packet arrivals of a given size for different arrival models and a different number of sessions. The exact distribution is compared with the distribution obtained from an independence assumption on the loss probability of packets. Numerical examples are provided to show that the exact distribution may be worse than the distribution obtained under the independence assumption for applications such as forward error correction or better for applications such as straight message retransmission.>

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

A study is made of a class of binary trees that grow in a random environment, where the state of the environment can change at every vertex of the trees. Such trees arise in multiaccess communication. The trees considered are single-type and two-type binary trees that grow in a two-state Markovian environment. For each kind of tree, the conditions on the environment process for extinction of the tree are determined, and the problem of calculating the expected number of vertices of the tree is addressed. Different ways of growing the trees are compared.>

A class of discrete-time priority queueing systems with Markov modulated arrivals is considered. In these systems, N queues are served by a single server according to priorities that are preassigned to the queues. Packet arrivals are modeled as discrete-time batch processes with a distribution that depends on the state of an independent common two-state Markov chain. This allows coverage of a wide range of applications in computer and communication systems when the parameters of the arrival processes are not fixed in time but vary according to the state of the underlying Markov chain. The steady-state joint generating functions of the queue length distributions of this class of systems are derived. From these, moments of the queue lengths as well as average time delays can be obtained. A numerical example provides some insight into the behavior of such systems. Also, the effect of the transition rate between the states of the modulating Markov chain on the average time delay in the system is investigated for different patterns of loads on the queues of the system.>

The implementation of a local area network based on a passive optical star is considered. Two distributed synchronization problems are addressed: (1) generating a global event clock for synchronizing the nodes' operation, and (2) distributed scheduling for accessing the shared passive medium, which is a hybrid (deterministic and random) technique. A hybrid scheduling algorithm is presented that is fair and equivalent to a distributed queue.>

The analysis of a rate-based access control scheme in high speed environments that is based on a buffered leaky bucket algorithm is presented. The analysis is carried out in discrete time, which is representative of asynchronous transfer mode environments. For the cell arrivals to the leaky bucket, a general discrete Markovian arrival process is considered which models bursty and correlated sources. The introduction of the deficit function allows the reduction of the original problem to a more standard discrete time queuing system with the same arrival process. As an important special case, the detailed analysis of the binary Markov source throttled by such rate-based access control schemes is presented. Along with explicit recursions for computation of state probabilities and simple characterization of the asymptotic behavior of the queue buildup, some guidelines for the parameter selection of these schemes is provided.>

The authors analyze polling systems with multiple types of simultaneous arrivals, namely, batches of customers may arrive at the different queues at an arrival epoch. The authors consider cyclic polling systems with N queues, general service time distribution in each queue, and general switchover times. For both the exhaustive and the gated service disciplines the authors derive the necessary equations for computing the N expected waiting time figures. A pseudo conservation law for these system is also derived. The authors compare several special cases of the correlated arrivals polling system, discuss the computational aspects of the numerical method, and examine the applicability of the analysis to other polling systems.>

The cyclic polling model, its enhancement by customer routing, and the replacement of a fixed polling order by a random polling order are reviewed. Modeling of polling systems, performance improvement, and system optimization issues are discussed. Examples are given that include token rings, ARQ and time-sharing schemes, random-access protocols, robotics and manufacturing systems. Emphasis is not on the analytical derivations of polling systems but rather on the description of the capabilities and limitations of the different polling models.>

A selective-repeat automatic-repeat request (SR ARQ) system model in which packets arrive at the transmitter according to a general renewal process is analyzed. The overall delay of a packet in a system that operates under the SR ARQ protocol consists of the queuing delay at the transmitter and the resequencing delay at the receiver. The joint distribution of the buffer occupancies at the transmitter and at the receiver is derived, and the tow types of delay are compared using numerical examples.>

Recursive formulas are derived for computing the state probabilities in priority queuing systems (preemptive and nonpreemptive). The derivation is based only on the general structure of the generating function involved, and thus is similar and more general than previous methods. Also discussed are the applications of the method to other queuing systems.>

Multiaccess networks in which the shared channel is noisy are considered. A slotted-time collision-type channel, Poisson infinite-user model, and a ternary feedback are assumed. Due to the noise in the shared channel, the received signal may be detected as a collision event though no message or a single message is transmitted. This kind of imperfect feedback is referred to as an error. A common assumption in all previous studies of multiaccess algorithms in channels with errors is that the channel is memoryless. The problem of splitting algorithms when the channel is with memory is considered here. A two-state first-order Markovian model for the channel is introduced and the operation of the tree collision resolution algorithm in this channel is analyzed. A stability result, i.e. the necessary conditions on the channel parameters for stability conditions hold, the throughput of the algorithm is calculated. Extensions to more general channel models are discussed.>

An analysis is made of polling systems with correlated arrivals, namely, systems in which the arrival processes of customers to the queues are not assumed to be independent. The authors consider cyclic polling systems with N queues, general service time distribution in each queue, and general switch-over times. For both the exhaustive and the gated service disciplines they derive the necessary equations for computing the N expected waiting time figures. A 'pseudo' conservation law for these systems is also derived. The analysis approach can be applied to other polling systems with correlated arrivals.>

New distributed dynamic channel assignment algorithms for a multihop packet radio network are introduced. The algorithms ensure conflict-free transmissions by the nodes of the network. The basic idea of the algorithms is to split the shared channel into a control segment and a transmission segment. The control segment is used to avoid conflicts among nodes and to increase the utilization of the transmission segment. It is shown how these algorithms can be used in order to determine time-division multiple access (TDMA) cycles with spatial reuse of the channel.>

The performance of a multistation packet-radio network in which the nodes of the network employ some collision resolution algorithm (CRA) for accessing a shared radio channel is analyzed. The two CRAs considered here are the binary-tree CRA (BTCRA) and the clipped binary-tree CRA (CBTCRA). The exact analysis of a multistation network with these access schemes is intractable. Therefore, the authors present an approximate method that captures the interactions among the nodes of different stations. The mean idea is to view the interference among the nodes of different stations as independent random noises and compute the probabilities of these noises, taking into account the interactions between the nodes. Numerical results of the approximate analysis are presented and compared with the results of simulations.>

A multistation packet radio network with m stations and a finite number of nodes n that uses a conflict-free protocol to access the backbone network of stations through a shared channel is discussed. The goal is to derive an allocation of the channel time slots (time-division multiplexing cycle), so that all transmissions will be conflict-free and some measure of performance (e.g., the expected total weighted throughput, the expected weighted holding cost) will be optimized. The methodology that is used is to bound the performance and to allocate the slots according to the golden ratio policy.>

An ALOHA-type communication system with many nodes accessing a common receiver through a time-slotted shared radio channel is considered. Due to topological and environmental conditions, the receiver is prone to fail to detect some or all of the packets transmitted in a slot; this phenomenon is called erasure. The receiver may also capture, that is, detect a single transmission out of many. In addition, noise errors may cause the receiver to detect nonexistent collisions. Using the feedback information regarding the detection of zero or one packet or a collision at the receiver, the nodes determine their transmission policy. A class of decentralized multiaccess algorithms that maintain system stability under the above phenomenon is presented, and the maximal throughput they can support is determined. The maximal throughput of these algorithms is insensitive to some noise errors and erasures.>

Multi-access networks are considered in which the shared channel is noisy. The authors assume a slotted-time collision-type channel, Poisson infinite-user model, and binary feedback. Due to the noise in the shared channel, the received signal may be detected as a collision even though no message or a single message is transmitted. This kind of imperfect feedback is referred to as error. A common assumption in all previous studies of multi-access algorithms in channels with errors is that the channel is memoryless. The authors consider the problem of splitting algorithms when the channel has memory. They introduce a two-state, first-order Markovian model for the channel and analyze the operation of the tree collision-resolution algorithm in this channel. They obtain a stability result, i.e., the necessary conditions on the channel parameters for stability of the algorithm. Assuming that the stability conditions hold, they calculate the throughput of the algorithm. Assuming that the stability conditions hold, they calculate the throughput of the algorithm. Extensions to more general channel moders are discussed.>

Distributed dynamic channel assignment algorithms for a multihop packet radio network are introduced. The algorithms ensure conflict-free transmissions by the nodes of the network. The basic idea of the algorithms is to split the shared channel into a control segment and a transmission segment. The control segment is used to avoid conflicts among the nodes and to increase the utilization of the transmission segment. It is shown how these algorithms can be used to determine time-division multiaccess cycles with spatial reuse of the channel.>

The authors model the internal structure of a packet-switching node in a real-time system and characterize the tradeoff between throughput, delay, and packet loss as a function of the buffer size, switching speed, etc. They assume a simple shared-single-path switch fabric, though the analysis can be generalized to a wider class of switch fabrics. They show that with a small number of buffers the node will provide a guaranteed delay bound for high-priority traffic, a low average delay for low-priority traffic, no loss of packets at the input and low probability of packet loss at output.>

Multiple-access algorithms that handle erasures as well as captures are introduced. The algorithms are evaluated according to the maximal throughput that they can support for a Poisson arrival process. An example is given which shows that, in practice, the positive effect of captures compensates the negative effect of erasures. An approach that effectively utilizes the capture phenomena is introduced. This approach incorporates a random power-level-selection scheme that allows each node to choose randomly to transmit in one of several allowable levels of power. Design issues such as number of levels, selection schemes, etc. are discussed.>

The application of group testing techniques to the design of efficient algorithms for multiaccess systems with a heterogeneous population of users is studied. For a reservation system with binary (something/nothing) feedback, the authors present the procedure used to determine the optimal nested multiaccess algorithms. This procedure is not practical for moderate and large numbers of heterogeneous users because the computations and memory required for their determination are exponential in the number of users. Consequently, the authors introduce the notion of ordered algorithms and present the procedure for determining the optimal ordered algorithm. The computational complexity and memory requirements of this procedure are polynomial in the number of users. To show the effectiveness of ordered algorithms, the performance of optimal ordered algorithms for various orders is studied and compared to the performance of simpler suboptimal ordered algorithms and with optimal nested algorithms. The authors also study the performance of nested multiaccess algorithms (based on group testing procedures) for a direct transmission system with ternary feedback when the population of users is very large, and, for simplicity, a system with two classes of users.>

The standard model of a multiple-access channel with ternary feedback is considered. When packets of a batch of k nodes initially collide, it is assumed that no a priori statistical information about k is available. An algorithm is presented and analyzed that enables the nodes to compute a statistical estimate of k. Combining the estimation procedure with tree algorithms leads to batch-resolution algorithms that resolve conflicts more efficiently than any other reported to date. Both complete-resolution and partial-resolution algorithms are presented.>

Algorithms for accessing a slotted-time collision-type broadcast are considered under a Poisson infinite-user model, where each user observes the channel and determines for each slot whether idle or success or collision has occurred. The highest throughput previously achieved for this model is 0.4878. A new scheme is introduced which does not exceed the limitations of the system model, yet achieves a throughput of 0.4892. Extra information is added to the message that can be used only when the message is received successfully. One form of extra information is described, and a new algorithm that exploits it is proposed.>

A class of discrete-time priority queueing systems with partial interference is considered. In these systems,Nnodes share a common channel to transmit their packets. One node uses a random access scheme, while other nodes access the channel according to preassigned priorities. Packet arrivals are modeled as discrete-time batch processes, and packets are forwarded through the network according to fixed prescribed probabilities. Steady-state analysis of the class of systems under consideration is provided. In particular, we present a recursive method for the derivation of the joint generating function of the queue lengths distribution at the nodes in steady state. The condition for steady state is also derived. A simple example' demonstrates the general analysis and provides some insights into the behavior of systems with partial interference such as multihop packet radio systems.

Distributed algorithms for the detection and resolution of deadlocks in store-and-forward computer communication networks are presented and validated. The algorithms use a fixed amount of storage at each node (that is independent of the size of the network). The detection algorithm is simple but requires network-wide coordination. The resolution algorithm is based on earlier approaches, but uses the network-wide coordination to address certain synchronization problems. When the detection and resolution algorithms are merged, it is guaranteed that packets will arrive at their destinations in finite time.

Tandem packet-radio systems are considered. The nodes of the tandem have infinite buffers, they share a common radio channel for transmisison of data packets and each node transmits whenever it has a packet ready for transmission. An approximate analysis is developed for an arbitrary tandem. The approximation uses the exact results obtained for a four-node tandem and is based on exploiting the special features of tandem systems. The approximation is compared with simulation results and very good agreement is observed.

A system with many nodes accessing a common receiver is considered. The forward channel is a time-slotted collision-type common radio channel. Due to a nonreliable forward channel, the receiver may misinterpret the actual event of a slot. For instance, an idle or a success slot can be interpreted as a conflict and a conflict or a success slot can be interpreted as an idle slot. The former kind of error is called a noise error, while the latter is called an erasure. Splitting multiple-access algorithms are introduced that can handle erasures as well as noise errors. A remarkable feature of the algorithms is that they ensure that, under stable operation, all packets are eventually successfully transmitted, including the erased packets (those packets that were involved in an erasure). The property that is exploited in devising these algorithms is that nodes whose packets were erased can detect that situation as they transmit and acknowledge that the slot was idle. Consequently, they can either retransmit immediately or wait until some agreed point in time (such as the end of a collision resolution interval) and then transmit. The performances of the proposed algorithms are evaluated according to the maximal throughput they can support for Poisson arrival process. The performance degradation due to erasures and noise errors is quantified.

A distributed algorithm for the detection of deadlocks in store-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most O(n2+ m) messages and O(log (n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which cause the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.

In many communication systems, the stronger of two or more overlapping packets might capture the receiver and thus be received without error. The effect of capture on collision-resolution algorithms in a slotted ALOHA type broadcasting network is investigated here. Extensions to the algorithms are suggested for both the situations in which the receiver can or cannot distinguish between success slots and capture slots. In particular, we present a class of retransmission schemes for packets that have been transmitted during capture slots but have not been received correctly. The performance analysis is confined to a simplified model in which the nodes of the network are divided into two groups and only packets sent by the nodes of one of them might be captured. For this simplified model and for each extended algorithm, explicit recursive equations are given, from which the average conditional collision-resolution interval length, as well as the maximal throughput, can be determined. As expected, we show that in the presence of capture, the performance of the network is improved and the maximal attainable throughput is increased. Extensions of the simplified model such as dividing the nodes intoKgroups instead of two, or considering the situation that capture depends on relative distances and transmission powers, are also discussed. For the latter situation we give simulation results.

The effect of capture on splitting-type protocols in a slotted ALOHA broadcasting network is investigated. At first, it is assumed that the nodes of the network are divided into two groups, and only packets sent by nodes of one of the groups might be captured. The situation in which the receiver can distinguish between success slots and capture slots and that in which it cannot are both considered. For each of these situations, splitting-type multiple access protocols are described and their performance in terms of achievable throughputs is evaluated. Extensions of these protocols to a general capture model are also discussed.

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

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

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

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