CAN201 W6

Lecture

记虽然笔记迟了，但是一定会补回来呀！
这周第一部分是TCP congestion control。我有空再写笔记，我们先进入第二环节。也就是网络层 Network layer.

---

网络层服务

• 在发送主机和接收主机对之间发送段（segment）
• 在发送端把段封装到数据报（datagram）中
• 在接收端，将段上交给传输层实体
• 网络层协议存在于每一个主机和路由器（全部都有）
• 路由器检查每一个经过他的IP数据报头部 网络层功能：

转发：将分组从路由器的输入接口转发到合适的输出接口。
路由：使用路由算法来决定分组从发送主机到目标接受主机的路径（路由选择算法和路由选择协议）

数据平面

• 本地，每个路由器功能
• 决定从路由器输入端口到达的分组如何转发到输出端口
• 转发功能：
  • 传统方式：基于目标地址+转发表
  • SDN方式：基于多个字段+流表

    控制平面

• 网络范围内的逻辑
• 决定数据报如何在路由器之间路由，决定数据包从源到目标主机之间的端到端路径
• 2个控制平面方法：
  • 传统的路由算法：在路由器中被实现
  • software-defined networking (SDN): 在远程的服务器中实现

传统方式：每-路由器控制平面（per-router）
在每一个路由器中的单独路由器算法元件，在控制平面进行交互

传统方式的路由和转发的相互作用

SDN方式：逻辑集中的控制平面
一个不同的（通常是远程的）控制器和本地控制代理（CAs）交互
传统方式是僵化的，不可以编程，SDN方式可以对网络进行编程操作。

网络服务模型

从发送方主机到接收方主机传输数据报的“通道”，网络提供什么养的服务模型？
对于单个数据报的服务：

• 可靠传送
• 延迟保证，如：少于40ms的延迟

对于数据报流的服务：

• 保序数据报传送
• 保证流的最小带宽
• 分组之间的延迟差

连接建立

• 在某些网络架构中是第三个重要的功能
  • ATM, frame relay, X.25
• 在分组传输之前，在两个主机之间，在通过一些路由器所构成的路径上建立一个网络层连接（涉及到路由器）
• 网络层和传输层连接服务区别：
  • 网络层：在2个主机之间，涉及到路径上的一些路由器
  • 传输层：在两个进程之间，很可能只体现在端系统上（TCP连接）

CBR:恒定速率; VBR:变化速率; ABR:可用比特率; UBR:不指名比特率;

---

路由器结构概况

高层面（非常简化的）通过路由器体系架构

• 路由：运行路由选择算法/协议（RIP, OSPF, BGP）生存路由表
• 转发：从输入到输出链路交换数据报–根据路由表进行分组的转发

输入端口功能

为什么输入端口有队列？（输入端口缓存）

• 当交换机构的速率小于输入端口的汇聚速率时–>在输入端口可能要排队（排队延迟以及由于输入缓存溢出会造成丢失）
• Head-of-the-line (HOL) blocking: 排在队头的数据报阻止了队列中其他数据向前移动
  
  在一个分组时间内，绿色分组遭到了堵塞。

通过内存交换

第一代路由器

• 在CPU直接控制下的交换，采用传统的计算机。
• 分组被拷贝到系统内存，CPU从分组的头部提取出目标地址，查找转发表，找到对应的输出端口，拷贝到输出端口。
• 转发速率被内存的带宽限制（数据报通过BUS两遍）–> 不足之处
• 一次只能转发一个分组
  

通过总线交换

• 数据报通过共享总线，从输入端口转发到输出端口
• 总线竞争：交换速度受限于总线带宽（但是现在只通过总线一次了）
• 一次处理一个分组
• 对于接入或企业级路由器，速度足够（但是不适合区域或者骨干网络）
  

通过互联网络（crossbar）交换

• 同时并发转发多个分组，克服总线带宽限制
• Banyan（榕树）网络，crossbar（纵横）和其他的网络互联网被开发，将多个处理器连接成多处理器
• 当分组从端口A到达，转给端口Y：控制器短接相应的两个总线
• 高级设计：将数据报分片为固定长度的信元，通过交换网络交换
  

