3 EWF-BA for Supporting Fair Service Allocation

Multiple Service in Optical Access Networks

NamUk Kim, HyunHo Yun, Yonggyu Lee, and Minho Kang

Optical Internet Research Center, Information and Communication University, 119, Munjiro,Yuseong, Daejon, (305-714), Korea(ROK)

{niceguy, exhyho, yonggyu, mhkang}@icu.ac.kr

Abstract. In this paper, the service work reservation method for the efficient service differentiation and the bandwidth arbitration for the fair service allocation among access nodes are fully studied. In the polling based generalized TDM networks, QoS (Quality of Service) based mul- tiple service is achieved by the reservation based service scheduling as well as the class based packet scheduling. These are tightly coupled with each other in every protocol step and determine the final performances of multiple service. For the seamless fair service, we propose the ser- vice quality pre-engagement (SQP) scheme and the equal weighted fair bandwidth arbitration (EWF-BA) mechanism. These make the thread based fair service allocation among access nodes possible while the class based service differentiation is maintained. The analytic and simulation results reveal that proposed mechanisms efficiently guarantee the QoS based multiple service with high network performances and the service fairness.

1 Introduction

The dynamic bandwidth allocation over the polling based generalized TDM net- works is applied to many access networks such as Ethernet-PON (Passive Optical Networks) and WDM optical networks for upstream data transmission control[1- 3]. Contrast to the simple broadcast and select mechanism of downstream[1], the upstream transmission scheduling is complicate because the channel must be ef- ficiently and fairly shared by all ONU(Optical Network Unit)s. At the same time, the moderate QoS level must be guaranteed for supporting multiple ser- vice. In the generalized TDM network, the data channel consists of two kinds of time unit, the service slot and the frame cycle. The service slot represents for single ONU’s allocated bandwidth in time domain during which ONU transmits queued data to OLT(Optical Line Termination). The frame cycle, generally ex- pressed as the frame in circuit switched networks, is total sum of service slots of every ONUs. Hence, the efficiency of the service reservation for multiple services and the service work coordination for high utilization are the performance criti- cal. These performances are tightly related with each other. Up to now, several protocols are contributed to this issue[1,3]. Among these, the simplest one is the static bandwidth allocation (SBA) which fixes the service slot and the frame

M. Freire et al. (Eds.): ECUMN 2004, LNCS 3262, pp. 81–90, 2004.

c Springer-Verlag Berlin Heidelberg 2004

no arbitration scheme like IPACT[1] in OLT side. It supports the static service fairness. Based on these service coordination mechanisms, general class based packet schedulings can be applied to the upstream port of ONU for multiple service[3]. But the performance of packet scheduling is tightly correlated with the service coordination(service work scheduling) because arbitration determines the service bandwidth within which packet scheduler sends data packets.

In this paper, we propose the noble SQP-DBA(Service Quality Preengage- ment with DBA) that is the QoS bandwidth reservation mechanism under the strict priority(SP) queuing packet service. Then, we also introduce a new ser- vice work scheduling mechanism, EWF-BA(Equal Weighted Fair - Bandwidth Arbitration), to achieve the high network performances as well as the real time service fairness in inter ONU domain. Although proposed mechanisms are intro- duced to the Ethernet-PON networks for analysis, our schemes can be applied to all kinds of generalized polling based TDMA networks independent from the physical media and topological differences.

2 Supporting Multiple Service in DBA Based Networks

Like other switch networks, general packet scheduling methods can be applied to ONU’s upstream data transmission for supporting multiple service[2]. But due to the DBA’s discrete operation, WFQ and the proportional delay differentiation (PDD) are hard to guarantee the tight delay bound and the efficient service differentiation in spite of high complexity. In this paper, we consider SP for the service differentiation. SP guarantees the absolutely prioritized service to higher priority traffic. But it easily causes the bandwidth monopolization and resultant service starvation of low class. This can be more serious when SP is applied with DBA. These problems mainly comes from the fact that the packet scheduling is separated from the channel reservation. The DBA mechanism for the service work scheduling is done with three steps. In next chapter, we briefly overview the DBA service reservation. For easy expressions, following notations are used when ONU_j, and m_th cycle are assumed. All notations are expressed for the class i ofj_thONU of total N ONUs networks.

•Q^m_i,j(t): Size of all queued data frames at arbitrary time t

•D^m_i,j: Reported queue size at service slot ending instance form+ 1_thcycle

•A^m_i,j:Allocated bandwidth by service work arbitration

•S_i,j^m:Total serviced data frames(service work)•R: Upstream link speed

