張清玲，何榮希（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧 大連116026）

?

中文核心期刊

長距離無源光網(wǎng)絡(luò)中自適應(yīng)多線程輪詢算法

張清玲，何榮希
（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧 大連116026）

摘要：針對長距離無源光網(wǎng)絡(luò)覆蓋范圍廣、傳播時延大的特點，提出一種基于上行數(shù)據(jù)包時延的自適應(yīng)多線程輪詢算法（A M TP）。該算法中O LT依據(jù)上行數(shù)據(jù)包時延狀況動態(tài)調(diào)整輪詢周期內(nèi)對O N U的帶寬授權(quán)次數(shù)。仿真結(jié)果表明：與已有算法相比，A M TP算法具有較高的信道利用率、較低的上行數(shù)據(jù)包平均時延和時延抖動值。

關(guān)鍵詞：長距離無源光網(wǎng)絡(luò)；動態(tài)帶寬分配；自適應(yīng)；多線程輪詢

0　引言

長距離無源光網(wǎng)絡(luò)（LR-PON）將OLT與ONU之間距離擴展到100km甚至更遠，導(dǎo)致往返時延高達1ms［1］，因此，在設(shè)計動態(tài)帶寬分配算法（DBA）時應(yīng)充分考慮傳播時延的影響，盡可能減少信道空閑時間，以提高信道利用率［1，2］。

多線程輪詢算法（MTP）［3，4］是針對LR-PON設(shè)計的經(jīng)典DBA算法，其通過在OLT與ONU之間建立多個平行進程進行通信，可以提高信道利用率。固定線程數(shù)目的MTP無法很好適應(yīng)網(wǎng)絡(luò)負載變化，文獻［5］提出一種根據(jù)網(wǎng)絡(luò)負載動態(tài)改變輪詢周期內(nèi)對ONU授權(quán)次數(shù)的AMGAV算法，可以提高信道利用率。但是，AMGAV未考慮OLT收到Report消息至ONU收到Gate消息這段時間內(nèi)可能有數(shù)據(jù)包到達ONU的情況。為此，文獻［6］引入帶寬預(yù)測機制，提出S-AMGAV算法，有利于盡快上傳新到達ONU的數(shù)據(jù)包。但是該算法一個周期內(nèi)ONU授權(quán)次數(shù)高達十幾次，大大增加了控制開銷。上述算法依據(jù)網(wǎng)絡(luò)負載來調(diào)整輪詢周期內(nèi)使用線程數(shù)目，但是，網(wǎng)絡(luò)負載僅反映一段時間內(nèi)用戶產(chǎn)生數(shù)據(jù)的平均情況，未能很好反映網(wǎng)絡(luò)實時狀況?？紤]到網(wǎng)絡(luò)數(shù)據(jù)流量的突發(fā)性，即使在高負載情況下也可能會有一些ONU處于輕負載狀態(tài)。同樣地，在低負載條件下也可能存在重負載ONU。上行數(shù)據(jù)包時延能較好反映網(wǎng)絡(luò)中產(chǎn)生以及緩存數(shù)據(jù)包的情況?；诖?，本文在繼承上述算法優(yōu)點基礎(chǔ)上，進一步考慮突發(fā)業(yè)務(wù)特點以及網(wǎng)絡(luò)負載分布不均和動態(tài)變化等特征，提出一種基于數(shù)據(jù)包時延的自適應(yīng)多線程輪詢算法（AMTP）。該算法在OLT端依據(jù)實時數(shù)據(jù)包時延動態(tài)改變輪詢周期內(nèi)線程數(shù)目，既能避免使用過多線程，減少控制開銷，又能減少上行信道空閑時間，提高信道利用率。

1　算法描述

