扈紅超，郭云飛，陳庶樵，伊鵬

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002)

1 引言

以應(yīng)用和服務(wù)為特征的網(wǎng)絡(luò)承載網(wǎng)的發(fā)展使得網(wǎng)絡(luò)業(yè)務(wù)呈現(xiàn)多元化的發(fā)展趨勢，視頻點(diǎn)播、VoIP等為特征的多媒體及相關(guān)技術(shù)(如 P2P)成為了下一代互聯(lián)網(wǎng)(NGI, next generation internet)和三網(wǎng)融合下網(wǎng)絡(luò)業(yè)務(wù)的典型特征之一。多媒體業(yè)務(wù)的重要特征是具有多播性，相對(duì)于單播業(yè)務(wù)<源s-目的d>一對(duì)一的傳輸，多播業(yè)務(wù)存在多個(gè)目的，這一特征要求網(wǎng)絡(luò)核心交換節(jié)點(diǎn)能夠支持多播交換，從而提高網(wǎng)絡(luò)傳輸效率和吞吐量[1,2]。就現(xiàn)有交換機(jī)制而言，輸出排隊(duì)(OQ,output queuing)交換結(jié)構(gòu)交換和存儲(chǔ)單元都需工作于N倍線路速率，構(gòu)建大容量交換系統(tǒng)時(shí)不具備良好的擴(kuò)展性；輸入排隊(duì)(IQ, input queuing)交換結(jié)構(gòu)需要集中式的調(diào)度[3]，構(gòu)建大容量交換系統(tǒng)時(shí)存在瓶頸。近年來隨著微電子技術(shù)的進(jìn)步，在交換單元內(nèi)部集成一定容量的緩存成為了現(xiàn)實(shí)，基于帶緩存交叉開關(guān)構(gòu)建的聯(lián)合輸入交叉節(jié)點(diǎn)排隊(duì)(CICQ, combined input-crosspoint queuing)交換結(jié)構(gòu)備受關(guān)注[4]。CICQ通過在每個(gè)交叉點(diǎn)集成了一定的緩存將N×N的交換結(jié)構(gòu)分割為N個(gè)N×1和N個(gè)1×N的子結(jié)構(gòu)，并將輸入、輸出的帶寬沖突隔離開來，使分布式調(diào)度成為了現(xiàn)實(shí)。目前基于 CICQ構(gòu)建的調(diào)度機(jī)制集中在提供高吞吐量[5~11]、模擬 OQ[12~14]和性能保障[15~17]和多播交換[18~20]方面。

在 CICQ交換結(jié)構(gòu)的多播研究方面，文獻(xiàn)[18]分析了(K,Na)- c omplex 多播流量模型下CICQ的吞吐量，指出當(dāng)加速比S有限時(shí)吞吐量隨交換結(jié)構(gòu)規(guī)模N→∞大幅下降；在均勻“可允許”到達(dá)下，當(dāng) S ＞ 1 和交叉點(diǎn)緩存容量時(shí)交換系統(tǒng)是穩(wěn)定的，為更好地理解CICQ多播交換機(jī)制奠定了基礎(chǔ)。單多播輪詢調(diào)度 (MURS, multicast and unicast round robin scheduling) 策略[20]根據(jù)輪詢優(yōu)先級(jí)的不同可細(xì)分為單播優(yōu)先(MURS_uf)、多播優(yōu)先(MURS_mf)和混合輪詢(MURS_mix)算法。同IQ結(jié)構(gòu)相比較，MURS大幅提升了交換系統(tǒng)的時(shí)延和吞吐量性能?；谳敵龅墓蚕斫徊纥c(diǎn)緩存O-SMCB (output-based shared-memory crosspoint- buffered)調(diào)度機(jī)制[21]，在“可允許”均勻和“對(duì)角”多播流量到達(dá)下，O-SMCB可在節(jié)省50%的緩存條件下提供接近100%的吞吐量性能。

