In this paper, we investigate the performance of a multi-cell CDMA network by determining the maximum throughput that the network can achieve for a given grade-of-service requirement, quality-of-service requirement, network topology and call arrival rate profile. Our analysis is restricted to the reverse link and accounts for mobility of users between cells. A constrained nonlinear optimization problem is formulated that maximizes the network throughput subject to upper bounds on the blocking probabilities and a lower bound on the bit energy to interference ratio. The goal is to optimize the usage of network resources, provide consistent grade-of-service for all the cells in the network, and maintain a pre-specified quality-of-service. The solution to the optimization problem yields the maximum network throughput as well as the maximum number of calls that should be admitted in each cell for a given topology and call arrival rate profile. Our optimization algorithm yields significantly higher throughput compared with traditional call admission schemes.

Designing a call admission control (CAC) algorithm that guarantees call blocking probabilities for arbitrary traffic distribution in CDMA networks is difficult. Previous approaches have assumed a uniform traffic distribution or excluded mobility to simplify the design complexity. We define a set of feasible call configurations that results in a CAC algorithm that captures the effect of having an arbitrary traffic distribution and whose complexity scales linearly with the number of cells. To study the effect of mobility and to differentiate between the effects of blocking new calls and blocking handoff calls, we define a net revenue function. The net revenue is the sum of the revenue generated by accepting a new call and the cost of a forced termination due to a handoff failure. The net revenue depends implicitly on the CAC algorithm. We calculate the implied costs which are the derivatives of the implicitly defined net revenue function and capture the effect of increases in the number of calls admitted in one cell on the revenue of the entire network. Given a network topology with established traffic levels, the implied costs are used in the calculation of a CAC algorithm that enhances revenue and equalizes call blocking probabilities. Moreover, our algorithm provides guaranteed grade-of-service for all the cells in the network for an arbitrary traffic distribution.

The effect of call arrival rate on the capacity of a code-division multiple-access (CDMA) cellular network is evaluated. First the inter-cell and intra-cell interferences of every cell on every other cell are calculated for a given network topology. Then the capacity region for the number of simultaneous calls in every cell is defined for specified system parameters. This region is used to evaluate the new call blocking and handoff call blocking probabilities. The network throughput is found by considering the revenue generated by accepting a new call and the cost of a forced termination due to handoff failure. Implied costs are calculated for both high and low mobility of calls between cells, and the effect of mobility on pricing is discussed. Implied costs are used to maximize the throughput with respect to the call arrival rates by applying a gradient descent algorithm.

In order to meet the ATM Forum recommendations, rates must be guaranteed to each individual ATM connections across a high-speed switch fabric in the face of thousands of individual connections, burstiness of traffic in individual connections, a wide diversity of rates, differing expectations of rates for different traffic classes, and the arrival and departure of hundreds of connections per second. In addition, the situation is compounded by the presence of multicast traffic which has rate guarantees. We describe an architecture and Implementation for an ATM switching system which address the above requirements. Our approach uses a novel two-level scheduling algorithm: a higher level scheduling algorithm for aggregated cell units called frames and a distribution scheme for cells within a frame. This approach has significant advantages in terms of implementation complexity. It is particularly effective in treating traffic with differing QoS requirements differently in the process of flow control across the switching fabric. It enables the fulfilment of arbitrary rate guarantees to individual connections in an easily controllable way. It makes the scheduling of multicast particularly efficient and easy. We describe all these advantages and present numerical results supporting our claims. Implementational features of the architecture are discussed to demonstrate the feasibility of such a design.

Traditional design rules, wherein cells are dimensioned in order to get an equal amount of demand in each cell are not directly applicable to CDMA networks where large cells can cause a lot of interference to adjacent small cells. In order to enable iterative cell placement we use a computationally efficient iterative process to calculate the inter-cell and intra-cell interferences as a function of pilot-signal power and base station location. These techniques enable us to improve the placement of cells in a CDMA network so as to enhance network capacity. We show examples of how networks using this design technique will provide higher capacity than ones designed using conventional techniques.

