集中式路由選擇算法( centralized routing algorithm)

用完整的、全局性的網(wǎng)絡(luò)知識計算出從源到目的地之間的最低開銷路徑。鏈路狀態(tài)（LS）算法

• D(v):到算法的本次迭代，從源節(jié)點到目的節(jié)點v的最低開銷路徑的開銷。
• p(v):從源到0沿著當(dāng)前最低開銷路徑的前一節(jié)點(v的鄰居)。
• N':節(jié)點子集;如果從源到v的最低開銷路徑已確知，v在N'中。

Initialization:
N' = {u}
for all nodes V
  if V is aneighbor of u
     then D(v) = c(u,V)
  else D(v) =∞
Loop
  find W not in N' such that D(W) is a minimum
  addwtoN'
  update D(V) for each neighbor V of w and not in N' :
     D(v) = min(D(v)， D(W)+ C(W,v) )
/* new cost to V is either old cost to V or known
least path cost to w plus cost from w to V */
until N'= N

Example.png

answer.png

最低費用路徑和轉(zhuǎn)發(fā)表.png

鏈路狀態(tài)算法評價

• 復(fù)雜性：若有N個節(jié)點則時間復(fù)雜度為O(N²)
• 存在問題：
  • 算出來的結(jié)果并非最優(yōu)值
  • 沒有加權(quán)值，導(dǎo)致流量只會在一條路上，因此時延大
  • 沒有達(dá)到等開銷結(jié)果
  • 導(dǎo)致震蕩
  • 時間復(fù)雜度高

在分散式路由選擇算法( decentralized routing algorithm)

路由器以迭代、分布式的方式計算出最低開銷路徑。沒有節(jié)點擁有關(guān)于所有網(wǎng)絡(luò)鏈路開銷的完整信息。距離向量算法(DV)算法
Bellman-Ford方程: d_x(y)=min{c(x,y)+d_v(y)}

DV算法.png

DV算法概述.png

DV算法實例.png

DV算法評價

DV算法“好消息”傳播速度快，“壞消息”傳播速度慢。

毒性逆轉(zhuǎn)

其思想較為簡單:如果z通過y路由選擇到目的地x，則z將通告y，它(即z)到x的距離是無窮大，也就是z將向y通告D_z(x)=∞ (即使z實際上知道D_z(x)=5)。只要z經(jīng)y路由選擇到x，z就持續(xù)地向y講述這個善意的小謊言。因為y相信z沒有到x的路徑，故只要z繼續(xù)經(jīng)y路由選擇到x (并這樣去撒謊)，y將永遠(yuǎn)不會試圖經(jīng)由z路由選擇到x。
毒性逆轉(zhuǎn)解決了一般的無窮計數(shù)問題嗎?沒有。你應(yīng)認(rèn)識到涉及3個或更多節(jié)點(而
不只是兩個直接相連的鄰居節(jié)點)的環(huán)路將無法用毒性逆轉(zhuǎn)技術(shù)檢測到。

LS與DV比較

• 報文復(fù)雜性。我們已經(jīng)看到LS算法要求每個節(jié)點都知道網(wǎng)絡(luò)中每條鏈路的開銷。這就要求要發(fā)送O(|N||E|)個報文。而且無論何時一條鏈路的開銷改變時，必須向所有節(jié)點發(fā)送新的鏈路開銷。DV算法要求在每次迭代時，在兩個直接相連鄰居之間交換報文。我們已經(jīng)看到，算法收斂所需時間依賴于許多因素。當(dāng)鏈路開銷改變時，DV算法僅當(dāng)在新的鏈路開銷導(dǎo)致與該鏈路相連節(jié)點的最低開銷路徑發(fā)生
  改變時，才傳播已改變的鏈路開銷。
