Dynamical Fast IP-Routing Lookup Algorithm

Abstract

This paper proposes a dynamical fast IP-routing lookup algorithm (DFR). This algorithm uses special data structure to construct index table, and can support inserting, deleting and updating route dynamically. DFR algorithm accesses memory at most four times and at least two times for a route look up. DFR is suitable not only for hardware implementation but also for software implementation.

Content

《1 引言》

1 引言

进入20世纪90年代以来, 因特网业务发展迅猛。随着网络的发展, IP在网络中起着越来越重要的作用。当前, 整个网络呈现用户业务IP化、IP业务综合化、IP技术多样化的趋势。

为了适应未来宽带网络的发展, 世界上各大电信厂商纷纷研制高性能路由器。但是, 因特网的迅猛增长使得路由器中的路由表迅速增长。路由表规模的增长限制了路由器的转发速率。因而路由查找技术成为路由器的关键技术之一, 是衡量路由器性能的重要指标。为了解决路由器速度瓶颈, 近年来, 快速路由查找技术是一个热门课题, 也提出了不少路由查找算法, 如LC算法^[1], 页面压缩 (page compress) 算法^[2], 采用硬件的分级索引算法^[3,4]等。这些算法虽然优化了某些性能, 但都在路由查找的时间复杂度、空间复杂度以及插入、删除和更新路由的速度等三个方面有一定的局限性。一种好的算法应该在这三者之间寻求一种好的平衡。

动态快速路由查找算法 (DFR) 是针对现有算法的不足提出的。它利用前缀扩展的特性, 通过构造特定的数据结构, 使得算法支持动态插入、删除和更新表项。该算法只需最多4次访存就能完成1次查找。通过压缩技术, 该算法需要的存储空间很小, 不仅适合于硬件实现, 也适合于软件实现。

《2 DFR算法原理》

2 DFR算法原理

DFR算法的实现原理主要依据前缀扩展的特性。将一个前缀用前缀/长度来表示, 假定有前缀p/l, 扩展后的前缀长度为m, 且m>l。设前缀p的二进制表示为

$p_{1} p_{2} \dots p_{l}, p_{i} = 0 或 1 。$ $p_{1} p_{2} \dots p_{l}, p_{i} = 0 或 1 。$

将扩展后的前缀的二进制表示为

$p^{'}_{1} p^{'}_{2} \dots p^{'}_{l} p^{'}_{l + 1} p^{'}_{l + 2} \dots p^{'}_{m}, p^{'}_{i} = 0 或 1 。$ $p^{'}_{1} p^{'}_{2} \dots p^{'}_{l} p^{'}_{l + 1} p^{'}_{l + 2} \dots p^{'}_{m}, p^{'}_{i} = 0 或 1 。$

如果p₁p₂…p_l=p′₁p′₂…p′_l, 且p′_l+1p′_l+2…p′_m构成一个完备集合, 则称前缀p为前缀扩展。

前缀扩展的目的是为了把任意长度的前缀变成固定长度的前缀, 扩展的位数可以是任意值。一个前缀经扩展后形成一个集合, 且集合中的前缀在数值上是连续的, 利用这个特性来存放前缀集合, 这种连续性将会简化路由查找操作。通过前缀扩展, 在进行路由查找时可以一次比较多位。根据IP包的目的地中对应位的值, 查到对应位的前缀。

前缀扩展可以按需分段扩展。例如, 对路由器中所有的前缀可以分三段来进行扩展, 第一段可以将所有前缀 <16 b的前缀扩展成16 b位长, 第二段将长度为17 b到24 b的前缀都扩展成24 b位长, 第三段可以将所有长度 >24 b的前缀扩展成32 b位长。前缀扩展增加了前缀表项数, 增加表项数意味着需要更大的存储空间, 但是前缀扩展却能成倍地提高路由查找的速度。

前缀扩展的主要特性包括长度特性、覆盖性和无交叠性。

《2.1长度特性》

2.1长度特性

长度特性是指前缀扩展所覆盖的范围长度刚好是2的指数次幂。如果一个前缀扩展x位, 那么它所覆盖的范围长度将是2^x。

例如有两个前缀01/2和011/3, 将这两个前缀分别扩展成4 b位长, 形成的前缀集合P为

$Ρ = {0100, 0101, 0110, 0111} 。$ $Ρ = {0100, 0101, 0110, 0111} 。$

如果一个前缀p开始扩展了x位, 形成一个前缀集合P, 如果改为扩展x′位, 其中x′<x, 则相当于将所有的前缀缩小2^x-x′倍。所有在数值上不是2^x-x′的整数倍的前缀都是扩展所形成的, 因而也不是路由表中真正存在的前缀, 缩小时则将这些前缀忽略。缩小时必须保证缩小的位数不大于扩展的最小位长, 即不能影响路由表中真正的前缀, 也就是保证缩小后所有的前缀都必须至少有1位扩展位或没有扩展。同样地, 当有多个前缀时, 缩小时不能影响长度最长的前缀。

