A key issue in supporting quality of service (QoS) over wireless networks is to estimate the wireless channel capacity that varies randomly with time and space. In this paper, we propose a new model named effective channel capacity to predict the available channel capacity during any given time interval with the required degree of confidence. By leveraging large deviations techniques, we relate the fading channel capacity with the theory of effective bandwidth and establish a connection between the theory of effective bandwidth and information theory. We derive a set of algorithms and apply them to Nakagami-m fading channels. Consequently, our results provide a foundation for the performance analysis of upper layer algorithms and protocols for QoS provisioning over wireless networks

In this paper, we propose a new model named effective fade duration envelope to characterize the accumulative conditional fade durations of individual users or groups of users in wireless communication systems. The proposed model has the following novelties: (1) it introduces the statistical upper and lower bounds with the required degree of confidence for accumulative conditional fade durations during any given time interval; (2) it characterizes various conditional fading circumstances in wireless multi-user communication systems.

In this paper, we propose a theoretical framework to analyze the performance of upper layer algorithms and protocols such as scheduling disciplines which exploit the gain of multi-user diversity to optimize the utilization of wireless communication systems while supporting service differentiation between different users.

Previous work on congestion control in TCP/IP networks combines improved end-user transmission mechanisms with active queue management schemes at network routers. An active queue management scheme consists of two stages. In order to stabilize the queues at a router, one must first determine an appropriate packet marking probability given the current degree of congestion. Second, in order to realize the desired marking probability, an effective packet marking algorithm needs to be implemented to decide which packets should be marked. Researchers have increasingly focused on the first stage, namely determining the fraction of packets to mark, overlooking the fact that for a given marking probability, various possible marking algorithms result in different queue variance, and thus loss, delay, and jitter. We propose a marking algorithm DREAM. DREAM decouples the functions of reducing queue variance and randomizing the phases of flows. Compared to existing schemes, it significantly reduces queue variance while avoiding flow synchronization. Based on a simple Markov chain model we explain why our scheme is superior. Our simulation results confirm its effectiveness. Furthermore, DREAM is simple to implement and has a much lower overhead as compared with existing mechanisms.

This paper presents a new mechanism of weighted fair bandwidth sharing for differentiated services (DiffServ) assured forwarding (AF) services. The mechanism is named SCALE-WFS, i.e. Scalable Core with Aggregation Level labEling-Weighted Fair bandwidth-Sharing. It aims to achieve near-optimal max-min weighted fairness without per-flow management at core routers. Through extensive simulation and simple analysis, we show its advantages over the current solutions (CSFQ or TCM+RED3) for different flow weights, RTTs and protocols (TCP and UDP), especially under the scenarios of different bandwidth provisioning and multiple congested gateways. Apart from "per-flow" and completely "core-stateless", SCALE represents a third management level-the label-based flow "aggregation" level. It reduces the information redundancy in the "per-flow" and surpasses the performance of the "core-stateless". Thus we avoid the non-scalability of per-flow management in DiffServ networks while keeping its good quality of services. We show that the SCALE-WFS is effective, scalable and robust for weighted fairness guarantees.

As networks evolve to carry multi-service traffic, each flow's bandwidth requirement is getting very diverse. We notice that even though the bandwidth usage level at a certain link is not high, if the number of connections carried on the link is excessive, it should be regarded as congested. We introduce connection resource notion into the traffic engineering. By incorporating the bandwidth resource notion and connection resource notion together into the problem formulation, we set up a more precise model for the multi-service network. To represent congestion cost at the links effectively, a nonlinear convex curve is used. The curve is then piece-wise linearized in the LP problem formulation. A calculation algorithm to get the link metric from the solution of the optimization problem is devised. In our framework, the congestion cost is caused either by the shortage of bandwidth or connection resource. Under the shortest path first routing scheme, we show through numerical experiments that the link metric set calculated by the new algorithm effectively reduces the congestion cost.

We have studied the delay related rate oscillation within Diffserv. The selective attenuation feedback via estimation (SAFE) is proposed to reduce the oscillation while maintaining fast response to network dynamics. SAFE has no per-flow accounting. Furthermore, the hashing technique is adopted to keep the operating overhead of SAFE to its minimum. System analysis supports the effectiveness of SAFE. The simulation result also shows that SAFE significantly reduces the rate oscillation, therefore achieves a high link utilization and small queue size while maintaining very low control overhead.

This paper assesses the predictability of network traffic by considering two metrics: (1) how far into the future a traffic rate process can be predicted for a given error constraint; (2) what the minimum prediction error is over a specified prediction time interval. The assessment is based on two stationary traffic models: the auto-regressive moving average (ARMA) model and the Markov-modulated Poisson process (MMPP) model. Our study in this paper provides an upper bound for the optimal performance of online traffic prediction. The analysis reveals that the application of traffic prediction is limited by the quickly deteriorating prediction accuracy with increasing prediction interval. Furthermore, we show that different traffic properties play different roles in predictability. Traffic smoothing (low-pass filtering) and statistical multiplexing also improves predictability. In particular, experimental results suggest that traffic prediction works better for backbone network traffic, or when short-term traffic variations have been properly filtered out. Moreover, this paper illustrates the various factors affecting the effectiveness of traffic prediction in network control. These factors include the traffic characteristics, the traffic measurement intervals, the network control time-scale, and the utilization target of network resources. Considering all of the factors, we present guidelines for utilizing and evaluating traffic prediction in network control areas.

In voice trunking over ATM (VTOA) technology, the tandem is replaced by three components: trunk inter-working function (T-IWF), control and signaling inter-working function (CS-IWF), and ATM network. This new architecture calls for re-examination of the signaling channel delay issues, which are well-studied and well-specified for TDM networks. In VTOA, the ATM network together with the inter-working functions act as a virtual tandem switching system, which is called "ATM-based distributed virtual tandem switching system". The aim is that the performance of the ATM-based trunking network should be at least as good as the TDM-based network. The cross-office delay budget must be shared among the inter-working functions and the ATM network. Hence, the time for the ATM network to establish a switched virtual connection (SVC) is stringent. In this paper, we propose a simple adaptive SVC caching scheme to offload the high processing capacity burden on ATM switches. After a SVC is established in the usual way for a call, it is not torn down after the conversation is over. Instead, it is kept alive for variable duration (i.e., delayed release) with the expectation that there would be another call request for the same terminating end office during that time. The caching duration is adaptively changed with call arrival rate and call setup delay in the ATM network in order to stay within the delay budget specified by the requirements. The adaptability and the convergence of the algorithm are also shown by extensive simulations related to practical scenarios.

This paper addresses the fundamental issue of providing per-flow fairness within the Diffserv framework. The fair allocation derivative estimation (FADE) algorithm for estimating flow fair share in the absence of per-flow information is proposed. FADE calculates fair share feedback using a modified quasi-Newton method. This efficient method for estimating fair share provides a more precise model than other existing fairness estimation approaches. As such, it is able to more accurately estimate fair share and quickly converge to the proper rate. The simulation compares FADE to other proposals and demonstrates the overall effectiveness of the algorithm.

We introduce a rapid measurement-based traffic modeling technique that can be completely automated; no parameter tuning or other manual intervention is required. The model is designed such that both its rate cumulative density and power spectral density functions match those of the original traffic over the time-scales of interest. Since the model is derived from Fourier series representation and the discrete-time Markov Modulated Poisson Process (MMPP), it can easily capture diverse, even non-rational, power spectral densities.

