计网学习笔记六 Network Layer Overview
这节课开始进入了网络层的学习，讲述了网络层提供的功能，还有路由器内部是什么样子的，以及virtual circuit网络和datagram网络的一点比较。
网络层有什么作用呢？用一句话来说，就是需要负责将传输层的报文段从发送端传输到接收端。再详细一点点就是：
- 在发送方将传输层传下来的数据报文段封装成网络层数据报；
- 在接收方将接收到的数据报向上送到传输层；
- 网络层协议在所有的host和router都有应用；
- router需要检查流经它自身的所有数据报的header。
Network Layer Functions
网络层的功能有两个：routing 和 forwarding。
用旅行来比喻：如果数据报是需要出门旅行的人，那么routing就是提前决定好一条旅游的路线（从哪到哪然后到哪再到哪……），forwarding则是在路线中的某一个站点进出的过程。
Routing
routing使用路由算法找到一条从src到dest的最短路径。
routing属于网络层的控制平面，需要多个路由器进行协调，以后慢慢阐述。
Forwarding
“Forwarding 是网络层数据平面唯一需要实现的功能。“
Forwarding通过switching，来将数据包从节点入口移动到指定的节点出口，“在某个时刻一个包进来了，决定在哪个端口出去”。在这个过程还需要做error handling, queuing 和scheduling。
其中router进行switching的过程和二层交换机是十分相似的，router有一个forwarding table，起到了类似于交换机表的作用：
但forwarding table并不是自学习得来的，而是需要各个路由器之间的路由算法进行通信后才可以配置完成。也就是说，控制平面的routing决定了数据平面需要使用的forwarding table。
forwarding 时网络层还会提供一点其它的功能，如queuing 和 scheduling，因为拥塞实时存在，所以加上这两个功能。
Service Model
网络层的服务模型（service model）是指，如果想要传输一个数据报，那么传输所用的"channel"应该为什么样子的呢？
要用的"channel"需要考虑的因素非常多，即我们的"channel"应该为传输提供了什么样的服务……例如有以下服务：
对需求做出抽象后产生的服务功能越强，那么实现起来的代价就越大——所以作为应用最广的协议层，便宜很重要！
先不提实现成本，来看看IP和ATM协议的对比——它们提供了什么服务：
可以看到，IP协议的best effort服务真是够鬼舞的……好像什么都干不了，看看ATM协议能做的还真多，还分了四种优先级供人选择。
但ATM协议还是败了，就是败在了实现成本这方面。虽然IP看上去不咋地，但在现今与适当的带宽供给相结合已经能够用于大量的应用，已经“足够好”。
Inside the Router
Overview了网络层提供的功能和服务，我们来看路由器的工作原理，看它是如何进行forwarding的。
总体路由器系统容量
其中 N 为路由器的外端口数量；R 为 端口的传输速率 (即“line rate”)；
在 RFC 8238 第五部分的定义（5.1）有：
The line rate or physical-layer frame rate is the maximum capacity to send frames of a specific size at the transmit clock frequency of the DUT.
The term "nominal value of line rate" defines the maximum speed capability for the given port -- for example (expressed as Gigabit Ethernet), 1 GE, 10 GE, 40 GE, 100 GE.
路由器的属性差异
路由器是有种类区分的，在不同应用场景下的路由器的配置也有所不同：
- Core 核心路由器
- R = 10/40/100/200/400 Gbps
- NR = O(100) Tbps (Aggregated速率)
- Edge 边缘路由器
- R = 1/10/40/100 Gbps
- NR = O(100) Gbps
- Small business 小型路由器（家用）
- R = 1 Gbps
- NR < 10 Gbps
路由器的实现机制
- 两个平面：控制平面负责
routing，数据平面负责forwarding； - 控制平面由一系列处理器和软件组成，路由器之间进行交流决定路由算法；
- 组成部分包括：输入端口、交换结构、输出端口、路由处理器。
问：为什么输入输出端口以及交换结构大部分用硬件实现？
主要challenge：接收数据包的速率的时间要求（例如100B大小的包要达到40Gbps的速率接收，则只有20ns时间处理）远远快于软件实现；所以不用普通的x86芯片，用的更快的ASICs实现（专用的网络处理器）。
Input Port Functions
输入端口主要有以下四个任务：
进行了线路端接和链路层处理后，我们来到了执行查找输出端口的步骤。转发表通过路由处理器计算和更新（或者由SDN转发过来的内容更新，SDN在控制平面会讲），转发表从路由处理器经过独立总线复制到 line card中，使用副本可以使得查找决策可以在各个输入端口上分别执行，无须调用集中式路由处理器。
但问题来了，IP有四十亿多的地址，一个端口对应一个地址的话，转发表怎么够装？
如何处理这样的规模问题？采用地址聚合。（可扩展性好）我们用最长前缀匹配规则 LPM rules来对地址们进行聚合。
LPM的定义如下：
来看一个例子。假设我们的交换机有四个端口，给出各个端口接收到的packet的地址范围（为了方便，用一个字节）；可以看到这些地址的LPM分别是蓝色标记的部分：
然后我们就可以根据LPM来把地址和对应的端口写入转发表中，此时一个端口对应的是一个“聚合起来”的地址群，而不只是单单的一个。
由于需要达到纳秒级别执行，即使是用硬件执行查找，简单线性搜索匹配还是太慢。所以我们用一个Trie tree来查找匹配。（或者看这篇：路由查找算法研究综述）这是针对前缀查找问题的一个好方法，有点类似哈夫曼树，可以基于前缀长度而不是前缀内容做线性遍历。
除了查找算法，在硬件上也需要进行对访存消耗的优化，如TCAM（三态内容可寻址存储器，电平控制）。
Switching fabric
交换结构可以由三种不同的交换技术实现，即内存memory、总线bus和纵横式crossbar。
交换速率switching rate是指packet从输入端口传输到输出端口的速率，通常以输入/输出的line rate的倍数来衡量，
memory
早期的路由器是传统的计算机，对packet进出的使用IO机制进行处理（即中断--系统调用，packet被copy到内存中），在这种情况下如果内存带宽每秒能读出/写入B个packet，那么总的吞吐量一定小于B/2。另外还不能同时forward两个packet，即使端口不同——因为经过系统共享总线一次只能进行一次内存读/写。
现代的很多路由器同样采用memory方式，但与早期不同的是，查找packet并将其switch进内存中的行为是由输入端口的line card进行处理的。（这种方式很便宜，相对其它两种）
bus
bus交换方式是通过路由器内部的背板总线来实现的，不需要路由处理器的操作。当packet查找出对应的输出端口时，packet头部被打上一个label（相当于多加一层header），这个label记录了对应的输出端口；然后它被放到总线上传输，这时所有的输出端口都能收到该packet，但只有label上记录的输出端口才能保存该packet。
因为一次只有一个packet可以通过总线（同一时间的其余packet需要原地等待），所以bus方式的switching rate与背板总线速率有关。
crossbar
为了克服bus方式共享总线带来的速率限制，我们可以用2N条总线来构建一个复杂的互联网络（对应N个输入端口和N个输出端口）；然后总线的交叉点可以通过交换结构控制器来在任何时候进行开启/关闭，由此可以实现多个packet的并行转发。这种方式面对多个输出端口不同的packet时，是non-blocking的。
Cisco CRS利用三级non-blocking交换策略实现对多个输出端口相同packet进行并行switching。
Output Port Function
输出端口需要做的就是选择并取出正在queueing的packet，然后执行链路层功能，再进行物理层线路端接传输。
输出端口有三个组成部分：
Classifier：流分类器，负责将packet分到各个流中；Buffer management：决定哪一个packet以及在什么时候会被丢弃；Scheduler：packet调度器，在queueing的packets中决定哪一个packet以及在什么时候会被传输走；
在最简单的FIFO机制路由器里面，没有classification机制，buffer的management仅仅是把buffer尾部溢出的packet丢弃，scheduler也只是简单地使用FIFO来对packet调度——谁先来谁就能先出去。FIFO机制弊端太多，我们来看看这三个组成部分可以在此之上有什么提升：
Packet classification
Classifier可以根据packet的header来进行流分类（有意义的调度必须要先分类）：
Scheduler
对于调度器来说，一个好的调度算法非常重要（纳秒级别的处理要尽可能快）。常见的调度算法有FIFO、优先级调度（Priority scheduler）、加权公平调度等。
我们来说一下优先级调度和加权公平调度。
对于这两个调度算法来说，buffer里面的每个流都有一个buffer队列。优先级调度的策略很容易理解：就是优先级越高的队列总是比优先级低的队列先进行packet传输；而加权公平调度则是有几种情况：最简单的round-robin方式就是简单的对每一个队列都进行周期性的packet传输，你一下我一下；而weighted fair queue(WFQ)方式是对队列进行加权后，按照权值来进行周期性循环。
PS：在早些时期，运营商可以自己调整ISP路由器中的队列优先级（谁给钱多，谁的packet就传输得越多越快），所以需要法案来规定这些东西……
VC网络(ATM)和数据报网络(Internet)
在第一节讲过我们的network的连接可以分为电路交换模式和分组交换模式。在这里我们来说一下它们在网络层中分别对应使用的具体协议实现：电路交换（virtual circuit网络）对应的是ATM协议，而分组交换（datagram网络）对应的是IP协议。
virtual circuit网络
VC网络需要在传输数据前在src和dest之间先确立好一条路线，在这条路线上的路由器和交换机都是固定分配好后就不变的，这也表示这条路线是这次传输专属的，性能可以被准确估计。这条路线需要用路由器来找出（shortest path）。
每一个在VC网络上传输的packet都会带着一个VC number，VC number在路线上的每一个link存在，它在转发表中的使用如下：
VC网络的建立和断开就像大公司招人，正式职工一般是长期聘用的，不会断开那么快。它使用信令协议（Signaling Protocols）来建立、维持以及断开VC连接，具体协议有ATM, frame-relay, X.25，但是在今天的Internet已经基本看不见了（因为实现昂贵，昂贵的原因：需要保存途径连接的状态）
datagram网络
datagram网络的特点是无确定连接、无转发状态记录，同样的src-dest的packet，在网络中走的可能是不同的路线。
和VC网络的转发表不同，datagram网络的转发表记录的src地址可能是switch地址，也可能是一整个subnet的地址群：
Virtual Circuits vs Datagram Networks
两种网络的routing：VC网络(左)和datagram网络(右)。
相关资料：Virtual Circuits vs Datagram Networks；有一个小的总结：