•t_m:Arrival instance ofm_thgate message •λ_i : Traffic arrival rate

Fig. 1.Service reservation procedures of DBA.

We also assume that traffic is grouped into K classes of service which are ordered, such that class i is better than class i+1 from class 0 to class K-1, in terms of the queuing delay and the packet loss. Hence, the notation X_j^m for ONUj (X can be Q, D, A, S) is equal to the sum of all classes,_K−1

n=0 Xi,jm. 2.1 Service Work Reservation Mechanisms of DBA

Under DBA, the data transmission is done with three consecutive steps as shown in Fig.1. First, ONU reserves the next cycle’s bandwidth(service slot) by sending the Report message in which D_j^m is set to Q^m_j (tm+A^m_j /R) at the end of the service slot. Secondly, when OLT receives Report message, it arbitrates the re- quest service work ofONUj with those of other ONUs. Then, it notifiesONUj

of the size of the following cycle’s service slot, A^m_j⁺¹, with the Gate message which will be sent with considering the reference time difference between OLT and ONU. Generally, that is little larger than the sum of the guard band time and two times of tp. Along with this service work scheduling, OLT also must check the variation oft_p as well as physical device’s performance parameters to avoid data collisions. Finally, when Gate message arrives,ONU_j transmits data frames to OLT within A^m_j ⁺¹. Hence, the real service work(S_j^m+1) is always no larger thanA^m_j⁺¹. Hence, major properties of DBA operation are the backward reservation and the discrete service with the long service vacation[1]. With this reservation based DBA, the pipelined service is possible with the high utilization and the robustness to burst traffic.

2.2 SQP-DBA for QoS Based Multiple Service Reservation

When SP is applied, the service work reservation under DBA is done as follows.

D^m_i,j=Q^m_j (tm+

K−1 i=0

S_i,j^m/R), S_i,j^m ≤A^m_i,j (1)

S^m_i+1,j =min(Q^m_i+1,j(tm), A^m_j −

i

n=0

Q^m_n,j(tm)), i≤K−2 (2) Therefore, the prioritized service for the high class is easily guaranteed. But as the traffic load increases or burst traffic arrives in short epoch, the large service

i=0

(S_i,j^m −D^m_i,j) =

i=0

S^m_K−1,j =−S_K−^m 1,j =D^m_K−1,j−S_K−^m 1,j (3) Therefore it is impossible for the low class traffic to receive the reserved service due to the bandwidth shortage, D^m_i,j >> A^m_i,j⁺¹ = (A^m_i,j⁺¹ −_i−2

n=0Q^m_n,j⁺¹) . When burst traffic happens, this problem can continue to several cycles[3].

Therefore, increased SRG enlarges the average buffer size and arouses the long transfer delay of lower classes. As shown in (3), S is inevitable due to the backward reservation property of DBA and is independently determined by higher priority class traffic’s arrival. Therefore, for the efficient multiple service that guarantees each class the expectable service level even under the absolute SP, it is important to minimize the unpredictable SRG. Proposed SQP-DBA satisfies this by the QoS based service reservation. In SQP-DBA, ONU reserves the next service slot as the sum of total queued frame size and the QoS reservation bandwidth,Dqos determined by the service policy. Simply, we choose Dqos as the current cycle’s service work of quality guaranteed p classes. Therefore, the bandwidth reservation ofONU_j is done

D^m_i,j=Q_queue+D_qos=Q^m_i,j(t_m+

K−1 i=0

A^m_i,j/R) +S_i,j^m, i≤p (4)

D_j^m=

K−1 i=0

Q^m_i,j(t_m+

K−1 i=0

A^m_i,j/R) +

p

i=0

S_i,j^m (5)

By this, if there is no abrupt change of traffic arrival in the service vacation,S can be reduced to _K−2

i=p+1S_i,j^m−D^m_i,j . Hence, the lower priority traffic(i > p) does not experience the serious bandwidth starvation. But, there can be two sorts of reservation mismatches as follows.

i. D^m_qos <_p

i=0λiV^m≈_p

i=0Qi,j(tm+1) case : This happens when burst traf- fic arrives abruptly. By the SRG mismatch, lower priority classes from p+1 to K-1 lose their reserved bandwidth with amount of_p

i=0Q_i,j(t_m+1)−D_qos and backlogged. But this mismatch is rapidly reflected to the next cycle reservation by QoS bandwidthD^m_qos⁺¹. and can be serviced by DBA in the following cycle.

ii. D^m_qos > _p

i=0λ_iV^m ≈ _p

