This paper proposes an optimization as an extension to a swarm-like styled, collaborative multicast routing protocol designed for unidirectional ad-hoc networks - called MUNet. MUNet is inspired by swarm intelligence and further motivated by collaboration discovery. The concept of spatial locality suggests the use of neighbor nodes for network resilience (i.e. path self-healing and shortening.) Potential link breakage can be prevented collaboratively by reinforcing neighbor nodes, prior to any costly time-consuming link recovery. Critical path is shortened when exists. In unidirectional ad-hoc networks where essential feedback does not exist at the MAC layer, neighbor collaboration, while increasing network resilience, can adversely affect the overall routing performance. In order to improve routing efficiency and resource utilization, the optimization applies a heuristic feature into the original MUNet protocol. Instantaneously determined by local control traffic density, a node probabilistically sets a level of its responsiveness to participate in the routing protocol maintenance. Compared with the original MUNet and ODMRP using GlomoSim, the proposed optimization mechanism shows a significant reduction on routing overhead along with an improvement on protocol effectiveness.

Reducing packet loss and increasing overall efficiency in multiple source queuing systems is one of the most important issues in the design of traffic control algorithms. On the other hand, the other important issue in such systems is to provide every individual source with the ability to take advantage of a fair portion of the shared available resources such as buffer space or server bandwidth. In this paper a novel technique for reducing packet loss in a class of queuing systems with self-similar traffic patterns is introduced. The technique takes advantage of the modeling power of neural networks to offer a dynamic buffer management scheme capable of efficiently addressing the trade off between packet loss and fairness issues.

We present a four-state discrete-time Markov-modulated Poisson process (DMMPP) to characterize multimedia traffic which exhibits both short-term and long-term correlation. By taking advantage of the correlation structure of a two-state DMMPP, we can construct a four-state DMMPP by superposing two two-state DMMPPs in which one two-state DMMPP captures the short-term correlation of arrivals and the other two-state DMMPP captures the long-term correlation of arrivals. We have developed a systematic algorithm to match eight parameters of two two-state DMMPPs which can exactly capture the mean and the variance of the measured trace and also closely fit the probability mass function and the autocorrelation function. In addition, we present two experiments of traces, including a computer-generated trace and a measured trace. The results show that under certain time scales this four-state DMMPP model can capture the statistical behavior of the arrival process and predict the queueing performance very well.

A new data traffic control scheme is developed for maintaining the packet error rate (PER) of real-time voice traffic while allowing nonreal-time data traffic to utilize the residual channel capacity of the multi-access link in an integrated service wireless CDMA network. Due to the delay constraint of the voice service, voice users transmit their packets without incurring further delay once they are admitted to the system according to the admission control policy. Data traffic, however, is regulated at both the call level (i.e., admission control) and at the burst level (i.e., congestion control). The admission control rejects the data calls that will otherwise experience unduly long delay, whereas the congestion control ensures the PER of voice traffic being lower than a specified quality of service (QoS) requirement (e.g., 10/sup -2/). System performance such as voice PER, voice-blocking probability, data throughput, delay, and blocking probability is evaluated by a Markovian model. Numerical results for a system with a Rician fading channel and DPSK modulation are presented to show the interplay between admission and congestion control, as well as how one can engineer the control parameters. The tradeoff of using multiple CDMA codes to reduce the transmission time of data messages is also investigated.

In this paper, we introduce a procedure for modelling the output process of a finite discrete time queue with selective discard mechanism loaded with a prioritized discrete-time batch Markovian arrival process in which the priority level of a cell depends on the priority level of other cells in the flow. We show through numerical examples that this procedure is reasonably accurate. Moreover, we introduce a framework for the analysis of queueing networks with D-BMAP/sup [H,L]/ flows.

Several types of network traffic have been shown to exhibit long-range dependence (LRD). In this work, we show that the busy period of an ATM system driven by a long-range dependent process can be very large. We introduce a new traffic model based on a fractional Brownian motion envelope process. We show that this characterization can be used to predict queueing dynamics. Furthermore, we derive a new framework for computing delay bounds in ATM networks based on this traffic model. We show that it agrees with results given by large deviation theory with less computational complexity.