We evaluate the effects of mobility and reservations on new call blocking and handoff blocking in multirate wireless networks. The model evaluated uses fixed channel assignment (FCA) with priority for handoffs over new call arrivals by reserving a number of channels for handoff calls in all the cells. The performance measures used are new call blocking and handoff drop probabilities. The methodology used is that of implied costs which we calculate from the the network net revenue which considers the revenue generated by accepting a new call into the network as well as the cost of a handoff drop in any cell. Simulation and numerical results are presented showing the accuracy of the model. We present numerical results showing the effect of reservations on the call blocking probability. The implied cost analysis shows that mobility has a significant knock-on effect on the traffic elsewhere in the network and we capture this effect through the net revenue which is sensitive to the level of mobility. We calculate the sum revenue for a given network by maximizing the net revenue using implied costs in a gradient descent algorithm. This analysis indicates that in the case of multiple classes of traffic the call carrying capacity of the network is sensitive to the choice of reservation parameters.

A new MAC protocol which supports peer-to-peer direct communication is introduced for a packet switched wireless network. Terminals that are located within range of each other and are sufficiently isolated from the base station can communicate with their peers directly without the use of the base station as a relay. Slotted Aloha is used as the access protocol. Throughput and delay of the protocol are evaluated. Numerical results are presented which show that significant improvements in throughput/delay performance can be obtained over a system using slotted Aloha without peer-to-peer communication.

We propose the multi-channel deflection crossbar (MCDC) as a promising architecture for broadband ATM switching under the realistic constraints imposed by VLSI technology. MCDC is an internally nonblocking, buffer efficient, crossbar based architecture. MCDC is also capable of multi-channel switching with cell sequence integrity preserved. Through a comparative study against a well-known ATM switch architecture, we show that the proposed MCDC architecture is able to incorporate a greater number of input channels and buffers for a given IC die size and requires a lower clocking rate.

Shadow prices are calculated for least loaded routing (LLR) and aggregated least busy alternative (ALBA) routing in circuit-switched networks for the blocking probability obtained from fixed point algorithms. Numerical results are presented for the calculation of these shadow prices in small networks. As an application of these shadow prices, we also formulate a constrained optimization problem to calculate the sum capacity of LLR and ALBA for a given network. Comparison of the sum capacities indicate that the optimization using shadow prices results in a significant improvement. This provides evidence that matching capacity distribution to traffic is important even when adaptive routing schemes such as LLR and ALBA are used in the network. We also calculate upper bounds on the sum capacity which serve to indicate how well the optimized LLR and ALBA perform. The numerical results also confirm that with a small number of states the capacity of ALBA approaches that of LLR.

We introduce a novel multicast switching paradigm, the deflecting multicast switch (DMS), which accomplishes the replication and routing functions of a multicast switch simultaneously. The architecture is shown to have low connection complexity and can be implemented in a modular fashion. A self-routing and self-replication algorithm with minimal control overhead is described which allows for distributed control of these functions. A key requirement of ATM, namely the maintenance of cell sequence in a session, is easily ensured. Analytical results are presented for the calculation of the cell loss probability, the number of stages to guarantee an upper bound on the cell loss probability and the buffer delays. For the case of uniform traffic patterns, numerical results are presented which exhibit the number of stages required for a fixed cell loss probability as well as the buffer delays.

The intensity of exogenous traffic is a critical input to a variety of network functions, including routing, flow control, and capacity planning. Currently, however, the scope of measurements in a large scale, circuit-switched network is quite limited and does not include gathering of the exogenous traffic intensity in real-time. This paper formulates methods of estimating the exogenous traffic intensity, without requiring additional measurements beyond what is currently available. The performance of the proposed methods is compared based on network simulations and is shown to be accurate and robust.>

This paper develops a copy network architecture that can maintain the cell sequence integrity in multi-channel ATM switching. The architecture is internally nonblocking in the sense that the copying process of cells is constrained only by the availability of output channels. By using a relative ordering among the inputs, shared buffering, and a new switching paradigm called the nonblocking binary group network, we show how the cell sequence integrity can be maintained. Next, assuming the fanout request values of cells are distributed independently from cell to cell, we formulate a method of analyzing the performance of the copy network. This method uses the technique of tagged Markov chains to derive the stationary distributions for the number of cells in the copy network from which, delay, throughput, and cell loss probability can be accurately calculated as critical performance measures. We conduct a numerical study for the proposed architecture using this method wherein the effects of key network and traffic variables such as buffer and network sizes, and the mean and the variance of fanout request values are determined under arbitrary types of fanout distribution. Finally, we quantify the performance improvement due to fanout splitting which allows the fanout request from a single cell to be satisfied over multiple time slots.

