What’s Inside a Router? | orange’s blog

type

status

date

slug

summary

通用路由器结构

以传统的路由器为例

let’s turn our attention to its forwarding function—the actual transfer of packets from a router’s incoming links to the appropriate outgoing links at that router.

下图是一个通用路由结构，Four router components can be identified:

Input ports：

它执行物理层功能（line termination），终止（terminating）路由器上的输入物理链路，如input port最左和output port最右的那个方框所示
它执行链路层功能（link layer protocol），将帧封装/解封装，这个是由input port或output port中间的那些方框实现的

比如从链路层解封装，找到一个IP分组，交给查找函数来排队进行转发

它实现查找函数（lookup function），是由input port最右边的那个方框实现的

在这里，forwarding table被用来参考，用以决定到达的packet应该被转发到这个交换机的哪个output port

控制包（如携带路由协议信息的包）从输入端口被转发到路由处理器（routing processor）

注意：这里的port指的都是物理的路由器输入输出接口，与前面讲的网络应用程序和传输层之间的socket软件端口明显不同
为什么有一个队列？

当fabric的速度小于输入端口的汇聚速度时，在输入端口可能需要排队，排队延迟以及输入缓存溢出可能会造成数据报丢失
head of line blocking：排在队头的数据报阻止了队列中其他数据报向前移动

输出端口竞争：只能有一个分组被传递、交换到一个输出端口，要是一个输出端口被占用了，其他想来这个端口的分组就会阻塞

因此需要一个排队来匹配输入输出速度的一致性

switching fabric：交换结构

连接路由器的input ports和output ports
这个交换结构是完全在路由器里面的

output ports：

当数据报从交换机构出来的速度比输出速度要快时，就需要输出端口有一个缓存用于给数据报排队
由调度规则在排队的数据报中选择进行传输

调度：选择下一个要通过链路传输的分组
规则：先到先发、丢弃策略

有网络层功能：成帧
有物理层功能：将到达的数据报变成比特打出去

routing processor

实现control plane的功能
在传统路由器中，它用来执行路由协议、维护路由表、附加链路状态信息、为路由器计算出forwarding table
在SDN路由器中，它用来与远程控制器通信，以便接收远程控制器计算出的forwarding table，并且把这些表项记录安装在路由器的input ports
计算出来的forwarding table被copy下来，沿着图里面的虚线（一个单独的总线）被传到data plane
network management

input/output ports、switching fabric几乎都是在硬件层面实现的，这些data plane的功能执行要比control plane上面的功能执行快得多，control plane functions一般是在软件中实现，然后在routing processor上执行（一般来说就是CPU）

如果把packet forwarding比作是车子进入又离开环岛，这个过程需要一些信息：

Destination-based forwarding

开车的人进入环岛时在一个收费站停住，然后告诉工作人员他的最终目的地，然后工作人员查找一个路线表，告诉这个司机在环岛的哪个出口出去

Generalized forwarding（广义转发）

工作人员还可以根据除目的地以外的许多其他因素来决定汽车从哪个出口出去，比如汽车牌照的权限等。在广义转发中，任何数量、任何类型的因素都可能改变工作人员为这个车决定的出口

Input Port Processing and Destination-Based Forwarding

line cards简介

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

如下图所示，line-termination实现物理层的功能，data link processing实现链路层的功能。其中，lookup是是整个路由操作的核心，router就是在这里在forwarding table里面查找到到达的数据包通过switching fabric应该被转发到哪个输出端口

而forwarding table要么是routing processor算出来的，要么是remote SDN controller算出来的，然后复制一份、沿着一条单独的总线被传到data plane的每个line card上

在每一个line card上都有一份forwarding table的副本，这样路由选择就可以在本地完成了，就不用在每个数据包到达时都调用routing processor，从而避免中央处理的堵塞

forwarding table的实现方式

问题：如果IP地址有32位，forwarding table如果要给每个地址列一个表项的话，就要列上万条

As an example of how this issue of scale can be handled, let’s suppose that our router has four links, numbered 0 through 3, and that packets are to be forwarded to the link interfaces as follows:

也就是根据地址范围进行划分：

使用这种类型的转发表，路由器将数据包的目的地址前缀与表中的条目进行匹配

与接口对应的前缀有重合的情况：

11001000 00010111 00011000 10101010：

它的前21位与接口2相匹配，但是前24位与接口1相匹配

When there are multiple matches, the router uses the longest prefix matching rule

有了转发表之后，look up这个步骤的硬件逻辑就只是在转发表里面搜索，找到最长的匹配前缀

Although “lookup” is arguably the most important action in input port processing, many other actions must be taken: (1) physical- and link-layer processing must occur, as discussed previously; (2) the packet’s version number, checksum and time-to-live field—all of which we’ll study in Section 4.3—must be checked and the latter two fields rewritten; and (3) counters used for network management (such as the number of IP datagrams received) must be updated.

Switching

The switching fabric is at the very heart of a router, as it is through this fabric that the packets are actually switched (that is, forwarded) from an input port to an output port. Switching can be accomplished in a number of ways, as shown in Figure 4.6:

转发（交换）的三种方式：

switching via memory

传统电脑的交换方式，交换是由CPU控制的。输入输出端口的运行方式就跟传统的I/O设备一样
一个包到达路由器，首先会向routing processor示意，然后这个包就被复制到processor的内存里面（写入）
processor取出包header里面的目的地址，在转发表里面查找合适的输出端口
把包复制到这个输出端口的缓存区里面（读出）
如果内存带宽是B的话，那么总体转发吞吐量必须小于B/2