This paper evaluates the buffer requirements resulting from rate mismatch in a 32/spl times/32 ATM switch with sixty OC-3 (155 Mbps) and four T-1 (1.5 Mbps) ports. Rate mismatch is expected to be a common occurrence in ATM wide area networks, particularly at the network seams. Without proper dimensioning, the switch buffers can rapidly overflow as a result of high-speed input traffic destined to a low-speed port. We specifically consider the Cisco Systems LightStream 1010 ATM switch architecture in our analysis, and compare the design options of a larger common shared buffer with that of adding buffers to each T-1 output port. We consider traffic from individual high-speed servers, LAN workstations, and aggregated Ethernet traffic.

We propose a framework for the performance analysis and flow classification design of multi-protocol over ATM (MPOA) network. The study based on the real Internet/intranet traces shows that even at high cost with long delay for each shortcut setup, MPOA can offer significant performance gain over the traditional routed network in an inter ELAN communication environment. In comparison, the MPOA performance gain in an Internet backbone environment is much less significant, mainly because of the dominant short-lived flows contributed by both d.n.s. and h.t.t.p. applications. We also propose a flow classification algorithm, which substantially reduces the implementation complexity while achieves the same level of performance as compared to the default flow classification algorithm proposed by MPOA standard. A simple timeout mechanism is also introduced to the flow cache table management for significant performance improvement. We further develop a stable, adaptive flow classification algorithm, which achieves a near-optimal solution to minimize the constrained MPOA resource utilizations.

We present simple and informative new measurement functions. Their applications on real traffic traces provide insightful guidelines for measurement-based network control. We investigate practical scenarios and conclude that robust and insensitive measurement intervals can be found with the consideration of multiplexing and connection/flow dynamics. We find that a considerable percentage of the effective bandwidth is required by low frequency traffic in the context of realistic implementations. For a queuing node with the maximum allowable queuing delay d/sub max/, it is quantitatively shown that peak rate of the input traffic filtered (smoothed) with the averaging period of 200d/sub max/ captures more than 80% of the effective bandwidth when traffic aggregation and flow/connection dynamics are considered.

We identify important characteristics of a fading/shadowing channel and present the work of measurement-based channel modeling for packet-level network queueing analysis. Our integration of wireless channel modeling and data queueing analysis at the packet-level provides a unique approach to study the effect of various channel dynamics on high-layer network performance, which otherwise cannot be captured through the traditional bit-level physical-layer channel modeling. In our study, the channel statistics are decomposed into three frequency regions [i.e., low (LF), mid (MF), and high (HF)]; the statistics in each frequency region is found to have significantly different impact on the queueing performance. While the HF statistics can be largely ignored in channel modeling due to their negligible impact on queueing performance, the LF statistics play the most important role in channel modeling because of substantial impact on queueing performance. Since the shadowing mainly represents the LF behavior of a channel, its dynamics are found to have a dominant effect on network performance as compared to the effect of multipath fading dynamics. In wireless networks, there are many other system factors which may change the channel dynamics, such as mobile user driving patterns, and forward-error-correction (FEC) coding (fixed or adaptive) using automated repeat request (ARQ) scheme. Our study further examines the individual impact of these factors on the network performance. In the measurement-based channel modeling, we use a Markov chain modeling technique to match the important channel statistics for queueing system analysis. The study shows an excellent agreement in queueing solutions between using the real original channel traces and using the sequences generated by the matched Markov chain models.

Data performance in ATM networks should be measured on the packet level instead of the cell level, since one or more cell losses within each packet is equivalent to the loss of the packet itself. Two packet-level control schemes, packet tail discarding and early packet discarding, were proposed to improve data performance. In this paper, a new stochastic modeling technique is developed for performance evaluation of two existing packet-discarding schemes at a single bottleneck node. We assume that the data arrival process is independent of the nodal congestion, which may represent the unspecified bit-rate traffic class in ATM networks, where no end-to-end feedback control mechanism is implemented. Through numerical study, we explore the effects of buffer capacity, control threshold, packet size, source access rate, underlying high-priority real-time traffic, and loading factor on data performance, and discuss their design tradeoffs. Our study shows that a network system can he entirely shut down in an overload period if no packet-discarding control scheme is implemented, under the assumption that there are no higher layer congestion avoidance schemes. Further, unless with sufficiently large buffer capacity, early packet discarding (EPD) always outperforms packet tail discarding (PTD) significantly under most renditions. Especially under the overload condition, EPD can always achieve about 100% goodput and 0% badput, whereas the PTD performance deteriorates rapidly. Among all the factors, the packet size has a dominant impact on EPD performance. The optimal selection of the EPD queue control threshold to achieve the maximum goodput is found to be relatively insensitive to traffic statistics.

This paper proposes a novel approach for adaptive flow classification for flow-based hybrid switching systems to match the time varying traffic/resource characteristics. It minimizes the maximum of the system resource utilizations associated with packet processing power, signalling capacity and routing table size. After formulating the proposed flow adaptation as a min-max stochastic control problem, a heuristic algorithm is developed. The simulation study based on real traces shows the viability of the proposed flow adaptation for dynamic resource management in hybrid switching system design. The algorithm is simple to implement and only requires the adaptation of two global variables at time intervals of every few seconds based on the present usage of resources.

This paper evaluates the additional buffer requirements of an ATM shared-memory switch using packet-level (store-and-forward) rather than cell-level (cut-through) service scheduling. Packet-level scheduling is important to tag and IP switching for multipoint-to-one services; it allows different connections to be merged into a single virtual connection to reduce routing complexity. Cisco Systems will incorporate packet-level scheduling in their LightStream 1010 ATM switch using a feature upgrade card possessing per flow queueing; we thus specifically consider the LightStream 1010 architecture in our analysis.

The fast fading channel modeling traditionally focuses on physical-level dynamics such as signal strength and bit error rate. We characterize fast fading channel dynamics at the packet-level and analyze the corresponding data queueing performance in various environments. The integration of wireless channel modeling and data queueing analysis provides us a unique way to capture important channel statistics with respect to various wireless network factors such as channel bandwidth, mobile speed and channel coding. The second order channel statistics, i.e., channel power spectrum, is identified to play a dominant role in fast fading channel modeling. The data queueing performance is largely dependent on the interaction between the channel power spectrum and the data arrival power spectrum, whichever has a lower frequency power will have a dominant impact on the queueing performance. The data arrival power spectrum provides a measure of burstiness and correlation behavior of data packet arrivals. In queueing analysis, we use a Markov chain modeling technique to match the measured important channel statistics.

The research on guaranteeing quality of services has been to a large extent focusing on satisfying cell-level performance such as cell loss rate, cell delay variation, etc. In the authors' previous work, they have used stochastic modeling techniques to evaluate the packet-level performance of two existing packet discarding schemes, packet tail discarding and early packet discarding, based on three packet-level performance measures: packet success probability, goodput, and badput. The work focused on the performance evaluation of data packet transmission over ATM unspecified bit rate (UBR) service. With the introduction of available bit rate (ABR) service, source regulation based on closed-loop control becomes increasingly important. In this work we analyze the performance of early packet discarding when the source transmission rates are governed by the feedback information from a congested ATM bottleneck node. Numerical study shows that the steady-state performance are largely affected by slow time scales of the feedback system. Nonetheless, the design of control threshold in early packet discarding is not significantly sensitive to the system time scales.