由于網(wǎng)絡(luò)數(shù)據(jù)流量的突發(fā)性，網(wǎng)絡(luò)中各個時刻產(chǎn)生數(shù)據(jù)包的數(shù)量是變化的。數(shù)據(jù)包產(chǎn)生速率越大，ONU緩存數(shù)據(jù)越多，上行數(shù)據(jù)包平均時延越大。為了改善時延性能，相應(yīng)地需要增加線程數(shù)目。因此，可以根據(jù)上行數(shù)據(jù)包時延情況來動態(tài)改變輪詢周期內(nèi)為各個ONU進行帶寬授權(quán)的次數(shù)。在AMTP算法中，OLT依據(jù)ONU上行數(shù)據(jù)包的平均時延值來動態(tài)調(diào)整每個輪詢周期的線程數(shù)目，使用盡量少的線程來保證上行數(shù)據(jù)包平均時延維持在一個較低水平。在具體描述所提算法前，引入以下符號：N：ONU的個數(shù)；BWi，j：ONUi在線程j的帶寬請求；B0：各個ONU的最小保證帶寬；BWj：線程j所有ONU的帶寬請求之和；Thnum：輪詢過程中所使用的線程數(shù)目；Bscarity，j：線程j所有輕負載ONU節(jié)省帶寬的總和；BW0：為各個ONU分配的初始化帶寬；Bexces，j：線程j所有重負載ONU不足帶寬的總和；R：上下行鏈路的傳輸速率；TG，j：OLT為線程j所有ONU進行帶寬授權(quán)的時刻；Tth：線程融合閾值門限；TR，j：OLT收到線程j所有ONU的Report消息時刻；Gi，j：OLT在線程j為ONUi分配的帶寬；Tg：連續(xù)兩個ONU上行數(shù)據(jù)傳輸保護時間間隔。

算法具體描述如下：

算法首先為各個ONU的各個線程進行初始化帶寬分配，分配的帶寬為：

系統(tǒng)進入正常通信狀態(tài)后，為防止重負載ONU獨占上行信道，設(shè)置各個ONU的最大保證帶寬B0= 15500字節(jié)［7］。將帶寬請求小于等于、大于B0的ONU分別稱為輕、重負載ONU，并將輕負載ONU節(jié)省下來的帶寬按比例分配給重負載ONU［8］。線程j授權(quán)ONUi的帶寬為：

與MTP算法［4］一樣，AMTP算法可能也會出現(xiàn)線程融合問題［9］。為了克服線程融合問題，可以減少當(dāng)前線程的部分帶寬，然后將這部分帶寬分配給下一線程中的ONU。即當(dāng)BWjBWj+1≥Tth時，可將線程j中部分帶寬分配給線程j+1的ONU。同時，若OLT對于線程j的帶寬授權(quán)消息沒有發(fā)送出去而線程j+1的帶寬請求消息已到達OLT（即TG，j≥TR，j+1），并且BWj+1與BWj之和小于B0時，則將線程j+1的帶寬請求在線程j進行帶寬授權(quán)。這樣在線程j+1報告的緩存數(shù)據(jù)在線程j就上傳，可以降低這部分緩存數(shù)據(jù)的上行時延，全網(wǎng)數(shù)據(jù)包平均時延也會在一定程度上降低［9］。

國際電信聯(lián)盟規(guī)定在100km范圍內(nèi)的接入網(wǎng)中，要使語音信息無失真地傳給用戶，需要保證其傳輸時延不超過1.5ms［7］。由文獻［9］可知，即使是在高負載條件下，如果線程間采用合適的調(diào)度算法和適當(dāng)?shù)木€程數(shù)目，仍然能保證網(wǎng)絡(luò)中上行數(shù)據(jù)包時延低于1.5ms。在所提出的AMTP算法中，為了減少算法的復(fù)雜度，同時使用盡量少的控制信息以提高上行信道傳輸效率，算法規(guī)定每個輪詢周期中最多使用3個線程。