i=0Q_i,j(t_m+1) case :In this case, high class traffic rapidly diminishes after reservingD_QoS due to the change of the number of ser- vice applications or customers. But this is not a problem because there always are queued packets in low class buffers by the backward reservation property of DBA.

Hence, the service work of lower classes increases with the amount of SRG as

K−1 i=p+1

S_i,j^m+1 =D^m_qos−

p

i=0

Q_i,j(t_m)(=

p

i=0

λ_iV^m) +

K−1 i=p+1

D^m_i,j (6)

Fig. 2.(a)Service curve of SQP and SP under DBA (b)simulation result of SRG.

Therefore the delay of lower class traffic becomes short while there is no perfor- mance degradation of the channel utilization or throughput.

In any cases, it is possible that the lower prioritized non-real time traffic can be serviced by the original DBA’s reservation mechanism while the objective QoS guaranteed p classes traffic is serviced with the minimum delay and the abso- lutely guaranteed throughput. Moreover, becauseD_qos is set to the current cy- cle’s serviced work of p classes, the change of service pattern is rapidly reflected to the whole service reservation mechanism. This rapid service adaptation of SQP- DBA is easily explained by surveying the service tracking speed which means how fast the service scheduler follows and affects the traffic arrival pattern(demand) change to service scheduling. Fig. 2 shows the service curve and the simulation result of SP and SQP under DBA. The traffic arrival of each cycle is character- ized by λm. Packet service is done during service slot with the service rate R which is same to the gradient(∆) of the service curve. In service curve, the delay is examined as the horizontal deviation between the arrival and the service curve and the queue size is the vertical deviation. Hence, the delay and queue increases in the vacation and the service scheduler tracks the arrival curve by the service reservation. Hence, the performance critical factor is the service tracking speed.

When m_th vacation time(V^m) is enough larger than the service slot Q^m_j /R), which is general, and is assumed as upper bounded by value V with OLT’s service arbitration scheme, the service rate of SQP+DBA is approximately,

R_SQP ≈R[

K−1 i=0

Q^m_i,j(t_m+S^m_j /R) +

p

i=0

S_i,j^m]/^K−

1

i=0

Q^m_i,j(t_m+S^m_j /R) (7)

=R[1 +

p

i=0

S_i,j^m/(Q^m_j −S_j^m)]> R,0≤p≤K−1 (8)

The gradient of SQR-DBA service curve,R_SQR, is higher than SP+DBA case in every service slot. The access delay by the increased QoS bandwidth is negligible compared with the vacation period. Therefore, SQP-DBA can track

of lower priority classes is driven as[4]

Q_low= λ_lowL²

2(1−ρlow)+ξ(ρ_p) ρ_p

1−ρpE[V]−ρ_lowE[V] +ρ_lowE[V]²

2E[V] (9) Theξ(ρp) is used to intuitionally reflect the effect of higher priority classes. It proportionally increases according toρ_pbecause largeρ_pbrings about large back- logged queue of lower classes. In case of SP+DBA, p is equal to K-2. Hence, the lowest priority class is affected byρ_SP =_K−2

i=0 ρ_iand the large queue and delay are invoked byξ(ρ_p)ρ_SP/(1−ρ_SP). But in SQP-DBA,D_qosis already reserved for higher p classes. Therefore, the effective load is changed toρ_SQP =ρ−_p

i=0ρ_i=

_K−2

i=p+1ρiand this meetsξ(ρSQP)ρSQP/(1−ρSQP)<< ξ(ρp)ρSP/(1−ρSP). By this service load separation, low priority classes(i > p) contend for service among only K-1-P classes. It minimizes the performance degradation of non-real time lower priority traffic although SP is strictly applied for the real time traffic.

This guaranteed and isolated service differentiation for the real multiple service is the objective of SQP-DBA. By SQP-DBA’s QoS bandwidth pre- reservation scheme, the real traffic can be serviced always within the minimum queuing delay with the minimum interference to lower priority classes. This makes the service quality pre-engagement of each service class with the service policy possible. It can also solve the light load penalty problem of the one stage SP scheduler system[3]. This happens when SRG is same to the high classes’

total traffic intensity of service vacation. This causes the low class’ long queuing delay even in the light load condition. Especially, when higher class traffic is pe- riodic, the light load penalty more easily happens. This problem can be resolved by SQP whenDqos is set to total sum of periodic traffic. Hence, the important issue of SQP is the choice of p value. In the best case, p can be K-1 but it causes the low channel utilization by the large SRG mismatch because it is not the back- ward reservation mechanism any more. Along with this, there needs two times of the original link bandwidth for supporting doubled request. Hence, generally, it is reasonable to set p as the total number of periodic real time traffic classes.

