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