網(wǎng)絡(luò)容錯(cuò)性和通信延遲度量參數(shù)的研究及應(yīng)用.pdf

1、一個(gè)圖G的直徑是G的所有點(diǎn)對(duì)間距離的最大值.當(dāng)一個(gè)網(wǎng)絡(luò)被模型化為一個(gè)圖時(shí)(處理器看作結(jié)點(diǎn),處理器之間的連線看作結(jié)點(diǎn)間的邊),直徑是最大傳輸延遲的度量.而涉及圖G中兩點(diǎn)間w條內(nèi)部不相交的路徑的G的w-直徑是G的直徑的推廣.它起源于并行結(jié)構(gòu)和分布計(jì)算網(wǎng)絡(luò)中對(duì)路由、可靠性、隨機(jī)路由和其他通訊協(xié)議的研究,是圖的直徑的自然推廣,注重實(shí)際應(yīng)用.論文首先討論了一類具體網(wǎng)絡(luò)——廣義超立方體網(wǎng)絡(luò)的寬直徑.給出了確定該網(wǎng)絡(luò)寬直徑的兩種證明方法.同時(shí)在原搜尋

2、算法思想的基礎(chǔ)上給出并實(shí)現(xiàn)了兩種具體的搜尋并行路徑的方法(一種基于拓?fù)浣Y(jié)構(gòu)特性,一種基于結(jié)點(diǎn)的編碼),該方法思想簡明、易于應(yīng)用,具有一定的通用性.其次,論文在邊不交的前提下,定義了一個(gè)圖的一個(gè)新參數(shù)——入-直徑.該參數(shù)不但能度量圖的容錯(cuò)性和通信延遲,而且能反映網(wǎng)絡(luò)"瓶頸"的某種信息.它實(shí)際上是圖的w-直徑在某種意義上的推廣.論文還討論了入-直徑的性質(zhì),給出了一個(gè)求入-直徑的算法.論文還對(duì)網(wǎng)絡(luò)在通訊中出現(xiàn)的各種各樣的"瓶頸"問題提出了一種