In this paper we present a new state estimation method based on the leaky bucket (LB) mechanism. It is called the multi-level leaky bucket (MLLB) and can be used to determine the current state of a multirate source, e.g, a Markov modulated process. The MLLB provides information about the instantaneous bit rate of a source allowing more effective flow control. We compare the performance of our mechanism to a simple leaky bucket. We show that our mechanism is able to police both the average bit rate and the average burst duration of a source which cannot be policed by a single leaky bucket. Our results were obtained by a simulation of both mechanisms.

Multipath source routing schemes can be distinguished by their choice of allocation granularity. The schemes proposed in the literature advocate a per-connection allocation wherein all the packets of a connection are constrained to follow the same path. The authors believe that a smaller allocation granularity permits a finer control to be exerted and would result in improved performance, especially in the presence of bursty traffic sources. A simple two-node network is used to compare the performance of both allocation schemes. An analytical model is developed to compute the resequencing delay distribution for the per-packet allocation. It is observed that as the burstiness of the arrival process increases, the per-packet allocation is able to accommodate bursts in a more graceful fashion, resulting in better performance. The per-packet allocation also permits a more equitable distribution of network resources than the per-connection.>

A routing architecture applying the concept of multichannel transmission groups (MCTGs) for ATM systems is proposed. A queuing analysis of an internally nonblocking ATM switch employing this MCTG concept with partially shared output buffers is presented. The analysis is based on the discrete-time D/sup /A///D/c/B queuing model. Both bulk input traffic bulk-size distribution (A) and deterministic traffic (D/sub 1/+. . .+D/sub N/) are considered. The impact of switch speedup on the performance is also taken into account. It is shown that the MCTG architecture yields better performance in terms of delay and cell loss probability than its single channel counterpart. It is also found that the switch speedup required to closely approximate the optimal performance obtained by having the switch fabric run N times as fast as the input and output channels, where N is the size of the switch, is rather small compared to N. This makes the practical realization of the proposed switch architecture feasible.>

Methods for determining the network reliability of a multihop packet radio network in the presence of hostile jammers are discussed. A new connectivity parameter called radio connectivity is defined as the maximum number of disjoint communication paths that are still usable between given nodes s and d after the jammer is on or, more generally, the minimum number of jammers needed to disconnect s and d. A lower bound on the radio connectivity is computed by studying the number of jamming independent paths. The time complexity of obtaining the radio connectivity is analyzed and shown to be NP-hard except for some special cases. Greedy heuristics for developing approximate answers for general networks are described. Euclidean networks, in which the nodes and links correspond to points and line segments in the Euclidean geometry and satisfy Euclid's four fundamental axioms, are also discussed. It is found that the maximum number of independent paths between a pair of source and destination nodes that can possibly exist is five. An extension in which there is a protected zone of known size around the sender and receiver is studied.>

The authors study data link error control protocols suitable for point-to-multipoint communication where data are delivered to the destinations in the order they are sent. They study a series of adaptive protocols differing in the way that the sender uses the outcomes of the previous transmissions. The protocols are based on the go-back-N schemes discussed by I.S. Gopal and J.M. Jaffe (1984), whose protocols are generalized to the case where multiple copies of a message are sent (instead of just a single copy). The optimum number of copies is determined and is found to depend on how many receivers have not yet received the message. These adaptive protocols can be applied to all three basic ARQ (automatic repeat request) schemes, namely, stop-and-wait, go-back-N, and selective-repeat. A dynamic programming technique is used to solve this optimization problem. A throughput comparison shows that, by sending the optimum number of copies of a data frame instead of just a single copy, the performance will be significantly improved.>

