《计网：自顶向下》读书笔记（四）——网络层

4.1 概述

4.1.1 转发和选路

网络层的作用是将分组从一台发送主机移动到一台接收主机，为此需要两种重要的网络层功能：1)转发（当一个分组到达某路由器的一条输入链路时，该路由器必须将该分组移动到适当的输出链路），2)选路（当分组从发送方流向接收方时，网络层必须决定这些分组所采用的路由或路径，计算这些路径的算法被称为选路算法（routing algorithm））。
转发是指将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作。选路是指分组从源到目的地时，决定端到端路径的网络范围的进程。
每台路由器具有一张转发表（forwarding table），路由器通过检查到达分组首部中的一个字段的值，然后使用该值在该路由器的转发表中索引查询来转发一个分组，查询转发表的结果是分组将被转发的路由器的链路接口。
分组交换机是指一台通用分组交换设备，它根据分组首部字段中的值，从输入链路接口到输出链路接口传送分组。某些分组交换机称为链路层交换机（link-layer switch），它们基于链路层中的作转发决定。其他分组交换机称为路由器（router），它们基于网络层字段中的值作转发决定。
网络层还有一种重要的网络功能，即连接建立（connection setup）。

4.1.2 网络服务模型

网络服务模型（network service model）定义网络的一侧边缘到另一侧边缘之间（即发送端系统与接收端系统之间）分组的端到端运输特性。
发送主机中，当运输层向网络层传递一个分组时，能由网络层提供的特定服务包括：确保交付、具有时延上界的确保交付，此外这些服务能够为给定的源和目的地之间提供分组的流：有序分组交付、确保最小带宽、确保最大时延抖动、安全*。
因特网的网络层提供了单一的服务，称为尽力而为服务（best-effort service）**。

4.2 虚电路和数据报电路

仅在网络层提供连接服务的计算机网络被称为虚电路（Virtual-Circuit，VC）网络；仅在网络层提供无连接服务的计算机网络被称为数据报网络（datagram network）。
因特网是数据报网络。

4.2.1 虚电路网络

一条虚电路（VC）的组成如下：1)源和目的主机之间的路径；2)VC号，沿着该路径的每段链路一个号码；3)沿着该路径的每台路由器中的转发表表项。属于一条虚电路的分组将在它的首部携带一个VC号，因为一条虚电路在每条链路上可能具有不同的VC号，所以每台中间路由器必须用一个新的VC号替代每个传输分组的VC号，该新的VC号从转发表获得。
在虚电路网络中，该网络的路由器必须为进行中的连接维持连接状态信息（connection state information）。
在虚电路中有3个明显不同的阶段：1)虚电路建立，2)数据传送，3)虚电路拆除。
端系统向网络发送指示虚电路启动与终止的报文，以及路由器之间传递的用于建立虚电路（即修改路由器表中的连接状态）的报文被称为信令报文（signaling message），用来交换这些报文的协议常称为信令协议（signaling protocol）。

4.2.2 数据报网络

在数据报网络（datagram network）中，每当一个端系统要发送分组时，它就为该分组加上目的地端系统的地址，然后将该分组推进网络中，完成这些无需建立任何虚电路。在数据报网络中，路由器不维护任何有关虚电路的状态信息。
路由器用分组的目的地址的前缀（prefix）与转发表中的表项进行匹配，如果存在匹配，该路由器向与该匹配相联系的链路转发分组。路由器使用最长前缀匹配规则（longest prefix matching rule），即在转发表中寻找最长的匹配项，并向与最长前缀匹配的链路接口转发该分组。

4.2.3 虚电路和数据报网络的由来

4.3 路由器工作原理

网络层的转发功能（forwarding function），即实际将分组从一台路由器的入链路传送到适当的出链路。
一台路由器有4个组成部分：输入端口、交换结构、输出端口和选路处理器。

4.3.1 输入端口

达到线路速度（line speed），即执行一次查找的时间少于从输入端口接收一个分组所需的时间。
内容可寻址内存（Content Addressable Momery，CAM）允许一个32比特IP地址提交给CAM，由它再以基本上常数时间返回该地址对应的转发表表项内容。也可以将转发表表项保存在高速缓存中。
一个分组可能会在进入交换结构时暂时阻塞（blocked），这是由于来自其他输入端口的分组当前正在使用该交换结构。

