第三部分(交換2)

基于入端口緩存的隊(duì)列調(diào)度交換結(jié)構(gòu)一般采用定長(zhǎng)交換技術(shù)，變長(zhǎng)分組（如IP包）需要在入端口被分成多個(gè)固定長(zhǎng)度的信元（cell），然后在出端口進(jìn)行重組；初期對(duì)交換結(jié)構(gòu)容量的需求在幾百M(fèi)b/s~Gb/s數(shù)量級(jí)。此時(shí)，OQ結(jié)構(gòu)相對(duì)于共享緩存、IQ結(jié)構(gòu)在吞吐率、時(shí)延等方面有較大優(yōu)勢(shì)；隨著交換容量的迅速提高（線速、端口數(shù)量），OQ結(jié)構(gòu)緩存的存取速率成為瓶頸；為了構(gòu)建大規(guī)模、高速交換結(jié)構(gòu)，IQ、CIOQ交換結(jié)構(gòu)及其調(diào)度方法再次成為人們研究的重點(diǎn)；為了消除HOL現(xiàn)象，一般采用VOQ結(jié)構(gòu)?？偣灿蠳2個(gè)FIFO，到達(dá)入端口i去往出端口j的分組被存儲(chǔ)在VOQi,j中；在每個(gè)時(shí)隙，位于各隊(duì)列的第一個(gè)分組有機(jī)會(huì)被選中發(fā)往其目的輸出端，但每個(gè)入端口的N個(gè)隊(duì)列最多只能有一個(gè)分組被選中；如果各輸入端的分組到達(dá)率相同，且等概率地發(fā)往各輸出端，就稱這種到達(dá)業(yè)務(wù)服從均勻分布。吞吐量（throughput）和時(shí)延（delay）是分析交換結(jié)構(gòu)性能的重要參數(shù)；吞吐量是指，在一個(gè)時(shí)隙周期，交換結(jié)構(gòu)傳輸?shù)姆纸M總數(shù)；時(shí)延是指，一個(gè)分組從到達(dá)到離開所需要的時(shí)間；如果各等待隊(duì)列的長(zhǎng)度是有限的，則稱交換結(jié)構(gòu)是穩(wěn)定的。為了使交換結(jié)構(gòu)工作在穩(wěn)定狀態(tài)，并具有較好的網(wǎng)絡(luò)性能，隊(duì)列的調(diào)度算法（schedulingalgorithms）起關(guān)鍵作用；調(diào)度算法可用匹配圖加以說(shuō)明，如下圖所示。圖中左右兩邊的節(jié)點(diǎn)分別代表輸入、輸出端口，各條邊表示相關(guān)入口有分組要發(fā)往對(duì)應(yīng)的出口；調(diào)度器的作用：從最多N2條邊中選出一組邊（匹配），使一個(gè)入端口最多只與一個(gè)出端口相連，同時(shí)一個(gè)出端口最多只與一個(gè)入端口相連；匹配結(jié)果可用矩陣表示為：M=(Mi,j)，i,j≤N，當(dāng)入端口i與出端口j匹配后，對(duì)應(yīng)元素Mi,j=1；一個(gè)簡(jiǎn)單的例子如下圖所示。選擇調(diào)度算法需考慮的因素：效率：在一個(gè)時(shí)隙周期能實(shí)現(xiàn)較多的“輸入-輸出”匹配，以獲得較高的吞吐量以及較低的時(shí)延；公平性：需避免部分隊(duì)列長(zhǎng)期得不到服務(wù)的現(xiàn)象；穩(wěn)定性：對(duì)于可能出現(xiàn)的任何業(yè)務(wù)模型，隊(duì)列長(zhǎng)度均是有限的；低復(fù)雜度：算法運(yùn)算耗費(fèi)的時(shí)間需較短，否則會(huì)限制交換結(jié)構(gòu)的線速。最大極限匹配（MaximumMatching）最大權(quán)重匹配（MWM：MaximumWeightMatching）在匹配圖中，首先給各條邊賦予不同的權(quán)值，以代表該VOQ隊(duì)列的優(yōu)先程度（它可以代表隊(duì)列長(zhǎng)度，等）；對(duì)于連接入端i到出端j的邊ei,j，設(shè)wi,j為其權(quán)值，則實(shí)現(xiàn)MWM的目標(biāo)就是使最大。如下圖所示：復(fù)雜度較高（N3），對(duì)于速率較高的大規(guī)模分組交換結(jié)構(gòu)，實(shí)現(xiàn)難度大；較典型的算法有LQF（longestqueuefirst）、OCF（oldestcellfirst）；LQF算法以等待隊(duì)列的長(zhǎng)度為權(quán)值，但可能使部分業(yè)務(wù)量較少的隊(duì)列長(zhǎng)期得不到服務(wù)；OCF算法則以各隊(duì)列第一個(gè)分組的等待時(shí)間為權(quán)值。B.最大規(guī)模匹配（MSM：MaximumSizeMatching）以獲得最多“匹配對(duì)”為目標(biāo)；是MWM的特例（當(dāng)各條邊的權(quán)值均為1時(shí)）；前例的MSM算法結(jié)果如下圖所示。最大匹配（MaximalMatching）在添加新匹配對(duì)時(shí)，不刪除已確定的配對(duì)，簡(jiǎn)化匹配過(guò)程（復(fù)雜度較低）；如果一個(gè)非空的入端口在一個(gè)匹配周期未實(shí)現(xiàn)匹配，其目的端口一定與其它入端口已經(jīng)匹配；一般地，能成功配對(duì)的數(shù)量少于最大極限匹配的情況。A.并行迭代匹配（PIM：ParallelIterativeMatching）在每個(gè)時(shí)隙周期最多可以有N次迭代過(guò)程。在每個(gè)匹配周期開始時(shí)，全部輸入端、輸出端均為未匹配狀態(tài)；只有未實(shí)現(xiàn)匹配的輸入端、輸出端才能參與新一輪的匹配；每次迭代，全部輸入、輸出端并行執(zhí)行3個(gè)步驟：請(qǐng)求（Request）、同意（Grant）、接受（Accept）。

