5-网络层（下）

链路状态路由选择

（Link State Routing）简称LS

距离矢量路由法由于不能从全局把握问题，只能从邻居节点获取信息导致了无穷计数，路由环等问题

这些问题可以通过链路状态路由选择加以解决

LS主要思想

1. 发现：发现邻居节点，了解它们的网络地址
2. 设置：设置规定到每个邻居的成本度量
3. 构造：构造分组，包含所了解到的所有信息
4. 发送：将这个分组发送给其他路由器
5. 计算：计算到每个路由器的最短路径

发现

发现邻居节点

当一个路由器启动时，会向每条点对点线路发送一个特别的HELLO分组，收到HELLO分组的路由器会回送一个应答，应答中包含自己的名字（采用全球唯一的一个名字Globally Unique Name）

设置

设置链路成本（开销/量度/代价）

可以自动发现设置或是采用人工设置，常见的量度是设置为与链路带宽成反比

延迟也可以作为量度

• 路由器会发送一个特别的ECHO分组，另一端立刻回送一个应答
• 通过测量往返时间RTT，可以获得一个合理的延迟估计值
• 可以通过多次测量，取平均值，保证结果有效性

构造

构造链路状态分组：Link State Packet/Adevertisement(LSP/LSA)，分组内包含的信息有：

• 发送方标识(ID of the sender)
• 序列号(sequence number)，一个路由可能发送多个分组，序列号就是用于却别同一路由的不同分组的
• 年龄(age)
• 邻居列表(list to neighbors)，储存了能够到达的所有邻居
• 到邻居的成本/量度(delay to each neighbor)

构造链路状态分组的时机

周期性的构造分组，或者在有特殊事件发生时构造，例如某条线路或邻居DOWN掉了，这就是我们所说的触发更新

发布/分发

发布链路状态分组，这一步操作关系着LSA/LSP能否分发到所有的路由器，如果这一步出现差错导致LSP不能分发给所有路由，会导致路由器构造的拓扑图不完整，即对网络认识不完整

基本算法：

每个分组都包含一个序列号，序列号随新分组发送而递增，路由器会记录下它所看见的所有（源路由器，序列号）有序对

当一个新分组到达路由器时，路由器会结合源路由器与序列号进行判断：

1. 如果序列号大于当前已经存在的最大序列号，则该分组被当作新分组向其他所有路由器转发（泛洪广播）
2. 如果序列号与当前已经存在的最大序列号相等，则路由器抛弃当前分组选择新到达的分组（喜新厌旧）
3. 如果序列号小于已经存在的最大分组，则被认定为过时分组而被丢弃

基本算法遇到的问题

• 序列号回转：加入序列号多短，例如3bit，则可用的序列号只有8种000-111，所以分组假如收到000和111，无法判断二者的大小（可能是本轮的过时分组也可能是下一轮的最新分组）
• 路由器崩溃：假如一台正在运行的路由器突然崩溃，那么它的序列号会重新从0开始，这就导致接收方路由器会将新产生的分组当作过时分组进而丢弃
• 序列号损坏，假如发送方传输序列号过程中发生一位错误例如由4变为65540，则后续的5-65540分组都会被认定为旧分组而丢弃

解决方法

序列号回转问题的解决方法就是采用32位序列号，这样在有限的时间内，机器不可能发生序列号回转的情况，而是一直处于递增状态

解决路由器崩溃和序列号损坏问题就利用到了分组中的年龄，当分组到达路由器后，年龄随时间逐秒递减1，直至年龄归0时，如果仍没有符合顺序新分组到达，则该分组被丢弃。而一般情况下每十秒会有一个新分组到达，假如超出时限，很可能是DOWN机或超过六个分组丢失，所以，成功解决了路由器崩溃的情况。而如果新到达的分组序列号与之前留存的分组序列号不是相邻的，则年龄倒计时不会停止，直到归0，所以也成功解决了序列号损坏的问题

算法改进