By this, multiple service of SQR and the high utilization of DBA are guaranteed simultaneously. But the SQP-DBA client has no control authority for service allocation. Hence, there must be the optimized service work scheduling in OLT, defined as the arbitration, for the service fairness and high performances in net- work domain. In next section, we introduce the equal weighted fair-bandwidth arbitration (EWF-BA) mechanism to efficiently support these demands.

3 EWF-BA for Supporting Fair Service Allocation

In well arbitrated networks, the service work is fairly and efficiently distributed to all ONUs in the short epoch. Under DBA, the service fairness is directly determined by two elements,V_j^mandA^m_j . First,V_j^maffects the the queuing delay and zitter.A^m_j is a crucial factor of the service thread which reveals how stably and consistently the service is maintained with the consistent pattern. Proposed EWF-BA is a noble service work scheduling scheme which arbitrates the service slot with consideration of the service demand as well as the service thread of each ONU.Vc is assumed as the optimized frame cycle by which the QoS guaranteed service is possible to all N ONUs. The static arbitration that is based on the max-min theory allocates the service work byA^m_j⁺¹= min(D^m_j ,VcR/N). Hence, it guarantees the static service fairness which everyS_j^msatisfies fair conditions of | S^m_j ⁺¹−S_j^m |≤ RT_c/N and | S_j^m−S^m_k |≤ RT_c/N, j = k. Therefore the service interval is not more than T_c in any cases. But it is impossible for burst ONUs that reportsD^m_burstto efficiently use the unused bandwidth of under-flow cycle in whichD_burst^m >> V_cR/N happens. so, burst ONU must wait for several cycles if total network load is low. This is not fair if demand based best service is considered. EWF-BA targets for real time fair service arbitration that keeps the thread of each ONU. In general DBA which does not fix the frame cycle,Vm

varies by the arbitration.

The objective of EWF-BA is to maintain the equal service fairness among ONUs in the short epoch as well as the long time period by maintaining the service ratio equal to all ONUs as| S_j^m+1−S_j^m|=| S_k^m+1−S^m_k |, k =j. This keeps the service fairness under any arbitration result. When the policy based weighted fair services is considered, it is also possible to apply the different service ratioµ_i to each class for different service weight as

|S^m_j ⁺¹−S_j^m|/|S_k^m+1−S_k^m|=µ_j/µ_k,^K−

1

i=0

µ_i =µ,0≤k≤K−1 (10)

In this paper, we target for only the equal weighted fair case in which the service ratio is same to all ONUs but the different weight is also applicable with same approach. For the thread based fair service, we introduce two parameters. The one is the bandwidth occupation ratio C_m. It shows the service ratio of each ONU compared with total service work of N ONUs in the previous cycle at the OLT’s arbitration instance. C_m is expressed as following equation when t^m_j,R is the time instance at which ONUj’s m_th report frame arrives at OLT, C_j^m=A^m_j /_N−1

n=0 A^m_n =A^m_j /(t^m_j,R⁺¹−t^m_j,R)R. It can be calculated by the simple time calculation as shown in Fig.3. ByC_m, it is possible to reflect the service thread of each ONU to the arbitration. The other is the overflow ratio, R^m_j = [_N−1

n=0,n=j(A^m_j +D_j^m)−V_cR]/V_cR, which is the excessively requested bandwidth ratio normalized by V_cR. It is meaningful only when _N−1

n=0,n=j(A^m_j +D^m_j ) is greater than VcR. These parameters are proportionally reflected to the final reduction weight value,W_j^m+1, to keep the thread as well as the service fairness.

Fig. 3.Service reservation procedures of DBA.

In stable service condition, (W0^mD^m0 +W1^mD1^m+...+W_N−^m 1D^m_N−1) < V_cR is maintained. Hence, OLT calculates the reduction weight asW0^m = (normalized C_j^m)R^m_j =A^m_j N[_N−1

n=0,n=j(A^m_j +D^m_j )−VcR]/VcR_N−1

n=0 A^m_n . Based on this, if_N−1

n=0,n=j(A^m_j +D^m_j )> VcR, OLT arbitrates service slot by following (11).

A^m_j⁺¹=D_j^m[1−A^m_j N[

N−1 n=0,n=j

(A^m_j +D_j^m)−V_cR]/V_cR(

N−1 n=0

A^m_n +A^m_j )] (11)