• 收斂速度。我們已經(jīng)看到LS算法的實現(xiàn)是一個要求O(|N|E|)個報文的(|N|²)算法。DV算法收斂較慢，且在收斂時會遇到路由選擇環(huán)路。DV算法還會遭遇無窮計數(shù)的問題。
• 健壯性。當(dāng)路由器損壞時，對于LS算法，路由器能夠向其連接的鏈路(而不是其他鏈路)廣播不正確的開銷。作為LS廣播的一部分，一個節(jié)點也可損壞或丟棄它收到的任何LS廣播分組。但是一個 Ls節(jié)點僅計算自己的轉(zhuǎn)發(fā)表;其他節(jié)點也自行執(zhí)行類似的計算。這就意味著在LS算法下，路由計算在某種程度上是分離的，提供了一定程度的健壯性。在DV算法下，一個節(jié)點可向任意或所有目的節(jié)點通告其不正確的最低開銷路徑。更一般地，我們會注意到每次迭代時，在DV算法中一個節(jié)點的計算會傳遞給它的鄰居，然后在下次迭代時再間接地傳遞給鄰居的鄰居。在此情況下，DV算法中一個不正確的節(jié)點計算值會擴(kuò)散到整個網(wǎng)絡(luò)。

層次路由選擇

• 自治系統(tǒng)（AS)，每個AS由一組處于相同管理控制下的路由器組成。
• 負(fù)責(zé)向在本AS之外的目的地轉(zhuǎn)發(fā)分組的路由器稱為網(wǎng)關(guān)路由器。

自治系統(tǒng)內(nèi)部的路由選擇

RIP(路由選擇信息協(xié)議)

RIP是一種距離向量協(xié)議，RIP使用跳數(shù)作為其費用測度。
一條路徑的最大費用被限制為15,因此RIP被限制用在網(wǎng)絡(luò)直徑不超過15跳的自治系統(tǒng)內(nèi)。前面講過，在DV協(xié)議中，相鄰路由器之間相互交換距離向量。對任何一臺路由器的距離向量是從這臺路由器到該AS中子網(wǎng)的最短路徑距離的當(dāng)前估計值。在RIP中，選路更新信息在鄰居之間通過使用一種RIP響應(yīng)報文(RIP response message)交換，大約30秒相互交換一次。由一臺路由器或主機(jī)發(fā)出的響應(yīng)報文包含了一個由多達(dá)25個AS內(nèi)的目的子網(wǎng)列表，還有發(fā)送方到其中每個子網(wǎng)的距離。響應(yīng)報文又被稱作RIP通告(RIP advertisement)。每臺路由器維護(hù)一張稱為選路表(routingtable)的RIP表。一臺路由器的選路表包括該路由器的距離向量和該路由器的轉(zhuǎn)發(fā)表。
如果一臺路由器一旦超過180秒沒有監(jiān)聽到其鄰居，則該鄰居不再被認(rèn)為是可達(dá)的，即要么其鄰居死機(jī)了，要么連接的鏈路中斷了。當(dāng)發(fā)生這種情況時，RIP修改本地選路表，然后通過向相鄰路由器(那些仍然可達(dá)的路由器)發(fā)送通告來傳播該信息。路由器也可通過使用RIP請求報文，請求其鄰居到指定目的地的費用。路由器在UDP上使用端口520相互發(fā)送RIP請求與響應(yīng)報文。該UDP報文段在標(biāo)準(zhǔn)IP數(shù)據(jù)報中承載在路由器之間。RIP使用一個位于網(wǎng)絡(luò)層協(xié)議(IP)之上的運輸層協(xié)議(UDP) 來實現(xiàn)網(wǎng)絡(luò)層功能(一種選路算法)，

OSPF(開放最短路優(yōu)先)

OSPF的核心是一個使用洪泛鏈路狀態(tài)信息的鏈路狀態(tài)協(xié)議和一個Dijkstra最低費用路徑算法。使用OSPF,一臺路由器構(gòu)建了一幅關(guān)于整個自治系統(tǒng)的完整拓?fù)鋱D(即一幅圖)。于是,每臺路由器在本地運行Djkstra的最短路徑算法，以確定一個以自身為根節(jié)點到所有子網(wǎng)的最短路徑樹。各條鏈路開銷是由網(wǎng)絡(luò)管理員配置的(參見“實踐原則:設(shè)置OSPF鏈路權(quán)值”)。OSPF不強(qiáng)制使用設(shè)置鏈路權(quán)值的策略(那是網(wǎng)絡(luò)管理員的任務(wù))，而是提供了一種機(jī)制(協(xié)議)，為給定鏈路權(quán)值集合確定最低開銷路徑的路由選擇。每當(dāng)一條鏈路的狀態(tài)發(fā)生變化時(如開銷的變化或連接/中斷狀態(tài)的變化)，路由器就會廣播鏈路狀態(tài)信息。即使鏈路狀態(tài)未發(fā)生變化，它也要周期性地(至少每隔30 min一次)廣播鏈路狀態(tài)。

