Nonuniform traffic analysis on a nonblocking space-division packetswitch

The nonuniform traffic performance on a nonblocking space division packet switch is studied. When an output link is simultaneously contended by multiple input packets, only one can succeed, and the rest will be buffered in the queues associated with each input link. given the condition that the traffic on each output is not dominated by individual inputs, this study indicates that the output contention involved by packets at the head of input queues can be viewed as an independent phase-type process for a sufficiently large size of the switch. Therefore, each input queue can be modeled by an independent Geom/PH/1 queueing process. Once the relative input traffic intensities and their output address assignment functions are defined, a general formulation can be developed for the maximum throughput of the switch in saturation. The result indicates under what condition the input queue will saturate. A general solution technique for the evaluation of the queue length distribution is proposed. The numerical study based on this analysis agrees well with simulation results     

分组交换中分组流的概率特性与输出排队

本文分析快速分组交换中分组流的概率特性与输出排队。在输入分组流为复合泊松流的假设之下，论证了复合泊松流在分组交换过程中的叠加性、分解性、泊松性、马尔柯夫性、输出与输入的不变性等。然后，将输出分组流转换为连续时间的马尔柯夫链，分析了输出分组流的概率特性，并得到了输出排队长分布和充满缓冲器的概率。     

Performance analysis of a random packet selection policy formulticast switching

This paper studies a random packet selection policy for multicast switching. An input packet generates a fixed number of primary copies plus a random number of secondary copies. Assuming a constant number of contending packets during a slot, the system is modeled as a discrete time birth process. A difference equation describing the dynamics of this process is derived, the solution of which gives a closed form expression for the distribution of the number of packets chosen. Then this result is extended to the steady state distribution through a Markov chain analysis. It is shown that the old packets have larger fanout than the fresh packets and the copy distribution of the mixed packets is determined. The packet and copy throughput taking into account the old packets have been obtained. We determined the mean packet delay as well as an upperbound for packet loss probabilities for finite buffer sizes. The asymptotic distribution of the number of packets is also given for large switch sizes under saturation by applying results from the renewal theory. Finally, simulations are done to determine the performance of the switch under mixed (unicast plus multicast) traffic     

有优先级的输出排队快速分组交换机性能研究

输出排队结构是快速分组交换中交换性能最佳的交换结构。本文研究输出排队结构交换任意种优先级业务的排队性能。分别在独立和相关到达两种情况下导出了任意优先级业务的平均排队长度等特征参数,发现当N×N规模互连网络的端口数N足够大时,两种业务到达模型的排队性能趋于一致。文中提出了一种数值迭代法来求取用二维Markov过程表示的高、低优先级分组队列长度的稳态解。计算机模拟结果证实了文中的分析。     

Performance evaluation of multiple input-queued ATM switches withPIM scheduling under bursty traffic

In this letter, we analyze the performance of multiple input-queued asynchronous transfer mode (ATM) switches that use parallel iterative matching (PIM) for scheduling the transmission of head-of-line cells in the input queues. A queueing model of the switch is developed under independently, identically distributed, two-state Markov modulated Bernoulli processes bursty traffic. The underlying Markov chain of the queueing model is a quasi-birth-death (QBD) chain. The QBD chain is solved using an iterative computing method. Interesting performance metrics of the ATM switch such as the throughput, the mean cell delay, and the cell loss probability can be derived from the model. Numerical results from both the analytical model and simulation are presented, and the accuracy of the analysis is briefly discussed     

Performance analysis of the ATM shuffleout switch under arbitrarynonuniform traffic patterns

Shuffleout is a blocking multistage asynchronous transfer mode (ATM) switch using shortest path routing with deflection, in which output queues are connected to all the stages. This paper describes a model for the performance evaluation of the shuffleout switch under arbitrary nonuniform traffic patterns. The analytical model that has been developed computes the load distribution on each interstage link by properly taking into account the switch inlet on which the packet has been received and the switch outlet the packet is addressing. Such a model allows the computation not only of the average load per stage but also its distribution over the different links belonging to the interstage pattern for each switch input/output pair. Different classes of nonuniform traffic patterns have been identified and for each of them the traffic performance of the switch is evaluated by thus emphasizing the evaluation of the network unfairness     

