基于閉環反饋模式的彈性分組環多阻塞點公平算法

程方，黃世廣，郁志勇，張治中

（1. 重慶郵電大學 通信與信息工程學院，重慶 400065；2. 中興通訊股份有限公司，廣東 深圳 518057）

1 引言

彈性分組環（RPR, resilient packet ring）是一種新型的 MAC層協議[1]，其拓撲類似于傳統的FDDI[2]、令牌環[3]網絡，均采用了雙環結構。RPR集Ethernet的經濟性，SDH的高帶寬和高可靠性，IP技術的智能性于一體，受到了業界的廣泛關注。迄今，對 RPR組網技術的研究大致可以分為 2大類[4～9]：MAC協議性能分析和公平算法。公平算法是指當網絡發生擁塞時，控制環上的節點以便在擁塞鏈路上分配到公平的帶寬。在公平算法研究方面，業界廣泛采用的算法都是基于單阻塞點情況的，性能較好的有2種[10～12]：一種是循環排隊多址接入（CQMA,cyclic queuing multiple access）算法；另一種是空間重用協議（SRP, spacial reuse protocol）算法。盡管CQMA和SRP都可以實現帶寬的動態分配，但存在致命的缺點：算法存在振蕩而導致帶寬利用率不高。Gambiroza等人據此提出了環內分布式虛擬時間調度（DVSR, distributed virtual-time scheduling in rings）算法[9]，在單阻塞點情況下，具有非常好的性能。當RPR網絡規模較大，且業務動態變化時，已有的研究表明[10～12]：排頭阻塞（head-of-line blocking）對網絡性能的影響是非常嚴重的，在此情況下，即使阻塞點遠離某節點的目的節點，其業務都會受到較大的限制，即導致大量業務受到不必要的“懲罰”。因此，包括DVSR在內的單阻塞點算法不能保證帶寬的利用率。據此，研究了多阻塞點公平算法，目的在于解決單阻塞點公平性算法所存在的問題。

2 多阻塞點公平性評價準則

文獻[9]針對RPR單阻塞點情況提出了RIAS公平性評價準則，雖然保證了MAC協議公平性的要求，在提高網絡利用率方面取得較大突破，但是它并不適合于多阻塞點情況。本文借鑒了文獻[8]的思想，提出了一種適合于多阻塞點情況的評價準則。

不失一般性，設 RPR環網是有向的，包括 N個節點（0＜N≤255），每條鏈路的帶寬相等，均為C。一條流（flow）就是在一個確定的輸入輸出節點對之間的業務，記入節點i和出節點j之間的業務為flow(i, j）。令Rij代表節點i和j間的公平速率，則在鏈路n上已分配的速率Fn為

對于已分配的速率矩陣R={Rij}，有以下約束條件：

定義1 矩陣R滿足式(2)和式(3)的約束條件，就說R是可行且是唯一的。

定義2 設θi為源節點i的加權值，θij為流(i, j)的加權值，如果存在一個可行的速率矩陣R，使得下述條件成立，則稱鏈路n是穿過鏈路n的flow(a,b)與R相關的瓶頸段，記為Bn(a, b)。

1) Fn=Cn，1≤n≤N；

2) Rab/θab=max{Rij/θij}(1≤i j≤N，且 i＝a), 穿過鏈路n的流都由節點a發出；

3) IAn(a)/θa=max{IAn(i)/θi}(1 ≤ i≤ N)， 且Rab/θab=max{Rij/θij}(1≤i, j≤N，且 i＝a)，穿過鏈路n的流由多個源節點發出。

定義 3 設θi和θi′分別為源節點i與源節點 i′的加權值，θij和θi′j′分別為 flow(i, j)與 flow(i′, j′)的加權值，RBn(i,j)為穿過瓶頸段Bn(i, j)的流，一個可行的速率矩陣R如果滿足下述條件，則被認為是滿足多阻塞點公平性評價準則的。

在保證可行性且 flow(i, j)與 flow(i′, j′)經過的鏈路至少有一段相同的前提下，若要增加Rij，除非減小 Ri′j′ (1≤i,i′,j,j′≤N)，且