當(dāng)前基于CICQ構(gòu)建的多播調(diào)度策略主要集中在如何提高系統(tǒng)的吞吐量和時(shí)延性能，尚無工作著眼于單多播混合調(diào)度的公平性問題。本文在這一方面進(jìn)行了探索，提出支持單多播混合公平性的理想調(diào)度——(MUMF, mixed uni-and multicast fair scheduling) 模型，MUMF調(diào)度算法采用基于時(shí)間戳(timestamp)的調(diào)度機(jī)制，通過輸入調(diào)度和交叉點(diǎn)調(diào)度確保單多播流的公平性。針對(duì)其復(fù)雜度過高，提出了改進(jìn)調(diào)度算法 MUMF。MUMF調(diào)度算法每個(gè)輸入、輸出可獨(dú)立進(jìn)行變長分組交換，無需加速便可為流提供時(shí)延和公平性保障。本文剩余章節(jié)安排如下：第2部分是相關(guān)工作；第3部分詳細(xì)闡述了MUMF和MUMF交換機(jī)制；第4部分對(duì)MUMF調(diào)度算法的性能進(jìn)行仿真評(píng)估；第5部分是結(jié)束語。

2 相關(guān)工作

現(xiàn)有公平服務(wù)調(diào)度策略的研究主要集中在如何在共享輸出鏈路的單播競爭流之間提供公平服務(wù)，具體而言，若K條流 F = ｛ f1, f2, … ,fK｝共享輸出帶寬為 R的鏈路 L，流 fk的預(yù)約帶寬為 rk，且調(diào)度器 s根據(jù) r為每條流 f計(jì)算權(quán)重kkwk表征其歸一化需求帶寬，即。設(shè)Wk,s（t1, t2）為調(diào)度器 s下［t1, t2） 間隔內(nèi)流 fk獲得的服務(wù)量，理想的公平服務(wù)調(diào)度器 s滿足然而，受硬件處理器處理機(jī)制和分組處理系統(tǒng)特性的限制，實(shí)際調(diào)度系統(tǒng)無法達(dá)到這一目標(biāo)。最壞服務(wù)公平指數(shù)(WFI,worst-case fairness index)[22]和比例服務(wù)公平指數(shù)(PFI, proportional fairness index)[23]是衡量實(shí)際交換系統(tǒng)調(diào)度器公平性的重要指標(biāo)。用 fik表示到達(dá)交換系統(tǒng)輸入端口i的第k條多播流，目的輸出端口集合為 oik，預(yù)約帶寬為rik，Wikj,s（t1, t2）表示［t1, t2）內(nèi)調(diào)度策略s下輸出端口 j ∈oik為流fik提供的服務(wù)量，理想公平多播調(diào)度器滿足）。若

則稱交換系統(tǒng)在調(diào)度策略 s下能夠?yàn)槎嗖チ魈峁㏄FI公平性。

由于受Crossbar輸入和輸出帶寬競爭的雙重約束，基于共享鏈路的調(diào)度策略無法直接應(yīng)用到基于虛擬輸出排隊(duì)的 IQ或者 CICQ交換結(jié)構(gòu)中。MFS(multicast fair scheduling)[24]為每個(gè)輸入端口分配一份額計(jì)數(shù)器 ci記錄該端口獲得的調(diào)度份額，并為每個(gè)分組分配一到達(dá)時(shí)間戳，同時(shí)分兩級(jí)對(duì)多播進(jìn)行調(diào)度：首先輸入端口選擇具有最小虛擬時(shí)間戳的流 k : min Vik(t)作為該端口的候選流，其中，Vik(t)為端口i第k條流的虛擬時(shí)間；其次，選擇輸入端口i:進(jìn)行調(diào)度，其中，Bik為端口i第k條流的預(yù)約帶寬。MFS能夠在高負(fù)載下提供良好的公平性。CMF(credit based multicast fair schedul-ing)[25]依據(jù)預(yù)約帶寬 rij(t)為每個(gè)輸入、輸出對(duì)計(jì)算一可用份額 cij(t)和累計(jì)調(diào)度差額 Aij(t)。在Request階段選擇 Aij(t) ＞ 0 和具有最小到達(dá)時(shí)間的分組，而Grant階段選擇具有最大 Aij(t)的分組。CMF將多播分組復(fù)制為單播分組并采用逼近GPS的調(diào)度策略，獲得了較低的相對(duì)時(shí)延和公平性。

