以路由緩存表項指針作標記的標記交換探析

劉永強

（江蘇海洋大學，江蘇連云港 222005）

隨著IP 寬帶應用需求的不斷提高，對網絡的帶寬提出了更高要求，而路由器對IP 數據分組的轉發速率是制約頻帶拓寬的關鍵因素。提高IP 數據分組的轉發性能大致有如下的幾種思路[1]：①將路由和轉發分開；②用快速硬件對IP 分組進行報頭處理、尋徑和轉發；③使用分布式網絡接口；④以交換結構提高各接口之間的帶寬。

無論從IP 路由器的體系結構上還是從實現技術上看，上述的幾種研究思路，雖然能使IP 分組的轉發速率有一定的提高，但始終未克服從路由表中查找路由（本文稱之為表格路由）這個瓶頸，這與IP 地址的體系結構有關。IP 地址的分配雖然具有全局性，然而IP分組的路由是基于目的地址的，從IP 地址中可得到包括地址類型、網絡地址、主機地址3 個信息，其不具備方向性，這些信息對路由器中的某個IP 數據分組來說就像置身迷宮，只能在一定的路由策略下通過多次的比較或查找以確定數據分組的去向，這使得主干網上的路由器不得不維護龐大的路由表和路由緩存表，而且對每個到達的IP 分組（即使是同一數據流或同一轉發等價類）都需要在該路由緩存散列表[2]上進行一次查找，如果路由緩存沒有命中，則需要做一次完整的更花時間的路由計算，再將結果加入到路由緩存中供下次利用，而高速緩存（包括聯想存儲器CAM 和TCAM——ternary CAM）因受容量的制約致使取得的性能改善很有限，這是IP 地址體系結構的先天不足。

1 MPLS 及IPLS 的引入

設計和實施一種不需要查找路由表，直接經計算即可得到路由（本文稱之為計算路由）的地址體系結構目前條件尚不成熟。為減小IP 地址目前的這種結構體系對IP 分組轉發速率的進一步提高所產生的影響，提出了將路由和轉發分開，并在此基礎上利用“一次路由，多次轉發/交換”技術的多種方案。諸如MPLS（多協議標記交換）、IPLS（IP 分組標記交換）等，兩者使主干網上路由器的數據分組的轉發性能有了很大的提高，有望成為未來互聯網新的技術平臺。

MPLS 綜合了IP 選路和ATM 交換的優點，實現基于IP 路由機制和ATM 交換機制的統一技術平臺。但是這種基于ATM 的體制存在著如下缺陷[3]：①在網絡邊緣的節點上IP 分組與ATM 信元之間拆與裝比較復雜，而且在傳輸速率非常高時，甚至難以實現；②FEC（轉發等價類）標記與各種標記域的相互對應較難保證；③通信雙方之間2 條不對稱性的單向LSP（標記交換路徑）沒有有效地利用雙向對稱的ATM 交換通路的帶寬；④MPLS 隧道的功能在ATM 上只有VPI 和VCI兩級；⑤ATM 的信元標記歸并可能會發生交織；⑥MPLS 使用動態IP 選路可能形成環路。總體上看，MPLS 是將IP 地址的最長前綴匹配改為標記的精確匹配。

為克服MPLS 的以上缺陷，使用基于IP 分組的標記交換（IPLS）構建寬帶網絡有明顯的優勢[3]。下面討論標記交換中的標記問題。

2 標記的概念

幾乎所有關于標記交換的資料中對標記沒有準確的語意，只是給出了說明性的定義，比較傾向的描述是一種簡短的，具有固定長度的，用以標識網絡中一個“轉發等價類（FEC）”的，只具有局部意義的標識符。由于其在標記交換中起到非常重要的作用，因此必須具有明確的語意，可以看作是FEC 的別名，或者是IP 地址的最長前綴匹配等，然而，具體到協議棧實現中究竟選取什么作標記需要仔細研究。實際上，IP 地址也是一種標記，用以標記互聯網上的一臺主機。