《2.2覆盖性》

2.2覆盖性

前缀扩展的覆盖性是指, 如果将一个前缀用前缀/长度/输出端口来表示, 假如存在两个前缀p₁/l₁/o₁和p₂/l₂/o₂, 将p₁和p₂分别进行前缀扩展, 形成两个新的集合P₁和P₂, 如果集合P₂是P₁的子集, 那么P₁和P₂的交集部分的输出端口应该为P₂的输出端口o₂。

根据最长前缀匹配原则, 在P₁和P₂的交集部分用P₂的输出端口o₂时, 则需要满足:

$l_{1} \leq l_{2} 。 (1)$ $l_{1} \leq l_{2} 。 (1)$

假设前缀p₁和p₂都被扩展成m位长, 扩展的位数分别为x₁和x₂, 则:

$\begin{array}{l} x_{1} = m - l_{1} ‚ (2) \\ x_{2} = m - l_{2} 。 (3) \end{array}$ $\begin{array}{l} x_{1} = m - l_{1} ‚ (2) \\ x_{2} = m - l_{2} 。 (3) \end{array}$

根据前缀扩展的长度特性, p₁和p₂扩展后所覆盖的范围分别为2^x₁和2^x₂。假定集合P₁和P₂中的最小值分别是S₁和S₂, 由于集合P₂是P₁的子集, 则需要满足以下两式:

$\begin{array}{l} S_{2} \geq S_{1} ‚ (4) \\ S_{1} + 2^{x_{1}} \geq S_{2} + 2^{x_{2}} (5) \end{array}$ $\begin{array}{l} S_{2} \geq S_{1} ‚ (4) \\ S_{1} + 2^{x_{1}} \geq S_{2} + 2^{x_{2}} (5) \end{array}$

设S₂=S₁+Δx, 代入式 (5) 有

$2^{x_{1}} \geq Δ x + 2^{x_{2}}, (6)$ $2^{x_{1}} \geq Δ x + 2^{x_{2}}, (6)$

其中Δx≥0, 故有

$x_{1} \geq x_{2} 。 (7)$ $x_{1} \geq x_{2} 。 (7)$

由式 (2) 和式 (3) 可知l₁≤l₂。

从数轴上看, 一个前缀经扩展后对应数轴上的一条线段, 每条线段就代表一个前缀经扩展后所形成的前缀集合, 集合中的最小值对应线段的起点, 而且扩展后集合中所有的前缀都有相同的下一跳 (Next-hop) 。

用前缀/长度/下一跳来表示一个前缀的属性。假定有两个前缀01/2/3和011/3/5, 将这2个前缀分别扩展成4 b位长, 形成2个前缀集合:

$\begin{array}{l} Ρ_{1} = {0100, 0101, 0110, 0111} ‚ \\ Ρ_{2} = {0110, 0111} 。 \end{array}$ $\begin{array}{l} Ρ_{1} = {0100, 0101, 0110, 0111} ‚ \\ Ρ_{2} = {0110, 0111} 。 \end{array}$

它们在数轴上的表示如图1所示。

《图1》

图1多个前缀扩展的数轴表示

Fig.1 Presentation of several prefix expansion on the axis

如果要为0111查找下一跳, 根据最长匹配原则, 相匹配的前缀应该是011/3/5, 而不应该是01/2/3, 因为011/3/5匹配得更长。

前缀扩展的覆盖性使得路由查找支持最长前缀匹配。在进行前缀扩展时, 扩展后的重叠区域的下一跳路由信息将会是该区域内有最大长度的前缀, 从而保证了路由查找时的最长匹配。同时在进行路由更新时也将会只对局部范围进行更新, 从而简化了路由更新操作。当两个前缀经扩展后, 如果一个前缀集合是另一个前缀集合的子集, 而且这两个前缀有相同的下一跳路由信息, 在生成路由转发表时, 可以将这两个前缀进行合并, 在数轴上看, 将只有一个前缀的下一跳路由信息。

《2.3无交叠性》

2.3无交叠性

如果前缀用前缀/长度来表示, 假如存在2个前缀p₁/l₁和p₂/l₂, 将p₁和p₂分别进行前缀扩展, 形成2个新的集合P₁和P₂, 如果集合P₂中最小的元素属于P₁, 但集合P₁中最小的元素不属于P₂, 那么P₂中最大的元素也属于P₁。

假设前缀p₁和p₁都扩展成m位长, 集合P₁和P₂中最小元素的二进制表示分别为:

$\begin{array}{l} a_{1} a_{2} \dots a_{l} \underset{m - l_{1} 个 0}{00 \dots 0} ‚ a_{i} = 0 或 1 ； \\ b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 0}{00 \dots 0} ‚ b_{i} = 0 或 1 。 \end{array}$ $\begin{array}{l} a_{1} a_{2} \dots a_{l} \underset{m - l_{1} 个 0}{00 \dots 0} ‚ a_{i} = 0 或 1 ； \\ b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 0}{00 \dots 0} ‚ b_{i} = 0 或 1 。 \end{array}$