由于 IQ結(jié)構(gòu)集中式的調(diào)度機(jī)制無法構(gòu)建大規(guī)模交換系統(tǒng)，導(dǎo)致MFS和CMF在實(shí)際應(yīng)用中受到限制。此外，CICQ結(jié)構(gòu)還受到交叉點(diǎn)隊(duì)列的競爭約束，因而MFS和CMF也無法直接應(yīng)用到CICQ結(jié)構(gòu)中，然而它們?yōu)镃ICQ混合公平調(diào)度策略的設(shè)計(jì)提供了重要思路。另外，雖然針對(duì)單播調(diào)度公平性的研究成果相對(duì)較豐，然而多播分組具有多個(gè)可選目的輸出端口，必須采用適用于多播的公平調(diào)度策略和公平性評(píng)價(jià)基準(zhǔn)，且采用扇出分割和不分隔的調(diào)度策略對(duì)性能有較大影響，因而適用于單播的公平調(diào)度策略也無法直接應(yīng)用到混合調(diào)度中。下面首先介紹MUMF調(diào)度策略。

3 MUMF混合調(diào)度策略

3.1 交換系統(tǒng)模型

圖1給出了NN×規(guī)模的支持單多播混合調(diào)度的CICQ交換系統(tǒng)總體結(jié)構(gòu)。為解決分組的隊(duì)頭阻塞(HOLB, head of line blocking)問題，采用虛擬輸出隊(duì)列(VOQ, virtual output queuing)排隊(duì)機(jī)制，為單/多播分組分別維護(hù)了獨(dú)立的單/多播虛擬輸出隊(duì)列{U VQij}和{M VQim}。對(duì)于單播分組，采用N個(gè)虛擬輸出隊(duì)列可完全避免隊(duì)頭阻塞；對(duì)于多播分組，理論上需要在每個(gè)輸入端口i維護(hù)2N- N -1個(gè)MVQim隊(duì)列。為此，必須通過設(shè)計(jì)有效的分組入隊(duì)機(jī)制(QM, queuing mechanism)降低多復(fù)制端口的隊(duì)頭阻塞，在每個(gè)輸入端口維護(hù) M (M ＜2N-N-1)個(gè)MVQim隊(duì)列；經(jīng)輸入復(fù)制后進(jìn)入Crossbar的多播分組僅存在單一輸出端口，因而僅需在每個(gè)交叉點(diǎn)維護(hù)一交叉點(diǎn)單/多播虛擬輸出隊(duì)列。為防止UXBij( M XBij)溢出，為每個(gè) U XBij(M XBij)維護(hù)一流控狀態(tài)信號(hào) siuj ( simj)。假定到達(dá)各輸入的分組定長，標(biāo)記為cell。以線路速率R傳輸一個(gè)cell的時(shí)間稱為一個(gè)時(shí)隙(slot)。

3.2 理想調(diào)度模型