• 当一个链路状态分组到达某个路由器时，它首先被放到一个保留区中等待一段时间
• 如果来自相同路由器的另一个分组到达了，这两个分组的序列号会被比较：
  • 如果相等，是重复分组，丢弃
  • 如果不相等，旧的那个被丢弃

计算

当一个路由获得了全部链路状态分组就可以构造出全网络的拓扑图来了，这种拓扑图一般采用最短路径算法（例如：狄克斯特拉算法）来计算。计算的最终结果是一棵树，会存储在路由表种，用来引导分组的转发

L-S路由算法特点：

单区域OSPF

开放的最短路径优先协议(Open Shortest Path First)

链路状态路由典型实例，在TCP/IP协议种，OSPF位于IP协议之上，OSPF是一种基于开放标准的链路状态路由协议，是目前IGP中应用最广，性能最优的协议

OSPF特点

• OSPF可以在大型网络中使用
• OSPF克服了路由自环
• 支持VLSM，CIDR等技术，具有现代路由选择协议的特征
• 使用带宽作为度量值（10^8/BW）
• 收敛速度快
• 通过分区实现高效的网络管理

OSPF基本概念

Internet由很多不同组织运营的独立网络或自制网络系统构成，早期的资质系统内部（也称域内），运行着RIP协议，目前大多是OSPF协议

对于有些庞大的资质系统AS，会将系统划分为多个区域Area，每个区域内单独运行OSPF，且每个系统中必然存在一个0号区域，作为骨干区域，所有区域都必须连接到骨干区域上，在一个区域中运行OSPF称作单区域OSPF ，一个AS如果不划分区域运行OSPF，则只有一个0号区域。

单区域OSPF运行时部分术语

• RouterID：一个３２位无符号整数，是路由器的唯一标识，在自制系统内唯一
• 协议号：89号，OSPF报文直接封装在IP分组中，通过IP分组的头部的protocol协议号就可以判别是否为OSPF分组
• TTL：TTL一般为1，说明，OSPF一般只传递一跳，也就是只传给相邻的邻居节点

OSPF使用带宽($10^8$/BW)作为代价判断标准

例如，10M的以太链路，对应的代价=10^8/10*10^6=10.

为了适应带宽增长，有些厂商的代价计算公式是可以配置的

OSPF分组类型

OSPF运行步骤

1. 建立路由器毗邻关系
2. 选举DR和BDR
3. 发现路由
4. 选择最佳路由
5. 维护路由信息

建立路由器毗邻关系（全毗邻关系）

OSPF运行中最重要的一步

达到全毗邻状态的两个路由器，它们内部LSP数据库内容完全一致，当两个路由器交换DD报文后发现数据库内容本来就完全一致时，就会跳过交换完整数据库内容的过程，直接成为全毗邻状态，建立全毗邻关系的过程叫做同步

同步可能是个冗长的过程，在同步期间，网络社会是不安定的。

如图中的网络拓扑结构所示，如果两两节点之间逐个进行同步，则n个路由器需要进行n*(n-1)/2次的同步，但如果，选出一个特殊路由器作为指定路由器DR（Designated Router），所有路由器只与它进行同步，则同样能获取到全网的拓扑信息并且同步次数缩减至n-1次

指定路由器DR通过选举得出，选举过程如下：

• 登记选民：统计本网段内的OSPF路由器
• 定候选人：统计本网段内priority>0的OSPF路由器
• 竞选演说：所有候选人都假定自己是DR
• 投票选举：首先选举priority值最大的，如果相等，则选择RouterID最大的

无类域间路由 CIDR

IP协议面临的两大问题

1. 分类造成了数百万个地址浪费

C类地址含有256-2=254个可用地址，B类含有约65000个可用地址，假如我目前需要的地址数在500左右，而C类无法满足需求，B类空闲地址过多，就会导致我不得不使用较大的B类，这也就造成了地址的浪费

2. 路由表膨胀

