第7章-互聯(lián)網(wǎng)絡-資料下載頁
2025-08-16 01:02本頁面
【正文】 P2→P3 P0→P1 應用需求 t P2→P3 P0→P1 SIMD互連 t P2→P3 P0→P1 MIMD互連 控制方式： 采用分布控制方式，即各 NIC或交換開關(guān)只根據(jù)消息的源和目的地址控制本身的狀態(tài) (不能影響已連接的通道 )。 拓撲結(jié)構(gòu)： 拓撲結(jié)構(gòu)不影響互連函數(shù)的實現(xiàn)，只影響互連函數(shù)實現(xiàn)的效率或性能。 第三節(jié) 消息傳遞機制 一、消息尋徑方式與傳輸性能 線路交換 面向連接 傳遞消息前，先建立源到目的結(jié)點的物理通路。 T N1 N2 N3 N4 消息 1 消息 2 D 說明：本圖傳輸時忽略了鏈路時延。 網(wǎng)絡時延： Tcs(n,d)=dnt/b+n/b≈ n/b，其中 ntn 尋徑阻塞處理： 放棄尋徑消息 nt，等待通道空閑時重發(fā)。 回下頁 包交換 面向無連接 （ 1）存儲 轉(zhuǎn)發(fā)尋徑 整個數(shù)據(jù)包到達中間結(jié)點后，再尋徑和轉(zhuǎn)發(fā)。 R T N1 N2 N3 N4 數(shù)據(jù)包 1 數(shù)據(jù)包 2 D 網(wǎng)絡時延： Tsf(n’,d)=dnt/b+dn’/b=d(nt+n’)/b 對單個消息，存儲 轉(zhuǎn)發(fā)比線路交換 時延大 ； 對整個網(wǎng)絡，存儲 轉(zhuǎn)發(fā)比線路交換 利用率高 。 尋徑阻塞處理： 中間結(jié)點需要緩沖整個數(shù)據(jù)包，等待通道空閑時轉(zhuǎn)發(fā)。 轉(zhuǎn)上頁 回下頁 （ 2）虛擬直通尋徑 包的尋徑頭部到達中間結(jié)點后即可尋徑、傳輸。 T N1 N2 N3 N4 數(shù)據(jù)包 1 D 網(wǎng)絡時延： Tvd(n’,d)=dnt/b+n’/b≈ n’/b 網(wǎng)絡狀態(tài)較好時，虛擬直通與線路交換時延相當； 網(wǎng)絡狀態(tài)不好時，虛擬直通與存儲 轉(zhuǎn)時延相當。 尋徑阻塞處理： 中間結(jié)點需要緩沖幾個數(shù)據(jù)片 (最多為整個數(shù)據(jù)包 )，等待通道空閑時轉(zhuǎn)發(fā)。 轉(zhuǎn)上頁 回下頁 （ 3）蟲孔尋徑 將數(shù)據(jù)包分成很小的數(shù)據(jù)片，各片以流水方式傳輸。 轉(zhuǎn)上頁 T N1 N2 N3 N4 數(shù)據(jù)包 1 數(shù)據(jù)包 2 D 網(wǎng)絡時延： Twh(n’,d)=dnt/b+n’/b≈ n’/b 網(wǎng)絡狀態(tài)較好時，蟲孔尋徑與線路交換時延相當； 網(wǎng)絡狀態(tài)不好時，蟲孔尋徑不如存儲 轉(zhuǎn)時延。 尋徑阻塞處理： 中間結(jié)點只需緩沖一個數(shù)據(jù)片 (非消息或數(shù)據(jù)包 )，所有中間結(jié)點全部停頓 (流水占用一連串資源 )。 中間結(jié)點流水狀態(tài)表示： 用一根就緒 /請求線實現(xiàn)相鄰結(jié)點間的握手協(xié)議。 前一結(jié)點 R/A 后一結(jié)點 物理通道 回 54頁 路由 S（發(fā)送方） 路由 D（接收方） 狀態(tài) R/A線 狀態(tài) R/A線 可接收片 高 → 低，低 發(fā)送準備好 低 → 高 正在發(fā)送 高 正在接收 不驅(qū)動 禁止接收 不驅(qū)動 尋徑阻塞處理的優(yōu)化： 采用虛擬通道方法，使一個物理通道為多個數(shù)據(jù)包傳輸所共享。 物理通道 ( ) 前一結(jié)點 R/A 2 2 交換 開關(guān) 2 2 交換 開關(guān) 后一結(jié)點 二、路由算法 所有的路由算法都是根據(jù)網(wǎng)絡拓撲結(jié)構(gòu)的特征而設計的。 路由算法有確定性路由算法和自適應路由算法兩大類。 確定性路由算法： 路由只與源和目的地址有關(guān)； 自適應路由算法： 路由除與源和目的地址有關(guān)外，還與網(wǎng)絡傳輸狀態(tài) (路徑上的其他流量 )有關(guān)。 確定性路由算法 一般有算術(shù)路由法、源路由法、查表路由法三種。 （ 1）算術(shù)路由法 各交換開關(guān) 根據(jù)消息中源與目的地址、拓撲結(jié)構(gòu)中的 當前開關(guān)位置 來計算到下級開關(guān)的所選路徑。 如： 2D網(wǎng)格的 XY路由算法、 3D立方體的 E立方路由算法等。 特點： 當前開關(guān)需知道自己在網(wǎng)絡中的位置。 （ 2）源路由法 源結(jié)點 根據(jù)源與目的地址計算出 沿途各交換開關(guān) 的輸出端口號插入消息中；各開關(guān)根據(jù)消息中相關(guān)信息選擇開關(guān)狀態(tài)。 特點： 降低了開關(guān)的復雜度，源結(jié)點需知道全部網(wǎng)絡拓撲結(jié)構(gòu)。 （ 3）查表路由法 源結(jié)點根據(jù)目的地址計算出路由域 i插入消息中； 各交換機維護一個路由表 R(包含輸出端口 o及 下一跳路由 域 i’)，以消息中路由域 i為索引查表 R，得 o=R[i]及 i’，修改 i=i’，將消息從端口 o轉(zhuǎn)發(fā)出去。 特點： 當前交換機 (交換開關(guān) )只需知道下級交換機路由域即可。適合復雜的網(wǎng)絡連接。 回下頁 自適應路由算法 一般為確定性路由算法的擴展算法，即可根據(jù)網(wǎng)絡傳輸狀況在幾條路徑中選擇一條。 擴展算術(shù)路由算法： 數(shù)據(jù)包頭中增加控制信息，由交換機識別并控制 (需改變交換機設計 )； 擴展源路由算法： 源結(jié)點從多條路徑中選 (根據(jù)歷史信息 )一條到數(shù)據(jù)包頭中 (不改變交換機設計 )； 擴展查表路由算法： 路由表項中包含多條路由域 i’，交換機根據(jù)網(wǎng)絡狀態(tài)選擇并控制。 應用： 不廣泛 (交換機時延的增加抵消了帶寬的增加，可通過其他方法解決負載不均勻問題 )。 轉(zhuǎn)上頁 三、死鎖解決 死鎖產(chǎn)生原因 迎面死鎖： 兩個結(jié)點相互以同步方式發(fā)送消息時會發(fā)生。 結(jié)點 B ① ③ 消 息 處 理 結(jié)點 A 結(jié)點 A結(jié)點 B迎面死鎖示意圖 消 息 處 理 ② ④ 路由死鎖： 資源為非搶占式、網(wǎng) 絡中通道緩沖區(qū)已滿時，各消息路徑 構(gòu)成閉環(huán)時會產(chǎn)生。 路由死鎖示意圖 回下頁 死鎖的避免 （ 1）迎面死鎖解決 NIC無法發(fā)送消息時仍可接收 消息。即可從接收隊列中優(yōu)先處理 已發(fā)送消息的應答。 結(jié)點 B ① ③ 消 息 處 理 結(jié)點 A 消 息 處 理 ② ④ 只接收 ②的應答 只接收 ①的應答 （ 2）路由死鎖解決之一 — 虛擬通道技術(shù) 當某虛擬通道被阻塞時，總可選擇其他虛擬通道傳輸，打破閉環(huán)。 C4 C1 C3 C2 C4 C1 C3 C2 V3 V4 轉(zhuǎn)上頁 轉(zhuǎn) 49頁 只需在部分通道上設置虛擬通道，即可打破閉環(huán)。 （ 3）路由死鎖解決之二 — 轉(zhuǎn)彎路由技術(shù) 通過限制轉(zhuǎn)彎的種類來避免產(chǎn)生通道閉環(huán)。 以 2D網(wǎng)格網(wǎng)絡為例進行分析： 基本方法 沿 x方向路由時轉(zhuǎn)彎無限制，沿 y方向路由時不允許向 x方向轉(zhuǎn)彎。 +x→+y x→ y +x→ y x→+y 算法對路徑的限制分析： 16種轉(zhuǎn)彎中禁止了 4種； 限制越多，阻塞概率越大。 方法擴充 — 16種轉(zhuǎn)彎中只禁止 2種已經(jīng)可避免死鎖。 西優(yōu)先算法 北最后算法 負優(yōu)先算法 死鎖的解決 流控機制的部分功能 主要是解決兩個消息同時爭用一個物理通道的問題。 解決方法： 緩沖法、阻塞法、揚棄并重發(fā)、繞道法。 包緩沖區(qū) 片緩 沖區(qū) 包 2 包 1 輸出 通道 方法 1： 緩沖法 包 2 包 1 門 控制 方法 2： 阻塞法 包 2 包 1 方法 3： 揚棄并重發(fā) 應答包 2： NACK 包 2 包 1 方法 4： 阻塞后繞道 繞其它通道 采用方案： 一般選擇 2種左右。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1