计算机网络学习笔记-网络层

前言

正在学习计算机网络这门课程，顺便做个笔记，记录一下知识点。

参考资料： 中科大郑烇老师全套《计算机网络（自顶向下方法 第7版，James F.Kurose，Keith W.Ross）》课程：https://www.bilibili.com/video/BV1JV411t7ow?p=1 《计算机网络（自顶向下方法 第7版，James F.Kurose，Keith W.Ross）》

第四章：网络层

导论

网络层所提供的服务：

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

网络层的关键功能：转发和路由

• 转发：将分组从路由器的输入接口转发到合适的输出接口 这是一个局部的功能 是数据平面的功能 路由器从不同的端口接收分组，再通过合适的端口将其分发出去。
• 路由：使用路由算法来决定分组从发送主机到目标接收主机的路径 这是一个全局的功能 是控制平面的功能
  • 路由选择算法
  • 路由选择协议

举个例子说明转发与路由： 计算机网络一口气学了好长时间，打算去郊区的公园散散心：

• 转发就好像是在行程中通过每个路口时的决策，从哪里进入路口，又从哪里出去
• 路由就像是在出发前用手机导航规划全局路径的过程

数据平面与控制平面

• 数据平面： 局部的处理，每个路由的功能：
  • 决定从路由器输入端口到达的分组如何转发到输出端口
  • 转发功能：
    • 传统方式：基于目标地址 转发表
    • SDN方式：基于多个字段 流表
• 控制平面： 全局的处理，网络范围内的逻辑：
  • 决定数据报如何在路由器之间路由，决定数据报从源到目标主机之间的端到端路径
  • 两个个控制平面方法：
    • 传统的路由算法: 在路由器中被实现（路由表）
    • SDN（software-defined networking，软件定义网络）：在远程的服务器中实现

传统方式：每一个路由器既实现了数据平面的功能，也实现了控制平面的功能。

• 在每一个路由器中的单独路由器算法元件，在控制平面进行交互
  • 控制平面：路由算法决定端到端路径（分布式操作）
  • 数据平面：IP协议根据转发表决定了IP数据报在此路由器上的局部转发（分布式操作）
  • 二者是紧耦合的，在一个路由实体中

  在路由器之上有路由实体，这些路由实体之间要交换路由信息。然后分布式的计算路由表，交给IP协议实体，然后IP协议实体根据路由表进行匹配，最后转发。

  • 带来的问题：分布式的操作使得修改路由器的运行逻辑是一件困难的事情

SDN方式：逻辑集中的控制平面

• 一个不同的（通常是远程的）控制器与本地控制代理（CAs）交互
  • 控制平面的功能集中在一个服务器（远程控制器，Remote Controller）上去实现，计算得到流表，将其交给每一个分组交换设备，分组交换设备对流表进行装载，对接收到的IP实体做多字段的匹配（传统方式只匹配目标主机的IP地址），按照流表对应的动作对IP实体进行操作，包括：转发，阻塞（block），泛洪等
  • 分组交换设备仅按照远端的服务器计算发来的流表进行操作，这样改变其行为逻辑就会简单许多。
  • 由此分析：控制平面是集中式的、远程的，便于修改。

网络服务模型

从发送方主机到接收方主机传输数据报的“通道”，网络提供的服务模型：

• 对于单个数据报的服务：
  • 可靠传送
  • 延迟保证，如：少于40ms的延迟
• 对于数据报流的服务：
  • 保序数据报传送
  • 保证流的最小带宽
  • 分组之间的延迟差
• 连接建立：在某些网络架构中是第三个重要的功能
  • 在分组传输之前，在两个主机之间，在通过一些路由器所构成的路径上建立一个网络层连接（涉及到路由器）
  • 网络层和传输层连接服务区别：
    • 网络层: 在两个主机之间，涉及到路径上的一些路由器
    • 传输层: 在两个进程之间，很可能只体现在端系统上(TCP连接)

虚电路和数据报网络

网络层能够在两台主机之间提供无连接的服务或有连接的服务

• 数据报网络（datagram network）仅在网络层提供无连接服务
• 虚电路网络（Virtual-Circuit，VC）仅在网络层提供连接服务

由上一章我们知道运输层也可以实现面向连接的服务，但是这与网络层实现连接服务是不同的：

• 网络层提供的是主机到主机（host-to-host）间的服务 运输层提供进程到进程间的服务
• 网络层连接服务除了在端系统中，也在位于网络核心的路由器中出现 运输层的连接服务只在端系统中实现

虚电路网络

虚电路网络从源头到目的地的路径表现得很像电话线路。

一条虚电路的组成如下：

• 源和目的主机之间的路径（即一系列链路和路由器）
• VC号，沿着该路径的每段链路的一个号码
• 沿着该路径的每台路由器中的转发表表项 属于一条虚电路的分组将在它的首部携带一个VC号。因为一条虚电路在每条链路上可能具有不同的VC号，每台中间路由器必须用一个新的VC号替代每个传输分组的VC号，该新的VC号从转发表获得。

下图展示了一个简单的虚电路网络和对应路由器的转发表

虚电路中路由器维持着连接状态信息

（埋个坑，以后补充）

路由器的组成

路由：运行路由选择算法／协议 (RIP, OSPF, BGP)-生成路由表

路由器的组成包括：

• 输入端口
• 输出端口
• 交换机（high-seed switching fabric）将输入端口与输出端口连接起来，构成局部的转发（根据路由表）。

输入端口

• 物理层：把物理信号转化为数字信号（Bit级接收）
• 数据链路层：链路层协议动作、解封装得到IP协议实体 判断帧头、帧尾，利用CRC检查出错（具体见下一章）
• 网络层：通过路由表将分组进行转发 分布式交换：
  • 根据数据报头部的信息如：目的地址，在输入端口内存中的转发表中查找合适的输出端口（匹配 行动）
  • 基于目标的转发：仅仅依赖于IP数据报的目标IP地址（传统方法）
  • 通用转发：基于头部字段的任意集合进行转发
• 输入端口缓存：

在输入端口会有一个队列，用于缓解输出、输入的不一致性。

• 当交换机构的速率小于输入端口的汇聚速率时， 在输入端口可能要排队 排队延迟以及由于输入缓存溢出可能造成丢失
• 排在队头的数据报阻止了队列中其他数据报向前移动

交换结构

交换速率：分组可以按照该速率从输入传输到输出