1) Rij/θiθij≥Ri′j′/θi′θi′j′, i=i′；

RBn(i,j)＞0, R[Bn(i,j),Bn′(i′,j′)]＞0, n ≠ n′；

3) IAn(i)/θi≥IAn(i′)/θi′, 除上述條件以外。

由以上定義，如果 flow(i, j)與 flow(i′, j′)的源節點相同，則前者的速率與相應的加權值之比不小于后者；如果網絡上存在不同的瓶頸段，2條流至少穿過一個相同的瓶頸段，則穿過瓶頸段較少的流的速率與相應的加權值之比不小于穿過較多瓶頸段的流的速率與相應的加權值之比；除上述2種情況外，穿過同樣的鏈路 n，且源節點為i的流的速率之和與節點 i的加權值之比不小于源節點為 i′的流的速率之和與節點i′的加權值之比。

為便于理解，對多阻塞點公平性評價準則舉例予以說明。如圖1所示，各條流的容量需求為無限大，多阻塞點公平性評價準則共享帶寬如下：R14=R15=R25=R45=0.333C，R12=0.667C。如果考慮flow(1,2)，當flow(1,5)沒有減少速率，增加flow(1,2)的速率是不可行的，違反了條件 1)。如果考慮flow(2,4)和 flow(2,5)，不減少 flow(1,5)或者 flow(4,5)的速率，而增加flow(2,4)和flow(2,5)的速率也是不可行的，違反了條件3)。對于條件2)，假設網絡上存在2個瓶頸段[S2,S3]和[S4,S5]，要增flow(4, 5)，只能減少flow(1,5)或者flow(2,5)的速率。

3 基于閉環反饋模式的多阻塞點公平算法

3.1 算法實現模塊

圖2 基于閉環反饋模式的多阻塞點公平性算法的實現

基于閉環反饋模式的多阻塞點公平算法的組成模塊如圖2所示，主要包括被控對象、反饋部分和控制部分3部分。反饋部分又由3個模塊組成：擁塞檢測模塊、計算單元模塊和調整單元模塊。算法的核心是確定反饋部分的公平速率值。

3.2 公平速率的確定

如圖3所示，在節點S0和Sn之間，節點S0最多有1條業務流經過節點Sn，節點S1最多有2條業務流經過節點Sn，節點Sn-1最多有n條業務流經過節點Sn。設Sn為阻塞節點，節點S0,S1,…,Sn的權值分別為 a0,a2,…,an。

圖3 算法模型

令m＝a0+a1+…+an。對阻塞節點Sn，計算得到每條聚合流實際分配到的帶寬分配矩陣為：

設bij為每條業務流的權值，。

則在理想狀態下，每一條業務流實際分配的帶寬為：

假設第i個節點預留的A類業務和B-CIR（承諾速率）類業務的帶寬為mi，其剩余的C類和B-EIR（額外速率）類的業務流的分配權值為wij，有：

令wij= albij，則每條業務流的本地公平帶寬Cw可以表示為：

對于某一阻塞點來說，它將下游阻塞節點所廣播的公平幀的內容和自己計算的本地公平速率進行比較，選擇其中較小者廣播給上游節點。假設Cwr為第r個阻塞節點所分配的公平速率值，某條業務流經過調整后所分配到的公平帶寬為 C′w，則本地的公平帶寬C′w為：

經過式(6)調整后，鏈路可能尚有剩余的帶寬，為了最大限度利用鏈路資源，實現空間重用，剩下的業務流所分配到的帶寬需要進一步調整，如圖 4所示。

圖4 多阻塞點網絡參考模型

對于圖 4，根據式(6)，需要調節的業務流為flow(2,7)和 flow(3,7)，那么 flow(1,4)和 flow(2,4)要共享剩余的帶寬不小于式(5)得到的帶寬。這里采用通用的做法，令所有節點和業務流的權值相等（即al=a，bij=b），則本地阻塞節點在分配了通過本地節點又通過下游阻塞節點的業務流后，剩余的業務流所分配到的帶寬 C′w為