This paper develops fast algorithms for the construction of a circulant modulated rate process to match with the two primary traffic statistical functions: rate distribution f(x) and autocorrelation R(/spl tau/). Using existing modeling techniques, f(x) has to be limited to certain forms such as Gaussian or binomial; R(/spl tau/) can only consist of one or two exponential terms which are often real exponentials rather than complex. In reality, these two functions are collected from real traffic traces and generally expressed in a very complicated form. We only consider the traffic whose correlation function can be approximated by the sum of complex exponentials. Our emphasis is placed on the algorithm design for matching complicated R(/spl tau/) in traffic modeling. The typical CPU time for traffic modeling with R(/spl tau/) consisting of five or six complex exponential terms is found to be in the range of a few minutes by the proposed algorithms. Our study further shows an excellent agreement between the original traffic traces and the sequences generated by the matched analytical model. The selection of the measurement-window in traffic statistics collection for queueing performance analysis is also discussed.

This paper addresses a fundamental problem in resource management for flow-based hybrid switching systems. Such systems aim at efficient transport of layer-3 connectionless IP traffic over layer-2 connection-oriented ATM switching fabrics. One idea behind flow-based hybrid switching is to decompose individual IP packet streams into flows and then to classify them into short-lived and long-lived flows. While the short-lived flows are good for forwarding by the embedded software through permanent virtual connections (PVCs), the long-lived flows are more effectively transmitted by hardware through switched virtual connections (SVCs). Clearly the flow identification/classification mechanism will have great impact on the utilization of the system's resources. Our paper focuses on the resources which are directly associated with packet processing power, signaling capacity, and flow cache table size. Our study indicates that the presently available static flow classification methods have a vital shortcoming in balancing the utilization of the system's resources. We propose a novel approach for adaptive flow classification based on the min-max objective for the system resource utilizations to match with the time-varying traffic/resource characteristics based on the monotone properties and sensitivity analysis of the resource utilizations as functions of the control parameters, we first prove that the optimal solution of the static min-max problem is achieved at a unique balance point for the resource utilizations. With the intuition gained from the static results, we then design an adaptive controller formulated as a hierarchical stochastic automata control system with local search. The optimality of the proposed adaptive controller is tested against the static optimal control based on real trace simulations. The simulation studies in highly nonstationary environments show the viability of the proposed flow adaptation for dynamic resource management in hybrid switching system design. The algorithm is simple to implement and only requires the adaptation of two global variables at time intervals of every few seconds based on the present usage of resources.

We develop analytical approximations for the first order and second-order statistics of the delay jitter experienced by a stationary traffic stream multiplexed at a major communication node; these approximations are then used to gain insight into the behavior of jitter at a single node under diverse system and traffic conditions. Our construction applies when the node can be modeled as a finite quasi-birth-death (QBD) process and the interarrival time probability density functions (pdfs) for the tagged stream are obtainable. We compare the jitter performance of three different tagged streams: periodic, Poisson, and on/off binary Markov process. Because jitter behavior is most deleterious for the former, we study the individual effects of various system and traffic parameters on the jitter statistics of a periodic stream multiplexed in a Markov-modulated Poisson process (MMPP)/M/1/K system. To demonstrate the flexibility of this analytical technique, we also consider a JPEG video stream multiplexed with JPEG, MPEG, and data sources on an OC-12 line.

In this paper, we present a numerical approach to the performance study of a delayed feedback system with one congested node and multiple connections. This approach consists of modeling the feedback system as a finite quasi-birth-death process. Due to the peculiar block tridiagonal nature of its generator, efficient techniques exist for its steady-state and transient solutions. Using these techniques, we examine a simple parsimonious feedback system for issues such as throughput/loss performance, fairness, and stability. Our approach has the flexibility to study the effect of several additional factors such as asynchronous feedback, two-level control, and explicit rate notification in the presence of underlying high-priority traffic. This study brings to light the tradeoffs between system performance and the complexity of the feedback scheme. Our study shows that the time scales of correlation of the feedback system have a dominant effect on its performance. These time scales are associated with the feedback delay, the durations of active/idle periods of traffic sources, and the time scales of the underlying high-priority traffic. We also examine the effect of the time scales on the convergence time for the transient queueing system.

This paper develops fast algorithms for construction of circulant modulated rate process to match with two primary traffic statistical functions: distribution f(x) and autocorrelation R(/spl tau/) of the rate process. Using existing modeling techniques, f(x) has to be limited to certain forms such as Gaussian or binomial; R(/spl tau/) can only consist of one or two exponential terms which are often real exponentials rather than complex. In reality, these two functions are collective for real traffic traces and generally expressed in a much more complicated form. Our emphasis here is placed on the algorithmic design for matching complicated R(/spl tau/) in traffic modeling. The typical CPU time for the traffic modeling with R(/spl tau/) consisting of five or six complex exponential terms is found in the range of a few minutes by the proposed algorithms. Our study further shows an excellent agreement between original traffic traces and sequences generated by the matched analytical model.

We propose an explicit-rate ABR feedback control scheme, UT (uniform tracking). The distinct feature of UT is that it achieves max-min fairness by tracking an effective number of sources; specific constraint information is not required. As a result, its implementation is much simpler than that of other fair control schemes; indeed, its complexity is similar to that of unfair explicit-rate controls. In the thorough simulation study, UT demonstrates its ability to scale with speed, distance, number of users (both persistent and bursty), and number of switches while remaining robust, efficient, and fair under stressing conditions with MPEG background traffic and multiple propagation delay loops.

We develop a Markov chain modeling framework for throughput/delay analysis of data services over cellular voice networks, using a dynamic channel stealing method. Some effective approximation techniques are also proposed and verified for simplification of the modeling analysis. Our study identifies the average voice call holding time as the dominant factor affecting the data delay performance. Especially in heavy load conditions, namely when the number of free voice channels becomes momentarily less, the data users will experience large network access delay in the range of several minutes or longer on average. We also examine the data performance improvement by using a priority data access scheme and speech silence detection technique.

Closed-loop input rate regulation schemes have come to play an important role in the transport of the available bit rate (ABR) traffic service category for ATM. We present a numerical approach to the performance study of a delayed feedback system with one congested node and multiple connections. This approach consists in modeling the feedback system as a finite quasi-birth-death (QBD) process. Due to the peculiar block tri-diagonal nature of its generator, efficient techniques exist for its steady-state and transient solutions. Using these techniques, we examine a simple parsimonious feedback system for issues such as throughput/loss performance, fairness and stability. Our approach has the flexibility to study the effect of several additional factors such as asynchronous feedback, two-level control and explicit rate notification in the presence of underlying high-priority traffic. This study brings to light the trade-offs between system performance and the complexity of the feedback scheme. Our study shows that the time scales of correlation of the feedback system have a dominant effect on its performance. These time scales are associated with the feedback delay, the durations of active/idle periods of traffic sources and the time scales of the underlying high-priority traffic. We also examine the effect of the time scales on the convergence time for the transient queueing system.

This paper focuses on the important stability issue of ABR traffic control with explicit-rate schemes. We develop a novel design approach with three advantages. First, the ABR rate is only adapted to the low-frequency variation of the underlying VBR traffic, which effectively prevents network congestion with much improved control stability. Second, a linear dynamic model is presented which makes the optimal control theory readily applied to the design of ABR control. Third, the control of different ABR loops is uncoupled, which significantly simplifies the control scheme. With this approach, stability analysis for the controlled network becomes feasible with the knowledge of VBR traffic characteristics. We propose a new explicit-rate ABR control scheme, called the H/sub 2/ scheme, which has the same level of design complexity as the existing schemes but with rigorously proved stability. The stability problem of the existing explicit rate schemes is also considered.