• 运行速度经常是输入/输出链路速率的若干倍
• 如果是N 个输入端口：交换机构的交换速度是输入线路速度的N倍比较理想，才不会成为瓶颈

下面我们来分析分组如何从输入端口转向输出端口：

三种典型的交换机构

• 基于memory（内存）
  • 第一代路由器
  • 路由器就是一个计算机，通过软件的方式实现路由
  • 输入端口和输出端口分别插入网卡，从输入端口接收来的分组，通过系统总线，交给路由软件，匹配路由表，最后决定从哪一个网口发出。
  • 转发速率被内存的带宽限制 (数据报通过BUS两遍)
  • 一次只能转发一个分组
• 基于bus（总线）
  • 数据报通过共享总线，从输入端口转发到输出端口
  • 总线竞争: 交换速度受限于总线带宽
  • 一次处理一个分组
  • 总线速度能达到：Cisco 1900：1 Gbps；Cisco 5600：32 Gbps。对于接 入或企业级路由器，速度足够（ 但不适合区域或骨干网络）
• 基于crossbar（互联网络）
  • 同时并发转发多个分组，克服总线带宽限制
  • 当分组从端口A到达，转给端口Y；控制器短接相应的两个总线
  • 高级设计：将数据报分片为固定长度的信元，通过交换网络交换（分组长度是不同的）
  • Cisco12000：以60Gbps的交换速率通过互联网络

输出端口

• 网络层：接收fabric传来的分组，将分组排队，将分组交给对应链路层的网卡
  • 当数据报从交换机构的到达速度比传输速率快 就需要输出端口缓存
  • 同样，如果队列溢出，分组丢失
  • 由调度规则选择排队的数据报进行传输（并不一定是先来先服务）
• 链路层：封装成帧（添加帧头、帧尾、目标MAC地址）
• 物理层：将数字信号转化为物理信号，将数据传出去
• 输出端口排队：

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

调度机制

调度: 选择下一个要通过链路传输的分组

• FIFO (first in first out) scheduling: 按照分组到来的次序发送
  • 丢弃策略：
    • tail drop: 丢弃刚到达的分组
    • priority: 根据优先权丢失/移除分组
    • random: 随机地丢弃/移除
• 优先权调度：发送最高优先权的分组
  • 多类，不同类别有不同的优先权
    • 类别可能依赖于标记或者其他的头部字段（如：IP source/dest, port numbers, ds，等）
    • 先传高优先级的队列中的分组，除非没有
    • 高（低）优先权中的分组传输次序：FIFO
• 轮转 （Round Robin (RR) ）调度：
  • 多类
  • 循环扫描不同类型的队列, 发送完一类的一个分组，再发送下一个类的一个分组，循环所有类
• Weighted Fair Queuing (WFQ，加权公平队列)：
  • 一般化的Round Robin
  • 在一段时间内，每个队列得到的服务时间是：Wi / (XIGMA(Wi )) ×t，和权重成正比
  • 每个类在每一个循环中获得不同权重的服务量

IP协议（Internet Protocol）

IP协议在整个协议栈的位置：

IP数据报格式

• 固定20字节头部（一行4字节，固定一共5行）
• 除固定20字节头部外有可选项部分
• body部分（数据载荷部分）
  • TCP的段
  • UDP的数据报

说明：

• ver（IP 协议版本号，4bit）：4 → IPv4； 6 → IPv6
• head.len（头部长度，4bit）：以字节为单位
• type of service（数据类型，8bit）：标识数据报载荷的类型，为了使分组调度时有依据（由于IP网络运营模式，现在基本不用）
• length（数据报总长，16bit）：标识此IP数据报的总长，以字节为单位
• 分片/重组使用（如果IP数据报超过链路层的最大传输单元MTU，就会分片）
  • 16-bit identifier（16bit）：判断分片是否是同一个IP数据报
  • flags（4bit）：1 → 后面还有分片；0 → 后面无分片（此分片是最后一个）
  • fragment offset（12bit）：偏移量
• time to live（TTL，8bit）：最大剩余段数（每经过一个路由器减一）
• upper layer（上层协议，8bit）：决定将载荷部分交给上层哪种类型的协议实体（例：TCP、UDP等）
• Internet checksum（头部校验和，16bit）：数据部分不进行校验，只判断头部是否异常 IPv6取消了该字段
• 32 bit source IP address（32位源IP地址）
• 32 bit destination IP address（32位目标IP地址）
• data：数据报的载荷部分
• Options（可选部分）：例如，每经过一个交换节点，该地址会被记录在option中，即形成一个经过的路由器的列表，这样一来，目标端就知道该分组的传输路径。

IP 分片和重组

IP 分片的原因：

网络链路有MTU (最大传输单元)：链路层帧所携带的最大数据长度。如果IP数据报长度大于MTU，那么就需要将其分片。

不同的链路类型有不同的MTU

思考，如果仅仅是将一个IP数据报“粗暴”地直接分片，那么第一片包含头部信息，路由器知道如何处理，那么其他片没有头部信息，路由器便无法识别，显然这样是不行的。那么分片就需要一些“手段”：

假设要传输一个4000字节的数据报：20字节头部 3980字节数据

链路层最大传输单元（MTU）为：1500字节

• 第一片：20Bytes头部 1480Bytes数据
  • flags = 1
  • fragment offset = 0
• 第二片：20Bytes头部 1480Bytes数据
  • flags = 1
  • fragment offset = 1480 / 8 = 185
• 第三片：20Bytes头部 1020Bytes数据
  • flags = 0
  • fragment offset = 2960 / 8 = 370

  注意：在计算偏移量的时候需要除以8（以8字节为单位）

每一片都到最后的目标主机才进行重组，中间转发节点不重组。

如果到达目标主机的分片有丢失，那么分片全部丢弃。

IPv4

IP编址

IP地址：32位标示，对主机或者路由器的接口编址

• 一个IP地址和一个接口相关联

接口: 主机/路由器和物理链路的连接处

• 路由器通常拥有多个接口
• 主机也有可能有多个接口
• IP地址和每一个接口关联

子网（Subnets)）

如下图，是一个包含三个子网的网络

必备的两个条件：

• IP地址
  • 子网部分（高位bits），也称子网号：每个IP是相同的
  • 主机部分（低位bits）
• 在子网内部分组的收发不需要借助路由器（仅通过交换机），一跳可达。

子网的判断：

• 要判断一个子网, 将每一个接口从主机或者路由器上分开,构成了一个个网络的孤岛
• 每一个孤岛（网络）都是一个都可以被称之为subnet
• 如下图，共有6个子网：

