路由交換設備，簡稱路由器，是網路互聯的核心設備，它的基本結構如圖1所示，主要由一個路由處理器、一個交換結構、輸入連線埠和輸出連線埠組成。輸入連線埠與輸入鏈路相連，執行物理層和數據鏈路層功能，接收數據包，根據IP位址查找確定數據包的輸出連線埠。輸出連線埠與輸出鏈路連線，也執行物理層和數據鏈路層功能，緩衝和傳送數據包。路由處理器運行路由協定和執行網路管理功能。交換結構用於連線輸入連線埠、輸出連線埠和路由器處理器，以便把輸入連線埠的數據包交換到一個或多個輸出連線埠，或者路由處理器上。
圖1 路由交換設備基本結構
基本介紹
- 中文名：路由交換設備
功能,查找算法,路由器結構,第一代路由器,第二代路由器,第三代路由器,路由器結構,性能指標,
功能
路由器的基本功能可分為路由處理、數據包轉發和其他處理。其中，兩個關鍵的功能是路由處理和數據包轉發，如圖2所示。
路由處理包括執行路由協定(如RIP和OSPF協定)，構造和維護路由轉發表，生成網路拓撲結構視圖。修改路由轉發表也可通過管理行為或手工增加、刪除路由。
數據包轉發一般包括以下操作：
①數據包有效性驗證：包括檢查IP版本號和報頭長度域、計算報頭檢驗碼等。
②目的IP位址解析和路由表查找：根據數據包的目的地址與路由表項的地址掩碼查找路由表，確定數據包的輸出連線埠與下一跳地址。
圖2路由器邏輯功能
③數據包生命周期控制：路由器調整數據包內的生命周期(Time-to-Live)域值，防止數據包在網路內無限期轉發。
④計算校驗碼：因修改TTL值，重新計算IP報頭的校驗碼。
另外，路由器還可能因IP數據包的長度超過最大傳輸單元長度而執行數據包分段功能。
路由器的其他處理包括數據包優先權分類，以及路由器執行網路管理功能等。
查找算法
長期以來，路由表的查找時間是制約路由器性能提高的主要問題。首先，路由器在接收到每個數據包後，需要在路由表中查找與目的地址具有最長地址掩碼匹配的路由表項，再把數據包轉發到該路由表指定的輸出連線埠上。其次，查找最長前綴匹配，使得一些傳統的完全匹配算法(如完全的哈希鍊表、二進制查找、標準相聯存儲器等)不能直接套用於路由表查找。另外，一個路由表，特別是骨幹網路由器的路由表，一般存儲數千個，甚至上萬個路由表項。這些因素的共同作用使得提高路由表查找速度變得困難。
這幾年已提出多種可有效改進路由表查找性能的算法，可分為硬體方法、壓縮方法和哈希表方法。傳統的硬體方法是使用聯想存儲器和高速緩衝(Cache)存儲路由表，但缺點是擴展性較差，不適於支持大路由表的高性能路由器。已提出的一種改進算法是把邏輯電路與存儲器結合在一起，使存儲器智慧型化，以極大地提高存儲器的訪問速度。另一種改進方法是利用大存儲空間存儲整個路由表，並採用專用硬體來修改路由表，以克服路由表修改困難的缺點。
壓縮算法是利用路由表的稀疏特性構造一個複雜而緊湊的路由表，以便把整個路由表存放在路由處理器的一級高速緩衝內，這樣就可以通過減少訪問記憶體次數來提高查找速度，但卻相對增加了路由表的複雜性。
一種改進哈希表的方法是對一個給定的IP位址循環地選取不同的前綴表達式，再分別求哈希表的值，其擴展性差。另一個可擴展哈希表查找算法的是對於一個N位地址，只需用0(logN)時間查找最長前綴匹配。這種算法給每個可能的最長前綴匹配分別計算一個獨立的哈希表，然後根據前綴表達式長度使用二進制查找算法，而不是從可能最長前綴表達式開始查找。另外，該算法為每個哈希表存儲內部標記，當哈希表查找失敗時，將指向另一個較短的前綴表達式的哈希表。一個路由表項的內部標記用壓縮方法存儲，可有效地減少標記項存儲空間。最後，預先求出一個前綴表達式的一個包括所有路由表項的哈希表，既可以快速修改哈希表，又能進一步減少平均存儲時間。
路由器結構
第一代路由器
第一代路由器是在一個通用處理計算機上用軟體來實現數據包的轉發，如圖3所示。
圖3基於匯流排的路由器結構
輸入數據包被轉發到CPU，CPU查找路由表確定下一跳地址後，再將其轉發到輸出連線埠。數據包通常緩衝在中心存儲器內，這使得數據包必須兩次經過匯流排，這將會成為最主要的系統瓶頸。另外，所有路由處理和節點管理軟體都在CPU上執行，降低了數據包的轉發性能。這種結構決定了路由器的性能是相當低的。即使提高CPU性能，由於路由表查找操作將占用大量的匯流排頻寬，因此也不可能線性地提高路由器的性能。
第二代路由器
第二代路由器相對用軟體實現的第一代路由器的一個重要改進是引入了分散式數據包轉發功能。在網路連線埠上除了設定輸入、輸出緩衝外，還設定了分散式處理器和路由高速緩衝，以減少系統匯流排負載。這樣，數據包轉發只需一次經過匯流排，同時，大量路由表查找是在路由高速緩衝中命中的，從而迅速減少了匯流排拷貝次數，加速了數據包轉發速度，如圖4所示。
在這種結構中，路由器維持一個中心路由表，在網路接口上分散式處理器的高速緩衝內保存一些最近使用的路由。如果一條路由不在網路接口處理器的高速緩衝內，則該路由將從中心路由表複製到高速緩衝內。下面簡單地描述數據包的轉發過程。
當一個新的目的地址的IP數據包到達時，若該數據包的目的地址不能在高速緩衝內命中，則該數據包將被轉發到中心處理器。中心處理器查找路由表，再將該數據包轉發到合適的輸出連線埠，同時將對應於該數據包目的地址的路由表項拷貝到輸入連線埠的高速緩衝內。若高速緩衝的路由表項已滿，則將優先替換最久沒有使用的路由表項。這樣，當這個數據包的後繼數據包到達時，它們的目的地址很有可能在高速緩衝內命中，那么就不再需要由中心處理器轉發，而能加快轉發速度了。
圖4使用路由高速緩衝的路由器結構
這種結構的主要缺點是路由器的吞吐量同IP數據包的到達模式相關。當網路拓撲的改變使高速緩衝內的路由表項失效時，會導致路由器性能的迅速下降。另外，共享匯流排也是一個系統性能的瓶頸。
對這種結構的一種改進方法是增加鏈路接口的高速緩衝空間，使整個轉發路由表保存在高速緩衝內，但中心處理器結構限制了路由器性能的進一步提高。
另一種基於匯流排的多處理器路由器結構如圖5所示。該結構同時採用了並發引擎與多條匯流排結構來提高系統性能。網路接口模組按線速傳送與接收數據包。當收到一個IP數據包時，控制電路將IP數據包的報頭分離，加上一個識別標記後，再拷貝到一個轉發引擎上進行有校性驗證和路由表查找，而在轉發引擎執行路由功能的同時，將IP數據包的剩餘部分並發地存儲到一個輸入緩衝內。當轉發引擎確定了輸出連線埠，並且把修改的IP數據包的報頭連同標記信息一起拷貝到對應的輸出連線埠模組緩衝內後，再將IP數據包的剩餘部分從輸入接口模組緩衝也拷貝到輸出連線埠模組緩衝內，最終由輸出連線埠模組傳送到輸出鏈路。
圖5並發引擎多匯流排的路由器結構
轉發引擎可並發地處理不同的數據包報頭。輸入控制電路將數據包報頭從IP數據包剝離後，一種是按輪轉方法把報頭分配給各轉發引擎，而輸出控制電路為了保證按數據包的到達順序傳送數據包，同樣地也按輪轉方法拷貝數據包報頭。另一種更為智慧型的方法是將每個數據包報頭分配給最低負載的轉發引擎，這可以取得更好的負載平衡。同樣地，輸出控制電路必須根據輸入控制電路分配報頭的順序選擇下一個轉發引擎來獲取已處理報頭，以保證按數據包的到達順序傳送數據包。轉發引擎完成報頭處理後，返回一個新的報頭和路由信息，包括下一跳地址。路由處理器的任務是運行路由協定，構造轉發引擎的路由轉發表。
由於路由器的所有網路接口不可能同時阻塞，因此這種共享轉發引擎結構可增加路由器的連線埠密度。另外，轉發引擎只完成下一跳地址解析任務，那就只需要將IP數據包報頭拷貝到轉發引擎，而在網路接口模組之間直接地交換數據包負載，這樣即大大地減少了系統匯流排負載。
第三代路由器
為解決第二代路由器的性能瓶頸問題，第三代路由器的設計使用了交換開關，以及共享記憶體代替共享匯流排的辦法。交換開關相當於在N個輸入連線埠和輸出連線埠間建立N條匯流排，使輸入連線埠和輸出連線埠之間通過並發的方式交換多個數據包，從而提高系統頻寬。
但一般的交叉開關存線上頭阻塞(HeaderofLineblocking)的問題，使得頻寬利用率不高。一個解決方法是採用內部加速，使交叉開關的內部頻寬大於輸入鏈路的頻寬總和，輸出連線埠同時接收多個輸入連線埠的數據包。這種輸出排隊方式的優點是數據包只輸出排隊延遲，但缺點是擴展性差。另一個解決方法是在輸入連線埠虛擬排隊。在每個輸入連線埠處對應一個輸出連線埠，各維持一個輸出先進先出佇列。模擬結果和解析方法已證明這種方法可獲取100%的吞吐量，並且只需取內部的加速比為2，即可獲得同內部加速為N(N72)時相似的吞吐量，因而是可擴展的。交換開關的另一問題是採用變長長度交換與固定長度交換。採用變長長度交換不需要分隔數據包，可提供頻寬利用率，但變長交換的控制過於複雜，所以更多的是採用固定長度交換。路由器將可變長度的IP數據包分隔為一些固定長度的信元，採用標記技術，快速地把一串信元交換到輸出連線埠，並在輸出連線埠重組IP數據包。
一個基於交換開關的高性能路由器的結構如圖6所示。在這個結構中，多個鏈路接口、多個轉發引擎和一個路由處理器通過一個高速的交換開關互聯。路由處理器同樣是控制中心，主要任務是運行路由協定，動態維護轉發引擎的高速緩衝路由表，以及執行網路管理功能。
當一個IP數據包到達鏈路接口時，IP數據包報頭通過交換開關複製到一個轉發引擎內，而剩下的負載部分則存儲在輸入鏈路接口內。轉發引擎查找本地高速緩衝路由表，確定IP包的輸出鏈路接口，修改IP包報頭，然後將IP包報頭和轉發指令傳輸到輸入鏈路接口。輸入鏈路接口將新的IP包報頭與原IP包負載重新組合成一個完整的IP包，通過交換開關轉發到輸出鏈路接口。
圖6基於交換開關的高性能路由器結構
轉發引擎按先來先服務的順序處理IP包報頭，處理過程分為3個階段：
①驗證IP包報頭的有效性，包括驗證IP長度、數據包長度和IP選項等。
②檢測在路由高速緩衝內是否存在同目的地址相匹配的路由，若不存在，則在相關的轉發路由表中查找，同時在路由高速緩衝中存儲對應於該目的地址的路由，然後修改IP包的生命周期域，重新計算IP校驗值。
③重填IP包報頭，將新的IP包報頭連同必需的輸出連線埠信息一起拷貝到輸入連線埠模組。
路由器結構
從前面的討論可知，一個路由器的瓶頸是處理頻寬、存儲器頻寬或內部交換頻寬。為了同時消除這3個瓶頸，超高性能的路由器採用了一種基於交換的全分布結構，如圖7所示。
圖7基於交換的全分布結構
每個網路接口具有內部處理器和緩衝空間，執行輸入流量、輸出流量的所有協定處理任務。各個網路接口通過一個高速交換矩陣互聯，以交換數據和控制信息。路由處理器執行中心控制任務。這樣，所有的協定處理和存儲操作分別分布在網路接口和路由處理器上並發地執行，提高了性能。
在網路接口中，特定媒質接口完成所有的物理層和介質訪問子層的功能，交換結構接口完成IP交換的前期和後期工作。在交換一個IP之前，先將IP包分成一些固定長度的信元，附上內部路由標識符或者標記優先權等；而在交換後，則將接收到的一些具有相同標識符的信元重組為一個IP數據包。
當前，超高性能的路由器的吞吐量設計目標已經達到了數百甚至數千吉比特。為了實現如此高的速度，必須採用最佳化關鍵處理模組性能的設計方法。圖8把路由器的所有處理分為時間關鍵的和非時間關鍵的。時間關鍵處理的任務主要包括IP包報頭處理、目的地址解析與查找、IP數據包生命周期控制、校驗碼計算、IP包交換等，而對於QoS路由器來說，還包括數據包分類，即根據數據包的源地址、目的地址、源連線埠、目的連線埠以及IP包的服務類型，將數據包映射為一些網路流。由於這些處理的速度直接決定了路由器轉發數據包的速度，因此在路由器結構中一般用專用硬體來實現這些功能，稱為路由器的快速路徑。
非時間關鍵處理的任務主要包括差錯控制協定(ICMP)、路由協定(RIP、OSPF、BGP)、網路管理協定(SNMP)等的處理。這些處理通常是在通用處理器上完成的，稱為路由器的慢速路徑。慢速路徑獨立於快速路徑，不會影響路由器的轉發速度。
圖8IP路由器中的IEEE802網路接口
性能指標
上面介紹了幾種不同的路由器結構，接下來再簡要討論一下路由器，主要是高性能路由器的性能指標，包括吞吐量與轉發率、延遲、報文重排序、路由表容量、路由抖動和QoS，以及最長匹配、路由收斂性、過濾等。下面將主要討論前面6個指標。
①吞吐量與轉發率
接口吞吐量和轉發率是路由器的基本指標，它雖僅僅是路由器指標的一部分，但人們經常將吞吐量和轉發率理解為最重要的指標，甚至是惟一的指標。
在接口吞吐量和轉發率測試時，向被測試設備的每一個接口傳送報文。目的地址要求能覆蓋200000個以上的子網，測試設備提供的信息流要達到線速度。需要注意的是，吞吐量在商業中是一個很通順的詞，而事實上，路由測試技術檔案RFC1242將它定義成設備在零丟失下包轉發的最高負載。容易出現概念混淆的是將吞吐量理解為以線速率提供信息流，然後對傳送的包進行計數而忽略任何損失。應該強調吞吐量意味著零損失，吞吐量是嚴格的指標。為了得到路由器的完整行為，還要測量在最大給定負載下的轉發率。在轉發率測試中，以線速率提供包，並對收到的包進行計數，以確定是否有損或零損失。轉發率的測試結果一般比吞吐量要高。
OC-192吞吐量是超高性能路由器的重要指標，在40位元組的負載下，每秒要處理的報文超過80億個，聚合速度為115.2Gbit/s。Cisco12416在處理Imix時(指按照網際網路流量特徵構造的報文組合，40位元組56%、1500位元組23%、576位元組17%和52位元組5%)，獲得了接近線速率的吞吐量。40B的IP包吞吐量為52%，這意味著12416將以線速率的52%對信息流進行無損轉發，但並不意味會丟失48%。事實上，Cisco和Juniper在轉發40位元組的IP包時達到了線速率的99%。
②延遲
路由器的處理延遲能力在某種程度上與吞吐量一樣重要。對於聲音和視頻等對延遲敏感的套用，則顯得尤為重要。理想情況下，延遲最好是小而且恆定的，一個延遲抖動很大的路由器難以獲得很好的套用。
③報文重排序
Juniper推出OC-192接口後，同行們就一直注意著報文重排序問題。導致重排序的原因是通過JuniperOC-192卡，實際上存在著4條路徑，這也意味著報文可以通過不同路徑，亂序到達。事實上，Juniper的OC-192接口確實在IP和多協定標記交換(MPLS)流量上重排序了一些報文。當轉發40B的IP報文時，Juniper的OC-192卡至多只對IP和MPLS流量的0.51%進行了重排序。而在Imix情況下，IP報文重排序達到了2.65%。在OC-192上，只要流量速度超過了Imix線速度的73%或者IP的56%，就會發生重排序，而在OC-48接口上卻沒有這類重排序。
④路由表容量
經過20世紀90年代的發展，BGP網路的個數直線上升，在最近的18個月時間裡，BGP網路數量已經開始快速的速率增長。不難想像，在今後幾年裡，BGP表在規模上至少會翻倍或是變為原來的3倍。
事實上，BGP表容量在很大程度上取決於設備存儲器。Juniper的M160提供768MB的RAM。Cisco公司的12416配置為256MB，新的12416版本會提供1GB存儲器，但卻沒有明確說明1GB的12416能否獲得超過40萬個路徑。
BGP表項的多少取決於軟體的設計。如何構造一個合理的算法，快速處理大容量的路由表是設計者面臨的主要問題。例如，JuniperM160處理路由硬體本質上是高端PC，具有自己的CPU和硬體驅動，即使有了768MB的RAM，可以存儲大約140萬個路徑，之後，M160開始將記憶體的內容存到硬碟上。M160在超過240萬個路徑後停止獲得路徑，因為它超出了交換區的空間。即使獲得更多的存儲空間，路由器還是不能完成更多的表項。
⑤路由抖動
實際網路的核心路由器在某一秒內可能會丟失上萬個網際網路路由，或者立刻就會產生成千上萬個新路由。核心路由器能否很好地處理這種不穩定性呢?
抖動性測試通常會給路由器裝載超過20萬條的路由條目，同時也裝載20萬條備份路由以及20萬條第3組路由，以便於在主路由關閉時，可以向所有的接口以線速度傳送40B的IP報文。測試持續一段時間(如30s)後，測試儀的BGP層撤銷1/4主路由。所有的撤銷路由都有相應的備份路由，所以對於每一個報文，總有一些可用的路由。一段時間後(如30s)，再重新廣播前面撤銷的5萬條主路由，這個過程將持續多次。
好的路由器應該在這種測試中只有很少或沒有性能損耗。15萬個路由項以內，也就是屬於穩定的路由中，由於沒有改變其路由選擇信息，因此性能應該比較平滑。而對於那些有抖動的路徑，報文應該於瞬息之間被切換到備份路徑上。
好的設備在穩定和抖動路徑上的轉發速度應該基本上沒有差異。
實際上，要獲得完美的性能，還有很長一段路要走。測試表明，在穩定的路徑上，Cisco的12416在轉發報文時，速度上基本沒有改變。但是，Cisco路由器在抖動路徑上轉發報文的速度則大大降低了。
在抖動路徑上的轉發速度將花費一段較長的時間才能恢復正常。Cisco對它的收斂時間進行了估計，即從一個節點的路由升級傳播到整個網路所需要的時間比它測試常用的30s的間隔要長一點。
JuniperM160在穩定的OC-48路徑上的轉發速度不如Cisco的穩定，但抖動幅度比Cisco小。在抖動路徑上，M160比Cisco更為出色，主要體現在轉發的下降幅度比Cisco的要小，在每次突變後能比Cisco更快地完成收斂。
⑥QoS
QoS是人們常掛在嘴邊的話題之一，大部分考慮是通過保證確定流量類型來收取額外費用，例如在網際網路發生擁塞時獲得優先處理。實際上，很多經營者都把QoS視為有利可圖之道，QoS的效果或許與商家描述的正相反。有人做過測試，假設定義3種服務級別∶黃金級、白銀級、青銅級，傳輸流量比率為70∶20∶5。Cisco12416和JuniperM160實際為70∶16∶5和70∶14∶5。也就是說，即便是在擁塞的情況下，還是有足夠的頻寬來滿足所有黃金級流量，不產生數據包丟失；而白銀級和青銅級則丟失較多。
為此，在QoS問題上，至少有兩點值得我們深思：第一，即使是目前技術最領先的Cisco和Juniper，對於簡單的3種服務類型(CoS，ClassofService)的流量處理也只能達到目前這個水平，所以仍有很遠的路要走；第二，目前網際網路的業務流量每秒鐘都在發生變化，分類機制不精確也是必然的，那些號稱能夠為多種流量級別提供細粒度精確控制的產品實際是不可能實用的，幾種簡單的恆定的流量也必須花很長時間來調節緩衝區的大小，才能達到上述測試結果。
