一種新型的聯合單播／組播的兩級交換結構

摘要：高速交換結構的設計中一般很難以較低的復雜度實現其對組播業務的支持。提出一種聯合單播/組播的兩級交換結構TSSIUM，該結構通過對Crossbar結構級聯一個組播合路結構實現，因此可以極低的復雜度即可實現對組播業務的支持。理論分析和實測數據均表明，該結構在容許的通信量下可以達到100％的吞吐率。

關鍵詞：組播交換； 調度算法； 吞吐率； 時延

中圖法分類號：TP393．02文獻標識碼：A

文章編號：1001－3695(2007)01－0286－02

1引言

Internet上的多媒體業務，如流媒體、視頻會議和遠程教育等，正在成為信息傳送的重要組成部分，這就要求網絡具有組播能力。路由器作為網絡中的關鍵設備，因此其交換結構的設計應考慮對組播業務的支持。因為對于組播業務，輸出排隊（OQ）的交換結構存在極大的加速比[1，2]，因而現有支持組播業務的交換結構一般采用虛擬輸出排隊（VOQ）的Crossbar結構，通常主要采用以下兩種方式：

（1）組播復制（Copy Multicast）。組播信元根據其輸出端口數在VOQ隊列之前進行復制。與單播情形不同，對于組播業務VOQ隊列的速度和交換矩陣的內部帶寬必須加速N倍。隨著鏈路速率和端口數的增加，這種方式在現有的工藝水平下很難實現。

（2）組播扇出（Fanout Multicast）。利用Crossbar結構的固有特性，輸入端口立即傳送組播信元到交換結構，中心交換單元負責將該信元送到每一個輸出端口。信元送出的方式有兩種，即扇出不拆分（No Fanoutsplitting），該方式下一個信元的所有拷貝必須在同一時隙被送出，如果組播信元對任何一個輸出端口的爭用一旦失敗即沒有信元被傳送，信元必須在下一個時隙再次努力；扇出拆分（Fanoutsplitting），該方式下組播信元可以在任意數目的時隙內被送到輸出端口，只有那些在前一個時隙內競爭不成功的組播信元才在下一個時隙繼續爭用輸出端口。研究表明，扇出拆分的方法用較高的復雜度可以使交換吞吐率有所提高，但是隨著組播比例的增加，吞吐率會逐漸降低[3]。

以上兩種方式均存在吞吐率較低，實現復雜的問題。為此我們提出了聯合單播/組播的兩級交換結構TSSIUM，該結構在容許的通信量下對于獨立均勻分布業務可以達到100％的吞吐率，并且具有極低的復雜度，易于硬件實現。

2TSSIUM交換結構

傳統的交換結構一般基于輸出排隊(OQ)結構。在這種結構下，到達輸入端口的信元將被立即交換到相應的輸出端口。OQ的優點是能夠提供最優的吞吐率和時延控制，但為了保證OQ的正常運行必須N倍地加速。

為了克服OQ結構的可擴展性問題，高速交換考慮采用輸入排隊(IQ)結構。到達的信元首先被保存在輸入端口的緩沖區中，然后通過調度算法決定信元何時通過交換結構傳送到輸出端口。IQ的優點是不需要加速，但是存在隊頭阻塞問題(Head of Line Blocking)。如果隊列隊頭的信元被阻塞，同隊列到其他輸出端口的信元就不能被轉發。研究表明，當端口數較多時，在所有輸出均勻分布的貝努利到達下，IQ只能達到58．6%的吞吐率[4]。 

解決輸入排隊隊頭阻塞問題的一種簡單方案是虛擬輸出排隊(VOQ)。在此結構下，每個輸入端口為每個輸出設置一個隊列，從而消除了鏈頭阻塞并保持加速比為1。理論研究和仿真試驗均表明，采用一定的調度算法，VOQ交換結構可以達到100%的吞吐率[5~7]。

聯合單播/組播的兩級交換結構（TwoStage Switches of Integrated Unicast and Multicast，TSSIUM）如圖1所示。其第一級交換結構采用Crossbar交換矩陣（N輸入，N+1輸出），并設置VOQ輸入緩存；第二級交換結構包括單播信元輸出緩存單元、組播復制單元和合路緩存單元。

圖1聯合單播/組播的兩級交換結構

我們僅考慮分組定長的情形，即分組在進入第一級交換結構前已被分成定長的信元，時間被分成等長的時隙。輸入端口i(1≤i≤N)的信元到達是一個離散時間的隨機過程Ai(t)，在一個時間片t內，最多只有一個信元到達一個輸入端口。第一級交換結構中，單播輸出端口為(1→N)，組播輸出端口為N+1。到達輸入端口i且輸出端口是j的信元放入VOQ隊列Qi， j中 ，所有組播信元放入隊列Qi，N+1中，(1≤i≤N)。我們定義Aij(t)為信元到達Qi， j的到達過程，到達過程的集合為A(t)={Ai(t)，1≤i≤N}。