由于 $b_{1} b_{2} \dots b_{l_{1}} b_{l_{1} + 1} \dots b_{l_{2}} \underset{m - l_{2} 个 0}{00 \dots 0} \in Ρ_{1}$ $b_{1} b_{2} \dots b_{l_{1}} b_{l_{1} + 1} \dots b_{l_{2}} \underset{m - l_{2} 个 0}{00 \dots 0} \in Ρ_{1}$ , 故

$a_{i} = b_{i}, i = 1, \dots, l_{1} 。 (8)$ $a_{i} = b_{i}, i = 1, \dots, l_{1} 。 (8)$

根据前缀扩展的定义, 集合P₁和P₂中最大元素的二进制可以分别表示为:

$\begin{array}{l} a_{1} a_{2} \dots a_{l_{1}} \underset{m - l_{1} 个 1}{11 \dots 1}, a_{i} = 0 或 1 ； \\ b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 1}{11 \dots 1} ‚ b_{i} = 0 或 1 。 \end{array}$ $\begin{array}{l} a_{1} a_{2} \dots a_{l_{1}} \underset{m - l_{1} 个 1}{11 \dots 1}, a_{i} = 0 或 1 ； \\ b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 1}{11 \dots 1} ‚ b_{i} = 0 或 1 。 \end{array}$

由式 (8) 可知

$a_{1} a_{2} \dots a_{l_{1}} \underset{m - l_{1} 个 1}{11 \dots 1} \geq b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 1}{11 \dots 1} 。 (9)$ $a_{1} a_{2} \dots a_{l_{1}} \underset{m - l_{1} 个 1}{11 \dots 1} \geq b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 1}{11 \dots 1} 。 (9)$

由前缀扩展的完备性可知

$b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 1}{11 \dots 1} \in Ρ_{1} 。$ $b_{1} b_{2} \dots b_{l_{1}} \underset{不全为 0}{b_{l_{1} + 1} \dots b_{l_{2}}} \underset{m - l_{2} 个 1}{11 \dots 1} \in Ρ_{1} 。$

这就说明如果集合P₂中最小的元素属于P₁, 但集合P₁中最小的元素不属于P₂时, P₂中最大的元素也属于P₁。前缀扩展的无交叠性说明不会出现图2所示的情况。

《图2》

图2 前缀扩展的无交叠性Fig.2 Non-overlapped characteristic of prefix expansion

前缀扩展的无交叠性使得两个前缀要么没有重叠, 要么一个前缀扩展后的集合是另一个前缀扩展后的集合的子集。如果知道前缀扩展的起点位置和扩展的位数, 就很容易计算终点位置。在插入、删除和更新路由时, 可以利用前缀扩展的无交叠性来进行局部操作, 从而减小操作范围, 提高插入、删除和更新速度。

《3 DFR算法设计》

3 DFR算法设计

DFR算法采用两级索引3次查找结构来构建索引表。

《3.1一级索引表的结构》

3.1一级索引表的结构

DFR算法将IP地址的前16 b的完备集合形成一级索引, 共65536个表项构成一个线性表, 每个表项用4 B表示, 将4 B分为4部分:标记、掩码长度/指针、输出端口、偏移量。格式如图3所示。

《图3》

图3一级索引表结构

Fig.3 Structure of the first level index table

标记标记用来识别该项是否存在一个前缀经扩展后形成的起点位于该项。当标记位为1时, 表示有某个前缀长度 ≤16 b的前缀经扩展后形成的起点位于该项, 否则标记为0。

掩码长度/指针掩码长度/指针域用来记录掩码信息或下一级索引的头指针, 该域存放的信息与偏移量的值相关。当偏移量为零时, 没有二级索引表, 如果有某个前缀经扩展后的起点位于该表项, 那么一级索引的第5—20位 (16 b) 用于记录起于该点的前缀的长度。将这16 b分为4组, 每4位记录一个掩码, 共记录4个掩码, 并将掩码长度域中的掩码按自左至右依次减小的顺序放置。

当偏移量>0时, 此时一级索引中存放的是指针, 第1位仍然用作标记, 低4 b用作记录偏移量, 将第2—28位用于存放二级索引的指针, 指针域共27 b。此时如果需要查找二级索引就可以通过指针域中的指针来查找下一级索引表。

输出端口输出端口用于存放下一跳信息。将一级索引表项中的第21—28位用于记录端口索引。在进行路由查找时, 查找到输出端口就能查找到完整的下一跳路由信息。

