公平算法

公平控制原理

公平算法的目標就是結合速率控制機制對本節點接入的所有C業務和B2EIR業務(以後統稱為低優先級業務)採用基於反饋控制機制的公平控制算法,實現帶寬的動態公平分配,使得所有節點按照本節點的權重值公平的佔用帶寬,同時使帶寬利用率最大化,避免了某些節點無限制接入數據而使得下游節點處於飢餓狀態。

公平控制的原理就是當節點監測出輸出鏈路擁塞時,就啓動公平算法機制,計算本地的公平速率,然後通過反饋機制向上遊發送公平速率信息,使得環上其他節點可隨時瞭解擁塞節點處的流量情況,並根據公平信息調整自己的接入速率,當下遊擁塞消除後,就逐漸提高自己的發送速率,在經過一段收斂時間之後,環上所有節點將會基於各自的權重值所分得的速率進行發送,對於等權值的RPR環,則應該以統一的速率發送,從而實現了帶寬分配的公平性

SRP算法

在RPR中採用了SRP作為帶寬分配算法。其基本原理是在算法中設置兩個變量FORWARD_RATE和MY_RATE,二者分別表示轉發業務的發送速率和本地站點業務的發送速率。當FORWARD_RATE+MY_RATE＞LOW_THRESHOLD時,我們就稱節點n是擁塞的,這裏LOW_THRESHOLD是一個低於鏈路能力的固定值。當節點n發生擁塞,它就發送一個控制信息給它的上游節點,這個控制信息中包含着它自己站點業務的發送速率MY_RATE[n]。當上遊節點i接收到包含MY_RATE[n]值的擁塞控制信息後,它將降低自己的速率控制器值,我們稱之為ALLOWED_RATE。如果從節點n接收到擁塞信息的上游節點n-1也是擁塞的,那麼它將把節點最近計算的ALLOWED_RATE值和它自己的測量值MY_RATE[n-1]相比較,取較小值送給上游節點。這樣,站點的業務速率將不再超過這一流量所經過的下游任一節點所廣播的MY_RATE值。如果節點n-1沒有擁塞,它將把MY_RATE[n-1]設置為全空的值,以指示沒有發生擁塞。接收到全空值的節點將間歇性地增加它們自己的ALLOWED_RATE值。值得注意的是,節點n-1雖然處於擁塞狀態,但MY_RATE[n-1]＞FORWARD_RATE[n-1]時,節點n-1同樣將MY_RATE[n-1]設置為全空值,這是因為,這種情況表示,節點的擁塞狀況是由節點n-1發送的業務導致的,而不是由上游節點所發送的業務導致的。

這個算法的基本思想是如果所有的節點以接收到的MY_RATE的最小值來分享瓶頸鍊路,那麼流量的速率將會相等,公平性也由此而來。在沒有擁塞的情況下,流量將間歇性地增加它們自己的ALLOWED_RATE,以保證獲得最大化的帶寬利用率。總的説來SRP具有較好的有效性、簡單性和可拓展性,但也存在一些問題。①算法必須設定恰當的算法參數,如控制信息的發送間隔、轉發緩存器的容量和低優先級門限的大小等。這些參數的設置將會對網絡中處於不同位置的節點,及不同優先級的業務產生影響。②由於SRP只有一個單獨的速率控制器,這將會產生如下的一些問題：如隊頭阻塞問題和不平衡業務情形下的帶寬分配不公平問題等。

DVSR算法

VioletaGambiroza等人基於RIAS公平模型設計了一種新的RPR帶寬分配算法,稱為DVSR(DistributedVirtual-timeSchedulinginRings)。RRIAS公平模型由兩個關鍵部分組成,第一部分定義了IA流在鏈路上的公平性需求流量粒度,第二部分確保在第一部分限制下的最大化空間複用,即IA流可以使用那些因各種原因其他流暫時無法使用的帶寬。RIAS力圖實現最大化的空間再利用和更大的網絡吞吐量。?

與RPR標準公平算法只在擁塞節點計算全局統一公平速率不同,DVSR為針對不同終節點的每個流量都設置一個速率控制器,所有站點業務的發送速率首先要受速率控制器所控制。在DVSR中最主要的問題就是如何確定每個流量速率控制器的值。這可以通過在RPR節點上的業務監視器測量,並由公平帶寬分配器計算出的結果來確定。設為從節點i(包括n)出發抵達節點n的流量的速率,DVSR公平速率滿足

這實際上是一個基於節點觀測流量速率的Max_min運算。它假設rn代表節點i的帶寬需求。公平帶寬分配器通過公平算法,並結合從下游節點接收到的控制消息,為本節點的每個流量計算出一個公平速率,並將本站點的業務以計算出的公平速率發送,同時將各流量的公平速率寫入到循環控制包的相應位置,發送給上游。接收到控制消息的上游節點同樣利用這些消息,並綜合本地消息考慮,為每一個流量設置一個速率。這樣,DVSR實現最大化的空間再利用。