The multiobjective routing problem in multiple-class integrated services networks is presented. A multiserver two-class queuing model is introduced, where packets from the first class can be queued, while packets from the other class are blocked when the number of packets in the system exceeds some threshold. Therefore, the first class wants to minimize its average packet delay, while the other class wants to minimize its blocking probability. The resulting multiobjective routing problem is formulated as a Nash game, where each class tries to minimize its own cost function in competition with the other class. The routing policy for a two-server parallel system is derived and the strategy and performance of each class are shown.>

A high-bandwidth reconfigurable asynchronous transfer mode (ATM) switch fabric is proposed. The design is modular to allow for expansion to a large switch size and is feasible for implementation with current technology 2*2 buffered electronic crossbar switches. It uses wavelength division multiplexing of fiber channels in combination with nonagile tunable laser diodes. A novel approach for reconfiguration of the switch fabric is proposed. It is shown that with relatively low hardware overhead, a highly reliable switch fabric can be achieved while maintaining high bandwidth. Maximum fault tolerance is studied by mapping to the marriage problem of graph theory. The results provided by this approach significantly reduce the tuning range needed for reconfiguring the switch.>

The problem of furnishing an asynchronous transfer mode (ATM) based broadband-ISDN (B-ISDN) with two bearer services supporting different grades of transfer quality is addressed. The focus is on priority bandwidth and buffer management in the ATM communications nodes (switches, multiplexers or concentrators, and expanders) in the context of a multichannel network architecture. Detailed queueing analyses and simulations and results are provided to evaluate the differentiation between traffic classes that can be achieved by different strategies. The implementation complexity of the different schemes is discussed. Various priority queueing strategies characterized mainly by different degrees of resource sharing and a general system model for performance evaluation are introduced. Performance comparisons and design tradeoffs are addressed.>

A set of computer-based modeling tools to help understand the performance and behavior of spread spectrum networks is presented. These tools allow for numerical evaluation of important network performance measures and experimentation with network parameters. A connectivity model for a direct sequence spread spectrum packet radio network which allows the computation of network throughput and can be used to study routing techniques is discussed. This model places direct sequence spread spectrum networks on an equal footing with narrowband networks which have been modeled using the collision channel and transmission range concepts. The mathematical models and algorithms used to evaluate network performance are described, and several examples are presented to demonstrate the impact of various parameters.>

A large-scale asynchronous transfer mode (ATM) switch fabric that can be constructed with currently feasible technology is proposed. Based on analysis of the technology, it is found that module interconnection becomes the bottleneck for a large fast packet switch. Fault tolerance for the switch is achieved by dynamic reconfiguration of the module interconnection network. The design improves system reliability with relatively low hardware overhead. An abstract model of the replacement problem for the design is presented, and the problem is transformed into a well-known assignment problem. The maximum fault tolerance is found, and a fast replacement algorithm is given. The reconfiguration capability can also be used to ameliorate imbalanced traffic flows. The authors formulate this traffic flow assignment problem for the switch fabric and show that the problem is NP-hard. A simple heuristic algorithm is proposed, and an example is given.>

The architecture and performance of fixed-node virtual channel (VC) routing in asynchronous transfer mode (ATM) networks is studied. In fixed-node routing, only the nodes are specified, and any of the available parallel links between nodes may be used. Applying the fixed-node routing architecture in ATM networks has the advantages of more efficient use of network resources, better availability/reliability and performance, and the ability to support superrate services. The sequencing problem associated with this approach in conventional packet-switched networks can be easily solved in the ATM environment. An analysis is presented of the performance of this routing architecture for an internally nonblocking ATM switch with partially shared output buffers based on a discrete-time D/sup (A)//D/c/B queuing system for general input traffic. A D/sub 1/+ . . . +D/sub N//D/c/B queuing system is used for deterministic traffic. It is shown that the fixed-node routing architecture yields better performance in terms of delay, loss probability, channel utilization, and switch throughput than its fixed-path counterpart.>

The discrete-time D[A]/D/c/B queueing system is studied. We consider both a bulk arrival process with constant bulk inter-arrival time (D) and general bulk-size distribution (A) and a periodic arrival process (D1 + ··· + DN). The service/transmission times are deterministic (D) and the system provides for a maximum of c servers with a buffer size B. The motivation for studying this queueing system is its application in performance modeling and analysis of an asynchronous transfer mode (ATM) switch with multichannel transmission groups.