The paper investigates multichannel switching as a promising alternative to traditional single-channel switching where virtual paths established in a switch are between a single input channel and a single output channel. A particular non-blocking condition is derived for flip networks, which is exploited to realize a multichannel switching architecture that supports an arbitrary number of channel groups. The architecture is internally nonblocking and bufferless. Using one flip network recursively a number of times based on the number of channel groups, the resulting architecture becomes efficient in the sense that the cross point complexity is O(N log/sub 2/ N) for N inputs. Other distinguishing features are the abilities to provide multicasting, superrate switching (i.e., rates that exceed the capacity of a single channel are accommodated), multirate switching (i.e., bit pipes of different rates are supported simultaneously), multiple performance requirements (i.e., services with different performance requirements are treated accordingly), and fair access to all inputs (i.e., no input is systematically discriminated against). In multichannel switching, cells belonging to a single session can traverse multiple channels. Providing the cell sequencing integrity becomes a challenging issue. The architecture proposed in the paper accomplishes the task without employing any cell resequencing mechanism.>

The paper presents a method of controlling the pattern of packet flow in the statistical data fork (SDF), such that the output channels are assigned to a channel group based only on their addresses and this assignment is maintained independently of the offered load to the SDF. The proposed method is realized by using a structural property of the SDF which is derived in the paper. It is shown that a sufficient condition for this property to hold is for the probabilities of packets destined for different channel groups to be certain permutations of each other. It is shown, using this property, that the flow of packets in the SDF can be governed by a two phase process wherein in the first phase, packets are routed in different subnetworks to result in the probability patterns that match the requirement of the structural property, and in the second phase, these packets are delivered to the channel groups which are partitioned only according to their addresses.>

The paper investigates multi-channel switching as a promising alternative to traditional single-channel switching where virtual paths established in a switch are between a single input channel and a single output channel. Building on a particular nonblocking condition for the flip networks, a multi-channel switching architecture that supports an arbitrary number of channel groups is formulated. In multi-channel switching, cells belonging to a single session can traverse multiple channels. The architecture proposed in the paper provides the time ordering integrity among those cells without employing any resequencing mechanism.>

Introduces a new measure of conditional connectivity for large regular graphs by requiring each vertex to have at least g good neighbors in the graph. Based on this requirement, the vertex connectivity for the n-dimensional cube is obtained, and the minimal sets of faulty nodes that disconnect the cube are characterized.>

We propose new decoders for decoding convolutional codes over finite-state channels. These decoders are sequential and utilize the information about the channel state sequence contained in the channel output sequence. The performance of these decoders is evaluated by simulation and compared to the performance of memoryless decoders with and without interleaving. Our results show that the performance of these decoders is good whenever the channel statistics are such that the joint estimate of the channel state sequence and the channel input sequence is good, as, for example, when the channel is bursty. In these cases using even a partial search decoder such as the Fano decoder over the appropriate trellis is nearly optimal. However, when the information between the output sequence and the sequence of channel states and inputs diminishes, the memoryless decoder with interleaving outperforms even the optimal decoder which knows the channel state.

Fixed (nonadaptive) and forward adaptive differential pulse code modulation of regenerative composite sources is investigated. In the fixed code, an approximate formula is given for the optimal value of the prediction coefficient. This is then used as an initial guess to optimize the code (predictor and quantizer) through a numerical method. In the forward adaptive scheme, the state of the switch in the composite source is estimated using a MAP sequence estimation algorithm, and the code is then matched to the mode process corresponding to the estimated switch state. The performance of the two systems is evaluated with quantizers of 4, 8, and 16 levels. The results show that the forward adaptive scheme significantly outperforms optimized fixed DPCM in the sense of mean-squared error. Stochastic stability of the code is also established for the fixed DPCM scheme as well as for an adaptive scheme which receives the switch state as side information.>

