公平算法

公平算法

公平控制原理

公平算法保證了低優先權的B_EIR和C類業務在RPR環上的公平接入。通過設定公平算法的權重，可以使不同的結點具有不同的接入速率。節點可以分別在外環和內環上設定不同的權重。

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

公平控制的原理就是當節點監測出輸出鏈路擁塞時(如圖1所示),就啟動公平算法機制,計算本地的公平速率,然後通過反饋機制向上游傳送公平速率信息,使得環上其他節點可隨時了解擁塞節點處的流量情況,並根據公平信息調整自己的接入速率,當下游擁塞消除後,就逐漸提高自己的傳送速率,在經過一段收斂時間之後,環上所有節點將會基於各自的權重值所分得的速率進行傳送,對於等權值的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實現最大化的空間再利用。