The authors obtain the optimum transmission ranges to maximize throughput for a direct-sequence spread-spectrum multihop packet radio network. In the analysis, they model the network self-interference as a random variable which is equal to the sum of the interference power of all other terminals plus background noise. The model is applicable to other spread-spectrum schemes where the interference of one user appears as a noise source with constant power spectral density to the other users. The network terminals are modeled as a random Poisson field of interference power emitters. The statistics of the interference power at a receiving terminal are obtained and shown to be the stable distributions of a parameter that is dependent on the propagation power loss law. The optimum transmission range in such a network is of the form CK/sup alpha / where C is a constant, K is a function of the processing gain, the background noise power spectral density, and the degree of error-correction coding used, and alpha is related to the power loss law. The results obtained can be used in heuristics to determine optimum routing strategies in multihop networks.>

The authors present two adaptive techniques, involving route selection and channel access, which significantly improve the throughput and delay performance of a multihop, receiver-directed CDMA (code-division multiple-access) packet radio network. Routing is accomplished by choosing among potential next nodes in a distribution fashion, based on the simple metric of queue length. De facto preference is given to congested nodes by the channel access protocol, based on queue length ratios, in order to increase their (outbound) throughput without increasing the number of channel collisions. These algorithms have the effect of spreading network traffic more evenly across the network, thereby alleviating the congestion at bottleneck nodes, so that network throughput approaches that analytically predicted using a homogeneity assumption. Simulation results are presented which quantify the achieved improvement for networks with varying connectivity fractions.>

Some data-link layer error control go-back-N ARQ (automatic repeat-request) protocols are studied that are suitable for point-to-multipoint communication over broadcast channels where data are delivered to the destinations in the order they are sent. A series of protocols differing in the way that the sender uses the outcomes of the previous transmissions are studied. The system delay, rather than the throughput, is the optimization measure. The optimal number of copies that the sender should transmit to minimize the time between when the sender first transmits a data frame and when the data frame is accepted by all the receivers is determined. The results show that sending the optimum number of copies of a data frame instead of just a single copy significantly improved the delay performance.>

Unlike data traffic, the voice packet stream from a node has very high correlation between consecutive packets. In addition, in order for the speech to be properly reconstructed, a delay constraint must be satisfied. A queueing model that accurately predicts packet loss probabilities for such a system is presented. Analytical results are obtained from an embedded bivariate Markov chain and are validated by a simulation program. Based on this model, the impact of the delay constraint, talkspurt detection thresholds, and packet size on packet loss are studied. Two schemes, named 'instant' and 'random', for discarding late packets are considered. Simulation results show that better performance can be obtained by using the latter scheme.>

The problem of routing virtual circuits according to dynamical probabilities in virtual-circuit packet-switched networks is considered. Queueing network models are introduced and performance measures are defined. A decentralized asynchronous adaptive routing methodology based on learning automata theory is presented. Every node in the network has a stochastic learning automaton as a router for every destination node. The routing probabilities that are assigned to the network paths are updated asynchronously on the basis of current network conditions. A learning algorithm suitable for routing is used. Some initial simulation experiments, for a simple network, show convergence to optimal routing.>

A study is made of some data-link-layer error-control protocols suitable for point-to-multipoint communication over broadcast channels where data are delivered to the destinations in the order they are sent. The authors study a series of protocols differing in the way that the sender uses the outcomes of the previous transmissions. The protocols are based on the go-back-N schemes discussed by I.S. Gopal and J.M. Jaffe (1984). The authors generalize their proposed protocols to the case where multiple copies of a message are sent (instead of just a single copy). The optimum number of copies is determined, which depends not only on the round-trip propagation delay of the channel and the error probability, but also on the number of receivers that have not yet received the message. A dynamic programming technique is used to solve this optimization problem. The throughput comparison shows that by sending the optimum number of copies of a data frame instead of just a single copy, the performance will be significantly improved.>

