网络层根据网络拓扑和流量特征为任意两个节点确定一条（多条）传输路径，并完成任意两个节点之间的数据递交。
网络层的功能通过网络层设备—路由器—实现。
5.1 网络层的设计问题
5.1.1 存储转发数据包交换
路由器是网络层设备，除了具有网络层的功能以外，还具有物理层和数据链路层的功能。
在直接相邻的两个路由器端口之间运行物理层协议（编码、速率等）和数据链路层协议（第三章学习的滑动窗口协议，提供一条线路上可靠的数据传输、第四章交换机的转发封装功能等）。
在所有路由器上运行的路由有关的协议属于网络层协议。
路由器处理数据过程：当一个数据（帧）到达路由器的一个入境端口后，首先进行帧的校验和验证（数据链路层功能），通过校验的帧中的负载字段（数据包或分组）提交给网络层，进入网络层的存储队列（网络层存储功能），路由器根据一定的调度规则处理队列中的数据包（网络层调度功能），被调度到的数据包根据路由表确定出境端口（网络层路由功能），并将数据包转发到所确定的端口（网络层转发功能），出境端口按照端口类型封装数据包为帧并发送出去（数据链路层功能）。
存储转发：将入境数据缓存（存储），根据一定的规则调度到出境端口并发送（转发）的过程。
5.1.2 提供给传输层的服务
网络层向传输层提供的服务包括无连接的服务和面向连接的服务。
无连接的服务由数据网络（互联网）阵营支持。初始由ARPANET选择，为了防止由于部分网络节点或线路瘫痪而严重影响路由，做到只要两个节点之间存在路径（两个节点是连通的），数据就可以被自动路由递交。
面向连接的服务由电话公司阵营支持。支持顺序递交的基础上，提供实时流量、可靠性等各种服务质量。
三网融合（电话网、有线电视网、数据网）要求一个网络支持以上两种服务并支持多种服务类型。
5.1.3 无连接服务的实现
所有的数据包被独立地注入到网络中，每个数据包携带完整的目的地址，在网络中被独立路由（在每个路过的路由器根据本身的路由表，和数据包中的目的地址，确定下一步的转发线路）。数据包之间由于网络状态的变化（反映到某些路由器路由表的变化，从而导致从当前路由器以后路径的变化）可能经过不同的路径。所谓“独立”，指的是任意两个数据包的路径没有相关性。
检查A的路由表中的错误：转发只能是邻居节点
5.1.4 面向连接服务的实现
事先为一次传输确定一条路径（虚电路，虚的含义是使用一条线路的部分资源而非全部），本次传输中的所有数据包使用同样的路径递交。
可以分为按需虚电路和永久虚电路。按需虚电路为每次传输计算一条路径，传输完毕后拆除虚电路；永久虚电路一直保存在网络中，每次传输选择一条虚电路。
虚电路使用一个标识符标识本虚电路。虚电路标识符具有“局部（本地）”特征，即每台路由器可能选择不同的标识符。标识符在整条路径上不断变化，不影响数据转发。
每个数据包携带一个虚电路标识符用于中间路由器的转发，每经过一个路由器，虚电路标识符的取值可能变化。
5.1.5 虚电路与数据报网络的比较
5.1 网络层设计要点（虚电路子网、数据报子网）
问题 | 数据包网络 | 虚电路网络 |
电路建立 | 不需要 | 需要 |
寻址 | 每个包包含全部的源和目的地址。 | 每个包包含简短的VC号。 |
状态信息 | 路由器不保留连接状态。 | 针对每个连接，每条VC都需要路由器保留其状态。 |
路由方式 | 每个数据包被单独路由。 | 建立VC时选择路由，所有包都遵循该路由。 |
路由器失效的影响 | 没影响，除了那些路由器崩溃期间丢失的包。 | 穿过故障路由器的所有VC都将崩溃。 |
服务质量 | 困难 | 容易，如果在预先建立每条VC时有足够的资源可以分配。 |
拥塞控制 | 困难 | 容易，如果在预先建立每条VC时有足够的资源可以分配。 |
实现上的一些共同考虑
都需要路由算法的支持：无论是数据报服务还是虚电路服务，都需要根据网络状况（网络拓扑和应用需求）计算从一个源节点到目标节点的路由（一条或多条路径）。
都需要将计算所得的路由分布式保存在路径经过的路由器中。每个路由器只保存路径的一部分（下一跳），所有路由器协同完成数据递交。
数据进入网络后逐跳转发。
数据进入路由器后都需要存储转发（缓存和查表）。
后续内容基于上述共同假设，不再具体区分。所以，本书大部分情况以数据报服务为例，但同样适用于虚电路。
5.2 路由算法
路由算法和路由协议
路由算法和路由协议的最主要的目标是为数据传输寻找一条（或多条，本书主要讨论一条）从源节点到目的节点的路径。这条路径应该能够满足给定的优化目标要求，应该能够反应当前的网络状态（包括网络拓扑—网络的连接情况，和网络的流量负载状况等）。
路由算法和路由协议是路由器中的一个重要功能，目标是建立和维护存放在路由器中的路由表。路由器还有另外一个重要功能，即使用路由表对数据进行的转发功能（被路由功能，如IPv4）。
路由算法是一个优化问题的求解，更为精确的说，是一个受限的优化问题的求解。可以很复杂，有些情况下是NP-hard问题。常用的路由算法使用较为简单的启发式算法求解。本书主要讨论相对简单的启发式算法。
路由算法可以分为集中式路由算法和分布式路由算法。也可以分为静态路由算法和动态（自适应）路由算法。还可以有其它分类形式。
- 集中式路由算法一般要求有一个负责计算路由的中心节点，这个中心节点拥有全局网络信息，求解后的路由结果发送到其它节点。分布式路由算法中每个节点使用局部信息分别计算自己的路由。
- 静态路由算法是实现确定路由，路由确定后不再随着网络状态的变化而改变。动态（自适应）路由算法根据网络当前的情况“实时”确定路由。
路由算法根据网络状态计算路由时，需要了解网络的当前状态，这个状态也是路由算法使用的数据结构。这个结构的获得需要通过网络中路由节点之间交换信息获得，这些信息交换需要遵循一定的规则，属于路由协议。
在本书中，路由算法和路由协议可以交换使用。
路由算法（协议）属于网络层协议的一部分，一般驻留在节点的操作系统中。
虚电路路由只有在建立路径时才计算路径，在使用过程中不再改变，即使网络状态发生剧烈改变。
数据报路由“实时”的根据网络状态修改部分相关节点的路由，不同的数据包可能使用不同的路径。（在数据包传递过程中，路由算法根据当前网络状态修改了路由表）
“实时”一般采用周期性或重大改变触发式的计算路由表。或采用两者结合的方式。
路由算法的特征
路由表既要反应当前的网络状态，又要保持一定的稳定性。需要优化和稳定的折中。不稳定的路由表会造成许多不可知的错误。
路由表的计算既需要达到（近似达到）优化目标，又需要计算简单、用时少。一般路由表需要在相对短的时间内收敛到稳定状态，这个路由表会使用相对较长的时间。
常见的特征有：
- 正确性
- 简单性
- 鲁棒性：在长时间连续运行过程中对于故障的抵抗力
- 稳定性：一个稳定的算法可以迅速收敛，达到平衡，并且保持平衡状态
- 公平性：单个连接的公平
- 有效性：全局的效率（与公平性矛盾）
路由是发现网络路径的过程
- 将网络建模为节点和链接的图形
- 决定优化什么（例如，公平与效率）
- 更新拓扑变化的路由（例如故障）
转发是沿路径发送数据包
5.2.1 Optimality principle 优化原则
最优化原则、sink tree
作为最优化原则的一个直接结果，从所有的源到一个指定目标的最优路径的集合构成了一棵以目标节点为根的树。这样的树称为汇集树（sinktree），如图 5-6 (0）所示，图中的距离度量是跳数。所有路由算法的目标是为所有路由器找到这样的汇集树，并根据汇集树来转发数据包。
最优化原则：如果路由器J在从路由器I到路由器K的最优路径上，那么从J到K的的这一段子路径必定是从J到K的最优路径。
最优化原则可以通过反证法证明。
最优路径通常称为最短路径，可以使用不同的度量值或它们的组合来定义（依据优化目标）：
- 跳数
- 距离
- 带宽
- 平均流量
- 通信成本
- 平均延迟
最优化原则可以避免环路。即遵循最优化原则计算的路径没有环路，但是当网络拓扑收集不准确时，可能造成环路。
5.2.2 Shortest path algorithm 最短路径
最短路径路由
Dijkstra的算法计算图上的汇树：
每个链接都分配了一个非负权重/距离
最短路径是总重量最低的路径
使用权重1给出跳数最少的路径（按1的作用为权重）
算法：
从sink开始，将其他节点的距离设置为无穷大
放松与其他节点的距离
选取距离最小的节点，将其添加到汇点树中
重复此操作，直到所有节点都在汇点树中
最短路径算法用于计算任意两个节点之间的最短路径，网络中经常使用的是迪杰斯特拉算法，当然还有其它的算法。
迪杰斯特拉算法工作在加权无向图或有向图上，先决条件是加权图已知。
迪杰斯特拉算法有几个特点：
- 是一种贪心算法
- 权值为标量
- 权值非负
迪杰斯特拉算法不适用于权值为矢量或权值为负值的情景。
- 矢量加法具有方向性
- 权值为负使得贪心算法不成立
5.2.3 Flooding 泛洪
flooding算法
泛洪（扩散）算法：每个路由节点把从一个端口收到的数据从其它所有端口转发出去。
泛洪算法不需要事先知道网络的拓扑结构图（从现在起，网络拓扑指的是网络连接+权值），所以适用于协议开始时传递拓扑信息（见本章链路状态协议）。
基本的泛洪算法经过所有可能的路径，具备以下特性：
- 最可靠：只要有一条路径连接就能传递到
- 最快：肯定使用了最短路径
- 代价最大：所有路径至少走一遍，通常一条路径就可可以有效支持广播
泛洪算法的优化：
- 每个路由器只转发最新的数据，已经转发过的不再转发
- 限制每个数据被转发的次数（设置一个计数器，每经过一跳计数器减一，计数器为0就丢弃该数据包）
5.2.4 动态路由算法
动态路由算法：每个路由器能够根据当前的网络状态（网络拓扑）计算从自己到所有其它路由器的最短路径。
动态路由算法也称为自适应路由算法，包含两个方面的内容：获得当前的网络状态，根据网络状态计算路由。
根据获得当前网络状态和计算最短路由的不同，常见的路由算法有：
- 距离矢量路由算法
- 链路状态路由算法
- 二者的混合
1. Distance vector routing 距离矢量
距离矢量路由及无穷计算问题
距离矢量路由算法：每个路由器（路由节点）定期地与自己的邻居相互交换距离矢量，根据距离矢量计算路由表。
- 距离矢量是一组矢量<目的节点，距离>
- 是一种分布式的计算方法：根据邻居传来的距离矢量，从自己的邻居中选择距离最短的作为下一跳。每个节点只知道路径的下一跳。
- 是较早的一类路由算法
距离向量是一种分布式路由算法，最短路径计算在节点之间进行分割，算法如下：
- 每个节点都知道与其邻居的链接距离
- 每个节点向所有邻居通告最低已知距离的向量
- 每个节点使用接收到的向量来更新自己的向量
- 定期重复
若遇到距离相同，则选择标号较小的那一个
J到达A、I、H、K的距离：8、10、12、6
故障可能导致DV在寻找无法到达的节点的路径时“计数到无穷大”
距离矢量路由算法只是根据邻居的距离矢量计算自己的路由表，当计算一条路径时，无法判断邻居所说的最短路径是否通过自己（这是分布式算法本身固有的缺陷），所以可能带来环路问题。
环路带来的缺陷是数据在网络中无休止地循环（IP协议中规定了数据分组在网络中的最大存活时间，用以克服环路）
环路带来的第二个缺陷是算法收敛慢，尤其是线路出现问题时很难达到收敛。
常见的克服无穷计算（计数）的方法有：
- 逆向有毒（带有染毒逆向的水平分裂法）：防止路由器向邻居返回一个从该邻居得到的最佳路径
- 抑制定时器：在一段时间内，不接受从邻居传来的不好的路径
- 都存在缺陷
距离矢量路由算法虽然具有一个根本性的缺陷（一个路由节点无法知道自己是否在邻居宣称的最短路径上），从而无法从根本上克服环路问题（即使在理论上，网络实际比理论探讨复杂得多），环路问题可能带来不可预知的网络错误（有时使得网络无法正常运行），但是在很多时候非常有用，尤其是在不同的自治域间计算路由（见Internet框架结构）。
自治域（AS，Autonomous System）指的是由一个组织统一建立、维护、使用的网络（类似于局域网，但现在指的是用于给用户传递数据的广域网ISP）。这个网络的拓扑结构对外保密，能够使用的路径由组织统一发布。域间路由只能根据这些信息计算路由。
最终解决方案是保持完整的路径信息（BGP协议，一种改进的用于域间路由的距离矢量协议）。
2. Link state routing 链路状态
链路状态路由
链路状态路由算法：每个路由器通过定期或触发式扩散自己的邻接信息给所有节点，从而得到完整的网络拓扑图，依据完整拓扑图计算自己的路由表。
- 每个路由节点都需要一张完整而一致的网络拓扑图
- 使用最短路径算法计算从自己到其它所有节点的最短路径，每个节点知道全部的路径信息
- 是改进后的路由算法
链路状态是距离矢量的替代方案，计算量更大，动力学更简单；广泛应用于互联网（OSPF、ISIS）；算法如下：
- 每个节点（可靠地）在LSP（链路状态包）中洪泛其邻居的信息；所有节点都学习完整的网络图
- 每个节点都运行Dijkstra算法来计算每个目的地的路径
Seq.number和age用于可靠的泛洪
新的LSP在所有其他线路上接收和发送的线路上得到确认
示例显示了路由器B上的LSP数据库
source E：通过EAB和EFB发送
如果第四项被转发前，C的链路状态包的一个副本由F到达，则状态位变为100011
链路状态路由算法能够正确运行的基本保证是每个路由节点的邻接信息能够可靠地传递到所有其它路由节点。所以，可靠的扩散算法至关重要。扩散的任意一步（即邻接信息在两个路由器之间的传递）都必须是可靠的，可靠算法参见第3章内容（任意两个相邻的节点之间可靠的数据传输），所以每个节点保留的数据结构中都有转发和确认两个字段。
为了减少可能的错误带来的影响（校验和从理论上无法保证数据100%正确），每个邻接信息只能存活一定的时间（年龄字段）。
为了减少扩散代价，邻接信息使用编号，使用优化后的扩散算法。
即使这样，也可能有环路，主要是邻接信息不能完全正确的在规定时间到达所有路由器，从而带来路由器中的网络拓扑图不一致。
可能碰到的一个部署问题
无论是距离矢量还是链路状态路由算法，都是以所有其它路由器为目标。当网络中的路由器数量增多时，路由表项会随着路由器的增长而线性增长。路由表项过多会带来两个主要的问题：较大的存储空间和较长的查表时间。路由器的存储空间（尤其是快速存储空间NVRAM）有限且价格昂贵；路由器需要尽快地转发分组。这就是由路由器数目增多而带来的扩展性问题（Scalability problem）。这个问题不解决会使得整个网络性能剧烈下降甚至不可用。
解决这个问题的一个思路是层次路由：将大的网络划分为多个区域，区域内部详细路由，区域之间域间路由。
层次路由用于减少路由表项。
距离矢量路由和链路状态路由的比较
3. Hierarchical routing 层次路由
分级路由
分层路由减少了路由计算的工作量，但可能会导致比平面路由稍长的路径.
路由算法计算从一个路由器到其它路由器的最短路径，支持一对一的路径计算和数据传递。
在有些应用中，需要支持广播、组播、选播、移动节点等。这需要根据基本路由算法进行扩展，从而产生了新的路由算法：
- 广播路由
- 组播路由
- 选播路由
- 移动路由
基本解决方式是根据最短路径算法计算一棵树，在路由表中添加相应的表项和相应的转发算法，从而支持数据通过计算得到的树进行传递。在计算构建树时，由于两种路由协议中每个节点所知信息不同而有所不同。
4. Broadcast routing 广播路由
广播路由
广播路由：找到支持数据广播的转发路径。
使用分别为每个节点发送一次的方式非常低效，常用方式是使用类似树结构来进行转发，可以避免在一条线路上转发同样的数据多次。
如果网络运行链路状态路由协议，那么每个节点包含完整的网络拓扑信息，则很自然能够计算从其它所有节点到广播节点的汇聚树。然后依据汇聚树转发给最短路径经过自己的节点。
如果网络运行距离矢量路由协议，每个节点不能计算汇聚树，使用逆向路径转发：当一个节点收到广播分组，判断这个分组是否从自己到广播源节点的最短路径的端口上收到。如果是，则认为是第一份收到的数据，转发给所有其他邻居节点；否则，则认为是重复分组，不再转发。
广播向所有节点发送数据包
RPF（反向路径转发）：将链路上接收到的广播发送到所有剩余链路的源。或者，可以在所有节点上构建和使用汇聚树。
5. Multicast routing 组播路由
组播路由：找到支持数据组播的转发路径
当组成员节点较为稠密时，可以使用基于广播树的方式：直接使用广播树近似，或对广播树剪枝。
如果网络运行链路状态路由协议，则树的生成和剪枝非常自然。
如果网络运行距离矢量路由协议，使用逆向路径转发，通知上游节点剪枝：如果一个路由器连接的主机没有组成员，并且没有收到其它路由器的关于组的连接请求，则认为本节点与组无关，通知上游路由器剪枝掉自己；如果一个路由器原来位于组的转发树（结构）上，现在所有下游节点都提交了剪枝请求，并且自己直接连接的主机再没有组成员，则也向上游路由器发送剪枝掉自己的请求。
dense case
多播发送到称为组的节点子集，为每个组和源使用不同的树
上述组播路由需要为每个组的每个成员建立一棵树，路由节点需要保存的组路由信息较多。
可以使用基于核心（汇聚点）的方式，即为每个组寻找一个核心，组的所有成员都使用最短路径连接到核心。发送时，信息首先传递到核心，然后经核心传递到所有其它节点。
基于核心的方式每个组只需要一棵树。
但是，核心的选择非常困难，在有些目标要求下（如代价最小），问题可能是NP-hard。
最短路径树不一定是最小代价树（Steiner Tree Problem）
sparse case
CBT（基于核心的树）使用单个树进行多播，树是从核心节点到组成员的汇树，多播将进入核心，直到到达CBT
6. Anycast routing 选播路由
选播路由：当节点向一个组传递数据时，只需要向距离最近的一个组节点发送即可；反之，当从一个组接收数据时，也是选择距离自己最近的节点。
实质：所谓组，即为一个分布式系统的多个站点；选播路由就是为当前路由器从这些站点中选择距离自己最近的一个。最近，可以是物理距离，也可以是多个度量值的组合，与已学习的路由算法一致。
当网络使用距离矢量路由算法时，非常简单，所有组成员使用一个统一的标识，直接选择到这个标识的最短路径即可。
当网络使用链路状态路由算法时，可以使用修改的迪杰斯特拉算法从这些站点中选择一个距离自己最近的站点（执行贪心算法，直到第一个组成员标记）
Anycast向一个（最近的）组成员发送数据包，在许多地方与节点脱离常规路由
可以看做某个节点出现在多个位置上（同一个组的不同节点）
使用普通路由的算法找到最近节点位置即可
7. Routing for mobile hosts 移动主机路由
移动路由
移动主机路由：支持主机的移动：能够找到它并将数据传送给它。
移动支持：家乡代理，每台主机到达其它地方后，需要与家乡（登记注册地）服务器通信，告知自己现在的位置。
其它节点向移动主机发送数据时，首先发送到其注册地址（这是主机唯一对外宣称的官方地址），家乡代理将数据转发给移动主机。
移动主机使用当前地址与发送主机联系。
发送主机直接发送到移动主机当前位置。
中间需要隧道技术支持：隧道技术即为封装技术，详细见网络互联。
初始时，每个地点的管理服务器分为三个部分：本地主机在本地，本地主机在外地，外地主机在本地。各个地点的服务器定期交换部分内容，完成路由。
可以通过本地代理联系移动主机
固定归属代理通过隧道将数据包传输到移动主机；回复可以优化后续数据包的路径
不更改路由器或固定主机
8. Routing in ad hoc networks 自组织网络路由
Ad Hoc路由：路由节点也是移动的。通常情况是没有基站的多台主机互联成Ad Hoc网络，每台主机需要作为路由器，为不能直接通信的主机提供路由和转发功能。此时，需要在任意两个节点之间寻找一条能够通信的路径。
按需路由发现，常见的协议为按需距离矢量路由算法（AODV）。
当一个节点需要给另外一个节点发送数据时，首先检查是否存在到达目标节点的路由。一般情况下，移动节点由于内存和电池容量的限制，不会存储并活跃多个路由，所以常见的结果为当前没有路由。这时，扩散路由请求，直到目标节点（或达到最大跳数）。沿着扩散路径逆方向建立路由表。
网络拓扑随着无线节点的移动而变化
路线通常按需制定，例如AODV
5.3 拥塞控制算法
处理拥塞是网络和传输层协同工作的责任
目的：减少拥塞，提高网络整体性能
当过多的流量出现时可能会导致拥塞，拥塞产生后由于过多的数据丢失和重传，致使网络性能下降
Goodput (=useful packets，有效吞吐量)
5.3.1 拥塞控制
拥塞产生的原因
- 传输层注入太多的、超过网络处理能力（网络容量）的数据
- 网络层路由协议不能充分使用网络资源、不能适应流量的分布变化
- 网络资源不足以支持流量
拥塞控制的基本思路
- 网络层的路由节点感知、检测拥塞状况，并在需要时将拥塞状况返回给网络层或传输层相关实体
- 网络层和传输层依据一定的标准处理拥塞
- 拥塞控制可以分为拥塞避免和拥塞处理：提前做好各种准备，避免拥塞的发生，如加大网络资源提供、控制流量准入、调节流量分布特性、设计更好的路由协议等方式避免拥塞的发生；将要或已经发生拥塞时，可以减少流量的注入、流量调节、负载脱落等解决拥塞。
拥塞控制的基本原则
发现拥塞，传递信息，调整系统
- 监控系统，检测何时何地发生拥塞
- 将信息传递给可以采取行动的地方
- 调整系统操作以纠正问题
哪些指标可用于衡量拥堵程度？
Loss of packets 数据包丢失
Queue length 队列长度
Queueing delay 排队延迟
Retransmitted packets due to time out 由于超时而重新传输的数据包
Other variation of the above 上述其他的变体
拥塞避免政策
5.3.2 拥塞控制的途径
网络必须尽最大努力提供负载
- 不同时间尺度下的不同方法
- 节点还应减少提供的负载（传输）
提高网络供给：根据较长时间段的检测，判定网络资源不能支持现有流量，则需要增加网络资源。
- 找到瓶颈资源并提高供给
- 时间较长（几个月甚至更长）
5.3.3 流量感知路由
流量感知路由：将链路负载作为权值计算的一个因素，通过改变链路权值重新计算路由，使新的流量绕开负载较重的热点区域
- 实时改变路由会引发路由震荡
- 要处理陈旧信息对路由计算的影响
- 流量工程：一般将一天的流量归纳为几个特征模板，并为每个模板计算相应的路由，每个模板的路由工作较长时间（几个小时）
- 最新进展：流量工程（微软SWAN），几分钟计算一次
- 问题是对一个实时流量选择哪一个模板，并处理切换时的一系列问题
根据流量选择路由，而不仅仅是拓扑
例如，如果CF已加载，则使用EI进行西向东交通
但要注意避免振荡
5.3.4 准入控制
准入控制：除非网络能够携带额外的流量，否则不再建立新的连接。
- 适用于虚电路
- 可以和流量感知路由算法结合，即为新的连接寻找一条负载较轻的路径
准入控制仅在网络具有足够容量（例如，具有虚拟电路）时才允许新的流量负载
可以与寻找一条不拥挤的路线相结合
5.3.5 流量调节
流量调节：当将要发生拥塞时，感知拥塞的路由节点必须告诉发送节点降低发送速率
- 确定拥塞：一般通过检测路由节点的排队队列长度
- 发送方降低发送速率
- 抑制包：路由节点直接给发送方返回一个抑制包，发送方接收到抑制包后降低发送速率
- 显示拥塞通知（ECN）：设置分组头部的位表明拥塞，接收方返回数据时将此通知返回给发送方，发送方收到通知后降低发送速率
- 逐跳后压：抑制包在返回途中逐跳降低所经过路由节点的发送速率
抑制包（choke packet）
通知拥塞发送方的最直接方式是直接告诉发送方。在这种方法中，路由器选择一个被拥塞的数据包，给该数据包的源主机返回一个抑制包（choke packet）。抑制包中的目标地址取自该拥塞数据包。同时，在原来的拥塞数据包上添加一个标记（设置头部中的一位〉，因而它在前行的路径上不会产生更多的抑制包。除此以外，数据包的转发过程如同平常一样。
当源主机收到了抑制包，按照要求它必须减少发送给指定目标的流量，
显式拥塞通知 (ECN, Explicit Congestion Notification)
拥挤的路由器向主机发送信号以降低流量
ECN（显式拥塞通知）标记数据包，接收器向发送器返回信号
逐跳后压
5.3.5 负载脱落
负载脱落：当上述方法不能完全消除拥塞时，随机丢弃部分分组。
- 可以根据应用不同，设置不同的分组选择策略：对文件传输而言，旧的分组更好，选择丢弃新的分组；对语音通信而言，新的分组更好，选择丢弃旧的分组。
- 但是设定由用户完成，如何刺激大家选择合适的优先级不容易
拥塞控制（RED）
- 在Internet中，使用随机早期检测协议（RED，Random Early Detection）：每个路由器实时检测队列长度，如果超过一定的阈值，代表将要发生拥塞，尽早地随机选择一些分组丢弃。RED协议尤其适用于不支持ECN的网络中。现在新的拥塞控制主要集中在基于ECN的拥塞控制（新的路由器支持）
5.4 服务质量 QoS
服务质量机制是根据网络实际状态和用户的需求，确定用户数据的传输方案，使之与要求尽量匹配的一些方法的统称。本部分内容主要要求一些基本的方法，更加精细的算法很多很复杂。
- 流量整形：将随机的用户流量进行规则化处理，以便网络路由。包括漏桶和令牌桶算法。
- 包调度算法：使用多个队列对不同用户需求进行调度，以便“公平”地使用网络资源。
- 准入控制：根据用户服务质量需求描述，确定用户传输数据所使用路径的允许与否。
- 综合服务：一种广泛应用于组播的资源预留方式。
- 区分服务：对用户数据进行类型（优先级）设置，并根据不同类型提供不同资源使用的方式。
服务质量取决于可靠性、延迟、抖动、带宽
5.4.1 Application requirements 应用需求
不同的应用程序关心不同的属性
我们希望所有应用程序都能得到他们需要的东西
Jitter Control 抖动控制
抖动、缓冲
延迟的变化（标准差）或者数据包到达时间的变化称为抖动
网络提供具有不同QoS（服务质量）的服务以满足应用需求
Network Service | Application |
Constant bit rate | Telephony |
Real-time variable bit rate | Videoconferencing |
Non-real-time variable bit rate | Streaming a movie |
Available bit rate | File transfer |
5.4.2 Traffic shaping 流量整形
流量整形调节进入网络的数据的平均速率和突发性
流量整形（也称为“数据包整形”）是一种计算机网络流量管理技术，它延迟部分或全部数据报，使其符合所需的流量配置文件。流量整形是一种限速形式。
流量整形通常与以下内容结合使用：
- 差异化服务、集成服务——包括流量分类和优先级。
- 加权循环赛（WRR）
- 随机早期检测（RED）、加权红色（WRED）和红色输入/输出（RIO）——降低了端口队列缓冲区尾部丢失的可能性，从而降低了TCP全局同步的可能性。
- 多个端口队列缓冲区。
漏桶和令牌捅
漏桶算法、令牌桶算法
令牌/泄漏桶限制了流量的平均速率（R）和短期突发（B）
对于token，桶大小为B，水以R的速度进入并被移除发送；与leaky相反。
漏桶和令牌桶是网络中用于流量整形的主要方法。根据所学知识，回答下面问题：
1）漏桶的工作原理是什么？
① 在每个主机连接到网络的接口处都包含一个漏桶，即一个有限长度的内部队列。
② 如果当队列满的时候，又有一个分组到来，则该分组被抛弃。
③ 每经过一个常数时间才允许把一个分组放到网络上。
④ 这种机制可以将主机内用户进程发送出来的一个不均匀分组流变成网络上的一个均匀分组流，他把突发的分组流变得很平滑，从而降低了拥塞的几率。
⑤ 无论负载突发性如何，漏桶算法都强迫输出按平均速率进行。
2）令牌桶的工作原理是什么？
① 漏桶中保存的是令牌，这些令牌由时钟产生，每隔T产生一个。
② 要使一个分组被传送出去它就必须要抓住并销毁一个令牌。
③ 令牌桶允许将令牌（即许可权）保存起来，直至达到桶的最大尺寸n
④ 当令牌桶满后，令牌桶丢弃令牌，不丢弃分组。
⑤ 从本质上讲，令牌桶所做的事情是：允许突发流量但是不得超过一个预定的最大值
3）区别
① 流量整形策略不同：漏桶法不允许将空闲的主机许可权保存起来以便将来发送更大的突发数据，而令牌法则允许将许可权保存起来，直至达到桶的最大尺寸。
② 丢弃对象不同：当令牌桶满了之后，丢弃令牌，但是不丢弃分组；相反的，在漏桶算法中丢弃分组。
计算题例题：在一个5Mbps网络上有一台主机，其流量通过一个令牌桶整型，令牌桶的填充速率为2Mbps。初始时令牌桶被填满到容量8Mb。试问该计算机能以5Mbps的全速率传输多长时间。
设时间为t
∴ t = 8/3 s
5.4.3 Packet scheduling 包调度
在同一个流的数据包之间以及在竞争流之间分配路由器资源的算法称为（数据）包调度算法（packetscheduling algorithms）
例：
5.4.4 Admission control 准入控制
准入控制通过是否允许一个流进入网络来避免多个流对网络资源的过度使用，从而影响服务质量。
准入控制采用流量规范，并决定网络是否可以承载它
有一个对应于带宽和延迟性能保证的流规格说明方法。该方法在流量源端采用 CR, B）令牌桶整形，而在路由器采用 WFQ。每个流都有一个WFQ权重W，该权重值足够大到能排空速率为R的令牌桶，如图5-33所示。例如，如果流的速率为 lMbps，路由器和输出链路的容量为 l Gbps，那么在路由器的输出链路上该流的权重必须大于所有流的全部权重的千分之一。这保证了该流具有最低带宽。如果流得不到足够大的速度，那么该流就不允许进入网络。
5.4.5 Integrated services 综合服务
综合服务主要用于针对单播和组播应用
资源预留
为每个流设计QoS；处理多播流量。资源预留协议（RSVP, Resource reSerVation Protocol）：
- 接收方将请求发送回发送方
- 沿途的每个路由器都保留了资源
- 路由器合并同一流的多个请求
- 整个路径已设置，或未进行预订
组播路由算法（树的计算、建立和维护）、使用树结构进行组播数据传递等都不属于RSVP协议的内容。RSVP协议只关心资源的预留，当然这些功能需要相互配合。
综合服务带来的可扩展性问题
综合服务协议会带来路由器的可扩展问题（相对于路由器节点太多引发的可扩展性问题，层次路由），这个问题的核心是每个流（无论是组播还是单播）都需要途经的路由器保存一个路由表项。
当网络中存在越来越多的流时，路由表项会随着流的数目线性增长，对这些表项的计算和维护需要的计算、存储资源和信息交换也会不断增长，最终导致网络性能下降甚至崩溃。
Internet中一般不支持基于 流的路由算法或协议，只是与目的地址有关，称为无状态路由算法。
常用于服务质量的协议为基于类别的区分服务。
5.4.6 Differentiated services 区分服务
按QoS等级进行设计；每个服务类别对应特定的转发规则；顾客买他们想要的东西
加急班优先于普通班
流量速度较慢，但应用程序质量更好
DiffServ的实现：
客户在包装上标记所需的类别
ISP调整流量以确保标记是付费的
路由器使用WFQ提供不同的服务级别
确保转发：4种优先级别和三种丢弃概率（12种服务）
5.5 网络互联
一个互联网络的集合：
5.5.1 How networks differ 网络的区别
5.5.2 How networks can be connected 网络怎样连接
基于公共网络层（IP）的互联网
不同类型网络互联
互联不同协议的网络非常复杂，协议转换通常不是首选项。
不同类型网络关注的重点、采用的技术方案可能区别很大，体现在实现上则是协议采纳的数据结构（头部）和处理数据结构的算法可能具有很大的差异。
从一种协议到另外一种协议的转换可能会丢失一些信息，也可能需要一些新的信息。
最终的协议转换过程可以类比常见的一种游戏：每个人带着耳机看上一个人表演然后表演给下一个人。
5.5.3 Tunneling 隧道技术
网络互连（隧道技术）
隧道技术是解决不同种类网络互联一个特例的方法。
隧道技术用于解决发送和接收网络属于同一类型网络，但是中间经过不同类型网络的情况。
隧道技术是一种封装技术，在中间网络传输时将整个数据包使用中间网络的协议类型封装。
网络种类不同，则封装数据包的头部和对头部的处理方法不同，而数据包的头部和对头部处理的方法驱动数据在网络中被路由，不同的头部及其处理方法对应于汽车的引擎。
5.5.4 Internetwork routing 互联网路由
5.5.5 Packet fragmentation 数据包分段
不同类型的网络互联还会带来另外一个问题，即不同网络支持的最大传输单元（MTU，Maximum Transmission Unit）不同。通俗讲，就是每个网络一次数据传输的最大能力不同。
带来的问题：当一个大的分组经过一个MTU较小的网络时不能直接把这个分组传输，无法承载大于MTU的数据。
可能的解决方案是在网络的入口路由器将其分成小的部分（分段），在出口路由器或以后的某个地方重新组装。
组装是难点。需要分段时做一些额外数据结构和算法（具体见IPv4）
路径MTU发现避免了网络碎片
- 路由器向源返回MTU（最大传输单元）并丢弃大数据包
5.6 Internet网络层
Internet的网络层主要包括Internet完成网络层主要功能的协议栈，包括：。
- Internet路由协议：用于计算任意两个节点之间的数据传输路径，并将路径分布保存在途径的路由器中；包括域内路由（OSPF）和域间路由（BGP）。主要原理在5.2节已经学习，这里只是两个实例。
- Internet数据转发（被路由）协议：规定数据在Internet中传输时应该遵循的协议，只有遵循这个协议，数据才能够被网络沿着路由协议计算所得的路径（路由表）从发送方逐跳交换到接收方。包括协议格式（IPv4协议头、IPv6协议头）以及处理算法。协议除了需要支持正常的转发功能、服务质量以外，还需要处理不同网络互联带来的一些问题，主要是数据包分段等。
- Internet控制协议：用于在网络中传递控制信息（ICMP协议）、支持转发数据时需要的链路层地址（ARP协议）、动态主机配置协议等。
- IP地址：用于标识网络上的设备，并基于此进行路由转发。为了克服由于节点数目太多带来的路由器中路由表项可扩展性问题，采用了层次地址，并具有明显的地理指向性。为了支持层次路由，分类IP地址和不分类IP地址的相关机制。
- IP组播：支持网络层的组播功能。原理5.2节已介绍。
- 移动IP：支持节点的移动性。原理与第4章、5.2节相似
5.6.1 IPv4 协议
IPv4协议
IPv4协议是过去几十年最主要的网络层协议之一，提供尽力而为（best effort）或尽最大努力的数据传输服务。
IPv4协议驻留（运行）在Internet主机的操作系统内，驻留在路由器的网络层中。
IPv4支持最基本的数据传输服务，如数据包逐跳转发、数据包分段等。
IPv4协议很少提供服务质量等功能的支持，在支持越来越多的种类不同的数据传输服务要求时，出现了所谓“瘦腰现象”。
网络控制信息等使用IPv4协议格式封装，支持控制信息在网络内的传递。
IPv4协议对应的协议数据单元是数据包（分组），包括头和数据两个部分。数据来自于上层协议（传输层协议）或IPv4服务的网络层协议（网络控制信息协议）等。
IPv4协议分为协议头和处理算法，头格式规定了数据传递时必须携带的信息，处理算法根据这些信息完成数据的递交。
IPv4协议头由20字节定长部分和可选的变长部分组成。
- 版本（4位）：协议属于的版本，常见的取值为4（0100）和6（0110）。发送方机器设定，中间经过的路由器和最终的接收方读取数值，确定使用什么格式解析头部。
- 头长（IHL，4位）：规定了头部的长度，取值范围为5~15，单位为4字节（或格式中的一行）。最小头长为20字节（固定头部），最大头长为60字节（可选头部最长40字节）。
- 区分服务（DS，8位）：前6位标记数据包的服务类型，路由器根据不同的服务类型采取不同的调度方式（见5.4节区分服务）；后2位用于携带显示拥塞通知（ECN），用于标识数据包在传递过程中是否经历了拥塞，路由器或发送主机依次调整速率。（见5.3节拥塞控制）
- 总长度（16位）：整个数据包的长度，以字节为单位，包括头和数据的总长度。最大取值为65535。
运行在以太网中的主机发送或接收的数据包长度受到以太网帧最大长度的限制：以太网帧最大负载为1500字节，所以一个数据包在以太网中传输时其总长度取值不大于1500.
- 标识（ID，16位）：标识一个数据包。如果数据包需要分段，则需要将数据包的数据字段分成多份，每份数据再封装为一个数据包（添加数据包头部，为了能够路由转发），分段的数据包（子数据包）中的标识字段与被分段数据包（父数据包）的标识一致（继承）。重新组装时，将标识一样的数据包组装。
- 不分段（DF，1位）：标识数据包不能分段。如果携带此标识的数据包进入一个小分组网络（MTU不支持携带的数据量），则被拒绝转发，并发送相应消息。
- 更多段（MF，1位）：标识后面是否还有分段，置位标识还有，否则没有，自己就是最后一段。MF=1，DF=0表示后面还有分段
- 分段偏移量（fragment offset，13位）：标识本分段数据在原来数据包数据中的位置（偏移量），8字节为单位。
- 生存期（TTL，8位）：用于规定数据包在网络中存在的时间。可以取值为时间单位（秒），也可以取值为跳数。每经过一个时间单位或一跳减一，为0时丢弃该数据包。一个重要应用是避免数据包在网络上由于路由环路（5.2节提到路由环路不可避免）在网络上无休止地循环。也可用于探测网络路径。
- 协议（protocol，8位）：用于标识数据包中所携带数据的类型。将数据提交给指定的处理进程。
- 头校验和（16位）：用于确定头部在传输过程中是否发生了错误。由于IP协议不提供可靠的传输，所以不对整个分组（数据）校验；由于头部携带的信息对于路由数据非常重要，所以校验头部。经常使用的是反码加法。头校验和每跳都会变化（至少TTL发生变化）。
- 源地址（Source Address，32位）：发送方的IP地址。用于中间路由器向发送方发送某种控制信息（如抑制分组），或接收方回复。
- 目标地址（Destination Address，32位）：接收方的IP地址。用于查表，确定转发路径。
- 选项（Options，0~40字节）：4字节的倍数，用于可选择的功能，如源路由、时间戳等。
分段举例：一个大的IP分组经过小分组网络时，被分成了多个小的分组。
- 分段过程：将大的分组的数据分成若干部分，为每部分封装一个IP头。子分组的头部字段取值与父分组头部字段的关系：如版本号、头长度、区分服务、标识、生存期、协议、源地址、目标地址等字段直接继承；跟分段相关的字段如总长度、MF、分段偏移量等需要根据分段情况填写。
- 组装过程：根据与分段相关的字段将各分段携带的数据组装在一起，为其封装一个IP头。组装时，标识号一致的分段需要组装为一个分组；判断所有数据是否都已经收到，根据总长度、分段偏移量、MF、IHL计算判断。
5.6.2 IP 地址
IP地址、子网、子网掩码、子网划分
IPv4地址长度为32位，用于标识一台主机或路由器的一个端口。
IP地址是一种逻辑地址，为了减少为每个IP地址单独路由引发的路由器表项过多（路由器表项可扩展性问题），通常采用层次地址。即IP地址的一部分用于标识所在的网络，另一部分标识在网络中的编号，分别称为网络地址和主机地址。
路由器表项只保存到一个网络的路由表项，负责将分组递交到所在的网络。
与网卡地址（MAC地址）不同：位于同一个网络的网卡地址原则上没有任何关系，是相互独立的。真正通信时，需要IP地址与网卡地址的转换（ARP协议）。
IP地址的网络号也称为（网络）前缀。原则上，位于同一个网络的主机之间具有相同的网络号。
路由器的一个端口与其所连接的设备属于同一个网络。如果路由器的端口与一个子网相连，则此端口和网络中所有主机属于同一个网络，分配的IP地址具有相同的网络号；如果路由器的端口与另外一台路由器的某个端口相连，则这两个不同路由器的端口也属于同一个网络。
IP地址中的网络号需要某种声明：一种是子网掩码，一种是分类的IP地址（稍后介绍）。
子网掩码：用于声明IP地址中网络前缀的长度（前多少位为网络号）。
子网掩码的定义方式：与IP地址位数相同，如果一个IP地址中某一位属于网络号，则子网掩码对应的位置1，否则置0。
IP地址和子网掩码都可以使用点分十进制表示。
由于IP地址定义为“网络号+主机号”，所以，子网掩码的形式为“111……1000……0”。可以使用两种方式声明：“255.255.0.0”或“IP/16”
IP地址与子网掩码“按位与”，就得到IP地址所在的网络。通常一个网络使用主机全0表示。
地址以称为prefixes前缀的块分配
- 前缀由网络部分决定
- 有地址在边界上对齐
- 书面地址/长度，例如18.0.31.0/24
IP地址举例：与主机（202.194.196.80，子网掩码：255.255.240.0） 在同一个网络内的其它主机的IP地址范围是什么？
思路：这个网络内的主机的IP地址具有相同的网络号，主机号任意配置。
第一步：首先计算主机所在网络的网络号。使用已知主机的IP地址和子网掩码按位与即可。
第二步：主机号从全0到全1。最后可以去掉有特殊意义的主机位全0和全1。
子网掩码：255.255.11110000.00000000【有连续8+8+4=20位1】
主机：202.194.11000100.80
可以得到最小的网络号：202.194.192.0（202.194.11000000.0）
最大的网络号：202.194.207.255（202.194.11001111.255）
得到IP地址范围为（因为是IP地址范围，所以不包含全0和全1）：202.194.192.1~202.194.207.254
子网、子网划分
当一个网络规模较大时（网络号较短、主机号较长，能够容纳很多的主机），根据需要，可以进一步将这个网络划分为多个子网。
在内部将一个网络块分成几个部分供多个内部网络使用，但对外部世界仍然像单个网络一样。这就是所谓的子网划分（subnetting），分割一个大型网络得到的一系列结果网络（比如以太网〉称为子网（subnet）。
子网划分方法：从主机位的最高位置根据需要拿出一位或几位作为子网的编号。划分的原则是每个划分后的子网必须具有相同的网络号，并且主机空间满足子网要求。（与后面的CIDR相似）
一个网络划分为多个子网时，需要路由器的支持，路由器的一个接口作为对外接口与外界相连，作为整个网络的代表；其它接口作为对内接口，分别对应不同的子网。
从外部看起来，还是一个网络。从内部，区分不同的网络。
实现上，其它路由器只保留最初的网络表项；只有内部路由器，保留多个子网的表项。这样的方式，使得每个网络（组织）内部的划分不影响外面的其它节点。
子网划分举例：见下图
第一步：根据每个子网规模需求，为其确定子网；
第二部：在内部路由器上填上相应的表项。
子网划分后的路由分析。
子网划分IP前缀以帮助管理，看起来像是网络外的单个前缀
IP地址：
- 子网部分（高位比特）
- 主机部分（低位）
什么是子网？
- 具有相同IP地址子网部分的设备接口
- 可以在没有路由器干预的情况下物理地相互连接
当一个IP数据包到达主路由器，路由器如何知道应该将它转发到哪个子网？
当数据包到达时，路由器会查看该数据包的目标地址，井检查它属于哪个子网。具体做法是：路由器把数据包的目标地址与每个子网的掩码进行 AND 操作，看结果是否对应于某个前缀。
CIDR(无类域间路由)
CIDR、地址聚合技术
CIDR: Classless InterDomain Routing 无类域间路由
为了进一步减少路由表项，可以将地理位置相同的网络聚合成一个更大的网络。使得其它位置的路由器能够使用一个（或几个）路由表项为这些网络进行数据转发。
聚合的原理与子网划分类似。
从伦敦几个大学申请IP地址开始。
聚合后的路由表项和路由过程。
最长前缀匹配。如果有一个分组与多个路由表项匹配，则按最长匹配转发。
聚合将多个IP前缀连接到一个更大的前缀中，以减少路由表的大小
最长匹配前缀（longest matching prefix ）
CIDR的工作原理：当一个数据包到达时，路由器扫描路由表以确定目的地是否在前缀的地址块内。有可能多个具有不同前缀的表项得到匹配，在这种情况下，使用具有最长前缀的表项，具体方法
- 计算每个prefix对应的子网掩码
- 每个子网掩码和数据包ip地址进行与操作对比prefix
- 多个match选择子prefix长的选项
分类和特殊寻址
A：128个网络，每个网络1600万台机器；
B：16384个网络，每个网络65536台机器；
C：200万个网络，256台机器
NAT－网络地址转换
NAT
网络地址转换协议，在网络内部使用私有地址，在网络外部使用公有地址。当一个节点需要向外网发送数据时，将内网的私有IP地址转换为公有IP地址，并将端口号映射为新的端口号。当接受一个数据时，通过映射关系查找对应的私有IP地址及传输层端口号，重新封装传递。
5.6.3 IPv6协议
它的主要目标是：
( 1 ）即使地址空间的分配效率不高，也能支持几十亿台主机。
(2）降低路由表的大小。
(3 ）简化协议，使路由器更快速地处理数据包。
(4）提供更好的安全（认证和隐私）。
(5 ）更加关注服务类型，特别是针对实时数据。
(6）辅助指定范围内的组播。
(7）主机漫游时无须改变地址。
(8 ）允许协议向未来演进。
(9 ）允许新老协议共存多年。
主要的IPv6头
- 区分服务（Differentiated services，最初称为流量类别〉字段的用途主要是区分数据包的服务类别，这些数据包具有不同的实时传递需求。它主要被用在服务质量的区分服务体系中， 使用方式与IPv4数据包的同名字段一样。此外，最低2位用来发送显式拥塞指示，也与IPv4 的方式相同。
- 流标签（Flowlabel) 字段为源端和接收方提供了一种建立伪连接的方式，即源端和接收方把一组具有同样需求并希望得到网络同等对待的数据包打上标记。
- Next header: identify upper layer protocol for data
Next hearder指的当前头之后还有哪种扩展头；若是IP最后一个头，则定义了upper layer的协议（TCP/UDP）
- 校验和（Checksum）字段被去掉了，因为计算校验和会极大地降低性能。
- Options：被允许，但在header之外，由“Next Header”字段指示
- ICMPv6：ICMP的新版本
- 隧道：IPv4路由器之间的IPv4数据报中携带IPv6作为有效载荷
扩展头
巨型数据报Header格式
- Next header：接下来是哪个头
- 第二个字段（0），不包含起始的8个强制的字节以外当前逐跳扩展头有几个字节
- 第三个字段表明该选项定义的是数据报的长度（代码194），以4个字节为单
- Jumbo payload length：数据报payload的长度
路由扩展头：
- Next header和header extension length与定义上一个扩展头相同
- 路由类型给出了剩余部分的格式
- 剩余段数：记录地址列表中还有多少地址尚未被访问到
5.6.4 Internet控制协议
ICMP——Internet 控制消息协议
ICMP
是返回错误信息的IP的companion
ARP——地址解析协议
ARP工作过程
查找本地IP地址的以太网地址
ARP（地址解析协议）让节点从其IP地址中找到目标以太网地址
某一层的地址只在本层有效，网络层负责寻找路径，而真正实现消息传递的是链路层，所以要实现两层地址之间的映射。
即关键在于已知源IP、源MAC和目的IP的情况下怎样获取目的MAC
具体例子如上图所示，有两个/24的网络（左侧为CS网络，右侧为EE网络），这两个局域网通过一个IP路由器相连。以太网的每台机器和路由器上的每个接口都有一个唯一的以太网地址，E1~E6。
1. （同一子网的消息传递）主机1用户给主机2用户发送数据包
① 根据已知域名找到主机2的IP（由DNS系统返回IP地址）
② 主机 1 发送一个广播包到以太网络上请求拥有 IP 地址192.32.6.5.5 的主机。该广播包将会到达 cs 网络上的每一台主机，并且每台主机都会检查自己的IP地址。只有主机2会用自己的以太网地址 (E2)作为应答。通过这种方式，主机1 得知IP 地址 192.32.65.5 是一台拥有以太网地址为E2的主机。
请求和获得应答两个过程所使用的协议称为地址解析协议 (ARP, Address Resolution Protocol）
2. （不同子网消息的传递）主机 1 给 EE 网络上的主机 4发送数据包
（1）主机 1 发现目标 IP 地址不在 cs 网络。同时它知道应该把所有这些网络外的流量发给路由器，该路由器称为默认网关（Defaultgateway）
按照惯例，默认网关具有网络上的最低地址（198.31.65.1 ）。
为了给路由器发送帧，主机 1 必须知道该路由器在cs 网络上的接口地址。因此，主机1 发送一个ARP广播报文，请求198.31.65.1 对应的以太网地址，从该广播报文的应答报文它获知所需的以太网地址为E3：然后用该地址给路由器发送帧。
如果路由器不知道主机4的以太网地址，它可以再次使用ARP。
（2）主机1不知道主机4在另一个子网上，仍然可以从主机1 发送一个数据包给主机4。解决办法是让cs 网络上的路由器回答针对主机4的ARP请求，并且以E3 作为响应。然后，路由器将收到发给192.32.63.8 的帧，并将该帧转发到 EE 网络。这个解决方案称为ARP代理（proxyARP）
在以太网上广播时，以太网帧的目的地址全为1，即FF-FF-FF-FF-FF-FF-FF
DHCP——动态主机配置协议
DHCP
动态主机配置协议（DHCP）是用于互联网协议（IP）网络上的主机的网络配置协议。
连接到IP网络的计算机必须先进行配置，然后才能与其他主机通信。
所需的最基本信息是IP地址、默认路由和路由前缀。
DHCP消除了网络管理员的手动任务。
它还提供了一个连接到网络的设备的中央数据库，并消除了重复的资源分配。
5.6.5 标签交换和MPLS
MPLS（多协议标签交换）沿着已建立的路径发送数据包；ISP可以用于QoS
在IP前添加一个MPLS header用于存储标签
MPLS header字段
- 共四个字节，四个字段。
- 标签存放索引用于标签交换
- QoS字段指明服务类型
- S字段涉及层次网络中叠加多个标签
- TTL字段表明还可以被转发几次
当数据包进入MPLS网络时根据IP地址添加标签，离开时去除标签
- 在MPLS网络中进行转发只使用标签信息
- MPLS可以转发IP数据包和非IP数据包（多协议）
- MPLS可以在一个数据包前添加多个标签，从而同时在多个标签层次上运行
5.6.6 OSPF一一内部网关路由协议
OSPF
OSPF 在一个自治系统内部计算路由
- 一个自治系统根据实际的链接情况可以抽象为一个带权值的有向图
- 路由器之间有双向链路，权值可能不同；广播网络到路由器双向，但网络到路由器权值为0（广播网络会把数据传递到每个出境口），路由器到局域网是单向的（局域网只有主机，无路由功能路径只能到达不能穿越）
“open”: publicly available（不属于任何一家公司私有）
Uses Link State algorithm （使用链路状态算法进行路由）
- LS packet dissemination（链路状态包扩散）
- Topology map at each node（在每个节点建立网络拓扑图）
- Route computation using Dijkstra’s algorithm（在网络拓扑图上运行最短路径算法）
OSPF广播包会为每一个和它临接的路由器携带一条信息
广播信息会通过泛洪算法扩散到整个自治系统
- OSPF的广播信息是通过IP数据包（而不是TCP或UDP）进行传递
OSPF是一个基于连接状态的路由方法
OSPF把一个大的网络（自治系统）分割为多个带编号的区域，这些区域都连接到骨干区域（或0号区域）
- AS内任何一个区域出发，通过骨干区域，都可以到达AS内部的任意另一个区域
- 两个在不同区域内的主机通信一定要通过骨干区域
- 连接到两个或以上区域的路由器叫做区域边界路由器（它必须是骨干区域的一部分？）
- 只有一个边界路由器通往区域外，叫做存根区域（stub area），存根区域不需要外部路由信息，因为只有一个路由选择。
- 通往其他AS的路由器是AS边界路由器
5.6.7 BGP一一外部网关路由协议
BGP
BGP计算相互连接的自治系统之间的路由
- BGP和OSPF最重要的区别是BGP还需要考虑各种网络背后组织的政策限制（比如，有的AS系统不希望转发跟它没有关系的数据包，美国发出的数据不能通过伊拉克）
通常的传输AS间的路由政策包括中转传输和对等传输
- 中转服务需要付费购买，对等传输的对等体双方都将获益（降低中转服务账单）
- 图中AS1可以为AS2和AS4之间的数据传递提供中转服务，AS3只会分别和AS2和AS4进行对等传输
BPG沿着政策允许的路由传递信息
- BGP是距离矢量协议的一种形式，但与域内距离矢量协议有很大区别
- BGP告知路由的方向（建立传输路由）的方向与数据的路径方向相反
- BGP告知路由信息包括前缀（目的地址，AS路径，下一跳路由器）
互联网AS间路由：BGP
a)BGP (Border Gateway Protocol): the de facto standard（实际使用的标准）
b)BGP给每个AS提供了方法去：
1.从相邻的AS获得子网的可到达信息
2.把可到达信息传递给AS内部所有路由器
3.根据可到达信息和政策决定一个好的路由
c)BGP还可以允许一个子网向互联网其他区域广播它的存在
为什么AS内和AS间路由不同？
Policy:
- Inter-AS: 网络管理者要控制自己的流量怎样路由，并且决定谁的路由可以通过自己的网络
- Intra-AS: 单一管理者完全控制一个AS，不需要考虑其他政策
- Scale: 使用层次路由来节省路由表的尺寸，减少路由表更新带来的流量
5.6.8 Internet Multicasting（互联网组播）
互联网组播中分组使用预留的IP地址范围（class D）
- 28位用于标识组，网络可以同时并存250万个组
- 路由器上的组播管理协议管理分组
PIM协议负责计算组播路由
- Dense mode uses RPF（逆向路径转发树） with pruning
- Sparse mode uses core-based trees（稀疏模式使用核心树）
除了数据中心和有线电视网络以为，IP组播用处不多
5.6.9 移动IP
移动IP协议的设计需求
- 每台主机可以在任何地方使用它的家乡IP地址
- 不允许修改固定主机的软件
- 不允许改动路由器软件和各类表
- 发给移动主机的大多数数据包不应该绕道而行
- 移动主机在家时不应该有任何开销
移动IP解决方案
- 每个允许用户漫游的网点必须创建一个 家乡代理
- 移动主机出现在一个外地网点时，获得一个外地网点的新IP地址（交地址）
- 移动主机通过转交地址通知家乡代理
- 家乡地址获得发送给该移动主机的数据，隧道给当前在外（转交地址）的移动主机
- 不管通信对方是谁，移动主机都可以直接发送应答数据包，但使用家乡地址作为应答数据包的源地址。