In this paper we present a method to establish real-time connections with guaranteed quality of service (QOS), based on a per-session probabilistic burstiness curve (PBC). Under two distinctive service disciplines, role proportional processor sharing and fixed rate processor sharing, we derive useful probabilistic bounds on per-session end-to-end loss which is caused by either buffer overflow in the path or excessive delay to the destination. One remarkable feature of the bounding solutions is that they are solely determined by the PBC of each session itself, independent of the network environment and other connections. To improve network resource utilization, our method is extended to allow statistical sharing of buffer resources. The admission control scheme presented in this paper has a great flexibility in connection management since bandwidth and buffer allocations can be adaptively adjusted among incoming and existing sessions according to present network resource availability. We also present a novel method to compute the PBC of multimedia traffic based on the measurement of two important statistics (rate histogram and power spectrum). Our study of MPEG/JPEG video sequences reveals the fundamental interrelationship among the PBC, the traffic statistics, and the QOS guarantee, and also provides many engineering aspects of the PBC approach to real-time multimedia services in ATM networks.

This paper uses measurement-based traffic models to evaluate a shared-memory ATM switch with 32/spl times/32 155 Mbit/s ports and an external multicasting engine; this is the design of Cisco System's next-generation ATM switch, the LightStream-1010 (LS-1010). Assuming that the multicast traffic can take approximately 30% of the total switch load, we find that an external multicasting engine requires a 32 (8) cell buffer at a replication rate of 16 (64) cells per cell service time. We discover that in a multimedia environment, the shared-memory architecture requires 10-30 times less total memory than the bus architecture; a 64 K cell buffer is sufficient to handle 90% utilization with the nonuniform traffic that we investigated. Multiple-priority classes are considered.

We study the effectiveness of statistical multiplexing and buffer sharing under the multimedia high-speed networking environment. We focus on the impact of frequency-domain source characteristics on dynamic resource sharing. By applying a novel statistical matching technique, we can, for the first time, investigate the multiplexing performance of a wide-range of realistic traffic sources using sophisticated traffic models. It has been shown that the effectiveness of statistical multiplexing and buffer sharing highly depends on the frequency-domain characteristics of the traffic as well as the corresponding QoS requirements. For practical "low-frequency" sources; e.g., VBR-video streams and LAN-to-LAN traffic, we show that significant savings in bandwidth and buffer-space can be achieved via resource sharing under practical loss and delay constraints. These findings re-illustrate the important role of traffic characteristics in the design/selection of network control strategies. The trade-offs among different design alternatives (e.g., multiplexing versus buffering) and the implications on some control schemes, e.g., traffic shaping/input-rate control, are also discussed.

The analytical tool developed by the authors provides a general solution technique for integration of traffic measurement and queueing analysis. The frequency-domain approach is used to combine the advanced techniques in two areas: signal processing and queueing analysis. Essentially, signal processing techniques are used to obtain the steady-state and second-order statistics of a traffic stream. We propose a new programming method for the construction of a special class of Markov chains to statistically match with each given traffic stream (or superposition of heterogeneous traffic streams). The analytical queueing solutions can therefore be obtained by the folding-algorithm based on Markov chain input modeling. Comprehensive numerical examples show the great potential of the statistical-matching and queueing (SMAQ) tool to solve measurement-based traffic management issues.

Consider a single node queueing system which can be modeled by a finite quasi-birth-death (QBD) process. We present a computational technique for spectral analyses (i.e., second-order statistics) of output, queue, and loss. The emphasis is placed on the performance evaluation of output power spectrum and input-output coherence function with respect to various input power spectral properties and system parameters. The coherence function is defined to measure the linear relationship between input and output processes. Through the evaluation of the coherence function, we identify a so-called nonlinear break frequency, /spl omega//sub b/, under which the low-frequency traffic stay intact via a queueing system. Such a low-frequency I/O linearity plays an important role in characterizing the output process, which may form a partial input to other "downstream" queues of the network. In particular, the unchanged "upstream" low-frequency traffic characteristics are expected to have a significant impact on the "downstream" queues as well. Our numerical analysis examines the sensitivity of /spl omega//sub b/ to traffic characteristics and system parameters. The study further indicates that the link capacity requirement of traffic at a given buffer system is essentially characterized by its maximum input rate filtered at /spl omega//sub b/.

Consider the link bandwidth allocation for transport of correlated traffic through a queueing system under a maximum allowable delay constraint d/sub max/. We decomposed the traffic into three frequency regions: low-frequency traffic in 0<|/spl omega/|/spl les//spl omega//sub L/, high-frequency traffic in |/spl omega/|/spl ges//spl omega//sub H/ and mid-frequency traffic in /spl omega//sub L/<|/spl omega/|

In this paper, we study the sojourn-time statistics and the temporal behavior of nodal congestion in integrated broadband networks. The node is modeled as a finite quasi-birth-death (QBD) process with level-dependent transitions. By formulating the problem as one which is amenable to the generalized folding algorithm (GFA), we are, for the first time, able to analyze realistic systems with large buffer and complex input traffic. The dynamics of the system under realistic traffic environment and different operating regimes are studied. The effects of various modeling artifacts such as fluid-flow and infinite-buffer approximations are also investigated. The potential of statistical multiplexing in reducing bursty cell loss is demonstrated. The trade-offs between different system design alternatives, e.g., buffering vs. statistical multiplexing, are discussed. We also investigate the controlling effect of preemptive cell discarding on steady-state and transient system performance. Both single-level and two-level overload control with hysteresial-switching mechanisms are considered. The use of sojourn-time based QoS metrics to supplement long-term steady-state metrics is also discussed.

Recent measurement studies in Bellcore and elsewhere have convincingly established the presence of statistical self similarity in high-speed network traffic. What is less clear --- and as such the subject of intense current research --- is the impact of the self-similarity on network performance. Given that traditional queueing models of network performance do not model self-similarity, the validity of traditional models to predict network performance would be supported if it is shown that self-similarity does not have measurable impacts on performance. On the other hand, if the converse of this assertion were true, it would have significant impacts on the way networks are designed and analyzed, as well as open up new areas of research in mathematical modeling, queueing analysis, network design and control. The issues addressed in this session are therefore of fundamental importance in high-speed network research.Given that queueing behavior is dominated by traffic characteristics over the time scales of busy periods, it has been argued that phenomena that span many time scales, such as self-similarity, should not be relevant for queueing performance. However, the paper by Narayan, Erramilli and Willinger presents evidence that for data traffic, the long range dependence (which is related to the self-similarity in traffic) can dominate queueing behavior under a variety of conditions. Specifically, it is shown based on a series of carefully designed simulation experiments with actual traffic traces, that the queueing behavior with actual traces is considerably heavier than that predicted by traditional theory, and that these differences are attributable to long range dependence. The paper by Heyman and Lakshman investigates modeling of video traffic to predict cell loss performance with finite buffer systems, and they conclude that long-range dependence is not a crucial property in determining the finite buffer behavior of video conferences. In particular, a Markov chain model that does not model long-range dependence is nevertheless able to reproduce various operating characteristics over a wide range of loadings obtained with the actual video trace. Mukherjee, Adas, Klivansky and Song investigate the performance impacts of short-range and long-range correlation components using simulations with a fractional ARIMA model. They also discuss a strategy to provide quality of service guarantees with long range dependent traffic, as well as recent results on NSFNET traffic. Finally, the paper by Li describes a frequency-domain based analytical tool that matches a special class of Markov chains with traces exhibiting a variety of characteristics, including long-range dependence. Good agreement is reported between analytical queueing solutions of the matched Markov chains, and simulation results obtained video and data traffic traces.This session therefore brings together a wide range of viewpoints on this issue. Resolution of such seemingly conflicting conclusions lies in the fact that in performance analysis, answers sensitively depend on the specific details of a problem. Thus the proper question to ask is not whether or not self-similarity matters in queueing; but under what conditions it matters. Likewise, the question to ask is not whether a class of models is invalid; but to identify the conditions under which traditional Markov or self-similar traffic models are expected to be valid. Finally, given an understanding of statistical features that are relevant to a given problem, the challenge is to model these accurately and parsimoniously so that the model is useful in practical performance analysis. The work outlined in the abstracts below adds significantly to our understanding of these issues.