随着互联网的发展，路由表动辄上万条，这导致信息传递的速度变慢，增加了通信过程中端到端的延迟。

为解决上述问题，就提出了CIDR技术

CIDR

Classless Inter Domain Routing，即无类域间路由，CIDR缓解了地址枯竭的趋势，尤以其中的B类地址枯竭趋势见著。控制甚至缩减了路由表的开销

CIDR基本思想

分配地址的方法：按需分配，不再采用A类B类来分配 （例如：在CIDR出现之前假设一个用户需要2000个IP地址只能申请B类地址，但这会造成60000多个地址的浪费，CIDR出现后，就可以按需分配，2000个地址，最接近2048，所以需要11个主机位，所以网络位个数就是21，因此，可以分配一个块地址x.x.x.x/21给用户，就可以满足需求，并且除了两个不可以地址还有46个地址可扩展）

有了CIDR之后，路由表必须增加一组数据，就是地址的32位子网掩码用于寻径，即每个路由表都至少需要记录一个三元组（目的IP地址，子网掩码，输出线路）

过程

当一个分组到达路由器，路由器会提取其中的目的IP地址和子网掩码，进行按位与后确定目标网络，然后查找路由表，假如路由表中有多条线路与之匹配，则选择网络位最长的（IP地址的最长匹配前缀），例如地址为196.168.24.1遇到表中有能够匹配的两个地址（196.168.10.0/19，196.168.10.0/22）则会选择其中网络位更长的地址，因为网络位越长，说明网络越小，越接近我们寻找的目标网络

缩减路由表规模-聚合

如图，中间路由不需要记录12条路由的全部信息，只需要记录三条汇总的路由就可以。而最右边路由则只需要记录中间路由即可

这些都依靠路由的聚合完成，路由聚合必须保证子网地址是连续的，关键是确定新的聚合空间中网络位个数(网络位就是聚合的几个网络中不变的位)

聚合结果：超网

聚合的前提条件：

- 子网构成的地址空间是连续的
- 下一跳一定是相同的

CIDR还带来了额外的好处：隔离了路由翻动

网络地址翻译NAT

提出NAT的原因

• IPv4地址池已经枯竭
• 每个上网的设备都需要上网资源，包括IPv4地址

为了解决上述问题，就需要使用到私人地址，私人地址是不可路由的地址，可以用于广域网链路上。私人地址不具备唯一性，在IPv4的三类地址中都保留了一部分地址作为私人地址

由于私人地址不具备唯一性，无法连接至互联网，就需要用到上文所提的网络地址翻译NAT（net address translate），NAT负责私人IP地址与公有IP地址之间的转换（一种类似的技术：PAT，port address translate（超载）可以将多个私有IP地址影射到同一个公有IP地址的不同端口）

NAT

NAT是一个IP地址耗尽的快速修补方案（RFC3022中描述），内部网络使用私人地址，当内部网络需要和外网进行通信时，私人地址转换为合法的公网IP。NAT转换器负责完成这种转换过程。

NAT转换器

功能：

• 由NAT转换器完成私人地址与公网IP地址之间的转换，并且维护一个地址转换表
• 当有外网的分组到达时，NAT转换器查找地址转换表，转换分组目标地址后，转发该分组到内网

位置：

NAT转换器可以是一个专用的服务器，也可以运行在内网的边界路由器上，也可以在家用路由器(AP)上

工作原理：

NAT工作原理如下图所示，首先内外内的主机将信息封装，此时封装的分组内第一层是源地址（内网地址），第二次是目的地址（公网地址）第三层两个参数分别是源和目的的端口号，当分组到达NAT转换器时，NAT转换器将分组进行解封装，提取其中的源地址和端口，将其替换为公网地址和端口，并将这组变化信息记录在地址转换器上，然后将其发往目的地址，目的地址收到分组后，假如需要重新返回一个分组（做出应答），只需要调换源和目的的位置就可以返回该分组，分组再次到达NAT转换器时，转换器同样首先解封装，然后检索地址转换表，查找目的端口对应的内网地址，并替换掉公网地址和端口，随后将分组转发到对应的内网地址

