基于IPS和不同周期定時控制的帶寬分配

楊 臻，程紅霞，邱保志

(1.鄭州師范學(xué)院 信息科學(xué)與技術(shù)學(xué)院，河南 鄭州 450044；2.鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450002)

0 引 言

隨著互聯(lián)網(wǎng)和計算機技術(shù)的飛速發(fā)展，用戶對帶寬的需求越來越高。雖然主干網(wǎng)和局域網(wǎng)的基礎(chǔ)設(shè)施也有非?？斓陌l(fā)展(如10Gbit以太LAN)，但隨著大量用戶訪問遠(yuǎn)程資源，接入網(wǎng)就降低了用戶總的網(wǎng)絡(luò)容量[1]。在早期的互聯(lián)網(wǎng)中，業(yè)務(wù)流量主要是由純文本網(wǎng)頁和圖片構(gòu)成，只需有限的帶寬容量就可完成。然而，現(xiàn)在大多數(shù)通過互聯(lián)網(wǎng)傳輸?shù)牧髁渴怯牲c對點文件、視頻共享、在線實時游戲、視頻流、視頻點播、教育、IP電話和IPTV等構(gòu)成。這些應(yīng)用在接入網(wǎng)側(cè)需要更多的帶寬，而且某些應(yīng)用在包時延變化(packet delay variation，PDV)、丟包率和端到端時延等服務(wù)質(zhì)量方面還有要求。為了滿足這些應(yīng)用在服務(wù)質(zhì)量方面的要求，服務(wù)提供商也在研究并不斷推出新的接入網(wǎng)技術(shù)，如提出了光纖到戶(fiber-to-the-home，F(xiàn)TTH)體系結(jié)構(gòu)[2]。最受歡迎的FTTH體系結(jié)構(gòu)便是無源光網(wǎng)絡(luò)(passive optical network，PON)結(jié)構(gòu)，由于其底層設(shè)施中只有無源光單元，能夠?qū)崿F(xiàn)低成本、高帶寬數(shù)據(jù)傳輸和遠(yuǎn)程接入等，因此它在光纖接入構(gòu)架中具有最好的經(jīng)濟性。在PON的下行方向，數(shù)據(jù)包在PON的中心局側(cè)廣播，即光線路終端(optical line terminal，OLT)；在用戶側(cè)，即光網(wǎng)絡(luò)單元(optical network unit，ONU)收集數(shù)據(jù)包并發(fā)送給用戶；在上行方向，由于眾多ONU通過單一光纖線路連接到OLT，故必須采用多址接入技術(shù)來克服擁塞狀況。在PON中，主要采用兩種多址接入技術(shù)：時分多址(time division multiple access，TDMA)和波分多址(wavelength division multiple access，WDMA)；在TDMA技術(shù)中，在網(wǎng)絡(luò)側(cè)有兩個主要的標(biāo)準(zhǔn)。一個是吉比特PON(gigabit PON，GPON)，由ITU-T制定；另一個是以太PON(ethernet passive optical network，EPON)，由IEEE 802.3ah工作組制定。

較易實現(xiàn)和低成本使得EPON比GPON在學(xué)術(shù)研究領(lǐng)域和工業(yè)界更受歡迎，所以關(guān)于提高EPON的性能如接入容量和服務(wù)質(zhì)量的研究引起了人們的廣泛關(guān)注，如EPON中的帶寬分配就是其中重要的研究方向之一。

EPON中的帶寬分配算法包括靜態(tài)的和動態(tài)的。在靜態(tài)分配算法中，OLT把固定大小不變的傳輸窗口分配給每個ONU，無需考慮每個ONU的流量要求；而在動態(tài)分配算法中，把大小可變的傳輸窗口動態(tài)地分配給不同的ONU，需要考慮每個ONU的流量要求。OLT和ONU之間的通信是通過多點控制協(xié)議(multipoint-control protocol，MPCP)來完成的。

