1、路由選擇算法
網(wǎng)絡(luò)互聯(lián)，使得通信子網(wǎng)為端結(jié)點的通信提供了多條傳輸路徑的可能性，端結(jié)點主要完成數(shù)據(jù)的分組和組裝，中間結(jié)點則基于存儲-轉(zhuǎn)發(fā)技術(shù)，采用一定的算法在多條傳輸路徑中選擇一條來，并維持一個路由表來記錄有關(guān)的路徑信息，采用的算法就是路由選擇算法。在數(shù)據(jù)報方式中，網(wǎng)絡(luò)結(jié)點要為每個分組做出路由選擇，而在虛電路方式中，只需在連接建立時確定路由。路由選擇算法有多種，大致可分成靜態(tài)算法和動態(tài)算法兩大類。
靜態(tài)路由是在路由器中設(shè)置的固定路由表。除非網(wǎng)絡(luò)管理員干預(yù)，否則靜態(tài)路由不會發(fā)生變化。由于靜態(tài)路由不能對網(wǎng)絡(luò)的改變作出反映，一般用于網(wǎng)絡(luò)規(guī)模不大、拓?fù)浣Y(jié)構(gòu)固定的網(wǎng)絡(luò)中。靜態(tài)路由的優(yōu)點是簡單、高效、可靠。在所有的路由中，靜態(tài)路由優(yōu)先級最高。當(dāng)動態(tài)路由與靜態(tài)路由發(fā)生沖突時，以靜態(tài)路由為準(zhǔn)。
動態(tài)路由是網(wǎng)絡(luò)中的路由器之間相互通信，傳遞路由信息，利用收到的路由信息更新路由器表的過程。它能實時地適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)的變化。如果路由更新信息表明發(fā)生了網(wǎng)絡(luò)變化，路由選擇軟件就會重新計算路由，并發(fā)出新的路由更新信息。這些信息通過各個網(wǎng)絡(luò)，引起各路由器重新啟動其路由算法，并更新各自的路由表以動態(tài)地反映網(wǎng)絡(luò)拓?fù)渥兓討B(tài)路由適用于網(wǎng)絡(luò)規(guī)模大、網(wǎng)絡(luò)拓?fù)鋸?fù)雜的網(wǎng)絡(luò)。當(dāng)然，各種動態(tài)路由協(xié)議會不同程度地占用網(wǎng)絡(luò)帶寬和cpu資源。
靜態(tài)路由和動態(tài)路由有各自的特點和適用范圍，因此在網(wǎng)絡(luò)中動態(tài)路由通常作為靜態(tài)路由的補充。當(dāng)一個分組在路由器中進行尋徑時，路由器首先查找靜態(tài)路由，如果查到則根據(jù)相應(yīng)的靜態(tài)路由轉(zhuǎn)發(fā)分組；否則再查找動態(tài)路由。
2、路由選擇協(xié)議
在動態(tài)路由選擇算法中，路由器通過與相鄰結(jié)點周期地交換路由信息來更新和維護路由表，交換路由信息所使用的協(xié)議就是路由協(xié)議。
因特網(wǎng)采用分層次的路由選擇協(xié)議，之所以采用層次的路由選擇協(xié)議主要基于以下兩點考慮。第一，因特網(wǎng)的規(guī)模非常大，如果讓所有的路由器知道所有的網(wǎng)絡(luò)應(yīng)怎樣到達，則這種路由表將非常大，處理起來也太花時間。而所有這些路由器之間交換路由信息所需的帶寬就會使因特網(wǎng)的通信鏈路飽和。第二，許多單位不愿意外界了解自己單位網(wǎng)絡(luò)的布局細(xì)節(jié)和本部門所采用的路由選擇協(xié)議（這屬于本部門內(nèi)部的事情），但同時還希望連接到因特網(wǎng)上。
為了能夠采用分層的路由協(xié)議，因特網(wǎng)引入了自治系統(tǒng) as的概念。自治系統(tǒng) as 的定義：在單一的技術(shù)管理下的一組路由器，而這些路由器使用一種 as 內(nèi)部的路由選擇協(xié)議和共同的度量以確定分組在該 as 內(nèi)的路由，同時還使用一種 as 之間的路由選擇協(xié)議用以確定分組在 as之間的路由。在as的基礎(chǔ)上，因特網(wǎng)引入了兩大類路由選擇協(xié)議 ：
內(nèi)部網(wǎng)關(guān)協(xié)議 igp (interior gateway protocol) 即在一個自治系統(tǒng)內(nèi)部使用的路由選擇協(xié)議。目前這類路由選擇協(xié)議使用得最多，如路由選擇信息協(xié)議rip（routing information protocol） 、開放式最短路徑優(yōu)先ospf (open shortest path first)、中間系統(tǒng)到中間系統(tǒng)的路由選擇協(xié)議is-is（intermediate system to intermediate system routing protocol）、internet組管理協(xié)議igmp（internet group management protocol）等。
外部網(wǎng)關(guān)協(xié)議egp (external gateway protocol) 若源站和目的站處在不同的自治系統(tǒng)中，當(dāng)數(shù)據(jù)報傳到一個自治系統(tǒng)的邊界時，就需要使用一種協(xié)議將路由選擇信息傳遞到另一個自治系統(tǒng)中。這樣的協(xié)議就是外部網(wǎng)關(guān)協(xié)議 egp。在外部網(wǎng)關(guān)協(xié)議中目前使用最多的是邊界網(wǎng)關(guān)協(xié)議bgp-4。
3、rip協(xié)議
路由信息協(xié)議（rip）協(xié)議是基于dvr距離矢量的路由選擇協(xié)議。rip協(xié)議中，如果路由器a和網(wǎng)絡(luò)b直接相連，那么路由器a到網(wǎng)絡(luò)b的距離就是1。如果從路由器a出發(fā)，到達網(wǎng)絡(luò)b中間需要經(jīng)過n個路由器，那么路由器a到網(wǎng)絡(luò)b的距離就是n+1。rip協(xié)議中的距離也稱為“跳數(shù)”，每增加一個路由器，跳數(shù)就加1。
rip協(xié)議允許一條路徑上最多包含15個路由器，因此距離的最大值為16（表示網(wǎng)絡(luò)不可達），所以rip協(xié)議只適合于小型的網(wǎng)絡(luò)。在rip協(xié)議中，路由表不但要記錄到達目的網(wǎng)絡(luò)的下一站信息，還要記錄到達目的網(wǎng)絡(luò)的距離（跳數(shù)）。
rip協(xié)議認(rèn)為距離最小的路就是最好的路，其工作原理如下：
每個路由器每隔30s給自己的所有的鄰居路由器廣播rip報文，報文的內(nèi)容是這個路由器當(dāng)前的路由表信息。
收到鄰居路由器的路由表信息后，每個路由器都要更新自己的路由表，填加新的路由表項后更改舊的路由表項。這樣下一次就可以將更新后的路由表告訴自己的領(lǐng)居。
如果180s內(nèi)沒有收到某個路由器的路由表信息，就認(rèn)為這個路由器出了故障，路由表中所有以這個路由器為下一站的表項中的距離修改為16，表示目的網(wǎng)絡(luò)不可達。
經(jīng)過一段時間后，每個路由器都會知道到達每個網(wǎng)絡(luò)的路由，構(gòu)建出完整的路由表。
4、ospf協(xié)議
rip協(xié)議比較簡單，但只適用于規(guī)模較小的網(wǎng)絡(luò)（跳數(shù)<=16)。并且定期廣播路由表會耗費比較大的網(wǎng)絡(luò)資源。開放的最短路徑優(yōu)先ospf協(xié)議（open shortest path first）是對rip的改進，支持大型的網(wǎng)絡(luò)。ospf是基于鏈路狀態(tài)的路由協(xié)議。 對于一個路由器而言，它的鏈路狀態(tài)是指這個路由器與哪些路由器相鄰，以及它們之間鏈路的“度量”。 ospf使用帶寬、延時、負(fù)載、距離和費用等多種因素來考慮度量，度量越小，代價越低。鏈路狀態(tài)不包含路由信息，只是表明了兩個路由器之間的連接狀態(tài)。 每個路由器都有一個鏈路狀態(tài)數(shù)據(jù)庫，記錄當(dāng)前網(wǎng)絡(luò)的連接狀況。
ospf支持大型的網(wǎng)絡(luò)，它將一個自治系統(tǒng)分為若干個區(qū)域，每個區(qū)域內(nèi)的路由器相互交換鏈路狀態(tài)信息，區(qū)域也不能太大，在一個區(qū)域內(nèi)的路由器最好不超過 200 個。 存在一個主干區(qū)域，連接各個區(qū)域，主干區(qū)域負(fù)責(zé)收集非主干區(qū)域發(fā)出的匯總路由信息，并將這些信息發(fā)送給到各區(qū)域。劃分區(qū)域的好處就是將利用洪泛法交換鏈路狀態(tài)信息的范圍局限于每一個區(qū)域而不是整個的自治系統(tǒng)，這就減少了整個網(wǎng)絡(luò)上的通信量。在一個區(qū)域內(nèi)部的路由器只知道本區(qū)域的完整網(wǎng)絡(luò)拓?fù)?，而不知道其他區(qū)域的網(wǎng)絡(luò)拓?fù)涞那闆r。ospf 使用層次結(jié)構(gòu)的區(qū)域劃分。在上層的區(qū)域叫作主干區(qū)域(backbone area)。主干區(qū)域的標(biāo)識符規(guī)定為0.0.0.0。主干區(qū)域的作用是用來連通其他在下層的區(qū)域。
ospf由五種類型的分組來完成鏈路的更新：
類型1，問候(hello)分組。
類型2，數(shù)據(jù)庫描述(database description)分組。
類型3，鏈路狀態(tài)請求(link state request)分組。
類型4，鏈路狀態(tài)更新(link state update)分組，用洪泛法對全網(wǎng)更新鏈路狀態(tài)。
類型5，鏈路狀態(tài)確認(rèn)(link state acknowledgment)分組。
ospf的工作原理就是由該五類分組完成 ：
每個路由器會周期性地向相鄰路由器發(fā)送探測報文，檢測其是否可達。如果鄰站給與應(yīng)答，說明鏈路正常；否則說明鏈路出了故障。
如果一個路由器檢測到某條鏈路狀態(tài)發(fā)生了變化，該路由器就發(fā)送鏈路狀態(tài)更新報文，使用泛洪法對全網(wǎng)更新鏈路狀態(tài)。所謂泛洪法是指每個路由器收到更新報文后都將這個報文發(fā)送給自己的相鄰路由器，直到報文送達到整個網(wǎng)絡(luò)。
即便鏈路狀態(tài)沒有發(fā)生變化，每隔30分鐘路由器要向網(wǎng)絡(luò)中的其他路由器廣播鏈路狀態(tài)信息，以確保鏈路狀態(tài)數(shù)據(jù)庫與全網(wǎng)保持一致。
每個路由器收到其他路由器的鏈路狀態(tài)信息后，更新鏈路狀態(tài)數(shù)據(jù)庫，構(gòu)建整個網(wǎng)絡(luò)的拓?fù)鋱D，利用dijkstra的最短路徑算法計算出到達每個網(wǎng)絡(luò)的最短路徑。
5、 bgp協(xié)議
bgp 是不同自治系統(tǒng)的路由器之間交換路由信息的協(xié)議。 bgp 較新版本是 2006 年 1 月發(fā)表的 bgp-4（bgp 第 4 個版本）， 可以將 bgp-4 簡寫為 bgp。因特網(wǎng)的規(guī)模太大，使得自治系統(tǒng)之間路由選擇非常困難。對于自治系統(tǒng)之間的路由選擇，要尋找最佳路由是很不現(xiàn)實的。當(dāng)一條路徑通過幾個不同 as 時，要想對這樣的路徑計算出有意義的代價是不太可能的。比較合理的做法是在 as 之間交換“可達性”信息，力求尋找一條能夠到達目的網(wǎng)絡(luò)且比較好的路由（不能兜圈子），而并非要尋找一條最佳路由。
每一個自治系統(tǒng)的管理員要選擇至少一個路由器作為該自治系統(tǒng)的“ bgp 發(fā)言人”。
一般說來，兩個 bgp 發(fā)言人都是通過一個共享網(wǎng)絡(luò)連接在一起的，而 bgp 發(fā)言人往往就是 bgp 邊界路由器，但也可以不是 bgp 邊界路由器。一個 bgp 發(fā)言人與其他自治系統(tǒng)中的 bgp 發(fā)言人要交換路由信息，就要先建立 tcp 連接，然后在此連接上交換 bgp 報文以建立 bgp 會話(session)，利用 bgp 會話交換路由信息。bgp 所交換的網(wǎng)絡(luò)可達性的信息就是要到達某個網(wǎng)絡(luò)所要經(jīng)過的一系列 as。當(dāng) bgp 發(fā)言人互相交換了網(wǎng)絡(luò)可達性的信息后，各 bgp 發(fā)言人就根據(jù)所采用的策略從收到的路由信息中找出到達各 as 的較好路由。
bgp-4 共使用四種報文來完成as之間的會話，分別是：
打開(open)報文，用來與相鄰的另一個bgp發(fā)言人建立關(guān)系。
更新(update)報文，用來發(fā)送某一路由的信息，以及列出要撤消的多條路由。
?；?keepalive)報文，用來確認(rèn)打開報文和周期性地證實鄰站關(guān)系。
通知(notification)報文，用來發(fā)送檢測到的差錯。
在 rfc 2918 中增加了 route-refresh 報文，用來請求對等端重新通告。
bgp具有以下特點：
可靠的路由更新機制
豐富的metric度量方法
從設(shè)計上避免了環(huán)路的發(fā)生
支持cidr（無類別域間選路）
豐富的路由過濾和路由策略
周期性發(fā)送keepalive報文效驗tcp的連通性
無需周期性更新,路由更新只發(fā)送增量路由