Planes in Routers

• Data Plane (数据平面)， 对于每一个经过的数据包，根据控制平面下放的规则（路由表， MAC表等），快速决定是否进行转发、丢弃等操作。速度量级为纳秒级别。
• Control Plane (控制平面)， 运行路由协议，生成网络拓扑和路由表等，把这些下发给数据平面，速度为秒级别。
• Management Plane (管理平面)， 管理员与路由器交互的界面，用于配置、监控、维护路由器。同时保障设备的安全，速度为秒或分钟级别。

What’s Inside a Router ?

这是CS168中的图，我觉得不错，是故引用。

• Controller Card (控制器卡) ，承载了控制平面和管理平面，可与其他路由器交流后进行更改表之类的行为，但并不参与数据平面的运行。可以运行路由协议， 计算路由表， 生成转发表(发送给Linecard)，提供管理接口，处理协议控制包。
• Linecard (线卡)， 是实际负责接入和转出数据流量的硬件板卡， 是数据平面的物理载体。可拆卸的线卡使我们灵活规划一个路由器的大小，一般一个机框中有1-20个线卡。有些线卡中会有CPU， 更好控制线卡的行为。
  • 每一个线卡都会有几个ports (接口)，每一个接口都可以用于转入或转出。
  • 线卡上会有Fowarding Chip (转发芯片)， 真正执行数据平面转发的核心硬件元件，使用硬件而不是CPU处理的软件，使得数据平面的速度得以达到纳秒级别。具有解析数据包头部，查表，决策，修改/封装， 队列与调度多种功能。
• Fabric (交换网板)，是数据平面的核心内部通道，连接所有线卡，实现线卡中数据的无阻塞高带宽交换。 同时，假如交换网板与线卡间某条通路断开，依旧有别的通路可以使它们进行数据交换。
  • Fabric Chips (交换网芯片)位于交换网板上，也属于数据平面的核心组成部分。将来自线卡的数据包切分为固定长度的信元 (Cell)，在无阻塞交换网络中路由到目标线卡，再由目标线卡重组。

Packets

• User Packets: only in data plane.
• Control Plane Traffic: port -> forwarding chip -> Controller Card. 送至Controller Card即可。
• Punt Traffic: port -> forwarding chip -> Controller Card. 让Controller Card 知道异常发生了。
• Fowarding Chips 能够识别packet是上述哪一种。

Efficient Forwarding

如果一个地址范围2.1.1.0/24匹配端口5，此时我想要将一个包传给2.1.1.225，可能此时就需要展开许多地址 (如2.1.1.1， 2.1.1.2， 2.1.1.3 …)来进行匹配。这无疑会导致传递数据速度变慢。同时，一个端口可能可以匹配多个端口，我们该怎么解决这两个问题？

• Longest Prefix Match (LPM， 最长前缀匹配)，一种LPM的实现原理如下：
  • 将表中的地址展开为2进制，不确定的位数用 ‘ . ‘ 表示。
  • 将目标也展开为2进制与表中的地址一一比对，取最长前缀进行匹配，将包转发至对应端口。
  • 如果没有能够匹配到的地址，使用默认地址。如果没有默认地址，则将包丢弃。

这样的LPM的缺陷也很明显，你必须匹配所有表中的地址，对于匹配的N个地址，时间复杂度为O(N)。

• 用 Tries (字典树) 是一种高效实现LPM的方式，下图形象地展示了原理，(图中的value即为port)

到达最远的蓝色节点返回即可。上图没有设计默认端口，如需要设置默认端口，将所需要的端口绑定至 ‘…’ 的白色节点即可，此时它的颜色应该是蓝色。此时的时间复杂度是O(L)（L是IP地址位数)，快了很多。