針對EPON已提出了多種動態(tài)帶寬算法(dynamic bandwidth allocation，DBA)。早期的動態(tài)帶寬分配解決方案是由Kramer G.等提出的“具有自適應(yīng)周期時間的交叉輪詢”(interleaved polling with adaptive cycle time，IPACT)算法[3]，也稱為在線DBA，IPACT算法的最好變體就是采用最大窗口限制技術(shù)。在IPACT算法中，OLT以交叉方式逐個地發(fā)送GATE消息給ONU，無需等待其它ONU的下一個REPORT消息的到達(dá)。如果增加最大窗口尺寸，就可能導(dǎo)致ONU本地緩存器中數(shù)據(jù)包更長的等待時間；相反，如果減小窗口尺寸，又會導(dǎo)致更多的GATE和REPORT被傳輸，從而給系統(tǒng)帶來額外開銷；針對高負(fù)載ONU的公平帶寬分配，文獻(xiàn)[3]提出了另一種DBA算法，即基于交叉輪詢停止(interleaved polling with stop，IPS)的DBA，也稱為離線DBA。在該算法中，OLT在開始發(fā)送GATE消息給下一個周期的ONU之前，要等待來自全部ONU在每個周期的REPORT消息。這樣，OLT在開始為ONU分配帶寬之前，就可以知道全部ONU的總帶寬請求。因此，OLT就可以在高負(fù)載ONU之間公平地分配剩余帶寬。然而，離線DBA在上行信道插入了一個空閑時間Ttidle，Ttidle由算法的計算時間和OLT與ONU之間的往返時間(round trip time，RTT)(假設(shè)全部ONU有相同的RTT)構(gòu)成。

(1)

(2)

式中：Ri為第i個ONU請求的帶寬。之后，把在當(dāng)前周期里還沒有分配的剩余帶寬公平地在全部高負(fù)載ONU之間進行分配。

文獻(xiàn)[3]針對EPON提出了一種基于動態(tài)帶寬分配的智能模糊邏輯的延遲性能(intelligent fuzzy logic based dynamic bandwidth allocation，IFLDBA)算法，并從仿真的角度將IFLDBA與其它一些著名的算法的時延和帶寬利用率進行了比較。評估結(jié)果表明，IFLDBA能顯著改善數(shù)據(jù)包延遲和帶寬利用率。文獻(xiàn)[4]提出了一種高效節(jié)能的DBA算法，同時保證基于上游和下游方向的帶寬請求的網(wǎng)絡(luò)性能。文獻(xiàn)[5]針對EPON提出了一種DBA，如果在當(dāng)前周期中沒有輕負(fù)載存在，就可以通過選擇一個高負(fù)載ONU來提高空閑時間的利用，而且算法根據(jù)ONU的流量負(fù)載將輕負(fù)載ONU置入睡眠模式，以使高負(fù)載ONU充分利用其空閑時間。文獻(xiàn)[4,5]的算法都是基于解決離線DBA中的空閑時間問題而提出，但算法改變了ONU服務(wù)順序，從而可能導(dǎo)致PDV。同時算法要發(fā)送額外控制消息，這又會造成額外的開銷，用來減小ONU本地緩沖器中的包時延算法是隊列大小預(yù)測算法[6,7]。如果一個ONU能夠預(yù)測它在下一個周期的緩沖器大小，則它就請求必需的帶寬而無需等待一個周期時間。然而，本地流量源的突發(fā)性以及不準(zhǔn)確的隊列大小預(yù)測也會造成帶寬浪費。文獻(xiàn)[8]針對目前WDM-EPON中帶寬分配和接入存在的問題，提出了一種低成本保護結(jié)構(gòu)及動態(tài)資源分配算法，目的是降低WDM-EPON的接入成本和提高傳輸效率。文獻(xiàn)[9]研究了多信道波分復(fù)用/時分復(fù)用混合以太網(wǎng)無源光網(wǎng)絡(luò)系統(tǒng)的上行波長帶寬分配算法，將問題映射到調(diào)度理論中的并行多處理器模型進行分析，考慮了實際網(wǎng)絡(luò)中傳播時延的多樣性對波分復(fù)用以太網(wǎng)無源光網(wǎng)絡(luò)帶寬分配的影響，提出了支持搶先機制的基于最短傳播時延/最長剩余處理時間混合調(diào)度策略的改進調(diào)度算法，提高了信道資源的利用率。文獻(xiàn)[10]提出了一種適用于多業(yè)務(wù)EPON的上行帶寬分配算法——周期和準(zhǔn)周期結(jié)合的動態(tài)帶寬分配算法，算法針對以太網(wǎng)業(yè)務(wù)和話音業(yè)務(wù)的特性，分別采取準(zhǔn)周期同步輪詢動態(tài)帶寬分配和周期固定帶寬分配機制，算法提高了系統(tǒng)帶寬利用率和帶寬分配的公平性。

