[發明專利]交換機及調度算法

在審

• 申請號: 201310695464.4
• 申請日: 2013-12-17
• 公開（公告）號: CN104717160A
• 公開（公告）日: 2015-06-17
• 發明（設計）人: 謝軍;涂曉東;孟中樓;張文默;陸一飛;宋偉
• 申請（專利權）人: 華為技術有限公司;電子科技大學
• 主分類號: H04L12/931
• 分類號: H04L12/931;H04L12/935;H04L12/937
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 劉芳

技術領域

本發明實施例涉及通信技術領域，尤其涉及一種交換機及調度算法。

背景技術

交換機是網絡中的重要設備，交換機的交換結構和調度算法決定了交換機的性能和成本。其中，調度算法主要實現網絡輸入端口和輸出端口之間的匹配，從而解決資源競爭，盡量提高網絡性能，調度算法的好壞直接影響整個交換網絡的性能。Crossbar交換結構是輸入排隊的典型實現方式，在Crossbar交換結構中，為了消除輸入隊列隊頭阻塞（HOL）現象，提高系統吞吐率，一種有效的辦法是采用虛擬輸出隊列（VOQ），即在每個輸入端口，對應每個輸出端口都設一個輸入輸出（FIFO）隊列，每一輸入端口對應的FIFO隊列緩存相應的發送數據幀，如VOQ12指輸入端口1到輸出端口2的發送數據幀。圖1為N個輸入端口N個輸出端口的交換結構示意圖，如圖1所示，輸入端口輸入的發送數據幀分別被緩存至VOQ隊列中等待發送，調度器（N,N）用于管理隊列信息，執行調度算法，調度算法首先根據輸入隊列的狀態做出匹配結果,然后控制交換結構中交叉點的開合。由于crossbar調度器（N,N）無內部存儲、無阻塞，在調度過程中通常會出現競爭沖突問題，為了解決端口處的沖突，硬件中最常見的ISLIP調度算法為：在N×N個輸入隊列與N個輸出端口中尋找1組匹配，使得1個輸出最多匹配1個輸入，1個輸入最多匹配1個輸出。所有的輸入端口和輸出端口在新的時隙到來時開始匹配，每次匹配之后，只有尚未匹配的端口有資格參加下一輪的匹配，算法一直到迭代收斂為止。迭代收斂是指下一輪迭代不會增加新的連接，每一輪迭代分為3步：輸入請求，輸出授權，輸入認可。

而在FC交換機中，通常采用緩沖區到緩沖區的流量控制方式，這種流量控制機制建立在信用值管理的基礎上，主要由兩個相連設備的數據發送端來控制。具體地，在每個端口的發送端會有一個緩沖區到緩沖區的信用值，該信用值表示與之連接的對端設備的接收緩沖區容量（即最多能夠緩存多少幀數據），同時發送端還有一個信用值計數器(初始值為0)，每當源端口向目的端口發送出去一幀數據，信用值計數器會進行加1操作，用來指示對端設備已經占用了一個緩沖區容量來存儲這一幀數據，如果對端設備把這幀數據從接收緩存區間中讀出來或者并沒有緩存這個數據而是進行丟棄操作，那么對端設備就會給發送端回復一個RDY信號，發送端接收到這個信號后便對信用值計數器進行減1操作，只有信用值計數器的值小于信用值時才發送端可以發送數據。

結合上述流量控制方式可以看出，為了避免發送和接收沖突，上述調度算法必須保證在一個時隙內每個輸入端口至多發送一個信元，每個輸出端口至多接收一個信元，而且需要多次迭代，在交換機中每一信元在等待端口匹配的過程中會導致延時大，從而導致輸入端口緩存消耗的資源較大，因此會造成資源浪費。

發明內容

本發明實施例提供一種交換機及調度算法，可節省輸入端口緩存的資源。

第一方面，本發明實施例提供一種交換機，包括：

N個輸入端口、N個輸出端口和調度裝置；

所述N個輸入端口中，每個輸入端口都設置M個數據緩存隊列和N個信息緩存隊列，所述M個數據緩存隊列用于緩存輸入端口輸入的任一發送數據幀，所述N個信息緩存隊列用于緩存任一所述發送數據幀的幀信息，M小于等于N，M和N為整數；

每一輸入端口的所述M個數據緩存隊列和N個輸出端口之間通過調度裝置連接，所述調度裝置用于執行調度算法，根據每一輸入端口的N個信息緩存隊列的狀態調度出發送數據幀。

在第一方面的第一種可能的實施方式中，所述調度裝置包括：

發送器，用于根據輸入端口的N個信息緩存隊列中的任一信息緩存隊列非空的指示信息，向非空的信息緩存隊列指示的輸出端口發出請求直到所述請求得到授權；

輪詢仲裁器，用于根據信息緩存隊列的優先級進行輪詢仲裁，選擇授權的第一輸入端口，其中，每一輸出端口都有一個對應的輪詢仲裁器；

處理器，用于讀取所述第一輸入端口的數據緩存隊列緩存的發送數據幀。

結合第一方面的第一種可能的實施方式中，在第一方面的第二種可能的實施方式中，所述發送數據幀的幀信息包含：發送數據幀的優先級、緩存所述發送數據幀的數據緩存隊列號和輸出端口號，所述輪詢仲裁器用于：

根據接收到的請求所對應的信息緩存隊列緩存的發送數據幀的優先級進行輪詢仲裁，選擇授權的所述第一輸入端口；

所述處理器用于：

根據所述第一輸入端口的信息緩存隊列緩存的信息緩存隊列號讀取所述信息緩存隊列號對應的數據緩存隊列中的發送數據幀。