An EM Algorithm for Markov Modulated Markov Processes

An expectation–maximization (EM) algorithm for estimating the parameter of a Markov modulated Markov process in the maximum likelihood sense is developed. This is a doubly stochastic random process with an underlying continuous-time finite-state homogeneous Markov chain. Conditioned on that chain, the observable process is a continuous-time finite-state nonhomogeneous Markov chain. The generator of the observable process at any given time is determined by the state of the underlying Markov chain at that time. The parameter of the process comprises the set of generators for the underlying and conditional Markov chains. The proposed approach generalizes an earlier approach by RydÉn for estimating the parameter of a Markov modulated Poisson process.      

一种基于Credit的变长分组并行交换网络调度算法

该文提出了一种新的并行分组交换(PPS)网络调度算法。该算法通过在解复用器处采用以变长分组为业务分配单元的方式消除了信元的乱序问题;通过采用Credit机制进行业务分配,实现了业务到各个交换平面完全公平的分配;各个并行交换单元采用组合输入输出排队,降低了对缓存和交换平面的加速要求,同时可以充分利用现有单Crossbar网络调度算法的研究成果。文中证明了该算法对业务分配的公平性,对高速缓存的需求量以及整个网络的稳定性,仿真进一步证明了该算法具有良好性能。     

The performance analysis and implementation of an input accessscheme in a high-speed packet switch

The performance analysis of an input access scheme in a high-speed packet switch for broadband ISDN is presented. In this switch, each input port maintains a separate queue for each of the outputs, thus n ² input queues in an (n×n) switch. Using synchronous operation, at most one packet per input and output will be transferred in any slot. We derive lower and upper bounds for the throughput which show close to optimal performance. The bounds are very tight and approach to unity for switch sizes on the order of a hundred under any traffic load, which is a significant result by itself. Then the mean packet delay is derived and its variance is bounded. A neural network implementation of this input access scheme is given. The energy function of the network, its optimized parameters and the connection matrix are determined. Simulation results of the neural network fall between the theoretical throughput bounds     

Analysis of a discrete-time queue with integrated bursty inputs in ATM networks

In this paper, we carry out an exact analysis of a discrete-time queue system with a number of independent Markov modulated inputs in ATM networks, using a generating function approach. We assume that the queueing system has an infinite buffer with M servers. The cell arrival process is characterized by a number of independent Markov modulated geometrical batch arrival processes. We first obtain the generating function of the queue-size distribution at steady-state in vector form, then derive an expression for the average queue-size in terms of the unknown boundary probabilities. To obtain those unknown probabilities, we use the technique proposed in Reference 1. This involves decomposing the system characteristic function to evaluate the roots and solving a set of linear equations. One of the contributions of this paper is presented in Lemma 1, which characterizes the property of the underlying eigenvalues. For one special case of at least M-1 cell arrivals during one slot at one Markov state and of at least M arrivals at all other states, the determination of the unknowns is straightforward. If every Markov modulated arrival process can be further decomposed into a number of i.i.d. two-state, or three-state, or even four-state Markov modulated arrival processes, then each root can be obtained separately using an iterative algorithm. Numerical results are presented to validate the proposed traffic models against actual traffic measurements.     

Throughput analysis, optimal buffer allocation, and trafficimbalance study of a generic nonblocking packet switch

A general model is presented to study the performance of a family of space-domain packet switches, implementing both input and output queuing and varying degrees of speedup. Based on this model, the impact of the speedup factor on the switch performance is analyzed. In particular, the maximum switch throughput, and the average system delay for any given degree of speedup are obtained. The results demonstrate that the switch can achieve 99% throughput with a modest speedup factor of four. Packet blocking probability for systems with finite buffers can also be derived from this model, and the impact of buffer allocation on blocking probability is investigated. Given a fixed buffer budget, this analysis obtains an optimal placement of buffers among input and output ports to minimize the blocking probability. The model is also extended to cover a nonhomogeneous system, where traffic intensity at each input varies and destination distribution is not uniform. Using this model, the effect of traffic imbalance on the maximum switch throughput is studied. It is seen that input imbalance has a more adverse effect on throughput than output imbalance     

Performance of a nonblocking space-division packet switch withcorrelated input traffic