内存至少被访问两次（一次读一次写），平均读出速率必定小于B/2

一次只能转发一个包（就算是两个目的地不同的包也不能同时转发），因为同一时间只有一个内存读写

Switching via a bus

输入端口通过共享总线将数据包直接传输到输出端口，而不需要routing processor的介入
input port在数据包上附上一个内部交换标签，用来指示该数据包传输到本地输出端口，并将数据包传输到总线上
每个output port都接收这个包，但是只有跟那个内部交换标签匹配的端口才将包留下
output port将包上之前被附上的内部交换标签去掉，因为这个标签只在交换机内部使用，以通过总线
如果许多包到达了路由器，就算它们不在同一个input port，它们也必须一个一个进行传送，因为总线一次只能传送一个包，因此交换速度也受限于总线速度

Switching via an interconnection network

用于克服单一总线带来的限速问题，采用更为复杂的互联网络
crossbar switch是由2N个总线组成的互联网络，将N个输入端口连接到N个输出端口
crossbar switch不会有阻塞，只要没有别的包也正在被转发到那个output port
但是如果两个input port不同的包要前往同一个output port，那么其中一个包就必须在入口处等待
交换结构其实就是去选择打开或关闭哪个交叉点

实际上每条线（A、B、C、X、Y、Z）都是通的，只是他们的交汇点不通，而fabric controller相当于就是去选通交汇点（intersection），所以A-Y和B-Z看起来会有交叉，但是实际上B-Y这个交汇点没有通，所以不会有问题，只要保证output port不同就一定可以parallel地传输信息而不会遇到blocking

Output Port Processing

Where Does Queuing Occur?

Let’s now consider these queues in a bit more detail, since as these queues grow large, the router’s memory can eventually be exhausted and packet loss will occur when no memory is available to store arriving packets.

It is here, at these queues within a router, where such packets are actually dropped and lost.

假设输入端口和输出端口都有相同的传输速率 packets per sec，现在这里有N个输入端口和N个输出端口。现假设所有的包都长度相同且同时到达输入端口

定义为包从输入端口移动到输出端口的速率

Input Queuing

switch fabric is not fast enough—不能让所有到达的分组无时延地通过它传送

如果交换结构的传输速度够快的话，就算N个输入端口有N个数据包，它们都要到达同一个输出端口，也可以在下一批包到达之前，将它们全部传输完毕

在这个图中，黑色阴影的数据包将要被发送到同一个输出端口

此时如果路由器选择传输左上角的数据包，那么右下角的数据包就必须排队等待，并且它后面那个浅色数据包也必须排队等待，就算它的目的地跟黑色数据包不同

This phenomenon is known as

head-of-the-line (HOL) blocking

in an input-queued switch—a queued packet in an input queue must wait for transfer through the fabric (even though its output port is free) because it is blocked by another packet at the head of the line.

Output Queuing

当输出端口没有足够的空间来存储一个新到达的包，它就必须决定是把这个包丢掉（drop-tail）还是丢掉已经在排队的包来为这个包腾出空间，在一些情况下，在缓存区满之前就需要丢弃掉一个数据包，从而向发送方提供一个拥塞信号

active queue management (AQM) algorithms)：一种主动丢包的标记策略

这种策略的结果就是，数据包调度程序（packet scheduler）必须从排队的数据包中选择一个来传输

与输入端口排队的不同之处：

假设此时还是比快N倍，由于输出端口在一个单位时间内只能传输一个数据包，因此到达的N个数据包还是不得不排队，并且由于交换速度要快很多，在输出端口打出一个数据包的时间内，有可能已经从交换结构又传送过来了很多个数据包

How Much Buffering Is “Enough?”

之前的结论：缓存大小（B）应该等于信息一个往返（RTT）的时间内链路可以传输的比特数（link capacity C）

但是如果TCP有很大的数量（N），缓存大小的估计就需要除以一个

缓存大小也不是越多越好，因为很多的缓存会导致排队延迟特别大

bufferbloat(缓存膨胀）

现假设图上这个home router需要20ms来传输一个packet，RTT=200ms，0时刻突然有25个包到达并开始排队，因此每隔20ms就有一个包被传送出去，当t=200ms的时候收到第一个ACK

One of these queued packets is then transmitted once every 20 ms, so that at t = 200 msec, the first ACK arrives, just as the 21st packet is being transmitted. (这里我有问题，感觉这本书这里写错了，计算可知，20ms发送一次，到200ms的时候，发送了10次，正在发送第11次，而不应该是第21次，所以后面的排队长度应该是15而不是5)

然后这个ACK到达之后会引起router发送下一个正在排队的包

t=220ms之后，host这边就会往下再传输一个包，然后这个包也加入排队，并且在这同一时刻，第11个包也发送出去了

因此在这个情境下，ACK的到来会导致当排队长度达到5（其实应该是10）之后就不会再减少了，因为一旦发出去一个包又会再次到达一个包，也就是说，现在这个pipe已经被占满了，输入速率=输出速率，正是由于有这个缓存区导致排队时间很长且恒定，无法适用，哪怕抓包都只能是看到网络正常传输，数据的确是一直在发送，只是说你的TCP发送方刚发送的数据就马上需要排队（这个队很长，由于之前的突发分组造成的）