4.3.2 交换结构

三种交换技术是：经内存交换、经一根总线交换和经一个互联网络交换。

4.3.3 输出端口

4.3.4 何时出现排队

输入端口和输出端口处都能形成分组队列，随着这些队列的增长，路由器的缓存空间将会最终耗尽，且出现丢包（packet loss）。
交换结构速率（switching fabric speed）即交换结构能够从输入端口到输出端口移动分组的速率。
输出端口排队的后果就是，输出端口上的一个分组调度程序（packet scheduler）必须在这些排队的分组中选出一个来传送，如先来先服务（FCFS）调度和加权公平排队（WFQ，在具有排队等待传输的分组的不同端到端连接之间公平地共享输出链路）。分组调度程序在提供服务质量保证（quality-of-service guarantee）方面起着关键作用。
如果没有足够的内存来缓存一个入分组，要么丢弃到达的分组（一种称为弃尾（drop-tail）的策略），要么删除一个或多个排队的分组以便为新来的分组腾出空间。主动队列管理（Active Queue Management，AQM）算法通过在路由器队列中丢弃或标记数据包将拥塞情况隐式或显式地通知源端，源端相应地减小数据发送速率来响应数据包的丢弃或标记，避免更严重的拥塞发生。随机早期检测（Random Early Detection，RED）算法是一种得到最广泛地研究和实现的AQM算法，在RED算法中，为输出队列长度维护着一个加权平均值，如果平均队列长度小于最小阈值则当一个分组到达时该分组被接纳进入队列，相反，如果队列满或平均队列长度大于最大阈值则当一个分组到达时该分组被标记或丢弃，最后，如果一个分组到达发现平均队列长度在最大阈值和最小阈值之间则该分组以某种概率值（一般是与平均队列长度、最小阈值和最大阈值有关的函数值）被标记或丢弃。
输入排队交换机中的线路前部（Head-Of-the-Line，HOL）阻塞，即在一个输入队列中排队的分组必须等待通过交换结构发送（即使输出端口是空闲的），因为它由位于线路前部的另一个分组阻塞。

4.4 网际协议：因特网中的转发和编址

4.4.1 数据报格式

IPv4数据报中的关键字段有：

1. 版本号
   4比特规定了数据报的IP协议版本。
2. 首部长度
   需要4比特来确定IP数据报中的数据部分实际从哪里开始，一般的IP数据报都有20字节的首部。
3. 服务类型（TOS）
   使不同类型的IP数据报能相互区分开来。
4. 数据报长度
   IP数据报的总长度（首部加上数据）。
5. 标识、标志、偏移量
   与IP分片有关。
6. 寿命（Time-To-Live，TTL）
   确保数据报不会永远在网络中循环。
7. 协议
   指明了IP数据报的数据部分应交给哪个运输层协议。
8. 首部检验和
   帮助路由器检测收到的IP数据报中的比特错误。
9. 源和目的IP地址
10. 选项
    允许IP首部被扩展。
11. 数据（有效载荷）

一个链路层帧能承载的最大数据量叫做最大传输单元（Maximum Transmission Unit，MTU）。当IP数据报比MTU小时，将IP数据报中的数据分片成两个或更多个较小的数据报，用单独的链路层帧封装这些较小的IP数据报，然后向输出链路上发送这些帧，这些较小的数据报叫<stron>。</stron>

4.4.2 IPv4编址

