【计算机网络笔记】路由算法之层次路由

系列文章目录

什么是计算机网络？
什么是网络协议？
计算机网络的结构
数据交换之电路交换
数据交换之报文交换和分组交换
分组交换 vs 电路交换
计算机网络性能（1）——速率、带宽、延迟
计算机网络性能（2）——时延带宽积、丢包率、吞吐量/率
计算机网络体系结构概念
OSI参考模型基本概念
OSI参考模型中非端-端层（物理层、数据链路层、网络层）功能介绍
OSI参考模型中端-端层（传输层、会话层、表示层、应用层）功能介绍
TCP/IP参考模型基本概念，包括五层参考模型
网络应用的体系结构
网络应用进程通信
网络应用对传输服务的需求
Web应用之HTTP协议（涉及HTTP连接类型和HTTP消息格式）
Cookie技术
Web缓存/代理服务器技术
传输层服务概述、传输层 vs. 网络层
传输层——多路复用和多路分用
传输层——UDP简介
传输层——可靠数据传输原理之Rdt协议
传输层——可靠数据传输之流水线机制与滑动窗口协议
传输层——TCP特点与段结构
传输层——TCP的可靠数据传输
TCP连接管理（图解三次握手和四次挥手）
传输层——拥塞控制原理与解决方法
TCP的拥塞控制机制
网络层服务与核心功能
网络层服务模型——虚电路网络
网络层服务模型——数据报网络
Internet网络的网络层——IP协议之IP数据报的结构
IP分片
IP编址与有类IP地址
IP子网划分与子网掩码
CIDR与路由聚合
DHCP协议
网络地址转换(NAT)
ICMP（互联网控制报文协议）
IPv6简介
路由算法之链路状态路由算法
路由算法之距离向量路由算法

---

---

层次路由

更准确地说，它是一种路由策略。

链路状态路由算法和距离向量路由算法都需要将任意规模网络抽象为一个图再计算路由。若一个网络的规模特别大，那么这种抽象就会过于理想。

• 从网络规模的角度考虑，如果有6亿目的结点的网络，那么路由表几乎无法存储，并且路由计算过程的信息 （e.g. 链路状态分组、 DV）交换量巨大，会淹没链路
• 还需要考虑网络管理自治性的问题

层次路由就是把大规模网络再抽象一层，将一个区域内的路由器聚合在一起，称为自治系统AS (autonomous systems)。

• 同一AS内的路由器运行相同的路由协议(算法)，即自治系统内部路由协议 (“intra-AS” routing protocol)。不同自治系统内的路由器可以运行不同的AS内部路由协议
• 每一个自制系统（AS）都有一个或多个特殊的路由器，叫网关路由器(gateway router)，它位于AS“边缘”，通过链路连接其他AS的网关路由器。所以可以通过网关路由器与其它AS交换路由信息

因此，就可以把路由分为自治系统内的路由和自治系统间
的路由。

自治系统间(Inter-AS)路由任务

假设AS1内某路由器收到一个目的地址在AS1 之外的数据报。那么路由器应该将该数据报转发给哪个网关路由器呢？为了解决这样的路由问题，AS1必须：

• 学习到哪些目的网络可以通过AS2到达，哪些可以通过AS3到达
• 将这些网络可达性信息传播给AS1内部路由器

以路由器1d为例，看看它的转发表设置。

• 假设AS1学习到(通过AS间路由协议)：子网x可以通过AS3 (网关 1c)到达，但不能通过AS2到达。这样的信息会被告知AS1中的所有路由器
  • 路由器1d：利用AS内部路由信息，确定其到达1c 的最小费用路径接口l，然后在转发表中增加入口：(x, I)
• 假设AS1通过AS间路由协议学习到：子网x通过 AS3和AS2均可到达
  • 为了配置转发表，路由器1d必须确定应该将去往子网x的数据报转发给哪个网关。这个任务也是由AS间路由协议完成，去在多个网关中进行选择
  • 怎么选择？会用到热土豆路由，也就是将分组发送给最近的网关路由器

整个过程概括如下：