OSPF的優(yōu)點

• 安全。能夠鑒別OSPF路由器之間的交換( 如鏈路狀態(tài)更新)。使用鑒別，僅有受信任的路由器能參與一個AS內(nèi)的OSPF協(xié)議，因此可防止惡意入侵者將不正確的信息注入路由器表內(nèi)。在默認(rèn)狀態(tài)下，路由器間的OSPF報文是未被鑒別的并能被偽造。
• 多條相同開銷的路徑。當(dāng)?shù)竭_(dá)某目的地的多條路徑具有相同的開銷時，OSPF允許使用多條路徑( 這就是說，當(dāng)存在多條相等開銷的路徑時，無須僅選擇單一的路徑來承載所有的流量)。
• 對單播與多播路由選擇的綜合支持。多播OSPF (MOSPF) 提供對OSPF的簡單擴(kuò)展，以便提供多播路由選擇。MOSPF使用現(xiàn)有的OSPF鏈路數(shù)據(jù)庫并為現(xiàn)有的OSPF鏈路狀態(tài)廣播機(jī)制增加了一種新型的鏈路狀態(tài)通告。
• 支持在單個AS中的層次結(jié)構(gòu)。一個OSPF自治系統(tǒng)能夠?qū)哟位嘏渲枚鄠€區(qū)域。每個區(qū)域都運行自己的OSPF鏈路狀態(tài)路由選擇算法，區(qū)域內(nèi)的每臺路由器都向該區(qū)域內(nèi)的所有其他路由器廣播其鏈路狀態(tài)。在每個區(qū)域內(nèi)，一臺或多臺區(qū)域邊界路由器負(fù)責(zé)為流向該區(qū)域以外的分組提供路由選擇。最后，在AS中只有一個OSPF區(qū)域配置成主干區(qū)域。主干區(qū)域的主要作用是為該AS中其他區(qū)域之間的流量提供路由選擇。該主干總是包含本AS中的所有區(qū)域邊界路由器，并且可能還包含了一些非邊界路由器。在AS中的區(qū)域間的路由選擇要求分組先路由到一個區(qū)域邊界路由器(區(qū)域內(nèi)路由選擇)，然后通過主干路由到位于目的區(qū)域的區(qū)域邊界路由器，進(jìn)而再路由到最終目的地。

自治系統(tǒng)間的路由選擇：BGP(邊界網(wǎng)關(guān)協(xié)議)

廣播路由選擇算法

網(wǎng)絡(luò)層提供了一種從源結(jié)點到網(wǎng)絡(luò)中的所有其他結(jié)點交付分組的服務(wù)

最直接的方法

發(fā)送結(jié)點向每個目的地分別發(fā)送分組的副本
缺點：

• 效率低
• 增加更多的開銷

無控制洪泛

源節(jié)點向它的所有鄰居發(fā)送分組的副本
結(jié)果：導(dǎo)致廣播風(fēng)暴——無休止的廣播分組的復(fù)制

受控洪泛