其中，m為在某一阻塞節點經過式(6)調節的業務流總數；p為產生業務流且有業務流不需式(6)調節的節點總數；q為第l個節點所發出的，不需要式(6)調節的業務流總目。wk為業務流的分配權值，wk=ab。

式(5)～式(7)在理論上很好地解決了多阻塞點帶寬分配的問題，但在工程應用上，算法實現難度偏高?？蓪⑹?5)～ 式(7)進一步轉換成式(8)。

式(8)中，num為流經本地節點的業務流總數；LCw(k)0為本地節點的公平速率；RC+1為下一狀態的剩余帶寬；RC0為當前狀態下的剩余帶寬；FCw(k)0為本地節點向上游節點廣播的公平速率值；FCw(k)-1為下游阻塞節點向本地節點廣播的公平速率值。

式(8)由上而下計算，主要思想如下。

1) 由式(8a)估算第 k條 flow(i,j)的本地節點公平速率值。

2) 每處理一條業務流，num自減1。

3) 通過式(8c)，選擇 LCw(k)0和 FCw(k)-1中的較小者，封裝成多阻塞點公平幀，向上游節點廣播。

4) 通過式(8d)計算下一狀態的剩余帶寬RC+1。

對于單一阻塞節點來說，式(5)～式(7)組合而成的算法時間復雜度是O(sn2)，式(8)的算法時間復雜度是O(n2)。但對整個網絡來說，如果存在s個阻塞節點，由式(5)～式(7)組合而成的算法需要等待下游阻塞節點完成帶寬的公平分配后才能公平分配本地公平帶寬，因此時間復雜度是O(sn2)。式(8)則是一旦接收到某條數據流的公平幀就調整該條數據流，不需要等待下游阻塞節點完成帶寬的公平分配，所以式(8)的時間復雜度是 O(n2)。可見，在多阻塞狀態下，式(8)更優越。

3.3 算法的選擇

對于圖 4，不失一般性，設剩余帶寬為 1，每條流的分配權值為1，節點S3和節點S6為阻塞節點。

算法 1 由式(5)～式(7)確定多阻塞點的公平速率值。

根據式(5)，得到節點 S6估算的本地公平速率值為

節點S3估算的本地公平速率值為

當節點S6的公平幀反饋到節點S3后，經比較，有 R27＞R′27，R37＜R′37，依據式(6)，R′27和 R′37被調整為

為了最大限度利用剩余帶寬，根據式(7)，重新計算 R′14和 R′24為

所以系統最終構建的公平帶寬為

算法2 由式(8)確定多阻塞點的公平速率值。

由圖4可得，wk=ab=1，流經阻塞節點S6的業務流總數為5，由式(8)得到

當阻塞節點S6將flow(2,7)的公平速率值（0.2）反饋到阻塞節點S3后，S3由式(8a)得到公平速率估算值為

經比較，節點S3將0.2封裝到MCFF中，再發送給上游節點，即R′27最終的公平速率值R′27=0.2。此時，下一狀態的剩余帶寬為(1-0.2)=0.8，流經S3的業務流的總數目num變為3。

同理，當阻塞節點S6將flow(3,7)的公平速率值0.2反饋到阻塞節點S3后，S3通過計算，得到公平速率的估算值為

經比較得出 R′37最終的公平速率值 R′37=0.2。此時，剩余帶寬為(0.8-0.2)=0.6，流經S3的業務流的總數目num變為2。

由于flow(1,4)和flow(2,4)沒有流經阻塞節點S6，對S6不產生影響，所以它們的公平速率值由式(8a)求得：R′14= R′24=0.3。則最終的公平速率為