问题：

• 违背了IP地址的唯一性
• 破坏了IP网络的无连接特性，使其成为了一个面向连接的网络，NAT转换器维护着整个连接状态，一旦NAT转换器崩溃，这种连接方式也会失效
• 违背了最基本的协议分层原则，在转换器中修改了分组内的端口号，端口号是由上层传输层管理的内容，跨层工作
• 如果传输层不是采用TCP／UDP而是采用其他协议，那么NAT转换器也会失效
• 有些应用需要在分组载荷中插入IP地址，接收方会提取载荷中的IP地址，而NAT转换器只操作头部数据，不会修改分组载荷内的内容，因此将导致该类应用无法正常运行
• NAT让一个公网IP地址可以承载61400个（65536-4096）私人地址，导致了严重的超载

优点：

• 节省了公有IP地址
• 提供了私网访问外网的多样性
• 具有一定的的保密性和安全性

互联网控制信息协议ICMP

IP提供的是尽力传送的服务，分组可能会遭遇拥塞，丢弃，找不到目的机等等问题。因此，我们经常需要知道一条到目的机的路是否通达，延时大小等等。因此我们设计了IP协议的姊妹协议ICMP协议

ICMP互联网控制信息协议

(Internet Control Message Protocol)

• 可以向源报告目标超时，不可达等问题
• 用来测试网络，如ping,tracert

ICMP整个作为载荷封装到IP分组的数据域中

ICMP类型

ICMP应用

PING

使用ping命令（即调用ping过程）时，将向目的站点发送一个ICMP回声请求报文（包括一些任选的数据），如目的站点接收到该报文，必须向源站点发回一个ICMP回声应答报文，源站点收到应答报文（且其中的任选数据与所发送的相同），则认为目的站点是可达的，否则为不可达。

PING的作用

• 测试TCP/IP是否正常工作：ping 127.0.0.1
• 测试网络设备是否正常工作：ping 本机IP地址
• 检查对外连接的路由器：ping 默认网关
• 检查与某台设备的畅通情况：ping 设备IP
• 检查DNS设置：ping www.baidu.com
• 执行DNS的反向查询，利用IP地址反向查询到域名：ping -a IP地址

tracert

当ping不通某个接口时，假如我们想知道是哪个地方失败，就需要用到tracert工具

tracert会逐个发送ICMP分组，TTL从1开始递增，首先发送TTL=1的分组，分组到达第一跳，TTL减为0，分组被丢弃，，此时目的路由器就会返回一个应答分组，源路由器可以通过应答分组获知ICMP分组成功到达第一跳，依次会发生TTL=2，3…的分组，知道收到一条错误应答，说明该路径在这个环节不可达。也就找到了错误的源头。tracert最大支持30跳。

PMTU

利用(Type = 3 , code = 4)的ICMP消息

路径MTU(Path Maximum Transimition Unit),动态发现互联网上任意一条路径最大传输单元的技术，每个网络都有各自的MTU也就是最大承载能力，常见的以太网的MTU是1500byte，传输的数据一旦超过这个大小就需要进行分片操作，但是分片操作消耗大，安全隐患多，消除这种问题的方法就是在一开始就探明这条路径的最大传输单元

PMTU算法/PMTU技术

一般来说，ICMP消息仅发送给源机，由于ICMP是封装在IP分组中发送的，所以有一条规定：ICMP消息不生成自己的错误报告。这样的理由是假如某处发生拥塞，若ICMP生成自己的差错报告，则新生成的ICMP也会在此处拥塞，故而新的ICMP再次生成差错报告，如此往复，拥塞越来越严重

地址解析协议ARP

(Address Resolution Protocol)

ARP是一个运行在局域网中的协议，它将，目标机的IP地址映射到MAC地址上。