偏移量偏移量是前缀长度减去16 b所得到的值, 这里要求前缀长度 > 16 b, 如果前缀长度 < 16 b, 可以直接在一级索引中存放输出端口, 此时偏移量不起作用。设前16 b相同的前缀形成的集合为P, 前缀P_i是集合P中的元素, 设P_i的前缀长度为l_i, 则偏移量k_i=l_i-16, 设k_max∈k_i且k_max≥ k_i, 因此k_max是集合P中最大的偏移量, 一级索引中的偏移量域中存放的是这个最大的偏移量。当偏移量为0时, 表示没有二级索引, 此时可以直接通过一级索引中的输出端口查找到下一跳, 当偏移量 > 0时, 表示该一级表项中有前缀长度 >16 b的前缀存在, 此时的路由信息存放在二级索引表中, 需要通过二级索引表来进行查找。

《3.2二级索引表结构》

3.2二级索引表结构

当偏移量 > 0时, 存在二级索引。二级索引结构如图4所示。二级索引主要包括码字数组CWA和压缩下一跳数组CNHA两大部分, 其中CWA由多个码字CW组成, CNHA由多个下一跳索引NHI组成。当一级索引的标记位为1时, 二级索引的头部有一个2 B的掩码记录MR, 二级索引头部的掩码记录用来记录一级索引中长度<16 b的前缀的掩码长度, 当一级索引的标记位为0时, 二级索引中不需要头部的MR。

《图4》

图4二级索引表结构

Fig.4 Structure of the second level index table

每个CWA包含一个Map和Base。Map是由于采用压缩技术后形成的一个位映射, Map中的每一位顺序对应完整的二级索引表的每个表项, 每个1对应一个前缀扩展的起点或终点的下一位。Base表示此CWA之前的Map中累积的1的个数, 第一个CWA的Base为0。每个Map和Base的长度都是2 B (16 b) 。当偏移量<5时, 由于最多有2⁴=16个二级索引表项, 此时用一个Map来存放二级索引表的位映射就足够了, 因此可以省去2字节的Base。

每个CNHA包含掩码记录MR和输出端口OP两部分。MR用2 B来表示, 每4 b记录一个掩码长度, 共能记录4次重叠。注意, NHI中的掩码记录和二级索引表头部的掩码记录的意义不一样。NHI中的掩码记录是用来记录二级索引表中前缀的偏移量的, 而头部的掩码记录是用来记录一级索引表中的前缀长度的 (如果一级索引的标记位为1) , 因为当存在二级索引表时, 一级索引表中存放的是二级索引表的头指针, 不能存放掩码记录, 此时把一级索引表中对应的掩码记录转移到二级索引表的头部。输出端口用1个字节来表示, 输出端口只是一个下一跳路由的索引, 通过输出端口可以找到下一跳路由信息。每个Map中的1顺序对应一个下一跳索引 (NHI) 。

从图4中可以看到, 在第一个CW之前有一个最大端口数 (MP) 和一个实际端口数 (RP) , MP和RP只有当偏移量 > 4时才存在。最大端口数用于存放当前CNHA中能容纳的最大端口索引的数目, 实际端口数用于存放当前CNHA中实际存放的端口索引的数目, MP和RP各为2 B。设置这两个域的目的是为了提高插入和删除路由的速度, 如果每次添加或者删除路由表项都重构二级索引表, 使得效率很低, 为了尽量减小重构二级索引表的频率, 为CNHA预留一定的空间, 只有当预留的空间全部用完时才重构二级索引表。当一级索引的偏移量<5时, 由于最多只有2⁴=16个二级索引表项, 也就是只有16个位映射对应一个Map, 因此存在的NHI的数目很小, 如果出现添加或者删除路由表项, 这种操作的复杂度并不大, 因此当一级索引的偏移量<5时出现添加或删除表项的操作将重构二级索引表, 此时也就不需要为CNHA预留空间。

《3.3前缀扩展范围的计算》

3.3前缀扩展范围的计算

由于前缀扩展的覆盖性, 在进行路由插入、删除和更新操作时需要知道前缀扩展的范围, 前缀扩展范围的计算可以利用前缀及其掩码来计算扩展范围的起点和终点。一级索引表和二级索引表都应该分别计算前缀的扩展范围。

对二级索引表, 将前16 b相同的前缀形成一个集合, 记为P。如把192.1.X.X的有相同前缀192.1的IP地址归为一类。这些IP地址在一级索引里位于同一组, 从具有相同一级索引的IP地址 (即前16 b相同) 中选取一个最长的前缀, 设其前缀长度为l_m, l_m-16为偏移量, 设为k, 每个一级索引最多对应2^k个二级索引表项。这样, 二级索引的表项数将是动态变化的, 随着前缀长度的不同而不同。

设集合P中前缀p_i的前缀长度为l_i, 其输出端口为h_i , 并设

$o_{i} = l_{i} - 16, k = \max {o_{i} | p_{i} \in Ρ}, (10)$ $o_{i} = l_{i} - 16, k = \max {o_{i} | p_{i} \in Ρ}, (10)$

