帶時(shí)限的輸入隊(duì)列交換機(jī)實(shí)時(shí)調(diào)度.pdf

1、近年來，隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，交換機(jī)的結(jié)構(gòu)正在經(jīng)歷著巨大的變化。早期的OQ(Output-Queued，輸出隊(duì)列)結(jié)構(gòu)：優(yōu)點(diǎn)是能夠提供最優(yōu)的吞吐量和延時(shí)控制，但是帶來了交換結(jié)構(gòu)的內(nèi)部帶寬和輸出隊(duì)列的存儲器訪問速率必須是輸入端口鏈路速率的N倍的缺點(diǎn)。后來的IQ(Input-Queued，輸入隊(duì)列)結(jié)構(gòu)：優(yōu)點(diǎn)是克服了OQ結(jié)構(gòu)的缺點(diǎn)，不需要加速比，但是出現(xiàn)了HOL(Head of Line blocking，隊(duì)頭阻塞)的問題。
　　

2、 由于傳統(tǒng)的輸出隊(duì)列交換結(jié)構(gòu)具有較差的可擴(kuò)展性，所以輸入隊(duì)列(IQ)交換結(jié)構(gòu)又重新進(jìn)入了人們的視線，并且得到了越來越廣泛的使用。在IQ交換機(jī)中采用VOQ(Virtual output queued，虛擬輸出隊(duì)列)緩存來解決HOL問題。現(xiàn)在越來越多的輸入隊(duì)列交換機(jī)結(jié)構(gòu)的調(diào)度算法都會遇到時(shí)限保障的問題，所以人們需要設(shè)計(jì)好的算法來保證數(shù)據(jù)傳輸滿足它相應(yīng)的時(shí)限。這就是基于時(shí)限的輸入隊(duì)列分組調(diào)度的問題。由于時(shí)限保障意味著吞吐量和速度的保障，所以這

3、個(gè)問題也一直是時(shí)分多址調(diào)度，優(yōu)化網(wǎng)絡(luò)調(diào)度和實(shí)時(shí)調(diào)度的研究熱點(diǎn)和難點(diǎn)。
　　 對于帶時(shí)限的輸入隊(duì)列分組調(diào)度問題，人們設(shè)計(jì)了不同的算法。其中一種是Birkhoff-Von Neumann算法，但是這種算法要求所有的流量擁有一個(gè)共同的時(shí)限并且不過載。后來，又提出了最早時(shí)限優(yōu)先(EDF)調(diào)度，最小松馳度優(yōu)先(MLF)調(diào)度等方法來解決流量具有多個(gè)時(shí)限的問題。最近，通過改進(jìn)，一種基于非EDF的算法被提出，叫做基于流的迭代分組調(diào)度(FIPS)

4、。這種算法可以產(chǎn)生比EDF算法更高的吞吐量。
　　 本文主要研究帶時(shí)限的輸入隊(duì)列交換機(jī)中加權(quán)的實(shí)時(shí)調(diào)度問題。主要研究內(nèi)容如下：
　　 (1)結(jié)合NPC問題的基本理論和歸約的定義，給出了NPC問題的證明方法，進(jìn)而證明了在一個(gè)帶時(shí)限帶權(quán)重的輸入隊(duì)列交換機(jī)實(shí)時(shí)調(diào)度中，如果有兩個(gè)時(shí)限類，第一類流量不過載，總的流量過載，調(diào)度最大權(quán)重流量的問題是一個(gè)NPC問題。
　　 (2)在證明了這樣的一個(gè)問題是NPC問題后，下一步就要找

5、到一個(gè)近似算法來解決這個(gè)問題，在這里，我們選擇了貪心算法。首先給出了交換機(jī)實(shí)時(shí)調(diào)度問題的貪心算法，然后根據(jù)線性規(guī)劃的基本知識及交換機(jī)實(shí)時(shí)調(diào)度的一些性質(zhì)，建立交換機(jī)實(shí)時(shí)調(diào)度問題的線性規(guī)劃模型，對其進(jìn)行性能分析，最后得出兩個(gè)重要的結(jié)論：1.交換機(jī)實(shí)時(shí)調(diào)度的貪心算法是1/3-OPT的；2.貪心算法1/3-OPT的性能界是緊。
　　 (3)對貪心算法進(jìn)行仿真，將得出的數(shù)據(jù)用圖表進(jìn)行分析，得出分析結(jié)果：1。在負(fù)荷較低的情況下，貪心算法調(diào)度