主机与物理链路之间的边界叫做接口（interface）。互联几台主机的接口与路由器的一个接口的网络形成一个子网（subnet）。指明一个IP地址的哪些位标识的是主机所在的子网以及哪些位标识的是主机的位掩码叫做子网掩码（subnet mask）。
因特网的地址分配策略被称为无类别域间选路（Classless Interdomain Routing，CIDR），对于子网寻址，32比特的IP地址被划分为两部分，并且也具有点分十进制形式a.b.c.d/x，其中x指示了在地址的第一部分中的比特数。形式为a.b.c.d/x的地址的x最高比特构成了IP地址的网络部分，并且经常被称为该地址的前缀（prefix）或网络前缀。
在采用CIDR之前，限制具有8、16和24比特子网地址的网路分别被称为A、B和C类网络，这种编址方案称为分类编址（classful addressing）。
为了获取一块IP地址用于一个组织的子网，网络管理员也许首先会与其ISP联系，ISP会从已分给它的更大地址中提供一些地址。一个组织一旦获得了一块地址，它就可为该组织内的主机与路由器接口分配独立的IP地址，这项任务目前常使用动态主机配置协议（Dynamic Host Configuration Protocol，DHCP）来完成。利用DHCP，主机可以自动获取IP地址，网络管理员可以配置DHCP，以便某给定主机每次与该网络连接时能得到一个相同的IP地址，或者被分配一个临时的IP地址（temporary IP address），主机每次与该网络连接时该地址都可能是不同的。默认网关即第一跳路由器地址。由于DHCP具有能将主机连接进一个网络的自动化网络相关方面的能力，故它又常被称为即插即用协议（plug-and-play protocol）。
DHCP协议的4个步骤是：

1. DHCP服务器发现：
   新到达的主机的首要任务是发现一个要与其交互的DHCP服务器，可通过DHCP发现报文（DHCP discover message）来完成，客户机在UDP分组中向端口67发送该发现报文（将该IP数据报传递给链路层，链路层然后将该帧广播到所有与该子网连接的子网）。
2. DHCP服务器提供：
   DHCP服务器收到一个DHCP发现报文时，用一个DHCP提供报文（DHCP offer message）对客户机做出响应，每个服务器提供报文中含有收到的发现报文的事务ID、向客户机推荐的IP地址、网络掩码以及IP地址租用期（IP address lease time，即IP地址有效的时间量）。
3. DHCP请求：
   新到达的客户机从一个或多个服务器中选择一个，并用一个DHCP请求报文（DHCP request message）对选中的服务器进行响应，回显配置参数。
4. DHCP ACK：
   服务器用DHCP ACK报文（DHCP ACK message）对DHCP请求报文进行响应，证实所要求的参数。一旦客户机收到DHCP ACK后，交互便完成了，该客户机就能够在租用期内使用DHCP分配给它的IP地址。

当在专用网内部的一些主机本来已经分配到了本地IP地址（即仅在本专用网内使用的专用地址），但现在又想和因特网上的主机通信（并不需要加密）时，可使用网络地址转换（Network Address Translation，NAT）。NAT路由器中有一张NAT转换表（NAT translation table），并且在表项中包含了端口号和IP地址，负责WAN端IP地址与LAN端IP地址间的转换。
NAT不允许外网主机访问内网主机，所以可以在两个对等方之间加一个中间对等方（不在NAT之后且与其中在NAT之后的对等方建立了TCP连接），一旦这对对等方之间创建了一个直接的P2P TCP连接，这两个对等方就能够交换报文或文件，这种雇佣关系称为连接反转（connection reversal），实际上被许多P2P应用程序用于NAT穿越。
NAT穿越越来越多地由通用即插即用（UPnP）提供，UPnP是一种允许主机发现并配置邻近NAT的协议。

4.4.3 ICMP：互联网控制报文协议

用于主机和路由器彼此交互网络层信息。

4.4.4 IPv6

IPv6将IP地址长度从32比特增加到了128比特，还引入了一种称为任播地址（anycast address）的新型地址（可以使一个数据报能交付给一组主机中的任意一个）。IPv6有简单高效的40字节首部。IPv6有一个难以捉摸的流（flow）定义，流标签字段即给特殊流（发送方要求特殊处理的流）的分组加上标签。IPv6首部还有一个8比特的流量类型字段，用于给出一个流中某些数据报的优先级。
IPv6中定义的字段：

1. 版本号
   这4比特用于标识IP版本号，将该字段值设为6。
2. 流量类型
   这8比特能使不同类型的IP数据报能相互区分开来。
3. 流标签
   该20比特用于标识一个数据报的流。
4. 有效载荷长度
   该16比特作为一个无符号整数，给出了IPv6数据报中跟在定长的40字节数据报首部后面的字节数量。
5. 下一个首部
   标识该数据报中的内容需要交付给哪个协议（如TCP或UDP）。
6. 跳限制
   转发数据报的路由器对该字段内容减1，如果跳限制计数到达0，则该数据报将被丢弃。
7. 源和目的地址
8. 数据
   这是IPv6数据报的有效载荷部分。

