第三部分(交換2)

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

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

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