請(qǐng)求：每個(gè)未匹配的輸入端向其全部目的輸出端發(fā)出請(qǐng)求；同意：如果一輸出端收到多個(gè)請(qǐng)求，就從中任意選擇一個(gè)，每個(gè)請(qǐng)求獲得“同意”的概率相等；接受：如果一個(gè)輸入端同時(shí)收到多個(gè)“同意”回復(fù)，就從中確認(rèn)一個(gè)，并將確認(rèn)信息告訴對(duì)應(yīng)的輸出端。PIM的一次迭代過(guò)程如下圖所示。當(dāng)業(yè)務(wù)為均勻分布時(shí)，一次PIM迭代后的吞吐率約為63%。假設(shè)N×N交換結(jié)構(gòu)的全部VOQ非空，那么每個(gè)輸出端口會(huì)同時(shí)收到N個(gè)請(qǐng)求，依據(jù)PIM原則，每個(gè)請(qǐng)求被同意的概率是1/N。那么，一個(gè)入端口未收到“同意”的概率就是

。當(dāng)業(yè)務(wù)為均勻分布時(shí)，N次PIM迭代后的吞吐率為100%。業(yè)務(wù)較重時(shí)，PIM可能引起不同連接間的不公平性。迭代輪循匹配（iRRM：IterativeRound-RobinMatching）工作方式與PIM相似，每次迭代包含3個(gè)步驟：請(qǐng)求（Request）、同意（Grant）、接受（Accept）；與PIM的不同之處在于，收端、發(fā)端不再采取隨機(jī)的方式選擇端口，而是采用輪循的方式，為此，在收端與發(fā)端，分別有一指針（入端口為ai，出端口為gj）指向最高優(yōu)先級(jí)端口，每完成一次選擇，指針值加1。工作示例如下圖所示，假設(shè)ai、gj的初始值均為1。iRRM相對(duì)于PIM具有較好的公平性；一次迭代后，iRRM的吞吐率與PIM相同；iRRM存在輸出端同步現(xiàn)象，會(huì)使其一次迭代吞吐率下降。入端口i的VOQ均為非空；各出端口指針值相同，均為i。一次迭代只有一對(duì)端口完成匹配，而且下一輪迭代時(shí)，所有出端口指針值仍相同。iSLIP為了解決iRRM輸出端口的同步現(xiàn)象；每次迭代同樣包含3個(gè)步驟：請(qǐng)求（Request）、同意（Grant）、接受（Accept）；與iRRM的不同之處在于，只有當(dāng)發(fā)端確認(rèn)后，收端指針才進(jìn)行更新，而且收端、發(fā)端指針只在第一次迭代時(shí)才進(jìn)行更新，其余N-1次迭代均不更新，避免出現(xiàn)部分VOQ隊(duì)列長(zhǎng)期得不到服務(wù)的現(xiàn)象（starvation）；單個(gè)VOQ等待服務(wù)的時(shí)間不超過(guò)2N個(gè)時(shí)隙。iSLIP的一次迭代過(guò)程如下圖所示。Starva