其中P是前16 b相同的前缀的集合。

设p_i=a.b.x.y, 用x₀, x₁, x₂, …, x₁₅代表x.y的二进制形式。如果将P_i的掩码从第17位起截取k位, 并用s₀, s₁, s₂, …, s_k-1代表截取的掩码的起点, 其中, 当j<o_i时, s_j=1, 当j≥o_i时, s_j=0。用e₀, e₁, e₂, …, e_k-1代表截取的掩码的终点, 其中, 当j<o_i时, e_j=0, 当j≥o_i时, e_j=1。由于前缀扩展的起点位置所对应的扩展位都为0, 因此有:

$\begin{array}{l} Μ (S_{i}^{0}) = (x_{0}, x_{1}, x_{2}, \dots, x_{k - 1} A Ν D \\ s_{0}, s_{1}, s_{2}, \dots, s_{k - 1}) 。 (11) \end{array}$ $\begin{array}{l} Μ (S_{i}^{0}) = (x_{0}, x_{1}, x_{2}, \dots, x_{k - 1} A Ν D \\ s_{0}, s_{1}, s_{2}, \dots, s_{k - 1}) 。 (11) \end{array}$

根据前缀扩展的特性, 扩展后的终点位置对应的扩展位必定是全1, 因此可以计算终点对应的物理存储地址为:

$\begin{array}{l} Μ (E_{i}^{0}) = (x_{0}, x_{1}, x_{2}, \dots, x_{k - 1} Ο R \\ e_{0}, e_{1}, e_{2}, \dots, e_{k - 1}) 。 (12) \end{array}$ $\begin{array}{l} Μ (E_{i}^{0}) = (x_{0}, x_{1}, x_{2}, \dots, x_{k - 1} Ο R \\ e_{0}, e_{1}, e_{2}, \dots, e_{k - 1}) 。 (12) \end{array}$

对每个IP地址P_i都有一对S $_{i}^{0}$ $_{i}^{0}$ 和E $_{i}^{0}$ $_{i}^{0}$ 与它相对应, 处于地址段[M (S $_{i}^{0}$ $_{i}^{0}$ ) , M (E $_{i}^{0}$ $_{i}^{0}$ ) ]中的IP地址都有相同的下一跳路由。由于经前缀扩展后, 就会存在地址重叠的问题, 根据前缀扩展的覆盖性, 长度越短的前缀覆盖的范围越大, 如果一个前缀p₂经扩展后处于p₁的扩展范围之内, p₁的下一跳路由为h₁, p₂的下一跳路由为h₂, 则处于p₂的扩展范围之内的IP地址的出口应该为h₂。

对一级索引表同样可以采用以上方法来计算前缀扩展的起点和终点, 根据计算的起点和终点位置对起点与终点之间的端口进行更新, 从而减小了更新范围和更新时间。

《3.4压缩原理与压缩方法》

3.4压缩原理与压缩方法

假定一级索引的偏移量为k, 当直接构建时, 二级索引的表项数将是2^k, 前缀扩展后的前缀集合中每个前缀对应1个二级索引表项。在每个前缀扩展的范围内都有相同的输出端口, 如果有些范围没有被扩展后的前缀所覆盖, 将在其中填入默认输出端口。

当偏移量较大时, 直接构建的二级索引表比较大, 由于在前缀扩展的范围内输出端口相同, 在相应的物理空间中对应连续的端口索引号, 如果连续的端口索引号能用一个端口号来表示, 就可以省下大量的空间。方法是用一个位来标记每个输出端口, 连续端口的第一个端口对应的位被置为1, 以后连续相同的端口都置0, 每两个相邻的1之间的位对应相同的输出端口。通过压缩, 形成了一个位映射。将位映射分成每16 b一组, 每组后面跟一个2 B的Base, 每16 b的映射 (Map) 和2 B的Base就形成一个压缩码字CW。

假如有位映射为100000001000000000000 00010001000…, 那么形成的码字数组如图5所示。第一个Base为0, 由于第一个CW的Map中有2个1, 所以第二个CW的Base为2, 当前CW中的Base为前面所有CW中1累积的个数。

《图5》

图5CWA的形成

Fig.5 Formation of CWA

《4 DFR算法实现》

4 DFR算法实现

《4.1算法数据结构》

4.1算法数据结构

为了减小存储空间和实现操作上的便捷性, 算法采用特殊的数据结构。一级索引表的每个表项用4 B来表示, 根据标志位的值和偏移量的不同, 各个字段的安排有所不同。