通過以上關(guān)于EPON的動態(tài)帶寬算法的分析，本文提出了一種介于在線DBA和離線DBA算法之間的中間算法。算法基于交叉輪詢停止并對上行信道中的傳輸采用不同的周期定時控制，即根據(jù)上行信道負(fù)載情況工作在兩種模式：在低負(fù)載時，算法切換到在線DBA模式，類似于IPACT算法；在高負(fù)載時，切換到離線DBA模式，這樣既能消除離線DBA算法中存在的空閑時間，同時又能實現(xiàn)剩余帶寬公平地在全部高負(fù)載ONU之間的分配，從而最大限度地提高帶寬利用率。工作模式的切換分別根據(jù)傳入給OLT的上行帶寬請求。

1 本文提出的DBA算法

1.1 算法原理

如果在空閑周期開始時間與空閑周期長度Tidle(Tcomputation+RTT)同步之前，OLT能夠知道來自于全部ONU的帶寬需求，則在上行信道中就可以發(fā)送GATE消息而沒有任何空閑時間。為了發(fā)送GATE消息，如果超過一半的ONU在最后一個門控ONU之后報告它們的帶寬請求，則OLT計算出分配給一半ONU的帶寬數(shù)量，而不是輪詢表中的全部ONU；否則，OLT直接發(fā)送一個GATE消息給輪詢表中的下一個ONU，這時OLT處于在線DBA模式，直到報告的ONU數(shù)量超過總數(shù)的一半。當(dāng)報告的ONU數(shù)量超過總數(shù)的一半時，OLT開始啟動離線DBA模式，并在ONU之間公平分配帶寬；當(dāng)OLT不能收集到足夠的REPORT信息時，算法切換到在線DBA模式。如果ONU的時隙時間很短，則上行信道就是低負(fù)載的。因此在在線模式下，不必考慮公平分配，因為系統(tǒng)有一個周期時間小于所需的周期時間限制。

1.2 算法實現(xiàn)

從算法原理可見，算法需要前一個周期的請求和帶寬分配信息，對最后一個門控ONU和最后一個報告的ONU都必須即時監(jiān)測。由于算法對一個周期中的ONU服務(wù)順序不會改變，因此，最后一個門控ONU和最后一個報告的ONU可以簡單地通過輪詢表來監(jiān)測。在線和離線模式之間的切換根據(jù)GATE定時器失效時來自于最后一個門控ONU所報告的ONU數(shù)量。這個參數(shù)與周期時間、請求的窗口尺寸和ONU的RTT有關(guān)。如果有一半的ONU的窗口尺寸非常小，則它們的服務(wù)時間就可能小于RTT。這樣，當(dāng)GATE定時器失效時，如果分配的總窗口尺寸不大于數(shù)據(jù)包的RTT，則OLT就無法收集到足夠的REPORT來計算新的半周期。

現(xiàn)在需要考慮的是離線模式下的EBD。本文采用類似于離線DBA算法中的EBD，但OLT僅用K個REPORT消息而不是全部N個REPORT消息，對于(N-K)個節(jié)點，OLT還沒有接收到其帶寬請求。在EBD算法中，把ONU分為2組：已報告的和未報告的，算法需要全部ONU的請求來公平地分配帶寬。對于那些報告還沒有到達(dá)OLT的ONU，所需信息將基于其先前周期生成。

