Network(2) -- 路由器里面有什么？

一般的路由器架构分为四个部分：

• 输入端口：它是输入的物理连接线的终点。输入端口也执行某些链路层需要的功能从而与另一端进来的链路层交互操作。最最重要的是，查找功能也是在输入端口完成的。就是在这里，转发表被咨询来决定到达的数据包被转发到哪一个输出端口(通过转换结构)。控制包（比如携带路由信息的那些数据包）从输入端口被转发到路由处理器。
• 转换结构：转换结构连接了路由器的输入端口和输出端口。它是一个路由器内部的“网络”
• 输出端口：输出端口储存着从转换结构接收到的数据包并发送这些数据包给外部连接。当连接是双向的时候，输出端口一般会跟输入端口成对。
• 路由处理器：路由处理器执行控制层面的功能。在传统路由器中，它执行路由协议，维护路由表，附加连接状态信息，并计算转发表。而在SDN路由器中，路由处理器负责与远程控制器沟通，从而接收远程控制器转发表的一个条目，并安装这些项目到路由器的输入端口。路由处理器也包含网络管理的功能。

路由器的输入端口、输出端口、以及转换结构几乎都是用硬件实现的。

控制层面的功能，比如执行路由协议，响应向上向下走的连接，与远程控制器沟通，执行管理功能……这些操作都是毫秒甚至秒级别的。这些控制层面的功能一般是用软件实现并在路由器的CPU中执行的。

输入端口处理和基于目的地的转发

转发表被从路由处理器复制到线卡(line cards)。在每一个线卡都有这样一个拷贝，就可以在本地做出转发的决策，在每一个输入端口，而不需要去调用中心化的路由处理器，从而避免了中心化处理的瓶颈。

下面来思考最简单的情况，即只根据目标地址来确定输出端口。在32位的寻址系统中，转发表的一种暴力求解的实现方法就是每个目标地址都占一行。因此有超过40亿可能的地址，所以这个选择肯定行不通。

这个问题怎么解决呢？现在我们假设路由器有四个连接，编号从0到3。

只需要通过地址的前缀来判断即可：

prefix
11001000 00010111 00010         0
11001000 00010111 00011000      1
11001000 00010111 00011         2
otherwise                       3

如果一个地址能匹配上多个前缀，遵循“最长前缀匹配法则”, longest prefix matching rule。因为搜索对时间的要求非常高，所以不仅需要使用硬件进行线性搜索，还需要有特殊的搜索算法。内存访问的时间也需要特别注意，需要设计嵌入在芯片内的DRAM和更快的SRAM。

一旦通过搜索确定了输出端口，数据包就可以被发送到switching fabric了。在一些设计中，如果其他输入端口的包正在使用switching fabric,则数据包会被阻塞，从而形成队列等待。除了搜索外，还有其他一些重要的行动：(1)物理的和链路层的处理一定要做；(2)数据包的版本号，checksum, time-to-live存活时间，都需要检查或者覆写；(3)用于网络管理的计数器也需要被更新。

在很多网络设备中都采取了这种“匹配 + 行动”的模式，不止是路由器。

交换结构 Switching

正是通过switching fabric, 数据包才能从一个输入端口交换（转发）到一个输出端口。

通过内存交换

就像传统计算机CPU直接控制输入和输出端口之间的交换。当输入端口有一个包到达时，先通过中断的方式告诉路由处理器。然后数据包就从输入端口被复制到处理器内存。然后路由处理器从头部信息中抽取目标地址，去转发表查找合适的输出端口，最后把数据包复制到输出端口的缓存里。在此情景下，如果内存最大的带宽是B个包/秒可以被读/写，那整体的吞吐量就一定会小于B/2。

一些现代的路由器还是通过内存交换的。与早期的路由器主要的不同点是，目标地址的查找以及把包存到合适的内存位置这些操作，是通过输入线卡line cards完成的。

通过总线交换

输入端口直接把包通过总线发送到输出端口，没有路由处理器的干涉。让输入端口首先给数据包贴上标签（头部）标明发送到哪个输出端口，然后就发送给总线。所有的输出端口都能接收到这个包，但只有匹配标签的才留下数据包。然后输出端口把标签移除。如果有多个包同时到达路由器，那只有一个能通过总线，其他的都要等着。

通过interconnection网络交换

纵横交叉的2N条总线，连接了N个输入端口和N个输出端口。switch fabric可以控制交叉点的开关。这种方法能够同时转发多个包。在输出端口不会阻塞，只要没有其他的包也被转发到同一个输出端口。然而，如果两个包，从不同的输入端口，指向同一个输出端口，那么其中一个必须在输入端口等着