存在于IPv4数据报格式中却不存在与IPV6数据报格式中的字段：

1. 分片/重新组装
   IPv6不允许在中间路由器上进行分片与重新组装（只能在源与目的地上执行）。
2. 首部检验和
   运输层和链路层协议执行了检验操作，所以不需要在网络层设置这种功能。
3. 选项
   不再是标准IP首部的一部分，但是可能出现在IPv6首部中由下一个首部指出的位置上。

博文补充：（转）IPv4和IPv6的区别有哪些。
从IPv4向IPv6迁移可以引入双栈（dual-stack），即IPv6节点也具有完整的IPv4实现。有一种双栈方法叫做建隧道（tunneling），在IPv6路由器之间用IPv4路由器互联，这些IPv4路由器的集合称为一个隧道（tunnel）。

4.4.5 IP安全性概述

IPsec是流行的安全网络层协议之一，它是面向连接的。
由IPsec会话提供的服务包括：密码技术协约、IP数据报有效载荷的加密、数据完整性、初始鉴别。

4.5 选路算法

一台主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器（default router），又称为该主机的第一跳路由器（first-hop router），每当某主机发送一个分组时，该分组都被传送给它的默认路由器，我们将源主机的默认路由器称为源路由器（source router），把目的主机的默认路由器称为目的路由器（destination router）。
最低费用路径（least-cost path）即最短路径（shortest path）。
全局选路算法（global routing algorithm）用完整的、全局性的网络知识来计算从源到目的之间的最低费用路径。
分布式选路算法（decentralized routing algorithm）以迭代的、分布式的方式计算出最低费用路径。

4.5.1 链路状态（Link-State，LS）选路算法

是一种使用全局信息的算法。在实践中，经常由链路广播状态（link state broadcast）算法来完成。链路费用相当于承载的流量。要确保并非所有路由器都同时运行LS算法。LS算法与Dijkstra算法相关。

4.5.2 距离向量（Distance-Vector，DV）选路算法

是一种迭代的、异步的和分布式（每个节点都要从一个或多个直接相连的邻居接收某些信息，执行计算，然后将计算结果发回给邻居）的算法。DV算法与Bellman–Ford算法相关。

4.5.3 层次选路

可以将路由器组织进自治系统（Autonomous System，AS）。在一个AS内运行的选路算法叫做自治系统内部选路协议（intra-autonomous system routing protocol）。在一个AS内的一台或多台路由器负责向本AS之外的目的地转发分组，这些路由器被称为网关路由器（gateway router）。从相邻AS获取可达性信息以及向该AS中的所有路由器传播可达性信息这两项任务由自治系统间选路协议（inter-autonomous system routing protocol）负责，解决固定维序路由当出现竞争时只能等待的一种实践方法是热土豆选路（hot potato routing），即当一个分组到来时，节点必须尽快脱内手，将其放入输出列最短的方向上排队，而不管该方向通向何方。

4.6 因特网中的选路

AS内部选路协议又称为内部网关协议（interior gateway protocol）。两个选路协议曾被广泛用于因特网上自治系统内的选路：选路信息协议（Routing Information Protocol，RIP）与开放最短路径优先（Open Shortest Path First，OSPF）。

4.6.1 因特网中自治系统内部选路：RIP

RIP通常被设置在较低层ISP和企业网中，运行方式很像DV协议。
RIP使用术语跳，跳是沿着从源路由器到目的子网（包括目的子网）的最短路径所经过的子网数量。
在RIP中，选路更新信息在邻居之间通过使用一种RIP响应报文（RIP response message）交换，大约30秒相互交换一次，由一台路由器或主机发出的响应报文包含了一个由多达25个AS内的目的子网列表，还有发送方到其中每个子网的距离，响应报文又被称作RIP通告（RIP advertisement）。
每台路由器维护一张称为选路表（routing table）的RIP表，包括该路由器的距离向量和该路由器的转发表。

4.6.2 因特网中AS内部选路：OSPF

OSPF通常被设置在较顶层的ISP中，核心就是使用一个洪泛LS协议。
在一个区域内，一台或多台区域边界路由器（area border router）负责为发送到该区域以外的分组选路，准确地说，AS内的一个OSPF区域配置成主干（backbone）区域，主干区域的主要作用是为AS内其他区域之间的流量选路。

