【正文】 ??? 1v 1v ),1()(不直接相連與節(jié)點若節(jié)點，直接相連與節(jié)點若節(jié)點vlvD 在用計算機進(jìn)行求解時，可以用一個比任何通路長度大得多的數(shù)值代替 ∞ 。 ?對應(yīng)所有的 i，路徑中的第 i和 i1條連接到同一個節(jié)點上。 ? 延時 (delay)— 分組從源結(jié)點到達(dá)目的結(jié)點花費的時間。 從這里可以看出 ， 不存在一種絕對的最佳路由算法 。 (4)算法應(yīng)具有穩(wěn)定性。用來確定所收到的分組應(yīng)傳送的外出線路。進(jìn)行數(shù)據(jù)交換的兩個端系統(tǒng)之間有一條虛電路（網(wǎng)絡(luò)連接）為它們服務(wù)。 ?這就使分組的控制信息部分的比特數(shù)減少，因而減少了額外開銷。 21 2022/8/21 虛電路和數(shù)據(jù)報 通信子網(wǎng)和網(wǎng)絡(luò)層服務(wù) 數(shù)據(jù)報服務(wù)與虛電路服務(wù)之爭 : ?讓網(wǎng)絡(luò)只提供數(shù)據(jù)報服務(wù)就可大大簡化網(wǎng)絡(luò)層的結(jié)構(gòu)。 ?一個節(jié)點接收到一個數(shù)據(jù)報后，根據(jù)數(shù)據(jù)報中的地址信息和節(jié)點所存儲的路由信息，找出一個合適的出路，把數(shù)據(jù)報原封不動地發(fā)送到下一個節(jié)點。 13 2022/8/21 H1 H5 H2 H4 H3 A C D B H6 E 分組交換網(wǎng) H1 向 H5 發(fā)送分組 H2 向 H6 發(fā)送分組 路徑可能變化 網(wǎng)絡(luò)隨時接受主機發(fā)送的分組（即數(shù)據(jù)報） 網(wǎng)絡(luò)為每個分組獨立地選擇路由。 10 2022/8/21 提供虛電路服務(wù)的特點 H1 H5 H2 H4 H3 A C D B H6 E 分組交換網(wǎng) 在虛電路建立后，網(wǎng)絡(luò)向用戶提供的服務(wù)就好像在 兩個主機之間建立了一對穿過網(wǎng)絡(luò)的 數(shù)字管道 。 ?如果目的站點 F準(zhǔn)備接收該連接建立請求，沿著該邏輯通路的反方向即 F654A發(fā)送CallAccept控制分組給源站點 A，這樣就建立一條 A和 F之間的邏輯通道 A456F。1 2022/8/21 第五章：網(wǎng)絡(luò)層 2 2022/8/21 電路交換和分組交換 通信子網(wǎng)和網(wǎng)絡(luò)層服務(wù) 交換通信網(wǎng)絡(luò)可以分為： 電路交換 (circuit switching)和 分組交換 (packet switching)。 7 2022/8/21 虛電路和數(shù)據(jù)報 通信子網(wǎng)和網(wǎng)絡(luò)層服務(wù) ?在邏輯通道建立好之后，站點 A和站點 F之間就可以相互傳輸數(shù)據(jù)了，所有分組是沿著該邏輯通道傳輸?shù)模匆粋€邏輯通道中所有分組傳輸?shù)穆酚墒枪潭ǖ?，而且只需在連接建立時進(jìn)行一次路由選擇。 所有發(fā)送的分組都按順序進(jìn)入管道，然后按照 先進(jìn)先出的原則沿著此管道傳送到目的站主機。 14 2022/8/21 H1 H5 H2 H4 H3 A C D B H6 E 分組交換網(wǎng) 網(wǎng)絡(luò)盡最大努力地將分組交付給目的主機， 但網(wǎng)絡(luò)對源主機沒有任何承諾。 19 2022/8/21 虛電路和數(shù)據(jù)報 通信子網(wǎng)和網(wǎng)絡(luò)層服務(wù) ?發(fā)送端要發(fā)送一個報文時， 把報文拆裝成若干個帶有序號和地址信息的數(shù)據(jù)報，依次發(fā)送到網(wǎng)絡(luò)節(jié)點。 ?但技術(shù)的進(jìn)步使得網(wǎng)絡(luò)出錯的概率已越來越小，因而讓主機負(fù)責(zé)端到端的可靠性不但不會給主機增加更多的負(fù)擔(dān)，反而能夠使更多的應(yīng)用在這種簡單的網(wǎng)絡(luò)上運行。 24 2022/8/21 虛電路和數(shù)據(jù)報 通信子網(wǎng)和網(wǎng)絡(luò)層服務(wù) 數(shù)據(jù)報服務(wù)和虛電路服務(wù)都各有一些優(yōu)缺點 (3): ?在使用數(shù)據(jù)報時，主機承擔(dān)端到端的差錯控制和流量控制。 ?無連接 （數(shù)據(jù)報）服務(wù)方式 通信子網(wǎng)內(nèi)部節(jié)點按數(shù)據(jù)報方式交換數(shù)據(jù)，而與端系統(tǒng)相連的網(wǎng)絡(luò)節(jié)點向端系統(tǒng)提供虛電路服務(wù)。 如果子網(wǎng)是用數(shù)據(jù)報方式，對收到的每個分組都必須重新做一次路由選擇，路由是改變的；如果采用虛電路方式，則只需要在建立電路時做一次路由選擇。 在網(wǎng)絡(luò)通信量和網(wǎng)絡(luò)拓?fù)湎鄬Ψ€(wěn)定的情況下，路由算法應(yīng)收斂于一個可以接受的解，而不應(yīng)產(chǎn)生過多的振蕩。 所謂 “ 最佳 ” 只能是相對于某一種特定要求下得出的較為合理的選擇而已 。 ? 負(fù)載 (load)— 通過路由器或線路的單位時間通信量。 ?最小花費路徑：源到目的地之間所有可能的路徑的鏈路花費總和最小。對于上述例子，可以使D(v)＝ 99。 （ 表中帶圓圈的數(shù)字是在每一次執(zhí)行步驟 (2)時所尋找的具有最小值的 D(w)值 ） 網(wǎng)絡(luò)的最短通路 步驟 N D(2) D(3) D(4) D(5) D(6) 初始化 {1} 2 5 1 ∞ ∞ 1 {1,4} 2 4 ① 2 ∞ 2 {1,4,5} 2 3 1 ② 4 3 {1,2,4,5} ② 3 1 2 4 4 {1,2,3,4,5} 2 ③ 1 2 4 5 {1,2,3,4,5,6} 2 3 1 2 ④ 48 2022/8/21 路由算法分類 路由選擇 當(dāng)?shù)谖宕螆?zhí)行步驟 2后，所有網(wǎng)絡(luò)節(jié)點都已包含在 N中，整個算法結(jié)束，得到以節(jié)點 1為根節(jié)點的最小時延通路樹。 ?還可被用來分發(fā)信息、判斷可達(dá)性、找到最短路徑等。若概率相等，則只是簡單地循環(huán)選擇下一節(jié)點。 ?常用于規(guī)模很小的網(wǎng)絡(luò)。 ?大多數(shù)情況下，動態(tài)方式會使用別的節(jié)點來的狀態(tài)信息來進(jìn)行路由選擇，因此會增加網(wǎng)絡(luò)中的負(fù)載。 64 2022/8/21 路由算法分類 路由選擇 分布路由選擇 是指每個結(jié)點周期性地從相鄰的結(jié)點獲得網(wǎng)絡(luò)狀態(tài)信息， 同時也將本結(jié)點做出的決定周期性地通知周圍各結(jié)點，以使這些結(jié)點不斷地根據(jù)網(wǎng)絡(luò)新的狀態(tài)更新其路由選擇決定。 如果讓所有的路由器知道所有的網(wǎng)絡(luò)應(yīng)怎樣到達(dá)，則這種路由表將非常大，處理起來也太花時間。目前這類路由選擇協(xié)議使用得最多，如 RIP(路由信息協(xié)議 ) 和 OSPF（最短路徑優(yōu)先） 協(xié)議。這樣的協(xié)議就是外部網(wǎng)關(guān)協(xié)議 EGP。 ?許多單位不愿意外界了解自己單位網(wǎng)絡(luò)的布局細(xì)節(jié)和本部門所采用的路由選擇協(xié)議（這屬于本部門內(nèi)部的事情），但同時還希望連接到因特網(wǎng)上。 在分布式路由選擇策略中，最基本的算法有兩個： ①距離向量算法：距離可以是最短鏈路的時延，也可以是結(jié)點數(shù)等。 61 2022/8/21 路由算法分