組播信元和單播信元在第一級交換結構中均只傳輸一次，組播信元傳往固定的輸出端口（N+1），交換矩陣帶寬占用與單播交換相同。第二級交換結構組播復制單元根據組播信元包含的輸出端口號進行復制，然后與從單播信元輸出緩存單元輸出的單播信元合路，最后統一輸出。

3性能分析

文獻[5，6]分別給出了交換結構容許的通信量、信元獨立到達、信元均勻到達的定義，但是沒有對組播情況作明確說明。本文對單播組播情況總體考慮后作如下定義：

定義2若信元到達的過程滿足以下兩個條件：①每個輸入端口的信元（包括組播、單播信元）到達是獨立同分布的；②每個輸入端口的信元（包括組播、單播信元）到達獨立于其他輸入端口，則我們稱信元的到達是獨立的。定義3若單播信元的到達過程具有相同的速率，并且目的端口均勻分布在所有的輸出端口；組播信元的到達過程亦具有相同的速率，并且組播扇出在各輸出端口均勻分布，則我們稱信元的到達是均勻的。

3．1吞吐率

吞吐率是指單位時間內交換結構轉發的信元數量，對于獨立均勻分布業務，在容許通信量下交換結構TSSIUM具有100％的吞吐率。

3．2時延

時延是指信元從到達交換結構到離開所經歷的時間。低負載情況下隊列時延較小，可以忽略。重負載情況下，算法每N個時隙服務單播FIFO一次，接近于到達速率為λi， j/N，確定服務時間為N個時隙的M/D/1排隊；每N個時隙服務組播FIFO一次，復制后接近于到達速率為λi， f，確定服務時間為N個時隙的M/D/1排隊[7]。那么在重負荷貝努利到達情形下：

3．3復雜度

第一級交換可用現有的Crossbar交換結構。第二級交換單播信元輸出緩存單元、組播復制單元和合路緩存單元，均可簡單實現。所以該結構實現的復雜度極低。

4結束語

網絡組播通信量的增加會大大增加交換的負擔，導致網絡擁塞。因此隨著網絡帶寬要求的增長，多媒體業務的增加，必須有新的技術和新的算法被不斷提出才能滿足未來的需求。我們提出的TSSIUM通過兩級交換結構實現組播，第一級交換結構以單播方式處理組播信元，極大地節省了Crossbar交換結構的帶寬，從而解決了現有組播調度算法吞吐率低的問題；第二級交換結構僅需以極低的復雜度即可實現組播復制，便于工程實現。該結構性能優越，實現簡單，因而具有一定的應用前景。

參考文獻：

［1］M Ajmone Marsan， A Bianco， et al. On the Throughput of InputQueued Cellbased Switches with Multicast Traffic[C]. Anchorage: Proceedings of IEEE INFOCOM2001， 2001.16641672.

［2］Sundar Iyer， Nick McKeown. On the Speedup Required for a Multicast Parallel Packet Switch[J]. IEEE Communications Letters， 2001，5(6):269.

［3］N McKeown，M Izzard，A Mekkiuikul.The Tiny Tera:A Packet Switch Core[J].IEEE Micro.，1998，(12):2633.

［4］Karol M， Hluchyj M， Morgan S. Input Versus Output Queueing on a Space Division Switch[J]. IEEE Transactions on Communication， 1988， 35(12):13471356.

［5］Adisak Mekkittikul， Nick McKeown. Practical Scheduling Algorithm to Achieve 100% Throughput in Inputqueued Switches [C]. IEEE Computer Society Press，1998.792799.

［6］N McKeown， V Anantharam， J Walrand. Achieving 100% Throughput in an Inputqueued Switch[C]. SanFrancisco:Proc. of IEEE INFOCOM’96， 1996.296302.

［7］McKeown N. The iSLIP Scheduling Algorithm for Inputqueued Switches[J]. IEEE/ACM Transactions on Networking， 1999， 7(2): 188201.

作者簡介：

賈娟（1982），女，北京人，碩士研究生，主要研究方向為高速網絡系統高可用性；

曲晶（1980），男，山西忻州人，工程師，主要研究方向為寬帶信息網絡；

伊鵬（1978），男，湖北黃岡人，博士，主要研究方向為高速路由器交換結構；

汪斌強（1963），男，安徽安慶人，教授，博導，總工，國家“863”信息領域重大課題“可擴展到T比特的高性能IPv4/IPv6路由器基礎平臺及實驗系統”總設計師，主要研究方向為高速路由器核心技術、寬帶信息網絡。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文