二级索引表将CWA和CNHA作为一个整体, 放在一个线性表中, CWA的空间可以计算, 假设偏移量是k, 那么CWA所需要的字节数为4×2^k-4=2^k-2, 其中k>4;如果k≤4, 那么CWA结构需要作一些变化, 此时由于只有1个Map, 因此省去Base, 这时CWA所占的字节数是2 B的空间。在最后一个CW之后是第一个NHI, 每个NHI包括一个2 B的MR和一个1 B的下一跳端口索引号, 为了能重构二级索引, 每个NHI都采用这种结构。当k>4时, 在二级索引的头部有一个最大端口数和一个实际端口数, 分别为2 B, 如果一级索引的标志位为1, 在最大端口数之前有一个2 B的掩码记录, 用来记录一级索引中对应的掩码。可以通过标志位来判定二级索引是否存在一个头部的掩码记录, 通过偏移量来判定是否存在最大端口数和实际端口数。

定义CW的数据结构为:

《图6》

《图7》

以上数据结构的定义采用与Future 协议源码的定义风格相一致的定义方式, 是为了兼容和将来的升级替换。

《4.2一级索引表的构建》

4.2一级索引表的构建

构建一级索引表时, 将所有的前缀扩展到16 b位长。在一级索引实现插入操作时, 首先计算前缀 (假设为a) 扩展的起点和终点, 然后在起点和终点间逐个表项操作, 对每个表项, 首先检查标志位, 如果该位为1, 说明有另一个前缀 (假设为b) 也起于该点, 如果a的扩展范围大于b, 对前缀b扩展范围内的端口索引不改变。对前缀b扩展范围内的输出端口进行保护的最好方法是确定它的扩展范围, 并跳过这个范围。

如果在添加的起点位置还有其他的前缀也起于该点, 则首先需要确定是更新路由还是添加新的路由, 如果前缀的掩码长度与掩码记录中某个掩码长度相同, 则说明是更新情况, 此时需要确定更新范围, 如果有某个前缀的长度大于当前前缀长度, 则计算该前缀的终点, 然后从终点加1的位置起开始更新, 后面的更新操作同上。

《4.3二级索引表的构建》

4.3二级索引表的构建

在二级索引表中也存在前缀扩展的覆盖问题和起点重叠的问题, 由于二级索引的结构和一级索引表不同, 并采用了压缩技术, 因此在实现路由插入、删除和更新时需要首先找到起点和终点位置对应的位映射位和对应的下一跳索引 (NHI) 。

《4.3.1 插入操作》

4.3.1 插入操作

插入操作主要包括两种情况:更新和插入新路由。

1) 更新操作

更新操作首先计算前缀扩展的起点m (S $_{i}^{0}$ $_{i}^{0}$ ) 和终点m (E $_{i}^{0}$ $_{i}^{0}$ ) , 并根据m (S⁰_i) 的值计算起点所在的码字W (S $_{i}^{0}$ $_{i}^{0}$ ) 和在对应的Map中的位B (S $_{i}^{0}$ $_{i}^{0}$ ) , 根据W (S $_{i}^{0}$ $_{i}^{0}$ ) 中Base的值和Map中B (S $_{i}^{0}$ $_{i}^{0}$ ) 之前Map中1的个数来确定起点对应的下一跳索引 (NHI) , 然后根据NHI中的掩码记录MR来确定是否是更新操作。类似地, 计算终点m (E $_{i}^{0}$ $_{i}^{0}$ ) 所在的码字W (E $_{i}^{0}$ $_{i}^{0}$ ) 和对应的Map中的位B (E $_{i}^{0}$ $_{i}^{0}$ ) , 然后更新码字W (S⁰_i) 和W (E $_{i}^{0}$ $_{i}^{0}$ ) 所对应的起点和终点的位B (S $_{i}^{0}$ $_{i}^{0}$ ) 和B (E $_{i}^{0}$ $_{i}^{0}$ ) 之间的内容及其对应的端口索引。

2) 插入新路由

如果插入路由的偏移量k小于最大偏移量K_m, 且K_m>4, 则判断起点与终点的重叠情况, 根据判断确定插入的端口索引的个数来确定是否需要重新构建二级索引表。如果K_m≤4或者k>K_m, 重新构建二级索引表。

判断起点和终点是否重叠的方法是检查起点对应的Map中的位被置为1, 则说明起点重叠, 否则不重叠;终点重叠的判别是检查终点对应位的下一位被置为1, 则说明重叠, 否则不重叠。如果起点重叠而终点不重叠, 或者起点不重叠而终点重叠, 则需要增加1个输出端口索引;如果起点和终点都不重叠, 则需要增加2个输出端口索引。插入新路由不会出现起点和终点都重叠的情况, 因为这可以作为更新路由的情况来处理。

对k≤K_m且K_m>4的情况, 二级索引的头部有1个最大端口数MP和实际端口数RP。此时首先判断添加的端口索引的个数n, 如果RP中的值与n的和大于MP中的值, 此时重构二级索引表, 否则, 更新二级索引表。

当起点重叠时, 只需在起点所对应的NHI中的掩码记录中添加前缀的偏移量值, 从起点到终点间的操作同更新情况, 要考虑前缀扩展的覆盖性, 在终点位置, 将终点对应位的下一位置1, 因为下一位所对应的下一跳索引不同, 并在终点对应的NHI之前插入1个新的NHI。