IP地址分类

A类地址：地址最高位为0，第一个字节的其它7位为网络号，后面三个字节（24bit）为主机号

• 一共有126个网络（27 - 2，全零和全一的网络号不使用）
• 每个网络有224 - 2个主机

B类地址：地址最高两位为10，前两个字节的其他14位为网络号，后面两个字节（16bit）为主机号

• 一共有214 - 2个网络
• 每个网络有216 - 2个主机

C类地址：地址最高三位为110，前三个字节的其他21位为网络号，后面一个字节（8bit）为主机号

• 一共有221 - 2个网络
• 每个网络有28 - 2个主机

A、B、C类地址称为：“单播地址” 通常获取的都是C类地址

D类地址（“组播地址”）：最高4位为1110，其余位为组播地址（Multicast address）

E类地址（预留）：最高5位为11110

• 互联网是以网络（局域网）为单位进行路由信息的通告，传播和计算。
  • 每个网络是路由表中的一个表项，而非IP地址
• 子网信息可以进一步聚集，更高层次可以以广域网为单位。

特殊的IP地址：

• 约定：
  • 子网部分: 全为0 → 本网络
  • 主机部分: 全为0 → 本主机
  • 主机部分: 全为1 → 广播地址，这个网路所有的主机
  • 127.X.X.X：回路地址（测试地址）：即TCP/UDP数据报传到IP层面后返回 类似我们在一个web项目的时候，本地测试模拟网络状态，通常地址为127.0.0.1（实际上访问的是本机）

内网(专用)IP地址：

• 专用地址：地址空间的一部份供专用地址使用
• 永远不会被当做公用地址来分配, 不会与公用地址重复
  • 只在局部网络中有意义，区分不同的设备
• 路由器不对目标地址是专用地址的分组进行转发
• 专用地址范围：
  • Class A： 10.0.0.0 ~ 10.255.255.255 MASK 255.0.0.0
  • Class B： 172.16.0.0 ~ 172.31.255.255 MASK 255.255.0.0
  • Class C： 192.168.0.0 ~ 192.168.255.255 MASK 255.255.255.0

无类域间路由（CIDR）

CIDR: Classless InterDomain Routing （无类域间路由）

上述A、B、C类地址存在明确的划分（通过IP号），但这会存在一个问题，A类地址不必说，数量很少，瞬间就被分配完了，B类地址也是一样的道理，但是这类地址可分配的主机数量很多，通常没有企业单位会拥有如此多待分配的主机，为了充分利用资源，所以出现了无类域间路由。

路由器如何区分无类域间路由？仅凭前几位是无法做到的（没有明确的网络号和主机号位数），因此伴随而生的子网掩码出现了：

• 如果位为1：表示该位为网络位（子网部分）
• 如果位为0：表示该位为主机位
• 子网部分可以在任意的位置
• 地址格式: a.b.c.d/x, 其中 x 是地址中子网号的长度（另一种表示方式）

给定一个IP地址，计算网络号：将IP地址与对应的子网掩码进行与运算

原始的A、B、C类网络的子网掩码分别是：

• A：255.0.0.0 ：11111111 00000000 0000000 00000000
• B：255.255.0.0：11111111 11111111 0000000 00000000
• C：255.255.255.0：11111111 11111111 11111111 00000000

路由信息的匹配，分析路由表表项：

• 目标子网号
• 子网掩码
• 下一跳
• 端口
• 获得IP数据报的目标地址，将其与子网掩码进行与运算，得到网络号
• 对照路由表的目标子网号进行匹配：
  • 如果找到，则按照表项对应的接口转发该数据报
  • 如果都没有找到,则使用默认表项转发数据报

一个主机如何获得IP地址：

• 系统管理员手动分配，每个操作系统不一样
• DHCP（ Dynamic Host Configuration Protocol）:从服务器中动态获得一个IP地址
  • 基于UDP的服务
  • 允许主机在加入网络的时候，动态地从服务器那里获得IP地址：
    • 可以更新对主机在用IP地址的租用期（租期快到了）
    • 重新启动时，允许重新使用以前用过的IP地址
    • 支持移动用户加入到该网络（短期在网）
  • DHCP工作概况：
    • 主机广播“DHCP discover” 报文[可选]
    • DHCP 服务器用 “DHCP offer”提供报文响应[可选]
    • 主机请求IP地址：发送 “DHCP request” 报文
    • DHCP服务器发送地址：“DHCP ack” 报文 最开始，主机用32位全零的地址作为本机地址，以32位全一的地址进行广播

    

    DHCP 返回:

    • IP 地址
    • 第一跳路由器的IP地址（默认网关）
    • DNS服务器的域名和IP地址
    • 子网掩码 (指示地址部分的网络号和主机号)

一个主机如何获得一个网络的子网部分：

• 一个机构，从ISP获得地址块中分配一个小地址块，该机构可以进行小地址块的分配
• ICANN: Internet Corporation for Assigned Names and Numbers，通过该机构直接申请IP地址
  • 分配地址
  • 管理DNS
  • 分配域名，解决冲突

路由聚集（route aggregation）：是一种层次编址的方式，目的是减少路由信息通告、计算的数量。在路由匹配表项的时候，数量要大大减少。

在路由聚集时，如果出现一个IP地址能匹配到多个路由表项（这是可能出现的）：采用最长前缀匹配，因为更精确。

NAT（Network Address Translation）

NAT：网络地址转换

内网主机向外部发送分组时，经过路由，将内网地址转换为外网地址；同样的，外网的分组经路由传向内网时，将外网地址转换为内网地址。（内网节点共用一个IP）

使用NAT的原因：本地网络只有一个有效IP地址（IP地址申请使用需要付费）

• 不需要从ISP分配一块地址，可用一个IP地址用于所有的（局域网）设备 → 省钱
• 可以在局域网改变设备的地址情况下而无须通知外界
• 可以改变ISP（地址变化）而不需要改变内部的设备地址，更换方便
• 局域网内部的设备没有明确的地址，对外是不可见的 → 安全

若要实现NAT，则路由器必须支持NAT：

• 外出数据包：替换源地址和端口号为NAT IP地址和新的端口号，目标IP和端口不变 远端的C/S将会用NAP IP地址，新端口号作为目标地址
• 记住每个转换替换对（在NAT转换表中） 源IP | 端口 vs NAP IP | 新端口
• 进入数据包：替换目标IP地址和端口号，采用存储在NAT表中的mapping表项，用（源IP，端口）

