[發明專利]共享存儲交換支持組播的雙門限端口隊列控制方法

無效

• 申請號: 200710164015.1
• 申請日: 2007-10-16
• 公開（公告）號: CN101141399A
• 公開（公告）日: 2008-03-12
• 發明（設計）人: 汪洋;余少華
• 申請（專利權）人: 武漢烽火網絡有限責任公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L1/18
• 代理公司: 北京捷誠信通專利事務所
• 代理人: 魏殿紳;龐炳良

技術領域

本發明屬于以太網交換機的數字信息傳輸控制技術領域，具體涉及一種共享存儲交換支持組播的雙門限端口隊列控制方法。

背景技術

交換結構是交換/路由設備完成轉發功能的核心，按照進入信元的緩存策略分類，可以分為輸入排隊、輸出排隊和共享存儲排隊。其中前兩種實現方式通常還包括一個空分(space-division)單元，典型的如Crossbar^[1]。大量的研究表明，輸出排隊能夠實現最優的性能，同時避免諸如線頭阻塞(HOL)之類降低系統效率的因素。與輸入或輸出排隊類型不同，共享存儲器(SM)的交換結構將交換的功能全部在一個公共存儲器中實現，其排隊原理非常類似于輸出排隊，且由于各個隊列共享存儲空間，提高了對存儲資源的利用率^[2]，加上沒有使用其他空分結構，使得共享存儲交換結構有較高的效率和較低的實現成本，從而在單板交換或大型交換系統的前端交換中占據主導地位^[3]。

共享存儲交換結構的一個難點在于存儲器的管理和分配。就實現而言，進入的報文在存到共享緩存之前，通常都被等分為固定長度的信元，存儲于共享緩存中的信元按照到不同的輸出端口組織為不同的輸出隊列。在系統負載較重時，各個隊列會競爭對共享緩存的使用，特別是在不均勻流量條件下，重負載端口的隊列會大量擠占公共緩存而影響其他端口對緩存的正常使用。因此，如何對交換結構的效率和公平性做出折衷一直是個研究熱點。

對隊列進行門限控制是通常采取的措施，此外還有不使用門限而對信元進行推出(push?out，PO)操作的算法^[4]。PO算法在理論上是最理想的，但其實現困難，因此一般作為一個基準的參考算法和其他算法進行對比。傳統的門限算法包括靜態門限(ST)，動態門限(DT)^[5][6]等。其中ST缺乏對流量場景的適應性，DT受到廣泛關注，但文獻[7]證明其表現不穩定，原因在于它試圖用一個簡單的線性模型來計算非線性的排隊系統。最近提出的研究包括使用衰減函數來計算每隊列的門限^[8]，這個算法將DT提出的全局的動態門限方法細化為每個隊列的動態門限，并認為一個輸出端口隊列所需要向共享存儲區索要的空間與剩余的空閑存儲區大小成正比，而與這個輸出端口隊列當前的長度成反比。當剩余的緩沖區的大小處于關鍵值時，為了最大程度地提高存儲器的利用率，鼓勵較短的隊列優先向剩余存儲器申請空間。文獻[7]提出使用模糊邏輯和遺傳算法來進行計算，并提出了在線計算和離線計算相結合的思想來解決遺傳算法難以在交換芯片控制器內實時完成的困難。

受組播的應用(如IPTV等)的推動，為了讓共享存儲交換結構也同時能夠高效地轉發組播流量，通常采用兩種機制來進行組播和單播的混合分組轉發^[1]。第一種是使用專用組播信元隊列(DedicatedMulticast?Queue，DMQ)的共享存儲，其原理如圖1所示，組播信元總是有最高的優先級，只有當組播信元隊列為空，或者組播隊列的線頭(Head?of?Line，HOL)不是發往同一個端口時，才對發往這個端口的單播信元進行輸出操作；另一種是使用地址拷貝的隊列(Address?CopyQueue，ACQ)，每個輸出隊列以FIFO方式保存信元在存儲空間中的地址。一個組播信元的地址會出現在多個端口的輸出地址隊列中，如圖2所示，其中帶陰影的信元地址指向相同的組播信元，這個組播信元存放于公共的共享存儲空間。此外，每個組播信元有自己的計數器，用于記錄需要轉發的端口數。

DMQ方案的缺陷在于，當突發組播流量的帶寬達到一定程度時，將嚴重妨礙單播信元的正常轉發，因為一般而言組播信元具有相對較高的優先級。對此，研究者提出了輪轉策略，帶權重輪轉策略等方案^[1]，但是這些策略又會在很多情況下造成組播隊列的線頭擁塞，因為組播隊列一般情況下只有一個。ACQ較好地解決了擁塞問題，因此雖然它也有別的弱點，如還需要額外的空間來存放地址隊列，但仍然成為共享存儲交換結構支持組播的主要機制。

如前所述，已有的門限控制算法本身尚存諸多問題，缺乏對組播考慮是另一個重要的掣制。為此，需要尋求能夠在組播-單播的混合流量環境下都能夠提供高效的信元準入(門限)機制，這種機制應該滿足以下要求：(1)易于在線計算；(2)適應流量場景；(3)維持組播和單播信元占用緩存資源的合理平衡；(4)實現系統效率和公平的合理折衷。