工作原理

当主机A只有主机E的IP地址而没有MAC地址时，主机A就会发出广播给局域网内所有主机，寻找主机E，其他主机在收到广播后不作应答，主机E在收到广播后返回自己的MAC地址

如果每一次发送数据都要来回发送ARP请求帧和返回帧，是非常耗费资源的，所以，有诸多的优化措施：

• 每个主机建立一个ARP表，缓存ARP的结果
• 用ARP请求中的源信息来更新ARP表（在ARP请求帧中包含源机的IP和MAC地址对，所以每一个收到请求帧的主机，即使不做应答，也会根据请求帧的结果更新ARP表）
• 每个机器在启动时都会广播它的IP/MAC地址对，当前在局域网内的全部主机在收到后将它们储存在ARP缓存表中，这就是所谓的免费ARP，此时请求机不奢求能够收到应答，因为他发出的目的IP地址就是它自己，但假如收到应答，说明该局域网中自己的IP地址被其他人使用了，发生了IP地址冲突（免费ARP最显著特征，source IP=target IP，源ID＝目标ID）

ARP请求帧是二层广播帧，目标机只有跟源机在同一个LAN中才能收到请求帧，假如目标机是一个远程机（不在同一个局域网内部），则ARP无法找到目标MAC地址。此时源机会先寻找整个网络中的默认网关，然后由默认网关找到目标机的MAC地址并最终返回源机

为了减少ARP请求次数，每个设备包括路由器都有各自的ARP表，ARP表是IP地址到MAC地址的映射表，存储在存储器内存中，自动维护，一旦掉电故障，表内信息全部消失。表中内容是自动更新和维护的

维护ARP表(arp -a 查看)

• 通过广播ARP请求中的源设备信息添加更新表
• 利用自己的ARP请求之应答信息来添加、更新表
• 删除超过一定时限的信息

拥塞控制

一个网络能够承载的数据流量是有限制的，在待传输分组不多，轻载的时候，发出的分组都能够顺利发送

拥塞

当一个子网，或子网的一部分出现太多分组时，网络性能急剧下降，导致拥塞（拥塞出现时，分组被丢弃，重传，网络吞吐量严重下降，甚至无法传输分组）

控制拥塞的方式：

开环：

开环控制试图用良好的设计从根源解决问题，本质就是保证问题从一开始就没有发生的可能性。开环决策不考虑网络当前状态，而是提前考虑

问题在于事物发展过快，任何一个曾经良好的开环设计随着时间推移都会被加速淘汰，开环设计很难准确的估计需求，即使超前的设计随着时间推移，也会越来越吃力

闭环：

基于上文所述的问题，更多采取闭环设计。

闭环控制建立在反馈环路的概念上，分三个步骤解决问题

• 监视系统：检测何时何地发生拥塞
• 传递拥塞信号：将拥塞信息传递到能够采取行动的地方
• 调整系统运行，控制拥塞发生

检测拥塞：

确定拥塞的量度，数值越大表示拥塞的程度越重：

• 因为缺乏缓存空间而丢弃的分组百分比
• 平均队列长度
• 超时和重传的分组数
• 平均分组延迟
• 分组延迟的标准方差

传递拥塞

传递拥塞有多种方式。

最常见的就是向源机返回一个拥塞警告分组，但由于当前路径拥塞，这个警告分组有可能根本无法到达源。

还可以设置每个分组保留一位或一个字段作为警告位，当拥塞度量超过阈值时，路由器就对这个位或者这个域填充位以此警告它的邻居。

还有一种方法，主机或路由器周期性向外发送探询，即probe分组，显式的询问有关拥塞的情况，然后在有拥塞的地方利用回收的信息路由流量

解决拥塞

拥塞产生的根本原因无非是发送了过多的分组，超过了资源承载的能力。（拥塞根源：负载>资源），因此要解决拥塞就是要扭转这个不等式，所以可以从两方面入手

