Ⅰ 什麼是路由啊 路由的組成 以及路由的演算法
路由：路由（routing）是指分組從源到目的地時，決定端到端路徑的網路范圍的進程。路由工作在OSI參考模型第三層——網路層的數據包轉發設備。路由器通過轉發數據包來實現網路互連。雖然路由器可以支持多種協議（如TCP/IP、IPX/SPX、AppleTalk等協議），但是在我國絕大多數路由器運行TCP/IP協議。路由器通常連接兩個或多個由IP子網或點到點協議標識的邏輯埠，至少擁有1個物理埠。路由器根據收到數據包中的網路層地址以及路由器內部維護的路由表決定輸出埠以及下一跳地址，並且重寫鏈路層數據包頭實現轉發數據包。路由器通過動態維護路由表來反映當前的網路拓撲，並通過網路上其他路由器交換路由和鏈路信息來維護路由表。
路由器的組成：
RAM（隨機存儲器）
功能：存放路由表；存放ARP告訴緩存；存放快速交換緩存；存放分組交換緩沖；存放解壓後的IOS；路由器加電後，存放running配置文件；
特點：重啟或者斷電後，RAM中的內容丟失。
NVRAM（非易失性RAM）
功能：存儲路由器的startup配置文件；存儲路由器的備份。
特點：重啟或者斷電後內容不丟失。
FLASH（快速快閃記憶體）
功能：存放IOS和微代碼。
特點：重啟或者斷電後內容不丟失；可存放多個IOS版本（在容量許可的前提下）；允許軟體升級不需替換CPU中的晶元。
ROM(只讀存儲器)
功能：存放POST診斷所需的指令；存放mini-ios；存放ROM監控模式的代碼。
特點：ROM中的軟體升級需要更換CPU的晶元（還好這種情況比較少遇到)
CPU（中央處理器）
衡量路由器性能的重要指標，負責路由計算，路由選擇等。
背板：
背板能力是一個重要參數，尤其在交換機中。
路由演算法：又名選路演算法，可以根據多個特性來加以區分。演算法的目的是找到一條從源路由器到目的路由器的「好」路徑（即具有最低費用的路徑[1]）。演算法設計者的特定目標影響了該路由協議的操作；具體來說存在著多種路由演算法，每種演算法對網路和路由器資源的影響都不同；由於路由演算法使用多種度量標准（metric），從而影響到最佳路徑的計算。
演算法分類：主要有RIP、IGRP（IGRP為 Cisco公司的私有協議）；鏈路狀態路由協議基於圖論中非常著名的Dijkstra演算法，即最短優先路徑（Shortest Path First， SPF）演算法，如OSPF。在距離向量路由協議中，路由器將部分或全部的路由表傳遞給與其相鄰的路由器；而在鏈路狀態路由協議中，路由器將鏈路狀態信息傳 遞給在同一區域內的所有路由器。 根據路由器在自治系統（AS）中的位置，可將路由協議分為內部網關協議 （Interior Gateway Protocol，IGP）和外部網關協議（External Gateway Protocol，EGP，也叫域 間路由協議）。域間路由協議有兩種：外部網關協議（EGP）和邊界網關協議（BGP）。EGP是為一個簡單的樹型拓撲結構而設計的，在處理選路循環和設置 選路策略時，具有明顯的缺點，已被BGP代替。
Ⅱ 路由器結構
輸入埠是物理鏈路和輸入包的進口處。埠通常由線卡提供，一塊線卡一般支持4、8或16個埠，一個輸入埠具有許多功能。第一個功能是進行數據鏈路層的封裝和解封裝。第二個功能是在轉發表中查找輸入包目的地址從而決定目的埠（稱為路由查找），路由查找可以使用一般的硬體來實現，或者通過在每塊線卡上嵌入一個微處理器來完成。第三，為了提供QoS（服務質量），埠要對收到的數據包進行業務分類，分成幾個預定義的服務級別。第四，埠可能需要運行諸如SLIP（串列線網際協議）和PPP（點對點協議）這樣的數據鏈路級協議或者諸如PPTP（點對點隧道協議）這樣的網路級協議。一旦路由查找完成，必須用交換開關將包送到其輸出埠。如果路由器是輸入端加隊列的，則有幾個輸入端共享同一個交換開關。這樣輸入埠的最後一項功能是參加對公共資源（如交換開關）的仲裁協議。普通路由器中該部分的功能完全由路由器的中央處理器來執行，制約了數據包的轉發速率（每秒幾千到幾萬個數據包）。高端路由器中普遍實現了分布式硬體處理，介面部分有強大的CPU處理器和大容量的高速緩存，使介面數據速率達到10Gbps，滿足了高速骨幹網路的傳輸要求。
路由器的轉發機制對路由器的性能影響很大，常見的轉發方式有：進程轉發、快速轉發、優化轉發、分布式快速轉發。進程轉發將數據包從介面緩存拷貝到處理器的緩存中進行處理，先查看路由表再查看ARP表，重新封裝數據包後將數據包拷貝到介面緩存中准備傳送出去，兩次查表和拷貝數據極大的佔用CPU的處理時間，所以這是最慢的交換方式，只在低檔路由器中使用。快速交換將兩次查表的結果作了緩存，無需拷貝數據，所以CPU處理數據包的時間縮短了。優化交換在快速交換的基礎上略作改進，將緩存表的數據結構作了改變，用深度為4的256叉樹代替了深度為32的2叉樹或哈希表（hash），CPU的查找時間進一步縮短。這兩種轉發方式在中高檔路由器中普遍加以應用。在骨幹路由器中由於路由表條目的成倍增加，路由表或ARP表的任何變化都會引起大部分路由緩沖失效，以前的交換方式都不再適用，最新的交換方式是分布式快速交換，它在每個介面處理板上構建一個鏡像（mirror）路由表和MAC地址表相結合的轉發表，該表是深度為4的256叉樹，但每個節點的數據部分是指向另一個稱為鄰接表的指針，鄰接表中含有路由器成幀所需要的全部信息。這種結構使得轉發表完全由路由表和ARP表來同步更新，本身不再需要額外的老化進程，克服了其它交換方式需要不斷對緩存表進行老化的缺陷。
交換結構最常見的有匯流排型、共享內存型、Cross-bar空分結構型。匯流排型結構最簡單，所有輸入和輸出介面掛在一個匯流排上，同一時間只有兩個介面通過匯流排交換數據。其缺點是其交換容量受限於匯流排的容量以及為共享匯流排仲裁所帶來的額外開銷。在調度共享數據傳輸通道上必須花費一定的開銷，而且匯流排帶寬的擴展受到限制，制約了交換容量的擴張，一般在中檔路由器中使用這種結構。共享內存型結構中，進來的包被存貯在共享存貯器中，所交換的僅是包的指針，這提高了交換容量，但它受限於內存的訪問速度和存儲器的管理效率，盡管存貯器容量每18個月能夠翻一番，但存貯器的存取時間每年僅降低5%，這是共享存貯器交換開關的一個固有限制。共享內存型結構在早期的中低檔路由器中普遍應用。Cross-bar空分結構相當於多條並行工作的匯流排，具有N×N個交叉點的交叉開關可以被認為具有2N條匯流排。如果一個交叉是閉合，輸入匯流排上的數據在輸出匯流排上可用，否則不可用。對流經它的數據不斷進行開關切換，可見開關速度決定了交換容量，隨著各種高速器件的不斷涌現，這種結構的交換容量普遍達到幾十Gbps以上，成為目前高端路由器和交換機的首選交換結構。
路由計算或處理部分主要是運行動態路由協議。接收和發送路由信息，計算出路由表，為數據包的轉發提供依據。各種檔次的路由器的路由表條目的大小存在很大差異，從幾千條到幾百萬條不等，因此高端路由器的路由表的構造對路由查找速度影響很大，其路由表的數據結構常採用二叉樹的形式，查找與更新的速度都比較快。
輸出埠在包被發送到輸出鏈路之前對包存貯，可以實現復雜的調度演算法以支持優先等級要求。與輸入埠一樣，輸出埠同樣要能支持數據鏈路層的封裝和解封裝，以及許多較高級協議。
一般而言，路由器對一個數據包的交換要經過一系列的復雜處理，主要有以下幾個方面：
1）壓縮和解壓縮
2）加密和解密
3）用輸入/輸出訪問列表進行報文過濾
4）輸入速率限制
5）進行網路地址翻譯（NAT）
6）處理影響本報文的任何策略路由
7）應用防火牆特性對包進行檢查
8）處理Web頁緩沖的重定向
9）物理廣播處理，如幫助性地址（ip help address）
10）利用啟用的QoS機制對數據包排隊
11）TTL值的處理
12）處理IP頭部中的任選項
13）檢查數據包的完整性
Ⅲ 計算機網路-網路層-路由器的構成
路由器是一種具有多個輸入埠和多個輸出埠的專用計算機，其任務是轉發分組。從路由器某個輸入埠收到的分組，按照分組要去的目的地（即目的網路），把該分組從路由器的某個合適的輸出埠轉發給下一跳路由器。下一跳路由器也按照這種方法處理分組，直到該分組到達終點為止。路由器的轉發分組正是網路層的主要工作。
整個的路由器結構可劃分為兩大部分：路由選擇部分和分組轉發部分。
路由選擇部分也叫做控制部分，其核心構件是路由選擇處理機。 路由選擇處理機的任務是根據所選定的路由選擇協議構造出路由表，同時經常或定期地和相鄰路由器交換路由信息而不斷地更新和維護路由表。 分組轉發部分由三部分組成：交換結構、一組輸入埠和一組輸出埠（請注意：這里的埠就是硬體介面）。
交換結構(switching fabric)又稱為交換組織 ，交換結構是路由器的關鍵構件，它的作用就是根據轉發表(forwarding table)對分組進行處理，將某個輸入埠進入的分組從一個合適的輸出埠轉發出去，交換結構本身就是一種網路，但這種網路完全包含在路由器之中，因此交換結構可看成是「在路由器中的網路」。實現這樣的交換有多種方法，以下這三種方法都是將輸入埠 I1收到的分組轉發到輸出埠O2。
圖4-45(a)的示意圖表示 分組通過存儲器進行交換 。目的地址的查找和分組在存儲器中的緩存都是在輸入埠中進行的。若存儲器的帶寬（讀或寫）為每秒M個分組，那麼路由器的交換速率（即分組從輸入埠傳送到輸出埠的速率）一定小於M2。這是因為存儲器對分組的讀和寫需要花費的時間是同一個數量級。
圖4-45(b)是 通過匯流排進行交換 的示意圖。採用這種方式時，數據報從輸入埠通過共享的匯流排直接傳送到合適的輸出埠，而不需要路由選擇處理機的干預。但是，由於匯流排是共享的，因此在同一時間只能有一個分組在匯流排上傳送。當分組到達輸入埠時若發現匯流排忙（因為匯流排正在傳送另一個分組），則被阻塞而不能通過交換結構，並在輸入埠排隊等待。因為每一個要轉發的分組都要通過這一條匯流排，因此路由器的轉發帶寬就受匯流排速率的限制。現代的技術已經可以將匯流排的帶寬提高到每秒吉比特的速率，因此許多的路由器產品都採用這種通過匯流排的交換方式。
圖4-45(c)是 通過縱橫交換結構(crossbar switch fabric)進行交換 。這種交換機構常稱為互連網路(interconnection network),它有2N條匯流排，可以使N個輸入埠和N個輸出埠相連接，這取決於相應的交叉結點是使水平匯流排和垂直匯流排接通還是斷開。當輸入埠收到一個分組時，就將它發送到與該輸入埠相連的水平匯流排上。若通向所要轉發的輸出埠的垂直匯流排是空閑的，則在這個結點將垂直匯流排與水平匯流排接通，然後將該分組轉發到這個輸出埠。但若該垂直匯流排已被佔用（有另一個分組正在轉發到同一個輸出埠），則後到達的分組就被阻塞，必須在輸入埠排隊。
在圖4-42中，路由器的輸入和輸出埠裡面都各有三個方框，用方框中的1,2和3分別代表物理層、數據鏈路層和網路層的處理模塊。物理層進行比特的接收。數據鏈路層則按照鏈路層協議接收傳送分組的核。在把航的首部和尾部去後，分組就被送入網路層的處理模塊。若接收到的分組是路由器之間交換路由信總的分組（如RIP或OSPF分組等），則把這種分組送交路由器的路由選擇部分中的路由選擇處理機。若接收到的是數據分組，則按照分組首部中的目的地址查找轉發表，根據得出的結果，分組就經過交換結構到達合適的輸出埠。 一個路由器的輸入埠和輸出埠就做在路由器的線路介面卡上。
輸入埠 中的查找和轉發功能在路由器的交換功能中是最重要的。為了使交換功能分散化，往往把復制的轉發表放在每一個輸入埠中（如圖4-42中的虛線箭頭所示）。路由遠擇處理機負責對各轉發表的副本進行更新。這些副本常稱為「影子副本」(shadow ),分散化交換可以避免在路由器中的某一點上出現瓶頸。
「但在具體的實現中還是會遇到不少困難。問題就在於路由器必須以很高的速率轉發分組。最理想的情況是 輸入埠的處理速率能夠跟上線路把分組傳送到路由器的速率。這種速率稱為線速 （line speed 或 wirc peed)。可以粗略地估算一下。設線路是0C-48鏈路，即2.5 Gbit/s。若分組長度為256位元組，那麼線速就應當達到每秒能夠處理100萬以上的分組。現在常用Mpps(百萬分組每秒)為單位來說明一個路由器對收到的分組的處理速率有多高。」
當一個分組正在查找轉發表時，後面又緊跟著從這個輸入埠收到另一個分組。這個後到的分組就必須在隊列中排隊等待，因而產生了一定的時延。
輸出埠 從交換結構接收分組，然後把它們發送到路由器外面的線路上。在網路層的處理模塊中設有一個緩沖區，實際上它就是一個隊列。當交換結構傳送過來的分組的速率超過輸出鏈路的發送速率時，來不及發送的分組就必須暫時存放在這個隊列中。數據鏈路層處理模塊把分組加上鏈路層的首部和尾部，交給物理層後發送到外部線路。
從以上可以看出，分組在路由器的輸入埠和輸出埠都可能會在隊列中排隊等候處理。若分組處理的速率趕不上分組進入隊列的速率，則隊列的存儲空間最終必定減少到零，這就使後面再進入隊列的分組由於沒有存儲空間而只能被丟棄。分組丟失就是發生在路由器中的輸入或輸出隊列產生溢出的時候。當然，設備或線路出故障也可能使分組丟失。
「轉發」和「路由選擇」的區別 ：在互聯網中， 「轉發」 就是路由器根據轉發表把收到的IP數據報從路由器合適的埠轉發出去。「轉發」僅僅涉及到一個路由器。但 「路由選擇」 則涉及到很多路由器，路由表則是許多路由器協同工作的結果。這些路由器按照復雜的路由演算法，得出整個網銘的拓撲變化情況，因而能夠動態地改變所選擇的路由，並由此構造出整個的路由表，路由表一般僅包含從目的網路到下一跳（用P地址表示）的映射，而轉發表是從路由表得出的。轉發表必須包含完成轉發功能所必需的信息。這就是說，在轉發表的每一行必須包含從要到達的目的網路到輸出埠和某些MAC地址信息（如下跳的乙太網地址)的映射。將轉發表和路由表用不同的數據結構實現會帶來一些好處，這是因為在轉發分組時，轉發表的結構應當使查找過程最優化，但路由表則需要對網路拓撲變化的計算最優化。路由表總是用軟體實現的，但轉發表則甚至可用特殊的硬體來實現。請讀者注意，在討論路由選擇的原理時， 往往不去區分轉發表和路由表的區別，而可以籠統地都使用路由表這一名詞。