以路由緩存表項(xiàng)指針作標(biāo)記的標(biāo)記交換探析

劉永強(qiáng)

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

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

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

1 MPLS 及IPLS 的引入

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

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

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

2 標(biāo)記的概念

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

從本質(zhì)上看，交換是指交換節(jié)點(diǎn)根據(jù)數(shù)據(jù)分組攜帶的標(biāo)記，按照某種設(shè)定的輸入輸出關(guān)系，對(duì)分組進(jìn)行處理的過(guò)程，以求在源與目的之間建立一條數(shù)據(jù)通道。可見，輸入輸出關(guān)系的高效利用是關(guān)鍵所在，這種關(guān)系的建立則可以采用各種有效的路由算法，與分組的處理是分離的。交換機(jī)與路由器中的這種輸入輸出關(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 以路由緩存表項(xiàng)入口指針作標(biāo)記

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

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

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

3.1 選取EPRC 作標(biāo)記的出發(fā)點(diǎn)

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

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

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

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

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

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

為增強(qiáng)EPRC 的兼容性，采用對(duì)IPv4 數(shù)據(jù)分組的選項(xiàng)[4]（Options）進(jìn)行擴(kuò)展。

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

圖1 IP 選項(xiàng)類型組成

表1 選項(xiàng)類型定義

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

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

圖2 IP 選項(xiàng)

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

圖3 路由緩存項(xiàng)定義

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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