Propagation Delay

传播延迟指的是在链路以某种速度传输1bit所用的时间。

Packetization Delay

打包延迟指的是从包中第一个bit开始计算，到最后一个bit被放入链路所经过的时间。

End-to-end delay

端到端延迟：Package从一端传输到另一端的时间，具体的计算方法就是每一个Router间的传播延迟+打包延迟的总和。

当链路上出现拥塞时，Router会将待转发的包放入Buffer此时的端对端延迟要在加上一项排队延迟，该项延迟是不可预测的，它由链路的拥塞时间决定。

Queue Model

这个队列模型就像一个水桶，Package从各个Router发到队列中，再以R的速度出队。这里就涉及到两个转发策略：即时转发、存储转发。不同的策略会影响队列的占用率。

从这可以看出为什么要把数据分解成Package来传输，因为这样可以利用链路来近乎并行的传输Package以降低端到端延迟。

Generic Packet Switching

当Package到达Router后将经历以下几个过程

  • 查找地址，然后根据转发表来决定转发给哪一个Router。
  • 更新标头，减少TTL，更新校验和
  • 排队，如果拥塞则放入Buffer来等待发出

Ethernet Switch

  • 检查每一个到达的帧的Header

  • 如果以太网目标地址在转发表中，则转发到对应的端口上

  • 如果没在转发表中则广播给所有端口

  • 当数据包到达时，转发表通过检查帧的源地址来更新

    比如有一个目标地址不在转发表中，那就会广播给所有Port此时如果有Port回应，则纪录这个源地址，以此来更新转发表。

Internet Router

  • 如果该包的Ethernet地址指向该Router则接受，否则丢弃这个包
  • 检查IP版本与数据包长度
  • 减少TTL，更新校验和
  • 检查TTL是否为0
  • 如果IP目标地址在转发表中，则直接转发到下一跳
  • 与之前一样，进行广播找到下一跳的地址
  • 创建新的Ethernet帧然后发送

这也引出两个问题：

  • 转发表是怎么搜索地址的？
  • 包是怎么发送给正确的Port的？ （ARP）

Ethernet forward table

以太网转发表——哈希表

进行多路Hash是为了避免碰撞

Internet forward table

IP转发表中的条目是有序的，在进行查找时会根据目标来选择查找的起点和终点

Switches and routers queue

同常情况下这个队列将接受来自各个Router的包，然后直接放入队列等待发送，但是如果有的源发送能力强，发的包非常多，有的源发送能力弱，发的包少，那前者将大量的占用这个队列，导致后者的包的延迟很大，并且这种公平化的入队规则无法让那些优先级高的包先被发送。

Strict priorities

这个策略会先根据Package的报头来获得它的优先级，然后放入对应优先级的队列。当高优先级的队列完全发送完时，才发送低优先级。

Weight Priorities

根据权重来决定该队列对链路的占用率。但这又引发一个问题，如果Package的长度不同，那长度大的包实际上的占用率会高于它应占的权重。

Fair Queueing

按照bit来轮询着发包，无权重，完全公平。

Weight Fair Queueing

这个算法的区别在于它发包的时候是以bit为单位来发的，而不是按照包为单位发，这样就保证了每一轮发的包是严格按照权重来占用链路。右上角的队列是实际发的顺序，右下角是包发完的顺序。