本文采用的剩余帶寬計算與離線DBA算法不同。我們把要研究的一個周期分為兩個半周期。在半周期中，可用剩余帶寬不能僅用當(dāng)前半個周期中的ONU的請求來測量。為了把剩余帶寬公平地分配給全部ONU，OLT也要考慮在前半個周期被服務(wù)的ONU的帶寬請求。來自于最后報告信息的K個ONU的剩余帶寬由式(3)計算，N-K個ONU的剩余帶寬，即來自于保存在輪詢表中先前報告信息的N-K個ONU的未使用的帶寬由式(4)計算

(3)

(4)

(5)

如果K個節(jié)點中每個節(jié)點的剩余帶寬數(shù)量小于K個節(jié)點總的剩余帶寬，算法就把K個ONU的總的剩余帶寬標(biāo)記為可用，反之，則意味著在前半個周期中的ONU是過載的。在這種情況下，算法將考慮PON中全部ONU的總需求，把可分配的剩余帶寬分配給當(dāng)前半個周期，以使前一個周期中的ONU在下一個周期有更多的剩余帶寬；此外，如果來自于前半個周期的N/2個ONU有未使用的剩余帶寬，則把這個未使用的剩余帶寬值也加到剩余帶寬中。這樣，算法就可以在每個半周期里確保公平分配。

(6)

2 算法性能評價

為了表明本文所提出的DBA算法的性能，考慮一個由16個ONU通過一個無源耦合器連接到一個OLT構(gòu)成的EPON接入網(wǎng)，耦合器和OLT之間、以及ONU和耦合器之間的距離大約為10 km。然后來比較3種算法在1Gbps和10Gbps的EPON上行信道兩種情況下單業(yè)務(wù)流量源和多業(yè)務(wù)流量時的字節(jié)丟失率和平均接入時延性能；單業(yè)務(wù)流量源采用恒定比特率(constant bit rates，CBR)的單一流量源，多業(yè)務(wù)流量源采用泊松帕累托突發(fā)過程(Poisson Pareto burst process，PPBP)的多業(yè)務(wù)流量源，即Pareto分布ON-OFF流量源；仿真在離散事件網(wǎng)絡(luò)仿真工具NS2中進行。

圖1為字節(jié)丟失率比較曲線。從圖1(a)可見，在單

圖1 3種算法的字節(jié)丟失率比較

業(yè)務(wù)流量源時，只有離線DBA算法在流量負(fù)荷超過0.9時存在字節(jié)丟失，而本文提出的DBA算法和IPACT算法均不存在字節(jié)丟失。這說明離線DBA算法相比于本文提出的DBA算法和IPACT算法有更差的帶寬利用率；從圖1(b)可見，在多業(yè)務(wù)流量源時，3種算法在1Gbps時均存在字節(jié)丟失，但在相同大小負(fù)荷情況下，本文提出的DBA算法的字節(jié)丟失率最低，而且出現(xiàn)在流量負(fù)荷超過0.8以后，而離線DBA算法在流量負(fù)荷為0.7以后就出現(xiàn)字節(jié)丟失，而從圖1(c)可見，3種算法在10Gbps時只有離線DBA算法和IPACT算法存在字節(jié)丟失，而本文提出的DBA算法無論流量負(fù)荷多大時都不存在字節(jié)丟失，說明本文提出的DBA算法在字節(jié)丟失率方面有最好的性能。

圖2為1 Gbps和10 Gbps時單業(yè)務(wù)流量源時的平均接入時延。可以看出，本文提出的DBA算法和IPACT算法要優(yōu)于離線DBA算法；而且對于3種算法，在低負(fù)荷時的平均接入時延都小于1 ms。當(dāng)負(fù)荷增加時，平均接入時延也增大，但本文提出的DBA算法仍能得到更好的平均接入時延性能。

圖2 單業(yè)務(wù)流量源時的平均接入時延比較