Spreading code protocols for a distributed spread-spectrum packet radio network are presented. A distributed single-hop system (i.e. each terminal can hear all other terminals) with the users approximately synchronized and a set of prespecified spreading codes are presented. The spreading code protocol is a policy for choosing a spreading code to be used, given that a terminal has a packet to send, and a policy for monitoring spreading codes, given that a terminal is idle. A slotted system where a packet occupies a number of slots is considered, and two protocols that involve changing the spreading code of a transmission after an initial header is transmitted are presented. In one protocol, the header is transmitted on a common code, and in the other it is transmitted on a receiver-based code, the rest of the packet being transmitted on a transmitter-based code. In the receiving mode, a terminal monitors either a common code, in the first case, or a receiver-based code in the latter. Upon recognizing its own address and the source address, the receiver dynamically switches to a despreading code corresponding to the source. Throughput results are obtained for the case of geometrically distributed packet lengths.>

An analytic framework is proposed for the study of singlehop spread-spectrum networks using random access and packet switching under various network topologies and channel conditions. The key feature of the theory is the identification of a set of probabilistic parameters, which, based on a symmetry argument, serve to efficiently summarize the effect on performance of various network considerations such as transmitter-receiver configuration, spreadspectrum code allocation, error correction and detection mechanisms, spreading format, jamming conditions, etc. Examples investigating capture effects, coding tradeoffs, and scheduling optimizations are presented. Various previously known results are shown to be special cases of the framework that we describe.

Multihop packet radio networks present many challenging problems to the network analyst and designer. The communication channel, which must be shared by all of the network users, is the critical system resource. In order to make efficient use of this shared resource, a variety of channel access protocols to promote organized sharing have been investigated. Sharing can occur in three domains: frequency, time, and space. This paper is mostly concerned with sharing and channel reuse in the spatial domain. A survey of results on approaches to topological design and associated channel access protocols that attempt to optimize system performance by spatial reuse of the communication channel is presented.

Single loop networks tend to become unreliable and suffer from poor performance when the number of nodes in the network becomes large. One approach to increasing reliability and improving performance is to use a double loop. In this paper, the performance (using analytical and simulation models) of a class of highly reliable double loop network architectures is presented. The richer topology of double loop networks allows more sophisticated routing algorithms to be used. Several routing algorithms are studied, including: fixed, adaptive to failure, and fully adaptive to failure and traffic load conditions.

In evaluating the performance of a communication network with unreliable components, researchers have traditionally approached the problem by enumerating all possible states of the system. Since the number of states of a communication network withnfailure-prone components is 2nthese methods are restricted to small systems. We present a new solution technique that is not doomed by the "statespace explosion" problem. Instead of enumerating all possible fail states, we consider only the most probable states. Since the network operates in these states most of the time, we can get upper and lower bounds and, hence, a good approximation of the network performance without having to analyze all possible states. We illustrate our solution technique by analyzing network reliability, the expected number of communicating pairs, and network average delay for some particular networks.

In this paper we investigate the capacity of networks with a regular structure operating under the slotted ALOHA access protocol. We first consider circular (loop) and linear (bus) networks and then proceed to two-dimensional networks. For one-dimensional networks we find that the capacity is basically independent of the network average degree and is almost constant with respect to network size. For two-dimensional networks we find that the capacity grows in proportion to the square root of the number of nodes in the network provided that the average degree is kept small. Furthermore, we find that reducing the average degree (with certain connectivity restrictions) allows a higher throughput to be achieved. We also investigate some of the peculiarities of routing in these networks.

In this paper we formulate a general model of the capacity of single-hop slotted ALOHA networks. We find that the capacity can be expressed as a function of the nodal degree (i.e., number of nodes within range of a transmitter). We than evaluate this model for various traffic matrices. In order to satisfy the requirements of a given traffic matrix, the transmission power is selected accordingly and this determines the degree of the nodes and, hence, the network performance. Finally we compare our results to simulation studies.