This paper presents a novel approach to dynamic transmission bandwidth allocation for transport of real-time variable-bit-rate video in ATM networks. Video traffic statistics are measured in the frequency domain. The low-frequency signal captures the slow time-variation of consecutive scene changes while the high-frequency signal exhibits the feature of strong frame autocorrelation. Our queueing study indicates that the video transmission bandwidth in a finite-buffer system is essentially characterized by the low-frequency signal. We further observe in typical JPEG/MPEG video sequences that the time scale of video scene changes is in the range of a second or longer, which localizes the low-frequency video signal in a well-defined low-frequency band. Hence, in a network design it is feasible to implement dynamic allocation of video transmission bandwidth using on-line observation and prediction of scene changes. Two prediction schemes are examined: recursive least square method and time delay neural network method. A time delay neural network with low-complexity high-order architecture, called "pi-sigma network," is successfully used to predict scene changes. The overall dynamic bandwidth-allocation scheme presented is shown to be promising and practically feasible in obtaining efficient transmission of real-time video traffic.>

We study link capacity allocation for a finite buffer system to transmit multimedia traffic. The queueing process is simulated with real video traffic. Two key concepts are explored in this study. First, the link capacity requirement at each node is essentially captured by its low-frequency input traffic (filtered at a properly selected cut-off frequency). Second, the low-frequency traffic stays intact as it travels through a finite-buffer system without significant loss. Hence, one may overlook the queueing process at each node for network-wide traffic flow in the low-frequency band. We propose a simple, effective method for link capacity allocation and network control using on-line observation of traffic flow in the low-frequency band. The study explores a new direction for measurement-based traffic control in high-speed networks.>

The paper presents a novel approach to dynamic transmission bandwidth allocation for transport of real-time variable-bit-rate video in ATM networks. The authors describe video traffic in the frequency domain: the low frequency signal captures the slow time-variation of consecutive scene changes; the high frequency signal exhibits the feature of strong frame autocorrelation. The study indicates that the video transmission bandwidth in a finite-buffer system is essentially characterized by the low, frequency signal. Since the time scale of scene changes is usually in the range of a second or longer, the low frequency video signal is defined in a well-founded low frequency band. Hence, it is feasible to implement dynamic allocation of video transmission bandwidth using on-line observation and prediction of scene changes. Two prediction schemes are examined: the recursive least square method vs. the time delay neural network method. A time delay neural network with low-complexity high-order architecture, called a "pi-sigma network", is successfully used to predict scene changes. The proposed dynamic bandwidth allocation scheme is shown to be promising and practically feasible in obtaining efficient transmission of real-time video traffic with guaranteed quality of services.>

Considers a single-server finite-buffer system. Its stationary random input process as characterized by the power spectrum P(/spl omega/) and the input rate steady state distribution f(x). The two functions represent second-order and steady-state input statistics. The authors use the superposition of heterogeneous 2-state Markov chains (MC) for construction of P(/spl omega/) and f(x). The resulting P(/spl omega/) is a monotone function of |/spl omega/|, and f(x) is the convolution of heterogeneous binomial functions. They show how to eliminate the state space explosion in input modeling. Unlike the existing modeling technique which matches the 2-state MC with each individual source, their 2-state MC are built to statistically match with functions P(/spl omega/) and f(x) of the aggregate input. The input state space is then reduced by many orders of magnitude. They examine the maximum throughput of a finite-buffer system to support P(/spl omega/) and f(x) subject to a desired average loss rate L. The numerical study explores a fundamental limit of buffer sizing to the maximum throughput improvement. A simple heuristic formula is developed, which tells quantitatively whether a given finite-buffer system operates in a so-called buffer-noneffective region. The new insight relating link capacity to low frequency input statistics explored in the paper is a fruitful starting point for further research.>

Key properties of multimedia traffic are characterized by the great diversity of correlation and burstiness. The authors construct the multimedia traffic by heterogeneous 2-state Markov chains (MC) and allow each 2-state MC to be defined on different transition intervals, representing the diversity of peak access rate from individual sources. Upon time renormalization, the queue is modeled by a multi-dimensional discrete Markov process. Generalizing the technique developed previously the authors are able to construct the entire solution of queue length distributions. It uses a generating function approach. By matrix spectral decomposition, one can decompose the evaluation of each individual vanishing/non-vanishing root. Each vanishing root is used to obtain the queue boundary values; each non-vanishing root constructs a geometric term in the expression of the queue length distribution. It is found that all the vanishing roots must be real and all the complex non-vanishing roots can be ignored. In numerical studies, the authors examine the effect of diverse source access rates and time-varying scales on ATM queues.>

A wideband source in high speed networks is typically represented by a binary random process. In this paper we characterize the second-order properties of each binary source by a multi-state Markov modulated Poisson process (MMPP). A comprehensive numerical study is carried out to identify the individual effect of the source second-order dynamics on the queue length and loss rate. The results can be used to verify the validity of the two-state Markov chain binary source assumption which is commonly made within the framework of input rate control and bandwidth allocation in high speed networks. The concept of input power spectrum is then developed as a unified source characterization for multimedia traffic queueing analyses.>

This paper presents a new computational method for steady state analysis of finite quasi-birth-death (QBD) processes with level-dependent transitions. The QBD state space is defined in two-dimension with N phases and K levels. Instead of formulating solutions in matrix-geometric form, the Folding-algorithm provides a technique for direct computation of /spl pi/P=0, where P is the QBD generator which is an (NK)/spl times/(NK) matrix. Taking a finite sequence of fixed-cost binary reduction steps, the K-level matrix P is eventually reduced to a single-level matrix, from which a boundary vector is obtained. Each step halves the matrix size but keeps the QBD form. The solution /spl pi/ is expressed as a product of the boundary vector and a finite sequence of expansion factors. The time and space complexity for solving /spl pi/P=0 is therefore reduced from O(N/sup 3/K) and O(N/sup 2/K) to O(N/sup 3/ log/sub 2/ K) and O(N/sup 2/ log/sub 2/ K), respectively. The Folding-algorithm has a number of highly desirable advantages when it is applied to queueing analysis. First, the algorithm handles the multilevel control problem in finite buffer systems. Second, its total independence of the phase structure allows the algorithm to apply to more elaborate, multiple-state Markovian sources. Its computational efficiency, numerical stability and superior error performance are also distinctive advantages.>

