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

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

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

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

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