This work studies the performance of a nonblocking space-division packet switch in a correlated input traffic environment. In constructing the input traffic model, the author considers that each input is a time division multiaccess (TDM) link connecting to multiple sources. Every source on a link supports one call at a time. Each call experiences the alternation of ON and OFF periods, and generates packets periodically while in ON period. The stochastic property of each call does not have to be identical. Packets from each individual call are destined to the same output. The output address of each call is assumed to be uniformly assigned at random. The author derives both upper and lower bounds of the maximum throughput at system saturation. His study indicates that, if the source access rate is substantially lower than the link transmission rate, the effect of input traffic correlation on the output contentions can generally be ignored. Also, the analysis of each input queue becomes separable from the rest of the switch. The same study is carried out with nonuniform call address assignment     

SCOQ: a fast packet switch with shared concentration and outputqueueing

A space-division, nonblocking packet switch with data concentration and output buffering is proposed. The performance of the switch is evaluated with respect to packet loss probability, the first and second moments of the equilibrium queue length and waiting time, throughput, and buffer overflow probability. Numerical results indicate that the switch exhibits very good delay-throughput performance over a wide range of input traffic. The switch compares favorably with some previously proposed switches in terms of fewer basic building elements used to attain the same degree of output buffering     

Bandwidth utilization efficiency enhancement for OFDM‐based WSN

Normally IEEE 802.16 (WiMAX) is used for mainly downlink traffic applications. However in the upper tier of 2‐tier (WiMAX‐WiFi) wireless sensor network, the uplink bandwidth faces bottlenecks for high throughput. In this paper, a solution has been proposed for this limitation of uplink bandwidth allocation through the use of queuing theoretic performance modeling. A Markov‐modulated Poisson process traffic model has been formed for orthogonal frequency division multiple access‐based transmission along with discrete time Markov chain system model for queuing. A downlink traffic pattern has been defined for wireless sensor network nodes. Analytical methods are used to estimate the performance parameters like throughput, delay, and probability of packet drop for resource allocation. An algorithm is formulated to find out minimum resource requirement for downlink and to transfer rest of the resources to uplink bandwidth allocation, for throughput enhancement. Uplink frame utilization is determined through another discrete time Markov chain model for adaptive triggering between the proposed maximum and the normal downlink to uplink ratio operations, for efficient distribution of bandwidth resources. Algorithm and simulation results prove outstanding improvement in the uplink throughput around 50%, without degrading the downlink throughput.     

Analysis of input and output queueing for nonblocking ATM switches

A switch model for ATM networks is analyzed. Its interconnection network is internally nonblocking and is provided with dedicated input and output queues, one per switch inlet and one per switch outlet. The switch operates with an internal speed-up: more than one packet per slot can be transferred from the head-of-line positions of the input queues to each output queue by the interconnection network. Two different operation modes are considered for the interaction between input and output queues: backpressure mode and queue loss mode. The analytical model developed for the evaluation of the switch performance under random traffic assumes an infinite size for the switch, arbitrary values for input and output queue size, as well as for the speed-up factor. Switch throughput, packet delay and loss performance are evaluated and the analytical model accuracy is assessed using computer simulation results     

Cognitive medium access control protocols for secondary users sharing a common channel with time division multiple access primary users

The unused time slots in a primary time division multiple access (TDMA) network are regarded as the potential channel access opportunities for secondary users (SUs) in cognitive radio (CR). In this paper, we investigate the medium access control protocols that enable SUs to access a common TDMA channel with primary users (PUs). The primary traffic is assumed to follow a Bernoulli random process. A two‐state Markov chain is used to model the secondary traffic, and two different scenarios are considered. The first scenario assumes that the secondary packet arrivals are independent and follow a Bernoulli random process and a cognitive carrier sensing multiple access (Cog‐CSMA) protocol is proposed. A Rayleigh fading channel is considered in evaluating Cog‐CSMA, and its throughput expression is derived in this paper. The second scenario assumes that the packet arrivals follow a correlated packet arrival process and a cognitive packet reservation multiple access (Cog‐PRMA) protocol is proposed. A Markov chain is used to model the different system states in Cog‐PRMA and derive the throughput. Numerical results show that the Cog‐CSMA and Cog‐PRMA protocols achieve the objective of supporting secondary transmissions in a TDMA network without interfering the PUs' transmissions and improve the network bandwidth utilization. Copyright © 2012 John Wiley & Sons, Ltd.     