由前述可知：2種方案都實現了多阻塞點公平算法的帶寬分配，且實現了阻塞鏈路上剩余帶寬的最大分配（流經阻塞節點S3、S6的業務流的速率和為1）。然而，算法1需要對flow(2,7)和flow(3,7)調節完成后，才能得到flow(1,4)和flow(2,4)的最終公平速率值，而算法2無此要求，因此算法2的復雜度更低。不過，算法2犧牲了某些業務流的公平性。例如，比較式(13)和式(17)可知，flow(1,4)和flow(2,4)所期待的公平速率值為方案1中的速率，即0.316 7，但實際只分配了0.3；flow(2,7)所期待的公平速率為方案1中的0.167，實際上為0.2。

總體來看，2個算法的性能相差不大，但算法2的復雜度更低，有利于快速解決網絡中的阻塞狀態。

3.4 偽代碼

設k為時間周期T內到達阻塞節點的業務流數目，MCFF[i]為本地節點接收到下游阻塞節點反饋來的第i條業務流的公平速率；Rcapacity為鏈路的剩余帶寬；vi表示阻塞節點計算出業務流 i的公平速率，則算法的偽代碼可表示為：

4 仿真實驗

基于OPNET modeler(Version 10.5)[13]，設計了RPR的節點仿真模型和鏈路仿真模型，仿真節點通過鏈路連接構成RPR雙纖反向傳輸環仿真環境，如圖5所示。其中node_A表示數據源，node_1表示RPR節點，1～4起濾波作用。圖6為RPR節點仿真模型結構，其中的核心是MAC功能實現模塊；Sink模塊是本地數據下載模塊；src_Tx和src_Rx分別是數據源的發送和接收模塊；0_Rx_0、0_Tx_0、1_Rx_1、1_Tx_1分別是4個物理層的收發模塊。

圖5 RPR仿真平臺

圖6 RPR節點模型

本文選擇了典型的“停車場景[9,10]”對上述算法進行了仿真研究，輸出指標主要是算法的公平性、收斂時間和帶寬利用率。為便于衡量本文算法性能，對單阻塞點和多阻塞點2種情況均進行了仿真。仿真參數設置見表1。

表1 仿真參數

4.1 單阻塞點情況

如圖7所示，本文選擇了典型的上游并行停車場景來考察算法在單阻塞點情況下的性能。節點 1以300kbit/s速率向節點4發送數據，節點2～5分別在時刻0.05s、0.1s、0.15s、0.2s，均以300kbit/s速率發送數據到節點6。仿真結果如圖8所示。

圖7 上游并行停車場景

結果分析：如圖 8(b)～圖 8(d)，在 0.2s后，各流都能快速收斂，不存在大的振蕩，而且穩定的流速率接近于依據公平性評價準則計算所得到的值，R26≈R36≈R46≈R56≈250kbit/s。

圖8(a)表示節點S1在0.23s左右接收到阻塞節點反饋回來的公平幀后，速率收斂于500kbit/s。該值充分說明，本文提出的基于反饋模式的多阻塞點公平算法：①能實現帶寬的空間重用；②目的地在阻塞點上游的任何業務流都能最大限度的利用剩余帶寬，不會受到阻塞點的影響。

圖8 單阻塞點情況下的仿真結果

4.2 多阻塞點情況

如圖9所示的多阻塞點停車場景，節點1在0s向節點10發送數據，節點2、3、4在時刻0.05s、0.1s、0.15s向節點5發送數據，而節點6、7、8、9在時刻 0.2s、0.25s、0.3s、0.35s向節點 10發送數據，且它們的發送速率均為300kbit/s，仿真時間為2s。結果如圖10所示。

圖9 多阻塞點停車場景

圖10 場景3情況下的仿真結果

結果分析：從圖 10(a)可以看出，flow(1,10)先以初始速率300kbit/s發送數據，在0.18s左右收斂于公平速率250kbit/s，再經過0.23s后，收斂于節點S9計算得到的公平速率200kbit/s，該發送速率滿足不大于源節點和目的節點之間所有阻塞點的公平速率。另外，由 250kbit/s收斂到200kbit/s的時間大約為30ms（小于50ms）。因此，本文公平算法能較快收斂于最小公平值，不存在較大的震蕩。