要實(shí)現(xiàn)單多播混合調(diào)度的短時(shí)公平性必須為輸入端口i的所有多播流｛fm｝分別維護(hù)獨(dú)立的虛ik擬多播輸出隊(duì)列并采用變長分組交換機(jī)制以逼近GPS系統(tǒng)。參考圖 1，則此時(shí)多播緩存隊(duì)列數(shù)目M = K，其中，K為端口i多播流數(shù)，因而隊(duì)列緩存維護(hù)復(fù)雜度為 O （K ）。最新研究成果表明，雖然internet骨干網(wǎng)絡(luò)同時(shí)存在的流可達(dá)幾十萬甚至上百萬，然而同時(shí)處于活動(dòng)狀態(tài)的流僅為上萬條[26]。用rikm表示到達(dá)輸入端口i的第k條多播流的預(yù)約帶寬，則去往輸出j的多播流的匯聚預(yù)約帶寬和輸入端口 i的多播流匯聚預(yù)約帶寬分別為去往輸出端口j的單播和多播業(yè)務(wù)流的累積預(yù)約帶寬為。對(duì)累積預(yù)約帶寬 r (t)進(jìn)行歸ij一化可得

圖1 MUMF交換系統(tǒng)總體結(jié)構(gòu)

且 ωij(t )滿足

為了便于描述，首先給出本文用到的以下相關(guān)術(shù)語和縮略語，如表1所示。

表1 相關(guān)符號(hào)定義

定義 1 積壓隊(duì)列(backlogged queue)稱時(shí)刻 t＞ 0 ，并稱t時(shí)刻為積壓流，記t時(shí)刻積壓流集合為 Bij（t ）。

定義 2 事件(event)稱分組到達(dá)/離去調(diào)度器 s為一次事件，用e表示，第n次事件 en發(fā)生的時(shí)刻用 tn表示，可見在 [tn, tn+1)的時(shí)間間隔內(nèi)匯聚流 fij的積壓流 Bij（t ）不變化。

可見，最壞情況下 I Si需從 N個(gè)隊(duì)頭分組中選N給定時(shí)，其復(fù)雜度 O （ lo g N ）為較小常量值。當(dāng)輸出 j確定后， I Si再從流集合 fij中選擇一單播或多帶寬，到達(dá)輸入i、去往輸出j的流歸一化匯聚帶寬為，則單多播的虛擬時(shí)間V′(t)計(jì)算為或者多播流)隊(duì)首分組的虛擬開始時(shí)間。令t時(shí)刻

其中， qijh(t)為時(shí)刻 t流 fijh對(duì)應(yīng)虛擬輸出隊(duì)列系統(tǒng)虛擬時(shí)間V′(t)且具有最小虛擬完成時(shí)間叉點(diǎn)隊(duì)列 U XBij（ M X Bij）?？梢?，I Si采用了層次化調(diào)度策略確保單多播混合調(diào)度的公平性和去往不同輸出端口分組的公平性。

3.3 MUMF交換機(jī)制

MUMF交換機(jī)制由分組入隊(duì)機(jī)制(QM)、輸入端口調(diào)度(IS)器和交叉點(diǎn)調(diào)度(CS)器構(gòu)成，其中QM調(diào)度機(jī)制將到達(dá)的多播分組根據(jù)目的端口進(jìn)行映射和入隊(duì)。下面詳細(xì)描述各模塊。

3.3.1 入隊(duì)策略(QM)

用 Q (?)表示分組入隊(duì)策略， Q (?)可描述為：給定分組c及其目的端口集合，確定c的入隊(duì)隊(duì)列{U VQij} 或{M VQim}, 其中為目的端口數(shù)。單播分組（U = 1）由于采用虛擬輸出隊(duì)列可完全避免分組的隊(duì)頭阻塞，因而即分組入隊(duì)到UVQiop。對(duì)于多播分組，若分組序列1{ p0, p1,… ,pn,…}的輸出端口數(shù)為U(U≥ 2 )，則理論上需要在每個(gè)輸入端口維護(hù) CUN個(gè) M VQim隊(duì)列；而對(duì)于給定最大輸出端口數(shù) Umax的分組序列{ p0, p1,… ,pn,…}，要完全避免隊(duì)頭阻塞問題，理論上需要在每個(gè)輸入端口維護(hù)個(gè)MVQim隊(duì)列，實(shí)現(xiàn)起來過于復(fù)雜。為此必須設(shè)計(jì)有效入隊(duì)機(jī)制降低隊(duì)頭阻塞概率，本文采用最小覆蓋調(diào)度(MCD, minimum cover dispatching)算法。RN的求和向量，稱向量序列為的一個(gè)覆蓋，xj= 0 或者1，若滿足：