A Theoretical Traffic Performance Analysis of an Integrated Voice-Data Virtual Circuit Packet Switch

A time division packet switch capable of concurrently handling both voice and data traffic is proposed, and some of its performance limitations are analyzed. The voice packet traffic is handled at a higher priority level than data traffic, in order to meet stringent timing criteria, and can be shown to be handled just as if it were circuit switched. The data traffic utilizes whatever time slots are not occupied with voice traffic. The principal performance limitations described in this exploratory study are the fraction of time the voice traffic is blocked due to all the available time slots already being used for voice traffic, and an upper bound on the mean delay encountered by the data traffic as it waits to find an available time slot. An illustrative numerical result is the following. If we assume that each voice telephone conversation lasts for a mean of five minutes, and that twenty voice calls are generated over a six hour time span, and each data session lasts for a mean of forty minutes, and that five data calls are generated over a six hour time span, then if separate line switched networks are used for voice and for data with long term blocking probability of one percent, a total of 703 64 kbits links would be required to support 461 voice stations and 882 data terminals. On the other hand, using the integrated voice/data switch described here, and if we assume that the total delay due to the switch alone for data packets cannot exceed a long term mean value of one second, then only 298 64 kbit/s links are required to support 461 voice stations and 882 data terminals, reducing the number of required links by a factor of about two. Moreover, the assumptions leading to this comparison suggest that the packet switch could in fact support significantly more than this number of voice stations and data terminals. This is achieved at the expense of additional buffering for the data in the packet switch approach.     

Evaluating the limit behavior of the ATM traffic within a network

This paper is concerned with the ATM traffic characterization within the network. Most of the work performed up to now has studied the effects of traffic on the access multiplexer and the first switch of an ATM network. Various source models were assumed to generate the ATM traffic. So, while the performance of a single switch node has been exhaustively examined, the statistical behavior of the traffic modified as it crosses the network has not been thoroughly analyzed yet. This paper, through an analysis of a network of cascaded queues, indicates that limit distributions exist in the statistical behavior of the traffic streams and in the queue performance, although a formal proof is believed to be very hard to obtain. The first modelling step consists of deriving the exact interdeparture time distribution for the cells of a reference-connection arriving to the output queue of a switch node with a general interarrival time distribution and multiplexed with a background traffic stream. The analysis is iterated through a long sequence of cascaded output queues, until the interdeparture time distribution converges. Simulations show that the analytical results are accurate at each stage of the network under the hypothesis of independent queues, and are also good approximations in the case of correlated queues. This study shows that the queue performance at the limit point is always better than the M/D/1 case. The distributions found in this way depend only on the connection bandwidth and on the background traffic behavior. The initial characteristics of a connection (burst length distributions and burst interarrival time distributions) only influence the convergence speed, not the limit distribution     

VoIP capacity analysis in cognitive radio system

In this letter, we analyze a voice over IP (VoIP) capacity in a cognitive radio system. We formulate the system as a two-dimensional discrete time Markov chain (DTMC). The VoIP traffic and wireless channel in the cognitive radio system are described as a Markov modulated Poisson process (MMPP) model and a Markov channel model, respectively. We demonstrate various numerical and simulation results, such as packet dropping probability and VoIP capacity.     

A TDM-based multibus packet switch

A new packet switch architecture using two sets of time-division multiplexed buses is proposed. The horizontal buses collect packets from the input links, while the vertical buses distribute the packets to the output links. The two sets of buses are connected by a set of switching elements which coordinate the connections between the horizontal buses and the vertical buses so that each vertical bus is connected to only one horizontal bus at a time. The switch has the advantages of: (1) adding input and output links without increasing the bus and I/O adaptor speed; (2) being internally unbuffered; (3) having a very simple control circuit; and (4) having 100% throughput under uniform traffic. A combined analytical-simulation method is used to obtain the packet delay and packet loss probability. Numerical results show that for satisfactory performance, the buses need to run about 30% faster than the input line rate. With this speedup, even at a utilization factor of 0.9, each input adaptor requires only 31 buffers for a packet loss rate of 10^-6. The output queue behaves essentially as an M/D/1 queue