在序號控制洪泛(sequence-number-controlled flooding)中，源節(jié)點將其地址(或其他的唯一標(biāo)識符)以及廣播序號(broadcast sequence number)放入廣播分組，再向它的所有鄰居發(fā)送該分組。每個節(jié)點維護(hù)它已經(jīng)收到的、復(fù)制的和轉(zhuǎn)發(fā)的源地址和每個廣播分組的序號列表。當(dāng)一個節(jié)點接收到一個廣播分組時，它首先檢查該分組是否在該列表中。如果在，丟棄該分組;如果不在，復(fù)制該分組并向該節(jié)點的所有鄰居(除了從其接收到該分組的那個節(jié)點)轉(zhuǎn)發(fā)。
受控洪泛的第二種方法稱為反向路徑轉(zhuǎn)發(fā)(Reverse Path Forwarding, RPF) ,有時也稱為反向路徑廣播(RPB)。 RPF的基本思想簡單。當(dāng)一臺路由器接收到具有給定源地址的廣播分組時，僅當(dāng)該分組到達(dá)的鏈路正好是位于它自己到其源的最短單播路徑上，它才向其所有出鏈路(除了它接收分組的那個)傳輸分組。否則，該路由器只是丟棄入分組而不向任何它的出鏈路轉(zhuǎn)發(fā)分組。因為該路由器知道它在這樣一條鏈路(該鏈路位于它自到發(fā)送方的最短路徑上)上或者將接收或者已經(jīng)接收了該分組的一個拷貝，所以可以將這樣的一個分組丟棄。注意，RPF不使用單播選路以實際將分組交付給目的地，它也不要求路由器知道從它自己到源的完整最短路徑。RPF僅需要知道它到發(fā)送方的單播最短路徑上的下一個鄰居，它僅使用這個鄰居的身份來決定是否洪泛一個接收到的廣播分組。

生成樹廣播

生成樹廣播.png

多播路由選擇

使單個結(jié)點能夠向其他網(wǎng)絡(luò)結(jié)點的一個子集發(fā)送分組副本
多播路由中的兩個問題：

• 怎樣標(biāo)識多播分組的接收方
• 怎樣為發(fā)送到這些接收方的分組編址
  由于這些原因，在因特網(wǎng)體系結(jié)構(gòu)中，多播數(shù)據(jù)報使用**間接地址(address indirection) **來編址。這就是說，用一個標(biāo)識來表示一組接收方，尋址到該組的分組的拷貝被交付給所有與該組相關(guān)的多播接收方。在因特網(wǎng)中，表示一組接收方的單一標(biāo)識就是一個D類多播地址。與一個D類地址相關(guān)聯(lián)的接收方組稱為一個多播組(multicast group)。

因特網(wǎng)組管理協(xié)議

IGMP版本3運行在一臺主機(jī)與其直接相連的路由器之間。
IGMP為一臺主機(jī)提供了手段，可讓它通知與其相連的路由器，在本主機(jī)上運行的一個應(yīng)用程序想加入一個特定的多播組。由于IGMP的交互范圍被局限于主機(jī)與其相連的路由器間，因此顯然需要其他協(xié)議來協(xié)調(diào)遍及因特網(wǎng)內(nèi)的多播路由器(包括相連的路由器)，以便多播數(shù)據(jù)報能路由到其最終目的地。后一個功能是由網(wǎng)絡(luò)層多播選路算法完成的。因此，因特網(wǎng)中的網(wǎng)絡(luò)層多播是由兩個互補(bǔ)的組件組成的: IGMP與多播選路協(xié)議。
IGMP只有三種報文類型。與ICMP類似，IGMP報文也是承載(封裝)在一個IP數(shù)據(jù)報中,使用的IP協(xié)議號為2。由一臺路由器向所有與主機(jī)相連的接口發(fā)送membership_ query報文，以確定該接口上的主機(jī)已加入的所有多播組集合。主機(jī)用一個membership_ report報文來響應(yīng)membership_ query報文。當(dāng)一個應(yīng)用程序首次加入一個多播組時，也可由主機(jī)產(chǎn)生membership_ report報文， 而不用等待來自路由器的membership_ query報文。最后一種IGMP報文類型是leave_ group報文。有趣的是，這種報文是可選的!但如果它是可選的，那么路由器如何檢測出一臺主機(jī)是何時離開該多播組的呢?問題的答案就在于使用了membership_ query報文:當(dāng)無主機(jī)響應(yīng)一個含有給定組地址的membership_ query報文
時，路由器就推斷出已沒有主機(jī)在這個多播組了。

多播路由選擇算法