在AMTP算法中，如果在一個最小保證帶寬的時間范圍內(nèi)，收到的上行數(shù)據(jù)包時延都高于1.5ms，此時如果當(dāng)前網(wǎng)絡(luò)負載低于0.8且線程數(shù)目低于3，則可以繼續(xù)增加輪詢周期使用的線程數(shù)目（加1）；如果網(wǎng)絡(luò)負載高于0.8，而且線程數(shù)目大于1，則應(yīng)減少輪詢周期使用的線程數(shù)目（減1）。另外，如果在一個最小保證帶寬時間范圍內(nèi)，收到的所有上行數(shù)據(jù)包時延都低于1.5ms，同時所使用線程數(shù)目大于1，此時應(yīng)減少使用的線程數(shù)目（減1）以減少控制開銷，進一步提高上行信道利用率。

AMTP算法動態(tài)改變線程數(shù)目后，在下一輪詢周期將按照更新后的線程數(shù)目為各個ONU進行帶寬授權(quán)，并重復(fù)執(zhí)行上述步驟。

2　計算機仿真及數(shù)據(jù)分析

本節(jié)利用OPNET軟件搭建LR-PON仿真平臺，對提出的AMTP算法進行仿真分析，并與MTP［4］、AMGAV［5］和S-AMGAV［6］三種算法進行比較。仿真網(wǎng)絡(luò)包括1個OLT、1個光分路器和16個ONU，ONU到OLT的距離為100km左右，AMTP的初始線程數(shù)為1，各線程初始化帶寬授權(quán)時間為0.3ms［4］，MTP算法的線程數(shù)固定為2，這是文獻［4］綜合考慮計算復(fù)雜度和數(shù)據(jù)包時延情況給出的最佳線程數(shù)。網(wǎng)絡(luò)用戶產(chǎn)生的上行數(shù)據(jù)業(yè)務(wù)服從H參數(shù)為 0.8的 Pareto分布，幀長為560bits，R=1Gb/s，Tg=5μs，Tth=5。仿真性能指標包括輪詢周期內(nèi)平均使用線程數(shù)、上行數(shù)據(jù)包平均時延、上行信道利用率和上行數(shù)據(jù)包時延抖動。

圖1　輪詢周期內(nèi)平均使用線程數(shù)

圖1給出了不同算法在一個輪詢周期內(nèi)平均使用的線程數(shù)隨相對網(wǎng)絡(luò)負載（網(wǎng)絡(luò)中每秒產(chǎn)生數(shù)據(jù)的總比特數(shù)與R的比值［7］）變化的情況，可以看出：S-AMGAV算法的平均線程數(shù)隨網(wǎng)絡(luò)負載的增加逐漸減少，AMGAV和AMTP算法變化不大。AMGAV算法的平均線程數(shù)維持在7左右，而AMTP算法較小，平均線程數(shù)在1～2之間。這是因為：在S-AMGAV算法中，單位周期的線程數(shù)與網(wǎng)絡(luò)中ONU的數(shù)目成反比，并且隨著網(wǎng)絡(luò)負載的增加逐漸減少。當(dāng)網(wǎng)絡(luò)中只有16個ONU且負載較低時，線程數(shù)接近20個。在AMGAV算法中，單位周期內(nèi)OLT為各個ONU的授權(quán)次數(shù)（線程數(shù)）與各個ONU的帶寬請求之和成反比，且不能超過8。因為授權(quán)次數(shù)為8的時間較多，所以AMGAV算法中不同負載下對各個ONU進行帶寬授權(quán)的次數(shù)變化不大。在AMTP算法中，最大輪詢線程數(shù)目設(shè)定為3，并且依據(jù)上行數(shù)據(jù)包時延動態(tài)調(diào)整，網(wǎng)絡(luò)中線程數(shù)目為1和2的時間相對較多，平均授權(quán)次數(shù)在1～2之間，授權(quán)次數(shù)最少。

圖2　不同算法上行數(shù)據(jù)包平均時延比較