对于NAT是有争议的：

• 路由器只应该对第3层做信息处理（物理层、链路层、网络层），而这里对端口号（4层，传输层）作了处理，显然不符合分层规范。
• 违反了end-to-end 原则：
  • 端到端原则：复杂性放到网络边缘 无需借助中转和变换，就可以直接传送到目标主机，显然这里路由器也承担了很多工作
  • NAT可能要被一些应用设计者考虑，例如：P2P applications
  • 外网的机器无法主动连接到内网的机器上（NAT穿越）
• NAT出现的原因是为了解决IP地址数量不够分配的情况，现在IP地址短缺的问题可以被IPv6解决
• NAT穿越： 很明显，内网的设备主动联系外网设备是容易做到的（路由器会在分组发出的时候记录下映射关系），但是如果外网设备主动连接内网中的设备是不可以的，并不知道具体的端口号。 解决方案：
  • 方案一：把路由表固定写死，映射关系是确定的，这样外部来的分组就可以查路由表，交给内网对应的主机。
  • 方案二： Universal Plug and Play (UPnP) 协议 / Internet Gateway Device (IGD) 协议 允许内网主机：
    • 获知网络的公共 IP地址
    • 列举存在的端口映射
    • 增/删端口映射 (在租用时间内) 自动化静态NAT端口映射配置：外部分组到来，先查询路由表的映射关系，如果没有找到对应的端口，自动分配一个主机，赋予其端口号。
  • 方案三：中继（used in Skype）
    • NAT后面的服务器主动建立和中继的连接（强调：需要主动连接）
    • 外部的客户端链接到中继
    • 中继在两个连接之间桥接

ICMP

因特网控制报文协议（ Internet Control Message Protocol，ICMP）

ICMP最典型的用途：差错报告

• 由主机、路由器、网关用于 传达网络层控制信息
  • 错误报告：主机不可到达、 网络、端口、协议
  • Echo 请求和回复（ping）
• ICMP处在网络层，但是是在IP协议的上面
  • ICMP消息由IP数据报承载

ICMP报文：类型（Type）、编码（Code）、引起ICMP报文首次生成的IP数据报首部和前8个字节内容（以便发送方能确定引发该差错的数据报）

Traceroute

• 源主机发送一系列UDP段给目标主机
  • 第一个：TTL =1
  • 第二个： TTL=2
  • 依次递增
  • 一个不可达的端口号
• 当 nth 数据报到达 nth 路由器：
  • 路由器抛弃数据报
  • 然后发送一个给源主机的ICMP报文 (type 11, code 0) → TTL过期
  • 报文包括了路由器的名字和IP地址
• 当 ICMP报文到达，源端计算RTT
• 标准的Traceroute程序实际上用相同的TTL发送3个一组的分组；因此Traceroute输出对每个TTL提供了3个结果
• 停止的判据：
  • UDP 段最终到达目标主机
  • 目标返回给源主机ICMP “端口不可达”报文 (type 3, code 3)
  • 当源主机获得这个报文时，停止

IPv6

引入IPv6的动机：IPv4的32-bit地址空间将会被很快用完

其他的原因：使用IPv4时路由器负担太重

IP数据报在每次经过路由时TTL就会减一，相应的头部长度就会变，首部校验和也会跟着改变，那么每一跳路由都需要进行校验和，此外上述提到的分片，加大了路由转发的负担。

IPv6数据报格式：

说明：

• 固定的40字节头部
• 数据报传输过程中，不允许分片 考虑如果分组太大，超过链路层的最大传输单元MTU，该如何处理？ 分组会被丢掉，同时向源主机发送一个ICMPv6的错误报告，目的让源主机重新发送更小的分组。
• 长度由32位变为128位
• Priority（pri）: 标示流中数据报的优先级
• Flow Label（流标签）：标示数据报在一个“flow” 同一个IP发送出去的同一个会话的数据，可以形成一个流，让网络对同一个流的数据做同样的处理
• Next header：标示上层协议（相当于IPv4中的upper layer（上层协议）） 标识传来的数据应该交给上层的哪一个协议实体去处理。
• hop limit：（相当于IPv4中的TTL）

相比于IPv4的其他变化：

• Checksum: 被移除掉，降低在每一段中的处理速度
• Options: 允许，但是在头部之外, 被 “Next Header” 字段标示
• ICMPv6: 新增ICMP的新版本
  • 附加了报文类型，例如：“Packet Too Big”
  • 增加多播组管理功能

IPv4到IPv6的过渡：

不是所有的路由器都能够同时升级的，那么在IPv4和IPv6路由器混合时，网络如何运转？

同时升级不可行，因此只能采用平滑升级。

分析上图，在目前一段时间内，可能有部分支持IPv6设备，它们在整个IPv4的“网络海洋”中犹如一个个的“孤岛”，支持IPv6与IPv4的设备不能相互通信（当然IPv6内部的网络可以通信，IPv4同样如此），如果一个IPv6的“孤岛”想向另一个IPv6的“孤岛”发送信息，只需要给分组在IPv4的“网络海洋”之中准备一艘“小船”就好，或者是隧道。

隧道: 在IPv4路由器之间传输的IPv4数据报中携带IPv6数据报

在IPv6与IPv4的边缘有同时支持两种协议的双栈协议。

可以将IPv6的数据报封装在IPv4的数据报当中，进行传输。

全面部署IPv6还需要很长一段时间，当慢慢地网络变成IPv6的“海洋”时，IPv4称为“孤岛”，那么则使用IPv6的隧道进行数据报传输，直到最后全面部署IPv6，完成平滑过渡。

路由选择算法

路由（route）

路由：按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径。

• 较好路径: 按照某种指标较小的路径
• 指标:站数, 延迟,费用,队列长度等, 或者是一些单纯指标的加权平均 采用什么样的指标,表示网络使用者希望网络在什么方面表现突出,什么指标网络使用者比较重视

路由的计算单位：网络（子网）

以IPv4为例，如果仅以精确的IP地址为计算单位，一共有232个，那么这个计算量过于庞大。

• 网络为单位进行路由，路由信息传输、计算和匹配的代价低
• 前提条件是：一个网络所有节点地址前缀相同，且物理上聚集
• 路由就是：计算网络到其他网络如何走的问题（路由信息通告 路由计算）

网络 - 网络的路由 = 路由器 - 路由器间的路由