圖3為1 Gbps和10 Gbps時多業(yè)務(wù)流量時的平均接入時延。可以看到，本文提出的DBA算法和IPACT算法的平均接入時延在所有負(fù)荷值時都在1 ms以下，但本文提出的DBA算法仍然比IPACT和離線DBA算法能夠獲得更好的平均接入時延性能，這是因為如果其它ONU有較低帶寬請求而有剩余帶寬存在時，本文提出的DBA算法可以提供更多的帶寬給高負(fù)載的ONU。

圖3 多業(yè)務(wù)流量源時的平均接入時延比較

3 結(jié)束語

本文提出了一種介于離線DBA和在線DBA之間的動態(tài)帶寬分配算法。算法既能消除離線DBA算法中存在的空閑時間問題，同時又能實現(xiàn)離線DBA算法的公平EBD；算法在兩個半周期里分配剩余帶寬，并根據(jù)每個周期時間里的流量負(fù)荷切換到在線DBA模式；通過單業(yè)務(wù)流量源和多業(yè)務(wù)流量源在1Gbps和10Gbps上行信道帶寬速率下的仿真結(jié)果表明，本文所提出的DBA算法在字節(jié)丟失率和平均接入時延性能方面都有明顯提高。

[1]Mercian A,Mcgarry M P,Reisslein M.Impact of report message scheduling (RMS) in 1G/10G EPON and GPON[J].Optical Switching & Networking,2013,12(3):1-13.

[2]Rawshan F,Park Y.Architecture of multi-OLT PON systems and its bandwidth allocation algorithms[J].Photonic Network

Communications,2013,25(2):95-104.

[3]Radzi NAM,Din NM,Al-mansoori MH,et al.Analysis of delay performance on the intelligent fuzzy logic dynamic bandwidth allocation algorithm[J].Arabian Journal for Science and Engineering,2013,38(9):2367-2374.

[4]Li C,Guo W,Hu W,et al.Energy-efficient dynamic bandwidth allocation for EPON networks with sleep mode onus[J].Optical Switching & Networking,2014,15:121-133.

[5]Dixit A,Lannoo B,Colle D,et al.Energy efficient dynamic bandwidth allocation for Ethernet passive optical networks:Overview,challenges,and solutions[J].Optical Switching & Networking,2014,18(2):169-179.

[6]Hedayati AR,Fesharaki MN.Parnian:A two-stage neste-dauction for dynamic bandwidth allocation in Ethernet passive optical networks[J].Iranian Journal of Science & Technology Transaction B Engineering,2011,35:45-61.

[7]Lai chia-lin,Lin hui-tang,Chiang hung-hsin,et al.Design and analysis of a frame-based dynamic bandwidth allocation scheme for fiber-wireless broadband access networks[J].IEEE/OSA Journal of Optical Communications and Networking,2014,6(5):486-500.

[8]ZHAO Haijun,LI Min,CUI Mengtian,et al.A sort of dynamic resource allocation algorithm based on low cost protective framework in WDM-EPON[J].Journal of Yunnan University(Natural Sciences),2012,34(6):658-663(in Chinese).[趙海軍,李敏,崔夢天,等.WDM-EPON中基于低成本保護結(jié)構(gòu)的一種動態(tài)資源分配算法[J].云南大學(xué)學(xué)報(自然科學(xué)版),2012,34(6):658-663.]

[9]SHUAI Qianjun,ZHU Weijia,YAN Jinyao,et al.Heterogeneous propagation delay of dynamic bandwidth assignment for WDM/TDM EPON[J].Journal of Beijing University of Posts and Telecommunications,2013,36(5):90-95(in Chinese).[帥千鈞,朱維嘉,顏金堯,等.WDM/TDM EPON 傳播時延的動態(tài)帶寬分配算法[J].北京郵電大學(xué)學(xué)報,2013,36(5):90-95.]

[10]ZHANG Yang,CHEN Lei,HUANG Xiang,et al.Multi-services bandwidth assignment algorithm in EPON[J].Journal of Beijing University of Posts and Telecommunications,2013,27(5):90-93(in Chinese).[張洋,陳雷,黃翔,等.多業(yè)務(wù)EPON動態(tài)帶寬分配算法[J].北京郵電大學(xué)學(xué)報,2013,27(5):90-93.]