Loss Probability of LRD and SRD Traffic in Generalized Processor SharingSystemsXiaolong Jin and Geyong MinDepartment of Computing, School of Informatics,University of Bradford, Bradford, BD7 1DP, UK{x.jin, g.min}@brad.ac.ukAbstractGeneralized Processor Sharing (GPS) is an efficient andflexible scheduling mechanism for sharing server capac-ity and providing differentiated Quality-of-Service (QoS)owing to its appealing properties of fairness, traffic isola-tion, and work conservation. This paper analytically in-vestigates the loss probabilities of individual traffic flowsin GPS systems subject to heterogeneous Long-Range De-pendent (LRD) and Short-Range Dependent (SRD) traffic,which have not been studied in the open literature. We de-rive and validate the closed-form expressions of the lossprobabilities of both traffic flows. We then evaluate the ef-fects of Hurst parameter of LRD traffic on the performanceof GPS systems in terms of traffic loss probability.1 IntroductionTraffic scheduling mechanisms are crucial to providedifferentiated Quality-of-Service (QoS) (e.g., packet delayand loss) for a diverse spectrum of network applications.As a promising traffic scheduling mechanism, GeneralizedProcessor Sharing (GPS) [13] has attracted tremendous re-search efforts owing to its appealing features, such as, fair-ness, traffic isolation, and work conservation [17, 18]. TheGPS mechanism assigns each traffic flow a fixed weightwhich can then guarantee a minimum service rate for theflow even though other traffic flows may be greedy in de-manding service. This property helps GPS achieve relativefairness among traffic flows, and meanwhile makes it possi-ble to isolate different flows and provide differentiated QoS.GPS is work-conserving in that it can redistribute any ex-cess service to backlogged traffic flows.Long-Range Dependent (LRD) characteristics (i.e.,large-lag correlation and scale-invariant burstiness) of net-1-4244-0910-1/07/$20.00c2007 IEEE.work traffic have been discovered by many recent measure-ment studies [1, 7, 14]. The fractal-like nature of LRDtraffic has significantly different theoretical properties fromthose of the conventional Short-Range Dependent (SRD)processes (e.g., Poisson processes, Markov modulated fluidprocesses [15]). However, most existing studies based onanalytical models have been limited to GPS systems subjectto either SRD traffic or LRD traffic only, such as, [5, 15, 19]for SRD traffic and [2, 3, 8, 18] for LRD traffic. Althoughpacket loss probability, as one of the most important QoSmetrics, plays a key role in the design, evaluation, and opti-mization of traffic scheduling mechanisms, no efforts havebeen reported in the open literature to analytically investi-gate the loss probability of GPS systems in the presence ofheterogeneous LRD and SRD traffic.Based on the analytical upper and lower bounds for thequeue length distributions of GPS systems reported i n [4],we derive the closed-form expressions of the loss probabili-ties of both flows in GPS systems fed with heterogeneousLRD fractional Brownian motion (fBm) traffic and SRDPoisson traffic. We demonstrate the validity and accuracy ofthe obtained loss probabilities t hrough comparison betweenanalytical results and extensive simulation results. Besides,we study the performance of GPS systems in terms of trafficloss probability under different working conditions. The re-sults reveal that the loss probability of LRD traffic increasessharply as its Hurst parameter increases, but the loss prob-ability of SRD traffic remains unchanged due to the flowisolation nature of GPS.The rest of the paper is organized as follows. In Section2, we introduce the characteristics and mathematical de-scription of heterogeneous LRD fBm traffic and SRD Pois-son traffic. We briefly review the upper and lower boundsfor the tails of queue length distributions of individual traf-fic flows in GPS systems subject to heterogeneous fBm andPoisson traffic in Section 3. Next, Section 4 derives theloss probabilities of fBm and Poisson traffic. Section 5 val-idates the analytical results through extensive experimentalsimulations and analyzes the performance of GPS systems.Finally, Section 6 concludes the paper.2 LRD versus SRD TrafficThis paper is intended to study the loss probabilities ofheterogeneous traffic in GPS scheduling systems. Specif-ically, we address two types of traffic, namely, LRD fBmtraffic and SRD Poisson traffic. In what follows, we willbriefly review the modelling issues of LRD and SRD traf-fic.Generally speaking, a traffic flow1can be modelled as astochastic process and denoted in a cumulative arrival formas A = {A(t)}t∈N, where A(t) is the cumulative num-ber of traffic arrivals at time t. Consequently, A(s, t)=A(t) − A(s) denotes the amount of traffic arriving in timeinterval (s, t].TrafficflowA can also be denoted in an in-crement form, i.e., A = {B(t)}t∈N, where B(t) is the traf-fic arriving in time interval (t − 1,t] with B(0) = 0. Thesetwo representation forms have the following relationship:A(t)=ti=0B(i) and B(t)=A(t) − A(t − 1).Note that for the sake of clarity of the model derivation,hereafter we will use subscripts f and p to distinguish agiven quantity of fBm and Poisson traffic, respectively.2.1 LRD fBm trafficSince the innovative study of Leland et al. [7] on LRDtraffic, many models and techniques have been developed tocharacterize traffic long-range dependence or generate LRDtraffic traces. Among the existing models, fractional Brow-nian motion (fBm) is identified as the most efficient and ac-curate way for modelling and generating LRD traffic [11].An fBm traffic flow can be expressed as Af= {Af(t)}t∈N[11]:Af(t)=λft + Zf(t), (1)where λfis the mean arrival rate and Zf(t)=afλf¯Zf(t).¯Zf(t) is a centered (i.e., E(¯Zf(t)) = 0)fBm with variance Var(¯Zf(t)) = t2Hf. The variance andcovariance functions of Afcan be given as follows:Var(Af(t)) = afλft2Hf, (2)Γf(s, t)=12afλf t2Hf+ s2Hf− (t − s)2Hf, (3)where H ∈ (12, 1] is Hurst parameter indicating the degreeof long-range dependence.In the increment form, traffic flow Afcan be expressedas Af= {Bf(t)}t∈Nwith mean arrival rate E(Bf(t)) =λfand variance Var(Bf(t)) = afλf.1All traffic flows are modelled in discrete time in this paper.2.2 SRD Poisson trafficUsing the similar notation of fBm traffic in Eq. ( 1), aPoisson traffic flow can be denoted as Ap= {Ap(t)}t∈N:Ap(t)=λpt + Zp(t), (4)where λpis the mean arrival rate