• 网络对应的路由器到其他网络对应的路由器的路由
• 在一个网络中：路由器 - 主机之间的通信，链路层解决
• 到了这个路由器就是到了这个网络

路由器 - 路由器之间的最优路径 = 主机对之间的最优路径

• 路由器连接子网，子网到路由器之间的跳数就是一跳，必须要走
• 路由器到下一跳路由器（节点到节点）之间的最优路径找到了，也就找到了从源子网向目标子网所有主机对之间的最优路径
• 大大降低了路由计算的规模
• 在路由计算中按照子网到子网的路径计算为目标，而不是主机到主机

路由选择算法(routing algorithm)：网络层软件的一部分,完成路由功能

下图为网络的图抽象

说明：

• 节点：路由器
• 边：把路由器连接在一起的网络或者是点到点的链路

边的代价（Cost of path）：

• 表示方式：c(x,x‘) → 链路的代价 (x,x’)

举例：c(w,z) = 5

• 代价可能总为１
• 或是链路带宽的倒数
• 或是拥塞情况的倒数

路由的输入：拓扑、边的代价、源节点

最优化原则(optimality principle)

路由算法的最终目的是找到汇集树（sink tree）

• 此节点到所有其它节点的最优路径形成的树
• 路由选择算法就是为所有路由器找到并使用汇集树

路由选择算法的原则：

• 正确性(correctness)： 算法必须是正确的和完整的,使分组一站一站接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项；没有处理不了的目标站地址；
• 简单性(simplicity)： 算法在计算机上应简单：最优但复杂的算法，时间上延迟很大，不实用，不应为了获取路由信息增加很多的通信量； 在一条公路上，为了市民更好的通行而派出大量的警力去维持秩序，结果警力就占用了公路的三分之二，显然是不合理的。
• 健壮性(robustness)： 算法应能适应通信量和网络拓扑的变化：通信量变化，网络拓扑的变化算法能很快适应；不向很拥挤的链路发数据，不向断了的链路发送数据：
  • 两个路由节点之间的通信链路的传输速度有可能会发生改变
  • 网络拓扑有可能发生改变：可能A、B两个节点原来是有通路的，结果这条通路又断掉了

  算法应该要适应这些变化。

• 稳定性(stability)： 产生的路由不应该摇摆
• 公平性(fairness)： 对每一个站点都公平
• 最优性(optimality)： 某一个指标的最优，时间上，费用上，等指标，或综合指标；实际上，获取最优的结果代价较高，可以是次优的

路由算法的分类：

从一个角度来看，可分为全局、分布式

• 全局：
  • 所有的路由器拥有完整的拓扑和边的代价的信息
  • link state 算法
• 分布式：
  • 路由器只知道与它有物理连接关系的邻居路由器，和到相应邻居路由器的代价值
  • 叠代地与邻居交换路由信息、 计算路由信息
  • distance vector 算法

从另一个角度看，可分为静态、动态

• 静态：
  • 路由随时间变化缓慢
  • 非自适应算法(non-adaptive algorithm)：不能适应网络拓扑和通信量的变化,路由表是事先计算好的
• 动态：
  • 路由变化很快
    • 周期性更新
    • 根据链路代价的变化而变化
  • 自适应路由选择(adaptive algorithm)：能适应网络拓扑和通信量的变化

链路状态算法（link state，LS）

链路状态算法就是著名的迪杰斯特拉(Dijkstra)算法。

配置LS路由选择算法的路由工作过程：

• 各点通过各种渠道获得整个网络拓扑, 网络中所有链路代价等信息（这部分和算法没关系，属于协议和实现）
• 使用LS路由算法,计算本站点到其它站点的最优路径(汇集树),得到路由表
• 按照此路由表转发分组(datagram方式)【数据平面的工作】
  • 分发到输入端口的网络层（严格意义上说不是路由的一个步骤）

基本工作过程

链路状态（LS）路由的基本工作过程：

1. 发现相邻节点,获知对方网络地址
   • 一个路由器上电之后,向所有线路发送HELLO分组
   • 其它路由器收到HELLO分组,回送应答,在应答分组中,告知自己的名字(全局唯一)
   • 在LAN中,通过广播HELLO分组,获得其它路由器的信息,可以认为引入一个人工节点
2. 测量到相邻节点的代价(延迟,开销)
   • 实测法,发送一个分组要求对方立即响应
   • 回送一个ECHO分组
   • 通过测量时间可以估算出延迟情况
3. 组装一个链路状态（LS）分组,描述它到相邻节点的代价情况
   • 发送者名称
   • 序号,年龄
   • 列表: 给出它相邻节点,和它到相邻节点的延迟
4. 将分组通过扩散（泛洪）的方法发到所有其它路由器
   • 顺序号:用于控制无穷的扩散,每个路由器都记录(源路由器,顺序号),发现重复的或老的就不扩散（网络是一个环状的，不加以控制可以一直扩散下去，形成”广播风暴“，浪费了大量的资源，） 具体问题：
     • 具体问题1: 循环使用问题
     • 具体问题2: 路由器崩溃之后序号从0开始
     • 具体问题3:序号出现错误

     解决方案：年龄字段(age)

     • 生成一个分组时,年龄字段不为0
     • 每个一个时间段,AGE字段减1
     • AGE字段为0的分组将被抛弃
   • 关于扩散分组的数据结构
     • Source ：从哪个节点收到LS分组
     • Seq，Age：序号,年龄
     • Send flags：发送标记,必须向指定的哪些相邻站点转发LS分组
     • ACK flags：本站点必须向哪些相邻站点发送应答
     • DATA：来自source站点的LS分组

   以上4步让每个路由器获得拓扑和边代价

5. 通过Dijkstra算法找出最短路径（这才是路由算法）
   • 路由器获得各站点LS分组和整个网络的拓扑
   • 通过Dijkstra算法计算出到其它各路由器的最短 路径(汇集树)
     • 每个节点独立算出来到其他节点（路由器=网络）的最短路径
     • 迭代算法：第k步能够知道本节点到k个其他节点的最短路径
   • 将计算结果安装到路由表中

应用情况

链路状态的应用情况：

• OSPF协议是一种LS协议,被用于Internet上
• IS-IS(intermediate system - intermediate system)：被用于Internet主干中, Netware

算法原理

符号标记：

• c(i,j)：从节点 i 到 j 链路代价（初始状态下非相邻节点之间的链路代价为∞）
• D(v)：从源节点到节点V的当前路径代价（节点的代价）
• P(v)：从源到节点V的路径前序节点
• N’: 当前已经知道最优路径的的节点集合（永久节点的集合）

