The LOOFA algorithm is a cell-based scheduler for CIOQ crossbar switches that can guarantee the work-conserving property in a cell-based switch if the crossbar switch works twice as fast as the line rate (speedup of two). Unfortunately, the cell based LOOFA algorithm is not work-conserving for variable- length packet switches because it interleaves the cells from different inputs to a particular output and does not necessarily serve cells belonging to a packet contiguously. Thus, the cells belonging to a variable- length packet must be reassembled at the output port before the packet can be transmitted. This requires a large buffer at the output stage, and causes extra delays. PLF, which is another suggested scheduling algorithm for variable-length packet switches, has its own limitations. PLF must use a considerable amount of memory at every crosspoint of the buffered crossbar, making the overall complexity high. In this paper we examine the work conserving property of the LOOFA and the PLF algorithms in variable-length packet switches and propose a packet-based version of the LOOFA (called the LOOFA-PB) for variable-length packets. The proposed algorithm is a (Lmax/2)-work- conserving algorithm and does not need a buffered crossbar or a speedup greater than two. In addition, the LOOFA-PB algorithm eliminates the need for reassembly and serves packets contiguously. As a result, it reduces the overall packet delay. Finally, eliminating the SAR functionality from the algorithm results in a smaller die size when implemented in an ASIC, and cheaper cost.

In a state of emergency, in complex and dynamic situations where packet delay increases and congestion builds up, certain network nodes may not to able to handle the traffic load. To avoid the congestion build-up in advance, it is mission critical to predict the symptoms of network traffic and to preemptively alter the routing paths to allow a smooth and efficient flow of data packets for effective situation management. In this paper, we have developed a practical methodology for estimation of key parameters of self-similar network traffic using index of dispersion for counts and coefficient of determination. Self-similarity causes performance degradation in the queueing delay and buffer overflow at routers and at switches. We proved the impact of Hurst parameter and fractal onset time on the average queueing delay and the waiting-time distribution of self-similar traffic, utilizing experimental queueing analysis. Based on the understanding obtained, we can predict the congestion of data network in advance through estimation of traffic parameters. In addition, the results of this study on the delay provide a practical means of finding a lower delay path in data networks under the self-similarity

In recent years, many fair packet scheduling algorithms have been proposed for switches and routers to provide the quality of service (QoS) guarantees required by many applications. In addition to the fairness and low end-to-end delay that these algorithms have to have, simplicity and scalability are two significant factors that play an important role. In this paper, we present proportional nested deficit round robin with credit adjusting (PNDRR-CA), which is a modified version of PNDRR. PNDRR-CA has a low latency and reduces burstiness. PNDRR-CA takes advantage of the input traffic pattern and decreases the serving size of flows when the input traffic contains many small packets. This helps to interleave packets in many practical scenarios, such as the Internet, where the majority of packets are relatively small. The latency and fairness of PNDRR-CA are studied and compared to other algorithms using simulation

Summary form only given. To control data network for a delay constraint application, it is necessary to understand the behavior of packet delay and the network traffic. In data network, the type of service (TOS) bits are included in the IP header to allow a router to construct various shortest path first (SPF) trees on various quality of service (QoS) needs (e.g., minimum delay). The average queueing delay is a major contributor to the packet delay due to the fact that the queueing delay increases rapidly as the utilization of a router increases. A number of studies of traffic measurements have established the presence of self-similarity that causes performance degradation including amplified queueing delay. A cost function is proposed to determine a metric in a routing table through the prediction of the average queueing delay. From this, the end-to-end packet delays in a simple data network are analyzed by applying prediction-based routing through a cost function using least cost delay constraint. By comparing the average packet delay of TOS 0 (default) routing with that of prediction-based TOS 16 (minimize delay) routing, we can demonstrate the performance improvement on the average packet delay with the presence of self-similar traffic.