其中，“⊕”為異或算子。可以看出，N維求和向量是自身的一個(gè)覆蓋。最小均衡覆蓋。

首先假設(shè)輸入端口i維護(hù)的 M VQim隊(duì)列數(shù)目為M, MCD算法工作過程如下。

2) 根據(jù)新到達(dá)分組p的目的端口集合 Op將其表達(dá)成分組標(biāo)識(shí)向量其中xj=1，若 j ∈Op，否則xj=0。

3) 將分組 p按照如下規(guī)則入隊(duì)到第 mo個(gè)多播虛擬輸出隊(duì)列 M VQimo：

確保不同輸出端口間流的公平性，I Si為匯聚流 fij，按照式(13)計(jì)算調(diào)度更新份額 σij( t )：

在每次調(diào)度時(shí)， I Si首先更新累積調(diào)度份額：端口j的多播隊(duì)頭分組集合，記依據(jù)隊(duì)頭分組集合索引結(jié)果為。 I Si輸入調(diào)度過程如算法1所示。

算法1 MUMF輸入調(diào)度過程

ISi調(diào)度過程

記 I Si選擇分組為p，｝。若p為單播則根據(jù)目的端口傳輸?shù)浇徊纥c(diǎn)隊(duì)列 U XBij，更新；否則，根據(jù)扇出集合 op復(fù)制到并更新

3.3.3 交叉點(diǎn)調(diào)度(CS)

MUMF交叉點(diǎn)調(diào)度根據(jù)單播累積份額 Wiju(t)、Wij(t)和多播累積份額 Wijm(t)、Wij(t)從集合 X Bj選擇交叉點(diǎn)隊(duì)列。同理記輸出j對(duì)應(yīng)的交叉點(diǎn)調(diào)度器為 C Sj。記輸出端口 j對(duì)應(yīng)的單播累積份額多播累積份額降序排列后對(duì)應(yīng)的索引，為對(duì)降序排列后隊(duì)長， limj(t)為t時(shí)刻多播交叉隊(duì)列的隊(duì)長。調(diào)度器ISi首先根據(jù) Wju(t)和 Wjm(t)確定單多播流調(diào)度的公平性，再根據(jù) φ ′和 φ ′確定各輸入端口間的公平性，如算法2所示。

算法2 MUMF交叉點(diǎn)調(diào)度過程

CSj調(diào)度過程

可見，MUMF交叉點(diǎn)調(diào)度首先選擇至當(dāng)前時(shí)刻t單多播業(yè)務(wù)已獲得的服務(wù)和預(yù)約服務(wù)之間的差額(Wju(t)和 Wjm(t))中的較大者對(duì)應(yīng)的業(yè)務(wù)類型(說明該類業(yè)務(wù)類型與預(yù)約帶寬之間的差距更大)，然后再從對(duì)應(yīng)業(yè)務(wù)類型中選取具有最大累積份額(Wiju(t)或 Wijm(t))的單/多播分組。

4 仿真實(shí)驗(yàn)

本節(jié)從時(shí)延、帶寬分配的公平性和吞吐量3個(gè)方面對(duì) MUMF算法的性能進(jìn)行仿真評(píng)估。實(shí)驗(yàn)采用 C++開發(fā)的交換系統(tǒng)性能仿真評(píng)估系統(tǒng)(SPES,switching performance evaluation system)[27]。SPES仿真實(shí)驗(yàn)環(huán)境配置如下：交換結(jié)構(gòu)的規(guī)模為16×16；輸入、輸出端口的帶寬歸一化為1；流量到達(dá)過程采用貝努利(Bernoulli)和突發(fā)(burst) 2種業(yè)務(wù)源[27]；流量分布模型采用均勻業(yè)務(wù)流分布模型。用λi標(biāo)識(shí)輸入端口i的流量到達(dá)強(qiáng)度，且?i , j,λi= λj， 單 多 播 業(yè) 務(wù) 比 例 分 別 為 α 和β（α + β=1）。假設(shè)每個(gè)單播分組具有相同的扇出分割數(shù)Φ，本文僅研究“可允許”到達(dá)過程，即