节点标记：每一个节点使用(D(v),p(v))

如： (3,B) 标记

• D(v)从源节点由已知最优路径到达本节点的距离
• P(v)前序节点来标注

两类节点：

• 临时节点(tentative node)：还没有找到从源节点到此节点的最优路径的节点
• 永久节点(permanent node) N’：已经找到了从源节点到此节点的最优路径的节点

流程：

1. 初始化
   • 除了源节点外,所有节点都为临时节点
   • 节点代价除了与源节点代价相邻的节点外,都为∞
2. 从所有临时节点中找到一个节点代价最小的临时节点,将之变成永久节点（假设找到一个节点W）
3. 对此节点的所有在临时节点集合中的邻节点，假设为节点V
   • 如 D(v) > D(w) c(w,v), 则重新标注此点, (D(W) C(W,V), W) 即源节点到V节点的距离又有最小值，则更新
   • 否则，不重新标注
4. 返回第2步，开始一个新的循环

案例：

Dijkstra算法的讨论

• 算法复杂度: n节点
  • 每一次迭代: 需要检查所有不在永久集合N中节点
  • n(n 1)/2 次比较: O(n2)
  • 有很有效的实现: O(nlogn)
• 可能的震荡： 举例：如果链路代价 = 链路承载的流量（拥塞程度）：

距离矢量算法（distance vector，DV）

• 动态路由算法之一
• DV算法历史及应用情况：
  • 1957 Bellman, 1962 Ford Fulkerson
  • 用于ARPANET, Internet(RIP) DECnet , Novell, ApplTalk
• 距离矢量路由选择的基本思想
  • 各路由器维护一张路由表
  • 各路由器与相邻路由器交换路由表
  • 根据获得的路由信息,更新路由表

如下图示例：

代价及相邻节点间代价的获得：

• 跳数(hops), 延迟(delay),队列长度
• 相邻节点间代价的获得：通过实测

路由信息的更新：

• 根据实测 得到本节点A到相邻站点的代价（如:延迟）
• 根据各相邻站点声称它们到目标站点B的代价
• 计算出本站点A经过各相邻站点到目标站点B的代价
• 找到一个最小的代价，和相应的下一个节点Z，到达节点 B经过此节点Z，并且代价为A-Z-B的代价

其它所有的目标节点一个计算法

实例

如下图：

• 以当前节点J为例,相邻节点 A,I,H,K
• J测得到A,I,H,K的延迟为： 8ms,10ms,12ms,6ms
• 通过交换DV, 从A,I,H,K获得到它们到G的延迟为 18ms,31ms,6ms,31ms
• 因此从J经过A,I,H,K到G的延迟为26ms,41ms,18ms, 37ms
• 将到G的路由表项更新为18ms,下一跳为：H
• 其它目标一样，除了本节点J（分组从J到J当然为0）

贝尔曼-福特（Bellman-Ford ）方程

实际上距离矢量算法是基于贝尔曼-福特（Bellman-Ford ）方程（动态规划）。

• 设：dx (y) = 从x到y的最小路径代价（x为源节点，y为目标节点）
• 则 dx (y) = min { c(x,v) dv (y) }
  • min：取所有x的邻居取最小的v
  • c(x,v)：x到邻居v的代价
  • dv (y)：从邻居v到目标y的代价

案例1：

• 明显：dv (z) = 5 , dx (z) = 3 , dw (z) = 3
• 由 B-F 方程得到： du (z) = min { c(u,v) dv (z) , c(u,x) dx (z) , c(u,w) dw (z) } = { 2 5 , 1 3 , 5 3 } = 4

核心思路：

• 每个节点都将自己的距离矢量估计值传送给邻居，定时或者DV有变化时，让对方去算
• 当x从邻居收到DV时，自己运算，更新它自己的距离矢量（采用B-F equation）
• Dx (y)估计值最终收敛于实际的最小代价值dx (y) 是迭代算法、分布式算法

异步式,迭代：每次本地迭代被以下事件触发：

• 本地链路代价变化了
• 从邻居来了DV的更新消息

分布式：

• 每个节点只是在自己的DV改变之后向邻居通告
• 然后邻居们在有必要的时候通知他们的邻居

每个节点的动作如下图：

案例2：

DV的特点

特点：

• 好消息传的快 好消息的传播以每一个交换周期前进一个路由器的速度进行 举例：假设刚架设的路由节点A，它与B连通了

• 经过第一个周期，c(A,B) = 1
• 经过第二个周期，c(A,C) = 2
• 如此下去

• 坏消息传的慢（无穷计算问题） 举例：路由节点A刚刚撤销了

• 第一次交换之后, B从C处获得信息,C可以到达A(C-A,但是要经过B本身),但是路径是2,因此B变成3,从C处走
• 第二次交换,C从B处获得消息, B可以到达A,路径为3, 因此,C到A从B走,代价为4
• 形成了一个环路
• 无限次循环下去，到A的距离就变成了∞（不可达）

实际上有一种缓解环路（无穷计算）的情况，即水平分裂(split horizon)算法。

水平分裂(split horizon)算法

注：有些教材也解释为“毒性逆转”。

一种对无穷计算问题的解决办法：

• 假设节点B直达A，C到A依赖于B，D到A依赖于B，C
• 现在突然A节点不可达
• C知道要经过B才能到达A，所以C向B报告它到A的距离为∞（虚假信息）；但是C告诉D它到A的真实距离
• 同样的，D告诉C它通向A的距离为∞（虚假信息），但是D告诉E它到A的真实距离 “左向虚假，右向真实”
• 这样在第一次交换的时候，B通过测试发现到A的路径为∞，而C也告诉B到A的距离为∞，因此B到A的距离为∞
• 在第二次交换的时候，C从B和D那里获知,到A的距离为∞，因此C到A的距离为∞
• 如此，坏消息也同样以一次交换一个节点的速度传播

值得注意的是，水平分裂算法在某些拓扑形式下会失败（存在环路），分析下图：

• A,B到D的距离为2, C到D的距离为1
• 现在假设C-D通路销毁
• C获知到D的距离为∞，从A,B获知到D的距离为∞，因此C认为D不可达
• A从C获知D的距离为∞，但从B处获知它到D的距离为2，因此A到B的距离为3，从B走
• B也有类似的问题
• 经过无限次之后，A和B都知道到D的距离为∞