多播路由的選擇的目標(biāo)就是發(fā)現(xiàn)一顆鏈路的樹，這些鏈路連接了所有具有屬于該多播組相連主機(jī)的路由器。

• 使用一棵組共享樹進(jìn)行多播選路。像在生成樹廠播的場合中一樣，跨越組共享樹的多播選路基礎(chǔ)是構(gòu)建一棵樹，該樹包括所有具有屬于該多播組相連主機(jī)的邊緣路由器。在實踐中，使用基于中心方法來構(gòu)造多播選路樹，具有屬于多播組相連主機(jī)的邊緣路由器向中心節(jié)點(經(jīng)單播)發(fā)送加入報文。像在廣播情況下一樣，一個加入報文使用單播選路朝著中心轉(zhuǎn)發(fā)，直到它到達(dá)已經(jīng)屬于多播樹的一臺路由器或到達(dá)該中心。沿著該加入報文擊過路徑的所有路由器。將向發(fā)起該名播加入的邊緣路由器轉(zhuǎn)發(fā)接收到的多播分組。

• 使用一棵基于源的樹進(jìn)行多播選路。組共享樹多播選路算法構(gòu)建單一的、共享的選路樹來路由所有發(fā)送方的分組，而第二種方法為多播組中的每個源構(gòu)建一棵多播選路樹。在實踐中，使用RPF算法(具有源節(jié)點x)來構(gòu)造一棵多播轉(zhuǎn)發(fā)樹，以用于來自源節(jié)點x的多播數(shù)據(jù)報。我們前面學(xué)習(xí)的RPF算法與其用于多播環(huán)境中的要求有些不同。為了理解其中的原因，考慮圖4-51中的路由器D。在廣播RPF情況下，它將向路由器G轉(zhuǎn)發(fā)分組，即使路由器G沒有加入該多播組的相連主機(jī)。對于D只有一個下游路由器G的情況來說，這還不算太壞。想象一下，若有上千臺路由器在D下游時會出現(xiàn)什么情況?這數(shù)千臺路由器中的每-臺都將收到不想要的多播分組。(這種情景并不像看起來那么想當(dāng)然。最初的MBone一全球第一個多播網(wǎng)絡(luò)[Casner 1992; Macedonia 1994] 就遭遇了這樣的問題。)解決在RPF下會收到不想要的多播分組這個問題的方法稱為剪枝(pruning)。 一臺接收到多播分組的多播路由器，如它無加入該組的相連主機(jī)，則它向其上游路由器發(fā)送一個剪枝報文。如果一臺路由器從它的每個下游路由器收到剪枝報文，則它就向上游轉(zhuǎn)發(fā)一個剪枝報文。

  
  
  圖4-51.png

因特網(wǎng)中的多播路由選擇

第一個用于因特網(wǎng)中的多播選路協(xié)議是距離向量多播選路協(xié)議(Distance Vector Multicast Routing Protocol, DVMRP) 。DVMRP實現(xiàn)了 具有反向路徑轉(zhuǎn)發(fā)與剪枝算法的基于源的樹。如前面所討論的那樣，DVMRP使用一種具有剪枝的RFP算法。
使用最廣泛的多播選路協(xié)議是協(xié)議無關(guān)的多播(Protocol-Independent Multicast, PIM)選路協(xié)議,該協(xié)議明確辨識兩種多播分布情形。在稠密模式(dense mode)中，多播組成員的位置分布稠密，即該區(qū)域內(nèi)的許多或大多數(shù)路由器都需要參與到多播數(shù)據(jù)報選路過程之中。PIM稠密模式是一種洪泛與剪枝反向路徑轉(zhuǎn)發(fā)技術(shù)，類似于DVMRP的思想。
在稀疏模式(sparse mode) 中，具有相連組成員的路由器數(shù)量相對于路由器總數(shù)來說很少，組成員極為分散。PIM稀疏模式使用匯合點來建立多播分布樹。在源特定多播(Source-Specific Multicast, SSM) 中，僅允許單一發(fā)送方向多播樹中發(fā)送流量從而大大簡化了樹的構(gòu)造和維護(hù)。