Recent studies on a wide range of network traffic measurements including LAN and WAN have revealed the presence of self-similarity. These types of traffic hold statistical similarity across multiple time scales. Burstiness is retained even with the aggregating self-similar traffic. This property degrades the performance of a network. The queueing delay is one of the performance measures. In this study, a G/M/1 queueing model is used to model a network with self-similar traffic. The results of this study demonstrate that the delay exhibits a rise as degree of self-similarity increases. We compare an analytic average queueing delay of the self-similar traffic to the delay of simulated model to obtain a useful method for the delay prediction. By adjusting a single parameter of the truncated power-tail (TPT) distributions, we can make the analytic curve follow the simulation results. This allows us to predict the delay by computing the TPT once we measure the Hurst parameter of an input traffic and its arrival rate, and the utilization of a router. Our results can benefit control, design, and resource allocation of high-speed networks.

We present an approach which addresses a fundamental scaling limitation for conventional switches. Instead of processing the data packets one by one, train queue processing groups multiple data packets together and processes them as one unit. There are two basic train queuing techniques, sequential train queuing and sequential-to-parallel train queuing. The sequential train queue processing can reduce the global switch processing frequency for the switch. The sequential-to-parallel train queue processing can reduce both the global switch processing frequency and data rate by using packet grouping and slicing mechanism. By employing train queuing techniques, a high bandwidth switch can be built and feasibly implemented.

Prefix matching is an essential part of some applications. A well known application of prefix matching is layers 3 and 4 switching in TCP/IP protocols. It is assumed that there are strings of an alphabet /spl Sigma/ which are ordered. The strings may have different lengths and some may be prefixes of others. We introduce a simple scheme for comparing and sorting strings of different lengths first. Then, data is manipulated and the well-known tree structures are tuned to handle the prefix matching queries. A string prefix represents a data space that includes all strings for which it is a prefix. Using this concept, first, we propose a binary prefix tree and extended it to two m-way tree structures, static m-way prefix tree and dynamic m-way prefix tree later. The m-way trees have better search performance at the expense of some memory space. The static m-way prefix is more suitable for an environment with few data transactions and is expected to give better memory usage and create a more compact tree structure. The dynamic m-way prefix tree is a superset of B tree and is suited better for an environment with large transactions. All data structures share a common property: no data string can be at a higher level than its prefix in the data set. The proposed data structures are simple, well defined, easy to implement in hardware or software and efficient in terms of memory usage and search time.

We analyze the performance of multiple rejects (MR) ARQ for RLC (radio link control) proposed by 3GPP. The main purpose of MR ARQ is to get efficient use of radio resources at receiver by reducing number of acknowledgements. We analyze MR ARQ and compare its performance with selective repeat (SR) ARQ in the wireless fading channel environment. Based on mathematical analysis and simulation, it is shown that we need to increase the size of buffer for MR ARQ to hold data packets for the period of acknowledgement, and need to increase the size of buffer much more for MR ARQ in the noisier channel environment. It is shown that as the length of period for acknowledgement is increased, we need to increase the size of buffer much more for the saturated throughput. Increasing the size of buffer is needed for the efficient use of radio resources by reducing the number of acknowledgements. Also, the increased delay is another tradeoff.

We analyze the performance of multiple rejects (MR) ARQ for RLC proposed by the 3GPP. The main purpose of MR ARQ is to get efficient use of radio resources at the receiver by reducing number of acknowledgements. We analyze MR ARQ and compare its performance with selective repeat (SR) ARQ in the wireless fading channel environment. Based on analysis, it is shown that we need to increase the size of buffer for MR ARQ to hold data packets for the period of acknowledgement, and need to increase the size of buffer much more for MR ARQ in the noisier channel environment. It is shown that as the length of period for acknowledgement is increased, we need to increase the size of buffer much more for the saturated throughput. Increasing the size of buffer is needed for the efficient use of radio resources to reduce number of acknowledgements.

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.

We analyze the performance of multiple rejects (MR) ARQ for RLC proposed by 3GPP. The main purpose of MR ARQ is to get efficient use of radio resources at receiver by reducing number of acknowledgements. We analyze MR ARQ and compare its performance with selective repeat (SR) ARQ in the wireless fading channel environment. Based on analysis, it is shown that we need to increase the size of buffer for MR ARQ to hold data packets for the period of acknowledgement, and need to increase the size of buffer much more for MR ARQ in the noisier channel environment. It is shown that as the length of period for acknowledgement is increased, we need to increase the size of buffer much more for the saturated throughput. Increasing the size of buffer is needed for the efficient use of radio resources to reduce number of acknowledgements.

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 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.

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.>

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.>