LS 和 DV 算法的比较

下面我们来分析链路状态算法和距离矢量算法的差别：

• 消息复杂度
  • LS: 有 n 节点, E 条链路,发送 报文O(nE)个
    • 局部的路由信息；全局传播
  • 只和邻居交换信息
    • 全局的路由信息，局部传播
  • 距离矢量算法更优
• 收敛时间
  • LS：O(n2) 算法
    • 有可能震荡
  • DV: 收敛较慢
    • 可能存在路由环路（无限循环问题）
  • 链路状态算法更优
• 健壮性：如果路由器故障会发生什么
  • LS：
    • 节点会通告不正确的链路代价
    • 每个节点只计算自己的路由表
    • 错误信息影响较小，局部，路由较健壮
  • DV：
    • DV 节点可能通告对全网所有节点的不正确路径代价
    • 每一个节点的路由表可能被其它节点使用 假如一个节点出现错误，通告全网到此路由的代价为0，那么全网的所有分组就都会涌向此节点
    • 错误可以扩散到全网
  • 链路状态算法更优

两种路由选择算法都有其优缺点，而且在互联网上都有应用。

因特网中自治系统（AS）内部的路由选择

路由选择信息协议（Routing Information Protocol，RIP）

• 在 1982年发布的BSD-UNIX 中实现
• 基于距离矢量算法：
  • 距离矢量：每条链路cost = 1， 代价就是跳数 (max = 15 hops，16代表目标不可达)
  • 约定V每隔30秒和邻居交换距离矢量（DV），通告
    • 情况一：定期30秒，而且在改变路由的时候发送通告报文
    • 情况二：在对方的请求下也可以发送通告报文
  • 每个通告包括：最多25个目标子网
    • 内容：目标网络 跳数（最大跳数为16，表示不可达）

下图是一个RIP协议的实例：

如果此时，节点A发送给D新的距离矢量，告知A到Z的跳数为4，那么D的距离矢量就会更新，如下图：

链路失效和恢复

如果180秒（6个周期）没有收到通告信息，则表示邻居或者链路失效

• 发现经过这个邻居的路由已失效
• 新的通告报文会传递给邻居
• 邻居因此发出新的通告 (如果路由变化的话)
• 使用毒性逆转（poison reverse）/水平分裂算法，阻止ping-pong回路 ( 不可达的距离：跳数无限 = 16 段)

RIP 进程处理

• RIP 以应用进程的方式实现：route-d (daemon)
• 通告报文通过UDP报文传送，周期性重复
• 网络层的协议使用了传输层的服务，以应用层实体的方式实现 这一点很有趣，网络层的功能以应用进程的形式来实现，为了实现这个功能，还要借助传输层来传输距离矢量DV

开放最短路优先（Open Shortest Path First，OSFP）

• “open”：标准可公开获得
• 使用链路状态算法：
  • LS 分组在网络中（一个AS内部）分发
  • 全局网络拓扑、代价在每一个节点中都保持
  • 路由计算采用Dijkstra算法
• OSPF通告信息中携带：每一个邻居路由器一个表项 “我是谁”，传输的链路状态分组是第几个版本，TTL “我有哪些邻居，我到邻居的代价是多少”
• 通告信息会传遍AS全部（通过泛洪）
  • 在IP数据报上直接传送OSPF报文 (而不是通过UDP和TCP)
• IS-IS路由协议：几乎和OSPF一样

OSPF高级特性

这些特性是在RIP中所没有的。

• 安全: 所有的OSPF报文都是经过认证的 (防止恶意的攻击)
• 允许有多个代价相同的路径存在 (在RIP协议中只有一个) 可以在代价相同的节点作“负载均衡”。
• 对于每一个链路，对于不同的TOS有多重代价矩阵 例如：卫星链路代价对于尽力而为的服务代价设置比较低，对实时服务代价设置的比较高 支持按照不同的代价计算最优路径，如：按照时间和延迟分别计算最优路径
• 对单播和多播的集成支持：
  • Multicast OSPF (MOSPF) 使用相同的拓扑数据库，就像在OSPF中一样
• 在大型网络中支持层次性OSPF

如果网络比较大，可以把自治区域划分成：骨干区域（backbone）、区域一、区域二… 不同的小区域之间的分组转发都需要借助区域边界路由器（area border routers），先将其路由至骨干区域。 泛洪仅在小区域内部进行。 分组的传递过程：小区域 →（通过区域边界路由器）→ 骨干区域 →（通过边界路由器）→ 传送到其他子网（依然通过另一个子网的骨干区域到达小区域）

层次性的OSPF路由：

• 两个级别的层次性: 本地, 骨干
  • 链路状态通告仅仅在本地区域Area范围内进行
  • 每一个节点拥有本地区域的拓扑信息 关于其他区域，知道去它的方向，通过区域边界路由器（最短路径）
• 区域边界路由器: “汇总（聚集）”到自己区域内网络的距离, 向其它区域边界路由器通告 同时参与了两个区域的路由计算
• 骨干路由器: 仅仅在骨干区域内，运行OSPF路由
• 边界路由器: 连接其它的自治系统（AS’s）

小结一下： 如果

ISP之间的路由选择

一个平面的路由

• 一个网络中的所有路由器的地位一样
• 通过LS, DV，或者其他路由算法，所有路由器都要知道其他所有路由器（子网）如何走
• 所有路由器在一个平面
• 平面路由的问题：
  • 规模巨大的网络中，路由信息的存储、传输和计算代价巨大：
    • DV: 距离矢量很大，且不能够收敛
    • LS：几百万个节点的LS分组的泛洪传输，存储以及最短路径算法的计算
  • 管理问题：
    • 不同的网络所有者希望按照自己的方式管理网络
    • 一方面希望对外隐藏自己网络的细节
    • 当然，还希望和其它网络互联

一个平面的路由面临计算成本的高昂代价以及管理问题，为此出现了一个解决方案：层次路由。

层次路由

将互联网中的路由问题分为两个层面（按照物理分布范围）：

• 自治区域内
• 自治区域间
• 层次路由：将互联网分成一个个自治区域AS(路由器区域)
  • 某个区域内的路由器集合，自治系统（autonomous systems ，AS)
  • 一个AS用 AS Number（ASN)唯一标示
  • 一个ISP可能包括一个或者多个AS
