网络设备硬核技术内幕 路由器篇 7 汤普金森漫游网络世界(下)

(本篇仿照了美国科学家乔治·盖莫夫在《物理世界奇遇记》中的写作手法，在此致敬)

上回说到，由于路由器转发平面找不到汤普金森先生对应的FIB表项，把汤普金森先生送去了主控板。

主控板的CPU历经千辛万苦，终于找到了汤普金森先生对应的路由表项。

那么，CPU是如何为汤普金森先生找到路由表项的呢？

原来，CPU存储和检索路由表项的方法，与NP线卡存储FIB表的方法，有着根本的区别。

前面提到，NP线卡上的FIB表项，是存储在TCAM处理器中的。

由于TCAM可以将Key的某些位设为not care，因此可以用于实现FIB表的最长匹配查找。

但是，主控板上的RIB(Route Information Base，路由信息库)，是只能保存在DRAM里的。这是为什么呢？

原来，RIB的大小远远大于FIB。

实际操作过企业级和电信级路由器的同学一定有印象，在这些路由器中，EBGP，iBGP，OSPF，IS-IS等路由协议是可以互相导入的。也就是说，同样的路由会在多个路由表中出现。这样一来，路由表的数量会大大多于FIB表。因此，只有近期匹配过数据包的路由条目，才会被下发到转发平面高成本的TCAM存储的FIB表中，其余的路由条目存储在主控板的RAM中。对于高端路由器，主控板能够存储的路由条目数可多达20M以上，而线卡上的FIB条目受限于TCAM容量，一般在256K-4M之间。

那么，主控板的CPU应该如何在海量的路由表中，以最快的速度找到最长匹配路由呢？

方法1：通过一种叫做Radix Tree的数据结构组织路由表项的索引。它可以在近似O(1)的时间里实现最长匹配。

方法2：在主控板的CPU上，外挂较小的TCAM，仅用来存储路由表项的索引。查找到路由表的索引后，再去RAM中读取对应的路由表。如下图所示：

CPU通过路由前缀，快速从TCAM内读取到DRAM中存储该路由信息的偏移量，再去DRAM中读取该条路由信息，这样可以利用较少的TCAM资源，节约大量在RAM中查询Radix Tree的时间。

正是这样的过程，让主控板的CPU能够为汤普金森先生找到出路。

汤普金森先生被扔回到NP芯片的传送带里。机器人扫了扫汤普金森先生的二维码，念道：“源地址 123.112.90.43，目的地址 75.126.33.156”

机器人身后的TCAM箱上的指示灯闪烁了一下，机器人继续念：下一跳：90.182.73.116，出接口：GigabitEthernet 3/0/1”，并在汤普金森先生身上贴了个新的二维码。

绿洲精灵看了看汤普金森先生身上的二维码，不禁倒吸一口凉气。

二维码上还写着：入接口：HundredGigabit 0/0/1。

而这里，正是槽位0，来自100G以太网接口的汤普金森先生将被送去槽位3，并从千兆接口挤出去。

汤普金森先生被机器人夹起来，送去一个排着长龙的队尾，人多得仿佛像早上8点的西二旗地铁站。

“这里就是NP的队列。”绿洲精灵告诉汤普金森先生，“NP支持VoQ队列，对每个出方向的接口都有一个虚拟的队列。”

“我们在槽位0，去槽位3的GE 3/0/1需要经过交换网板。但，这个接口现在拥塞状态，你看数据包都挤得跟豆包似的……”

汤普金森先生问：“为什么会拥塞呀？”

“能不嘛，你看你这来自100G接口的，非要从1G接口出去。”绿洲精灵翻了翻白眼。“和你一样要去那个接口的还很多，超过了1G的速率，所以……”

“所以，本线卡去往GE 3/0/1的VoQ队列信用不足，现在开始按WRED方式丢包！”绿洲精灵话音未落，机器人插话了。

绿洲精灵喊道：“等一等……”

但机器人是无情的。机器人从长长的队伍中随机提起了一些人，他们都瞬间消失了。机器人又把汤普金森先生提起来，一阵白光闪过，汤普金森先生什么都不知道了。

当汤普金森先生醒来的时候，演讲已经散场了。收拾会场的保洁阿姨叫醒了他。汤普金森先生摸了摸湿润的嘴边，揉了揉眼睛，走出了会场。

本期问题：

如果路由器按TD方式丢包，汤普金森先生能否走出这台路由器？

上期遗留问题解答：

为什么路由器的NP不需要提前读取数据包的源地址、目的地址等关键信息，而进入CPU时有专用硬件进行预先读取呢？

NP每级流水线中都有可编程的专用硬件，按照微码并行提取这些关键信息。而多核CPU没有这种专门从数据包头读取信息的多级单元，只有一个Parser一次性提取数据包头字段，预先读取并写入数据缓存(data cache)中。