Uses the well known technique of power spectral representation to characterize the second order statistics of packet loss during congestion at a statistical multiplexer. Unlike the steady state statistics, the second order statistics measures the time correlation behavior of loss. Typically, the low frequency loss power is associated with long periods of highly consecutive loss. The effect of the loss rate power spectrum on transmission qualities is service dependent. The study indicates that, by selective packet discarding, one can properly change the distribution of the overall loss rate spectrum among the multiplexed traffic streams, which can significantly improve the transmission quality of individual services. Moreover, with the design of multi-level buffer overload control, one can tune the loss rate steady state distribution of different priority streams to a piece-wise step function, which minimizes the packet loss impact on service qualities.>

The conditions under which nodal decomposition can be applied for networkwide, multimedia traffic analysis are determined. Through extensive simulation studies of individual departure source characteristics and intersource cross-correlation at the output side of a network node, the nodal decomposition approach is validated for large-scale high-speed, integrated networks. Both homogeneous and heterogeneous traffic environments in which individual sources are modeled as various two-state/multiple-state Markov-modulated processes are considered. By applying the validated nodal decomposition approach, the problem of analyzing the performance of a multimedia network as a whole becomes tractable. Each ATM node is modeled by a queue with infinite buffers and a deterministic server.>

The fundamental limits of input rate control by specific analysis in the frequency domain are explored. Both deterministic and stochastic analyses are developed. The simple deterministic analysis helps provide knowledge about the performance tradeoff for input rate control in a high-speed network.>

A wideband source in high speed networks is typically represented by a binary random process. The second-order properties of each binary source are characterized here by a multistate Markov-modulated Poisson process. A comprehensive numerical study is carried out to identify the individual effect of source second-order dynamics on queue length and loss rate. The concept of input power spectrum is then developed as a unified source measurement for multimedia traffic queuing analyses. The authors thoroughly explore the relationship between the source second-order dynamics in the time domain and the input power spectrum in the frequency domain, as well as its overall impact on system performance.>

The authors explore a new concept of spectral characterization of wide-band input process in high speed networks. It helps them to localize wide-band sources in a subspace, especially in the low-frequency band, which has a dominant impact on queueing performance. They choose simple periodic-chains for the input rate process construction. Analogous to input functions in signal processing, they use elements of DC, sinusoidal, rectangular pulse, triangle pulse, and their superpositions, to represent various input correlation properties. The corresponding input power spectrum is defined in the discrete-frequency domain. In principle, a continuous spectral function of stationary random input process can be asymptotically approached by its discrete version as one sufficiently reduces the discrete-frequency intervals. An understanding of the queue response to the input spectrum will provide a great deal of knowledge to develop advanced network traffic measurement theory, and help to introduce effective network resource allocation policies. The new relation between queue length and input spectrum is a fruitful starting point for further research.>

Queueing performance in a richer, heterogeneous input environment is studied. A unique way to understand the effect of second- and higher-order input statistics on queues is offered, and new concepts of traffic measurement, network control, and resource allocation are developed for high-speed networks in the frequency domain. The technique applies to the analysis of queue response to the individual effects of input power spectrum, bispectrum, trispectrum, and input-rate steady-state distribution. The study provides clear evidence that of the four input statistics, the input power spectrum is most essential to queueing analysis. Furthermore, input power in the low-frequency band has a dominant impact on queueing performance, whereas high-frequency power to a large extent can be neglected.>

The author uses a generating function approach with spectral decomposition for discrete queuing analysis with arrival and service Markov chains (MCs). The complexity of this approach lies in the construction of eigenvalues and eigenvectors for both arrival and service generating function matrices. A MC is called decomposable if it can be decomposed into a set of smaller MCs, where each of them has a number of states less than five. For decomposable arrival and service MCs, it is shown how to construct steady-state queuing solutions on the basis of simple Kronecker product properties. The evaluation of each individual root is well decomposed in a simple convergent form. As an example, the author has constructed solutions for those MCs decomposed in units of heterogeneous two-state MCs. In numerical studies the significant effect of large time-varying scales of arrival/service processes on queue length distribution has been explored.>

A new concept of spectral characterization of the wideband input process in high-speed networks is examined. The eigenstructure technique, through the modeling of input Markov chains, helps localize wideband sources in a subspace, especially in a low frequency band. Simple periodic chains are used for the construction of the input rate process. The input power spectral distribution is defined in a discrete frequency domain. Each input traffic stream is characterized by an independent Markov modulated Poisson process (MMPP). The underlying Markov chain is used to reflect the time autocorrelation properties of the input process at a macro level. Expressions are derived for correlation and power spectral functions of the MMPP input. A queuing analysis with multiple periodic input functions is described. The queue response to input correlation functions is examined. The advantages of using the spectral domain to analyze and design network control and resource management are discussed.>

For pt.I see ibid., p.1464 (1991). The authors apply their folding algorithm to study various queuing phenomena related to an asynchronous transfer mode (ATM) multiplexer. They examine how the different system parameters affect the packet loss and queuing delay, and show the performance improvements by overload controls. They also analyze the queuing performance under different dynamic resource allocation policies. These analyses provide important insights for ATM design. The wide applicability of the folding algorithm is emphasized by including many practical examples, whose complexities far exceed those found in the literature. A set of highly effective approximation techniques is also proposed to further extend the folding algorithm's application range.>

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

The transient behavior of a Markov-modulated Poisson arrival queue is studied under overload control. The queue has finite or infinite buffer capacity with multiple exponential servers. A Markov-modulated Poisson process is used to represent an aggregated voice or video packet arrival process in integrated services networks. With overload control, the arrival process is properly altered once the buffer contents exceed a designated level. The probability distribution of queue length as a function of time is obtained. The temporal effect of the overload control is measured in two forms. While in overload, the amount of time for the queue to fall into underload is measured. While in underload, the amount of time for the queue to rise to overload is measured. A proper design of the control will not only reduce the fall time but also increase the rise time. The transient queuing behavior as affected by time stochastic properties of the underlying Markov chain for the arrival process is also explored.>

A study is made of the performance of trunk grouping in packet switch system design, with emphasis on the analysis of maximum throughput, input queue delay and packet loss rate. The trunk grouping technique can be implemented on both sides of the switch. In principle, the output trunk grouping relieves traffic output contentions, while the input trunk grouping proposed prevents individual input links from overloading. The study shows a significant advantage of both input and output trunk groupings in removing local congestions caused by individual links, especially in a highly nonuniform traffic environment. To implement trunk grouping, it is suggested to not designate the connection of each virtual circuit to individual links in high speed network protocol design.>

A solution for multi-media traffic queueing analysis is presented. The key properties of multi-media traffic are characterized by a great diversity in correlation and burstiness. The multi-media traffic is constructed based on various two-state Markov chains. Upon a time index normalization, the queue is modeled by a multi-dimensional discrete Markov process. The entire solution of queue length distributions is constructed. It uses a generating function approach. By matrix spectral decomposition and diagonalization, one can decompose the evaluation of each individual vanishing/non-vanishing root. It is found that all the vanishing roots must be real and all the complex non-vanishing roots can be ignored. In numerical studies, the time index normalization in source modeling is first verified, and the effect of multi-media traffic properties on ATM queues is examined.>

