

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


INVESTIGATION OF DELAY JITTER OF HETEROGENEOUS TRAFFIC IN BROADBAND NETWORKS By HOOI MIIN SOO Bachelor of Science in Electrical Engineering Oklahoma State University Stillwater, Oklahoma 2000 Master of Science in Electrical Engineering Oklahoma State University Stillwater, Oklahoma 2003 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY in Electrical Engineering Dec 2006 ii INVESTIGATION OF DELAY JITTER OF HETEROGENEOUS TRAFFIC IN BROADBAND NETWORKS Thesis Approved: Dr. JongMoon Chung Dr. Keith A. Teague Thesis Advisor Dean of the Graduate Collage Dr. Charles F. Bunting Dr. Weili Zhang Dr. Venkatesh Sarangan Dr. A. Gordon Emslie iii PREFACE There is a great demand for wired and wireless network architectures to support a variety of applications with very high speed communication. Nowadays, the pace of our business and social lives has created a great demand for not only instant transferring and accessing various kinds of data by a click on the mouse (i.e. digitized voice and video, file transfers, ecommerce, transactions, email, telnet, web browsing and multicast), but also for reliable and better quality of Internet service. As a result, quality of service (QoS) currently becomes an issue of concern for wide area network (WAN) telecommunications providers or backbone carriers. For instance, what is the required bandwidth for the local area network (LAN) or wide area network (WAN) to provide sufficient capacity for video transferring with desired minimum level jitter? A critical challenge for both wired and wireless networking vendors and carrier companies is to be able to accurately estimate the quality of service (QoS) that will be provided based on the network architecture, router/switch topology, and protocol applied. The variation in QoS performance based on the priority assignment is of significant importance, due to the fact that the differentiated services (DiffServ) capable networks should be able to effectively control QoS through classifying traffic according to desired service level (prioritize the data flows) and marking the packets so that the routers can recognize the prioritized packet. We need a tool to investigate whether the packet prioritization could truly reduce the delay jitter or not. iv Therefore, the main objective of this study is to provide a theoretical analysis of delay jitter, which investigates the issues of traffic jitter characteristic in the homogenous wireless communication and heterogeneous wired networks deploying different priority scheduling algorithms. Although simulation can be a powerful tool, an engineer must understand the mathematical model underlying each program model to be applied correctly. In addition, one may not afford an extensive simulation, which requires an extensive data mining process. On the other hand, a mathematical formula is much easier to use compared to using a simulation model. Thus, the efficient way is to use a simulation tool in combination with a probably less realistic mathematical/analytic model. Plan of this thesis This thesis is organized as follows. In Chapter 1, an overview of this thesis is provided, which states why the proposed methodology is important and how it may contribute to designing and planning of internetworking system. Literature review on WAN networks and Internet traffic is given in Chapter 2, where the challenge of the heterogeneous traffic modeling compared to the homogeneous traffic modeling is discussed. The understanding of the WAN networks characteristics is needed to construct the analytic model. Chapter 3 provides mathematical derivations for the perclass jitter characteristic of a wireless network with automatic repeat request (ARQ) error control and headofline (HOL) priority scheduling. The derivations provide a direct method to analyze/evaluate the perclass jitter based on the DiffServ network and protocol parameters. In Chapter 4, the Gaussian traffic modeling combining with Maximum v Variance Approach to conduct the queue length analysis, which further apply in heterogeneous traffic jitter analysis of multiple priority queues.. The conclusion of this thesis is in Chapter 5, which summarizes the essential elements in order to provide guidelines for network designers trying to meet engineering specifications of performance deliverables. The references list is provided in Reference section. The main contributions of this dissertation are as follow: 1. Chapter 3 • Derive mathematical equations, which to be able to provide a mathematical tool to analyze the homogeneous traffic in wireless networks with adequate accuracy. • Propose a call admission control (CAC) scheme to improve the jitter performance. 2. Chapter 4 • Derive mathematical equations, which to be able to provide mathematical tool to analyze the heterogeneous traffic in wired broadband networks with adequate accuracy. Simulation is done to show the accuracy of the mathematical model. • Propose an adaptive distortionreducing peak outputrate enforcing (APORE) scheme to control/improve the jitter performance. vi ACKNOWLEDGMENTS First, I wish to express my heartfelt thanks to my major advisor, Dr. JongMoon Chung, for his encouragement, guidance, valuable discussions and advice throughout this work. I extend my sincere appreciation to my other committee members Dr. Weili Zhang, Dr. Charles F. Bunting and Dr. Venkatesh Sarangan, for their guidance. I extend my genuine gratitude to Dr. Keith A. Teague for serving as my dissertation defense chair. I wish to express my special appreciation to my family, my parent, for their unlimited and continuing love, encouragement, support and sacrifice. Moreover, I am sincerely thankful to my husband, Mr. Lee who has been always wonderfully encouraging me through out this work. Without them, I would not have come this far. Last but not the least, I would like to thank all that have assisting me in accomplishing this work. vii TABLE OF CONTENTS Chapter Page Chapter 1............................................................................................................................. 1 1.1 Overview............................................................................................................... 1 1.2 Delay Jitter Analysis Methodology ...................................................................... 6 1.3 Queueing and Teletraffic Theory Applied in HighSpeed Wide Area Networks (WANs) with Heterogeneous Type Traffic ................................................................ 8 1.4 Approximations for the Queue Length Distribution Gaussian Model for Broadband Traffic..................................................................................................... 15 1.4.1 SingleAsymptotic Upper Bound ................................................................... 16 1.4.2 Maximum Variance Asymptotic (MVA)........................................................ 17 1.4.3 MVA Lower Bound ....................................................................................... 18 1.4.4 MVA Upper Bound ....................................................................................... 18 1.4.5 MVA general approach (not bound) .............................................................. 19 1.4.6 Long Range Dependent Gaussian model: The Discrete Gaussian Model ...... 20 1.4.7 The Continuous Gaussian Model.................................................................... 21 1.4.8 Large twostage models: Heavy Traffic ......................................................... 22 Chapter 2........................................................................................................................... 23 2.1 Introduction: Analyzing traffic traces................................................................. 23 2.2 Aggregated Variance Method............................................................................. 23 2.2.1 Description and Methodology ......................................................................... 23 2.2.1 Simulation Results .......................................................................................... 26 2.2.3 Simulation Flow Chart..................................................................................... 28 2.3 R/S Method ......................................................................................................... 29 2.3.1 Description and Methodology ......................................................................... 29 2.3.2 Simulation Results ........................................................................................... 30 2.3.3 Simulation Flow Chart..................................................................................... 32 2.4 Estimating the Hurst Exponent using Wavelet Spectral Density ....................... 33 2.4.1 Description and Methodology ......................................................................... 33 2.4.2 Simulation Results ........................................................................................... 35 2.4.3 Simulation Flow Chart..................................................................................... 36 2.5 Observation and Discussion................................................................................ 37 Chapter 3........................................................................................................................... 39 3.1 Abstract............................................................................................................... 39 3.2 Introduction......................................................................................................... 39 3.3 Analytical Model ................................................................................................ 40 3.3.1 Network and System Model Assumptions....................................................... 40 viii 3.3.2 Theoretical Formulations................................................................................. 42 3.3.3 Jitter Analysis with NonPriority ARQ Traffic ............................................... 45 3.3.4 Jitter Analysis with Priority ARQ Traffic........................................................ 46 3.4 Discussions and Conclusions.............................................................................. 49 Chapter 4........................................................................................................................... 51 4.1 Introduction......................................................................................................... 53 4.2 Discrete Time Fluid Queue Model and Extreme Value [26].............................. 55 4.3 Jitter Analysis of Heterogeneous Traffic Networks ........................................... 65 4.3.1 Simulation and Numerical Study..................................................................... 67 4.4 Jitter Analysis of Heterogeneous Traffic Networks with Differentiated Services ………………………………………………………………………………..72 4.4.1 Simulation and Numerical Study..................................................................... 78 Chapter 5........................................................................................................................... 81 Conclusions…………………………………………………………………………81 Reference ………………………………………………………………………………...83 ix LIST OF FIGURES Figure Page Fig. 1.1 The actual Ethernet traffic trace in original time scale (time unit = 1ms)........... 13 Fig. 1.2 The Ethernet traffic trace is aggregated 10 folds (time unit = 0.01s).................. 13 Fig. 1.3 Original Ethernet traffic...................................................................................... 14 Fig. 1.4 Aggregated 100 Ethernet traffic flows. ............................................................... 14 Fig. 2.1 The relationship between aggregated variance equation and the least squares line. .................................................................................................................................. 25 Fig 2.2 This figure shows that Ethernet traffic is very selfsimilar, which is indicated by a fairly large H value................................................................................................. 27 Fig 2.3 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. ............................................................... 27 Fig 2.4 This figure shows that the data set is selfsimilar, and the level of selfsimilarity is indicated by the H value. Here, K = 10 and upto log10(d)=3.4 is used. ................ 31 Fig 2.5 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. K=10 and up to log10(d)=3.4 is used..... 31 Fig 2.6 The figure shows that Ethernet traffic is selfsimilar, and the level of selfsimilarity is indicated by the H value. ...................................................................... 35 Fig 2.7 The figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. ............................................................... 35 Fig 2.8 The comparison between the three methods is shown, where the level of selfsimilarity is indicated by the H value. The estimation range is between (0.82, 0.93) for Ethernet traffic for low m aggregated level, where all the three methods have proved that the Ethernet traffic is very selfsimilar. ................................................. 38 Fig. 3.1 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 10%. The solid line represents the nonpriority ARQ scheme, and the dotted line represents the priority ARQ scheme. ........................... 47 Fig. 3.2 Comparison between wireless networks nonpriority ARQ scheme with Pe = 20%. .......................................................................................................................... 48 Fig. 3.3 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 1% and 10% for class 1 through class 5............................ 48 Fig. 4.1 Plot of variance of Zm versus m. The variance reaches a maximum value and then begins to converge to 0. The parameters used are q=1000, μ=0.61, N=100, each individual arrival process with mean s X = 10 cells/sec, and autocovariance l Cs l e ( ) = 100 −0.04 ....................................................................................................... 64 x Fig. 4.2 Comparison between the approximation equation and the simulation results of the jitter distribution for utilization of 50% and 90% with 95% CI, for the case of T = 10. .......................................................................................................................... 70 Fig. 4.3 Distribution of jitter for the comparison between utilization of 50% and 70%, and for the comparison between T = 10 and 20............................................................... 71 Fig. 4.4 Distribution of jitter for utilization of 60%, T=10, and various Amin values with 95% CI, and T = 10................................................................................................... 79 xi LIST OF FLOWCHARTS Figure Page Flowchart 1 The simulation algorithm used to calculate delay jitter at a multiplexer ……………………………………………………….... 70 1 Chapter 1 Introduction 1.1 Overview Delay jitter is one of the most important parameters in quality of service (QoS) that indicates the level of variation of traffic services of realtime data transfer. In realtime wired/wireless data communication, delay jitter is defined as the difference in time delay of the arrival at the destination that each transmitted packet experiences commonly, which is also simply referred to as jitter. Delay jitter has been successfully analyzed for the performance of asynchronous transfer mode (ATM) network applications, in order to accurately estimate the quality of service (QoS) in terms of jitter that will be provided based on the network architecture, router/switch topology, and protocol applied. Several papers [2], [3], [4], and [5] have successfully analyzed the performance of the delay jitter in order to be more easily, consistently, and effectively implemented in various ATM network applications. In [2], the analysis of delay jitter was conducted on voice traffic using an exponential On/Off source in cellular wireless ATM network. In [3], the jitter bound for various classes of constant bit rate (CBR) traffic is analyzed, where the performance bound is used in the call/connection admission control (CAC) 2 mechanism. The multiple access control topology applied in [3] is based on a nonpreemptive priority polling scheme [4]. The papers of [6], [7], and [8] address delay jitter for more general type of wireless networks, rather than ATM. In [6], the time division multiple access (TDMA)/time division duplex (TDD) scheduling scheme is used. In [7], jitter is analyzed for mobile ad hoc networks (MANET) based on the ad hoc ondemand distance vector (AODV) routing protocol, where the authors propose a novel handover mechanism. Both [6] and [7] provide results on jitter performance analysis based on computer simulation for the wireless network models. In [8], the authors provide a jitter analysis on wireless networks involving automatic retransmission request (ARQ) error recovery, where the delay jitter is calculated using the windowlength generating function and the numerical results are verified through simulation. In [9], the jitter of homogeneous traffic in reference to the different priority classes has been analyzed. The delay jitter research of [9] extends the results of [1] and [10] for DiffServ networks, but all three papers do not consider the channel error probability or the ARQ error control scheme, which makes the results difficult to apply to wireless networking applications. Therefore, Chapter 3 the mathematical derivations to analyze the delay jitter performance of homogenous wireless networks that apply ARQ error recovery with time constraints have been developed, which resulted in [11]. In [11], we attempt to provide a novel analysis of the perclass jitter performance of DiffServ networks based on wireless channels that experience packet errors, assuming a nonpreemptive headoftheline (HOL) priority scheme. The derivations provide a direct method to analyze/evaluate the perclass jitter based on the DiffServ network, retransmission time constraints, and network packet error parameters 3 [12]. In addition, we evaluated the effects on the delay jitter in reference to the priority control scheme of the ARQ traffic for the two cases of: 1) the ARQ traffic has a priority over the original transmission traffic; and 2) the ARQ traffic has no priority over the original transmission traffic. As the next step, this homogenous jitter study is extended to heterogeneous wired and wireless network jitter analysis by deriving a general approach, which is going to be covered in this dissertation. In general, WAN traffic is often characterized by a diverse mix of heterogeneous data streams (e.g., multimedia, digitized voice, Internet, video, teleconferencing and many newly evolved applications), the periodicity of the individual streams is different from each other. In other words, in the heterogeneous environment, the input traffic streams are a superposition of data packet streams from different data sources with different periods. To further investigate heterogeneous jitter characteristics, first, a study is conducted on wired networks, and then the focus will be extended to wireless networks, which requires a longer time period due to its complexity. The studies that have been conducted and completed (but not limited to) in this dissertation are as follows: • Various possible traffic modeling techniques have been investigated • Diverse statistical properties of heterogeneous wireless networks is evaluated. • The traffic modeling combined with heterogeneous jitter analysis. Traffic analysis can assist one in developing a good traffic model for analyzing the jitter characteristic of heterogeneous wireless networks, where the results could serve as a tool to aid the network engineers and developers in wireless and wired network planning and architecture structuring. 4 The models, such as Markov Modulated Poisson Process (MMPP) and M/M/1/B have been applied in wireless network traffic modeling. In wired or wireless networks, the Poisson arrival may not be an appropriate model since actual networks traffic is very bursty in nature due to its longrange dependency (LRD) and selfsimilar characteristics. Numerous studies have found that aggregated traffic at a node (router, switch for wired networks case) or base station (for wireless networks case) exhibit LRD, and such traffic can be very bursty. Thus, many broadband traffic studies have evolved around Gaussian, and they show that Gaussian models indeed provide a good approximation to networks traffic if the aggregated traffic is sufficiently large [13],[14]. Hence, heterogeneous wireless network traffic processes can be modeled as a Gaussian process, where some of these models have been discussed in Chapter 4. In extension of the MVA approach, we can derive the MVA lower bound and upper bound to provide a boundary conditions on the traffic. Another popular approach in traffic modeling is by using Fractional Gaussian Noise (fGN), which is a stationary Gaussian process with LRD. Recent research [15][16][17] models the heterogeneous networks traffic in the wavelet domain, where selfsimilar traffic exhibits longrangedependent (LRD) correlations and nonGaussian marginal distribution [15]; it shows that the aggregated traffic can be decomposed into those two groups [15]. In conclusion, the following is the summary of the work conducted in this dissertation: 1. Investigate the characteristics of the wireless networks that applying retransmission request (ARQ) with homogeneous type traffic. 5 2. Investigate the issues of traffic jitter characteristic in heterogeneous wired communication networks deploying different scheduling algorithms. 3. The emphasis of this dissertation is to investigate the various possible traffic modeling techniques and evaluate the challenges in characterizing the diverse statistical properties of heterogeneous wireless networks. 4. Apply the Gaussian traffic modeling using MVA approach to conduct the queue length analysis, which will be further used in heterogeneous jitter analysis. 5. Analyze the difference between jitter probability of multiple priority queues and servers. The contributions of this dissertation are as follow: 1. Evaluate the characteristics of the wireless networks that applying retransmission request (ARQ) with homogeneous type traffic. 2. Evaluate the characteristics of the diverse statistical properties of wired networks with heterogeneous type traffic. 3. Investigate various possible traffic modeling techniques. 4. Apply the Gaussian traffic modeling using the MVA approach to analyze the queue length, and further generalize the heterogeneous jitter analysis. 5. Analyze the jitter process and the jitter probability distribution of multi priority class traffic. 6. Propose a scheme to control and improve networks performance in term of jitter. In order to do these, we have to first: • Study the traffic characteristics • Investigate the traffic modeling techniques 6 Then, we’ll be able to analyze the jitter process, and propose a scheme to control it. 1.2 Delay Jitter Analysis Methodology In realtime wired or wireless communications, each transmitted packet may experience a different time delay during arrival at the destination. This variation in delay is often referred to as delay jitter or simply jitter. For instance, let dn represent the packet transmission delay experienced by the nth packet from a tagged stream. Thus, the process of delay jitter between the nth and (n+1)th packet of a tagged stream with respect to data stream original period (interdeparture time between nth and (n+1)th packets transmitted from the source), T, is J n = dn − dn ∀n + , ~ 1 . (1.1) In the steadystate limit n dn = dn =∞ +1 lim , therefore jitter is a zero mean random sequence. Another interpretation of jitter is that it represents the difference in waiting times experienced by successive packets. Hence, we can relate the transmission delay and the queue length (number of packets) ahead of the tagged packet (i.e., n Q represents the number of customers ahead of the nth tagged packet). Let any customer’s service time be equal to one slot and follows firstinfirstout (FIFO) order, Qn = dn (in time slot units). Therefore, (1.1) implies that ~ , 1, 2,... 1 = − = J n Qn+ Qn n . (1.2) To prove this, let the variable n Q denote the number of customers, regardless of their class affiliation, that are waiting for service just ahead of the arrival of nth packet of the reference user. Thus, the nth packet of the reference user begins to enter service at time 7 n n n τ = t + Q . (1.3) Hence, ( ) ( ) ( ) 1 1 1 J t t Q Q T Q n n n n n n n n = − = − + − = + Δ + + + τ τ . (1.4) The normalized jitter with respect to the original data stream period (interdeparture time between nth and (n+1)th packets transmitted from the source), T can be expressed as:: J~n = J n − T = ΔQ(n), n =1, 2,... , where n n def ΔQ n = Q − Q ( ) +1 . (1.5) From (1.5), we can observe the study of jitter can be equivalently changed to the study of the queue size variation ΔQ(n) of pcustomer arrivals, which is the methodology that is going to be applied in this study. We want to find the pmf (probability mass function) of J n ~ , i.e., {~ } f J n , from the queue length distribution f {Qn} . A discretetime approach is used in the delay analysis, where time is slotted. It is assumed that the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. Next, the various traffic modeling techniques are discussed. First, let’s denote the heterogeneous network of steady state queue length distribution as the probability of queue size larger than x, i.e., P(Q > x) . Here, the input traffic at a highspeed multiplexer is characterized by a Gaussian process. Hence, the central limit theorem is applied to the traffic process. In highspeed networks, homogenous (i.i.d) and heterogeneous sources (independent but not identically distributed) are multiplexed at the multiplexer. Here, we are concerned about the delay jitter characteristic in heterogeneous traffic since real network traffic consists of multimedia traffic, which is a mixture of CBR voice, CBR video, real time VBR video, real time VBR voice, time critical data and nontime critical data. In networks, traffic management controls are on the level of traffic aggregates, and 8 not for individual links. Therefore, even though each link is not normally distributed, the aggregated traffic distribution shows Gaussian characteristics. This can be verified by applying the Central Limit Theorem (CLT) that states that summing a large numbers of independent variables with finite variance will converge or weakly converge to a Gaussian random density [22]. The tail of the queue length distribution ( P(Q > x) ) at highspeed multiplexer can be approximated under a variety of Cramer type assumptions (exponentially bounded marginal and autocorrelations of the arrival process). Thus, P(Q > x) of an infinite buffer is asymptotically exponential [26], P(Q > x) ~ Ce−ηx , (1.6) where the positive constant η is called the asymptotic decay rate, and the positive constant C is called the asymptotic constant, in which (1.6) is suggested for large values of x [2530]. In section 1.4, the discussion of some popular approaches to find the queue length distribution by applying Gaussian/Normal process is provided. 1.3 Queueing and Teletraffic Theory Applied in HighSpeed Wide Area Networks (WANs) with Heterogeneous Type Traffic Due to the fast growth of telecommunication technology over the last past ten years (based on demands for better mobile telephony and Internet services) there have been many studies on traffic behavior and network architechture. Hence, traffic modeling is one of the key issues in traffic engineering for efficient designing and controlling of 9 networks, where a mathematical model analysis of a complex system yields useful information. Here, Queueing theory and Teletraffic theory are applied as a tool for traffic modeling. Queueing theory concerns the usage of a network resource for which the demands are random. When the resource is not available to the users, the requested service demand is queued or declined. While Teletraffic theory is a branch of engineering mathematics that relies heavily (but not solely on) queueing theory, it can be viewed commonly as queueing theory applied for telecommunication systems. It is applied for evaluating network designs, performance, stability and routing protocols, and optimizing network resources through mathematical analysis and simulation. Hence, the following topics are essential in traffic modeling for networks: • Characterization of Internet traffic • Longrange dependent traffic models (LRD) • Heavytailed distribution traffic models • Gaussian traffic models • Effective bandwidth model • Traffic models for mobile networks • Traffic measurements • Traffic estimation and prediction Poisson modeling fails to properly characterize multiplexed network traffic, due to the fact that Internet and Wide Area Network (WAN) traffic is selfsimilar. The Poisson traffic model severely underestimates burstiness especially when traffic flows multiplex/aggregate. The selfsimilar characteristic can be analyzed using statistical 10 analytic tools, and the most popular methods are R/S plot, VarianceTime plot, Wavelet method, Periodogram method, and Whittle estimator. The several traffic models that are being proposed are Pareto On/Off model, M/G/∞ input model (infinite source Poisson model with heavytailed service/processing time), Fractional Brownian Motion (fBm), Fractional AutoRegressive Integrated Moving Average (ARIMA) process, which capture the heavytailed characteristic (burstiness) of selfsimilar traffic. Here, the Hurst parameter (H) is the measure of burstiness. Discretetime definition of selfsimilarity is a stationary times processes X, and we define the maggregated time series X (m) = {X (m) (k), k = 0,1,2,L} and X (m) (k) by averaging the original times series X over a nonoverlapping block of size m, which is given in (1). Thus, a process X is said to be selfsimilar with parameter β (0 <β <1) if for all m = 1, 2, … we have the following definitions: Exactly secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (1.7) Autocorrelation: ( ) ( ) ( ) R k R k X m X = . Asymptotically secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (1.8) Autocorrelation: ( ) ( ) ( ) R k R k X m X → as m →∞ . Eq. (1.7) and (1.8) define that selfsimilarity characteristic exists as the autocorrelation of the aggregated process has the same form as the original process, where the degree of variability or burstiness at different time scales will be the same. Fig. 1.1 and 1.2 show a graphical representation of selfsimilarity, where we can see that the networks traffic is very bursty and selfsimilar across all time scales. That is Fig. 1.1 and Fig. 1.2 look 11 similar to one another in a distribution sense, all of the plots involve a fair amount of burtiness. The traffic pattern in Fig. 1.2, which sampled at large scale (the data are aggregated over 10 folds time scale, i.e., from 1ms to 0.01s) does not smooth out. Thus, the other models such as Markov Modulated Poisson Process (MMPP) and M/M/1/B that can be applied in wireless network traffic modeling may not be a good fit. In wired or wireless networks, the Poisson arrival may not be an appropriate model since the networks traffic is very bursty in nature due to its longrange dependency (LRD) and selfsimilarity characteristics. Numerous studies have found that aggregated traffic at a node (router, switch for wired networks case) or base station (for wireless networks case) exhibit LRD, and such traffic are very bursty. Thus, many broadband traffic studies have evolved around Gaussian, and they show that Gaussian models indeed provide a good approximation to network traffic if the aggregated traffic is sufficiently large [13][14]. Hence, heterogeneous wireless network traffic processes can be modeled as a Gaussian process, where some of these models will be discussed in section 1.4. In extension of the MVA approach, we can derive the MVA Lower Bound and Upper Bound to provide a boundary condition on the traffic. Another popular approach in traffic modeling is by using Fractional Gaussian Noise (fGN), which is a stationary Gaussian process with LRD. Recent research [1517] models the heterogeneous networks traffic in the wavelet domain, where selfsimilar traffic exhibits longrangedependent (LRD) correlation and a nonGaussian marginal distribution [15]. In recent years, the emerging Gaussian model is believed to be the possible model for highspeed networks, where traffic flows in the networks are highly 12 multiplexed. The Gaussian model can be LRD by including H in the modeling process. The main reasons to consider Gaussian traffic modeling are Central Limit Theorem (CLT) and the Functional Central Limit Theorem (FCLT) [18]. As the network grows, the number of multiplexed/aggregated traffic flows at a node (e.g., router, switch) increase, and the shape of traffic distribution will become closer and closer to Gaussian [19][20]. The aggregated input traffic queueing processes will weakly converge to a Gaussian process [19][20], which is shown in Fig. 1.3 and 1.4. These two plots display a normal probability plot of the data, where if the data does come from a normal distribution, the plot will appear linear. As the traffic flows aggregate, the traffic becomes closer and closer to a Gaussian process, which illustrated in Fig. 1.4. The aggregated traffic is just as bursty as before, where it has the exactly same Hurst parameter H, but it is smoother [21]. Let a traffic process denotes as X, the aggregate of L independent copies of X is X ⊕L [21]. To demonstrate this, Fig. 1.4 shows the trace of aggregated process (byte.txt, a data set provided at Murad S. Taqqu’s website is used; the data is splitting up into nonoverlapping blocks, and then looking at the aggregation of two or more of those blocks). 13 Fig. 1.1 The actual Ethernet traffic trace in original time scale (time unit = 1ms). Fig. 1.2 The Ethernet traffic trace is aggregated 10 folds (time unit = 0.01s). 14 Fig. 1.3 Original Ethernet traffic. Fig. 1.4 Aggregated 100 Ethernet traffic flows. 15 1.4 Approximations for the Queue Length Distribution Gaussian Model for Broadband Traffic In highspeed networks, the aggregated traffic becomes close to Gaussian characteristic by applying Central Limit Theorem (CLT) that stated that summing a large number of independent variables with finite variance is going to converge or weakly converge to a Gaussian random variable [22]. The Gaussian model is useful for two main reasons. First, any stationary Gaussian process can be completely characterized by its mean and autocovariance. Second, the highspeed networks of today are highly complex and traffic is usually the superposition of some thousand network applications. By applying CLT, the aggregated traffic can be modeled as a Gaussian process; even though each single independent data source does not follow a Gaussian distribution. The only defect in this model is that there is a positive probability of a negative quantity of arriving traffic, which is impossible in real traffic. This significant weakness is counterbalanced by the fact that the CLT appeals as more and more traffic streams are aggregated to share a link, traffic becomes more Gaussian, and the case that the amount of negative traffic reduces as traffic is aggregated [24]. Many broadband traffic studies have evolved around Gaussian, and they show that Gaussian models indeed provide a good approximation to network traffic if the aggregated traffic is sufficiently large. In [22], [23], and [24], results show that the Gaussian traffic models could be the precise tool for analyzing the highspeed networks. Moreover, the Gaussian model is also a good fit for highspeed networks with 16 differentiated services (DiffServ). In differentiated services networks, traffic management controls are on the level of traffic aggregates, and not for individual links [23]. The input traffic at a highspeed multiplexer can be characterized by Gaussian processes. Thus, the tail of the queue length distribution ( P(Q > x) ) at highspeed multiplexer can be approximated under a variety of Cramer type assumptions (exponentially bounded marginal and autocorrelations of the arrival process). Thus, P(Q > x) of an infinite buffer is asymptotically exponential [26], P(Q > x) ~ Ce−ηx , (1.9) where the positive constant η is called the asymptotic decay rate, and the positive constant C is called the asymptotic constant. Equation (1.9) is suggested for large values of x [25][27][28][29][30]. 1.4.1 SingleAsymptotic Upper Bound [25] The singleasymptotic upper bound can be represented as ⎥⎦ ⎤ ⎢⎣ ⎡ ⎟⎠ ⎞ ⎜⎝ ⎛ + ⎟⎠ ⎞ ⎜⎝ > ≤ − ⎛ S x kD S P(Q x) exp 2k (1.10) where k, S, and D are defined by the first two moments of a single Gaussian input process and the service rate μ per input, Σ∞ = = 1 : 2 ( ) l D lCγ l [25]. TheCγ (l) denotes the autocovariance function of a stationary Gaussian net input processγ n =λn − μ , where γ n =λn − μ is the net amount of fluid input at time n and (x)+ := max{0, x} [25]. Since the mean and autocovariance function of X n can be computed in term of 17 k := −E{ 0} and C (l) as E{X n ) = −kn, γ γ and Σ Σ = = = 2 − 2 1 1 2 1 1 1 2 1 ( , ) ( ) n l n X l C n n C l l γ by a change of variable l = l2 − l1 , the variance can be expressed as a weighted sum of Cγ (l) , i.e., Σ = = + 1 1 Var{ } (0) 2 ( ) ( ) nn γ l γ X nC nl C l [25]. 1.4.2 Maximum Variance Asymptotic (MVA)[25][26] For a discretetime fluid queue, the amount of fluid in the buffer is denoted by Qn , which can be defined using Lindley’s equation [25]: + − Qn = (Qn 1 +γ n ) (1.11) where γ n =λn − μ is the net amount of fluid input at time n less the capacity μ , and (x)+ := max{0, x} [25]. Let X n represents a stochastic process {X : n = 0,1,2,L} n defined by Σ = − = n X n m m 1 : γ , the backward accumulation process (Note that the first two moment of X n is defined as above in SingleAsymptotic Upper Bound section). Assume stationary and ergodicity of γ n , and the stability condition, i.e., E{γ n}< 0 , the distribution of Qn converges to a steadystate queue distribution. Hence, the aggregate arrival process, λn , can be characterized by a stationary Gaussian process. Thus, the steadystate queue length distribution can be represented as P Q x P(X n x) n > = > ≥0 ( ) sup . (1.12) The function P(X n > x)achieves its maximum at a finite value of n nx = ) : P Q x P(X x) nx ( > ) = ) > (1.13) 18 where in a Gaussian process, the time scale nx ) is also the time at which 2 σ x,n achieves its maximum value 2 σ x . 1.4.3 MVA Lower Bound [25] By studying the asymptotic behavior of P(Q > x) , and with α =1 corresponding to the lower bound, (for a Gaussian process) the lower bound of P(Q > x) can be written in terms of ∫∞ = − z ψ (z) : 1 2π exp[ ( y 2 / 2)]dy (the tail function of the standard Gaussian distribution) as ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ > ≥ 2 ( ) x P Q x x σ ψ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − 2 2 2 exp 2 ~ x x x πx σ σ . (1.14) 1.4.4 MVA Upper Bound [25] The approach is to find a function of 2 z = x σ x , which resembles ψ (z) such that is similar to the asymptotic upper bound (1.11), ψ (z) = exp[−(z 2 / 2)] . (1.15) 19 1.4.5 MVA general approach (not bound) [26] In discrete time queue, the extreme value distribution of X n is determined by determining the extreme value distribution of a new stochastic process n Z , {Z : n = 0,1,2,L} n , which is defined as ((1 ) ) (1 ) n k X n Z n n − + − − = μ ρ μ ρ (1.16) where n Z is a normal process with E{Zn} = 0 , and 2 ((1 ) )2 Var{ } Var{ } n k X Z n n − + = μ ρ . (1.17) Thus, the steadystate queue distribution can be rewritten as [26] P Q x P(X n x) n > = > ≥0 ( ) sup sup ( 1) 0 = > ≥ n n P Z . (1.18) The Var{Zn} achieves its maximum value for n = nˆx [26] sup ( ) ( ˆ ) 0 P Zn u P Zn u n > ≈ > ≥ (1.19) for sufficiently large u. If Var{Zn}<<1 , then by using the approximation in (1.19) to obtain [26] P(Q > x) ≈ P(Znˆ >1). (1.20) Thus, the tail probability P(Q > x) can be defined as ( ) ∫∞ ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ > ≈ > = − max 1 2 ˆ 2 exp 2 ( ) 1 1 σ π P Q x P Zn x dx (1.21) 20 where σ max is the maximum value of Var{Zn} , which can be computed by determining the maximum value of Var{Zn} , 2 2 1 1 ((1 ) ) 0 2 Var{ } n k nC ( ) (nl)C (l) Z nγ l γ n − + + = Σ = μ ρ . (1.22) 1.4.6 Long Range Dependent Gaussian model [27] [32]: The Discrete Gaussian Model Assume a FIFO single server queue, and the time is divided into fixedlength sampling intervals (discrete time). The arrival process is considered to be stationary and ergodic, and Gaussian distributed. A discrete time queueing system has k statistically independent, but identical, traffic streams aggregated at a multiplexer. Let time be divided into fixedlength sampling intervals [28]. The amount of queued traffic in a buffer at time n is defined asVn , with standard deviation σ, and net input rate m. H is the Hurst parameter of the input traffic [27]. Under the longrange dependent (LRD) case, the overflow probability (unfinished work distribution) for a Gaussian fractal queue can be approximated by [13][19][22][27][32], ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − > ≈ − × − × − − − − ∞ H H t H m P V t m H H 2 2 2 2 2  (1 )  { } 2 ( , ) exp 2 1  σ ψ σ σ π (1.23) where H is the Hurst parameter of the traffic, Vn denotes the amount of queued traffic in a buffer at time n, σ is the standard deviation of the arriving traffic, m is the net input rate to the buffer (which has to be negative for stability) [13][19][22][27][32]. The function ψ (−m,σ ) represents the mean of the random variable that is normally distributed with mean –m and standard deviation σ [13][19][22][27][32], 21 . 2 2 2 ( , ) 2 2 2 ⎟⎠ ⎞ ⎜⎝ ⎛ = − − π σ σ ψ σ σ m e m erfc m m (1.24) 1.4.7 The Continuous Gaussian Model A superposition of independent Gaussian processes is still a Gaussian processes. Assume FIFO with single server queue. Let us define the cumulative arrival processes of class i, which are independent continuous Gaussian processes with stationary increments, as { } {i} i t i t A = m t + Z [14][27]. The mean input rate is mi and Z{i} is a centered continuous Gaussian process with variance ( ) Var {i} i t v t = Z [14][27]. The server capacity is denoted as c, and the queue with input A{i} is denoted as Q{i} [14][27]. Applying the path space of the Gaussian processes, reproducing kernel Hilbert space, and based on the estimate of the buffer emptiness probability, the lower bound for the aggregated queue distribution can be derived using the 1dimensional normal distribution as [27] ( ) ⎟⎠ ⎞ ⎜⎝ ⎛ − − ≥ ≥ ≥ Σ= − x k i i k t P Q k x P A x c m t x ( ) 1 {1, , } {1, , } 0 K K ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − = Σ Σ = = k i i x x k i i v t c m t 1 1 ( ) ( ) φ (1.25) where < 0 x t is the value of t which minimize the expression [14][27] 22 . ( ) ( ( )( )) 1 2 1 Σ Σ = = + − − k i i k i i v t x c m t (1.26) 1.4.8 Large twostage models: Heavy Traffic Let the arrival rate be λ > 0 , service rate μ > 0 , and offered load m = λ μ . Assume the arrival process is asymptotically normal. Let l N be a stationary number of customers in the system that has l channels. Then N is approximately normal with mean m and variance mz when m is large. The distribution of l N can be obtained as [chapter 7 of 33] ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − ≈ mz i m mz P(N (i)) (1 mz )ϕ i m φ l , (1.27) where ϕ is the standard normal density function, and φ is the standard normal distribution [chapter 1 of 33] exp( ( )2 / 2 2 ) 2 ( ) 1 μ σ σ π ϕ x = − x − . (1.28) In this chapter, the motivations of studying the jitter process and its concept have been discussed. The selfsimilarity characteristic of broadband networks traffic have also been studied. Then, several popular traffic modeling techniques for modeling the networks with heterogeneous type traffic have been investigated. In the next chapter, the methods used for determining the selfsimilarity of a network are being examined. 23 Chapter 2 Wide Area Networks and Internet Traffic Analysis 2.1 Introduction: Analyzing traffic traces The statistical analysis is applied to a set of collected data, and then a statistical inference of the data set is made. Here, we are interested in traffic selfsimilarity, which is measured by the Hurst parameter. The methods used to estimate the traffic selfsimilarity by computing the Hurst parameter (H) are: 1. Aggregated Variance 2. R/S Analysis 3. Wavelet Estimate 2.2 Aggregated Variance Method 2.2.1 Description and Methodology Aggregated variance method is also referred to as variancetime analysis. • For each m = 1, 2, 3, …, data is divided into nonoverlapping blocks of size m to obtain the aggregated process X (m) . For instance, if the given input data set has length N: X i k N m m X k km i k m m ( ) 1 ( ), 1,2, , / ( 1) 1 ( ) Σ = − + = = K . (2.1) 24 • For the variance vs. time loglog plot, the variance is first normalized to the corresponding sample variance (Thus, the estimate βˆ of the asymptotic slope will fall between –1 and 0, which suggests selfsimilarity). Then, we need to plot log10(var( X (m) )) versus log10(m). The variance is computed as ( ) Σ= = − N m k m X m k X N m X 1 var( ( ) ) 1 ( ) ( ) 2 . ) (2.2) Recall: The discretetime definition of selfsimilarity is a stationary times X, and we define the maggregated time series X (m) = {X (m) (k), k = 0,1,2,L} and X (m) (k) by averaging the original times series X over nonoverlapping block of size m, which is given in (2.1). Thus, a process X is said to be selfsimilar with parameter β (0 <β <1) if for all m = 1, 2, … we have the following: Exactly secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (2.3.a) Autocorrelation: ( ) ( ) ( ) R k R k X m X = . Asymptotically secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (2.3.b) Autocorrelation: ( ) ( ) ( ) R k R k X m X → as m →∞ . (2.3.a) and (2.3.b) define that selfsimilarity characteristic exists as the autocorrelation of the aggregated process has the same form as the original process, where the degree of variability or burstiness at different time scales will be the same. 25 Simple Least Squares Line Fitting: Now, by taking log10 on both sides of the variance in (2.3): X m [ X ] [m] 10 10 ( ) 10 log [var( )] = log var( ) −β log , and it can be rewritten as log [var( )] log [ ] log [var( )] 10 10 ( ) 10 X m = −β m + X (2.4) and var(X ) =σ 2 is a positive finite constant. Equation (2.4) can be fitted through a simple least squares line equation as y = mx + c . So, we try to fit a line through the points on the loglog plane. The graphical representation is given in Fig 1. Fig. 2.1 The relationship between aggregated variance equation and the least squares line. From the loglog plot, we estimate βˆ by computing the slope of the least line. Then, we can compute H using (6). The slope is formulated: Σ (Σ ) Σ Σ Σ − − = 2 2 ˆ i i i i i i n x x n x y x y β , where n is the number of samples. (2.5) (Note: To avoid computational round off errors (2.5) is used instead of a simple form of (2.4). This has been verified by comparing the results from both equations, with the later underestimating the slope value) x y slope = β c log [var( ( ) )] 10 X m [m] 10 log log [var( )] 10 X Note: the aggregated variance is normalized by the corresponding Statistical computed data point 26 • Hurst parameter is estimated by fitting a simple least squares line through the resulting points in the plane. By ignoring the very lowend and very highend m value, compute the slope ( βˆ ), and then the Hurst parameter (H) is computed as: (β 2) 2 1 β 2 ) ) ) H = + = − . (2.6) (Note: capped symbol means an estimate of the true value.) Simulation Results Ethernet data set: byte.txt (Note: the byte.txt data set (1999) is more recently collected compared to BCpAug89, but the this data set is smaller compared to BCpAug89) is used to plot Fig. 2. According to [34], Ethernet data in 1989 (AUG89 trace) has H ~0.8, and the traffic is more selfsimilar from 1990 onwards with H~0.9 (FEB92 trace during high internet traffic hour of Feb. 1992 with H~0.96 [34]). Fig. 2 shows the same degree of selfsimilarity in the Ethernet traffic of year 1999, which once again confirms that H~(0.90,0.96) for Ethernet traffic in 90’s. This may be due to the popularity of Internet usage, and more applications/services (e.g. digital video streaming, multimedia service) being able to be provided through Internet. The aggregated variance plot of Ethernet traffic is showed in Fig. 2.2. It has the H value 0.9279, which indicates that the traffic do have the selfsimilarity characteristic. 27 Fig 2.2 This figure shows that Ethernet traffic is very selfsimilar, which is indicated by a fairly large H value. Star Wars IV, high quality: Terse_StarWarsIV.dat data set is used to plot Fig. 2.3. Fig 2.3 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. 28 2.2.3 Simulation Flow Chart Begin Aggregate the input data series by dividing its length N into blocks of size m, and then averaging each block. Σ = − + = = km i k m m X i k m X k ( 1) 1 ( ) ( ) 1 ( ) 1, 2,K, N/m Compute its sample variance. ( ) Σ= = − N m k m X m k X N m X / 1 ( ) ( ) ( ) 2 / var 1 Normalize var X (m) corresponding to its sample. Plot the normalized variance log10( var X (m) ) versus log10(m). Fit a straight line (with a slope β =2H2) to the points on the plot. From the slope β (compute β by ignoring very low end and very high end m for more accuracy), and then compute (estimate) the Hurst parameter, where H=1 β/2. End 29 2.2 R/S Method 2.3.1 Description and Methodology R/S statistic is also referred to the rescaled adjusted range, and is formulated as ( ) max ( ) ( ) min ( ) ( ) . ( ) : 1 0 0 ⎥⎦ ⎤ ⎢⎣ ⎡ ⎟⎠ ⎞ ⎜⎝ − ⎛ − ⎟⎠ ⎞ ⎜⎝ = ⎛ − ≤ ≤ ≤ ≤ Y d d Y d Y t t d Y t t S d d S R t d t d (2.7) For a stationary time series, X = {X }, where i ≥ 1 i , with sample sum Σ = = d i i Y d X 1 ( ) 2 , and sample variance d X Y d d S d d i i Σ= − = 1 2 2 2 ( ) ( ) . (2.8) For fractional Gaussian noise or fractional ARIMA: [ ] H H E R / S(d) ~ C d as d ∞ and CH is a finite positive constant that is not dependent on d. Thus, we have [ [ ]] [ ] [ ] H E R S d H d C 10 10 10 log / ( ) = log + log , (2.9) From (2.9), H is directly proportional to the slope. Refer to the least squares line concept in section 2.2 for the same argument. The algorithm: (An algorithm of the code also given in [35]) • For a data length N, divide it into series of K blocks. • Then, for each lags d compute R(t ,d) S(t ,d) i i , for different starting point i t ; the starting points must be t d N i ( −1) + ≤ . • Plot log [ ( , ) / ( , )] 10 R t d S t d i i versus log ( ) 10 d . • Fit a least squares line through the points on the loglog plane, the slope of the line is the estimator for Hurst parameter, H = slope of the line. 30 (Note: the slope is calculated by using the same equation as (2.5).) The same Ethernet data set and the video file of Star Wars IV (high quality) are used to show that the multimedia source and Internet traffic do exist selfsimilarity, which illustrates in Fig. 2.4 and Fig. 2.5 using the R/S method. Since both figures have H value larger than 0.5, and closed to 1. 2.3.2 Simulation Results The same Ethernet data set and the video file of Star Wars IV (high quality) are used to show that the multimedia source and Internet traffic do exist selfsimilarity, which illustrates in Fig. 2.4 and Fig. 2.5 using the R/S method. Since both figures have H value larger than 0.5, and closed to 1. Compare to [35] H = 0.903 for K=10 and up to log10(d) = 4.6, the obtained results are closed to [35] but not exactly the same, this may due to only up to log10(d) = 3.4 estimate points are used. 31 Fig 2.4 This figure shows that the data set is selfsimilar, and the level of selfsimilarity is indicated by the H value. Here, K = 10 and upto log10(d)=3.4 is used. Fig 2.5 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. K=10 and up to log10(d)=3.4 is used. 32 2.3.3 Simulation Flow Chart Begin The input data series of length N is divided into K blocks (samples), and with partial sum Σ= = d i Y d Xi 1 ( ) , the sample variance is calculated as Σ= = − d i i X d Y d d S d 1 2 ( ) 1 2 (1/ )2 ( )2 Compute its R(d)/S(d) statistic by rescaled adjusted range, ⎥⎦ ⎤ ⎢⎣ ⎡ ⎟⎠ ⎞ ⎜⎝ − ⎛ − ⎟⎠ ⎞ ⎜⎝ = ⎛ − ≤ ≤ ≤ ≤ max ( ) ( ) min ( ) ( ) ( ) 1 ( ) ( ) 0 0 Y d d Y d Y t t d Y t t S d S d R d t d t d Plot log10( R(ti,d) / S(ti,d) ) versus log10(d). Fit a straight line (simple least squares line) to the points on the loglog plot. Compute the slope of the straight line, which is the estimator of the Hurst parameter, slope = H. End 33 2.4 Estimating the Hurst Exponent using Wavelet Spectral Density 2.4.1 Description and Methodology This method transforms the time series into discrete wavelets. In Matlab, Discrete Wavelet Transform can be use to decompose the input data to scaling and wavelet functions. 1. The Hurst exponent for a set of data is calculated from the wavelet spectral density, Σ= = j i j j i P c 2 1 2 2 1 where ci is the wavelet coefficients. (2.10) 2. Regression line through the normalized spectral density : H = abs((slope –1 )/2). (2.11) Recall: The spectrum of a longrange dependent process X(t) with the discrete wavelet transform coefficients X c show the following behavior E c j l j H C X [ 2 ( , )] = 2 (1−2 ) [43]. By taking log2 on both sides, log [ [ ( , )]] (1 2 ) log [2 ] log [ ] 2 10 2 2 E c j l H j C X = − + . (2.12) From (2.12): ( ) 2 1 2 1 2 1 − → = − slope = − H → H = slope H slope (2.13) which follows the same least squares line argument. Refer to the least square line concept in section 2.2. 34 Algorithm: • Compute the power spectrum by averaging the squares of the coefficients of the transform P(j). • Plot log2(P) versus log2(2j). • Fit a simple least squares line through the points on the loglog plane. • The Hurst parameter can be computed as H = 2 slope −1 .(Note: the slope is calculated by using the same equation as in (2.5).) The same Ethernet data set and the video file of Star Wars IV (high quality) are used to show that the multimedia source and Internet traffic do exist selfsimilarity, which illustrates in Fig. 2.6 and Fig. 2.7 using the wavelet method. Using this method, both of the data sets have calculated H value larger than 0.5, and closed to 1. 35 2.4.2 Simulation Results Fig 2.6 The figure shows that Ethernet traffic is selfsimilar, and the level of selfsimilarity is indicated by the H value. Fig 2.7 The figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. Wavelet Estimate Method to Approximate the Hurst parameter Wavelet Estimate Method to Approximate the Hurst parameter 36 2.4.3 Simulation Flow Chart Begin The input data series is transformed from time series into discrete wavelet. Then, the wavelet power spectral density can be calculated from Σ= = j i j j i P c 2 1 2. 2 1 Plot log2(P) versus log2(2j). Fit a straight line (simple least squares line) to the points on the loglog plot. Compute the slope of the straight line, which is the estimator of the Hurst parameter 2 slope − 1 H = . End 37 2.5 Observation and Discussion All three graphical estimation methods provide a good estimate of the Hurst parameter (Fig. 2.8), H, and allow us to detect selfsimilarity in an empirical data set. These three methods provide a closed estimation of H, which is between (0.85, 0.93) for Ethernet traffic, and a value between (0.85, 0.91) for Star Wars data set. However, these three methods provide point estimate to H, and we may be interested in a more refined data analysis, e.g., confidence intervals for H. Therefore, an interval estimation can be done with maximum likelihoodtype estimates (MLE) and related methods based on periodogram [34]. The slope of the graph is the graphical tool to compute the Hurst parameter, where the slope of the straight line will provide the information about the Hurst parameter. The critical step in this aspect is choosing the statistical computed points on the plane that should be used to compute the slope. Usually, the very low end and very high end points are not used [36]. Fundamentally, the goal of traffic modeling in this dissertation is: • To find a general/universal traffic model that is suitable for broadband networks. • The model could be appropriate to real traffic and to all type of traffic. • Performance of real networks transporting the traffic of the model could be estimated with adequate accuracy. By understanding the characteristics of Internet and multimedia traffic, we would be able to estimate the jitter process of the broadband networks with adequate accuracy, where the networks with heterogeneous type traffic are greatly different than the networks with homogeneous type traffic. The following two chapters have derived the mathematical equations for evaluating the jitter process in those networks. 38 Fig 2.8 The comparison between the three methods is shown, where the level of selfsimilarity is indicated by the H value. The estimation range is between (0.82, 0.93) for Ethernet traffic for low m aggregated level, where all the three methods have proved that the Ethernet traffic is very selfsimilar. 39 Chapter 3 Theoretical Analysis of Delay Jitter of Homogeneous Traffic in ARQ Wireless Networks 3.1 Abstract This chapter provides a theoretical analysis of delay jitter for homogeneous time constrained traffic and proposes a call admission control (CAC) scheme for wireless differentiated services (DiffServ) networks that apply SelectiveReject (SREJ) automatic retransmission request (ARQ). The CAC scheme regulates the lower class traffic to provide the required levels of delay jitter for the higher priority classes. 3.2 Introduction DELAY JITTER [1] (which is equivalents to interarrival packet jitter) is one of the most important parameters in quality of service (QoS) support measurement for realtime data transfer. Due to this fact, there are several papers that have analyzed the performance of delay jitter [6][7][61]. In [6], the time division multiple access (TDMA)/time division duplex (TDD) scheduling scheme is used. In [7], the jitter is analyzed for mobile ad hoc networks (MANET) based on the ad hoc ondemand distance vector (AODV) routing protocol, where the authors propose a novel handover mechanism. Both [6] and [7] provide results on jitter performance analysis based on 40 computer simulation for the wireless network models. In [61], the authors provide a jitter analysis on wireless networks involving ARQ error recovery, where the delay jitter is calculated using the windowlength generating function and the numerical results are verified through simulation. The delay jitter research of [9] extends the results of [1] and [10] for DiffServ networks, but all three papers do not consider the channel error probability or the ARQ error control scheme, which makes the results difficult to apply to wireless networking applications. Therefore, this paper provides a novel analysis of the perclass jitter performance of DiffServ networks based on wireless channels that experience packet errors, assuming a nonpreemptive headoftheline (HOL) priority scheme. The derivations provide a direct method to analyze/evaluate the perclass jitter based on the DiffServ network, retransmission time constraints, and network packet error parameters [12]. In addition, this paper evaluates the effects on the delay jitter in reference to the priority control scheme of the ARQ traffic for two cases of: 1) the ARQ traffic has a priority over the original transmission traffic; and 2) the ARQ traffic has no priority over the original transmission traffic. 3.3 Analytical Model 3.3.1 Network and System Model Assumptions In this dissertation’s chapter, we investigate a wireless communication link that is framed for a fixed packet size or is time slot based (e.g., timedivision multiple access (TDMA)) transmission. The examples of mobile cellular communications based on timecoordinated slotted data transmissions include Global Systems for Mobile Communications (GSM), IS54 and IS 136 of the North American Digital Cellular 41 (NADC), and Integrated Digital Enhanced Network (iDEN), which are all TDMA based protocols, and the hybrid codedivision multiple access (CDMA) based TDMA systems. Based on these models, in this paper, the traffic delay jitter characteristics are based on a discrete time (slotted) queueing structure. The network traffic model is assumed to be slotbased homogenous and statistically time division multiplexed. The ARQ model applied in this paper is a selectivereject/repeat topology, where only the packets that are erroneous are retransmitted. Additionally, assume class 1 has priority over class 2, class 2 has priority over class 3, and so on. Among the same priority the first in first out (FIFO) transmission ordering applies to the first transmission packets. In this paper, two kinds of ARQ traffic priority control schemes are investigated: 1) when the ARQ traffic has a priority over the original transmission traffic; and 2) when the ARQ traffic has no priority over the original transmission traffic. The network controller model that gives a nonpreemptive priority to the ARQ traffic is based on existing network schedulers that process admission control in reference to time delay bounds, such as the earliest deadline first (EDF) scheduler, where a delivery time deadline is applied to the data packets, thereby limiting the number of possible retransmissions of an erroneous packet [61]. For these types of schedulers, the ARQ packets will commonly have less of a time bound remaining for delivery, since a part of their delay bound would have been used in its former transmission(s), which would result in having a higher priority over the original transmission traffic [12], [61]. Based on these assumptions, in the following, the mathematical foundation of the analysis is established. 42 3.3.2 Theoretical Formulations Assume the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. A slot is defined as the time interval [t1, t), where t is a nonnegative integer (i.e., t ≥ 0). Here we define the mth time slot interval (cycle) of a tagged stream’s mth packet as [mT, (m+1)T ), where m and T are nonnegative integers. Any individual periodic T ’ traffic stream of interest among the different class of service (CoS) could be the tagged stream. Thus, as we investigate the jitter of a specific class, namely the nth class traffic stream, and define the traffic as a mixture 2 of the specified periodic T ’ tagged stream and the combined background traffic of numerous T ’ period streams from different sources. The number of packets that arrive in each slot will not only depend on the data sources but also on the number of ARQ packets that need to be retransmitted. Hence, the period of each renewal cycle is T = T ’ + T ’Pe, where the retransmitted packets will also consume the channel capacity. The term Pe represents the packet retransmission probability, which takes into account that an ARQ retransmission packet can also be erroneous again. Assume the packet errors are independent from packet to packet. Given the packet error probability perror, the probability that a packet transmission is successfully received is (1− perror). If up to r retransmissions are limited within the time bound, each of the j consecutive packet transmissions fail, and a successful transmission then follows, where j = 1, 2, · · ·, r, and r = 1, 2, · · · , T . Therefore, Pe becomes (1 ) 1 1 ( 1) 1 error T i i i error i e P =Σ p − p + = − − , where T is the transmission window size (processing rate) in packets (slots). The following notations are applied throughout this paper. The network’s packet processing rate is μ packets/s and the average arrival 43 rate is λtotal, and it is assumed that there are N classes of service. Hence, for a stable system the utilization is required to satisfy ( ) total total ( 1) 1 total ≤ 1 + + + + = + = − T Pe N N Peλ λ λ λ μ λ λ ρ L . (3.1) The utilization of a specific class n (i.e., n = 1, 2, . . .,N) is noted as n ρ , and it can be obtained from n ρ = (μ μ ) n [(λ λ ) μ ] n e n = + P , which considers the original transmission traffic and the retransmission traffic of the class n data packets. The CAC will control the amount of new admissions given to the class n sources such that the aggregated arrival rate of class n traffic does not exceed ( ( )) n n e = 1+ P ,max λ μρ . When the amount of ARQ packets increase the CAC will regulate the traffic loads of the lower classes by giving out less admissions, to maintain the required QoS of the higher priority classes. In order to investigate the effects of delay jitter in DiffServ networks, the derivation of the probability of jitter (i.e P{J~ = j}) becomes an essential building block. Let the random variable J j m n = , ~ , where n = 1, 2, . . .,N class and cycle m ≥ 1 [10], denotes the process of the normalized jitter or position difference between the mth and (m+1)th packet of the nth class tagged stream that originates from the same source. The term m n A ( +1), indicates the total number of class n packets that arrive in the (m +1)th time slot group. The average number of higher priority packets and ARQ packets that arrive in the (m+1)th period is represented as (m+1), (n−1) b , which can be obtained from ( +1), ( −1) ( +1), ( −1) ( +1), ( −2) ( +1),1 = + + + m n m n m n m b b b L b . The term (m+1), (n−1) b denotes the number of all the equivalent (n−1)th priority packets that enter the buffer before the class (n−1) 44 tagged stream’s (m+1)th packet. The probability that a jitter size of j will exist for the class n tagged stream is given by [9] P{J j} m n = , ~ = P{J j A k b a} m n m n m n = − = = , ( +1), ( +1), ( −1) ~  1 , P{A k b a} P{b a} m n m n m n ⋅ − = = ⋅ = ( +1), ( +1), ( −1) ( +1), ( −1) 1  . (3.2) In (3.2), the term P{A k b a} m n m n − = = ( +1), ( +1), ( −1) 1  is based on the consideration that the assignment probability of the class n packets is dependent to the number of the higher priority packets (i.e., variable a) that arrive within the time slot group specified by (m+1), (n−1) b . We subtract 1 from the total number of class n packets that arrive in the (m+1)th time slot group (i.e., A(m+1),n ) due to the fact that the tagged frame is also among the overall traffic. The binomial distribution used in (3.2) is based on { 1  } [ , ( 1)] ( 1), ( 1), ( 1) − = = = − − + + − P A k b a B p T a m n m n k (p)k ( p) T a k k T a − − − − ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − − = 1 ( 1) 1 (3.3) where k ∈[1, (T −a −1)], a ≤ j , and each class n packets have a successful (errorless) arrival probability p. The P{b a} m n = ( +1), ( −1) term represents the probability of the higher priority (class 1 to class (n1)) packets occupying a number of slots among the first j slots of jitter offset before the class n tagged packet enters service, and is calculated by the probability mass function of a bilateral geometric function (BGF) [9]. The discrete triangle distribution is applied to the termP{J j A k b a} m n m n m n = − = = , ( +1), ( +1), ( −1) ~  1 , , which is a symmetric distribution, which represents the probability that the time slot position of two sequentially arriving frames will be offset by a jitter amount of +j or −j slot(s) for the range [−k, k] 45 {~  1 , } ( ) , ( 1), ( 1),( 1) P J j A k b a j a m n m n m n k = − = = = Δ − + + − ⎪⎩ ⎪⎨ ⎧ ≤ + − − = + 0, otherwise , for 1 ( 1) 1 2 j k k j a k , (3.4) among the overall x possible time slots, 0 ≤ x ≤ T . A special case of this is the zero jitter case (i.e., j = 0) [9], which is simply { } { } Σ− = = = − = ( 1) 1 , , ~ 0 1 2 T ~ j m n m n P J P J j . (3.5) 3.3.3 Jitter Analysis with NonPriority ARQ Traffic In this section a comparison between the different packet error probabilities for wireless networks deploying a nonpriority ARQ scheme with fixed (limited) channel capacity is presented. The nonpriority ARQ scheme represents the case where the ARQ packets do not have a priority over the regular traffic. The probability of jitter for this case can be derived as, P{J j} m n = , ~ =Σ Σ = − − = − − Δ ⋅ ⎥⎦ ⎤ ⎢⎣ ⎡ − − +   0 1 (  ) 1 ' ' ( ) , ( 1) ( ) j a T a k j a k e n k T a j a T T P f a B ρ , (3.6) where 1 ≤ j ≤ (T −1) . The results are illustrated in Fig. 3.1. The { } ( ) ( 1), ( 1) 1 P b a f a m n = = + − term can be obtained from the probability mass function of a BGF [9], (1 )( ) ,   2 ( ) 1 1 ( 1) ( 1) f a p p a a j n n = − ≤ − − . (3.7) 46 The term (n−1) p is the probability of arrival of the higher priority packets and their ARQ packets compared to class n in a frame of T slots (i.e., Σ − − = = 1 ( 1) 1 n n i i p ρ ). The jitter probability for class 1 packets can be easily obtained from (3.6) P{J j} m = 1 , ~ =Σ− = Δ ⎥⎦ ⎤ ⎢⎣ ⎡ − 1   1 , ( 1) ( ) T k j k k T j T B ρ , 0≤ j ≤(T −1). (3.8) 3.3.4 Jitter Analysis with Priority ARQ Traffic In this section a comparison between the different packet error probabilities for wireless networks deploying a priority ARQ scheme with fixed (limited) channel capacity is presented. The probability of jitter for this case can be derived as, P{J j} m n = , ~ = Σ Σ = − − = − − Δ ⎥⎦ ⎤ ⎢⎣ ⎡ − − +   0 1 (  ) 2 ' ' , ( 1) ( ) ( / ) ( ) j a T a k j a k e n k T a j a T T P f a B λ μ (3.9) where 1≤ j ≤ (T −1) . In each slot there is a probability Perror of receiving a negative acknowledgement of the message. If a negative acknowledgement is received, the transmitter immediately retransmits the packet that was received in error instead of a new packet. The { } ( ) ( 1), ( 1) 2 P b a f a m n = = + − term can be obtained from the probability mass function of a BGF [9], (1 )( ) ,   2 ( ) 1 ' ( 1) ' 2 ( 1) f a p p a a j n n = − ≤ − − . (3.10) The term ' (n−1) p is the probability of arrival of the higher priority packets, which includes the retransmission packets of classes 1 through n, which can be obtained from Σ − − = = + 1 1 ' ( 1) n i i e n n P p ρ μ λ . 47 Fig. 3.1 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 10%. The solid line represents the nonpriority ARQ scheme, and the dotted line represents the priority ARQ scheme. 48 Fig. 3.2 Comparison between wireless networks nonpriority ARQ scheme with Pe = 20%. Fig. 3.3 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 1% and 10% for class 1 through class 5. 49 3.4 Discussions and Conclusions This paper provides a novel analysis of the perclass jitter probability of homogeneous traffic streams performance of DiffServ networks based on wireless channels that experience packet errors, assuming a nonpreemptive headoftheline (HOL) priority scheme. The investigation has been conducted for the case where the ARQ retransmission packets have priority over the first time transmission packets. The mathematical results were compared with simulation data, and the results show an accurate match, which verifies the derivations. The results of Fig. 3.1 show that for both the priority and nonpriority ARQ cases, the probability of jitter for the same class can be controlled to be approximately the same disregarding the channel packet error rate for the traffic of the higher priority classes if the CAC of the wireless network can obtain accurate packet error rate information and respond effectively in regulating the admission access. The call admission controller will dynamically manage the network traffic loads by regulating admissions based on the amount of retransmission traffic that is anticipated. Thus, the traffic load can be regulated dynamically to maintain the required jitter performance. Based on the observations of Fig. 3.1, Fig. 3.2, and Fig. 3.3, it can be observed that the normalized jitter probability of the priority ARQ scheme is larger than the nonpriority ARQ scheme. The difference in performance becomes more significant as the probability of packet error increases (e.g., when Pe increases from 1% to 10%, and 20%). However, class 1 and class 2 still maintain a relatively low probability of jitter compared to the traffic of the lower classes. In the ARQ scheme with priority control, the ARQ packets will block the new packets from being transmitted during the retransmission 50 process. Thus, the normalized jitter probability of the wireless network deploying ARQ with the priority scheme is worse compared to the ARQ with the nonpriority scheme, especially for the low priority packets. Although the ARQ priority scheme sacrifices the delay jitter performance for the low priority classes, it may be needed especially for realtime service applications in which the packet might be useless unless a successful reception of the packet is obtained within its time bound [12], [61]. In Fig.3.2, as Pe is 20%, no leftover channel capacity is available for class 5 (the lowest priority class) since a significant part of the channel capacity is used for retransmission of the higher priority class packets. In Fig.3.2, the negative values represent the normalized jitter probability of the priority ARQ scheme is larger than the nonpriority ARQ scheme, where probability of jitter for ARQ priority scheme minus nonpriority ARQ scheme. These results demonstrate the influence and the effectiveness of DiffServ in limiting the delay jitter for the high priority users. 51 Chapter 4 Jitter Characteristics of Heterogeneous Wired Communication Networks, Gaussian Traffic Modeling and Queue length approximation using the MVA Approach In realtime wired or wireless communications, each transmitted packet may experience different time delays during arrival at the destination. This variation in delay is often referred as delay jitter or simply jitter. Jitter is an unsurprising result of packet transferring in highspeed switched networks. The variable delay results from the processing and queueing at each node through the multihop network. This is because the packets transmitted between a given source and destination may vary in length, may take different routes, and may experience different delay at the switches. To compensate the packet delay jitter, the incoming packet are buffered at the destination, and then replayed at a constant rate based on the controller that regenerates the audio/realtime traffic (playback mechanism). The regenerated packets are therefore smoothed out. However, the compensation provided by the delay buffer is limited, where any incoming realtime traffic packets that have been delayed more than the replay delay bound limit, then the packets will be discarded. Thus, by controlling the delay jitter within the network can further reduce the timing distortion of realtime applications. In 52 order to examine the heterogeneous traffic network jitter behavior in a more general environment, we develop a generalized analytic approach to approximate the jitter probability density function (pdf) of a stationary tagged stream that is multiplexed on a highspeed IP network. The main objective of this chapter is to examine the relationship between the jitter and traffic characteristics, such as traffic load/utilization, and period T of the tagged stream. This insight may aid the design of the scheduling control of the buffer in the playback mechanism at each node. For a generalized approach to analyze a queueing process, the heterogeneous traffic arrivals at a node are modeled as a Gaussian process. In highspeed networks, it has been shown that aggregated traffic has a direct relation to Gaussian characteristics through Central Limit Theorem (CLT), which states that summing a large number of independent variables with finite variance can converge or weakly converge to a Gaussian random variable [22]. The networks’ selfsimilar traffic exhibits longrangedependent (LRD) correlations, and it is very close to being Gaussian and strongly LRD (i.e., approximately Fractional Gaussian noise), which is caused by both small and large file transfers over limited bandwidth links. Some of the traffic may follow a nonGaussian marginal distribution. However, by applying CLT, the aggregated traffic can be modeled as a Gaussian process; even though each single independent data source does not follow a Gaussian distribution. The Gaussian model is useful for two main reasons. First, any stationary Gaussian process can be completely characterized by its mean and autocovariance. Second, as today highspeed networks are highly complex and traffic is usually heavily multiplexed of thousands of network applications. By applying CLT, the aggregated 53 traffic can be modeled as Gaussian process; even each single independent data source does not follow a Gaussian distribution. The only defect in this model is that there is a positive probability of a negative quantity of arriving traffic, which is impossible to happen in real networks traffic. This significant weakness is counterbalanced by the fact that the CLT appeals as more and more traffic streams are aggregated to share a link; traffic becomes more Gaussian, and the case that the amount of negative traffic reduces as traffic is aggregated [24]. Many broadband traffic studies have evolved around the Gaussian model, and they show that Gaussian models indeed provide a good approximation to networks traffic if the aggregated traffic is sufficiently large. In [22], [23], and [24], the results shown that the Gaussian traffic model could be the precise tool for analyzing highspeed networks. Moreover, the Gaussian model is also a good fit for highspeed networks with differentiated services (DiffServ). In differentiated services networks, traffic management controls are on the level of traffic aggregates, not for individual links [23][54][55]. 4.1 Introduction In order to evaluate delay jitter, the queue length distribution of the output queue was first analyzed. We can relate the transmission delay and the queue length (number of packets) ahead of the tagged packet (i.e., n Q represents the number of customers ahead of the nth tagged packet). Let any customer’s service time be equal to one slot and follows FIFO order, n Q denotes the number of customers, regardless of their class affiliation, that are waiting for service just ahead of the arrival of the nth packet of the p 54 customer. Therefore, the normalized jitter relative to tagged stream period T is (see Chapter 1 for more detail discussion) ~ , 1, 2,... 1 = − = J n Qn+ Qn n . (4.1) ( ) ( ) 1 J T Q Q T Q n n n n = + − = + Δ + . (4.2) The normalized jitter with respect to the original data stream period (interdeparture time between nth and (n+1)th packets transmitted from the source), T: J~ = J − T = ΔQ(n), n =1, 2,... , n n where n n def ΔQ n = Q − Q ( ) +1 . (4.3) From (4.3), we can observe the study of jitter turns into an equivalent study of the queue size variation ΔQ(n) of a selected user’s packet arrival, which is the methodology that is going to be applied in this study. We want to find the pdf of J~n , i.e., Pr{~ } n J , from the queue length distribution of the steady state probability of the buffer with queue length q (P(Q>q)), q = 1, 2, … . A discretetime approach is used in the delay analysis, which a node/multiplexer is modeled as a discrete time fluid queue where the time is slotted. It is assumed that the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. In summary, the approach here is • First, apply the Gaussian traffic modeling using the MVA approach [25][25] to conduct the queue length analysis. Obtain the tail probability P{Q>q} based on the MVA approach for the discrete time queueing model [25][26] to conduct the queue length analysis, which is used in heterogeneous jitter analysis. This is done in section 4.2. At a node in highspeed networks, the packet arrival that consist of heterogeneous type traffic includes real time and 55 nonreal time integrated traffic streams from different sources (e.g., voice, audio, video, image, plain text and data of other newly developed Internet applications). A single link will carry hundreds or even thousands of applications, which apparently lead to the application of Central Limit Theorem, that the network traffic can be modeled by a Gaussian stochastic process. • Second, find the pdf of the jitter probability from the queue length distribution. This is done in section 4.3. 4.2 Discrete Time Fluid Queue Model and Extreme Value [26] The multiplexer is modeled as a fluid queue serving a large number of independent sources. In the discrete time model, the fluid is permitted to flow in and out of the buffer only at discrete time intervals denoted in k. Let N be the total number of sources served by the multiplexer, and (s) k X be the amount of traffic that arrives from source s into the buffer at time k, s =1, 2, …, N. Further, let Σ = = N s s k k X X 0 ) ( and μ − = Δ (0) k X , which means that k X is the aggregated fluid arriving at time k, and less the system capacity μ. Let ≥ 0 k Q be the amount of fluid in the buffer at time k, less than the capacity μ, and the k Q for the infinite buffer case can be represented using Lindley’s equation [26] ( ) max{ ,0}. k k 1 k k 1 k Q = Q + X = Q + X − + − (4.4) Lets say that the fluid queue has always been operational, that is k ∈ƶ = {…, 1, 0, 1, …} (instead of time starting at k = 0). As long as k X is a stationary and ergodic process, and 56 with = { } < 0 k X E X (the stability condition for an infinite buffer queuing system, where the arrival rate must be less than the service rate), (4) can uniquely determine a stationary process ( k Q~ ) that satisfies the equation, where for all k ∈ƶ = {…, 1, 0, 1, …} [26][45] ( k ∈ƶ from this point on). Due to k X being an ergodic stationary process, the tail probability of buffer queue length q at time k ( P(Q q) k > ) converges to a steady state tail probability of buffer queue length q ( P(Q > q) ) regardless of the initial condition Q0. Thus, for all k ∈ƶ, P(Q~ q) k > is equal to P(Q > q) , since the tail probability does not depend on the initial condition Q0, and the tail probability of a stationary process is the tail probability itself, where P(Q~ q) k > = P(Q > q) [26][45]. The relation between an ergodic stationary process k X and the corresponding stochastic process k Q~ , where k ∈ƶ [26] Σ≥ − ≥ = m i k i m k Q X 0 1 ~ sup (4.5) where m = 0, 1, 2, … .Since, P(Q~ q) k > = P(Q > q) for all k [26], P(Q q) P(Q~ q) k > = > ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ > = Σ≥ − ≥ P X q m i i m 0 1 sup . (4.6) From (4.5) and (4.6), we can see that the steady state tail probability P(Q > q) can be determined by summing all previous stationary aggregate fluid arrival process. In other words, the probability of the tail probability P(Q > q) is the same as the tail probability 57 of the supremum of a stochastic process denoted by Σ= − = m i m i W X 0 , where ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ > = > ≥ P Q q P W q m m 0 ( ) sup , m = 0, 1, 2, … [26]. This stochastic process, m W , is called the backward accumulation process, and it is not stationary. The first two moments of m W are defined as below [26] E W mX m { } = (4.7.a) Σ− = = + − 1 1 { } (0) 2 ( ) ( ) m i m X X Var W lC m i C i (4.7.b) where C (0) E{(X X )(X X )} X k k l = − − + Δ is the autocovariance function of Xk. Hence, P(Q > q) can be calculated by determining the tail probability of the supremum of the backward accumulative process m W , where the Extreme Value Theory is applied to this supremum of a stochastic process to obtain a simple approximation for P(Q > q) [26], which is shown in the next subsection below. Evaluating P(Q>q) at a multiplexer with Gaussian Arrival Process using the MVA approach We can obtain a simple approximation for P(Q>q) by applying the results from the theory in section 4.2, where determining the tail probability P(Q>q) of a queueing system is mapped to that of determining the tail probability of the supremum of the backward accumulation process m W (here only the discrete case is our concern) [26]. Let μ − = Δ (0) k X denote the link capacity of a multiplexer (e.g., an ATM multiplexer). Assume that (s) k X , the fluid arrival process of source s at time k, s = 1, …, 58 N, are independent mean ergodic stationary arrival processes with finite mean s X , and autocovariance C (l) s . ( ) 1 s k N k s A Σ X = Δ= is defined to be the aggregate arrival process. Then, Ak is also a mean ergodic stationary arrival process with mean Σ = = N s s A X 1 and autocovariance Σ = = N A s s C l C l 1 ( ) ( ) . So, Σ = = = − N s k s k k X X A 0 ( ) μ is a mean ergodic stationary process with mean X = A −μ (where = =Σ = = N s s k k X E X X 0 { } ( ) ( ) 1 Σ ( ) + −μ = N s s k X , since μ − = Δ (0) k X ) and autocovariance C (l) C (l) X A = . In other words, k X is the aggregate fluid arriving at time k, less the capacity μ. As long as X < 0, which means that the arrival rate must be less than the service rate, the infinite buffer queueing system is stable. Now, model the arrival process Ak as a stationary normal process. The main reason to consider Gaussian traffic modeling is the CLT [25][26]. As the network grows, the number of independent traffic sources aggregating at a node (e.g., router, switch, multiplexer) increase, and the shape of the traffic distribution will become closer and closer to Gaussian. Ak has both negative and positive components. The negative component in [26] imply that the buffer is empty due to the arrival process, which is not possible in reality. However, as the mean Ā of the aggregate process is typically several times larger than its standard deviation (0) A C , the probability of this negative flow is negligible. Since Ak is modeled as a normal process, both Xk and Wm are normal processes. Now, rewrite the arrival process, where determining the extreme value distribution of Wm 59 is equivalent to determining the extreme value distribution of a new stochastic process{Z : m = 0,1,K} m , which is defined as [26] ((1 ) ) (1 ) m k Z Wm m m − + + − = Δ μ ρ μ ρ (4.8) where μ ρ A Δ= is the utilization of the ATM multiplexer, ⎡ ⎤ μ q k Δ= is the time it takes for the fluid in the buffer at level q to empty, and μ is the service rate. Zm is the standardized maximum value, where μ ((1−ρ )m+ k) and μ (1−ρ )m are the scale and location parameters, respectively. Also, Zm is a normal process with [26] { } = 0 m E Z (4.9.a) 2 ((1 ) )2 { } { } m k Var W Var Z m m − + = μ ρ . (4.9.b) The extreme value distribution is used to quantify the probabilistic behavior of unusual or rare events, and provide a better fit to the data set. Justification of the new stochastic process m Z : Applying Central Limit Theorem, assume that{B : t ≥ 0} t is a Gaussian process with stationary increments such that 0 B = 0, and define ς := (Σ ) = − = − N n n t t E B E B 1 ( ) ( ) , and ( ) : var( ) t v t = B , where each (n) t B is an individual stream. Expressing P(B q) t > in terms of ς , v(t) , and the standard Gaussian tail function ψ (α ) : 2 / 2 2π e z dz ∫ = − , we obtain a multivariate version of the CLT of the normalized process [58] ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + > = ( ) ( ) v t P B q q t t ς ψ . (4.10) 60 Now, apply the Dominant TimeScale tq and the Maximum Variance Asymptotic approach. The term ( )2 ( ) q t v t +ς should attain its maximum value at some finite point q t = t , at which P(B q) t > attains it maximum. For Gaussian processes, q t , the dominant time scale is also the time at which it attains its maximum variance value v(t) . P(Q q) P(B q) t > = > is largely dominated by P(B q) tq > [25][26][58]. The q t should be a local maximum point of log[v(t) /(q +ς t)2 ] that lies in the open set q {t : v(t) > 0}, t must satisfy [58][59] . ( ) 0 log ( ) 2 t tq q t v t dt d = ⎥⎦ ⎤ ⎢⎣ ⎡ + = ς (4.11) Note: Eq. (4.10) and (4.11) will hold for discrete time processes. For notation simplicity, under (4.10) and (4.11), the new stochastic process m Z is defined as q m W m Z m m χ χ + + = (4.12) and define ⎡ ⎤ μ q k Δ= and μ ρ = A where m : E(W ) mE(X ) m χ = − = − = −[E(A −μ)]m = −[E(A) −μ]m = −m[ρμ −μ] 61 = −μ [ρ −1]m =μ [1−ρ]m (4.13) Substitute (4.13) into (4.12), we have q m W m Z m m [1 ] [1 ] μ ρ μ ρ + − + − = k m W m m [1 ] [1 ] μ μ ρ μ ρ + − + − = ( m k ) W m m − + + − = [1 ] [1 ] μ ρ μ ρ . (4.14) Proposition 1 [26] if and only if > 1 m>q m W Z From proposition 1 and (4.6), the relationship between the steady state tail probability of the buffer queue length q and the extreme value distribution of Zm and Wm ⎟⎠ ⎞ ⎜⎝ > = ⎛ > ≥ P Q q P W q m m 0 ( ) sup ⎟⎠ ⎞ ⎜⎝ = ⎛ > ≥ sup 1 0 m m P Z . (4.15) From the Dominated Convergence Theorem [26][48], the equations (4.16) and (4.17) show that { }→0 m Var Z as m →∞ if Σ < ∞ ∞ k=−∞ X  C (k)  (a sufficient condition for the ergodicity of a stationary process [49]), { } Σ∞ =−∞ →∞ = k m m X Var W C k m lim 1 ( ) (4.16) and 62 { } 2 2 (1 ) ( ) lim μ − ρ = Σ∞ =−∞ →∞ k X m m C k mVar Z . (4.17) Fig. 4.1 illustrates a plot of the variance of Zm versus m, it shows that { } m Var Z must reach its maximum value at some finite m = mmax ≥ 0. Next, the extreme/supremum value distribution will be applied to approximate the tail probability. Maximum Variance Approximation: “For a zero mean normal process Zm that is correlated in time and whose variance { } m Var Z achieves a maximum value for some finite mmax [26],” P Z u P(Z u) m m m > ≈ ⎟⎠ ⎞ ⎜⎝ ⎛ > ≥ max 0 sup (4.18) for sufficiently large u [26]. Fig. 4.1 illustrates this point by plotting { } m Var Z vs. m. For eq. (4.18), the right hand side approximation is a lower bound of the left hand side, that is P Z u P(Z u ) m m m > ≥ ⎟⎠ ⎞ ⎜⎝ ⎛ > ≥ max 0 sup [26]. “Typically, 1.5 { } mmax u > Var Z is sufficiently large for the approximation to work well [26]”. Thus, if { } << 1 m Var Z , then the tail probability P(Q>q) can be approximated as [26] ( ) ( 1) max > ≈ > m P Q q P Z x dx ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = ∫ − ∞ 2 exp 2 1 2 1 σ max π . (4.19) This is because the probability that P(Q>q) is much less that 1, the condition { } << 1 m Var Z readily hold for this analysis [26]. 63 Theorem A (Theorem A in [56], Theorem D.4 in [57]) “Let { t [L U]} t ς : ∈ , be a zero mean (centered) Gaussian process, and suppose that there exist constants a and γ such that {( ) } γ E ς ς a t s s t − 2 ≤ − for all t, s∈[L,U]. Then, there exists a constant K determined only by a and γ, such that for any A ⊂ [L,U] and y, ({ }) ( ) ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ > ≤ − A A P y K U L y y σ ς 2 /γψ (A.1) where { } A t A t σ Var ς ∈ = sup ”. Summary of the algorithm for obtaining the tail probability P(Q>q) based on the MVA approach for discrete time queueing model [26]: 1. Given individual arrival processes with mean s X and autocovariance C (l) s , compute the aggregate mean Σ = = N s s A X 1 , and autocovariance Σ = = N A s s C l C l 1 ( ) ( ) of the aggregate arrival process. 2. Compute { } m Var Z using Eq. (7.b) and (9.b) as 2 2 1 1 ((1 ) ) (0) 2 ( ) ( ) { } m k mC m i C i Var Z m A i A m − + + − = Σ − = μ ρ where μ > A is the link rate, μ ρ = A , and ⎡ ⎤ μ q k Δ= . 3. Determine 2 max σ , the maximum value of { } m Var Z . 4. Finally, compute the tail probability ( ) ( ) ∫∞ − > ≈ > = max 2 max 1 2 2 1 1 σ π P Q q P Z e dx x m , where mmax Z is the normal random variable. 64 The typical plot of { } m Var Z versus m is shown in Fig. 4.1. This analysis is done at an ATM multiplexer with the following assumptions: q=1000, μ=0.61, N=100, where individual arrival process has a mean s X = 10 cells/sec, and autocovariance of Gaussian process l s C (l) = 100e−0.04 . Fig. 4.11 Plot of variance of Zm versus m. The variance reaches a maximum value and then begins to converge to 0. The parameters used are q=1000, μ=0.61, N=100, each individual arrival process with mean s X = 10 cells/sec, and autocovariance l s C (l) = 100e−0.04 . 1 This figure is attempted to reproduce the result of Figure 3 in [26]. Both graphs have the same distribution shape but values may not be exactly the same, because the parameters used in [26] to plot Figure 3 are not provided by reference [26]. So, we cannot regenerate the plot with the same set of parameters used in [26] (which is unknown to us). The attempt here is to use the MVA theory and plot the Fig. 4.1 using a set of predicted parameters to regenerate the plot that is similar to Figure 3 in [26]. 65 4.3 Jitter Analysis of Heterogeneous Traffic Networks Assume the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. The time is slotted with the size being equal to the transmission of a packet. An arrival time slot is defined as the time interval [t1, t), where t is a nonnegative integer (i.e., t ≥ 0). Here we define the nth packet arrival time slot interval as [nT, (n+1)T) for the packet from the tagged stream (stream of interest), where n and T are nonnegative integers. The background traffic is the superposition of all the other traffic competing for the resources with the tagged stream at a node. In heterogeneous highspeed network, jitter experienced by realtime traffic can be worsening if traffic is not being regulated or some type of congestion control mechanism is not applied. Thus, a service discipline similar to the distortionreducing peak outputrate enforcing (PORE) [50] is used to prevent the delay jitter increasing without bound. Let’s refer to this as a tagged stream adaptive PORE (APORE) service discipline. The APORE service strategy guarantees the packets belong to a tagged stream are transmitted at a minimum spacing of Amin slots, where Amin = T 1. Whenever the queue level q < Amin , the server delays providing service to the tagged stream, instead provides firstcomefirst serve service to the background traffic. Thereby, it ensures the tagged stream experiences minimum jitter (see Fig. 4.4). Proposition: The probability that a jitter size of j will exist for the nth packet of the tagged stream is given by: P{J j} n ~ = = P{J j A q} n n = − = + ~  1 1 P{A q} n ⋅ − = + 1 1 = ( ) min ( ), 0 2 1 P Q q f j q A q > < ≤ (4.20) 66 where 1 ≤ j ≤ (T −1) and n+1 A indicates the total number of packets that arrive in the (n+1)th time slot group. In (4.20), the probability of q number of data packets that arrive among the available (T1) slots will be served. A special case of (4.20) is the zero jitter case (i.e., j = 0), which is simply P{~ = 0} n J = { } Σ− = − = ( 1) 1 1 2 ~ T j n P J j . (4.21) Derivations & Explanations: In (4.20), the term P{A q} n − = + 1 1 is the aggregated traffic arrival distribution that approximates the number of arrivals in the arrival slot of a tagged stream packet. It is based on the consideration of the probability the packets that arrive within the time slot group, which will be served ahead of the tagged packet. Subtract 1 from the total number of aggregated packets that arrive in the (n+1)th time slot group (i.e., (n+1) A ) due to the fact that the tagged frame is also among the overall traffic. The traffic distribution in eq. (4.20) is based on P{A q} P(Q q) n − = = > + 2 1 1 1 ({ }) ∫∞ − ≈ > = max 2 max 1 2 2 1 2 1 1 2 1 σ π P Z e dx x m (4.22) where q∈[1,(T −1)] , calculated using the MVA approach discussed in section 4.2. The discrete triangle distribution applied is a symmetric distribution, which represents the probability that the time slot position of two sequentially arriving frames will be offset by a jitter amount of +j or –j. Thus, the triangle distribution for the range [q, q] is applied as {~  1 ,} ( ) ( 1) P J j A q f j n n q = − = = + 67 ⎪⎩ ⎪⎨ ⎧ ≤ + − = + otherwise for j q A j q 0, , 1 ( 1) 1 2 min (4.23) which provides the normalized jitter probability of j given that q packet arrivals enter the server before the (n+1)th tagged packet of the tagged stream, among the overall x possible time slots, 0 ≤ x ≤ T. 4.3.1 Simulation and Numerical Study The following simulation and numerical results focus on the delay jitter in terms of pdf on the performance of a tagged stream under different traffic conditions. For the illustrative purpose, the bursty Internet traffic trace is used in this evaluation. The simulation environment has been set up in such a way that the information bit stream (e.g., video, multi media, digitized voice, etc) is packetized into fixedlength ATM cells (packets). The cells are transmitted using fixed interarrival time but the bit length is varied from celltocell (packettopacket). Accordingly, the delay jitter is defined as the delay jitter experienced between two successive packets (e.g., the nth and n+1th packets from the tagged stream), where the delay jitter is calculated based on (4.3) (see Flowchart 1). For the experiment, a real Internet traffic trace is used, BCpAug89 packet traces of LAN and WAN traffic seen on an Ethernet. We assume that Ethernet traffic sources are multiplexed on to an ATM network, where traffic is segmented into small and fixed sized cell/packet in order to achieve small delay and delay jitter [51][52]. The reason we base our analysis on ATM networks is because still ATM remains as the most widely used Internet backbone protocol at this time. The traces are in byte units, which is converted into ATM cell 53 bytes. The variable size Ethernet packets are segmented in to constant 68 size of 53 bytes packets (cells). Thus, the traffic transmitting in the network is fixed size packets and one packet is transmitted in each time slot. Flowchart 1 is the algorithm of delay jitter calculation at a multiplexer/node. The queue consists of a tagged stream packet and background stream packets. The tagged stream and background stream are segmented into ATM 53 bytes packets. There are a random number of background stream packets that enter the queue before the tagged stream packet. Whenever the queue level q < Amin , the server delays providing service to the tagged stream, instead provides firstcomefirstserve service to the background traffic. The traffic trace of BCpAug89 is resampled at 10 ms. Assume the average processing rate and overhead delay is 1ms per cell, the interarrival time between two consecutive cells is 10 ms, which will be equivalent to 10 time slots (for generate T = 10 tagged stream). Through the numerical example, we demonstrate the accuracy of the closed form delay jitter approximation of eq. (4.20) shown in Fig. 4.2 of a 95% confidence interval (CI), for selfsimilar traffic of heterogeneous networks. Here, we calculate the 95% CI for the delay jitter proportion between the real data set and the numerical analysis (eq. (4.20)). The width of the 95% CI reveals the degree of uncertainty in the estimate of the treatment effect; in another words, this is the interval which includes the true value with 95% certainty. The real data set is used to obtain the empirical pdf function for the delay jitter. Then, eq. (4.20) is used to approximate the delay jitter pdf function of the data set. Subsequently, confidence intervals for the estimations are computed. The confidence interval bounds on the standard deviation between the empirical and numerical values. 69 In Fig 10, we compare the approximation eq. (4.20) and the simulation results of the jitter distribution at a multiplexer serving various Internet applications. Fig. 4.2 shows that the delay jitter increases when the traffic utilization increases from 50% to 90%, for T equals to 10. In Fig. 4.3, we can observe that the tagged stream with a large period will tend to experience large delay variation as the utilization increases from 50% to 70%, where the T increases from 10 from 20. Fig. 4.4 illustrates the effectiveness of the control algorithm, the APORE service strategy that guarantees the packets belong to a tagged stream are transmitted at a minimum spacing of Amin slots, where Amin = T 1. If we choose the Amin to be larger than T 1, then we will introduce more delay variation to the tagged stream, as shown in Fig. 4.4 the probability of jitter increases as Amin > T1. We will not consider Amin < T1, because this will increase the possibility that a packet from the tagged stream may not be arrived to a node even it is its turn for entering service. 70 Flowchart 1 The simulation algorithm used to calculate delay jitter at a multiplexer. Fig. 4.2 Comparison between the approximation equation and the simulation results of the jitter distribution for utilization of 50% and 90% with 95% CI, for the case of T = 10. 71 Fig. 4.3 Distribution of jitter for the comparison between utilization of 50% and 70%, and for the comparison between T = 10 and 20. Fig. 4.4 Distribution of jitter for utilization of 60%, T=10, and various Amin values. 72 4.4 Jitter Analysis of Heterogeneous Traffic Networks with Differentiated Services In this section, the jitter characteristic of the priority class in the DiffServ network is analyzed. In order to provide high quality service, endtoend quality of service (QoS) support is required. Several network models and mechanisms have been proposed by the Internet Engineering Task Force (IETF) to improve the QoS of integrated service networks by deploying differentiated service (DiffServ), traffic engineering (TE), and constraintbased routing (CR) [53]. The realization of DiffServ in networks is one of the essential focuses of TE technologies under development. Recently, in wide area networks (WANs), protocols like multiprotocol label switching (MPLS) and generalized MPLS (GMPLS) are being developed with this focus of enabling effective TE with DiffServ capabilities. A basic differentiated service scheme can be provided by a set of priority scheduling algorithms. The traffic flows are aggregated according to their belonging to a certain class type called the perhop behavior (PHB) [54]. The traffic classification is done in qualitative terms, which are based on vendor concerns [54][55]. For example, the network administrator may configure the service rate of 50%, 35%, and 15% for classes 1, 2, and 3 respectively. Class 3 may correspond to delay jitter insensitive traffic, where the least bandwidth is being enforced for this class (e.g., best effort Internet traffic). Therefore, the research presented in this dissertation proposes a methodology to directly compute the QoS performance quantity (e.g., probability distribution of interarrival jitter) of network deploying differentiated services. The analytic models are applied in analyzing the contribution of multipleclass of services in Internet networks 73 with respect to interarrival packet jitter. In addition, the relationship between interarrival packet jitter and the system characteristics, such as the server utilization and priority, is also investigated. This tool will help to provide an analysis of network routers and network streams for various system server topologies in order to assist network system designers in the hardware/firmware development and estimate the quality of service of DiffServ networks with heterogeneous type traffic, which includes real time and nonreal time integrated traffic streams from different sources (e.g., voice, audio, video, image, plain text and data of other newly developed Internet applications). DiffServ capable networks provide endtoend QoS control by classifying and assigning different classes of services onto the incoming packets. Hence, at the base station’s router/switch, the packets are buffered before being multiplexed onto the highspeed link following a nonpreemptive HOL priority scheme, where the packets that have been postponed in services will wait at the head of the line of its equivalent class until all higher priority packets have been cleared out of the server. The APORE service control algorithm strategy that guarantees the packets belong to a tagged stream are transmitted at a minimum spacing of Amin slots, where Amin = T 1. Assume class 1 has priority over class 2, class 2 has priority over class 3, and so on. Among the same priority the first in first out (FIFO) transmission ordering applies. In the discrete time model, the fluid is permitted to flow in and out of the buffer only at discrete time interval denoted by k. Let N be the total number of sources served by the multiplexer. Define k d X , to be the aggregated fluid of class d arriving at time k, and less the system capacity μd of class d, where Σ = = N s s k d k d X X 0 ( ) , , and k d d X μ − = Δ (0) , . Here, we assume that each fluid arrival process of class d corresponding to source s, ( ) , s k d X , is an 74 independent mean ergodic stationary process with mean s d X , and autocovariance C (l) s . Let’s denote ( ) , 1 , s k d N k d s A Σ X = Δ= to be the aggregate arrival process. Then, Ak is also a mean ergodic stationary arrival process with mean Σ = = N d s s d A X 1 , and autocovariance Σ = = N A s s d C l C l d 1 , ( ) ( ) . Thus, k d k d d X = A − μ , , is a mean ergodic stationary process with mean d d d X = A −μ (where Σ = = = N s s d k d k d X E X X 0 ( ) , , { } ) and autocovariance C (l) C (l) Xd Ad = . Let 0 , ≥ k d Q be the amount of fluid corresponding to class d in the buffer at time k, less than the capacity μd , and k d Q , for the infinite buffer case can be represented using Lindley’s equation ( ) max{ ,0}. k ,d k 1,d k ,d k 1,d k ,d Q = Q + X = Q + X − + − (4.24) Let say that the fluid queue has always been operational, that is k ∈ƶ = {…, 1, 0, 1, …} (instead of time starting at k = 0). Due to k d X , being an ergodic stationary process, the tail probability of the buffer queue length q at time k ( ( ) , P Q q k d > ) converges to a steady state tail probability of buffer queue length q ( P(Q q) d > ) regardless of the initial condition. The steady state queue length distribution corresponds to the supremum distribution of an ergodic stationary process k d X , and the corresponding stochastic process k d Q , ~ . The maximum amount of fluid in the system at time k can be expressed as Σ− = − ≥ = 1 0 , 0 , ~ sup m i k i d m k d Q X (4.25) 75 where m = 0, 1, 2, … . On the supremum distribution of Integrated Stationary Gaussian process with linear drift, the limiting (steady state) queue length distribution corresponds to the supremum distribution, ( ) : lim ( ~ ) , P Q q P Q q d k k d > = > →∞ ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ > = Σ− = − ≥ P X q m i i d m 1 0 , 0 sup . (4.26) Let the supremum of a stochastic process for class d defined by Σ− = − Δ= 1 0 , , m i m d i d W X . Based on the Extreme Value Theory, we can study the supremum distribution of d Q through the supremum stochastic process m d W , . Note that this stochastic process m d W , is not stationary. Now, Ak,d is modeled as a stationary normal process, then both Xk and Wm are normal processes. This is justified by applying the Central limit Theorem, which mentioned in the introduction that the multiplexer will serve a large number of independent sources. Thus, we study the supremum distribution of m d W , through the new supremum stochastic process m d Z , , where m d Z , is a centered (zero mean) Gaussian process. So, determining the extreme distribution of m d W , is equivalent to determining the extreme distribution of m d Z , . Assume there is a total of D class of services, the extreme value distribution of a new stochastic process of class d{ : 0,1, ; 1,2, , } , Z m d D m d = K = K , which is defined as ((1 ) ) (1 ) , , m k W m Z d d m d d d m d − + − − = Δ μ ρ μ ρ (4.27) 76 where d d c N d s s c c c A d X d d μ ρ ρ μ Σ Σ = Σ = = Δ = = = 1 1 , 1 is the load of class d at the multiplexer, ⎡ ⎤ d k q μ Δ= is the time it takes for the fluid in the buffer at level q to empty, and μd is the service rate of class d. Based on this we can define Zm,d as a normal process with { } 0 , = m d E Z (4.28.a) 2 2 , , ((1 ) ) { } { } m k Var W Var Z d d m d m d − + = μ ρ . (4.28.b) Based on the Maximum Variance Approximation, the tail probability of class d, P(Qd>q), can be approximated as ( ) ( 1) max , > ≈ > d m d P Q q P Z x dx m d ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = ∫ − ∞ 2 exp 2 1 2 1 max , σ π . (4.29) This is based on the same argument proved in [26], which is explained in section 4.2 above. Due to the probability that P(Qd>q) is much less that 1, the condition { } 1 , << m d Var Z readily hold for this study. Proposition: The probability that a jitter size of j will exist for the nth packet of the tagged stream for a class d traffic source is given by P{J j} n d = , ~ = P{J j A q} n d n d = − = + ~  1 , 1, P{A q} n d ⋅ − = + 1 1, = ( ) min ( ), 0 2 1 d q,d d P Q > q f j < q ≤ A (4.30) where 1 ≤ j ≤ (T −1) and n d A +1, indicates the total number of packets that arrive in the (n+1)th time slot group of class d and higher priority classes compare to class d. In eq. 77 (4.30), the probability of q number of data packets that arrive among the available (T1) slots will be served. A special case of (4.30) is the zero jitter case (i.e., j = 0), which is simply P{~ 0} , = n d J = ΣΣ { } − = = − = ( 1) 1 1 , 1 2 ~ T j d c n c P J j . (4.31) Derivations & Explanations: In (4.30), the term P{A q} n d − = + 1 1, is the aggregated traffic arrival distribution of class 1 up to class d, that approximates the number of arrivals in the arrival slot of a class d tagged stream packet. It is based on the consideration that the assignment probability of the packets that arrive within the time slot group, which will be served ahead of the tagged packet. Subtract 1 from the total number of aggregated packets that arrive in the (n+1)th time slot group (i.e., n d A ( +1), ) due to the fact that the tagged frame is also among the overall traffic. The traffic distribution in (4.30) is based on P{A q} P(Q q) n d d − = = > + 2 1 1 1, ({ }) ∫∞ − ≈ > = d P Z e dx x m d max, 2 max 1 2 , 2 1 2 1 1 2 1 σ π (4.32) where q∈[1,(T −1)] , calculated using the MVA approach discussed in section 4.2. The discrete triangle distribution applied is a symmetric distribution, which represents the probability that the time slot position of two sequentially arriving frames will be offset by a jitter amount of +j or –j. Thus, the triangle distribution for the range [q, q] is applied as {~  1 ,} ( ) ( 1), , P J j A q f j n n d q d = − = = + 78 ⎪⎩ ⎪⎨ ⎧ ≤ + − = + 0, , , 1 ( 1) 1 2 min otherwise for j q A j q (4.33) which provides the normalized jitter probability of j given that q packet arrivals enter the server before the (n+1)th tagged packet of tagged stream, among the overall min A possible time slots. 4.4.1 Simulation and Numerical Study The jitter probability of heterogeneous traffic streams with HOL priority control in DiffServ networks has been investigated. The derivations of this section provide a direct method to analyze the perclass jitter based on the parameters ρ and T. Fig. 4.5 and 14 show the jitter probability distribution of three different classes for the case of T = 10 slots and ρ equal to 50%, and also assuming that the probability of traffic arrival in the T slot observation window for class 1, class 2, and class 3 are the same. Fig. 4.5 has shown the 95% CI for the delay jitter proportion between the real data set and the numerical analysis. The width of the 95% CI reveals the degree of uncertainty in the estimate of the treatment effect; in another words, this is the interval which includes the true value with 95% certainty. The wider the width the more uncertainty it is, and more data set that collected from the same population is needed to increase the confidence level. In Fig. 4.6, the approximation equation results are comparing to the simulation results of the jitter distribution. In Fig. 4.5 and 4.6, it can be observed that the probability distribution function of the interarrival packet jitter widens as the class priority is descending, thus resulting in a higher probability of packet jitter for low priority classes. This is an expected result, where the newly derived equations provide a method to directly compute 79 this physical probabilistic quantity. Also, for class 1 as ρ << 1 the probability of jitter at zero (no jitter) increases while the probability of jitter for the nonzero values is reduced. Fig. 4.5 Comparison among class 1, class 2 and class 3 with respect to the approximation equation and the simulation results of the jitter distribution for utilization of 50% with 95% CI, and T = 10. 80 Fig. 4.6 The comparison of probability jitter distribution among class 1, class 2, and class3, where utilization is 50% and T is 10. 81 Chapter 5 Conclusions In this dissertation, the following research has been conducted 1. Investigate the delay jitter performance of homogenous wireless networks that apply ARQ error recovery with time constraints have been developed. The effects on the delay jitter in reference to the priority control scheme of the ARQ traffic for the two cases are evaluated: i) the ARQ traffic has a priority over the original transmission traffic; and ii) the ARQ traffic has no priority over the original transmission traffic. 2. Investigate the issues of traffic jitter characteristics in heterogeneous wired communication networks deploying different scheduling algorithms: • Obtain the tail probability P{Q>q} based on the MVA approach for discrete time queueing model [25][26] to conduct the queue length analysis, which is used in heterogeneous jitter analysis. • To find the pmf (probability mass function) of interarrival packet jitter from the queue length distribution. 3. The objective of this dissertation is to investigate and analyze the various possible traffic modeling techniques and evaluate the challenges in characterizing the diverse statistical properties of heterogeneous wireless networks [1343][5660]: 82 • Study the characteristics of the traffic: selfsimilarity, heavytailed distribution, Gaussian traffic distribution. • Comparisons among the popular traffic models. 4. Apply the Gaussian traffic modeling using the MVA approach [25][26] to conduct the queue length analysis, which will be further used in heterogeneous jitter analysis [112]. 5. Analyze the difference between jitter probability of multiple priority queues and switches [112]: • The headofline (HOL) priority queueing mechanism is applied at the queueing and scheduling control. 6. Develop a service discipline called the tagged stream adaptive distortionreducing peak outputrate enforcing to control and avoid the delay jitter increases without bound. In conclusion, using the Gaussian traffic modeling technique combined with the MVA approach for selfsimilar network traffic, the delay jitter was shown with the 95% CI for the delay jitter proportion between the real data set and the numerical analysis. For future research, this analysis will be extended to multiple priority queueing case. The multihop jitter of wireless and wired network analysis can be conducted, where endtoend congestion control is needed at a router for fair bandwidth allocation perflow. The CoreStateless Fair Queueing (CSFQ) [47] can be applied to allocate fair bandwidth perflow, and performance is evaluated (the number of congested links). 83 References 1. C. C. Bisdikian, W. Matragi, and K. Sohraby, “A Study of the Jitter in ATM Multiplexers,” High Speed Networks and their performance: IFIP Trans. C, Commun. Systems, C21, pp. 219235, New York, 1994. 2. T. C. Wong, J. W. Mark, K. C. Chua, and B. Kannan, “Delay jitter performance of voice traffic in a cellular wireless ATM network,” Proc. IEEE 55th Veh. Technol. Conf.Spring 2002, vol. 1, pp. 9094, May 2002. 3. D. Zhao, X. Shen, and J. W. Mark, “QoS performance bounds and efficient connection admission control for heterogeneous services in wireless cellular networks,” Wireless Networks, vol. 8, pp.8595, 2002. 4. C.S. Chang, K.C. Chen, M.Y. You, and J.F. Chang, “Guaranteed qualityofservice wireless access to ATM networks,” IEEE J. Selected Areas in Commun., vol. 15, no. 1, Jan. 1997. 5. D. Zhao, X. Shen, and J. W. Mark, “Efficient call admission control for heterogenous services in wireless mobile ATM networks,” IEEE Commun. Mag., vol. 38, pp. 72 78, Oct. 2000. 6. W. K. Wong and V. C. M. Leung, “Scheduling for integrated services in next generation packet broadcast networks,” Proc. IEEE Conf. Wireless Commun. and Netw., vol. 3, pp. 12781282, Sept. 1999. 84 7. S. Marwaha, C. K. Tham, and D. Srinivasan, “A novel handover mechanism for wireless mobile ad hoc networks,” Proc. ICCS 2002, vol. 2, pp. 10631067, Nov. 2002. 8. U. Lambrette, L. Bruhl, and H. Meyr, “ARQ protocol performance for a wireless high data rate link,” Proc. IEEE 47th Veh. Technol. Conf.Spring 1997, vol. 3, pp. 1538 1542, May 1997. 9. J.M. Chung and H. M. Soo, “Jitter Analysis of Homogeneous Traffic in Differentiated Services Networks,” IEEE Commun. Lett., vol. 7, no. 3, pp. 130132, Mar. 2003. 10. A. Privalov, and K. Sohraby, “PerStream Jitter Analysis in CBR ATM Multiplexors,” IEEE/ACM Trans. on Netw., vol. 6, no. 2, Apr. 1998. 11. J.M. Chung, H. M. Soo and W.C. Jeong, “Jitter Analysis of Homogeneous Traffic in Wireless Differentiated Services Networks,” Proc. IEEE LANMAN 2004, CA, USA, Apr. 2528, 2004. 12. J. J. Metzner and J.M. Chung, “Efficient Energy Utilization with Time Constraint in Mobile Time Varying Channels,” IEEE Trans. Veh. Technol, vol. 49, no. 4, pp. 1169 1177, July 2000. 13. R. G. Addie, “On the applicability and utility of Gaussian models for broadband traffic,” Proc. IEEE Intl. Conf. on ATM, 1998. 14. P. Mannersalo and I. Norros, “GPS schedulers and Gaussian traffic,” Proc. IEEE INFOCOM, 2002. 15. S. Sarvotham. R. Riedi, and R. Baraniuk, “Connectionlevel Analysis and Modeling of Network Traffic,” IMW’01, CA, Nov. 2001, pp. 99103. 85 16. S. Ma and C. Ji, “Modeling Heterogeneous Netwrok Traffic in Wavelet Domain,” IEEE/ACM Trans. Networking, vol. 9, no. 5, Oct. 2001, pp. 634649. 17. H. Fei and W. Zhimei, “A Novel Traffic Based on Wavelet analysis,” Proc. ICCT 2003, vol. 2, April 2003, pp. 13921395. 18. Petteri Mannersalo, Gaussain and multifractal process in teletraffic theory, 2003. 19. R. G. Addie, “Traffic will be more Gaussian in Future,” Australian Telecom. Networks and Applications Conference. December, Melbourne, 1996. 20. R. G. Addie, On weak convergence of longrange dependent traffic processes, Technical Report SCMC9816, University of Soutern Queensland, 1998. 21. Damon Wischik, “Implications of longrange dependence,” notes on the implications of longrange dependence for optical networks, Feb. 2001. 22. R. G. Addie, “On the weak convergence of long range dependent traffic process,” Proc. of the International Workshop on Long Range Dependent, Jan. 1997. 23. P. Mannersalo and I. Norros, “GPS schedulers and Gaussian traffic,” in Proc. IEEE INFOCOM, 2002. 24. R. G. Addie, “On the applicability and utility of Gaussian models for broadband traffic,” Proc. IEEE Intl. Conf. on ATM, 1998. 25. J. Choe and N. B. Shroff, “A centrallimittheorembased approach for analyzing queue behavior in highspeed networks,” IEEE/ACM Trans. On Networking, vol. 6, no. 5, Oct. 1998, pp 659671. 26. J. Choe and N. B. Shroff, “ A new method to determine the queue length distribution at an ATM multiplexer,” in Proc. IEEE INFOCOM, 1997, pp. 550557. 86 27. R. G. Addie, M. Zukerman, and T. D. Neame. “Broadband traffic modeling: simple solutions to hard problems,” IEEE Communications Magazine, August. 1998, pp 88 95. 28. J. Abate, G. L. Choudhury, and W. Whitt, “Exponential approximations for tail probabilities in queuesI: Waiting times,” Oper. Res., vol. 43, no. 5, pp. 885901, 1995. 29. R. G. Addie and M. Zukerman, “An approximation for performance evaluation of stationary single server queues,” IEEE Trans. Commun., vol. 42, pp. 31503160. 30. R. Guerin, H. Ahmad, and M. Naghshineh, “Equivalent capacity and its application to bandwidth allocation in highspeed networks,” IEEE J. Select. Areas Commun., vol. 9, pp. 968981, Sept. 1991. 31. A. Simonian, “Stationary analysis of a fluid queue with input rate varying as an OrnsteinUhlenbeck process,” SIAM J. Appl. Math., vol. 51, pp. 828842. 1991. 32. R. G. Addie, M. Zukerman, and T. Neame, “Performance of a single server queue with self similar input,” IEEE 1995. 33. R. W. Wolff, Stochastic Modeling and the Theory of Queues, Prentice Hall, New Jersey, 1989. 34. Will E. Leland, Murad S. Taqqu, Walter Willinger, and Daniel V. Wilson, “On the selfsimilar nature of Ethernet traffic (extended version),” IEEE/ACM Trans. Net., vol. 2, no.1, Feb. 1994, pp. 115. 35. F. H. P. Fitzek and M. Reisslein, “MPEG4 and H.263 video traces for networks performance evaluation,” IEEE Net., Nov. 2001, pp. 4054. 36. Murad S. Taqqu, http://math.bu.edu/people/murad/methods/index.html 87 37. Arifler and B. L. Evans, “Modeling the selfsimilar behavior of packetized MPEG4 video using waveletbased methods,” Proc. Image Processing 2002, 2002, vol. 1, pp. 848851. 38. Thomas Karagiannis and Michalis Faloutsos, “SELFIS: A Tool For SelfSimilarity and LongRange Dependence Analysis,” 1st Workshop on Fractals and Self Similarity in Data Mining: Issues and Approaches (in KDD) Edmonton, Canada, July 23, 2002. 39. Thomas Karagiannis , http://www.cs.ucr.edu/~tkarag/Selfis/Selfis.html 40. D.R.Avresky, V. Shurbanov, R. Horst and P. Mehra, “Performance Evaluation of ServerNet R SAN under SelfSimilar Traffic,” 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Proc., Apr. 12  16, 1999, San Juan, Puerto Rico, pp. 143147. 41. The trace/data set, Star Wars IVat, http://wwwtkn.ee.tuberlin.de/research/trace/trace.html 42. The trace/data set, Ethernet traffic, http://math.bu.edu/people/murad/methods/index.html 43. R. C. Garcia and J.M. Chung, “Network Anomaly Detection Using A SelfSimilar Traffic Model Report”, NSF DMI0339471, Jan. 31, 2004. 44. W. Stallings, HighSpeed Networks TCP/IP and ATM Design Principles, Prentice Hall, New Jersey, 1998. 45. R. M. Loynes, “The Stability of a Queue with Nonindependent Interarrival and Service Times,” Proc. Cambridge Philos Soc., vol. 58, pp. 497520, 1962. 88 46. R. J. Adler, An Introduction to Continuity Extrema and Related Topics for General Gaussian Processes, Hayward, CA, Institute of Mathematical Statistics, 1990. 47. I. Stoica, S. Shenker, and H. Zhang, “CoreStateless Fair Queueing: A Scalable Architecture to Approximate Fair Bandwidth Allocations in HighSpeed Networks,” IEEE/ACM Trans. Net., vol. 11, no.1, Feb. 2003, pp. 3346. 48. P. Billingsley, Probability and Measure, New York: John Wiley & Sons, 1979. 49. E. Wong and B. Jajek, Stochastic Processes in Engineering Systems, New York: SpringerVerlag, 1985. 50. R. Landry and Ionnis Stavrakakis, “Study of Delay Jitter With and Without Peak Rate Enforcement,” IEEE/ACM Trans. On Commun., vol. 5, no. 4, Aug. 1997, pp. 543 553. 51. C.N. Chuah, R. H. Katz, Network provisioning and resource management for IP telephony, University of California, Berkeley, Report no. UCB/CSD991061, Sept. 1, 1999. 52. L. Zhang, L. Zheng, and K. S. Nge, “Effect of delay and delay jitter on voice/video over IP,” Elsevier Computer Commun., vol. 25, 2002, pp. 863873. 53. X. Xiao and L. M. Ni, “Internet QoS: A Big Picture,” IEEE Network, March/April 1999, pp. 818. 54. S. Blake, D. Black, M. Carlson, E. Davies Z. Wang, and W. Weiss, “An Architecture for Differentiated Services,” RFC 2475, Dec. 1998. 55. T. Li, and Y. Rekhter, “A Provider Architecture for Differentiated Services and Traffic Engineering (PASTE)”, RFC 2430, Oct. 1998. 89 56. Jinwoo Choe, Ness B. Shroff, "Use of the Supremum Distribution of Gaussian Processes in Queueing Analysis with LongRange Dependence and SelfSimilarity," Communications in Statistics  Stochastic Models, v
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Investigation of Delay Jitter of Heterogeneous Traffic in Broadband Networks 
Date  20061201 
Author  Soo, Hooi Miin 
Department  Electrical Engineering 
Document Type  
Full Text Type  Open Access 
Abstract  Scope and methodology of study./ A critical challenge for both wired and wireless networking vendors and carrier companies is to be able to accurately estimate the quality of service (QoS) that will be provided based on the network architecture, router/switch topology, and protocol applied. As a result, this thesis focuses on the theoretical analysis of QoS parameters in term of interarrival jitter in differentiated services networks by deploying analytic/mathematical modeling technique and queueing theory, where the analytic model is expressed in terms of a set of equations that can be solved to yield the desired delay jitter parameter. In wireless networks with homogeneous traffic, the effects on the delay jitter in reference to the priority control scheme of the ARQ traffic for the two cases of: (1)�the ARQ traffic has a priority over the original transmission traffic; and (2)�the ARQ traffic has no priority over the original transmission traffic are evaluated. In wired broadband networks with heterogeneous traffic, the jitter analysis is conducted and the algorithm to control its effect is also developed. Findings and conclusions./ First, the results show that high priority packets always maintain the minimum interarrival jitter, which will not be affected even in heavy load situation. Second, the Gaussian traffic modeling is applied using the MVA approach to conduct the queue length analysis, and then the jitter analysis in heterogeneous broadband networks is investigated. While for wireless networks with homogeneous traffic, binomial distribution is used to conduct the queue length analysis, which is sufficient and relatively easy compared to heterogeneous traffic. Third, develop a service discipline called the tagged stream adaptive distortionreducing peak outputrate enforcing to control and avoid the delay jitter increases without bound in heterogeneous broadband networks. Finally, through the analysis provided, the differential services, was proved not only viable, but also effective to control delay jitter. The analytic models that serve as guidelines to assist network system designers in controlling the QoS requested by customer in term of delay jitter. 
Note  Dissertation 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  INVESTIGATION OF DELAY JITTER OF HETEROGENEOUS TRAFFIC IN BROADBAND NETWORKS By HOOI MIIN SOO Bachelor of Science in Electrical Engineering Oklahoma State University Stillwater, Oklahoma 2000 Master of Science in Electrical Engineering Oklahoma State University Stillwater, Oklahoma 2003 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY in Electrical Engineering Dec 2006 ii INVESTIGATION OF DELAY JITTER OF HETEROGENEOUS TRAFFIC IN BROADBAND NETWORKS Thesis Approved: Dr. JongMoon Chung Dr. Keith A. Teague Thesis Advisor Dean of the Graduate Collage Dr. Charles F. Bunting Dr. Weili Zhang Dr. Venkatesh Sarangan Dr. A. Gordon Emslie iii PREFACE There is a great demand for wired and wireless network architectures to support a variety of applications with very high speed communication. Nowadays, the pace of our business and social lives has created a great demand for not only instant transferring and accessing various kinds of data by a click on the mouse (i.e. digitized voice and video, file transfers, ecommerce, transactions, email, telnet, web browsing and multicast), but also for reliable and better quality of Internet service. As a result, quality of service (QoS) currently becomes an issue of concern for wide area network (WAN) telecommunications providers or backbone carriers. For instance, what is the required bandwidth for the local area network (LAN) or wide area network (WAN) to provide sufficient capacity for video transferring with desired minimum level jitter? A critical challenge for both wired and wireless networking vendors and carrier companies is to be able to accurately estimate the quality of service (QoS) that will be provided based on the network architecture, router/switch topology, and protocol applied. The variation in QoS performance based on the priority assignment is of significant importance, due to the fact that the differentiated services (DiffServ) capable networks should be able to effectively control QoS through classifying traffic according to desired service level (prioritize the data flows) and marking the packets so that the routers can recognize the prioritized packet. We need a tool to investigate whether the packet prioritization could truly reduce the delay jitter or not. iv Therefore, the main objective of this study is to provide a theoretical analysis of delay jitter, which investigates the issues of traffic jitter characteristic in the homogenous wireless communication and heterogeneous wired networks deploying different priority scheduling algorithms. Although simulation can be a powerful tool, an engineer must understand the mathematical model underlying each program model to be applied correctly. In addition, one may not afford an extensive simulation, which requires an extensive data mining process. On the other hand, a mathematical formula is much easier to use compared to using a simulation model. Thus, the efficient way is to use a simulation tool in combination with a probably less realistic mathematical/analytic model. Plan of this thesis This thesis is organized as follows. In Chapter 1, an overview of this thesis is provided, which states why the proposed methodology is important and how it may contribute to designing and planning of internetworking system. Literature review on WAN networks and Internet traffic is given in Chapter 2, where the challenge of the heterogeneous traffic modeling compared to the homogeneous traffic modeling is discussed. The understanding of the WAN networks characteristics is needed to construct the analytic model. Chapter 3 provides mathematical derivations for the perclass jitter characteristic of a wireless network with automatic repeat request (ARQ) error control and headofline (HOL) priority scheduling. The derivations provide a direct method to analyze/evaluate the perclass jitter based on the DiffServ network and protocol parameters. In Chapter 4, the Gaussian traffic modeling combining with Maximum v Variance Approach to conduct the queue length analysis, which further apply in heterogeneous traffic jitter analysis of multiple priority queues.. The conclusion of this thesis is in Chapter 5, which summarizes the essential elements in order to provide guidelines for network designers trying to meet engineering specifications of performance deliverables. The references list is provided in Reference section. The main contributions of this dissertation are as follow: 1. Chapter 3 • Derive mathematical equations, which to be able to provide a mathematical tool to analyze the homogeneous traffic in wireless networks with adequate accuracy. • Propose a call admission control (CAC) scheme to improve the jitter performance. 2. Chapter 4 • Derive mathematical equations, which to be able to provide mathematical tool to analyze the heterogeneous traffic in wired broadband networks with adequate accuracy. Simulation is done to show the accuracy of the mathematical model. • Propose an adaptive distortionreducing peak outputrate enforcing (APORE) scheme to control/improve the jitter performance. vi ACKNOWLEDGMENTS First, I wish to express my heartfelt thanks to my major advisor, Dr. JongMoon Chung, for his encouragement, guidance, valuable discussions and advice throughout this work. I extend my sincere appreciation to my other committee members Dr. Weili Zhang, Dr. Charles F. Bunting and Dr. Venkatesh Sarangan, for their guidance. I extend my genuine gratitude to Dr. Keith A. Teague for serving as my dissertation defense chair. I wish to express my special appreciation to my family, my parent, for their unlimited and continuing love, encouragement, support and sacrifice. Moreover, I am sincerely thankful to my husband, Mr. Lee who has been always wonderfully encouraging me through out this work. Without them, I would not have come this far. Last but not the least, I would like to thank all that have assisting me in accomplishing this work. vii TABLE OF CONTENTS Chapter Page Chapter 1............................................................................................................................. 1 1.1 Overview............................................................................................................... 1 1.2 Delay Jitter Analysis Methodology ...................................................................... 6 1.3 Queueing and Teletraffic Theory Applied in HighSpeed Wide Area Networks (WANs) with Heterogeneous Type Traffic ................................................................ 8 1.4 Approximations for the Queue Length Distribution Gaussian Model for Broadband Traffic..................................................................................................... 15 1.4.1 SingleAsymptotic Upper Bound ................................................................... 16 1.4.2 Maximum Variance Asymptotic (MVA)........................................................ 17 1.4.3 MVA Lower Bound ....................................................................................... 18 1.4.4 MVA Upper Bound ....................................................................................... 18 1.4.5 MVA general approach (not bound) .............................................................. 19 1.4.6 Long Range Dependent Gaussian model: The Discrete Gaussian Model ...... 20 1.4.7 The Continuous Gaussian Model.................................................................... 21 1.4.8 Large twostage models: Heavy Traffic ......................................................... 22 Chapter 2........................................................................................................................... 23 2.1 Introduction: Analyzing traffic traces................................................................. 23 2.2 Aggregated Variance Method............................................................................. 23 2.2.1 Description and Methodology ......................................................................... 23 2.2.1 Simulation Results .......................................................................................... 26 2.2.3 Simulation Flow Chart..................................................................................... 28 2.3 R/S Method ......................................................................................................... 29 2.3.1 Description and Methodology ......................................................................... 29 2.3.2 Simulation Results ........................................................................................... 30 2.3.3 Simulation Flow Chart..................................................................................... 32 2.4 Estimating the Hurst Exponent using Wavelet Spectral Density ....................... 33 2.4.1 Description and Methodology ......................................................................... 33 2.4.2 Simulation Results ........................................................................................... 35 2.4.3 Simulation Flow Chart..................................................................................... 36 2.5 Observation and Discussion................................................................................ 37 Chapter 3........................................................................................................................... 39 3.1 Abstract............................................................................................................... 39 3.2 Introduction......................................................................................................... 39 3.3 Analytical Model ................................................................................................ 40 3.3.1 Network and System Model Assumptions....................................................... 40 viii 3.3.2 Theoretical Formulations................................................................................. 42 3.3.3 Jitter Analysis with NonPriority ARQ Traffic ............................................... 45 3.3.4 Jitter Analysis with Priority ARQ Traffic........................................................ 46 3.4 Discussions and Conclusions.............................................................................. 49 Chapter 4........................................................................................................................... 51 4.1 Introduction......................................................................................................... 53 4.2 Discrete Time Fluid Queue Model and Extreme Value [26].............................. 55 4.3 Jitter Analysis of Heterogeneous Traffic Networks ........................................... 65 4.3.1 Simulation and Numerical Study..................................................................... 67 4.4 Jitter Analysis of Heterogeneous Traffic Networks with Differentiated Services ………………………………………………………………………………..72 4.4.1 Simulation and Numerical Study..................................................................... 78 Chapter 5........................................................................................................................... 81 Conclusions…………………………………………………………………………81 Reference ………………………………………………………………………………...83 ix LIST OF FIGURES Figure Page Fig. 1.1 The actual Ethernet traffic trace in original time scale (time unit = 1ms)........... 13 Fig. 1.2 The Ethernet traffic trace is aggregated 10 folds (time unit = 0.01s).................. 13 Fig. 1.3 Original Ethernet traffic...................................................................................... 14 Fig. 1.4 Aggregated 100 Ethernet traffic flows. ............................................................... 14 Fig. 2.1 The relationship between aggregated variance equation and the least squares line. .................................................................................................................................. 25 Fig 2.2 This figure shows that Ethernet traffic is very selfsimilar, which is indicated by a fairly large H value................................................................................................. 27 Fig 2.3 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. ............................................................... 27 Fig 2.4 This figure shows that the data set is selfsimilar, and the level of selfsimilarity is indicated by the H value. Here, K = 10 and upto log10(d)=3.4 is used. ................ 31 Fig 2.5 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. K=10 and up to log10(d)=3.4 is used..... 31 Fig 2.6 The figure shows that Ethernet traffic is selfsimilar, and the level of selfsimilarity is indicated by the H value. ...................................................................... 35 Fig 2.7 The figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. ............................................................... 35 Fig 2.8 The comparison between the three methods is shown, where the level of selfsimilarity is indicated by the H value. The estimation range is between (0.82, 0.93) for Ethernet traffic for low m aggregated level, where all the three methods have proved that the Ethernet traffic is very selfsimilar. ................................................. 38 Fig. 3.1 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 10%. The solid line represents the nonpriority ARQ scheme, and the dotted line represents the priority ARQ scheme. ........................... 47 Fig. 3.2 Comparison between wireless networks nonpriority ARQ scheme with Pe = 20%. .......................................................................................................................... 48 Fig. 3.3 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 1% and 10% for class 1 through class 5............................ 48 Fig. 4.1 Plot of variance of Zm versus m. The variance reaches a maximum value and then begins to converge to 0. The parameters used are q=1000, μ=0.61, N=100, each individual arrival process with mean s X = 10 cells/sec, and autocovariance l Cs l e ( ) = 100 −0.04 ....................................................................................................... 64 x Fig. 4.2 Comparison between the approximation equation and the simulation results of the jitter distribution for utilization of 50% and 90% with 95% CI, for the case of T = 10. .......................................................................................................................... 70 Fig. 4.3 Distribution of jitter for the comparison between utilization of 50% and 70%, and for the comparison between T = 10 and 20............................................................... 71 Fig. 4.4 Distribution of jitter for utilization of 60%, T=10, and various Amin values with 95% CI, and T = 10................................................................................................... 79 xi LIST OF FLOWCHARTS Figure Page Flowchart 1 The simulation algorithm used to calculate delay jitter at a multiplexer ……………………………………………………….... 70 1 Chapter 1 Introduction 1.1 Overview Delay jitter is one of the most important parameters in quality of service (QoS) that indicates the level of variation of traffic services of realtime data transfer. In realtime wired/wireless data communication, delay jitter is defined as the difference in time delay of the arrival at the destination that each transmitted packet experiences commonly, which is also simply referred to as jitter. Delay jitter has been successfully analyzed for the performance of asynchronous transfer mode (ATM) network applications, in order to accurately estimate the quality of service (QoS) in terms of jitter that will be provided based on the network architecture, router/switch topology, and protocol applied. Several papers [2], [3], [4], and [5] have successfully analyzed the performance of the delay jitter in order to be more easily, consistently, and effectively implemented in various ATM network applications. In [2], the analysis of delay jitter was conducted on voice traffic using an exponential On/Off source in cellular wireless ATM network. In [3], the jitter bound for various classes of constant bit rate (CBR) traffic is analyzed, where the performance bound is used in the call/connection admission control (CAC) 2 mechanism. The multiple access control topology applied in [3] is based on a nonpreemptive priority polling scheme [4]. The papers of [6], [7], and [8] address delay jitter for more general type of wireless networks, rather than ATM. In [6], the time division multiple access (TDMA)/time division duplex (TDD) scheduling scheme is used. In [7], jitter is analyzed for mobile ad hoc networks (MANET) based on the ad hoc ondemand distance vector (AODV) routing protocol, where the authors propose a novel handover mechanism. Both [6] and [7] provide results on jitter performance analysis based on computer simulation for the wireless network models. In [8], the authors provide a jitter analysis on wireless networks involving automatic retransmission request (ARQ) error recovery, where the delay jitter is calculated using the windowlength generating function and the numerical results are verified through simulation. In [9], the jitter of homogeneous traffic in reference to the different priority classes has been analyzed. The delay jitter research of [9] extends the results of [1] and [10] for DiffServ networks, but all three papers do not consider the channel error probability or the ARQ error control scheme, which makes the results difficult to apply to wireless networking applications. Therefore, Chapter 3 the mathematical derivations to analyze the delay jitter performance of homogenous wireless networks that apply ARQ error recovery with time constraints have been developed, which resulted in [11]. In [11], we attempt to provide a novel analysis of the perclass jitter performance of DiffServ networks based on wireless channels that experience packet errors, assuming a nonpreemptive headoftheline (HOL) priority scheme. The derivations provide a direct method to analyze/evaluate the perclass jitter based on the DiffServ network, retransmission time constraints, and network packet error parameters 3 [12]. In addition, we evaluated the effects on the delay jitter in reference to the priority control scheme of the ARQ traffic for the two cases of: 1) the ARQ traffic has a priority over the original transmission traffic; and 2) the ARQ traffic has no priority over the original transmission traffic. As the next step, this homogenous jitter study is extended to heterogeneous wired and wireless network jitter analysis by deriving a general approach, which is going to be covered in this dissertation. In general, WAN traffic is often characterized by a diverse mix of heterogeneous data streams (e.g., multimedia, digitized voice, Internet, video, teleconferencing and many newly evolved applications), the periodicity of the individual streams is different from each other. In other words, in the heterogeneous environment, the input traffic streams are a superposition of data packet streams from different data sources with different periods. To further investigate heterogeneous jitter characteristics, first, a study is conducted on wired networks, and then the focus will be extended to wireless networks, which requires a longer time period due to its complexity. The studies that have been conducted and completed (but not limited to) in this dissertation are as follows: • Various possible traffic modeling techniques have been investigated • Diverse statistical properties of heterogeneous wireless networks is evaluated. • The traffic modeling combined with heterogeneous jitter analysis. Traffic analysis can assist one in developing a good traffic model for analyzing the jitter characteristic of heterogeneous wireless networks, where the results could serve as a tool to aid the network engineers and developers in wireless and wired network planning and architecture structuring. 4 The models, such as Markov Modulated Poisson Process (MMPP) and M/M/1/B have been applied in wireless network traffic modeling. In wired or wireless networks, the Poisson arrival may not be an appropriate model since actual networks traffic is very bursty in nature due to its longrange dependency (LRD) and selfsimilar characteristics. Numerous studies have found that aggregated traffic at a node (router, switch for wired networks case) or base station (for wireless networks case) exhibit LRD, and such traffic can be very bursty. Thus, many broadband traffic studies have evolved around Gaussian, and they show that Gaussian models indeed provide a good approximation to networks traffic if the aggregated traffic is sufficiently large [13],[14]. Hence, heterogeneous wireless network traffic processes can be modeled as a Gaussian process, where some of these models have been discussed in Chapter 4. In extension of the MVA approach, we can derive the MVA lower bound and upper bound to provide a boundary conditions on the traffic. Another popular approach in traffic modeling is by using Fractional Gaussian Noise (fGN), which is a stationary Gaussian process with LRD. Recent research [15][16][17] models the heterogeneous networks traffic in the wavelet domain, where selfsimilar traffic exhibits longrangedependent (LRD) correlations and nonGaussian marginal distribution [15]; it shows that the aggregated traffic can be decomposed into those two groups [15]. In conclusion, the following is the summary of the work conducted in this dissertation: 1. Investigate the characteristics of the wireless networks that applying retransmission request (ARQ) with homogeneous type traffic. 5 2. Investigate the issues of traffic jitter characteristic in heterogeneous wired communication networks deploying different scheduling algorithms. 3. The emphasis of this dissertation is to investigate the various possible traffic modeling techniques and evaluate the challenges in characterizing the diverse statistical properties of heterogeneous wireless networks. 4. Apply the Gaussian traffic modeling using MVA approach to conduct the queue length analysis, which will be further used in heterogeneous jitter analysis. 5. Analyze the difference between jitter probability of multiple priority queues and servers. The contributions of this dissertation are as follow: 1. Evaluate the characteristics of the wireless networks that applying retransmission request (ARQ) with homogeneous type traffic. 2. Evaluate the characteristics of the diverse statistical properties of wired networks with heterogeneous type traffic. 3. Investigate various possible traffic modeling techniques. 4. Apply the Gaussian traffic modeling using the MVA approach to analyze the queue length, and further generalize the heterogeneous jitter analysis. 5. Analyze the jitter process and the jitter probability distribution of multi priority class traffic. 6. Propose a scheme to control and improve networks performance in term of jitter. In order to do these, we have to first: • Study the traffic characteristics • Investigate the traffic modeling techniques 6 Then, we’ll be able to analyze the jitter process, and propose a scheme to control it. 1.2 Delay Jitter Analysis Methodology In realtime wired or wireless communications, each transmitted packet may experience a different time delay during arrival at the destination. This variation in delay is often referred to as delay jitter or simply jitter. For instance, let dn represent the packet transmission delay experienced by the nth packet from a tagged stream. Thus, the process of delay jitter between the nth and (n+1)th packet of a tagged stream with respect to data stream original period (interdeparture time between nth and (n+1)th packets transmitted from the source), T, is J n = dn − dn ∀n + , ~ 1 . (1.1) In the steadystate limit n dn = dn =∞ +1 lim , therefore jitter is a zero mean random sequence. Another interpretation of jitter is that it represents the difference in waiting times experienced by successive packets. Hence, we can relate the transmission delay and the queue length (number of packets) ahead of the tagged packet (i.e., n Q represents the number of customers ahead of the nth tagged packet). Let any customer’s service time be equal to one slot and follows firstinfirstout (FIFO) order, Qn = dn (in time slot units). Therefore, (1.1) implies that ~ , 1, 2,... 1 = − = J n Qn+ Qn n . (1.2) To prove this, let the variable n Q denote the number of customers, regardless of their class affiliation, that are waiting for service just ahead of the arrival of nth packet of the reference user. Thus, the nth packet of the reference user begins to enter service at time 7 n n n τ = t + Q . (1.3) Hence, ( ) ( ) ( ) 1 1 1 J t t Q Q T Q n n n n n n n n = − = − + − = + Δ + + + τ τ . (1.4) The normalized jitter with respect to the original data stream period (interdeparture time between nth and (n+1)th packets transmitted from the source), T can be expressed as:: J~n = J n − T = ΔQ(n), n =1, 2,... , where n n def ΔQ n = Q − Q ( ) +1 . (1.5) From (1.5), we can observe the study of jitter can be equivalently changed to the study of the queue size variation ΔQ(n) of pcustomer arrivals, which is the methodology that is going to be applied in this study. We want to find the pmf (probability mass function) of J n ~ , i.e., {~ } f J n , from the queue length distribution f {Qn} . A discretetime approach is used in the delay analysis, where time is slotted. It is assumed that the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. Next, the various traffic modeling techniques are discussed. First, let’s denote the heterogeneous network of steady state queue length distribution as the probability of queue size larger than x, i.e., P(Q > x) . Here, the input traffic at a highspeed multiplexer is characterized by a Gaussian process. Hence, the central limit theorem is applied to the traffic process. In highspeed networks, homogenous (i.i.d) and heterogeneous sources (independent but not identically distributed) are multiplexed at the multiplexer. Here, we are concerned about the delay jitter characteristic in heterogeneous traffic since real network traffic consists of multimedia traffic, which is a mixture of CBR voice, CBR video, real time VBR video, real time VBR voice, time critical data and nontime critical data. In networks, traffic management controls are on the level of traffic aggregates, and 8 not for individual links. Therefore, even though each link is not normally distributed, the aggregated traffic distribution shows Gaussian characteristics. This can be verified by applying the Central Limit Theorem (CLT) that states that summing a large numbers of independent variables with finite variance will converge or weakly converge to a Gaussian random density [22]. The tail of the queue length distribution ( P(Q > x) ) at highspeed multiplexer can be approximated under a variety of Cramer type assumptions (exponentially bounded marginal and autocorrelations of the arrival process). Thus, P(Q > x) of an infinite buffer is asymptotically exponential [26], P(Q > x) ~ Ce−ηx , (1.6) where the positive constant η is called the asymptotic decay rate, and the positive constant C is called the asymptotic constant, in which (1.6) is suggested for large values of x [2530]. In section 1.4, the discussion of some popular approaches to find the queue length distribution by applying Gaussian/Normal process is provided. 1.3 Queueing and Teletraffic Theory Applied in HighSpeed Wide Area Networks (WANs) with Heterogeneous Type Traffic Due to the fast growth of telecommunication technology over the last past ten years (based on demands for better mobile telephony and Internet services) there have been many studies on traffic behavior and network architechture. Hence, traffic modeling is one of the key issues in traffic engineering for efficient designing and controlling of 9 networks, where a mathematical model analysis of a complex system yields useful information. Here, Queueing theory and Teletraffic theory are applied as a tool for traffic modeling. Queueing theory concerns the usage of a network resource for which the demands are random. When the resource is not available to the users, the requested service demand is queued or declined. While Teletraffic theory is a branch of engineering mathematics that relies heavily (but not solely on) queueing theory, it can be viewed commonly as queueing theory applied for telecommunication systems. It is applied for evaluating network designs, performance, stability and routing protocols, and optimizing network resources through mathematical analysis and simulation. Hence, the following topics are essential in traffic modeling for networks: • Characterization of Internet traffic • Longrange dependent traffic models (LRD) • Heavytailed distribution traffic models • Gaussian traffic models • Effective bandwidth model • Traffic models for mobile networks • Traffic measurements • Traffic estimation and prediction Poisson modeling fails to properly characterize multiplexed network traffic, due to the fact that Internet and Wide Area Network (WAN) traffic is selfsimilar. The Poisson traffic model severely underestimates burstiness especially when traffic flows multiplex/aggregate. The selfsimilar characteristic can be analyzed using statistical 10 analytic tools, and the most popular methods are R/S plot, VarianceTime plot, Wavelet method, Periodogram method, and Whittle estimator. The several traffic models that are being proposed are Pareto On/Off model, M/G/∞ input model (infinite source Poisson model with heavytailed service/processing time), Fractional Brownian Motion (fBm), Fractional AutoRegressive Integrated Moving Average (ARIMA) process, which capture the heavytailed characteristic (burstiness) of selfsimilar traffic. Here, the Hurst parameter (H) is the measure of burstiness. Discretetime definition of selfsimilarity is a stationary times processes X, and we define the maggregated time series X (m) = {X (m) (k), k = 0,1,2,L} and X (m) (k) by averaging the original times series X over a nonoverlapping block of size m, which is given in (1). Thus, a process X is said to be selfsimilar with parameter β (0 <β <1) if for all m = 1, 2, … we have the following definitions: Exactly secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (1.7) Autocorrelation: ( ) ( ) ( ) R k R k X m X = . Asymptotically secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (1.8) Autocorrelation: ( ) ( ) ( ) R k R k X m X → as m →∞ . Eq. (1.7) and (1.8) define that selfsimilarity characteristic exists as the autocorrelation of the aggregated process has the same form as the original process, where the degree of variability or burstiness at different time scales will be the same. Fig. 1.1 and 1.2 show a graphical representation of selfsimilarity, where we can see that the networks traffic is very bursty and selfsimilar across all time scales. That is Fig. 1.1 and Fig. 1.2 look 11 similar to one another in a distribution sense, all of the plots involve a fair amount of burtiness. The traffic pattern in Fig. 1.2, which sampled at large scale (the data are aggregated over 10 folds time scale, i.e., from 1ms to 0.01s) does not smooth out. Thus, the other models such as Markov Modulated Poisson Process (MMPP) and M/M/1/B that can be applied in wireless network traffic modeling may not be a good fit. In wired or wireless networks, the Poisson arrival may not be an appropriate model since the networks traffic is very bursty in nature due to its longrange dependency (LRD) and selfsimilarity characteristics. Numerous studies have found that aggregated traffic at a node (router, switch for wired networks case) or base station (for wireless networks case) exhibit LRD, and such traffic are very bursty. Thus, many broadband traffic studies have evolved around Gaussian, and they show that Gaussian models indeed provide a good approximation to network traffic if the aggregated traffic is sufficiently large [13][14]. Hence, heterogeneous wireless network traffic processes can be modeled as a Gaussian process, where some of these models will be discussed in section 1.4. In extension of the MVA approach, we can derive the MVA Lower Bound and Upper Bound to provide a boundary condition on the traffic. Another popular approach in traffic modeling is by using Fractional Gaussian Noise (fGN), which is a stationary Gaussian process with LRD. Recent research [1517] models the heterogeneous networks traffic in the wavelet domain, where selfsimilar traffic exhibits longrangedependent (LRD) correlation and a nonGaussian marginal distribution [15]. In recent years, the emerging Gaussian model is believed to be the possible model for highspeed networks, where traffic flows in the networks are highly 12 multiplexed. The Gaussian model can be LRD by including H in the modeling process. The main reasons to consider Gaussian traffic modeling are Central Limit Theorem (CLT) and the Functional Central Limit Theorem (FCLT) [18]. As the network grows, the number of multiplexed/aggregated traffic flows at a node (e.g., router, switch) increase, and the shape of traffic distribution will become closer and closer to Gaussian [19][20]. The aggregated input traffic queueing processes will weakly converge to a Gaussian process [19][20], which is shown in Fig. 1.3 and 1.4. These two plots display a normal probability plot of the data, where if the data does come from a normal distribution, the plot will appear linear. As the traffic flows aggregate, the traffic becomes closer and closer to a Gaussian process, which illustrated in Fig. 1.4. The aggregated traffic is just as bursty as before, where it has the exactly same Hurst parameter H, but it is smoother [21]. Let a traffic process denotes as X, the aggregate of L independent copies of X is X ⊕L [21]. To demonstrate this, Fig. 1.4 shows the trace of aggregated process (byte.txt, a data set provided at Murad S. Taqqu’s website is used; the data is splitting up into nonoverlapping blocks, and then looking at the aggregation of two or more of those blocks). 13 Fig. 1.1 The actual Ethernet traffic trace in original time scale (time unit = 1ms). Fig. 1.2 The Ethernet traffic trace is aggregated 10 folds (time unit = 0.01s). 14 Fig. 1.3 Original Ethernet traffic. Fig. 1.4 Aggregated 100 Ethernet traffic flows. 15 1.4 Approximations for the Queue Length Distribution Gaussian Model for Broadband Traffic In highspeed networks, the aggregated traffic becomes close to Gaussian characteristic by applying Central Limit Theorem (CLT) that stated that summing a large number of independent variables with finite variance is going to converge or weakly converge to a Gaussian random variable [22]. The Gaussian model is useful for two main reasons. First, any stationary Gaussian process can be completely characterized by its mean and autocovariance. Second, the highspeed networks of today are highly complex and traffic is usually the superposition of some thousand network applications. By applying CLT, the aggregated traffic can be modeled as a Gaussian process; even though each single independent data source does not follow a Gaussian distribution. The only defect in this model is that there is a positive probability of a negative quantity of arriving traffic, which is impossible in real traffic. This significant weakness is counterbalanced by the fact that the CLT appeals as more and more traffic streams are aggregated to share a link, traffic becomes more Gaussian, and the case that the amount of negative traffic reduces as traffic is aggregated [24]. Many broadband traffic studies have evolved around Gaussian, and they show that Gaussian models indeed provide a good approximation to network traffic if the aggregated traffic is sufficiently large. In [22], [23], and [24], results show that the Gaussian traffic models could be the precise tool for analyzing the highspeed networks. Moreover, the Gaussian model is also a good fit for highspeed networks with 16 differentiated services (DiffServ). In differentiated services networks, traffic management controls are on the level of traffic aggregates, and not for individual links [23]. The input traffic at a highspeed multiplexer can be characterized by Gaussian processes. Thus, the tail of the queue length distribution ( P(Q > x) ) at highspeed multiplexer can be approximated under a variety of Cramer type assumptions (exponentially bounded marginal and autocorrelations of the arrival process). Thus, P(Q > x) of an infinite buffer is asymptotically exponential [26], P(Q > x) ~ Ce−ηx , (1.9) where the positive constant η is called the asymptotic decay rate, and the positive constant C is called the asymptotic constant. Equation (1.9) is suggested for large values of x [25][27][28][29][30]. 1.4.1 SingleAsymptotic Upper Bound [25] The singleasymptotic upper bound can be represented as ⎥⎦ ⎤ ⎢⎣ ⎡ ⎟⎠ ⎞ ⎜⎝ ⎛ + ⎟⎠ ⎞ ⎜⎝ > ≤ − ⎛ S x kD S P(Q x) exp 2k (1.10) where k, S, and D are defined by the first two moments of a single Gaussian input process and the service rate μ per input, Σ∞ = = 1 : 2 ( ) l D lCγ l [25]. TheCγ (l) denotes the autocovariance function of a stationary Gaussian net input processγ n =λn − μ , where γ n =λn − μ is the net amount of fluid input at time n and (x)+ := max{0, x} [25]. Since the mean and autocovariance function of X n can be computed in term of 17 k := −E{ 0} and C (l) as E{X n ) = −kn, γ γ and Σ Σ = = = 2 − 2 1 1 2 1 1 1 2 1 ( , ) ( ) n l n X l C n n C l l γ by a change of variable l = l2 − l1 , the variance can be expressed as a weighted sum of Cγ (l) , i.e., Σ = = + 1 1 Var{ } (0) 2 ( ) ( ) nn γ l γ X nC nl C l [25]. 1.4.2 Maximum Variance Asymptotic (MVA)[25][26] For a discretetime fluid queue, the amount of fluid in the buffer is denoted by Qn , which can be defined using Lindley’s equation [25]: + − Qn = (Qn 1 +γ n ) (1.11) where γ n =λn − μ is the net amount of fluid input at time n less the capacity μ , and (x)+ := max{0, x} [25]. Let X n represents a stochastic process {X : n = 0,1,2,L} n defined by Σ = − = n X n m m 1 : γ , the backward accumulation process (Note that the first two moment of X n is defined as above in SingleAsymptotic Upper Bound section). Assume stationary and ergodicity of γ n , and the stability condition, i.e., E{γ n}< 0 , the distribution of Qn converges to a steadystate queue distribution. Hence, the aggregate arrival process, λn , can be characterized by a stationary Gaussian process. Thus, the steadystate queue length distribution can be represented as P Q x P(X n x) n > = > ≥0 ( ) sup . (1.12) The function P(X n > x)achieves its maximum at a finite value of n nx = ) : P Q x P(X x) nx ( > ) = ) > (1.13) 18 where in a Gaussian process, the time scale nx ) is also the time at which 2 σ x,n achieves its maximum value 2 σ x . 1.4.3 MVA Lower Bound [25] By studying the asymptotic behavior of P(Q > x) , and with α =1 corresponding to the lower bound, (for a Gaussian process) the lower bound of P(Q > x) can be written in terms of ∫∞ = − z ψ (z) : 1 2π exp[ ( y 2 / 2)]dy (the tail function of the standard Gaussian distribution) as ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ > ≥ 2 ( ) x P Q x x σ ψ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − 2 2 2 exp 2 ~ x x x πx σ σ . (1.14) 1.4.4 MVA Upper Bound [25] The approach is to find a function of 2 z = x σ x , which resembles ψ (z) such that is similar to the asymptotic upper bound (1.11), ψ (z) = exp[−(z 2 / 2)] . (1.15) 19 1.4.5 MVA general approach (not bound) [26] In discrete time queue, the extreme value distribution of X n is determined by determining the extreme value distribution of a new stochastic process n Z , {Z : n = 0,1,2,L} n , which is defined as ((1 ) ) (1 ) n k X n Z n n − + − − = μ ρ μ ρ (1.16) where n Z is a normal process with E{Zn} = 0 , and 2 ((1 ) )2 Var{ } Var{ } n k X Z n n − + = μ ρ . (1.17) Thus, the steadystate queue distribution can be rewritten as [26] P Q x P(X n x) n > = > ≥0 ( ) sup sup ( 1) 0 = > ≥ n n P Z . (1.18) The Var{Zn} achieves its maximum value for n = nˆx [26] sup ( ) ( ˆ ) 0 P Zn u P Zn u n > ≈ > ≥ (1.19) for sufficiently large u. If Var{Zn}<<1 , then by using the approximation in (1.19) to obtain [26] P(Q > x) ≈ P(Znˆ >1). (1.20) Thus, the tail probability P(Q > x) can be defined as ( ) ∫∞ ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ > ≈ > = − max 1 2 ˆ 2 exp 2 ( ) 1 1 σ π P Q x P Zn x dx (1.21) 20 where σ max is the maximum value of Var{Zn} , which can be computed by determining the maximum value of Var{Zn} , 2 2 1 1 ((1 ) ) 0 2 Var{ } n k nC ( ) (nl)C (l) Z nγ l γ n − + + = Σ = μ ρ . (1.22) 1.4.6 Long Range Dependent Gaussian model [27] [32]: The Discrete Gaussian Model Assume a FIFO single server queue, and the time is divided into fixedlength sampling intervals (discrete time). The arrival process is considered to be stationary and ergodic, and Gaussian distributed. A discrete time queueing system has k statistically independent, but identical, traffic streams aggregated at a multiplexer. Let time be divided into fixedlength sampling intervals [28]. The amount of queued traffic in a buffer at time n is defined asVn , with standard deviation σ, and net input rate m. H is the Hurst parameter of the input traffic [27]. Under the longrange dependent (LRD) case, the overflow probability (unfinished work distribution) for a Gaussian fractal queue can be approximated by [13][19][22][27][32], ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − > ≈ − × − × − − − − ∞ H H t H m P V t m H H 2 2 2 2 2  (1 )  { } 2 ( , ) exp 2 1  σ ψ σ σ π (1.23) where H is the Hurst parameter of the traffic, Vn denotes the amount of queued traffic in a buffer at time n, σ is the standard deviation of the arriving traffic, m is the net input rate to the buffer (which has to be negative for stability) [13][19][22][27][32]. The function ψ (−m,σ ) represents the mean of the random variable that is normally distributed with mean –m and standard deviation σ [13][19][22][27][32], 21 . 2 2 2 ( , ) 2 2 2 ⎟⎠ ⎞ ⎜⎝ ⎛ = − − π σ σ ψ σ σ m e m erfc m m (1.24) 1.4.7 The Continuous Gaussian Model A superposition of independent Gaussian processes is still a Gaussian processes. Assume FIFO with single server queue. Let us define the cumulative arrival processes of class i, which are independent continuous Gaussian processes with stationary increments, as { } {i} i t i t A = m t + Z [14][27]. The mean input rate is mi and Z{i} is a centered continuous Gaussian process with variance ( ) Var {i} i t v t = Z [14][27]. The server capacity is denoted as c, and the queue with input A{i} is denoted as Q{i} [14][27]. Applying the path space of the Gaussian processes, reproducing kernel Hilbert space, and based on the estimate of the buffer emptiness probability, the lower bound for the aggregated queue distribution can be derived using the 1dimensional normal distribution as [27] ( ) ⎟⎠ ⎞ ⎜⎝ ⎛ − − ≥ ≥ ≥ Σ= − x k i i k t P Q k x P A x c m t x ( ) 1 {1, , } {1, , } 0 K K ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − = Σ Σ = = k i i x x k i i v t c m t 1 1 ( ) ( ) φ (1.25) where < 0 x t is the value of t which minimize the expression [14][27] 22 . ( ) ( ( )( )) 1 2 1 Σ Σ = = + − − k i i k i i v t x c m t (1.26) 1.4.8 Large twostage models: Heavy Traffic Let the arrival rate be λ > 0 , service rate μ > 0 , and offered load m = λ μ . Assume the arrival process is asymptotically normal. Let l N be a stationary number of customers in the system that has l channels. Then N is approximately normal with mean m and variance mz when m is large. The distribution of l N can be obtained as [chapter 7 of 33] ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − ≈ mz i m mz P(N (i)) (1 mz )ϕ i m φ l , (1.27) where ϕ is the standard normal density function, and φ is the standard normal distribution [chapter 1 of 33] exp( ( )2 / 2 2 ) 2 ( ) 1 μ σ σ π ϕ x = − x − . (1.28) In this chapter, the motivations of studying the jitter process and its concept have been discussed. The selfsimilarity characteristic of broadband networks traffic have also been studied. Then, several popular traffic modeling techniques for modeling the networks with heterogeneous type traffic have been investigated. In the next chapter, the methods used for determining the selfsimilarity of a network are being examined. 23 Chapter 2 Wide Area Networks and Internet Traffic Analysis 2.1 Introduction: Analyzing traffic traces The statistical analysis is applied to a set of collected data, and then a statistical inference of the data set is made. Here, we are interested in traffic selfsimilarity, which is measured by the Hurst parameter. The methods used to estimate the traffic selfsimilarity by computing the Hurst parameter (H) are: 1. Aggregated Variance 2. R/S Analysis 3. Wavelet Estimate 2.2 Aggregated Variance Method 2.2.1 Description and Methodology Aggregated variance method is also referred to as variancetime analysis. • For each m = 1, 2, 3, …, data is divided into nonoverlapping blocks of size m to obtain the aggregated process X (m) . For instance, if the given input data set has length N: X i k N m m X k km i k m m ( ) 1 ( ), 1,2, , / ( 1) 1 ( ) Σ = − + = = K . (2.1) 24 • For the variance vs. time loglog plot, the variance is first normalized to the corresponding sample variance (Thus, the estimate βˆ of the asymptotic slope will fall between –1 and 0, which suggests selfsimilarity). Then, we need to plot log10(var( X (m) )) versus log10(m). The variance is computed as ( ) Σ= = − N m k m X m k X N m X 1 var( ( ) ) 1 ( ) ( ) 2 . ) (2.2) Recall: The discretetime definition of selfsimilarity is a stationary times X, and we define the maggregated time series X (m) = {X (m) (k), k = 0,1,2,L} and X (m) (k) by averaging the original times series X over nonoverlapping block of size m, which is given in (2.1). Thus, a process X is said to be selfsimilar with parameter β (0 <β <1) if for all m = 1, 2, … we have the following: Exactly secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (2.3.a) Autocorrelation: ( ) ( ) ( ) R k R k X m X = . Asymptotically secondorder selfsimilar: Variance: mβ var(X (m) ) = var(X ) (2.3.b) Autocorrelation: ( ) ( ) ( ) R k R k X m X → as m →∞ . (2.3.a) and (2.3.b) define that selfsimilarity characteristic exists as the autocorrelation of the aggregated process has the same form as the original process, where the degree of variability or burstiness at different time scales will be the same. 25 Simple Least Squares Line Fitting: Now, by taking log10 on both sides of the variance in (2.3): X m [ X ] [m] 10 10 ( ) 10 log [var( )] = log var( ) −β log , and it can be rewritten as log [var( )] log [ ] log [var( )] 10 10 ( ) 10 X m = −β m + X (2.4) and var(X ) =σ 2 is a positive finite constant. Equation (2.4) can be fitted through a simple least squares line equation as y = mx + c . So, we try to fit a line through the points on the loglog plane. The graphical representation is given in Fig 1. Fig. 2.1 The relationship between aggregated variance equation and the least squares line. From the loglog plot, we estimate βˆ by computing the slope of the least line. Then, we can compute H using (6). The slope is formulated: Σ (Σ ) Σ Σ Σ − − = 2 2 ˆ i i i i i i n x x n x y x y β , where n is the number of samples. (2.5) (Note: To avoid computational round off errors (2.5) is used instead of a simple form of (2.4). This has been verified by comparing the results from both equations, with the later underestimating the slope value) x y slope = β c log [var( ( ) )] 10 X m [m] 10 log log [var( )] 10 X Note: the aggregated variance is normalized by the corresponding Statistical computed data point 26 • Hurst parameter is estimated by fitting a simple least squares line through the resulting points in the plane. By ignoring the very lowend and very highend m value, compute the slope ( βˆ ), and then the Hurst parameter (H) is computed as: (β 2) 2 1 β 2 ) ) ) H = + = − . (2.6) (Note: capped symbol means an estimate of the true value.) Simulation Results Ethernet data set: byte.txt (Note: the byte.txt data set (1999) is more recently collected compared to BCpAug89, but the this data set is smaller compared to BCpAug89) is used to plot Fig. 2. According to [34], Ethernet data in 1989 (AUG89 trace) has H ~0.8, and the traffic is more selfsimilar from 1990 onwards with H~0.9 (FEB92 trace during high internet traffic hour of Feb. 1992 with H~0.96 [34]). Fig. 2 shows the same degree of selfsimilarity in the Ethernet traffic of year 1999, which once again confirms that H~(0.90,0.96) for Ethernet traffic in 90’s. This may be due to the popularity of Internet usage, and more applications/services (e.g. digital video streaming, multimedia service) being able to be provided through Internet. The aggregated variance plot of Ethernet traffic is showed in Fig. 2.2. It has the H value 0.9279, which indicates that the traffic do have the selfsimilarity characteristic. 27 Fig 2.2 This figure shows that Ethernet traffic is very selfsimilar, which is indicated by a fairly large H value. Star Wars IV, high quality: Terse_StarWarsIV.dat data set is used to plot Fig. 2.3. Fig 2.3 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. 28 2.2.3 Simulation Flow Chart Begin Aggregate the input data series by dividing its length N into blocks of size m, and then averaging each block. Σ = − + = = km i k m m X i k m X k ( 1) 1 ( ) ( ) 1 ( ) 1, 2,K, N/m Compute its sample variance. ( ) Σ= = − N m k m X m k X N m X / 1 ( ) ( ) ( ) 2 / var 1 Normalize var X (m) corresponding to its sample. Plot the normalized variance log10( var X (m) ) versus log10(m). Fit a straight line (with a slope β =2H2) to the points on the plot. From the slope β (compute β by ignoring very low end and very high end m for more accuracy), and then compute (estimate) the Hurst parameter, where H=1 β/2. End 29 2.2 R/S Method 2.3.1 Description and Methodology R/S statistic is also referred to the rescaled adjusted range, and is formulated as ( ) max ( ) ( ) min ( ) ( ) . ( ) : 1 0 0 ⎥⎦ ⎤ ⎢⎣ ⎡ ⎟⎠ ⎞ ⎜⎝ − ⎛ − ⎟⎠ ⎞ ⎜⎝ = ⎛ − ≤ ≤ ≤ ≤ Y d d Y d Y t t d Y t t S d d S R t d t d (2.7) For a stationary time series, X = {X }, where i ≥ 1 i , with sample sum Σ = = d i i Y d X 1 ( ) 2 , and sample variance d X Y d d S d d i i Σ= − = 1 2 2 2 ( ) ( ) . (2.8) For fractional Gaussian noise or fractional ARIMA: [ ] H H E R / S(d) ~ C d as d ∞ and CH is a finite positive constant that is not dependent on d. Thus, we have [ [ ]] [ ] [ ] H E R S d H d C 10 10 10 log / ( ) = log + log , (2.9) From (2.9), H is directly proportional to the slope. Refer to the least squares line concept in section 2.2 for the same argument. The algorithm: (An algorithm of the code also given in [35]) • For a data length N, divide it into series of K blocks. • Then, for each lags d compute R(t ,d) S(t ,d) i i , for different starting point i t ; the starting points must be t d N i ( −1) + ≤ . • Plot log [ ( , ) / ( , )] 10 R t d S t d i i versus log ( ) 10 d . • Fit a least squares line through the points on the loglog plane, the slope of the line is the estimator for Hurst parameter, H = slope of the line. 30 (Note: the slope is calculated by using the same equation as (2.5).) The same Ethernet data set and the video file of Star Wars IV (high quality) are used to show that the multimedia source and Internet traffic do exist selfsimilarity, which illustrates in Fig. 2.4 and Fig. 2.5 using the R/S method. Since both figures have H value larger than 0.5, and closed to 1. 2.3.2 Simulation Results The same Ethernet data set and the video file of Star Wars IV (high quality) are used to show that the multimedia source and Internet traffic do exist selfsimilarity, which illustrates in Fig. 2.4 and Fig. 2.5 using the R/S method. Since both figures have H value larger than 0.5, and closed to 1. Compare to [35] H = 0.903 for K=10 and up to log10(d) = 4.6, the obtained results are closed to [35] but not exactly the same, this may due to only up to log10(d) = 3.4 estimate points are used. 31 Fig 2.4 This figure shows that the data set is selfsimilar, and the level of selfsimilarity is indicated by the H value. Here, K = 10 and upto log10(d)=3.4 is used. Fig 2.5 This figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. K=10 and up to log10(d)=3.4 is used. 32 2.3.3 Simulation Flow Chart Begin The input data series of length N is divided into K blocks (samples), and with partial sum Σ= = d i Y d Xi 1 ( ) , the sample variance is calculated as Σ= = − d i i X d Y d d S d 1 2 ( ) 1 2 (1/ )2 ( )2 Compute its R(d)/S(d) statistic by rescaled adjusted range, ⎥⎦ ⎤ ⎢⎣ ⎡ ⎟⎠ ⎞ ⎜⎝ − ⎛ − ⎟⎠ ⎞ ⎜⎝ = ⎛ − ≤ ≤ ≤ ≤ max ( ) ( ) min ( ) ( ) ( ) 1 ( ) ( ) 0 0 Y d d Y d Y t t d Y t t S d S d R d t d t d Plot log10( R(ti,d) / S(ti,d) ) versus log10(d). Fit a straight line (simple least squares line) to the points on the loglog plot. Compute the slope of the straight line, which is the estimator of the Hurst parameter, slope = H. End 33 2.4 Estimating the Hurst Exponent using Wavelet Spectral Density 2.4.1 Description and Methodology This method transforms the time series into discrete wavelets. In Matlab, Discrete Wavelet Transform can be use to decompose the input data to scaling and wavelet functions. 1. The Hurst exponent for a set of data is calculated from the wavelet spectral density, Σ= = j i j j i P c 2 1 2 2 1 where ci is the wavelet coefficients. (2.10) 2. Regression line through the normalized spectral density : H = abs((slope –1 )/2). (2.11) Recall: The spectrum of a longrange dependent process X(t) with the discrete wavelet transform coefficients X c show the following behavior E c j l j H C X [ 2 ( , )] = 2 (1−2 ) [43]. By taking log2 on both sides, log [ [ ( , )]] (1 2 ) log [2 ] log [ ] 2 10 2 2 E c j l H j C X = − + . (2.12) From (2.12): ( ) 2 1 2 1 2 1 − → = − slope = − H → H = slope H slope (2.13) which follows the same least squares line argument. Refer to the least square line concept in section 2.2. 34 Algorithm: • Compute the power spectrum by averaging the squares of the coefficients of the transform P(j). • Plot log2(P) versus log2(2j). • Fit a simple least squares line through the points on the loglog plane. • The Hurst parameter can be computed as H = 2 slope −1 .(Note: the slope is calculated by using the same equation as in (2.5).) The same Ethernet data set and the video file of Star Wars IV (high quality) are used to show that the multimedia source and Internet traffic do exist selfsimilarity, which illustrates in Fig. 2.6 and Fig. 2.7 using the wavelet method. Using this method, both of the data sets have calculated H value larger than 0.5, and closed to 1. 35 2.4.2 Simulation Results Fig 2.6 The figure shows that Ethernet traffic is selfsimilar, and the level of selfsimilarity is indicated by the H value. Fig 2.7 The figure shows that Star Wars IV data stream is selfsimilar, and the level of selfsimilarity is indicated by the H value. Wavelet Estimate Method to Approximate the Hurst parameter Wavelet Estimate Method to Approximate the Hurst parameter 36 2.4.3 Simulation Flow Chart Begin The input data series is transformed from time series into discrete wavelet. Then, the wavelet power spectral density can be calculated from Σ= = j i j j i P c 2 1 2. 2 1 Plot log2(P) versus log2(2j). Fit a straight line (simple least squares line) to the points on the loglog plot. Compute the slope of the straight line, which is the estimator of the Hurst parameter 2 slope − 1 H = . End 37 2.5 Observation and Discussion All three graphical estimation methods provide a good estimate of the Hurst parameter (Fig. 2.8), H, and allow us to detect selfsimilarity in an empirical data set. These three methods provide a closed estimation of H, which is between (0.85, 0.93) for Ethernet traffic, and a value between (0.85, 0.91) for Star Wars data set. However, these three methods provide point estimate to H, and we may be interested in a more refined data analysis, e.g., confidence intervals for H. Therefore, an interval estimation can be done with maximum likelihoodtype estimates (MLE) and related methods based on periodogram [34]. The slope of the graph is the graphical tool to compute the Hurst parameter, where the slope of the straight line will provide the information about the Hurst parameter. The critical step in this aspect is choosing the statistical computed points on the plane that should be used to compute the slope. Usually, the very low end and very high end points are not used [36]. Fundamentally, the goal of traffic modeling in this dissertation is: • To find a general/universal traffic model that is suitable for broadband networks. • The model could be appropriate to real traffic and to all type of traffic. • Performance of real networks transporting the traffic of the model could be estimated with adequate accuracy. By understanding the characteristics of Internet and multimedia traffic, we would be able to estimate the jitter process of the broadband networks with adequate accuracy, where the networks with heterogeneous type traffic are greatly different than the networks with homogeneous type traffic. The following two chapters have derived the mathematical equations for evaluating the jitter process in those networks. 38 Fig 2.8 The comparison between the three methods is shown, where the level of selfsimilarity is indicated by the H value. The estimation range is between (0.82, 0.93) for Ethernet traffic for low m aggregated level, where all the three methods have proved that the Ethernet traffic is very selfsimilar. 39 Chapter 3 Theoretical Analysis of Delay Jitter of Homogeneous Traffic in ARQ Wireless Networks 3.1 Abstract This chapter provides a theoretical analysis of delay jitter for homogeneous time constrained traffic and proposes a call admission control (CAC) scheme for wireless differentiated services (DiffServ) networks that apply SelectiveReject (SREJ) automatic retransmission request (ARQ). The CAC scheme regulates the lower class traffic to provide the required levels of delay jitter for the higher priority classes. 3.2 Introduction DELAY JITTER [1] (which is equivalents to interarrival packet jitter) is one of the most important parameters in quality of service (QoS) support measurement for realtime data transfer. Due to this fact, there are several papers that have analyzed the performance of delay jitter [6][7][61]. In [6], the time division multiple access (TDMA)/time division duplex (TDD) scheduling scheme is used. In [7], the jitter is analyzed for mobile ad hoc networks (MANET) based on the ad hoc ondemand distance vector (AODV) routing protocol, where the authors propose a novel handover mechanism. Both [6] and [7] provide results on jitter performance analysis based on 40 computer simulation for the wireless network models. In [61], the authors provide a jitter analysis on wireless networks involving ARQ error recovery, where the delay jitter is calculated using the windowlength generating function and the numerical results are verified through simulation. The delay jitter research of [9] extends the results of [1] and [10] for DiffServ networks, but all three papers do not consider the channel error probability or the ARQ error control scheme, which makes the results difficult to apply to wireless networking applications. Therefore, this paper provides a novel analysis of the perclass jitter performance of DiffServ networks based on wireless channels that experience packet errors, assuming a nonpreemptive headoftheline (HOL) priority scheme. The derivations provide a direct method to analyze/evaluate the perclass jitter based on the DiffServ network, retransmission time constraints, and network packet error parameters [12]. In addition, this paper evaluates the effects on the delay jitter in reference to the priority control scheme of the ARQ traffic for two cases of: 1) the ARQ traffic has a priority over the original transmission traffic; and 2) the ARQ traffic has no priority over the original transmission traffic. 3.3 Analytical Model 3.3.1 Network and System Model Assumptions In this dissertation’s chapter, we investigate a wireless communication link that is framed for a fixed packet size or is time slot based (e.g., timedivision multiple access (TDMA)) transmission. The examples of mobile cellular communications based on timecoordinated slotted data transmissions include Global Systems for Mobile Communications (GSM), IS54 and IS 136 of the North American Digital Cellular 41 (NADC), and Integrated Digital Enhanced Network (iDEN), which are all TDMA based protocols, and the hybrid codedivision multiple access (CDMA) based TDMA systems. Based on these models, in this paper, the traffic delay jitter characteristics are based on a discrete time (slotted) queueing structure. The network traffic model is assumed to be slotbased homogenous and statistically time division multiplexed. The ARQ model applied in this paper is a selectivereject/repeat topology, where only the packets that are erroneous are retransmitted. Additionally, assume class 1 has priority over class 2, class 2 has priority over class 3, and so on. Among the same priority the first in first out (FIFO) transmission ordering applies to the first transmission packets. In this paper, two kinds of ARQ traffic priority control schemes are investigated: 1) when the ARQ traffic has a priority over the original transmission traffic; and 2) when the ARQ traffic has no priority over the original transmission traffic. The network controller model that gives a nonpreemptive priority to the ARQ traffic is based on existing network schedulers that process admission control in reference to time delay bounds, such as the earliest deadline first (EDF) scheduler, where a delivery time deadline is applied to the data packets, thereby limiting the number of possible retransmissions of an erroneous packet [61]. For these types of schedulers, the ARQ packets will commonly have less of a time bound remaining for delivery, since a part of their delay bound would have been used in its former transmission(s), which would result in having a higher priority over the original transmission traffic [12], [61]. Based on these assumptions, in the following, the mathematical foundation of the analysis is established. 42 3.3.2 Theoretical Formulations Assume the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. A slot is defined as the time interval [t1, t), where t is a nonnegative integer (i.e., t ≥ 0). Here we define the mth time slot interval (cycle) of a tagged stream’s mth packet as [mT, (m+1)T ), where m and T are nonnegative integers. Any individual periodic T ’ traffic stream of interest among the different class of service (CoS) could be the tagged stream. Thus, as we investigate the jitter of a specific class, namely the nth class traffic stream, and define the traffic as a mixture 2 of the specified periodic T ’ tagged stream and the combined background traffic of numerous T ’ period streams from different sources. The number of packets that arrive in each slot will not only depend on the data sources but also on the number of ARQ packets that need to be retransmitted. Hence, the period of each renewal cycle is T = T ’ + T ’Pe, where the retransmitted packets will also consume the channel capacity. The term Pe represents the packet retransmission probability, which takes into account that an ARQ retransmission packet can also be erroneous again. Assume the packet errors are independent from packet to packet. Given the packet error probability perror, the probability that a packet transmission is successfully received is (1− perror). If up to r retransmissions are limited within the time bound, each of the j consecutive packet transmissions fail, and a successful transmission then follows, where j = 1, 2, · · ·, r, and r = 1, 2, · · · , T . Therefore, Pe becomes (1 ) 1 1 ( 1) 1 error T i i i error i e P =Σ p − p + = − − , where T is the transmission window size (processing rate) in packets (slots). The following notations are applied throughout this paper. The network’s packet processing rate is μ packets/s and the average arrival 43 rate is λtotal, and it is assumed that there are N classes of service. Hence, for a stable system the utilization is required to satisfy ( ) total total ( 1) 1 total ≤ 1 + + + + = + = − T Pe N N Peλ λ λ λ μ λ λ ρ L . (3.1) The utilization of a specific class n (i.e., n = 1, 2, . . .,N) is noted as n ρ , and it can be obtained from n ρ = (μ μ ) n [(λ λ ) μ ] n e n = + P , which considers the original transmission traffic and the retransmission traffic of the class n data packets. The CAC will control the amount of new admissions given to the class n sources such that the aggregated arrival rate of class n traffic does not exceed ( ( )) n n e = 1+ P ,max λ μρ . When the amount of ARQ packets increase the CAC will regulate the traffic loads of the lower classes by giving out less admissions, to maintain the required QoS of the higher priority classes. In order to investigate the effects of delay jitter in DiffServ networks, the derivation of the probability of jitter (i.e P{J~ = j}) becomes an essential building block. Let the random variable J j m n = , ~ , where n = 1, 2, . . .,N class and cycle m ≥ 1 [10], denotes the process of the normalized jitter or position difference between the mth and (m+1)th packet of the nth class tagged stream that originates from the same source. The term m n A ( +1), indicates the total number of class n packets that arrive in the (m +1)th time slot group. The average number of higher priority packets and ARQ packets that arrive in the (m+1)th period is represented as (m+1), (n−1) b , which can be obtained from ( +1), ( −1) ( +1), ( −1) ( +1), ( −2) ( +1),1 = + + + m n m n m n m b b b L b . The term (m+1), (n−1) b denotes the number of all the equivalent (n−1)th priority packets that enter the buffer before the class (n−1) 44 tagged stream’s (m+1)th packet. The probability that a jitter size of j will exist for the class n tagged stream is given by [9] P{J j} m n = , ~ = P{J j A k b a} m n m n m n = − = = , ( +1), ( +1), ( −1) ~  1 , P{A k b a} P{b a} m n m n m n ⋅ − = = ⋅ = ( +1), ( +1), ( −1) ( +1), ( −1) 1  . (3.2) In (3.2), the term P{A k b a} m n m n − = = ( +1), ( +1), ( −1) 1  is based on the consideration that the assignment probability of the class n packets is dependent to the number of the higher priority packets (i.e., variable a) that arrive within the time slot group specified by (m+1), (n−1) b . We subtract 1 from the total number of class n packets that arrive in the (m+1)th time slot group (i.e., A(m+1),n ) due to the fact that the tagged frame is also among the overall traffic. The binomial distribution used in (3.2) is based on { 1  } [ , ( 1)] ( 1), ( 1), ( 1) − = = = − − + + − P A k b a B p T a m n m n k (p)k ( p) T a k k T a − − − − ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ − − = 1 ( 1) 1 (3.3) where k ∈[1, (T −a −1)], a ≤ j , and each class n packets have a successful (errorless) arrival probability p. The P{b a} m n = ( +1), ( −1) term represents the probability of the higher priority (class 1 to class (n1)) packets occupying a number of slots among the first j slots of jitter offset before the class n tagged packet enters service, and is calculated by the probability mass function of a bilateral geometric function (BGF) [9]. The discrete triangle distribution is applied to the termP{J j A k b a} m n m n m n = − = = , ( +1), ( +1), ( −1) ~  1 , , which is a symmetric distribution, which represents the probability that the time slot position of two sequentially arriving frames will be offset by a jitter amount of +j or −j slot(s) for the range [−k, k] 45 {~  1 , } ( ) , ( 1), ( 1),( 1) P J j A k b a j a m n m n m n k = − = = = Δ − + + − ⎪⎩ ⎪⎨ ⎧ ≤ + − − = + 0, otherwise , for 1 ( 1) 1 2 j k k j a k , (3.4) among the overall x possible time slots, 0 ≤ x ≤ T . A special case of this is the zero jitter case (i.e., j = 0) [9], which is simply { } { } Σ− = = = − = ( 1) 1 , , ~ 0 1 2 T ~ j m n m n P J P J j . (3.5) 3.3.3 Jitter Analysis with NonPriority ARQ Traffic In this section a comparison between the different packet error probabilities for wireless networks deploying a nonpriority ARQ scheme with fixed (limited) channel capacity is presented. The nonpriority ARQ scheme represents the case where the ARQ packets do not have a priority over the regular traffic. The probability of jitter for this case can be derived as, P{J j} m n = , ~ =Σ Σ = − − = − − Δ ⋅ ⎥⎦ ⎤ ⎢⎣ ⎡ − − +   0 1 (  ) 1 ' ' ( ) , ( 1) ( ) j a T a k j a k e n k T a j a T T P f a B ρ , (3.6) where 1 ≤ j ≤ (T −1) . The results are illustrated in Fig. 3.1. The { } ( ) ( 1), ( 1) 1 P b a f a m n = = + − term can be obtained from the probability mass function of a BGF [9], (1 )( ) ,   2 ( ) 1 1 ( 1) ( 1) f a p p a a j n n = − ≤ − − . (3.7) 46 The term (n−1) p is the probability of arrival of the higher priority packets and their ARQ packets compared to class n in a frame of T slots (i.e., Σ − − = = 1 ( 1) 1 n n i i p ρ ). The jitter probability for class 1 packets can be easily obtained from (3.6) P{J j} m = 1 , ~ =Σ− = Δ ⎥⎦ ⎤ ⎢⎣ ⎡ − 1   1 , ( 1) ( ) T k j k k T j T B ρ , 0≤ j ≤(T −1). (3.8) 3.3.4 Jitter Analysis with Priority ARQ Traffic In this section a comparison between the different packet error probabilities for wireless networks deploying a priority ARQ scheme with fixed (limited) channel capacity is presented. The probability of jitter for this case can be derived as, P{J j} m n = , ~ = Σ Σ = − − = − − Δ ⎥⎦ ⎤ ⎢⎣ ⎡ − − +   0 1 (  ) 2 ' ' , ( 1) ( ) ( / ) ( ) j a T a k j a k e n k T a j a T T P f a B λ μ (3.9) where 1≤ j ≤ (T −1) . In each slot there is a probability Perror of receiving a negative acknowledgement of the message. If a negative acknowledgement is received, the transmitter immediately retransmits the packet that was received in error instead of a new packet. The { } ( ) ( 1), ( 1) 2 P b a f a m n = = + − term can be obtained from the probability mass function of a BGF [9], (1 )( ) ,   2 ( ) 1 ' ( 1) ' 2 ( 1) f a p p a a j n n = − ≤ − − . (3.10) The term ' (n−1) p is the probability of arrival of the higher priority packets, which includes the retransmission packets of classes 1 through n, which can be obtained from Σ − − = = + 1 1 ' ( 1) n i i e n n P p ρ μ λ . 47 Fig. 3.1 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 10%. The solid line represents the nonpriority ARQ scheme, and the dotted line represents the priority ARQ scheme. 48 Fig. 3.2 Comparison between wireless networks nonpriority ARQ scheme with Pe = 20%. Fig. 3.3 Comparison between wireless networks deploying the priority and nonpriority ARQ scheme with Pe = 1% and 10% for class 1 through class 5. 49 3.4 Discussions and Conclusions This paper provides a novel analysis of the perclass jitter probability of homogeneous traffic streams performance of DiffServ networks based on wireless channels that experience packet errors, assuming a nonpreemptive headoftheline (HOL) priority scheme. The investigation has been conducted for the case where the ARQ retransmission packets have priority over the first time transmission packets. The mathematical results were compared with simulation data, and the results show an accurate match, which verifies the derivations. The results of Fig. 3.1 show that for both the priority and nonpriority ARQ cases, the probability of jitter for the same class can be controlled to be approximately the same disregarding the channel packet error rate for the traffic of the higher priority classes if the CAC of the wireless network can obtain accurate packet error rate information and respond effectively in regulating the admission access. The call admission controller will dynamically manage the network traffic loads by regulating admissions based on the amount of retransmission traffic that is anticipated. Thus, the traffic load can be regulated dynamically to maintain the required jitter performance. Based on the observations of Fig. 3.1, Fig. 3.2, and Fig. 3.3, it can be observed that the normalized jitter probability of the priority ARQ scheme is larger than the nonpriority ARQ scheme. The difference in performance becomes more significant as the probability of packet error increases (e.g., when Pe increases from 1% to 10%, and 20%). However, class 1 and class 2 still maintain a relatively low probability of jitter compared to the traffic of the lower classes. In the ARQ scheme with priority control, the ARQ packets will block the new packets from being transmitted during the retransmission 50 process. Thus, the normalized jitter probability of the wireless network deploying ARQ with the priority scheme is worse compared to the ARQ with the nonpriority scheme, especially for the low priority packets. Although the ARQ priority scheme sacrifices the delay jitter performance for the low priority classes, it may be needed especially for realtime service applications in which the packet might be useless unless a successful reception of the packet is obtained within its time bound [12], [61]. In Fig.3.2, as Pe is 20%, no leftover channel capacity is available for class 5 (the lowest priority class) since a significant part of the channel capacity is used for retransmission of the higher priority class packets. In Fig.3.2, the negative values represent the normalized jitter probability of the priority ARQ scheme is larger than the nonpriority ARQ scheme, where probability of jitter for ARQ priority scheme minus nonpriority ARQ scheme. These results demonstrate the influence and the effectiveness of DiffServ in limiting the delay jitter for the high priority users. 51 Chapter 4 Jitter Characteristics of Heterogeneous Wired Communication Networks, Gaussian Traffic Modeling and Queue length approximation using the MVA Approach In realtime wired or wireless communications, each transmitted packet may experience different time delays during arrival at the destination. This variation in delay is often referred as delay jitter or simply jitter. Jitter is an unsurprising result of packet transferring in highspeed switched networks. The variable delay results from the processing and queueing at each node through the multihop network. This is because the packets transmitted between a given source and destination may vary in length, may take different routes, and may experience different delay at the switches. To compensate the packet delay jitter, the incoming packet are buffered at the destination, and then replayed at a constant rate based on the controller that regenerates the audio/realtime traffic (playback mechanism). The regenerated packets are therefore smoothed out. However, the compensation provided by the delay buffer is limited, where any incoming realtime traffic packets that have been delayed more than the replay delay bound limit, then the packets will be discarded. Thus, by controlling the delay jitter within the network can further reduce the timing distortion of realtime applications. In 52 order to examine the heterogeneous traffic network jitter behavior in a more general environment, we develop a generalized analytic approach to approximate the jitter probability density function (pdf) of a stationary tagged stream that is multiplexed on a highspeed IP network. The main objective of this chapter is to examine the relationship between the jitter and traffic characteristics, such as traffic load/utilization, and period T of the tagged stream. This insight may aid the design of the scheduling control of the buffer in the playback mechanism at each node. For a generalized approach to analyze a queueing process, the heterogeneous traffic arrivals at a node are modeled as a Gaussian process. In highspeed networks, it has been shown that aggregated traffic has a direct relation to Gaussian characteristics through Central Limit Theorem (CLT), which states that summing a large number of independent variables with finite variance can converge or weakly converge to a Gaussian random variable [22]. The networks’ selfsimilar traffic exhibits longrangedependent (LRD) correlations, and it is very close to being Gaussian and strongly LRD (i.e., approximately Fractional Gaussian noise), which is caused by both small and large file transfers over limited bandwidth links. Some of the traffic may follow a nonGaussian marginal distribution. However, by applying CLT, the aggregated traffic can be modeled as a Gaussian process; even though each single independent data source does not follow a Gaussian distribution. The Gaussian model is useful for two main reasons. First, any stationary Gaussian process can be completely characterized by its mean and autocovariance. Second, as today highspeed networks are highly complex and traffic is usually heavily multiplexed of thousands of network applications. By applying CLT, the aggregated 53 traffic can be modeled as Gaussian process; even each single independent data source does not follow a Gaussian distribution. The only defect in this model is that there is a positive probability of a negative quantity of arriving traffic, which is impossible to happen in real networks traffic. This significant weakness is counterbalanced by the fact that the CLT appeals as more and more traffic streams are aggregated to share a link; traffic becomes more Gaussian, and the case that the amount of negative traffic reduces as traffic is aggregated [24]. Many broadband traffic studies have evolved around the Gaussian model, and they show that Gaussian models indeed provide a good approximation to networks traffic if the aggregated traffic is sufficiently large. In [22], [23], and [24], the results shown that the Gaussian traffic model could be the precise tool for analyzing highspeed networks. Moreover, the Gaussian model is also a good fit for highspeed networks with differentiated services (DiffServ). In differentiated services networks, traffic management controls are on the level of traffic aggregates, not for individual links [23][54][55]. 4.1 Introduction In order to evaluate delay jitter, the queue length distribution of the output queue was first analyzed. We can relate the transmission delay and the queue length (number of packets) ahead of the tagged packet (i.e., n Q represents the number of customers ahead of the nth tagged packet). Let any customer’s service time be equal to one slot and follows FIFO order, n Q denotes the number of customers, regardless of their class affiliation, that are waiting for service just ahead of the arrival of the nth packet of the p 54 customer. Therefore, the normalized jitter relative to tagged stream period T is (see Chapter 1 for more detail discussion) ~ , 1, 2,... 1 = − = J n Qn+ Qn n . (4.1) ( ) ( ) 1 J T Q Q T Q n n n n = + − = + Δ + . (4.2) The normalized jitter with respect to the original data stream period (interdeparture time between nth and (n+1)th packets transmitted from the source), T: J~ = J − T = ΔQ(n), n =1, 2,... , n n where n n def ΔQ n = Q − Q ( ) +1 . (4.3) From (4.3), we can observe the study of jitter turns into an equivalent study of the queue size variation ΔQ(n) of a selected user’s packet arrival, which is the methodology that is going to be applied in this study. We want to find the pdf of J~n , i.e., Pr{~ } n J , from the queue length distribution of the steady state probability of the buffer with queue length q (P(Q>q)), q = 1, 2, … . A discretetime approach is used in the delay analysis, which a node/multiplexer is modeled as a discrete time fluid queue where the time is slotted. It is assumed that the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. In summary, the approach here is • First, apply the Gaussian traffic modeling using the MVA approach [25][25] to conduct the queue length analysis. Obtain the tail probability P{Q>q} based on the MVA approach for the discrete time queueing model [25][26] to conduct the queue length analysis, which is used in heterogeneous jitter analysis. This is done in section 4.2. At a node in highspeed networks, the packet arrival that consist of heterogeneous type traffic includes real time and 55 nonreal time integrated traffic streams from different sources (e.g., voice, audio, video, image, plain text and data of other newly developed Internet applications). A single link will carry hundreds or even thousands of applications, which apparently lead to the application of Central Limit Theorem, that the network traffic can be modeled by a Gaussian stochastic process. • Second, find the pdf of the jitter probability from the queue length distribution. This is done in section 4.3. 4.2 Discrete Time Fluid Queue Model and Extreme Value [26] The multiplexer is modeled as a fluid queue serving a large number of independent sources. In the discrete time model, the fluid is permitted to flow in and out of the buffer only at discrete time intervals denoted in k. Let N be the total number of sources served by the multiplexer, and (s) k X be the amount of traffic that arrives from source s into the buffer at time k, s =1, 2, …, N. Further, let Σ = = N s s k k X X 0 ) ( and μ − = Δ (0) k X , which means that k X is the aggregated fluid arriving at time k, and less the system capacity μ. Let ≥ 0 k Q be the amount of fluid in the buffer at time k, less than the capacity μ, and the k Q for the infinite buffer case can be represented using Lindley’s equation [26] ( ) max{ ,0}. k k 1 k k 1 k Q = Q + X = Q + X − + − (4.4) Lets say that the fluid queue has always been operational, that is k ∈ƶ = {…, 1, 0, 1, …} (instead of time starting at k = 0). As long as k X is a stationary and ergodic process, and 56 with = { } < 0 k X E X (the stability condition for an infinite buffer queuing system, where the arrival rate must be less than the service rate), (4) can uniquely determine a stationary process ( k Q~ ) that satisfies the equation, where for all k ∈ƶ = {…, 1, 0, 1, …} [26][45] ( k ∈ƶ from this point on). Due to k X being an ergodic stationary process, the tail probability of buffer queue length q at time k ( P(Q q) k > ) converges to a steady state tail probability of buffer queue length q ( P(Q > q) ) regardless of the initial condition Q0. Thus, for all k ∈ƶ, P(Q~ q) k > is equal to P(Q > q) , since the tail probability does not depend on the initial condition Q0, and the tail probability of a stationary process is the tail probability itself, where P(Q~ q) k > = P(Q > q) [26][45]. The relation between an ergodic stationary process k X and the corresponding stochastic process k Q~ , where k ∈ƶ [26] Σ≥ − ≥ = m i k i m k Q X 0 1 ~ sup (4.5) where m = 0, 1, 2, … .Since, P(Q~ q) k > = P(Q > q) for all k [26], P(Q q) P(Q~ q) k > = > ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ > = Σ≥ − ≥ P X q m i i m 0 1 sup . (4.6) From (4.5) and (4.6), we can see that the steady state tail probability P(Q > q) can be determined by summing all previous stationary aggregate fluid arrival process. In other words, the probability of the tail probability P(Q > q) is the same as the tail probability 57 of the supremum of a stochastic process denoted by Σ= − = m i m i W X 0 , where ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ > = > ≥ P Q q P W q m m 0 ( ) sup , m = 0, 1, 2, … [26]. This stochastic process, m W , is called the backward accumulation process, and it is not stationary. The first two moments of m W are defined as below [26] E W mX m { } = (4.7.a) Σ− = = + − 1 1 { } (0) 2 ( ) ( ) m i m X X Var W lC m i C i (4.7.b) where C (0) E{(X X )(X X )} X k k l = − − + Δ is the autocovariance function of Xk. Hence, P(Q > q) can be calculated by determining the tail probability of the supremum of the backward accumulative process m W , where the Extreme Value Theory is applied to this supremum of a stochastic process to obtain a simple approximation for P(Q > q) [26], which is shown in the next subsection below. Evaluating P(Q>q) at a multiplexer with Gaussian Arrival Process using the MVA approach We can obtain a simple approximation for P(Q>q) by applying the results from the theory in section 4.2, where determining the tail probability P(Q>q) of a queueing system is mapped to that of determining the tail probability of the supremum of the backward accumulation process m W (here only the discrete case is our concern) [26]. Let μ − = Δ (0) k X denote the link capacity of a multiplexer (e.g., an ATM multiplexer). Assume that (s) k X , the fluid arrival process of source s at time k, s = 1, …, 58 N, are independent mean ergodic stationary arrival processes with finite mean s X , and autocovariance C (l) s . ( ) 1 s k N k s A Σ X = Δ= is defined to be the aggregate arrival process. Then, Ak is also a mean ergodic stationary arrival process with mean Σ = = N s s A X 1 and autocovariance Σ = = N A s s C l C l 1 ( ) ( ) . So, Σ = = = − N s k s k k X X A 0 ( ) μ is a mean ergodic stationary process with mean X = A −μ (where = =Σ = = N s s k k X E X X 0 { } ( ) ( ) 1 Σ ( ) + −μ = N s s k X , since μ − = Δ (0) k X ) and autocovariance C (l) C (l) X A = . In other words, k X is the aggregate fluid arriving at time k, less the capacity μ. As long as X < 0, which means that the arrival rate must be less than the service rate, the infinite buffer queueing system is stable. Now, model the arrival process Ak as a stationary normal process. The main reason to consider Gaussian traffic modeling is the CLT [25][26]. As the network grows, the number of independent traffic sources aggregating at a node (e.g., router, switch, multiplexer) increase, and the shape of the traffic distribution will become closer and closer to Gaussian. Ak has both negative and positive components. The negative component in [26] imply that the buffer is empty due to the arrival process, which is not possible in reality. However, as the mean Ā of the aggregate process is typically several times larger than its standard deviation (0) A C , the probability of this negative flow is negligible. Since Ak is modeled as a normal process, both Xk and Wm are normal processes. Now, rewrite the arrival process, where determining the extreme value distribution of Wm 59 is equivalent to determining the extreme value distribution of a new stochastic process{Z : m = 0,1,K} m , which is defined as [26] ((1 ) ) (1 ) m k Z Wm m m − + + − = Δ μ ρ μ ρ (4.8) where μ ρ A Δ= is the utilization of the ATM multiplexer, ⎡ ⎤ μ q k Δ= is the time it takes for the fluid in the buffer at level q to empty, and μ is the service rate. Zm is the standardized maximum value, where μ ((1−ρ )m+ k) and μ (1−ρ )m are the scale and location parameters, respectively. Also, Zm is a normal process with [26] { } = 0 m E Z (4.9.a) 2 ((1 ) )2 { } { } m k Var W Var Z m m − + = μ ρ . (4.9.b) The extreme value distribution is used to quantify the probabilistic behavior of unusual or rare events, and provide a better fit to the data set. Justification of the new stochastic process m Z : Applying Central Limit Theorem, assume that{B : t ≥ 0} t is a Gaussian process with stationary increments such that 0 B = 0, and define ς := (Σ ) = − = − N n n t t E B E B 1 ( ) ( ) , and ( ) : var( ) t v t = B , where each (n) t B is an individual stream. Expressing P(B q) t > in terms of ς , v(t) , and the standard Gaussian tail function ψ (α ) : 2 / 2 2π e z dz ∫ = − , we obtain a multivariate version of the CLT of the normalized process [58] ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + > = ( ) ( ) v t P B q q t t ς ψ . (4.10) 60 Now, apply the Dominant TimeScale tq and the Maximum Variance Asymptotic approach. The term ( )2 ( ) q t v t +ς should attain its maximum value at some finite point q t = t , at which P(B q) t > attains it maximum. For Gaussian processes, q t , the dominant time scale is also the time at which it attains its maximum variance value v(t) . P(Q q) P(B q) t > = > is largely dominated by P(B q) tq > [25][26][58]. The q t should be a local maximum point of log[v(t) /(q +ς t)2 ] that lies in the open set q {t : v(t) > 0}, t must satisfy [58][59] . ( ) 0 log ( ) 2 t tq q t v t dt d = ⎥⎦ ⎤ ⎢⎣ ⎡ + = ς (4.11) Note: Eq. (4.10) and (4.11) will hold for discrete time processes. For notation simplicity, under (4.10) and (4.11), the new stochastic process m Z is defined as q m W m Z m m χ χ + + = (4.12) and define ⎡ ⎤ μ q k Δ= and μ ρ = A where m : E(W ) mE(X ) m χ = − = − = −[E(A −μ)]m = −[E(A) −μ]m = −m[ρμ −μ] 61 = −μ [ρ −1]m =μ [1−ρ]m (4.13) Substitute (4.13) into (4.12), we have q m W m Z m m [1 ] [1 ] μ ρ μ ρ + − + − = k m W m m [1 ] [1 ] μ μ ρ μ ρ + − + − = ( m k ) W m m − + + − = [1 ] [1 ] μ ρ μ ρ . (4.14) Proposition 1 [26] if and only if > 1 m>q m W Z From proposition 1 and (4.6), the relationship between the steady state tail probability of the buffer queue length q and the extreme value distribution of Zm and Wm ⎟⎠ ⎞ ⎜⎝ > = ⎛ > ≥ P Q q P W q m m 0 ( ) sup ⎟⎠ ⎞ ⎜⎝ = ⎛ > ≥ sup 1 0 m m P Z . (4.15) From the Dominated Convergence Theorem [26][48], the equations (4.16) and (4.17) show that { }→0 m Var Z as m →∞ if Σ < ∞ ∞ k=−∞ X  C (k)  (a sufficient condition for the ergodicity of a stationary process [49]), { } Σ∞ =−∞ →∞ = k m m X Var W C k m lim 1 ( ) (4.16) and 62 { } 2 2 (1 ) ( ) lim μ − ρ = Σ∞ =−∞ →∞ k X m m C k mVar Z . (4.17) Fig. 4.1 illustrates a plot of the variance of Zm versus m, it shows that { } m Var Z must reach its maximum value at some finite m = mmax ≥ 0. Next, the extreme/supremum value distribution will be applied to approximate the tail probability. Maximum Variance Approximation: “For a zero mean normal process Zm that is correlated in time and whose variance { } m Var Z achieves a maximum value for some finite mmax [26],” P Z u P(Z u) m m m > ≈ ⎟⎠ ⎞ ⎜⎝ ⎛ > ≥ max 0 sup (4.18) for sufficiently large u [26]. Fig. 4.1 illustrates this point by plotting { } m Var Z vs. m. For eq. (4.18), the right hand side approximation is a lower bound of the left hand side, that is P Z u P(Z u ) m m m > ≥ ⎟⎠ ⎞ ⎜⎝ ⎛ > ≥ max 0 sup [26]. “Typically, 1.5 { } mmax u > Var Z is sufficiently large for the approximation to work well [26]”. Thus, if { } << 1 m Var Z , then the tail probability P(Q>q) can be approximated as [26] ( ) ( 1) max > ≈ > m P Q q P Z x dx ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = ∫ − ∞ 2 exp 2 1 2 1 σ max π . (4.19) This is because the probability that P(Q>q) is much less that 1, the condition { } << 1 m Var Z readily hold for this analysis [26]. 63 Theorem A (Theorem A in [56], Theorem D.4 in [57]) “Let { t [L U]} t ς : ∈ , be a zero mean (centered) Gaussian process, and suppose that there exist constants a and γ such that {( ) } γ E ς ς a t s s t − 2 ≤ − for all t, s∈[L,U]. Then, there exists a constant K determined only by a and γ, such that for any A ⊂ [L,U] and y, ({ }) ( ) ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ > ≤ − A A P y K U L y y σ ς 2 /γψ (A.1) where { } A t A t σ Var ς ∈ = sup ”. Summary of the algorithm for obtaining the tail probability P(Q>q) based on the MVA approach for discrete time queueing model [26]: 1. Given individual arrival processes with mean s X and autocovariance C (l) s , compute the aggregate mean Σ = = N s s A X 1 , and autocovariance Σ = = N A s s C l C l 1 ( ) ( ) of the aggregate arrival process. 2. Compute { } m Var Z using Eq. (7.b) and (9.b) as 2 2 1 1 ((1 ) ) (0) 2 ( ) ( ) { } m k mC m i C i Var Z m A i A m − + + − = Σ − = μ ρ where μ > A is the link rate, μ ρ = A , and ⎡ ⎤ μ q k Δ= . 3. Determine 2 max σ , the maximum value of { } m Var Z . 4. Finally, compute the tail probability ( ) ( ) ∫∞ − > ≈ > = max 2 max 1 2 2 1 1 σ π P Q q P Z e dx x m , where mmax Z is the normal random variable. 64 The typical plot of { } m Var Z versus m is shown in Fig. 4.1. This analysis is done at an ATM multiplexer with the following assumptions: q=1000, μ=0.61, N=100, where individual arrival process has a mean s X = 10 cells/sec, and autocovariance of Gaussian process l s C (l) = 100e−0.04 . Fig. 4.11 Plot of variance of Zm versus m. The variance reaches a maximum value and then begins to converge to 0. The parameters used are q=1000, μ=0.61, N=100, each individual arrival process with mean s X = 10 cells/sec, and autocovariance l s C (l) = 100e−0.04 . 1 This figure is attempted to reproduce the result of Figure 3 in [26]. Both graphs have the same distribution shape but values may not be exactly the same, because the parameters used in [26] to plot Figure 3 are not provided by reference [26]. So, we cannot regenerate the plot with the same set of parameters used in [26] (which is unknown to us). The attempt here is to use the MVA theory and plot the Fig. 4.1 using a set of predicted parameters to regenerate the plot that is similar to Figure 3 in [26]. 65 4.3 Jitter Analysis of Heterogeneous Traffic Networks Assume the packets arrive and depart at the beginning of a slot, which leads to a discrete time queueing process. The time is slotted with the size being equal to the transmission of a packet. An arrival time slot is defined as the time interval [t1, t), where t is a nonnegative integer (i.e., t ≥ 0). Here we define the nth packet arrival time slot interval as [nT, (n+1)T) for the packet from the tagged stream (stream of interest), where n and T are nonnegative integers. The background traffic is the superposition of all the other traffic competing for the resources with the tagged stream at a node. In heterogeneous highspeed network, jitter experienced by realtime traffic can be worsening if traffic is not being regulated or some type of congestion control mechanism is not applied. Thus, a service discipline similar to the distortionreducing peak outputrate enforcing (PORE) [50] is used to prevent the delay jitter increasing without bound. Let’s refer to this as a tagged stream adaptive PORE (APORE) service discipline. The APORE service strategy guarantees the packets belong to a tagged stream are transmitted at a minimum spacing of Amin slots, where Amin = T 1. Whenever the queue level q < Amin , the server delays providing service to the tagged stream, instead provides firstcomefirst serve service to the background traffic. Thereby, it ensures the tagged stream experiences minimum jitter (see Fig. 4.4). Proposition: The probability that a jitter size of j will exist for the nth packet of the tagged stream is given by: P{J j} n ~ = = P{J j A q} n n = − = + ~  1 1 P{A q} n ⋅ − = + 1 1 = ( ) min ( ), 0 2 1 P Q q f j q A q > < ≤ (4.20) 66 where 1 ≤ j ≤ (T −1) and n+1 A indicates the total number of packets that arrive in the (n+1)th time slot group. In (4.20), the probability of q number of data packets that arrive among the available (T1) slots will be served. A special case of (4.20) is the zero jitter case (i.e., j = 0), which is simply P{~ = 0} n J = { } Σ− = − = ( 1) 1 1 2 ~ T j n P J j . (4.21) Derivations & Explanations: In (4.20), the term P{A q} n − = + 1 1 is the aggregated traffic arrival distribution that approximates the number of arrivals in the arrival slot of a tagged stream packet. It is based on the consideration of the probability the packets that arrive within the time slot group, which will be served ahead of the tagged packet. Subtract 1 from the total number of aggregated packets that arrive in the (n+1)th time slot group (i.e., (n+1) A ) due to the fact that the tagged frame is also among the overall traffic. The traffic distribution in eq. (4.20) is based on P{A q} P(Q q) n − = = > + 2 1 1 1 ({ }) ∫∞ − ≈ > = max 2 max 1 2 2 1 2 1 1 2 1 σ π P Z e dx x m (4.22) where q∈[1,(T −1)] , calculated using the MVA approach discussed in section 4.2. The discrete triangle distribution applied is a symmetric distribution, which represents the probability that the time slot position of two sequentially arriving frames will be offset by a jitter amount of +j or –j. Thus, the triangle distribution for the range [q, q] is applied as {~  1 ,} ( ) ( 1) P J j A q f j n n q = − = = + 67 ⎪⎩ ⎪⎨ ⎧ ≤ + − = + otherwise for j q A j q 0, , 1 ( 1) 1 2 min (4.23) which provides the normalized jitter probability of j given that q packet arrivals enter the server before the (n+1)th tagged packet of the tagged stream, among the overall x possible time slots, 0 ≤ x ≤ T. 4.3.1 Simulation and Numerical Study The following simulation and numerical results focus on the delay jitter in terms of pdf on the performance of a tagged stream under different traffic conditions. For the illustrative purpose, the bursty Internet traffic trace is used in this evaluation. The simulation environment has been set up in such a way that the information bit stream (e.g., video, multi media, digitized voice, etc) is packetized into fixedlength ATM cells (packets). The cells are transmitted using fixed interarrival time but the bit length is varied from celltocell (packettopacket). Accordingly, the delay jitter is defined as the delay jitter experienced between two successive packets (e.g., the nth and n+1th packets from the tagged stream), where the delay jitter is calculated based on (4.3) (see Flowchart 1). For the experiment, a real Internet traffic trace is used, BCpAug89 packet traces of LAN and WAN traffic seen on an Ethernet. We assume that Ethernet traffic sources are multiplexed on to an ATM network, where traffic is segmented into small and fixed sized cell/packet in order to achieve small delay and delay jitter [51][52]. The reason we base our analysis on ATM networks is because still ATM remains as the most widely used Internet backbone protocol at this time. The traces are in byte units, which is converted into ATM cell 53 bytes. The variable size Ethernet packets are segmented in to constant 68 size of 53 bytes packets (cells). Thus, the traffic transmitting in the network is fixed size packets and one packet is transmitted in each time slot. Flowchart 1 is the algorithm of delay jitter calculation at a multiplexer/node. The queue consists of a tagged stream packet and background stream packets. The tagged stream and background stream are segmented into ATM 53 bytes packets. There are a random number of background stream packets that enter the queue before the tagged stream packet. Whenever the queue level q < Amin , the server delays providing service to the tagged stream, instead provides firstcomefirstserve service to the background traffic. The traffic trace of BCpAug89 is resampled at 10 ms. Assume the average processing rate and overhead delay is 1ms per cell, the interarrival time between two consecutive cells is 10 ms, which will be equivalent to 10 time slots (for generate T = 10 tagged stream). Through the numerical example, we demonstrate the accuracy of the closed form delay jitter approximation of eq. (4.20) shown in Fig. 4.2 of a 95% confidence interval (CI), for selfsimilar traffic of heterogeneous networks. Here, we calculate the 95% CI for the delay jitter proportion between the real data set and the numerical analysis (eq. (4.20)). The width of the 95% CI reveals the degree of uncertainty in the estimate of the treatment effect; in another words, this is the interval which includes the true value with 95% certainty. The real data set is used to obtain the empirical pdf function for the delay jitter. Then, eq. (4.20) is used to approximate the delay jitter pdf function of the data set. Subsequently, confidence intervals for the estimations are computed. The confidence interval bounds on the standard deviation between the empirical and numerical values. 69 In Fig 10, we compare the approximation eq. (4.20) and the simulation results of the jitter distribution at a multiplexer serving various Internet applications. Fig. 4.2 shows that the delay jitter increases when the traffic utilization increases from 50% to 90%, for T equals to 10. In Fig. 4.3, we can observe that the tagged stream with a large period will tend to experience large delay variation as the utilization increases from 50% to 70%, where the T increases from 10 from 20. Fig. 4.4 illustrates the effectiveness of the control algorithm, the APORE service strategy that guarantees the packets belong to a tagged stream are transmitted at a minimum spacing of Amin slots, where Amin = T 1. If we choose the Amin to be larger than T 1, then we will introduce more delay variation to the tagged stream, as shown in Fig. 4.4 the probability of jitter increases as Amin > T1. We will not consider Amin < T1, because this will increase the possibility that a packet from the tagged stream may not be arrived to a node even it is its turn for entering service. 70 Flowchart 1 The simulation algorithm used to calculate delay jitter at a multiplexer. Fig. 4.2 Comparison between the approximation equation and the simulation results of the jitter distribution for utilization of 50% and 90% with 95% CI, for the case of T = 10. 71 Fig. 4.3 Distribution of jitter for the comparison between utilization of 50% and 70%, and for the comparison between T = 10 and 20. Fig. 4.4 Distribution of jitter for utilization of 60%, T=10, and various Amin values. 72 4.4 Jitter Analysis of Heterogeneous Traffic Networks with Differentiated Services In this section, the jitter characteristic of the priority class in the DiffServ network is analyzed. In order to provide high quality service, endtoend quality of service (QoS) support is required. Several network models and mechanisms have been proposed by the Internet Engineering Task Force (IETF) to improve the QoS of integrated service networks by deploying differentiated service (DiffServ), traffic engineering (TE), and constraintbased routing (CR) [53]. The realization of DiffServ in networks is one of the essential focuses of TE technologies under development. Recently, in wide area networks (WANs), protocols like multiprotocol label switching (MPLS) and generalized MPLS (GMPLS) are being developed with this focus of enabling effective TE with DiffServ capabilities. A basic differentiated service scheme can be provided by a set of priority scheduling algorithms. The traffic flows are aggregated according to their belonging to a certain class type called the perhop behavior (PHB) [54]. The traffic classification is done in qualitative terms, which are based on vendor concerns [54][55]. For example, the network administrator may configure the service rate of 50%, 35%, and 15% for classes 1, 2, and 3 respectively. Class 3 may correspond to delay jitter insensitive traffic, where the least bandwidth is being enforced for this class (e.g., best effort Internet traffic). Therefore, the research presented in this dissertation proposes a methodology to directly compute the QoS performance quantity (e.g., probability distribution of interarrival jitter) of network deploying differentiated services. The analytic models are applied in analyzing the contribution of multipleclass of services in Internet networks 73 with respect to interarrival packet jitter. In addition, the relationship between interarrival packet jitter and the system characteristics, such as the server utilization and priority, is also investigated. This tool will help to provide an analysis of network routers and network streams for various system server topologies in order to assist network system designers in the hardware/firmware development and estimate the quality of service of DiffServ networks with heterogeneous type traffic, which includes real time and nonreal time integrated traffic streams from different sources (e.g., voice, audio, video, image, plain text and data of other newly developed Internet applications). DiffServ capable networks provide endtoend QoS control by classifying and assigning different classes of services onto the incoming packets. Hence, at the base station’s router/switch, the packets are buffered before being multiplexed onto the highspeed link following a nonpreemptive HOL priority scheme, where the packets that have been postponed in services will wait at the head of the line of its equivalent class until all higher priority packets have been cleared out of the server. The APORE service control algorithm strategy that guarantees the packets belong to a tagged stream are transmitted at a minimum spacing of Amin slots, where Amin = T 1. Assume class 1 has priority over class 2, class 2 has priority over class 3, and so on. Among the same priority the first in first out (FIFO) transmission ordering applies. In the discrete time model, the fluid is permitted to flow in and out of the buffer only at discrete time interval denoted by k. Let N be the total number of sources served by the multiplexer. Define k d X , to be the aggregated fluid of class d arriving at time k, and less the system capacity μd of class d, where Σ = = N s s k d k d X X 0 ( ) , , and k d d X μ − = Δ (0) , . Here, we assume that each fluid arrival process of class d corresponding to source s, ( ) , s k d X , is an 74 independent mean ergodic stationary process with mean s d X , and autocovariance C (l) s . Let’s denote ( ) , 1 , s k d N k d s A Σ X = Δ= to be the aggregate arrival process. Then, Ak is also a mean ergodic stationary arrival process with mean Σ = = N d s s d A X 1 , and autocovariance Σ = = N A s s d C l C l d 1 , ( ) ( ) . Thus, k d k d d X = A − μ , , is a mean ergodic stationary process with mean d d d X = A −μ (where Σ = = = N s s d k d k d X E X X 0 ( ) , , { } ) and autocovariance C (l) C (l) Xd Ad = . Let 0 , ≥ k d Q be the amount of fluid corresponding to class d in the buffer at time k, less than the capacity μd , and k d Q , for the infinite buffer case can be represented using Lindley’s equation ( ) max{ ,0}. k ,d k 1,d k ,d k 1,d k ,d Q = Q + X = Q + X − + − (4.24) Let say that the fluid queue has always been operational, that is k ∈ƶ = {…, 1, 0, 1, …} (instead of time starting at k = 0). Due to k d X , being an ergodic stationary process, the tail probability of the buffer queue length q at time k ( ( ) , P Q q k d > ) converges to a steady state tail probability of buffer queue length q ( P(Q q) d > ) regardless of the initial condition. The steady state queue length distribution corresponds to the supremum distribution of an ergodic stationary process k d X , and the corresponding stochastic process k d Q , ~ . The maximum amount of fluid in the system at time k can be expressed as Σ− = − ≥ = 1 0 , 0 , ~ sup m i k i d m k d Q X (4.25) 75 where m = 0, 1, 2, … . On the supremum distribution of Integrated Stationary Gaussian process with linear drift, the limiting (steady state) queue length distribution corresponds to the supremum distribution, ( ) : lim ( ~ ) , P Q q P Q q d k k d > = > →∞ ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ > = Σ− = − ≥ P X q m i i d m 1 0 , 0 sup . (4.26) Let the supremum of a stochastic process for class d defined by Σ− = − Δ= 1 0 , , m i m d i d W X . Based on the Extreme Value Theory, we can study the supremum distribution of d Q through the supremum stochastic process m d W , . Note that this stochastic process m d W , is not stationary. Now, Ak,d is modeled as a stationary normal process, then both Xk and Wm are normal processes. This is justified by applying the Central limit Theorem, which mentioned in the introduction that the multiplexer will serve a large number of independent sources. Thus, we study the supremum distribution of m d W , through the new supremum stochastic process m d Z , , where m d Z , is a centered (zero mean) Gaussian process. So, determining the extreme distribution of m d W , is equivalent to determining the extreme distribution of m d Z , . Assume there is a total of D class of services, the extreme value distribution of a new stochastic process of class d{ : 0,1, ; 1,2, , } , Z m d D m d = K = K , which is defined as ((1 ) ) (1 ) , , m k W m Z d d m d d d m d − + − − = Δ μ ρ μ ρ (4.27) 76 where d d c N d s s c c c A d X d d μ ρ ρ μ Σ Σ = Σ = = Δ = = = 1 1 , 1 is the load of class d at the multiplexer, ⎡ ⎤ d k q μ Δ= is the time it takes for the fluid in the buffer at level q to empty, and μd is the service rate of class d. Based on this we can define Zm,d as a normal process with { } 0 , = m d E Z (4.28.a) 2 2 , , ((1 ) ) { } { } m k Var W Var Z d d m d m d − + = μ ρ . (4.28.b) Based on the Maximum Variance Approximation, the tail probability of class d, P(Qd>q), can be approximated as ( ) ( 1) max , > ≈ > d m d P Q q P Z x dx m d ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = ∫ − ∞ 2 exp 2 1 2 1 max , σ π . (4.29) This is based on the same argument proved in [26], which is explained in section 4.2 above. Due to the probability that P(Qd>q) is much less that 1, the condition { } 1 , << m d Var Z readily hold for this study. Proposition: The probability that a jitter size of j will exist for the nth packet of the tagged stream for a class d traffic source is given by P{J j} n d = , ~ = P{J j A q} n d n d = − = + ~  1 , 1, P{A q} n d ⋅ − = + 1 1, = ( ) min ( ), 0 2 1 d q,d d P Q > q f j < q ≤ A (4.30) where 1 ≤ j ≤ (T −1) and n d A +1, indicates the total number of packets that arrive in the (n+1)th time slot group of class d and higher priority classes compare to class d. In eq. 77 (4.30), the probability of q number of data packets that arrive among the available (T1) slots will be served. A special case of (4.30) is the zero jitter case (i.e., j = 0), which is simply P{~ 0} , = n d J = ΣΣ { } − = = − = ( 1) 1 1 , 1 2 ~ T j d c n c P J j . (4.31) Derivations & Explanations: In (4.30), the term P{A q} n d − = + 1 1, is the aggregated traffic arrival distribution of class 1 up to class d, that approximates the number of arrivals in the arrival slot of a class d tagged stream packet. It is based on the consideration that the assignment probability of the packets that arrive within the time slot group, which will be served ahead of the tagged packet. Subtract 1 from the total number of aggregated packets that arrive in the (n+1)th time slot group (i.e., n d A ( +1), ) due to the fact that the tagged frame is also among the overall traffic. The traffic distribution in (4.30) is based on P{A q} P(Q q) n d d − = = > + 2 1 1 1, ({ }) ∫∞ − ≈ > = d P Z e dx x m d max, 2 max 1 2 , 2 1 2 1 1 2 1 σ π (4.32) where q∈[1,(T −1)] , calculated using the MVA approach discussed in section 4.2. The discrete triangle distribution applied is a symmetric distribution, which represents the probability that the time slot position of two sequentially arriving frames will be offset by a jitter amount of +j or –j. Thus, the triangle distribution for the range [q, q] is applied as {~  1 ,} ( ) ( 1), , P J j A q f j n n d q d = − = = + 78 ⎪⎩ ⎪⎨ ⎧ ≤ + − = + 0, , , 1 ( 1) 1 2 min otherwise for j q A j q (4.33) which provides the normalized jitter probability of j given that q packet arrivals enter the server before the (n+1)th tagged packet of tagged stream, among the overall min A possible time slots. 4.4.1 Simulation and Numerical Study The jitter probability of heterogeneous traffic streams with HOL priority control in DiffServ networks has been investigated. The derivations of this section provide a direct method to analyze the perclass jitter based on the parameters ρ and T. Fig. 4.5 and 14 show the jitter probability distribution of three different classes for the case of T = 10 slots and ρ equal to 50%, and also assuming that the probability of traffic arrival in the T slot observation window for class 1, class 2, and class 3 are the same. Fig. 4.5 has shown the 95% CI for the delay jitter proportion between the real data set and the numerical analysis. The width of the 95% CI reveals the degree of uncertainty in the estimate of the treatment effect; in another words, this is the interval which includes the true value with 95% certainty. The wider the width the more uncertainty it is, and more data set that collected from the same population is needed to increase the confidence level. In Fig. 4.6, the approximation equation results are comparing to the simulation results of the jitter distribution. In Fig. 4.5 and 4.6, it can be observed that the probability distribution function of the interarrival packet jitter widens as the class priority is descending, thus resulting in a higher probability of packet jitter for low priority classes. This is an expected result, where the newly derived equations provide a method to directly compute 79 this physical probabilistic quantity. Also, for class 1 as ρ << 1 the probability of jitter at zero (no jitter) increases while the probability of jitter for the nonzero values is reduced. Fig. 4.5 Comparison among class 1, class 2 and class 3 with respect to the approximation equation and the simulation results of the jitter distribution for utilization of 50% with 95% CI, and T = 10. 80 Fig. 4.6 The comparison of probability jitter distribution among class 1, class 2, and class3, where utilization is 50% and T is 10. 81 Chapter 5 Conclusions In this dissertation, the following research has been conducted 1. Investigate the delay jitter performance of homogenous wireless networks that apply ARQ error recovery with time constraints have been developed. The effects on the delay jitter in reference to the priority control scheme of the ARQ traffic for the two cases are evaluated: i) the ARQ traffic has a priority over the original transmission traffic; and ii) the ARQ traffic has no priority over the original transmission traffic. 2. Investigate the issues of traffic jitter characteristics in heterogeneous wired communication networks deploying different scheduling algorithms: • Obtain the tail probability P{Q>q} based on the MVA approach for discrete time queueing model [25][26] to conduct the queue length analysis, which is used in heterogeneous jitter analysis. • To find the pmf (probability mass function) of interarrival packet jitter from the queue length distribution. 3. The objective of this dissertation is to investigate and analyze the various possible traffic modeling techniques and evaluate the challenges in characterizing the diverse statistical properties of heterogeneous wireless networks [1343][5660]: 82 • Study the characteristics of the traffic: selfsimilarity, heavytailed distribution, Gaussian traffic distribution. • Comparisons among the popular traffic models. 4. Apply the Gaussian traffic modeling using the MVA approach [25][26] to conduct the queue length analysis, which will be further used in heterogeneous jitter analysis [112]. 5. Analyze the difference between jitter probability of multiple priority queues and switches [112]: • The headofline (HOL) priority queueing mechanism is applied at the queueing and scheduling control. 6. Develop a service discipline called the tagged stream adaptive distortionreducing peak outputrate enforcing to control and avoid the delay jitter increases without bound. In conclusion, using the Gaussian traffic modeling technique combined with the MVA approach for selfsimilar network traffic, the delay jitter was shown with the 95% CI for the delay jitter proportion between the real data set and the numerical analysis. For future research, this analysis will be extended to multiple priority queueing case. The multihop jitter of wireless and wired network analysis can be conducted, where endtoend congestion control is needed at a router for fair bandwidth allocation perflow. The CoreStateless Fair Queueing (CSFQ) [47] can be applied to allocate fair bandwidth perflow, and performance is evaluated (the number of congested links). 83 References 1. C. C. Bisdikian, W. Matragi, and K. Sohraby, “A Study of the Jitter in ATM Multiplexers,” High Speed Networks and their performance: IFIP Trans. C, Commun. Systems, C21, pp. 219235, New York, 1994. 2. T. C. Wong, J. W. Mark, K. C. Chua, and B. Kannan, “Delay jitter performance of voice traffic in a cellular wireless ATM network,” Proc. IEEE 55th Veh. Technol. Conf.Spring 2002, vol. 1, pp. 9094, May 2002. 3. D. Zhao, X. Shen, and J. W. Mark, “QoS performance bounds and efficient connection admission control for heterogeneous services in wireless cellular networks,” Wireless Networks, vol. 8, pp.8595, 2002. 4. C.S. Chang, K.C. Chen, M.Y. You, and J.F. Chang, “Guaranteed qualityofservice wireless access to ATM networks,” IEEE J. Selected Areas in Commun., vol. 15, no. 1, Jan. 1997. 5. D. Zhao, X. Shen, and J. W. Mark, “Efficient call admission control for heterogenous services in wireless mobile ATM networks,” IEEE Commun. Mag., vol. 38, pp. 72 78, Oct. 2000. 6. W. K. Wong and V. C. M. Leung, “Scheduling for integrated services in next generation packet broadcast networks,” Proc. IEEE Conf. Wireless Commun. and Netw., vol. 3, pp. 12781282, Sept. 1999. 84 7. S. Marwaha, C. K. Tham, and D. Srinivasan, “A novel handover mechanism for wireless mobile ad hoc networks,” Proc. ICCS 2002, vol. 2, pp. 10631067, Nov. 2002. 8. U. Lambrette, L. Bruhl, and H. Meyr, “ARQ protocol performance for a wireless high data rate link,” Proc. IEEE 47th Veh. Technol. Conf.Spring 1997, vol. 3, pp. 1538 1542, May 1997. 9. J.M. Chung and H. M. Soo, “Jitter Analysis of Homogeneous Traffic in Differentiated Services Networks,” IEEE Commun. Lett., vol. 7, no. 3, pp. 130132, Mar. 2003. 10. A. Privalov, and K. Sohraby, “PerStream Jitter Analysis in CBR ATM Multiplexors,” IEEE/ACM Trans. on Netw., vol. 6, no. 2, Apr. 1998. 11. J.M. Chung, H. M. Soo and W.C. Jeong, “Jitter Analysis of Homogeneous Traffic in Wireless Differentiated Services Networks,” Proc. IEEE LANMAN 2004, CA, USA, Apr. 2528, 2004. 12. J. J. Metzner and J.M. Chung, “Efficient Energy Utilization with Time Constraint in Mobile Time Varying Channels,” IEEE Trans. Veh. Technol, vol. 49, no. 4, pp. 1169 1177, July 2000. 13. R. G. Addie, “On the applicability and utility of Gaussian models for broadband traffic,” Proc. IEEE Intl. Conf. on ATM, 1998. 14. P. Mannersalo and I. Norros, “GPS schedulers and Gaussian traffic,” Proc. IEEE INFOCOM, 2002. 15. S. Sarvotham. R. Riedi, and R. Baraniuk, “Connectionlevel Analysis and Modeling of Network Traffic,” IMW’01, CA, Nov. 2001, pp. 99103. 85 16. S. Ma and C. Ji, “Modeling Heterogeneous Netwrok Traffic in Wavelet Domain,” IEEE/ACM Trans. Networking, vol. 9, no. 5, Oct. 2001, pp. 634649. 17. H. Fei and W. Zhimei, “A Novel Traffic Based on Wavelet analysis,” Proc. ICCT 2003, vol. 2, April 2003, pp. 13921395. 18. Petteri Mannersalo, Gaussain and multifractal process in teletraffic theory, 2003. 19. R. G. Addie, “Traffic will be more Gaussian in Future,” Australian Telecom. Networks and Applications Conference. December, Melbourne, 1996. 20. R. G. Addie, On weak convergence of longrange dependent traffic processes, Technical Report SCMC9816, University of Soutern Queensland, 1998. 21. Damon Wischik, “Implications of longrange dependence,” notes on the implications of longrange dependence for optical networks, Feb. 2001. 22. R. G. Addie, “On the weak convergence of long range dependent traffic process,” Proc. of the International Workshop on Long Range Dependent, Jan. 1997. 23. P. Mannersalo and I. Norros, “GPS schedulers and Gaussian traffic,” in Proc. IEEE INFOCOM, 2002. 24. R. G. Addie, “On the applicability and utility of Gaussian models for broadband traffic,” Proc. IEEE Intl. Conf. on ATM, 1998. 25. J. Choe and N. B. Shroff, “A centrallimittheorembased approach for analyzing queue behavior in highspeed networks,” IEEE/ACM Trans. On Networking, vol. 6, no. 5, Oct. 1998, pp 659671. 26. J. Choe and N. B. Shroff, “ A new method to determine the queue length distribution at an ATM multiplexer,” in Proc. IEEE INFOCOM, 1997, pp. 550557. 86 27. R. G. Addie, M. Zukerman, and T. D. Neame. “Broadband traffic modeling: simple solutions to hard problems,” IEEE Communications Magazine, August. 1998, pp 88 95. 28. J. Abate, G. L. Choudhury, and W. Whitt, “Exponential approximations for tail probabilities in queuesI: Waiting times,” Oper. Res., vol. 43, no. 5, pp. 885901, 1995. 29. R. G. Addie and M. Zukerman, “An approximation for performance evaluation of stationary single server queues,” IEEE Trans. Commun., vol. 42, pp. 31503160. 30. R. Guerin, H. Ahmad, and M. Naghshineh, “Equivalent capacity and its application to bandwidth allocation in highspeed networks,” IEEE J. Select. Areas Commun., vol. 9, pp. 968981, Sept. 1991. 31. A. Simonian, “Stationary analysis of a fluid queue with input rate varying as an OrnsteinUhlenbeck process,” SIAM J. Appl. Math., vol. 51, pp. 828842. 1991. 32. R. G. Addie, M. Zukerman, and T. Neame, “Performance of a single server queue with self similar input,” IEEE 1995. 33. R. W. Wolff, Stochastic Modeling and the Theory of Queues, Prentice Hall, New Jersey, 1989. 34. Will E. Leland, Murad S. Taqqu, Walter Willinger, and Daniel V. Wilson, “On the selfsimilar nature of Ethernet traffic (extended version),” IEEE/ACM Trans. Net., vol. 2, no.1, Feb. 1994, pp. 115. 35. F. H. P. Fitzek and M. Reisslein, “MPEG4 and H.263 video traces for networks performance evaluation,” IEEE Net., Nov. 2001, pp. 4054. 36. Murad S. Taqqu, http://math.bu.edu/people/murad/methods/index.html 87 37. Arifler and B. L. Evans, “Modeling the selfsimilar behavior of packetized MPEG4 video using waveletbased methods,” Proc. Image Processing 2002, 2002, vol. 1, pp. 848851. 38. Thomas Karagiannis and Michalis Faloutsos, “SELFIS: A Tool For SelfSimilarity and LongRange Dependence Analysis,” 1st Workshop on Fractals and Self Similarity in Data Mining: Issues and Approaches (in KDD) Edmonton, Canada, July 23, 2002. 39. Thomas Karagiannis , http://www.cs.ucr.edu/~tkarag/Selfis/Selfis.html 40. D.R.Avresky, V. Shurbanov, R. Horst and P. Mehra, “Performance Evaluation of ServerNet R SAN under SelfSimilar Traffic,” 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Proc., Apr. 12  16, 1999, San Juan, Puerto Rico, pp. 143147. 41. The trace/data set, Star Wars IVat, http://wwwtkn.ee.tuberlin.de/research/trace/trace.html 42. The trace/data set, Ethernet traffic, http://math.bu.edu/people/murad/methods/index.html 43. R. C. Garcia and J.M. Chung, “Network Anomaly Detection Using A SelfSimilar Traffic Model Report”, NSF DMI0339471, Jan. 31, 2004. 44. W. Stallings, HighSpeed Networks TCP/IP and ATM Design Principles, Prentice Hall, New Jersey, 1998. 45. R. M. Loynes, “The Stability of a Queue with Nonindependent Interarrival and Service Times,” Proc. Cambridge Philos Soc., vol. 58, pp. 497520, 1962. 88 46. R. J. Adler, An Introduction to Continuity Extrema and Related Topics for General Gaussian Processes, Hayward, CA, Institute of Mathematical Statistics, 1990. 47. I. Stoica, S. Shenker, and H. Zhang, “CoreStateless Fair Queueing: A Scalable Architecture to Approximate Fair Bandwidth Allocations in HighSpeed Networks,” IEEE/ACM Trans. Net., vol. 11, no.1, Feb. 2003, pp. 3346. 48. P. Billingsley, Probability and Measure, New York: John Wiley & Sons, 1979. 49. E. Wong and B. Jajek, Stochastic Processes in Engineering Systems, New York: SpringerVerlag, 1985. 50. R. Landry and Ionnis Stavrakakis, “Study of Delay Jitter With and Without Peak Rate Enforcement,” IEEE/ACM Trans. On Commun., vol. 5, no. 4, Aug. 1997, pp. 543 553. 51. C.N. Chuah, R. H. Katz, Network provisioning and resource management for IP telephony, University of California, Berkeley, Report no. UCB/CSD991061, Sept. 1, 1999. 52. L. Zhang, L. Zheng, and K. S. Nge, “Effect of delay and delay jitter on voice/video over IP,” Elsevier Computer Commun., vol. 25, 2002, pp. 863873. 53. X. Xiao and L. M. Ni, “Internet QoS: A Big Picture,” IEEE Network, March/April 1999, pp. 818. 54. S. Blake, D. Black, M. Carlson, E. Davies Z. Wang, and W. Weiss, “An Architecture for Differentiated Services,” RFC 2475, Dec. 1998. 55. T. Li, and Y. Rekhter, “A Provider Architecture for Differentiated Services and Traffic Engineering (PASTE)”, RFC 2430, Oct. 1998. 89 56. Jinwoo Choe, Ness B. Shroff, "Use of the Supremum Distribution of Gaussian Processes in Queueing Analysis with LongRange Dependence and SelfSimilarity," Communications in Statistics  Stochastic Models, v 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