從本質上看，交換是指交換節點根據數據分組攜帶的標記，按照某種設定的輸入輸出關系，對分組進行處理的過程，以求在源與目的之間建立一條數據通道。可見，輸入輸出關系的高效利用是關鍵所在，這種關系的建立則可以采用各種有效的路由算法，與分組的處理是分離的。交換機與路由器中的這種輸入輸出關系建立方法可以不同，可使用的協議有許多，如路由信息協議（RIP）、內部網關路由協議（IGRP）、開放式最短路徑優先協議（OSPF）、外部網關協議（EGP）和邊界網關協議（BGP）等。

3 以路由緩存表項入口指針作標記

對于主干網節點上的一個待發送的數據分組，IP層大致完成如下過程：①從傳輸層或數據鏈路層接收數據分組并進行一定的處理；②在所連接的網絡中使用一定的路由算法選擇數據包傳輸的下一跳；③把數據分組交予數據鏈路層的驅動程序。其中第②步根據IP 地址經過一定的計算，然后到龐大的路由表中進行檢索，以得到該數據分組的下一跳，這一步十分費時，是路由器的瓶頸。

上面提到的“一次路由，多次轉發/交換”思想將在很大程度上緩解路由器路由選擇的壓力，然而這一思想要求路由器保持活躍的路由結果，緩沖將是比較可行的解決方案，而記錄路由結果有2 種選擇：①記錄數據流的輸出硬件端口（如網卡地址）；②記錄路由緩沖表項的入口指針。顯然，由于路由器需要收集許多管理數據，選擇記錄路由緩沖表項的入口指針是對路由的最好保持。

本文提出以路由緩沖表項的入口指針（Entry Pointer of Route Cache，EPRC）作IPLS 的標記，該入口指針可以是物理或邏輯地址，一般為邏輯地址。

3.1 選取EPRC 作標記的出發點

寬帶IP 網絡要求路由器有高速的數據分組轉發性能。一般來說，標記越簡潔、越能表現路由信息，那么使用的轉發規范也就越簡單，由此而獲得的數據分組轉發性能就越好，所以，使用路由緩沖表項的入口指針作標記是較為合適的選擇。使用含混或“曲線”的標記在高速數據分組轉發中很難想象有多好的性能表現。

3.2 IP 數據分組轉發性能的提高

選取EPRC 作標記既繼承了IP 路由的靈活性，又為高速的交換提供了可能。在已建好的連接上轉發數據分組時，根據其攜帶的標記將直接得到所需的路由信息。對內存的訪問只需一次，按10 ns 的訪存時間計算，理想情況下每秒可進行100 M 次路由/交換，假設數據分組的載荷平均為200 個字節，在網絡線路接口能達到較高的吞吐率的情況下，則總帶寬為160 Gbps，若考慮使用高速Cache、多體存儲器和更高速的內存，則得到的總帶寬將大于上面的數字，完全能滿足大多數主干網交換節點的需要。

3.3 EPRC 的應用限制

以路由緩存表項的入口指針作標記這一點在端節點與路由器或各路由器之間達成共識后，新的路由表項除標記和原有的內容外，還可包括服務類型、服務質量（QoS）、標記堆棧指示和標記操作等信息，其內容的多寡依據路由器提供的服務需要而定，跟標記無關，所以這種標記可應用于多種網絡協議，目前基本上沒有應用上的限制。至于擔心建立連接會損失一定的時間，這是不必要的，比如打電話需撥號是再正常不過的，況且大多數應用都是面向連接的，而且更關心的是網絡的數據傳輸速度。

4 標記在IP 網絡中的承載

為增強EPRC 的兼容性，采用對IPv4 數據分組的選項[4]（Options）進行擴展。

在IPv4 中，IP 選項類型組成如圖1 所示，其定義見表1。

圖1 IP 選項類型組成

表1 選項類型定義

如上所述，選項類型為0 和2 的已被使用，可利用保留的類型，即class=1。由于EPRC 在IP 數據分組的傳輸中需要將該選項復制到所有的分片中，故復制位應置為1，即二進制形如[101xxxxx]b，將此標記置于IP選項中，實際的路由緩存表項入口指針可選用4 個字節32 位整數，可容納4 G 項，可滿足一定規模的骨干路由器需要。