A general solution methodology is provided for analysis of multi-media traffic queues. An efficient algorithm for a class of quasi-birth-death (QBD) processes, which are very versatile in formulating multi-media traffic queues, is described. Based on the Markov chain reduction principle, the algorithm exploits structural property to overcome the difficulties caused by the extraordinarily large state space of the model. It is stable, accurate and efficient for handling very large-scale problems. Applications of the algorithm to analysis of multi-media traffic queues with finite buffer and multilevel overload controls are emphasized. Two continuous time QBD models are devised for the applications. Model 1 extends the finite M/M/1 queue with Markov-modulated Poisson arrivals. Model II is the Markovian version of the continuous fluid-flow model. Both queue distribution and packet loss rate are measured. The effectiveness of the algorithm is demonstrated through analysis of various design and control issues in multi-media traffic integrations.>

In dual unidirectional bus networks, packets usually occupy fixed-length slots form the sending station to the end of the network. An erasure node is a specialized station which recognizes packets which have passed their destination stations and releases the slots for subsequent use. The authors derive the optimal locations for erasure nodes and show analytically, for uniform traffic, that only several erasure nodes are needed to achieve throughput close to twice the nominal network bandwidth. The results are tested by simulation of the DQDB (distributed queue dual bus) protocol, which demonstrates a realistic improvement of 40% with only three erasure nodes. Fair access among the stations is improved as well. The authors generalize the analytic results by providing an algorithm for determining the optimal erasure node locations and the throughput improvement, given any arbitrary traffic pattern. The application of this methodology to the related problem of bridged subnetworks is briefly discussed.>

The authors study the performance of a nonblocking space-division packet switch, given that the traffic intensities at the switch not only are nonuniform but also change as a function of time. A finite-state Markov chain is used as an underlying process to govern the time variation of traffic for the entire switch. The packet arrivals at each input form an independent Bernoulli process modulated by the underlying Markov chain. The output address of each packet is independently and randomly assigned with probability distributions, which are also modulated by the Markov chain. Provided that the traffic on each output is not dominated by individual inputs the service time of each output queue for sufficiently large switches can be characterized by an independent Markov modulated phase-type process. A matrix geometric solution for the resultant quasi-birth-death type queuing process is presented. The maximum throughput is obtained at the system saturation. The performance of the switch is numerically examined under various traffic conditions. A contention priority scheme to improve the switch performance is proposed.>

The author presents a general solution using a generating function approach. The queue has multiple deterministic servers with infinite buffer size. Each server represents a time slot on an ATM link for the transmission of one cell. The arrival process is modeled by a number of independent Markov chains and each characterizes the stochastic properties of a different traffic type. By decomposing the generating function of the queue, the evaluation of the characteristic roots is separated. To characterize the great diversity of time scales of variation in multimedia traffic, the overall traffic arrivals are decomposed into multiple independent types. Each type is constructed by a number of i.i.d. two-state Markov chains and represents a different time scale of variation. Simple Kronecker product properties are then used to separate the evaluation of each individual root, so that the complexity involved to solve such a root is basically independent of the system size.>

Voice packet loss behavior at both the destination and internodal links in a packet-switched network is investigated. The fractional loss and blocking time periods for both are derived using a bivariate Markov model. The numerical results show that blocking due to the delay constraint at the destination can result in long periods of consecutive packet loss, which seriously degrade voice quality. The authors' work indicates that packets with excessive delay should be discarded at the internodal links, instead of blocking them at the destination. The relation between the internodal link buffer size and end-to-end permissible queueing delay is established.>

It is shown analytically that for uniform traffic, throughput close to twice the nominal network bandwidth may be achieved with only several erasure nodes. The optimal erasure node locations are calculated. The results are tested by simulation of the DQDB (distributed queue dual bus) protocol, yielding a realistic improvement of 40% with only three erasure nodes. Fair access among the stations is improved as well. The analytic results are generalized by providing an algorithm for determining the optimal erasure node locations and the throughput improvement, given any arbitrary traffic pattern. The application of this methodology to the related problem of bridged subnetworks is discussed.>

A generating function approach is used. The queue has multiple deterministic servers with infinite buffer size. Each server represents a time slot on an ATM link for the transmission of one cell. The arrival process is modeled by a number of independent Markov chains, and each characterizes the stochastic properties of a different traffic type. The generating function of the queue is decomposed in order to separate the evaluation of the characteristic roots. Further, to characterize the great diversity of time scales of variation in multimedia traffic, the overall traffic arrivals are decomposed into multiple independent types. Each type is constructed by a number of i.i.d. two-state Markov chains and represents a different time scale of variation. Simple Kronecker product properties are then used to separate the evaluation of each individual root. As the system size becomes large, the main computational limit in this method is the memory size required to solve linear equations for the boundary terms. Complete solutions for the first two moments of the queue are constructed. In numerical examples, calculations are made of the mean and the variance of the queue for a four-dimensional Markov queueing process. A new concept of time-scale decomposition is also introduced.>

An investigation is made of voice packet loss behavior at both the destination and internodal links in a packet switched network. The fractional loss and blocking time periods for both are derived using a bivariate Markov model. The numerical results show that blocking due to the delay constraint at the destination can result in long periods of consecutive packet loss, which seriously degrade voice quality. This work indicates that the packets with excessive delay should be discarded at the internodal links, instead of blocked at the destination. The relation between the internodal link buffer size and end-to-end permissible queuing delay is established.>

In this paper we will study the video packet loss due to excessive queueing delay in a single statistical multiplexer. Because of the real time nature of video service, packets exceeding a time constraint will be declared lost at the destination. Any packet arriving during the period when the queue length exceeds the threshold determined by the time constrain will be dropped at the destination. Thus, packet losses occur in clusters. We measure the quality of the received pictures by the expected underload period and the expected number of high priority arrivals during an overload period. The former quantity measures the frequency of packet dropping due to excessive delay, while the later is an indicator of the picture area affected. We analyze and compare two system schemes, where the first scheme drops late packets only at the destination and the second one blocks arrivals in front of the multiplexer once the packets exceed the permissible delay. Comparison of the two system schemes based on the two measurements mentioned above indicates that the second scheme is superior to the first one. In order to further improve the video service quality, a simple congestion control based on the dynamics of queue length is proposed. Our analysis shows that the proposed control scheme significantly extends the expected underload period.

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

A discrete-time queuing analysis is presented for integration of multiple traffic types in a packet-switched TDM (time-division multiplexing) system. The correlation of each traffic type is represented in terms of the power spectral density. The general expression obtained for the aggregate mean queue size indicates that slowly varying traffic types exert the largest effect on the queuing process. Also, a lengthy-steady traffic is highly predictable. An adaptive flow control and routing scheme, based on signal prediction, which successively adjusts the short-burst traffic arrival rate at each TDM node, is introduced and analyzed. The analytical results indicate a substantial reduction in the correlation effect on the system queuing behavior.>

In order to reduce the time delays as well as multiplexer memory requirements in packet voice systems, a family of congestion control schemes is proposed. They are all based on the selective discarding of packets whose loss will produce the least degradation in quality of the reconstructed voice signal. A mathematical model of the system is analyzed and queue length distributions are derived. These are used to compute performance measures, including mean waiting time and fractional packet loss. Performance curves for some typical systems are presented, and it is shown that the control procedures can achieve significant improvement over uncontrolled systems, reducing the mean waiting time and total packet loss (at transmitting and receiving ends). Congestion control with a resume level is also analyzed, showing that without increasing the fractional packet loss, the mean and variance of the queue can be reduced by selecting an appropriate resume level. The performance improvements are confirmed by the results of some informal subjective testing.>

