基於帶寬的非平衡負載分擔的製作方法

2023-07-24 03:01:06 1

專利名稱：基於帶寬的非平衡負載分擔的製作方法
基於帶寬的非平衡負載分擔1.技術領域
本發明屬於計算機通信領域。2.背景技術
對於同一路由協議來說，可以配置多條目的地址和開銷都相同的路由。如果到達同一目的地址的路由中，如果優先級別都相同，則同時採用這幾條路徑。在轉發去往該目的地址的報文時，依次通過各條路徑發送，實現網絡的負載分擔，並提高系統吞吐率，從而提高轉發效率。當各條路徑的帶寬相同時，則稱其為基於帶寬的平衡負載分擔；當帶寬不同時，即是基於帶寬的非平衡負載分擔。
目前的IPv6路由器一般帶有非平衡負載分擔功能。思科和華為的路由器在實現非平衡負載分擔時有如下限制:在各條分擔路由中，任一條鏈路的帶寬不能小於總帶寬的1/16，否則不參與負載分擔。這種策略使得用戶不能根據實際情況靈活地為各接口設置帶寬值。例如:有一臺帶寬為IOG的路由器和一臺帶寬為IG的路由器堆疊起來作為一臺設備使用時，如果需要用兩個IOG埠和一個IG埠形成三條等價路由，華為和思科的路由器是不支持這種組網的。如果一定需要這種組網環境的話，就需要將IOG接口的帶寬降低為7.5G來滿足「1/16」這個限制，這樣反而會降低路由轉發性能。本文中的實現將打破「在各條分擔路由中，任一條鏈路的帶寬不能小於總帶寬的1/16」這個限制，進一步提高路由轉發效率。
目前常用的算法如下:在數據平面FIB中增加一個成員，假設是UlEcmp[2]。它是一個ULONG型變量，由64位組·成。將其分成16份，每份佔4位，第一位用於表示數據有效性，後三位表示FIB表項的編號。因為FIB表項佔三位，所以最多能支持8條不同的等價路由。
假設有2條等價路由，一條帶寬是1G，其對應的FIB表項序號為X ;另一條帶寬為15G，其FIB表項序號為Y。則UlEcmp[2]變量被填充後結果如

圖1所示。其中第一位全部有效，都置位為1，為了便於觀察，不在下面的數組結構圖中顯示。
通過上面的例子可以看到如下限制:在各條分擔路由中，任一條鏈路的帶寬不能小於總帶寬的1/16,否則無法用成員ulEcmp[2]填充結果表示。3.發明內容
下面是改進的算法，不僅打破了上述「1/16」的限制，而且對任意一條等價路由的帶寬可以設置的最小精度為總帶寬的1/232，大大增加了用戶對帶寬設置的靈活性。
為了使得路由器能對收到的每一條流，快速的確定它該從哪個等價的接口中發送出去，便採用了對流的源IPv6地址和目的IPv6地址的前32位進行哈希計算得到的值來確定與該流相匹配的發送接口。該哈希函數的設計中用到了著名的三距離定理:用{X}表示正整數X的小數部分，設O < C < 1，C是無理數，則{C}，{2*C}，{3*C}，……{N*C}把[O,I]分成N+1段。這N+1段的長度最多只有三種可能取值，並且{(N+1)*C}會把某一長度最大的那段分為兩小段。如果C是黃金分割數，則{(N+1)*C}把最長那段分為兩個小段後，這兩個小段的長度為黃金分割的比例。
利用上述定理採用源和目的IPv6地址之和的前32位與黃金分割數(0.618)相乘得到的哈希值，對於相同的流，值相同。不同的流哈希值會在整個散列的區間上找到最長那段的黃金分割點，這樣便使得全部流的哈希值在整個散列區間上均勻分布。然後將所有參加負載分擔的接口的帶寬值累加形成從O到最大值為帶寬累加值的區間，並與上述散列得到的區間一一對應起來，那麼從總體流量上的均衡效果就和用戶在接口上配置的帶寬值相一致了，這樣基於帶寬的負載分擔功能便可以實現了。
利用偽代碼描述如下:W[i]表示各FIB表項對應的帶寬值，在負載分擔功能未開啟的情況下，該值為1，各等價路由負載均衡；在我們的功能使能時，w
到w[1-l]中的值為用戶配置的相應帶寬值。η表示等價FIB表項的個數，W_SUM表示各等價FIB帶寬之和，P[i]表示各等價接口佔總帶寬的比例大小，W_TMP表示臨時存放帶寬值。
I)首先計算等價 路由的總帶寬W_SUM = W
+W[l]+......+W[η-1]。
2)計算各等價接口佔總帶寬的比例大小
權利要求
1.基於帶寬的非平衡負載分擔，其特徵在於，在路由器負載分擔功能的實現中哈希函數採用以IP位址和黃金分割數相乘的方式，根據「三距離定理」，使得數據流的哈希值在
區間上均勻分布，來實現基於帶寬的非平衡負載分擔，使用戶配置的最小帶寬值可以精確到總帶寬值的1/232。
全文摘要
IPv6將成為下一代網際網路協議，高性能的IPv6路由器是目前的一個研究熱點。本發明以IPv6路由器的開發為背景設計了基於帶寬的非平衡負載分擔功能，該功能打破了以往用戶對負載分擔帶寬設置的限制，使用戶可以任意設置負載分擔帶寬的大小，從而提高路由器系統的吞吐量以及用戶配置的靈活性。
文檔編號H04L12/803GK103139092SQ20111038341
公開日2013年6月5日 申請日期2011年11月28日 優先權日2011年11月28日
發明者王文斌 申請人:王文斌