增加资源

可以在某些点间增加更多的通道，提升带宽，增加资源承载能力以解决问题。

降低负载

• 拒绝服务：拒绝为某些用户提供服务
• 服务降质：为某些用户的服务降低等级
• 绕开拥塞点：让用户更有预见性的安排需求

以上几种方法的反应顺序与速度

数据报子网中的流量限制方法

• 每台路由器可以监视它的输出线路和其它资源的使用情况
• 每条线路和一个实变量 u 关联在一起，其值位于(0.0 -1.0)之间
• 无论何时，只要 u 超出了阈值，对应的线路就进入到警告 “warning”状态
• 每个新到达的分组都将被检查，看它的输出线路是否处于 “警告状态”

处于警告状态后，可以采取抑制分组措施来解决问题。

抑制分组原理：

当发生拥塞后，路由器向源机发送ICMP抑制分组，源机在收到抑制分组后，削减发送到目的机的流量，并在一段时间内丢弃目的机发送的抑制分组，以避免过度削减流量。一段时间后，源机继续检测是否仍有抑制分组，如果不再收到抑制分组，就逐渐增加流量大小

逐跳抑制分组：

当网络拥塞或是距离过远时，直接发送抑制分组的效果并不好，这时可以采用逐跳抑制分组的方式，对目的机上游的路由器逐个进行抑制，这样可以快速解决拥塞问题，但这大大增加了上游路由器所需要的缓存空间

负载脱落/载荷脱落

处理拥塞最极端，最有效的方法。面对超载时，就会选择丢弃一部分分组，丢弃部分分组的决定方式有:

分组丢弃策略：

• 随即丢弃
• 丢弃新到达的分组(葡萄酒策略，适合文件传输)
• 丢弃早到达的分组(牛奶策略，适合多媒体类)
• 丢弃不太重要的分组(需要在分组中指明优先级)

随机早期检测（RED）

(Random Early Detection)

在情况恶化，无可救药之前，采取一定措施的检测方式，就是在拥塞早期对分组进行处理。根据路由器维护的最早的队列，平均长度来决定何时开始丢弃分组（拥塞处理开始）

流量整形

用户产生的数据总是忽大忽小的，具有突发特性。而流量整形就是调节数据平均传输速率（和突发数据流），以减少突发带来的拥塞，缓存溢出以及丢包等等问题。

流量整形算法主要有漏桶，令牌桶两种

漏桶

• 每个主机连接到网络的接口中都有一个漏桶，即一个优先长度的内部队列
• 当桶中有分组的时候，输出速率是恒定的，当桶空的时候，输出速率是0
• 当一个分组到达满的桶的时候，分组将被丢弃（满则溢）
• 每个时钟嘀嗒(tick)，仅允许一个分组或固定数量的分组发送出去

算法效果

主机内用户进程产生的分组流往往是一个不稳定的流，漏桶可以让它输出到网络时变成一个稳定流，抹平了突发尖峰，极大地减少了发生拥塞的机会。

缺点

漏桶满了之后数据将被丢弃，不能大量的突发数据

令牌桶

令牌桶是改进的漏桶算法

• 当大量数据突发的时候，令牌桶算法允许输出加快到某种程度
• 令牌桶拥有令牌（tokens），且以每△T秒产生一个令牌的速度往桶中输入令牌
• 一个分组要发送的时候，它必要从桶中取出和获取到一个令牌
• 令牌桶算法允许累积令牌，但最多可以累积n（令牌桶的容量）个令牌

和漏桶算法相比：

• 令牌桶允许突发，但是最大突发受制于令牌桶容量的限制
• 当桶满的时候，令牌桶算法丢掉的是令牌（不是分组）

计算最大突发时间

• 突发时间： S 秒
• 令牌桶容量： B字节
• 令牌到达的速率： R 字节/秒
• 最大输出速率： M 字节/秒

B+RS=MS

S=\frac{B}{M-R}