输出端口

• 当数据报从交换机构的到达速度比传输速率快就需要输出端口缓存
• 由调度规则选择排队的数据报进行传输

输出端口排队

• 假设交换速率Rswitch是Rline的N倍（N：输入端口的数量）
• 当多个输入端口同时想输出端口发送时，缓冲该分组（当通过交换网络到达的速率超过输出速率则缓存）
• 排队带来延迟，由于输出端口缓存溢出则丢弃数据报！

调度机制

那输出端口缓存溢出应该怎么调度呢？

• 调度：选择下一个要通过链路的传输分组
• FIFO (first in first out) scheduling: 按照分组来到的次序发送
  • 丢弃策略：如果分组达到一个满的队列，哪个分组会被抛弃呢？
    • tail drop：丢弃刚到达的分组
    • priority：根据优先权丢失/移除分组
    • random：随机的丢失/移除
      

调度策略：优先权

优先权调度：发送最高优先权的分组
多类，不同类别有不同的优先权

• 类别可以依赖于标记或者其他的头部字段：IP source/dest, port, numbers, ds, etc.
• 先传高级别的队列中的分组，除非没有
  
  假如有红的就一直红的，一直到没有红的再传绿的。

调度策略：其他

Round Robin (RR) scheduling:
循环扫描不同类型的队列，发送完一类的一个分组，再发送下一个类的一个分组，循环所有类。
学过，看看复习一下。

Weighted Fair Queuing (WFQ):

• 一般化的RR
• 在一段时间内，每个队列得到的服务时间是：Wi/(XIGMA(Wi))*t，和权重成正比
• 每个类在每一个循环中获得不同权重的服务量
  

---

IP: Internet Protocol

IP协议在哪里？干啥？（数据层面的转发功能）

在传输层和链路层之间的网络层。
主机，路由器中的网络层功能有：路由协议（路径选择，RIP,OSPF,BGP），IP协议（地址约定，数据报格式，分组处理的约定），ICMP协议（错误报告，路由器信令）

---

IP数据报格式

IP分片和重组(IP fragmentation, reassembly)

• 网络链路有MTU（最大传输单元）即链路层帧所携带的最大数据长度
  • 不同的链路类型
  • 不同的MTU
• 大的IP数据报在网络上分片“fragmented”
  • 一个数据报被分割成若干个小的数据报
    • 相同的ID
    • 不同的偏移量
    • 最后一个分片标记为0
  • 重组只在最终的目标主机进行（为什么不在中间重组，因为路由器太忙了，还可能路由表会变，中间几个分组还可以丢失，所以不如直接在目标主机进行）
  • IP头部的信息被用于标识，排序相关分片

• 4000字节数据报 –> 20字节头部，3980字节数据
• MTU = 1500 bytes
• 第一片：20字节头部+1480字节数据（偏移量：0）
• 第二片：20字节头部+1480字节应用数据（偏移量：1480/8=185）
• 第三片：20字节头部+1020字节应用数据（偏移量：2960/8=370）
• 偏移（以8字节为单位）= 1480/8
• fragflag等于1说明后面还有切片，等于0说明这就是最后一个切片了

---

基于目的地转发

转发表是由路由选择处理器计算和更新的，或者转发表接收来自远程SDN控制器的内容。

对于这个例子，在路由器的转发表中没有必要有40亿个表项，所以我们把这个表写成一个只有四个表项的转发表：

使用这种风格的转发表，路由器通过分组目的地址的前缀（prefix）与该表中的表项进行匹配；当有多个匹配时，该路由器使用最长前缀匹配规则（longest prefix matching rule）:即在该表中寻找最长的匹配项，并向与最长前缀匹配相关联的链路接口转发分组。
实践中也经常使用三态内容可寻址储存器（Tenary Content Address Memory, TCAM）来查找表项。

• 内容可寻址（Content addressable）:当前地址到TCAM:检索地址在一个时钟周期，无论表大小
• Cisco Catalyst:可以在TCAM中增加~1M的路由表项

---

Lab

讲的assignment1的task sheet。没什么卵用。