記λ= λi（α+ Φβ），用λij表示到達(dá)輸入端口i、去往輸出端口j的流量速率，則對(duì)于均勻流量到達(dá)分布：，且單播和多播混合下的到達(dá)速率和為

4.1 時(shí)延性能

本節(jié)分2種情形分析MUMF調(diào)度算法的時(shí)延性能：情形1)，單多播流量混合下MUMF調(diào)度算法的時(shí)延性能，設(shè)置扇出端口為 4，單多播流量比例4αβ=，改變?chǔ)耸蛊鋸?.1~1.0之間變化考察單多播分組平均時(shí)延大??；情形2)，單多播業(yè)務(wù)混合條件下MUMF調(diào)度算法的時(shí)延性能，設(shè)置扇出端口為4，考察在不同單多播流量比例αβ下，改變?chǔ)耸蛊鋸?.1~1.0之間變化考察單多播分組平均時(shí)延大小。

圖2給出了情形1)流量到達(dá)下MUMF調(diào)度算法的時(shí)延性能仿真結(jié)果?？梢钥闯?，與MURS_mix相比較MUMF調(diào)度算法的性能更優(yōu)。圖3給出了情形2)流量到達(dá)下，多播比例分別為10%、20%和30%時(shí)MUMF調(diào)度算法的平均時(shí)延性能?？梢姡S著多播流量比例的增加，單多播分組的平均時(shí)延不斷增大，這是由于多播流量增加相應(yīng)增大了隊(duì)頭分組阻塞的概率。

圖2 情形1)混合流量到達(dá)下分組的平均時(shí)延性能

圖3 情形2)混合流量到達(dá)下分組的平均時(shí)延性能

4.2 公平性能

公平性能評(píng)估采用Bernoulli和突發(fā)2種流量模型，為了便于分析，采用4×4規(guī)模的交換結(jié)構(gòu)，設(shè)置每個(gè)多播分組的扇出端口數(shù)為 4，即每個(gè)多播分組產(chǎn)生4個(gè)輸出端口。分2種情形進(jìn)行評(píng)估：

情形2)，單多播比例αβ=1，預(yù)約帶寬

首先考察情形1)流量到達(dá)下MUMF調(diào)度算法的公平性能仿真結(jié)果，如圖4所示。圖4分別給出了 Bernoulli和突發(fā)業(yè)務(wù)源下各輸入端口獲得輸出端口1的調(diào)度帶寬，其中， Wiju(Wijm

)分別表示輸入端口 i接受輸出端口 j提供的實(shí)際單播(多播)服務(wù)量。可以看出，無論是在Bernoulli還是突發(fā)業(yè)務(wù)流量到達(dá)下，各輸入端口多播均獲得正比于預(yù)約帶寬的實(shí)際帶寬。

圖4 情形1)Bernoulli業(yè)務(wù)源下公平性能仿真結(jié)果

其次，考察情形2)下MUMF調(diào)度算法的公平性能仿真結(jié)果，由于篇幅限制這里僅給出Bernoulli業(yè)務(wù)流到達(dá)下仿真結(jié)果，如圖5所示。圖5分別為Bernoulli單多播公平性能仿真結(jié)果，同樣考察各輸入端口獲得輸出端口1的實(shí)際帶寬。對(duì)于單播業(yè)務(wù)，由于其預(yù)約帶寬總和為 0.5，而到達(dá)輸出端口 1的單播流量總和為 0.5，因而所有單播分組都被調(diào)度輸出。

