什麼是路由器交換算法 路由器交換算法的代碼是什麼

今天給大家帶來什麼是路由器交換算法，路由器交換算法的代碼是什麼，讓您輕鬆解決問題。

一.CEF特快交換基本原理路由器和交換機是基礎網絡中最關鍵的部分，路由器和交換機其最主要的目的有兩個：一是如何準確的把數據包（幀）從源地址送到目標地址，二是如何更快速的送達。當然第二點的優先級要低於第一點的。為了更好的完成這兩個任務，交換機和路由器經過了多年的發展其各自交換包的方法也在不斷改進，其不論如何變化都是為了更好的完成這兩個根本任 務。本篇的主題是講解CEF基本原理
  www.zhishiwu.com  首先，先來看一下包轉發的過程。一般來說對於一個路由器會有以下三步：1. 查看這個包的目標地址是否可達2. 決定目標地址的下一跳和接口。3. 改寫MAC的包頭使得它可以成功的到達下一跳。
以上三步是路由器包交換的根本，到現在為止所有衍生出來的包交換方法都必須完成以上三個過程。

為了更好的理解CEF，再闡述一下另外兩種比較著名的包交換方法：進程交換和快速轉發
  www.zhishiwu.com  
進程交換
最古老的一個交換方法，被所有的平台所支持。
為了便於理解，用圖來具體講解進程交換的方式。 1. 接口進程（input interface processor）首先在網絡中發現數據包，然後把它傳遞給“input/output memory”（輸入輸出內存）2. 接口進程創建一個接到數據的中斷。在這個中斷過程中，中央處理器決定這個包的類型（一般是IP），如果需要的話就把它拷貝到內存中（processor memory）。最後，處理器把這個包放在一個適當的進入隊列中（process’ input queue），同時中斷取消。3. 然後調度程序開始啟動IP_INPUT進程  www.zhishiwu.com  4. 當IP_INPUT進程啟動，它開始從RIB（路由表）中決定下一跳和外出接口，然後查找ARP緩存找到下一跳的MAC地址.(如果緩存中沒有對應的地址的話將要進行ARP廣播)5. IP_INPUT進程重寫包的MAC地址，然後把包的放在合適端口的外出隊列中。6. 把包從外出端口的外出隊列中拷貝到外出端口的傳輸隊列。7. 外出接口處理器在外出隊列中發現這個包然後把這個包傳輸到網絡當中。
緊接著再來看第二種重要的交換方法：快速交換 1. 接口處理器發現網絡中的包，然後把包傳遞給input/output memory2. 接口處理器創建一個接收中斷。在這個中斷的過程中，中央處理器決定包的類型（假定是IP類型），然後立即開始交換這個包。3. 處理器開始搜索路由緩存來決定是否這個包的目的地址可達，外出接口是什麼以及這個包需要怎麼改寫MAC才能可達下一跳。4. 然後把包拷貝到外出端口的傳輸隊列或者外出隊列（這個根據不同廠商的不同而不同）。這時接收中斷取消，處理器繼續做剛才沒有做完的任務。5. 外出接口處理器發現數據包在傳輸隊列，然後把包傳輸到網絡中。

現在，回過頭來觀察對比一下這兩個交換方式究竟有什麼不同之處。
在講二者區別之前，先插一個概念。
到目前為止，包交換的方法有N種，其重要的有兩類，第一個就是進程交換，而第二類名字叫做“Interrupt Context Switching”，而這第二類中包含的交換方法有“快速交換”、我們熟知的CEF，還有 一個是Optimum交換。
在閱讀下麵的文字之前一定要把這個層次關係搞明白。

所謂進程交換，顧名思義，就是要創建進程，我們知道處理器在工作的時候是按照schedule（計劃）進行工作的，而進程交換就是這樣的，它會創建一個名 為“IP_INPUT”（假設討論的是IP包），然後放入到處理器的SCHEDULE中等待，什麼時候排到了什麼時候執行這個進程。發現什麼問題了嗎？排 隊這樣的規則從設計的角度來說是很不錯的，但是對於包交換來說就有一些拖遝，假設目前處理器有其他的工作要做，這個時候其創立的進程“IP_INPUT” 就必須在SCHEDULE中等著，不能執行，隻有當排到的時候才能執行，這樣顯然是浪費時間的。
相比之下，Interrupt Context Switching就要“霸道”很多，注意這個“INTERRUPT”，注意我的黑體字，這個交換方式跟進程交換的區別就是“不排隊”，隻要有包過來就先 處理它，等它處理完了，處理器再回去幹它SCHEDULE中的工作。
以上就是進程交換和Interrupt Context Switching的不同點之一。
另外一個不同點，如果你看過我上一篇文章的話，你可能有印象，就是增加了“緩存”，處理器在查找目標地址可達、下一跳這些信息的時候不是直接去查找路由表而是去查找緩存。這也是不同點之二。

