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

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

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

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

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