由于輸出端口1為所有的多播分組預(yù)留了0.5的預(yù)約帶寬，且在負(fù)載為0.125時(shí)達(dá)到飽和負(fù)載，因而從0.125開始各多播流受到帶寬公平性限制，最終穩(wěn)定到預(yù)約帶寬大小。

4.3 吞吐量性能

采用Bernoulli業(yè)務(wù)源進(jìn)行吞吐量評(píng)估，多播扇出端口數(shù)為4，單多播流量比例4αβ=，改變?chǔ)耸蛊鋸?.1至1.0之間變化。圖6給出了Bernoulli到達(dá)下 MUMF調(diào)度算法的吞吐量性能仿真結(jié)果?？梢钥闯?，MUMF調(diào)度算法的吞吐量隨到達(dá)強(qiáng)度的增加而增加，最后達(dá)到接近100%的吞吐量。

圖6 Bernoulli業(yè)務(wù)源下MUMF調(diào)度算法的吞吐量性能仿真結(jié)果

4.4 QM入隊(duì)機(jī)制

本節(jié)通過設(shè)定不同的輸出端口隊(duì)列數(shù)評(píng)估入隊(duì)機(jī)制QM的性能，QM入隊(duì)性能采用交換系統(tǒng)的平均時(shí)延進(jìn)行衡量，并設(shè)定3種不同情形對(duì)QM的性能進(jìn)行評(píng)估：①每個(gè)輸入端口維護(hù)4個(gè)多播虛擬輸出隊(duì)列；②每個(gè)輸入端口維護(hù)8個(gè)多播虛擬輸出隊(duì)列；③每個(gè)輸入端口維護(hù) 16個(gè)多播虛擬輸出隊(duì)列。采用Bernoulli流量到達(dá)過程，多播扇出端口數(shù)為4，單多播流量比例4αβ=，改變?chǔ)耸蛊鋸?.1~1.0間變化。圖7給出了Bernoulli均勻流量到達(dá)下 MUMF調(diào)度算法的時(shí)延性能?？梢钥闯觯S著多播隊(duì)列數(shù)目的不斷增加 MUMF的時(shí)延性能不斷改善，然而改善幅度變小。

圖7 Bernoulli均勻流量到達(dá)下，MUMF調(diào)度算法的時(shí)延性能

5 結(jié)束語

以視頻點(diǎn)播、VoIP等為特征的多媒體業(yè)務(wù)及相關(guān)技術(shù)成為下一代互聯(lián)網(wǎng)和三網(wǎng)融合下業(yè)務(wù)發(fā)展的典型特征。多播技術(shù)為多媒體業(yè)務(wù)的運(yùn)營提供了重要支撐?；诼?lián)合輸入交叉點(diǎn)排隊(duì)交換結(jié)構(gòu)，本文首先討論了 CICQ下單多播混合調(diào)度的理論模型，基于理論模型給出了一種逼近調(diào)度算法MUMF。仿真結(jié)果表明 MUMF調(diào)度算法具有良好的性能。依托于這一思想，后期將在支持區(qū)分服務(wù)方面進(jìn)行深入研究。

[1] SHEN Y, PANWAR S S, CHAO H J. SQUID: A practical 100%throughput scheduler for crosspoint buffered switches[J]. IEEE/ACM Transactions on Networking, 2010, 18(4):1119-1131.

[2] PAN D, YANG Y Y. Localized independent packet scheduling for buffered crossbar switches[J]. IEEE Transaction on Computers, 2009,58(2):260-274.

[3] NABESHIMA M. Performance evaluation of a combined inputand crosspoint-queued switch[J]. IEICE Trans on Commun, 2000,83(3):737-741.

[4] ROJAS-CESSA R, OKI E, JING Z, et al. On the combined input crosspoint buffered switch with round-robin arbitration[J]. IEEE Trans on Commun, 2005, 53(11):1945-1951.

[5] MHAMDI L, HAMDI M. MCBF: A high-performance scheduling algorithm for buffered crossbar switches[J]. IEEE Communications Letters, 2003, 7(9):451-453.