4.6.3 自治系统间的选路：BGP（Broder Gateway Protocol，即边界网关协议）

位于某条TCP连接端点的两台路由器被称为BGP对等方（BGP peer），沿着该连接发送所有BGP报文的TCP连接被称为BGP会话（BGP session）。BGP使得每个AS知道经过其相邻AS，哪些目的地是可达的。跨越两个AS的BGP会话被称为外部BGP（eBGP）会话（external BGP session）。
在BGP中，目的地不是主机而是CDIR化的前缀，每个前缀表示一个子网或一个子网的集合。
当一台路由器通过BGP会话通告一个前缀时，随着前缀包括一些BGP属性（BGP attribute），带有属性的前缀被称为一条路由（route），因此BGP对等方彼此通告路由。
当一台网关路由器接收到一个路由器通告时，它使用其输入策略（import policy）来决定是否接收或过滤该路由，是否设置某种属性。
所有进入桩网络（stub network）的流量必定是以该网络为目的地的，所有离开桩网络的流量必定是源于该网络的。经由多个不同的提供商连到其余网络的桩网络叫做多宿桩网络（multi-homed stub network）。

4.7 广播和多播选路

在广播选路（broadcast routing）中，网络层提供了从一个源节点到网络中的所有其他节点交付分组的服务；多播选路（multicast routing）使单个源节点能够向其他网络节点的一个子集发送分组的拷贝。

4.7.1 广播选路酸法

完成广播通信的最直接方式是N次单播（N-way-unicast），但是低效、开销大。
可以使用使用无控制洪泛(flooding)方法，该方法要求源节点向它的所有邻居发送一个分组的拷贝，当某节点接收了一个广播分组时，它复制该分组并向它的所有邻居转发。
还可以用受控洪泛方法，一种是通过序号控制洪泛（sequence-number-contolled flooding）实现，源节点将其地址（或其他的唯一标识符）以及广播序号（broadcast sequence number）放人广播分组，再向它的所有邻居发送该分组，每个节点维护它已经收到的、复制的和转发的源地址和每个广播分组的序号列表，当一个节点接收到一个广播分组时，它首先检查该分组是否在该列表中，如果在，丢弃该分组，如果不在，复制该分组并向该节点的所有邻居转发；另一种方法称为反向路径转发，有时也称为反向路径广播（Reverse Path Fordwarding，RPF，有时也称为反向路径广播即RPB），RPB的基本思想是当一台路由器接收到具有给定源地址的广播分组时，仅当该分组到达的链路正好是位于它自己到其源的最短单播路径上，它才向其所有出链路（除了它接收分组的那个）传输分组，否则，该路由器丢弃入分组。
另一种提供广播的方法是首先对网络节点构造出一棵生成树，当一个源节点要发送一个广播分组时，它向所有属于该生成树的特定链路发送分组，接收广播分组的节点则向生成树中的所有邻居转发该分组（它接收该分组的邻居除外），生成树不仅消除了冗余广播分组，而且能够被任何节点用于开始广播分组。
广播协议在实践中通常被用于应用层和网络层。

4.7.2 多播

在因特网体系结构中，多播数据报使用间接地址（address indirection）来编址。在因特网中，表示一组接收方的单一标识就是一个D类多播地址。与一个D类地址相关联的多个接收方称为一个多播组（multicast group）。
IGMP为一台主机提供了手段，可让它通知与其相连的路由器，在本主机上运行的一个应用程序如何加入一个特定的多播组。在实践中有两种方法用于确定多播选路树：1)使用一棵组共享树进行多播选路，2)使用一棵基于源的树进行多播选路。

4.8 小结

为使路由器的工作更容易，可以使用数据报网络层而不是虚电路网络层，使用一种流水线和固定长度的首部，取消分片，提供唯一的尽力而为服务。
选路算法把计算机网络抽象为一个具有节点和链路的图的方法，一种是全局方法（每个节点得到一张完整的网络图并且独立地应用一种最短路径选路算法），一种是分布式方法（各节点只有整个网络的部分知识且各节点一起协调工作以便沿最短路径交付分组），可以通过将大型网络划分成称为自治系统（AS）的独立管理域来解决规模问题。