IP 選項的定義如圖2 所示，詳見Linux 源代碼(v2.6.28.10)srcincludelinuxip.h。

圖2 IP 選項

路由緩存項的結構在內核源代碼srcin clude et oute.h中的定義如圖3所示。

圖3 路由緩存項定義

EPRC 在網絡層而非鏈路層實現，只需修改部分的路由軟件，無須增加硬件設備。EPRC 在IPv6 中同樣有合適的承載。

5 標記的分配、分發與操作

使用EPRC 作標記，路由緩存表項的分配就是標記的分配，在路由器采用數據流驅動的方式。標記的分發采用下游按需分發，在路由緩存表項分配完成后，將得到的入口指針由ICMP 攜帶告知上游節點并登記保存，待數據分組發送時將該標記裝配進IP 數據分組的選項里一并轉發出去。

以Linux（內核版本v2.6.28.10）為例，IP 數據分組在網絡層的處理流程[2，5]如下。當數據幀到達網絡設備時，將產生一個中斷，中斷程序調用驅動層的net_rx()，繼而產生軟中斷進入net_rx_action()，如發現這個數據幀是IP 分組，則調用IP 協議層ip_rcv()，IP 數據分組在經過netfilter 模塊處理后，進而調用ip_rcv_finish()，在該函數內，將調用IP 接口函數ip_route_input()執行實際的路由算法。其中入參5 個：skb (IP 包緩沖區)、iph-〉daddr(IP 包目的地址)、iph-〉saddr(IP 包源地址)、iph-〉tos(服務類型)和dev(輸入的網絡設備)。當函數返回0 時，說明成功找到路由。路由查詢結果放在skb-〉dst 中，其指向路由緩存中的一個結點。之后通過調用skb-〉dst-〉input(skb)來對該IP 數據包進行處理。由于這里的input 是路由緩存結點中的一個函數指針，根據數據包的流向進行處理，如果這個路由項表示轉發的，那么這個指針實際上指向的是ip_forward()，而如果是傳送給本地的，那么指向的是ip_local_deliver(),該函數將這個IP 包進一步傳給上層協議層處理，ip_forward()則將這個IP 包從網絡設備發送出去。

路由緩存結構關系如圖4 所示。

圖4 路由緩存結構關系圖

涉及的主要數據結構包括如下幾點：struct rt_hash_bucket rt_hash_table、struct rtable、struct dst_en try和變量rt_hash_mask。EPRC的保存可采用在結構rtable中新增對應的指針，形如struct rtable*eprc，初始化為null。

無論是數據分組輸入還是輸出，當搜索路由緩存失敗，則執行路由算法查找路由表并將表項保存到路由緩存中，利用函數rt_intern_hash()將創建的緩存項添加到哈希緩存頭部。此后，利用ICMP 攜帶該緩存路由表項指針以長整型反向回傳到上一跳（數據分組初始發起者無上一跳）并保存，放到對應的路由緩存項的指針eprc 中。

當有IP 數據分組輸入時，解析IP 的選項，如果攜帶有ERPC，則直接從路由緩存項中讀取，即可進入數據分組的下一處理環節。為安全起見，將增加審核環節，即需比對對應的源地址和目的地址等相關信息，以免使用過期的eprc。

當有IP 數據分組需要輸出時，在搜索路由緩存項成功返回后，如果保存有下一跳的eprc，則其組裝進IP分組的選項內一并轉發出去。

如涉及標記的操作壓棧、彈棧、合并和轉換等可沿用MPLS 的方法[6]。

6 結束語

在非計算路由中，要獲取數據包的下一跳信息，就必須對路由緩存所在的存儲器進行至少1 次讀取，表格路由中獲取路由信息最直接、最快捷的方法是以EPRC 作為標記。標記交換中以EPRC 作為標記處理單播的通信是可以勝任的，對多播和組播還有待進一步研究。