对终点重叠情况, 类似于起点重叠情况, 不同的是要将起点对应的位设置为1, 并在起点对应的NHI之后添加1个下一跳路由信息, 并将前缀的偏移量添加到掩码记录中, 并将它后面所有的NHI后移1个NHI的位置。

起点和终点都不重叠的情况属于以上2种情况综合。

对k≤K_m且K_m>4, 但是RP的值与添加的下一跳路由数之和大于MP的值的情况, 需要重新构建二级索引表。重构二级索引表时只需增加相应的输出端口索引的个数, 其他和原来的二级索引表一样, 将原二级索引表的CNHA之前的部分都复制到新表中, 根据重叠情况, 将起点和终点对应位的下一位相应地置1, 然后将原表的CNHA的相应部分复制到新表中, 并在起点与终点相对应的位置添加NHI, 这样就构成了新的二级索引表。

对k>K_m且k≤4或者k≤K_m且K_m≤4的情况, 只用1个Map就能存放所有的信息, 此时不需要码字中的Base, 也就是此时只用1个2 B的Map来存放位映射就可以了。

对k>K_m且K_m>4的情况, 需要重新分配CWA的空间, 分配时根据k的值来计算, CWA所需的空间是2^k-2个字节, 再根据RP的值与要添加的端口索引的个数来确定需要分配的最大端口数的值, 从而可以计算需要分配的二级索引表的空间大小。对这种情况, 关键是如何将原表的CWA构建成新表的CWA。从原表的CWA构建成新表的CWA需要利用前缀扩展的长度特性, 前缀扩展的长度特性表明, 前缀每扩展1位, 扩展后的起点对应的值扩大1倍。构建时, 可以先将新表全部清零, 然后将原表中每个1对应的位置扩大1倍, 并将新表中相应的位置设置为1。

《4.3.2 删除操作》

4.3.2 删除操作

删除操作需要在删除前缀的扩展范围内填充一个适当的输出端口, 因此删除操作要解决的关键问题就是确定一个替代输出端口。

1) 一级索引表前缀的删除

删除一级索引表中的前缀时, 首先要检查删除前缀对应的起点和终点的重叠情况。起点重叠只要检查起点对应的NHI的掩码记录就可以。终点重叠需要检查删除前缀的扩展范围内所有表项, 检测的最大范围是256。如果有某个前缀的起点位于删除前缀的扩展范围内, 计算其前缀扩展的终点, 如果终点和删除前缀的终点相同, 则说明终点重叠。

对起点重叠、终点不重叠的情况, 将起点对应的表项的掩码记录中要删除前缀的掩码删除, 并将删除前缀扩展范围内的相应表项的输出端口替换为适当的输出端口就完成了操作。

对起点不重叠、终点重叠的情况, 将起点对应的输出项的标志位清零, 并将起点到终点间所有项的输出端口都改为适当的替代输出端口。

对起点与终点都重叠的情况, 用将删除前缀的起点对应的表项中的掩码记录更新, 将要删除前缀的偏移量从掩码记录中删除, 然后在起点与终点间更新相应表项的输出端口索引就完成删除操作。

对起点和终点都不重叠的情况, 删除前缀要求将起点对应的表项的标志位清零, 再查找替代输出端口, 然后将起点到终点之间所有表项的输出端口索引改为替代输出端口。

2) 二级索引表前缀的删除

假设删除前缀的偏移量为k, 最大偏移量K_m, 当K_m>4时, 设最大端口数MP的值为m, 实际端口数RP中的值是n。删除二级索引表中的前缀主要有以下几种情况:

情况1 k≤K_m, 且K_m≤4。此时需要重新构建二级索引表, 二级索引表的构建需要根据重叠情况来分配存储空间。由于K_m≤4, 此时只有一个2 B的Map, 没有Base, 二级索引表的头部也没有MP和RP, 因此对Map的操作比较简单, 此时的删除操作主要是对NHI进行操作。

情况2 k<K_m, 且K_m>4。此时二级索引表的头部有一个MP和一个RP, 当删除一个前缀时, 要根据删除前缀的重叠情况和RP的值来判断是否需要重新构建二级索引表。假设要删除的NHI的个数为d, 当起点重叠而终点不重叠或起点不重叠而终点重叠时, d=1;起点与终点都不重叠时, d=2;起点与终点都重叠时, d=0。如果n-d小于某一常数c (比如10) , 此时只需要对二级索引表进行更新就可以, 如果n-d≥c, 则需要重新构建二级索引表。