[6] ZHANG X, BHUYAN L N. An efficient algorithm for combined input-crosspoint-queued (CICQ) switches[A]. IEEE GlobeCOM[C].2004.1168-1173.

[7] JAVIDI T, MAGILL R, HRABIK T. A high-throughput scheduling algorithm for a buffered crossbar switch fabric[A]. IEEE ICC[C].2001.1586-1591.

[8] PAN D, YANG Y Y. Localized independent packet scheduling for buffered crossbar switches[J]. IEEE Transaction on Computers, 2009,58(2): 260-274.

[9] CHANG C S, HSU Y H, CHENG J, et al. A dynamic frame sizing algorithm for CICQ switches with 100% throughput[A]. IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil, 2009. 738-746.

[10] SHEN Y, PANWAR S S, CHAO H J. SQUID: A practical 100%throughput scheduler for crosspoint buffered switches[J]. IEEE/ACM Transactions on Networking, 2008, (99):1119-1131.

[11] MAGILL B, ROHRS C, STEVENSON R. Output-queued switch emulation by fabrics with limited memory[J]. IEEE Journal on Selected Areas in Communications, 2003, 21 (4):606-615.

[12] CHUANG S T, IYER S, MCKEOWN N. Practical algorithms for performance guarantees in buffered crossbars[A]. IEEE INFOCOM[C].Miami, 2005. 981- 991.

[13] TURNER J. Strong performance guarantees for asynchronous crossbar schedulers[J]. IEEE/ACM Transactions on Networking, 2009,17(4):1017-1028.

[14] ZHANG X, et al. Adaptive max-min fair scheduling in buffered crossbar switches without speedup[A]. IEEE INFOCOM[C]. Anchorage, Alaska, 2007. 454-462.

[15] HE S M, SUN S T, GUAN H T, et al. On guaranteed smooth switching for buffered crossbar switches[J]. IEEE/ACM Transactions on Networking, 2008, 16(3):718-731.

[16] PAN D, YANG Z Y, MAKKI K, et al. Providing performance guarantees for buffered crossbar switches without speedup[A]. ICST QShine[C]. Berlin, 2009.297-314.

[17] GIACCONE P, LEONARDI E. Asymptotic performance limits of switches with buffered crossbars supporting multicast traffic[J]. IEEE Trans on Information Theory, 2008, 54(2):595-607.

[18] SUN S T, HE S M, ZHENG Y F, et al. Multicast scheduling in buffered crossbar switches with multiple input queue[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20(6):818-830.

[19] MHAMDI L. On the integration of unicast and multicast cell scheduling in buffered crossbar switches[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20(6):818-830.

[20] DONG Z Q, ROJAS-CESSA R. Output-based shared-memory crosspoint-buffered packet switch for multicast services[J]. IEEE Communication letters, 2007, 11(12): 1001-1003.

[21] BENNETT J C R, ZHANG H. WF2Q: Worst-case fair weighted fair queuing[A]. IEEE INFOCOM[C]. 1996.120-128.

[22] GOLESTANI S. A self-clocked fair queuing scheme for broadband applications[A]. IEEE INFOCOM[C]. 1994.636-646.

[23] NI N, BHUYAN L N. Fair scheduling for input buffered switches[J].Journal of Cluster Computing, 2003, 6(2):105-114.

[24] PAN D, YANG Y Y. Bandwidth guaranteed multicast scheduling for virtual output queued packet switches[J]. Journal of Parallel and Distributed Computing, 2009, 69(12): 939-949.

[25] HU C, TANG Y, CHEN X, LIU B. Per-flow queuing by dynamic queue sharing[A]. IEEE INFOCOM’07[C]. Anchorage, Alaska,2007.

[26] HU H C, YI P, GUO Y F. Design and implementation of high performance simulation platform for switching and scheduling[J]. Journal of Software, 2008, 19(4):1036-1050.