圖10(b)～圖10(d)中的3條數據流在0.18s時刻收斂于節點 S4計算出的公平速率(250kbit/s)。在0.41s左右，由于節點S1發送的數據流進一步收斂于公平值200kbit/s，因此鏈路約有50kbit/s剩余帶寬，為了進一步利用剩余帶寬，上述3條流都進一步調整到公平性評價準則計算所得到的值266.7kbit/s，實現了帶寬的空間重用，同時并沒有引起較大震蕩。各條流的傳送速率的公平性評價指標均接近于1(FI2,5(t)≈FI3,5(t)≈FI4,5(t)≈1)。

由圖 10(e)～圖 10(h)可知，在 0.3s后，各條流先收斂到速率250kbit/s，接著在0.35s后，節點S9檢測到自身為阻塞節點，對圖9上的4條流進行進一步調整，最后各條流的穩定速率接近公平性評價準 則 計 算 所 得 到 的 值 （ R6,10≈R7,10≈R8,10≈R9,10≈200kbit/s）。由此，基于反饋模型的多阻塞點公平算法能100%地利用剩余帶寬，實現帶寬的公平分配。

5 算法的FPGA實現

如圖11所示，基于閉環反饋模式的多阻塞點公平算法由公平幀調度模塊、算法實現模塊以及數據幀調度模塊組成，算法實現模塊又由阻塞監測、數據統計、帶寬分配3部分組成。數據流進入彈性分組環的節點時，節點根據數據的操作請求，通過多阻塞點公平性算法實現模塊，完成MAC協議公平性算法，實現帶寬在各節點間快速、公平的分配。

圖11 多阻塞點公平算法FPGA實現

數據幀調度模塊和公平幀調度模塊：前者用來判斷轉發數據幀的起止位置，提取報頭信息，完成轉發數據幀和本地數據幀的調度，確定產生本地業務流量；后者根據轉發公平幀提取有效報頭信息，實現轉發公平幀和本地公平幀的調度功能。

阻塞檢測：以緩存器STQ的隊列長度為檢測對象，通過計算求出緩存深度平均值（avg），如果avg超過設定門限（阻塞門限），則判斷本地節點發生阻塞。

數據統計：本地節點到目的節點的跳數（desthops）、數據幀中源節點到本地節點的跳數（srchops）、緩存地址值、映射地址、公平幀中的源MAC地址到本地節點的跳數、流經本地節點，又流經阻塞節點的業務流總數目、本地節點非阻塞時，流經本地節點，卻沒流經阻塞節點的業務流總數目。

帶寬分配：完成本地節點公平速率的計算，以及根據接收到的公平速率進行比較，將較小值傳遞給上游節點。

參考圖9的仿真模型，假設鏈路帶寬為1 000，S4既是本地節點又是阻塞節點，S8、S9是下游阻塞節點。那么 S4在阻塞狀態下收到節點 S8、S9廣播的公平幀。根據式(8)可知，S9計算的公平速率為200，反饋到節點S4后，flow(2,5)、flow(3,5)、flow(4,5)的最大允許發送速率被調整到266左右。為了簡化，減少仿真圖中顯示數據幀或公平幀的長度，并不失一般性，本文把流經數據幀調度模塊和公平幀調度模塊中的業務流的幀結構中的源MAC地址和目的MAC地址的寬度設置為8bit（有效地代表了環網中255個節點）。如一個簡單的數據幀“7E0872080E7E”（16進制表示，不包含數據幀結構中“協議類型/長度”以下的內容），“7E”表示幀開始或結束標志位，TTL為“08”、目的MAC地址為“08”、源MAC地址為“0E”。模擬公平幀類似，但不包含目的MAC地址，且比模擬數據幀多了 16bit公平值。設flow(6,10)、flow(7,10)、flow(8,10)、flow(9,10)的模擬數據幀為“7E077209017E”、“7E017205027E”、“7E017205037E”、“7E017205047E”；收到阻塞節點S9反饋的模擬公平幀為“7E0B720900C87E”。