• 路由变成了两个层次的路由：
  • AS内部路由：在同一个AS内路由器运行相同的路由协议
    • intra-AS routing protocol：内部网关协议
    • 不同的AS可能运行着不同的内部网关协议（如：LS，DV）
    • 能够解决规模和管理问题
    • 如：RIP,OSPF,IGRP
    • 网关路由器：AS边缘路由器，可以连接到其他AS
  • AS间运行AS间路由协议
    • inter-AS routing protocol：外部网关协议
    • 解决AS之间的路由问题，完成AS之间的互联互通
• 层次路由的优点：
  • 解决了规模问题：
    • 内部网关协议解决：AS内部数量有限的路由器相互到达的问题, AS内部规模可控 如果AS节点太多，可继续分割AS，使得AS内部的节点数量有限
    • AS之间的路由的规模问题：
      • 增加一个AS，对于AS之间的路由从总体上来说，只是增加了一个节点=子网（每个AS可以用一个点来表示）
      • 对于其他AS来说只是增加了一 个表项，就是这个新增的AS如何走的问题
      • 扩展性强：规模增大，性能不会减得太多
  • 解决了管理问题：
    • 各个AS可以运行不同的内部网关协议
    • 可以使自己网络的细节不向外透露，增加安全性

边界网关协议（Border Gateway Protocol，BGP）

• BGP (Border Gateway Protocol): 自治区域间路由协议“事实上的”标准 将互联网各个AS粘在一起的胶水
• BGP 提供给每个AS以以下方法：
  • eBGP: 从相邻的ASes那里获得子网可达信息（外部）
  • iBGP: 将获得的子网可达信息传遍到AS内部的所有路由器（内部）
  • 根据子网可达信息和策略来决定到达子网的“最优”路径

  

• 允许子网向互联网其他网络通告“我在这里”
• 基于距离矢量算法（路径矢量）
  • 这是一种“改进”后的距离矢量
  • 不仅仅是距离矢量，还包括到达各个目标网络的详细路径（AS序号的列表）能够避免简单DV算法的路由环路问题

BGP会话

• BGP 会话: 两个BGP路由器(“peers”)在一个半永久的TCP连接上 交换BGP报文（包括子网可达信息）:
  • 通告向不同目标子网前缀的“路径”（BGP是一个“路径矢量”协议）
• 当AS3中新增了X节点（如下图）：

当AS3网关路由器3a向AS2的网关路由器2c通告路径： AS3,X

• 3a参与AS内路由运算，知道本AS所有子网X信息
• 语义上：AS3向AS2承诺，它可以向子网X转发数据报
• 3a是2c关于X的下一跳（next hop）

路径的属性：

• 当通告一个子网前缀时，通告包括 BGP 属性：
  • prefix attributes = “route”
• 两个重要的属性：
  • AS-PATH: 前缀的通告所经过的AS列表: AS 67、AS 17
    • 检测环路；多路径选择
    • 在向其它AS转发时，需要将自己的AS号加在路径上
  • NEXT-HOP: 从当前AS到下一跳AS有多个链路，在NETX-HOP属性中，告诉对方通过那个 链路转发
  • 其它属性：路由偏好指标，如何被插入的属性

BGP是基于策略的路由：

• 当一个网关路由器接收到了一个路由通告, 使用输入策略来接受或过滤（accept / decline）
  • 过滤原因例1：不想经过某个AS，转发某些前缀的分组
  • 过滤原因例2：已经有了一条往某前缀的偏好路径
• 策略也决定了是否向它别的邻居通告收到的这个路由信息

BGP路径通告

• 路由器AS2.2c从AS3.3a接收到的AS3,X路由通告 (通过eBGP)
• 基于AS2的输入策略，AS2.2c决定接收AS3,X的通告，而且通过iBGP（TCP连接）向AS2的所有路由器进行通告
• 基于AS2的策略，AS2路由器2a通过eBGP向AS1.1c路由器通告 AS2,AS3,X 路由信息 路径上加上了 AS2自己作为AS序列的一跳

网关路由器可能获取有关一个子网X的多条路径，从多个eBGP 会话上：

• AS1 网关路由器1c从2a学习到路径：AS2,AS3,X
• AS1网关路由器1c从3a处学习到路径：AS3,X
• 基于策略，AS1路由器1c选择了路径：AS3,X，而且通过iBGP告诉所有AS1内部的路由器 不一定跳数少即判定为代价小，要基于策略的判断 有政治策略（例如：敌对公司）、经济策略等

BGP报文

• 使用TCP协议交换BGP报文
• BGP 报文： OPEN：打开TCP连接，认证发送方 UPDATE：通告新路径 (或者撤销原路径) KEEPALIVE：在没有更新时保持连接，也用于对 OPEN 请求确认 NOTIFICATION：报告以前消息的错误，也用来关闭连接

问题：一个自治区域（AS1）中的普通路由器如何才能将分组传递到另一个自治区域（AS2）内的路由器？

区域边界路由器可以通过外部网关协议获知AS2中路由器的存在，并通过内部网关协议通告AS1中所有的路由器。

BGP 路径选择

• 路由器可能获得一个网络前缀的多个路径，路由器必须进行路径的选择，路由选择可以基于：
  • 本地偏好值属性: 偏好策略决定
  • 最短AS-PATH：AS的跳数
  • 最近的NEXT-HOP路由器：热土豆路由（给最近的）
  • 附加的判据：使用BGP标示
• 一个前缀对应着多种路径，采用消除规则直到留下一条路径

热土豆路由

• 2d通过iBGP获知，它可以通过2a或者2c到达X
• 热土豆策略：选择具备最小内部区域代价的网关作为往X的出口（如：2d选择2a，即使往X可能有比较多的AS跳数）：不要操心域间的代价

内部网关协议与外部网关协议的不同

• 策略：
  • Inter-AS: 管理员需要控制通信路径，谁在使用它的网络进行数据传输
  • Intra-AS: 一个管理者，所以无需策略
    • AS内部的各子网的主机尽可能地利用资源进行快速路由
• 规模：
  • AS间路由必须考虑规模问题，以便支持全网的数据转发
  • AS内部路由规模不是一个大的问题
    • 如果AS 太大，可将此AS分成小的AS；规模可控
    • AS之间只不过多了一个点而已
    • 或者AS内部路由支持层次性，层次性路由节约了表空间, 降低了更新的数据流量
• 性能：
  • Intra-AS: 关注性能
  • Inter-AS: 策略可能比性能更重要

后记

本篇已完结

（如有补充或错误，欢迎评论区留言）