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

劉永強

（江蘇海洋大學(xué)，江蘇連云港 222005）

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

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

1 MPLS 及IPLS 的引入

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

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

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

2 標記的概念

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

從本質(zhì)上看，交換是指交換節(jié)點根據(jù)數(shù)據(jù)分組攜帶的標記，按照某種設(shè)定的輸入輸出關(guān)系，對分組進行處理的過程，以求在源與目的之間建立一條數(shù)據(jù)通道?？梢姡斎胼敵鲫P(guān)系的高效利用是關(guān)鍵所在，這種關(guān)系的建立則可以采用各種有效的路由算法，與分組的處理是分離的。交換機與路由器中的這種輸入輸出關(guān)系建立方法可以不同，可使用的協(xié)議有許多，如路由信息協(xié)議（RIP）、內(nèi)部網(wǎng)關(guān)路由協(xié)議（IGRP）、開放式最短路徑優(yōu)先協(xié)議（OSPF）、外部網(wǎng)關(guān)協(xié)議（EGP）和邊界網(wǎng)關(guān)協(xié)議（BGP）等。

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

對于主干網(wǎng)節(jié)點上的一個待發(fā)送的數(shù)據(jù)分組，IP層大致完成如下過程：①從傳輸層或數(shù)據(jù)鏈路層接收數(shù)據(jù)分組并進行一定的處理；②在所連接的網(wǎng)絡(luò)中使用一定的路由算法選擇數(shù)據(jù)包傳輸?shù)南乱惶虎郯褦?shù)據(jù)分組交予數(shù)據(jù)鏈路層的驅(qū)動程序。其中第②步根據(jù)IP 地址經(jīng)過一定的計算，然后到龐大的路由表中進行檢索，以得到該數(shù)據(jù)分組的下一跳，這一步十分費時，是路由器的瓶頸。

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

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

3.1 選取EPRC 作標記的出發(fā)點

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

3.2 IP 數(shù)據(jù)分組轉(zhuǎn)發(fā)性能的提高

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

3.3 EPRC 的應(yīng)用限制

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

4 標記在IP 網(wǎng)絡(luò)中的承載

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

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

圖1 IP 選項類型組成

表1 選項類型定義

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

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

圖2 IP 選項

路由緩存項的結(jié)構(gòu)在內(nèi)核源代碼srcin clude et oute.h中的定義如圖3所示。

圖3 路由緩存項定義

EPRC 在網(wǎng)絡(luò)層而非鏈路層實現(xiàn)，只需修改部分的路由軟件，無須增加硬件設(shè)備。EPRC 在IPv6 中同樣有合適的承載。

5 標記的分配、分發(fā)與操作

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

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

路由緩存結(jié)構(gòu)關(guān)系如圖4 所示。

圖4 路由緩存結(jié)構(gòu)關(guān)系圖

涉及的主要數(shù)據(jù)結(jié)構(gòu)包括如下幾點：struct rt_hash_bucket rt_hash_table、struct rtable、struct dst_en try和變量rt_hash_mask。EPRC的保存可采用在結(jié)構(gòu)rtable中新增對應(yīng)的指針，形如struct rtable*eprc，初始化為null。

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

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

當有IP 數(shù)據(jù)分組需要輸出時，在搜索路由緩存項成功返回后，如果保存有下一跳的eprc，則其組裝進IP分組的選項內(nèi)一并轉(zhuǎn)發(fā)出去。

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

6 結(jié)束語

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