Scheduling of voice traffic on broadcast-bus local area networks is considered. A voice scheduling scheme is proposed and evaluated. In this scheme, active voice calls are organized using a distributed global queue. Access scheduling overhead is reduced by voice packet arrival anticipation. To guarantee fairness and to reduce variance of the waiting time, the voice packet build-up during the overhead period is fairly shared among all calls by a round-robin service discipline. Three different voice packet service cases, namely nonexhaustive, exhaustive, and no-queueing, are evaluated. Simple closed-form approximation formulas have been proposed which show good agreement with simulation. The proposed scheme is shown to have performance approaching that of the centralized system.>

The performance of a nonblocking space-division packet switch is studied given that traffics are imbalanced at input and output. Analysis shows that the performance of packet queuing delay at switch input, as well as the entire throughput of the switch, can be adversely affected by such imbalances. The work is then extended to examine a transient imbalance case, where the switch experiences the alternation of two transient periods, each at a different traffic imbalance mode. The alternation is modeled by a two-state Markov chain. Both balanced and imbalanced cases can be viewed as the two extremes of the transient case. It is observed that the system throughput and the queuing performance in the transient case heavily depend on both mean sojourn time and steady-state probability at each imbalance mode.>

Once a voice buffer is full, it remains full for a certain period, during which many packets are possibly blocked, resulting in consecutive clippings in voice. The packet loss rate during this period changes slowly and has large fluctuations. It is shown that the temporal behavior of packet loss, especially at high rate, is inherently determined by voice correlation and system capacity and is independent of buffer size. Buffering may reduce the occurrence of short blocking periods associated with low rates packet loss but does not affect long ones associated with high packet loss rates. In fact, increasing the buffer size merely extends nonblocking periods, and thereby reduces the overall average packet loss rate, but packet-loss performance within existing blocking periods is not significantly improved. A simple tool is developed for calculating the boundary performance. It is found that it is possible to design a packet-switched voice system without buffering only at the expense of supporting a fewer number of calls. The issue of voice delay allocation between source and network is discussed, and it is shown that it is more effective to keep the network delay short while extending the source delay.>

An approach to the analysis of overload control in a finite buffer is introduced in which the original queuing process is modeled by a birth-and-death (BD) or quasi-birth-and-death (QBD) process. Overload control means to adapt the input process or the service process during the time period when the buffer content exceeds a certain level until it drops to another level. Such a control is necessary to reduce the occurrence of system shutdown periods and to protect high-priority messages against low-priority ones. Since the controlled process two be computed in terms of the will no longer be BD or QBD, the methodology commonly used for analyzing BD or QBD process cannot be applied. This makes direct analysis and computation of the controlled performance more complicated. The analytical methods consists in dividing the controlled process into two altering transient BD or QBD subprocesses, by observing only some selected transitions. Such a division enables the equilibrium probabilities of the controlled process to be computed in terms of the sojourn times of the two transient processes. It is shown that this is equivalent to the analysis and computation of equilibrium probabilities of the underlying stationary BD or QBD process.>

Random access scheduling schemes for broadcast-bus-type local area networks are considered. It is found that a good access scheduling scheme not only has information about the number of packets to be scheduled, but which, more importantly controls the average of this number, which can be achieved by properly choosing the scheduling interval. Furthermore, this scheduling interval is updated in such a way that adjacent intervals overlap, which by correlation gives a better estimate for the number of packets to be scheduled. The scheduling schemes developed using such concepts provide significant performance improvement over schemes using other scheduling approaches previously reported in the literature.>

An approach is presented to the analysis of overload control in a finite buffer. The author considers that the original queuing process is modeled by a birth-death (BD) or quasi-birth-death (QBD) process. By overload control, the author means to adapt the input process or the service process during the time period when the buffer content exceeds a certain level. Such control is necessary to reduce the number of system shutdown periods and to protect high-priority messages. The controlled process is no longer to be BD or QBD, which makes direct analysis and computation of the controlled performance more complicated. The analytical method is based on dividing the controlled process into two alternating transient BD or QBD subprocesses, by only observing some selected transitions. Using this method, the author finds closed-form solutions for the queue length distribution when the control is placed on any type of BD process or the M/PH/1/K and PH/M/1/K queues. As an example, this model is applied to the overload control of packet voice transmission on a TDM (time-division-multiplexed) link.>

A traffic model in which the interruption traffic is a correlated process is introduced. In this model the effect of correlation is culminated in a parameter that is the sum of all the imbalances of the autocorrelation function of the interruption process. Based on this model, the queueing analysis of integrated services on a packet switched TDM system is developed. It is shown that the presence of correlation increases the mean queue length. An adaptive flow control scheme that successively adjusts the short-bursty traffic arrival rate at each TDM node to reduce the correlation effect on the queue length build-up is proposed.>

Previous results on a single integrated-services TDM (time-division multiplexer) node are extended to the modelling and analysis of a network of integrated-service TDMs. Different interconnections of the integrated-services TDM nodes are studied by means of computer simulation. The results indicate that a Poisson assumption for the internal data arrivals is reasonable. With this assumption, the mean queue analysis at an individual node can be separated from the rest of the network, so that solution of the entire network can be obtained by combining the separate solutions.>

The authors discuss what they consider the fundamental issue of bandwidth allocation on an integrated local area network. An approach is introduced for dynamic bandwidth allocation which is based on traffic prediction concepts. It is especially well suited for real-time services such as video and voice. Using a control model two allocation schemes are proposed: the first is based on an analytical model of the traffic flow; the second is a simpler version that can be easily implemented on very high-speed systems. The results of simulation studies indicate a marked improvement in performance. The presented approach is especially effective when used in systems with large transmission path latencies as the network performance does not deteriorate with increasing latency. This is very useful if the network is to be used as a metropolitan area network.>

Voice transmission in burst switching is characterized by the process of talkspurt clipping, while in packet switching, it is characterized by the process of packet delay. In most analyses, the talkspurt clipping has been measured by the clipping probability averaged over all bits, and the packet delay has been measured by the delay performance averaged over all packets. The resulting measures overlook the duration of clipping in a talkspurt and the significant difference of delay in packets arriving at different times. Because of the nature of voice, different effects of these may result in substantially different degrees of voice distortion. This paper studies the worst case performance of both processes. The voice traffic is modeled as a process alternating between overload and underload periods. Statistically, more clipping and delay will be incurred while in the overload period. By worst case we mean that, in burst switching, we measure the worst case of talkspurt clipping duration in an overload period, while in packet switching, we measure the worst case of packet delay in an overload period. Furthermore, a simple closed form equation is derived which gives a very good approximation of the worst case mean packet delay performance. This equation can be more generally applied when the packet service time is to be geometrically distributed or when voice and data are to be integrated. The voice performances in burst switching and packet switching are also compared.

Data queueing is of primary concern in a voice/data integrated TDM system. The data queueing model is represented in the discrete-time domain with multiple servers and voice is given a higher priority than data. The data arrival process is assumed to be Poisson and the voice arrival process is characterized by a Markov chain. The correlation coefficient of the number of on voice calls between consecutive frames is used to measure the correlation behavior of the voice process. While the generating function approach may be used to analyze the queueing process, it involves the evaluation of a large number of boundary terms. On the assumption that the voice traffic consists ofNi.i.d. two-state Markov chains, we derive a simple expression for the mean queue size as a function of two variables in the form of the traffic departure processes. The results clearly reveal a significant influence of the correlation coefficient on the data queueing process. Then, an approximate analysis based on the departure processes is introduced. The numerical and simulation results indicate that this approximate approach yields reasonably accurate results.