CLOS網(wǎng)絡(luò)可重排算法研究.pdf

1、配線架是網(wǎng)絡(luò)及信息系統(tǒng)最基礎(chǔ)的部分，其核心功能模塊——開關(guān)網(wǎng)絡(luò)的處理連接請(qǐng)求的能力決定了整個(gè)網(wǎng)絡(luò)的性能。如果開關(guān)網(wǎng)絡(luò)能夠很好的處理多個(gè)連接請(qǐng)求，并使這些請(qǐng)求不發(fā)生沖突，那么整個(gè)網(wǎng)絡(luò)的丟失請(qǐng)求率將會(huì)大大降低，網(wǎng)絡(luò)性能也比較好。如果開關(guān)網(wǎng)絡(luò)對(duì)于多個(gè)連接請(qǐng)求不能很好的處理，及時(shí)有效的為其尋找到正確的路由，那么網(wǎng)絡(luò)就會(huì)總是處于阻塞的狀態(tài)，網(wǎng)絡(luò)性能大大降低，將影響網(wǎng)絡(luò)用戶的使用。
　　從開關(guān)網(wǎng)絡(luò)的阻塞特性來(lái)看，一般將開關(guān)網(wǎng)絡(luò)分為無(wú)阻塞網(wǎng)絡(luò)和

2、有阻塞網(wǎng)絡(luò)。無(wú)阻塞網(wǎng)絡(luò)又可以分為三種：嚴(yán)格不阻塞網(wǎng)絡(luò)，廣義不阻塞網(wǎng)絡(luò)和可重排不阻塞網(wǎng)絡(luò)。嚴(yán)格不阻塞網(wǎng)絡(luò)對(duì)于網(wǎng)絡(luò)硬件的要求比較高，在工程上不利于實(shí)現(xiàn)。廣義不阻塞網(wǎng)絡(luò)目前研究尚少?？芍嘏挪蛔枞W(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)的要求不高，利于實(shí)現(xiàn)，網(wǎng)絡(luò)不阻塞的關(guān)鍵是其路由算法。衡量有阻塞網(wǎng)絡(luò)性能的指標(biāo)是阻塞概率。
　　本文選取 CLOS網(wǎng)絡(luò)為研究背景，仔細(xì)研究了歷年來(lái)國(guó)際上提出的各種可重排不阻塞算法，并在此基礎(chǔ)上提出了兩種重排算法：即阻塞即重排算法和可降低連

3、接阻塞概率的重排算法。即阻塞即重排算法改進(jìn)了以往的存在多條阻塞連接再重新路由的方法，提出一旦連接請(qǐng)求發(fā)生阻塞立即重排的思路，縮減了為調(diào)用重排算法而人為加入連接的過(guò)程，大大提高了算法的效率。并且算法被理論證明了具有收斂性。可降低連接阻塞概率的重排算法是將重排的概念引入有阻塞網(wǎng)絡(luò)中，在為某請(qǐng)求建立路由的同時(shí)，預(yù)測(cè)出此連接是否會(huì)對(duì)后面的連接請(qǐng)求產(chǎn)生影響，即阻塞概率是否為0。如果答案是肯定的，那么調(diào)用重排算法，改動(dòng)已經(jīng)建立的連接方式，使阻塞概率

4、降低。
　　文章首先簡(jiǎn)單的介紹了研究的相關(guān)背景：配線架，開關(guān)網(wǎng)絡(luò)和CLOS網(wǎng)絡(luò)。接著討論了CLOS網(wǎng)絡(luò)的阻塞和不阻塞特性，一些相關(guān)的算法，還提出了阻塞概率的計(jì)算方法，為第五章的可降低連接阻塞概率的重排算法做了一定的鋪墊。然后詳細(xì)的介紹了國(guó)際上比較先進(jìn)的四種可重排算法。
　　本文提出的即阻塞即重排算法改進(jìn)了傳統(tǒng)的可重排算法中對(duì)連接說(shuō)明矩陣進(jìn)行操作的做法，提出了集合矩陣的概念，對(duì)集合矩陣的操作更能直觀的表現(xiàn)網(wǎng)絡(luò)的連接方式。集合矩