In other cases,A^m_j is same to the requested bandwidth,D^m_j . Hence, the unused bandwidth of under-flow frame cycle is efficiently reallocated to bursty ONUs and the heavy load of over-flow frame cycle is distributed to all ONUs by the service ratio and the occupation ratio. Additionally, the service slot of each ONU does not rapidly diminish and the service thread can gradually converge to the fair quality without the abrupt change. Although Vm can be larger that Vc in some frames in EWF-BA, it will not be long by this dynamic load distribution.

4 Simulation Results and Performance Evaluation

For effective simulations, we assume that all incoming data frames are classified into three service classes in ONU as class0 for the CBR and real time, class1 for non-real time and class2 for best effort service. The ON/OFF model is applied to Poisson and burst traffic sources. Traffic Load is uniformly distributed over three classes. The frame size distribution follows the real estimated traffic model in Poisson and burst traffic[5]. In burst traffic environment, we applied Pareto distributed(Hurst parameter 0.8) traffic generation scenario.

Fig.4.(a) shows DBA guarantees high utilization and the lower delay in low traffic load. But the delay gradually increases in high traffic load due to the increased cycle frame size. Fig.4.(b) shows the average delay of SQP-DBA based on EWF-BA is lower than SQP-DBA only case in every classes. This result comes from the fact that EWF-BA efficiently distributes the heavy traffic load to all ONUs with the equal weight until network goes into the stable service state. Moreover, Fig.5.(a) shows that the maximum delay of EWF-BA is smaller than SQP-DBA only case and total numbers of longer delayed data frames over targeted SLA value is relatively small. Finally, the congestion resolution period, time gap to overcome the reservation mismatch, is just several cycles and this

Fig. 4.(a) Average end to end delay and utilization when Poisson traffic applied. (b) Average end to end delay when burst traffic applied.

Fig. 5.(a) Maximum end to end delay when burst traffic applied.(b) Service ratio and interval when burst traffic applied(load=0.8,H=0.9).

means that EWF-BA can efficiently service some burst ONUs while the service fairness is maintained. This is more obvious in Fig.5.(b) This is derived from the same simulation scenario of above one but more burst load. In DBA case, the service ratio that is the service work normalized by the original request work is always one. But the service interval is too large to efficiently support the QoS guaranteed service. Moreover, the serious congestion duration is unpredictable and uncontrollable. Oppositely, EWF-BA guarantees the relatively short service interval and its value shows upper bounded pattern. This is possible by the load distribution and the service arbitration of EWF-BA. The service ratio is generally lower than DBA but is also lower bounded. Therefore, the differentiated service for QoS can be guaranteed within minimum delay by SQP and under stable service pattern and fairness by EWF-BA. In this simulation, the average queue size of EWF-BA is generally lower than DBA but the maximum queue size

guaranteed fair service under the service work reservation and arbitration. The SQP-DBA supports the prioritized service for the QoS guaranteed high prior- ity traffic while the service intervention among classes is effectively minimized.

When EWF-BA scheme is applied, the network performances, especially the delay and the service fairness among access nodes, are enhanced even if burst traffic happens in some ONUs. The bandwidth starvation by some heavy loaded ONUs can be also resolved within relatively short time epoch by the EWF-BA’s thread based load distribution scheme although more buffer size is needed.

Acknowledgement. This work was supported in part by the Korea Science and Engineering Foundation (KOSEF) through OIRC project and ETRI.

References

1. Kramer, G., Mukherjee, B., Pesavento, G.: IPACT-a dynamic protocol for an Eth- ernet PON (EPON). IEEE Communication Magazine, Vol. 40, (2002), pp. 74-80.

2. Rege, K., Dravida, S., Nanda, S., Narayan, S., Strombosky, J., Tandon, M., Gupta, D.: QoS Management in Trunk-and-Branch Switched Ethernet Network. IEEE Comm. Mag, Vol. 40 (2002) pp. 30-36.

3. Kramer, G., Mukherjee, B., Dixit, S., Ye, Y., Hirth, R.: Supporting differentiated classes of service in Ethernet passive optical networks. Journal of Optical Network- ing, vol. 1, (2002), pp. 280-298.

4. Leung, K., Disenberg, M.: A Single-Server Queue with Vacations and Gated Time- Limited Service. IEEE Transaction on Communication, Vol. 38, No. 9 (1990).

5. Leland, W., Taggu, M., Willinger, W., Wilson, D.: On the Self-Similar Nature of Ethernet Traffic. IEEE/ACM Transactions on Networking, Vol. 2, No. 1, (1994) pp.

1-15.