圖12 多阻塞點停車場景時序仿真

由圖12可見，節點S4產生了一個模擬公平幀“7E0F7204010A7E00”（端口 outputFF的輸出），公平幀控制值的內容是“010A”（“010A”的十進制表示為“266”）。可見，在本地節點既是阻塞節點又接收到公平幀情況下，本文設計的算法在FPGA實現中滿足了多阻塞點公平算法的要求。

6 結束語

本文對RPR多阻塞點公平算法進行了研究，提出了一種多阻塞點公平性評價準則，在此基礎上給出了一種多阻塞點公平性算法，并對算法的公平性和鏈路利用率進行了仿真分析和FPGA實現。結果表明：本文算法能有效地控制鏈路速率的變化，避免排頭阻塞的影響，在典型的停車場景中能夠較快地收斂到公平值。與單阻塞點算法相比，由于本文算法只對阻塞域之間的鏈路進行調整，因而大大提高了資源利用率。

[1] DAVIK F, YILMAZ M, GJESSING S, UZUN N. IEEE 802.17 resilient packet ring tutoria[J]. IEEE Communications Magazine, 2004,42(3):112-118.

[2] ROSS F E. Overview of FDDI: The fiber distributed data interface[J]. IEEE Journal on Selected Areas in Communication, 1989, 7(7):1043- 1051.

[3] SPADARO S, SOLE P J, CAREGLIO D, et al. Positioning of the RPR standard in contemporary operator environments[J]. IEEE Network,2004, 18(2):35-40.

[4] 王嵌, 吳重慶, 魏斌. 光彈性分組環節點光分組的組裝及時延分析[J]. 光學學報, 2009, 29(4):897-901.WANG Q, WU C Q, WEI B. Assembly and delay analysis of optical resilient packet ring on packets encapsulation[J]. Acta Optica Sinica,2009, 29(4):897-901.

[5] SHOKRANI A, TALIM J L. Modeling and analysis of fair rate calculation in resilient packet ring conservative mode[A]. IEEE International Conference on Communications (IEEE ICC 2006)[C]. Istanbul,Turkey, 2006. 203-210.

[6] TANG H, LAMBADARIS I, MEHRVAR H, Performance evaluation of VSQ: a fair MAC scheme for packet ring networks[J]. IEEE Journal on Selected Areas in Communication, 2006(6):107-114.

[7] YILMAZ M, ANSARI N. Weighted fairness in resilient packet rings[A]. IEEE International Conference on Communications (IEEE ICC 2007)[C]. Glasgow, Scotland, 2007.2192-2197.

[8] ZHOU X B, LIU L, ZENG L G. A novel fairness algorithm for resilient packet ring based on feedback theory[A]. The 9th International Conference on Advanced Communication Technology[C]. Phoenix Park, Republic of Korea, 2007.1407-1411.

[9] GAMBIROZA V, YUAN PING, LAURA B E. Design, analysis, and implementation of DVSR: a fair high-performance protocol for packet ring[J]. IEEE/ACM Transaction on Networking, 2004,12(1):85-102.

[10] 陶瀅. 彈性分組環若干關鍵問題的研究[D]. 北京：北方交通大學,2003.TAO Y. Studies on Some key Questions of Resilient Packet Ring[D].Beijing: Jiao Tong University, 2003.

[11] SHOKRANIT A, LAMBADARIS I, VINIOTIS Y. Configuring conservative mode fairness algorithm in resilient packet rings[A]. IEEE International Conference on Communications (IEEE ICC 2008)[C].Beijing: China, 2008.139-145.

[12] ZHOU S Y, WEI X. A fairness algorithm based on flow for register insertion ring[A]. Third International Conference on Communications and Networking[C]. Beijing, China, 2008.810-813.

[13] 張銘, 竇赫蕾, 常春藤. OPNET Modeler與網絡仿真[M]. 北京: 人民郵電出版社, 2007.ZHANG M, DOU H L, CHANG C T. OPNET Modeler and Network Simulation[M]. Beijing: Posts & Telecom Press, 2007.