The effects of redundancy and masking on the reliability of synchronizer circuits in the presence of metastability are considered. It is shown that in the jitter model developed by L. Kleeman (1990), in which circuit noise effects are considered, redundancy improves the probability of metastable failure of synchronizers, contrary to Kleeman's claim. A stochastic model that relates the noise model to the absorbing barrier problem for such noise effects is presented. It is demonstrated analytically that under considerably general conditions on the (masking) (Bcombinational circuit, clock delay, voter delay, and aperture alignment and width, the probability of metastable failure of the redundant synchronizer tends to zero with L, the number of component synchronizers. If the component synchronizers are identical, this probability of metastable failure decreases monotonically with L. Furthermore, the best combinational circuits to use in the general redundant synchronizer are the L-input AND and OR functions. Conditions are derived under which the majority voter function may or may not be effective in a general redundant synchronizer.>

An analytical model of the telecommunications network is formulated, representing the entire network as a single entity. The resulting model contains a realistic (i.e. not overly simplified) view of the network, and hence can be used to develop the optimal evolution strategy for the Bell Operating Companies (BOC's) network. The process of developing the optimal evolution strategy is referred to as the strategic planning process. Background associated with the strategic planning process of a telecommunications network is given. Attempts are made to illustrate some basic underlying assumptions in the telephony. The problem to be solved and nomenclature are defined. Models for the fundamental elements of the network, i.e. links and nodes, are defined. The optimization problem that includes all aspects of the network, i.e. end-to-end connectivity, is formulated.>

A simple, exact calculation is presented of the probability distribution of the number of hits in a block of n symbols in a frequency-hopped, spread-spectrum, multiple-access communication system. While the sequence of hits is not Markovian, there is an underlying Markovian structure that allows the probability distribution of the number of hits to be calculated in a recursive fashion. Knowing the probability distribution of the number of hits makes it possible to calculate the probability of error for a system employing error correcting codes for several different types of receivers, including receivers with both errors and erasures. The numerical results show that both the approximation obtained by assuming the actual sequence of hits is Markovian and the approximation obtained by assuming the hits are independent are very good. When the number of frequency slots is not too small (less than five), calculations show that assuming the independence of hits gives an error probability accurate to within 1% of the actual error probability. Assuming the hits are Markovian gives error probabilities which are accurate to within 0.001%.>

The information theoretic capacity is considered. In order to account for independent encoding and decoding and private (to the sender and receiver) hopping patterns, an interference channel model is adopted with K sender-receiver pairs with the ith receiver only interested in the message transmitted by the ith sender. Both synchronous and asynchronous hopping patterns are investigated. Although the channel exhibits memory in the latter case, it is possible to compute the capacity region. The asymptotic normalized sum capacity is also computed.>

The process of communicating in the presence of interference that is unknown or hostile is modeled as a two-person zero-sum game with the communicator and the jammer as the players. The objective function considered is the rate of reliable communication. The communicator's strategies are encoders and distributions on a set of quantizers. The jammer's strategies are distributions on the noise power subject to certain constraints. Various conditions are considered on the jammer's strategy set and on the communicator's knowledge. For the case where the decoder is uninformed of the actual quantizer chosen, it is shown that, from the communicator's perspective, the worst-case jamming strategy is a distribution concentrated on a finite number of points, thereby converting a functional optimization problem into a nonlinear programming problem. Moreover, the worst-case distributions can be characterized by means of necessary and sufficient conditions which are easy to verify. For the case where the decoder is informed of the actual quantizer chosen, the existence of saddle-point strategies is demonstrated. The analysis is also seen to be valid for a number of situations where the jammer is adaptive.>

It is shown that for worst-case partial-band jamming, the error probability performance (for fixed E/sub b//N/sub I/) becomes worse with increasing M for (M>16). The asymptotic probability-of-error is not zero for any E/sub b//N/sub I/(>ln 2), but decreases inverse linearly with respect to it. In the fading case, the error-probability performance (for fixed E/sub b//N/sub 0/) improves with M for noncoherent detection, but worsens with M for coherent detection. For large E/sub b//N/sub 0/ the performance of the Rayleigh fading channel asymptotically approaches the same limit as the worst case partial-band jammed channel. However, for values of M at least up to 4096, the partial-band jammed channel does better. While it is unlikely that an M-ary orthogonal signal set with M>1024 will be used in a practical situation, these results suggest an important theoretical problem; namely, what signal set achieves reliable communication.>