圖2比較了不同相對網(wǎng)絡(luò)負載下上行數(shù)據(jù)包平均時延的變化情況，可以看出：無論網(wǎng)絡(luò)負載如何變化，AMTP算法的上行數(shù)據(jù)包平均時延都低于另外三種算法。隨著網(wǎng)絡(luò)負載的增加，4種算法的上行數(shù)據(jù)包平均時延都逐漸增大，而AMTP算法增加較為緩慢。當(dāng)網(wǎng)絡(luò)負載低于0.5時，MTP算法的上行數(shù)據(jù)包平均時延高于S-AMGAV和AMGAV算法；當(dāng)網(wǎng)絡(luò)負載高于0.5時，MTP算法的上行數(shù)據(jù)包時延低于AMGAV算法，但是與S-AMGAV算法比較接近。這是因為AMTP算法采用動態(tài)輪詢周期時間，輪詢周期隨著網(wǎng)絡(luò)負載的變化動態(tài)調(diào)整，使用的線程數(shù)目也隨著上行數(shù)據(jù)包平均時延的變化而動態(tài)變化，可以保證上行數(shù)據(jù)包平均時延維持在低于1.5ms內(nèi)。在網(wǎng)絡(luò)負載較低時，SAMGAV和AMGAV算法能夠給各個ONU進行更多次授權(quán)，各個ONU也有更多機會上傳數(shù)據(jù)，所以時延性能比MTP算法好；當(dāng)網(wǎng)絡(luò)負載相對較高時，AMGAV算法給各個ONU的授權(quán)次數(shù)仍然多于MTP。由于此時ONU緩存的上行數(shù)據(jù)較多，而授權(quán)次數(shù)多意味著控制開銷大，相應(yīng)地用于傳輸數(shù)據(jù)的帶寬較少，可能導(dǎo)致較多數(shù)據(jù)包不能及時上傳，因而AMGAV算法的時延大于輪詢次數(shù)較少的MTP算法。

圖3　不同算法的上行信道利用率比較

圖3比較了不同相對網(wǎng)絡(luò)負載下4種算法上行信道利用率的變化情況，可以看出：不論是高負載還是低負載條件下，AMTP算法的信道利用率都明顯高于其它算法。當(dāng)網(wǎng)絡(luò)負載低于0.5時，MTP算法的信道利用率稍低于S-AMGAV以及AMGAV算法。當(dāng)網(wǎng)絡(luò)負載高于0.5時，結(jié)果剛好相反。這是因為：AMTP算法解決了多線程輪詢算法存在的線程融合和重復(fù)授權(quán)問題，同時能夠根據(jù)網(wǎng)絡(luò)中上行數(shù)據(jù)包時延情況動態(tài)改變所用線程數(shù)目，可以提高上行帶寬利用率。MTP算法采用固定的輪詢次數(shù)，不能根據(jù)網(wǎng)絡(luò)中數(shù)據(jù)包時延的情況做出調(diào)整，尤其是在低負載條件下，各個ONU進行數(shù)據(jù)上傳的機會固定不變，而各個ONU中緩存的數(shù)據(jù)包數(shù)量以及數(shù)據(jù)包到達ONU的時間不確定，導(dǎo)致ONU內(nèi)緩存的數(shù)據(jù)包可能會錯過僅有的2次上傳機會，上行信道在一段時間內(nèi)將處于空閑狀態(tài)，信道利用率降低。雖然當(dāng)網(wǎng)絡(luò)負載較大時，MTP算法的信道利用率越來越接近AMTP，但是仍然低于AMTP算法。這是因為：當(dāng)網(wǎng)絡(luò)負載較大時，網(wǎng)絡(luò)中平均每個時刻產(chǎn)生的數(shù)據(jù)包較多，需要傳輸?shù)纳闲袛?shù)據(jù)包也比較多，上行信道可能一直處于傳輸數(shù)據(jù)的狀態(tài)，利用率比較高。雖然如此，MTP算法線程數(shù)固定為2，而AMTP算法在負載較高時，所使用線程數(shù)目為1的時間較多，控制消息相對較少，所以信道利用率高于MTP算法。當(dāng)網(wǎng)絡(luò)負載較低時，MTP算法的信道利用率低于S-AMGAV和AMGAV算法，這是因為在SAMGAV和AMGAV算法中，OLT可以對各個ONU進行更多次授權(quán)，各個ONU也有更多的機會進行數(shù)據(jù)上傳。當(dāng)網(wǎng)絡(luò)負載增大時，由于MTP算法采用線程數(shù)固定為2，而在S-AMGAV和AMGAV算法中，一個周期內(nèi)OLT對ONU進行帶寬授權(quán)的次數(shù)仍然較多，控制消息的增加會占用更多的信道帶寬，造成信道利用率低于MTP算法。

