路由器功能与架构

• 数据路径功能
  • 根据分组目的IP地址查找转发表
  • 通过交换结构转发到输出端口
  • 输出端口调度和队列管理
• 控制面功能
  • 运行路由协议，构建路由表
  • 系统配置和管理

路由查找算法

Binary Trie

![[Pasted image 20240102174052.png]] ![[Pasted image 20240102174131.png]]

####性能

• 最差情况下，查找算法需要遍历Trie的所有层次，所以最差情况下需要有W次存储器访问，W为前缀的最大长度，对于IPv4为32，查找复杂度和更新复杂度为O(W)
• 最差情况下，增加一个前缀，需要增加W个节点，存储复杂度为O(NW)，N为转发表中的前缀数量

Leaf Pushing

![[Pasted image 20240102174439.png]]

Path Compression

• Compression：Trie中只有一个子节点的非前缀节点能够被删除
• 节点保持Compression相关信息
  • skip value：指示路径上有多少个比特被跳过
  • segment：指示最后一次跳过操作以来具体遗漏的比特串 ![[Pasted image 20240102175058.png]]
• 性能
  • 路径压缩可以有效地减少稀疏binary trie的高度
  • 在最差情况下，没有压缩的可能，因此采用路径压缩后查询和更新复杂度与binary trie一样，都是O(W)

Multi-bit Trie

• 查找时同时检查多个比特，称为查找步长（Stride）
• 如果前缀长度不为步长的整数倍，则对其进行扩充
• 例如步长为3，对于前缀1*可以扩充为100,101,110,111
• 步长为k，则Trie中的每个节点的条目数量为2k
• 每个条目组成：<下一跳信息，指向下一个子节点的指针（可以为空）> ![[Pasted image 20240102183349.png]]
• 性能
  • 步长为k比特，则查找的复杂度为O(W/k)，W为地址的长度
  • 更新复杂度O(W/k*2^k),每个节点有2^k个条目
  • 存储（空间）复杂度O(N*2^k*W/k),N为转发表表项数量

Leaf Pushing优化

• 节点上的每个条目要么包含一个指针，要么包含下一跳信息
• 相当于把下一跳信息Push down到叶子节点
• 存储空间减少为1/2 ![[Pasted image 20240102183713.png]]

LC Trie构造

节点分布稀疏时，Path Compression是压缩Trie的有效途径 固定步长multi-bit能够提高查找性能，但是当节点分布稀疏时存储冗余大 节点分布越密，存储效率越高，完全Trie无冗余！

1. 如果Trie的中间节点包含前缀，则进行Leaf Pushing操作，使得Trie中只有叶子节点包含前缀（即为前缀节点）
2. 通过Path Compression将Trie压缩（就是去掉只有一个孩子的节点）
3. 当子Trie的结构为完全子Trie时执行Multi-bit查找（完全二叉树只留叶子结点） 在LC Trie中每个节点需要保存：
4. Path Compression信息(Skip Value, Segment)
5. Multi-bit查找信息 (Stride)

![[Pasted image 20240102185801.png]]

• 性能
  • 查找步长为k，则查找复杂度、更新复杂度及存储复杂度与multi-bit Trie相同
    • 查找复杂度为O(W/k)，W为地址长度
    • 更新复杂度为O(W/k*2^k)
    • 存储（空间）复杂度O(N*2^k*W/k),N为转发表表项数量

tree Bitmap算法

交换结构

概念

吞吐量（Throughput)

• 当所有的输入端口以线速承载100%的业务的时候，平均汇聚输出速率和平均汇聚输入速率的比率
• 如果所有空闲输入-输出端口对都可以传输数据，则可以认为吞吐量是100%
• 线路速率（Line Speed）：简称为线速，交换机端口连接的线路所能达到的最高速率

加速（Speedup）

• 交换结构的内部转发速率和单个输入端口线速的比值
• 如果加速超过1，则输出端口必须使用缓存

输出竞争

• 多个输入端口请求同一个输出端口导致输出竞争
  • 由IP业务的突发性导致

内部阻塞

• 交换结构内部竞争导致内部阻塞
  • 无阻塞：空闲输入端口和空闲输出端口之间的连接始终可以被建立
    • 空闲端口：没有连接或者没有被请求连接的端口

交换机输出竞争和内部阻塞都会降低吞吐量，但后者是可以避免的，而前者是无法避免的 阻塞一般是指交换结构内部争用所导致，而输出竞争是发生在交换机的输出端口.阻塞和输出竞争是在空分交换中发生，对于时分交换，业务在时间上进行复用可以避免阻塞

3代交换结构

• 第一代：共享存储器交换，交换机速率受限于共享的存储器的访问速度，通常汇聚容量小于0.5Gbps
• 第二代：共享媒介交换，交换机速率受限于共享的总线（媒介）速率，通常汇聚容量小于5Gbps
• 第三代：空分交换，交换机速率受限于交换结构，通常汇聚容量可达到50Gbps甚至更高

Banyan交换结构

• Banyan交换结构为单路径多级交换结构
• 多级交换结构一般是由较小的交换单元组成的大的交换系统，也称为交换网络，交换单元常用2×2 Crossbar
• 共有log2N级，每一级都有N/2个交换单元，总交叉点数量：Nx=4×N/2× log2N ![[Pasted image 20240102195733.png]] ![[Pasted image 20240102195858.png]]

输入队列与输出队列

![[Pasted image 20240102200202.png]]

![[Pasted image 20240102200038.png]]