現(xiàn)代通信網(wǎng)絡交叉開關(guān)交換結(jié)構(gòu)調(diào)度算法

1、3. 交換結(jié)構(gòu)(SWITCHING FABRIC)根據(jù)轉(zhuǎn)發(fā)表對分組進行處理，將某個輸根據(jù)轉(zhuǎn)發(fā)表對分組進行處理，將某個輸入端口進入的分組從一個合適的輸出端口轉(zhuǎn)發(fā)出去。入端口進入的分組從一個合適的輸出端口轉(zhuǎn)發(fā)出去。是路由器的關(guān)鍵構(gòu)件是路由器的關(guān)鍵構(gòu)件三類常用交換結(jié)構(gòu)：三類常用交換結(jié)構(gòu)： 共享內(nèi)存、共享總線、共享內(nèi)存、共享總線、 crossbar(交叉開關(guān)交叉開關(guān))高性能交換結(jié)構(gòu)及其調(diào)度算法是研制高速高性能交換結(jié)構(gòu)及其調(diào)度算法是研制高速IPIP路由器路由器交換結(jié)構(gòu)是路由器的核心，有總線、共享交換結(jié)構(gòu)是路由器的核心，有總線、共享內(nèi)存和交叉開關(guān)內(nèi)存和交叉開關(guān)3 3種類型。種類型。目前在實際的路由器設計中

2、，一般采用如目前在實際的路由器設計中，一般采用如下兩種方式構(gòu)建高端路由器：共享內(nèi)存下兩種方式構(gòu)建高端路由器：共享內(nèi)存+ +集中轉(zhuǎn)發(fā)，分布緩存集中轉(zhuǎn)發(fā)，分布緩存+ +交換矩陣。交換矩陣。第一種方式的典型代表為第一種方式的典型代表為JuniperJuniper的的M40 M40 路路由器，由器，第二種方式的典型代表為第二種方式的典型代表為CiscoCisco的的GSR12000GSR12000路由器路由器總線總線 由于由于端口速率高，交換結(jié)構(gòu)需要加速，而且端口速率高，交換結(jié)構(gòu)需要加速，而且接口板與交換板之間、控制板與接口板之間、控接口板與交換板之間、控制板與接口板之間、控制板與交換板之間的連線很多

3、，目前的高速路由制板與交換板之間的連線很多，目前的高速路由器以及交換機都采用高速背板總線以提高系統(tǒng)的器以及交換機都采用高速背板總線以提高系統(tǒng)的吞吐率吞吐率。 為了提高效率，數(shù)據(jù)線采用串行差分線路，速率可達每秒鐘12吉比特。要保證如此高的傳輸速率和那么多的連線，對背板總線的設計要求非常高。如何降低數(shù)據(jù)的傳輸誤碼率以及保證時鐘同步是總線設計中的關(guān)鍵技術(shù)。斯坦福大學的Tiny Tera路由器項目中，大量采用串行總線的實現(xiàn)方法值得研究和借鑒共享內(nèi)存結(jié)構(gòu)共享內(nèi)存結(jié)構(gòu) 的路由器把接收的數(shù)據(jù)包存儲在共享內(nèi)存，端口間只需交換數(shù)據(jù)包指針而無需拷貝整個數(shù)據(jù)包，可有效提高交換結(jié)構(gòu)帶寬利用率。但存儲器存取速度受限制，

4、也限制路由器帶寬。交叉開關(guān)交叉開關(guān)在在N N個輸入端口和個輸入端口和N N個輸出端口間個輸出端口間建立建立N N條共享條共享總線總線。輸入。輸入和輸出端口通過并和輸出端口通過并發(fā)交換多個數(shù)據(jù)包而提高帶寬發(fā)交換多個數(shù)據(jù)包而提高帶寬。一般的交叉開關(guān)存在的一個問題是，輸入端一般的交叉開關(guān)存在的一個問題是，輸入端口口HOLHOL阻塞使帶寬利用率低。阻塞使帶寬利用率低。一一個解決方法是內(nèi)部加速，使交叉開關(guān)的內(nèi)個解決方法是內(nèi)部加速，使交叉開關(guān)的內(nèi)部帶寬大于輸入鏈路帶寬總和，輸出端口同部帶寬大于輸入鏈路帶寬總和，輸出端口同時接收多個輸入端口的數(shù)據(jù)包。這種輸出排時接收多個輸入端口的數(shù)據(jù)包。這種輸出排隊方式優(yōu)點