圖4　不同算法的上行數(shù)據(jù)包時延抖動比較

圖4比較了不同算法的上行數(shù)據(jù)包時延抖動隨相對網(wǎng)絡(luò)負載變化的情況。上行數(shù)據(jù)包時延抖動反映了網(wǎng)絡(luò)中各個ONU緩存數(shù)據(jù)包的時延變化情況。從圖4可以看出：無論網(wǎng)絡(luò)負載如何變化，AMTP算法的包時延抖動都低于MTP算法。當(dāng)網(wǎng)絡(luò)負載低于0.5時，AMTP算法的包時延抖動大于S-AMGAV和AMGAV算法；當(dāng)網(wǎng)絡(luò)負載高于0.5時，AMTP算法的包時延抖動小于S-AMGAV和AMGAV算法。這是因為：在網(wǎng)絡(luò)負載較低時，ONU中緩存的數(shù)據(jù)包較少，而S-AMGAV 和AMGAV算法使用的線程數(shù)目相對較多，數(shù)據(jù)包在各個線程內(nèi)都能被及時發(fā)送出去，由此數(shù)據(jù)包時延差別較小。在網(wǎng)絡(luò)負載較高時，AMTP中可以根據(jù)時延值的變化調(diào)整使用的線程數(shù)目，使所有數(shù)據(jù)包平均時延都維持在較低的范圍內(nèi)。MTP使用固定數(shù)目的線程，不能根據(jù)網(wǎng)絡(luò)條件的變化做出調(diào)整，網(wǎng)絡(luò)負載大時，ONU中可能緩存了幾個周期的數(shù)據(jù)，也可能存在剛到達的數(shù)據(jù)，因此，時延抖動較大。S-AMGAV算法隨著網(wǎng)絡(luò)負載的增加，單位周期內(nèi)對各個ONU授權(quán)的次數(shù)逐漸減少，在網(wǎng)絡(luò)負載較大時接近AMTP算法對各個ONU授權(quán)的次數(shù)，因此，包時延值大小差不多，時延抖動也比較接近。但是在AMGAV算法中，當(dāng)網(wǎng)絡(luò)負載較高時，單位周期內(nèi)OLT對各個ONU進行帶寬授權(quán)的次數(shù)仍然較多，這樣會因為控制消息的增多而使傳輸數(shù)據(jù)的帶寬減少，可能導(dǎo)致ONU內(nèi)緩存數(shù)據(jù)包增多，上行數(shù)據(jù)包平均時延差異大，包時延抖動最大。

3　結(jié)束語

MTP算法使用固定的線程數(shù)，無法適應(yīng)網(wǎng)絡(luò)負載的動態(tài)變化，AMGAV和S-AMGAV算法雖然可以依據(jù)網(wǎng)絡(luò)負載動態(tài)調(diào)整輪詢周期內(nèi)的線程數(shù)，但是一個周期內(nèi)對各個ONU進行帶寬授權(quán)的次數(shù)較多，增加的控制消息和線程切換過程都會延緩上行數(shù)據(jù)的傳輸，同時也增加了計算的復(fù)雜度。本文提出的AMTP算法根據(jù)網(wǎng)絡(luò)中數(shù)據(jù)包時延的變化情況，自適應(yīng)調(diào)整輪詢周期的線程數(shù)目，是一種更靈活和適應(yīng)性更強的DBA算法。仿真結(jié)果表明：與已有算法相比，AMTP算法盡可能減少每個輪詢周期內(nèi)使用的線程數(shù)目，能夠提高上行信道利用率，降低上行數(shù)據(jù)包平均時延和數(shù)據(jù)包時延抖動。