第一個不同點讓交換增速不少，那麼第二點不同的作用又是什麼呢？“緩存到底有什麼用？”

對於Interrupt Context Switching這一類交換方式來說有三種不同的交換方法剛才已經介紹過了，他們是 
Fast Switching
Optimum Switching
Cisco Express Forwarding
這三種方法的主要區別就體現於其構建緩存方法的差別上，而正是由於這種差別才導致他們某些特性的不同。
先從最基礎的快速交換（Fast Switching）談起 如上圖，這是一顆二叉樹，這也是快速交換中的緩存數據結構，快速交換把外出接口信息和需要重寫的MAC地址放到二叉樹中相應的節點上，而需要轉發到的目的地址就是二叉樹上節點所代表的地址。那麼這樣的遍曆是如何進行呢？比如給出一個數是4，轉化成二進製100，查找從最高位開始，從root節點出發，第一步走向root的右子樹，因為100的第一位（最高位）是1，而後走向左子樹，再繼續向左子樹方向走，這個時候就查找到100了。如果這是一個真實的IPV4地址的話，最多需要32次查找便可以找到我們需要的網段是不是很快呢？鑒於IPV4地址的長度原因，快速交換的二叉樹深度是32。以上就是快速交換高速緩存中的數據結構，以及查找方法，下麵我們看看由此而產生的一些特性，並且找出它的不足。1、由於這個快速緩存是憑空建立的，並沒有和路由表以及MAC緩存建立聯係，所以當我們想應用快速交換進行查找的時候必須要先進行一次完整的過程交換。2、由於在快速緩存中一個節點對應著一個地址，而且沒有指針可以鏈接各個節點，所以無法實現遞歸查詢。不過這並不影響路由器使用遞歸查詢，因為當每一個新的數據包進來之後都要進行一次進程交換，其間已經完成了遞歸查詢。3、由於節點信息的建立是由路由表和ARP緩存而來，當路由表或者是ARP緩存刷新時，對應的節點應該無效，這時就必須重新建立一個二叉樹，在這個過程中 快速交換是無法使用的，隻能用傳統的進程交換，試想如果這是一個非常大的網絡，其網絡狀態不斷變化，這將會大大影響快速交換的效率。通過介紹快速交換，現在解決了一個問題，為什麼高速緩存的建立要比直接查找路由表要快速。但是通過分析發現它也不是盡善盡美的，有沒有更好的辦法呢？我們看下一個交換方式Optimum Switching
快一點！更快一點！二叉樹的構想是好的，但是它最多可能查詢32級還是顯得有些多，有沒有更快的呢？Optimum Switching主要就是改進了快速交換的數據結構，它重新構造了一個多枝(256-way mtree)，如圖所示，這樣一來它最多隻需要四次查找就可以達到目的，而一般來說隻需要一到三次查找就可以了。這是一個不錯的構想，但對於快速交換的其他方麵並沒有進行改進，隻能算作快速交換的一個升級版本，不過它卻起到了承上啟下的作用。接下來我們看看具有革命性的CEF！CEF是在快速交換和Optimum Switching的基礎上發展起來的第三代基於 Interrupt Context Switching的交換方式，它很好的克服了前兩種方法帶來的弊端。 二，CEF提供了以下優點：1• 改進的性能，CEF是小於快速切換路由緩存CPU密集型。更多的CPU處理能力，可專用於第3層服務，如服務質量（QoS）和加密。2• 可擴展性，CEF在每個線卡提供了充分的交換容量時，分布式CEF（dCEF）模式是積極的。3• 彈性的CEF提供了前所未有的水平在大型動態網絡的一致性和穩定性的開關。4• 雖然您可以使用CEF在任何一個網絡的一部分，它是專為高性能，高彈性的第3層IP骨幹交換。例如：下圖顯示了CEF正在運行的Cisco 12000係列千兆位交換路由器在網絡的核心彙聚點（GSRS）交通水平，密度和性能是至關重要的。  在一個典型的高容量的互聯網服務供應商的環境，在支持的網絡鏈接到Cisco 7500係列路由器或其他接駁設備的核心彙聚設備的思科12012職係架構檢討。CEF在這些平台在網絡核心提供所需的性能和可擴展性，以應對持續增長和不斷增加的網絡流量。CEF是一種分布式的交換機製，與安裝在路由器的接口卡和帶寬的線性擴展。5• CEF有兩個組件一個叫做FIB(Forwarding Information Base)另一個叫做鄰接表（Adjacency Table），這兩個表包括了所有的轉發信息，而這些轉發信息是根據路由表和ARP來構造的。其中FIB表可以看作是RIB(Router Information Base)的鏡像，它們是一一對應的，這也就是說相較於快速轉發CEF不需要去維護高速緩存，當路由表變化的時候FIB表也會發生變化。鄰接表的作用是建 立二層信息表，當一個鄰居被發現（從ARP表中）並且獲知其二層信息之後，鄰接表就把這個信息寫入表中並且與第三層的FIB表提前進行關聯。
 為了更快速的找到目的地址可達性信息，它依舊采用了Optimum Switching的mtree方式，唯一有區別的是CEF構建的mtree節點中並沒有包含外出接口MAC地址這些信息，而是變成了一個指針，指向一個單獨建立的表。CEF采用一個4級每級256條通道結構的轉發表來指明轉發條目的位置，轉發表有next hop等信息，涵蓋了整個IPv4的地址範圍，並有指針指向另一個鄰接表。轉發條目(MAC地址之類)都存儲在一個單獨的鄰接表上。 如果以上步驟完成之後，那麼當一個數據包入站之後在進行目的地址的查詢之後便可以順利的進行轉發，大大節省了CPU的資源，並且可以完全拋棄進程交換。6•CEF簡化了查詢的步驟，提高了單位時間的工作效率。而且從整體上來看，路由信息和轉發信息是分離的，數據包的轉發隻根據轉發信息而不用參照路由信息，可以充分利用專用硬件的功能來達到線速轉發，CEF相較於前兩種交換方式的改進主要在於對路由信息的“獨立化”，而這種獨立化帶來的優勢就是可以進行“預查找”，而不必等到數據包到來是才進行查找。而不受路由變化或者其他因素的幹擾，保證了轉發的高速高效。這就是CEF能夠提速的最關鍵因素。 三。CEF操作在路由器初始化時，會根據路由器軟件配置中的信息構建一張路由選擇表(如靜態路由、直連路由，以及通過路由選擇協議交換動態學習到的路由)。在構建了路由選擇表之後，CPU自動創建FIB和鄰接表。FIB 和鄰近表顯示了按照最佳轉發方式進行的出現在路由選擇表中的數據。與基於通信流的流緩存不同，cEF表是基於網絡拓撲。當一個分組進入交換機時，交換機的第3層轉發引擎ASIC根據目的網絡和最詳細的網絡掩碼澎於最長匹配查找。並且不涉及除路由選擇表和預先建立的FIB 表之外的任何軟件。此外，一旦路由選擇表中發生了變化，所有的cEF 表會立即更新。這使得這個方法是高效的，緩存不會由於路由翻動而無效。CEF 更加適應網絡拓撲的變化。CEF在軟件形式上實現了路由和交換功能的分離，而並不意味著路由器物理結構上的分離，所以它也可以在一些多層交換機和低端的路由器上實施。它的高速表現在以下方麵：
1>在查詢方式上簡化了步驟，提高了速度；
2>在分離了路由和轉發功能。 CEF的講解到此為止了，對於CEF，之所以說他是革命性的，不僅僅是因為其改進了查找的方式，而是因為它還有很多其他的特征，比如在負載均衡方麵它相 較於其他的交換方式也有很大的進步；如果我們要啟用MPLS，必須使用CEF，因為隻有CEF能夠在轉發的包中加入標簽等等。總 結一下：回顧整個路由器包交換的發展，我們可以把它分成兩類，四種方法。兩類是：Process Switching類和Interrupt Context Switching類。四種方法：進程交換屬於Process Switching，其他的三種 Fast Switching，Optimum Switching，CEF(Cisco Express Forwarding)屬於Interrupt Context Switching 

以上就是什麼是路由器交換算法，路由器交換算法的代碼是什麼教程,希望本文中能幫您解決問題。