情况3 k=K_m, 且K_m>4。由于k=K_m, 说明删除的是具有最大偏移量的前缀, 具有最大偏移量的前缀在数轴上的表示是一个点, 因此需要找到某个前缀, 它的偏移量不大于最大偏移量, 但大于所有其他前缀的偏移量, 然后再将它作为新的最大偏移量 (设为k′) 来构建二级索引表。如果k′=k, 则采用和情况2同样的方法来判断是否需要重新构建二级索引表, 操作方法也完全一样。这里只讨论k′<k时重构二级索引表的情况。

k′<k时, 需要缩小二级索引表, 设删除前缀的值为v, MP的值为m, RP的值为r, 要删除的NHI的个数为n, 同样地, 根据重叠情况来确定n的值。如果r-n<c (c为某个常数) , 则重新分配的二级索引表的空间为

$2^{k^{'} - 2} + 3 m + 4 。$ $2^{k^{'} - 2} + 3 m + 4 。$

如果r-n>c, 则重新分配的二级索引表的空间为

$2^{k - 2^{'}} + 3 (m - c) + 4 。$ $2^{k - 2^{'}} + 3 (m - c) + 4 。$

k′<k时重构二级索引表的关键是如何确定k′及如何将原表中的1映射到新表中。

k′确定的方法是从第一个NHI开始, 逐个检测r个NHI的掩码记录 (不包含删除前缀对应的NHI) , 找到一个最大的偏移量, 它就是k′。

将原表中Map中的1映射到新表中, 需要利用前缀扩展的长度特性来确定它在新表中的位置。假设某个前缀的起点对应的值是w, 前缀扩展缩小的倍数e=2^k-k′, 则该前缀的起点在新表中对应的位置为p=w/e (一定是整数) , 则p对应的Map为p/16 (向下取整) , 对应的位b为p mod 16, 将相应的位设置为1。

由于在删除操作时, 除了要删除的前缀外, 其他所有前缀都至少扩展了k-k′位, 每个前缀在原表中覆盖的范围至少是e=2^k-k′, 因此检测位时可以一次跨越e个位来检测。

《4.4快速查找》

4.4快速查找

DFR算法的查找操作最多4次访存就能找到下一跳信息。首先根据IP地址的高16 b来确定一级索引, 当偏移量为0时, 直接找到对应的端口索引, 通过端口索引查找下一跳路由信息。当偏移量 > 0时, 通过一级索引的指针域查找二级索引表, 根据目的地址可以确定目的地址在二级索引中对应的CWA和NHI。查找过程如图6所示。图中V (B⁰₁₅) 和V (B $_{15 + k}^{16}$ $_{15 + k}^{16}$ ) 分别表示目的地址的第0—15位的值和第16— (15+k) 位的值, pSecIndex表示二级索引的首指针。

《图8》

图6路由查找的实现过程

Fig.6 Implementation of Route Lookup

《5 DFR算法性能分析》

5 DFR算法性能分析

《5.1空间复杂度》

5.1空间复杂度

设一级索引的偏移量为k, 二级索引中NHI的个数为n, 由二级索引表的数据结构可以计算, 当k>4时, 二级索引的NHI的个数是常数c的整数倍, 即n=λc, λ为整数, 此时二级索引表的存储空间为

$m_{1} = 2^{k - 2} + 3 λ c + 4 。 (13)$ $m_{1} = 2^{k - 2} + 3 λ c + 4 。 (13)$

当K≤4时, 只有一个2 B的Map和NHI, 因此二级索引表的存储空间为

$m_{2} = 2 + 3 n 。 (14)$ $m_{2} = 2 + 3 n 。 (14)$

根据因特网中前缀分布的特征, 通过以上公式可以计算, 构建整个转发表所需要的存储空间的量很小, 只需要800 kB ～ 1 MB就能存放一个有40 000条路由表项的路由表。

《5.2查找操作的时间复杂度》

5.2查找操作的时间复杂度

DFR算法的查找操作较为简单, 进行一次路由查找最多4次访存, 最少只需要2次访存。对400 MHz的CPU, 平均4次访存约需100 ns, 查找速度可达到10 Mp/s (packet per second) , 如果2次访存就能查找成功, 那么, 查找速度能达到20 Mp/s。在多任务的操作系统环境下, 考虑到代码的执行时间, 实际查找速度要慢些。

用DFR算法分别对500, 1 500, 3 500, …, 9 500 条路由的添加情况分别进行了仿真测试。对以上各组数据, 分别测试了前缀长度为8～16 b和8～24 b的情况。表1给出了DFR算法的仿真结果, 并给出了与其他算法的比较。

《6 结论》

6 结论

DFR算法利用前缀扩展的特点, 通过构造特定的数据结构来构建路由表, 使得该算法支持动态插入和删除路由表项。DFR算法的特点是:访存次数少, 存储空间小, 支持动态插入、删除和更新路由, 较好地处理了时间复杂度和空间复杂度的关系。由于以上特点, DFR算法不仅适合软件实现, 也适合硬件实现。

表1算法比较

Table 1 Comparison of algorithms

《图9》

Show More