參考文獻：

［1］SONG H，KIM B-W，MUKHERJEE B.Long-Reach Optical Access Networks：A Survey of Research Challenges，Demonstrations，and Bandwidth Assignment Mechanisms［J］.IEEE Commun.Surv.Tut.，2010，12（1）：112-123.

［2］KANTARCI B，MOUFTAH H T.Bandwidth Distribution Solutions for Performance Enhancement in Long-Reach Passive Optical Networks［J］，IEEE Commun.Surv.Tut.，2012，14（3）：714-733.

［3］HELMY A，F(xiàn)ATHALLAH H，MOUFTAH H.Interleaved Polling Versus Multi-Thread Polling for Bandwidth Allocation in Long-Reach PONs ［J］.IEEE/OSA J Opt.Commun.Netw.，2012，4（3）：210-218.

［4］SONG H，KIM B-W，MUKHERJEE B.Multi-Thread Polling：A Dynamic Bandwidth Distribution Scheme in Long-Reach PON［J］.IEEE JSAC，2009，27（2）：134-142.

［5］DIXIT A，DAS G，LANNOO B，et al.Adaptive multi-gate polling with void filling for long-reach passive optical networks［C］.Intern.Conf.on Transparent Optical Netw.（ICTON），Stockholm，IEEE Press，2011：1-4.

［6］DIXIT A，LANNOO B，COLLE D，et al.Synergized-adaptive multi-gate pollingwithvoidfilling：Overcomingperformancedegradationin LR-PONs［J］.IEEE/OSA J Opt.Commun.Netw.，2015，7（9）：837-850.

［7］KRAMER G，MUKHERJEE B，PESAVENTO G.Interleaved Polling with Adaptive Cycle Time（IPACT）：A Dynamic Bandwidth Distribution Scheme in an Optical Access Network［J］.Photonic.Netw.Commun.，2002，4（1）：89-107.

［8］朱婉瑩，何榮希，楊帥.EPON中節(jié)能動態(tài)帶寬分配算法［J］.光通信技術(shù)，2014，38（11）：35-38.

［9］AHMED J，CHEN J，WOSINSKA L，et al.Efficient inter-thread scheduling scheme for long-reach passive optical networks［J］.IEEE Commun.Mag.2013，51（2）：35-43.

中圖分類號：TN929.18

文獻標識碼：A

文章編號：1002-5561（2016）06-0021-04

DOI：10.13921/j.cnki.issn1002-5561.2016.06.006

收稿日期：2016-01-22。

基金項目：國家自然科學(xué)基金資助項目（61371091）資助。

作者簡介：張清玲（1990-），女，碩士生，主要研究方向為光網(wǎng)絡(luò)。

Adaptive multi-thread polling algorithm for long distance passive optical networks

ZHANG Qing-ling，HE Rong-xi
（College of Information Science and Technology，Dalian Maritime University，Dalian Liaoning 116026，China）

Abstract：In this paper，a packet delay based adaptive multi-thread polling algorithm （AMTP）has been proposed for a long reach passive optical network（LR-PON）which has large coverage and considerable propagation delay.AMTP can adjust the number of polling thread dynamically according to the average delay of the received packets.Simulation results show that the proposed algorithm can achieve higher channel utilization and lower packet delay，as well as decreased packet delay jitter compared with the existing algorithms.

Key words：LR-PON，dynamic bandwidth allocation（DBA），adaptive，multi-thread polling