5、是數(shù)據(jù)包只存在輸出排隊時延，隊方式優(yōu)點是數(shù)據(jù)包只存在輸出排隊時延，但缺點是擴展性較差但缺點是擴展性較差。另另一個解決方法是輸入虛擬排隊。交叉開關(guān)一個解決方法是輸入虛擬排隊。交叉開關(guān)在每個輸入端口對應于一個輸出端口維持一在每個輸入端口對應于一個輸出端口維持一個個FIFOFIFO隊列。隊列。調(diào)度算法確定各排隊數(shù)據(jù)包在路由器輸出端口的發(fā)調(diào)度算法確定各排隊數(shù)據(jù)包在路由器輸出端口的發(fā)送順序，得到輸入端口和輸出端口之間的一個匹配，送順序，得到輸入端口和輸出端口之間的一個匹配，提供輸入端口到輸出端口的通路提供輸入端口到輸出端口的通路。 n 先來先服務先來先服務n 隨機選擇隨機選擇(Random Select

6、ing)n 輪循輪循(Round-Robin)n 加權(quán)公平排隊加權(quán)公平排隊(WFQ-Weighted FairQueuing) n 分層鏈路共享算法等。分層鏈路共享算法等。3. 交換結(jié)構(gòu)交換結(jié)構(gòu)(switching fabric)調(diào)度算法確定各排隊數(shù)據(jù)包在路由器輸出端口的發(fā)調(diào)度算法確定各排隊數(shù)據(jù)包在路由器輸出端口的發(fā)送順序，得到輸入端口和輸出端口之間的一個匹配，送順序，得到輸入端口和輸出端口之間的一個匹配，提供輸入端口到輸出端口的通路提供輸入端口到輸出端口的通路。 n 先來先服務先來先服務n 隨機選擇隨機選擇(Random Selecting)n 輪循輪循(Round-Robin)n 加權(quán)公平

7、排隊加權(quán)公平排隊(WFQ-Weighted FairQueuing) n 分層鏈路共享算法等。分層鏈路共享算法等。3. 交換結(jié)構(gòu)交換結(jié)構(gòu)(switching fabric)調(diào)度算法中，加權(quán)公平排隊算法（調(diào)度算法中，加權(quán)公平排隊算法（WFQ-WFQ-Weighted Fair QueuingWeighted Fair Queuing）和經(jīng)過改進后的加權(quán)公）和經(jīng)過改進后的加權(quán)公平流排隊算法（平流排隊算法（WF2Q-Weighted Fair Flow WF2Q-Weighted Fair Flow QueuingQueuing）比較容易實現(xiàn)，而且性能也不錯?？偅┍容^容易實現(xiàn)，而且性能也不錯?？傊?，

8、要讓互聯(lián)網(wǎng)真正能夠綜合多種業(yè)務，作為之，要讓互聯(lián)網(wǎng)真正能夠綜合多種業(yè)務，作為網(wǎng)絡連接核心設備的路由器，必須提高端口速網(wǎng)絡連接核心設備的路由器，必須提高端口速率和交換容量，提供率和交換容量，提供QoSQoS保證和流量工程（保證和流量工程（TE-TE-Traffic EngineeringTraffic Engineering）功能。）功能。 加權(quán)公平排隊算法是一種理想的調(diào)度算法。它加權(quán)公平排隊算法是一種理想的調(diào)度算法。它根據(jù)每個連接權(quán)值分配鏈路帶寬。設各連接權(quán)根據(jù)每個連接權(quán)值分配鏈路帶寬。設各連接權(quán)值可表示為值可表示為w1, w2,w1, w2,wnwn，其中，其中wiwi=1=1，則排隊，則排

9、隊連接連接k k具有可保證帶寬具有可保證帶寬wkwk* *R/R/wiwi，R R為鏈路帶寬。為鏈路帶寬。因此，加權(quán)公平排隊算法可保護和隔離連接，因此，加權(quán)公平排隊算法可保護和隔離連接，公平分配剩余帶寬，并且若連接發(fā)送速率受限公平分配剩余帶寬，并且若連接發(fā)送速率受限于漏桶控制算法，則該連接具有一個可保證的于漏桶控制算法，則該連接具有一個可保證的端到端時延上限。但加權(quán)公平排隊算法缺點是端到端時延上限。但加權(quán)公平排隊算法缺點是需要保存每個排隊連接狀態(tài)信息，各數(shù)據(jù)包需需要保存每個排隊連接狀態(tài)信息，各數(shù)據(jù)包需求虛擬時鐘并且按優(yōu)先級排隊，其擴展性差。求虛擬時鐘并且按優(yōu)先級排隊，其擴展性差。分層鏈路共享服

10、務是指按類層次組織一個鏈路的分層鏈路共享服務是指按類層次組織一個鏈路的所有連接，路由器基于策略地給每個類對象分配所有連接，路由器基于策略地給每個類對象分配鏈路帶寬。分層鏈路共享需要實現(xiàn)以下幾個目標：鏈路帶寬。分層鏈路共享需要實現(xiàn)以下幾個目標：若一個類有足夠帶寬需求，應保證該類的最小網(wǎng)若一個類有足夠帶寬需求，應保證該類的最小網(wǎng)絡帶寬；若一個類具有剩余帶寬，應保證各兄弟絡帶寬；若一個類具有剩余帶寬，應保證各兄弟類公平使用這些剩余帶寬；在類層次內(nèi)，支持實類公平使用這些剩余帶寬；在類層次內(nèi)，支持實時和優(yōu)先級服務。對于以上這些目標，有時可能時和優(yōu)先級服務。對于以上這些目標，有時可能是沖突的，調(diào)度算法應實現(xiàn)相應機制優(yōu)先滿足某是沖突的，調(diào)度算法應實現(xiàn)相應機制優(yōu)先滿足某些目標要求。用于分層鏈路共享服務的調(diào)度算法些目標要求。用于分層鏈路共享服務的調(diào)度算法主要包括基于類排隊主要包括基于類排隊(Class Based (Class Based QueueingQueueing)4)4，分，分層加權(quán)公平排隊算法層加權(quán)公平排隊算法(Hierarchical Packet Fair (Hierarchical Packet Fair Queu