JWangL5's Blog
分类 系列 文章 相册 关于我
JWangL5's Blog

目录

网络笔记 | 07. 路由选择算法

卢旺 avatar卢旺  收录于  类别 机枢织序 和 系列 计算机网络
     约 3737 字   预计阅读 17 分钟 
网络层内容框架

  • 距离向量的定义

    • 路由信息协议RIP（Routing Information Protocol）是内部网关协议IGP中最先得到广泛使用的协议之一，其相关标准文档为RFC1058
    • RIP要求自治系统AS内的每一个路由器都要维护从它自己到AS内其他每一个网络的距离记录。这是一组距离，称为“距离向量D-V(Distance-Vector)
    • RIP使用跳数(Hop Count)作为度量(Metric)来衡量到达目的网络的距离
      • 路由器到直连网络的距离定义为1
      • 路由器到非直连网络的距离定义为所经过的路由器数加1，允许一条路径最多只能包含15个路由器
      • “距离”等于16时相当于不可达。因此，RP只适用于小型互联网。
      • 有些厂商的路由器没有按照标准文档来实现RIP，例如思科路由器就将路由器到直连网络的距离定义为0，但这并不影响其正常运行

  • 工作原理

    • RIP包含以下三个要点：仅周期性地（如30秒）和相邻路由器交换自己的路由表
    • RIP认为，好的路由就是距离短的路由，也就是通过路由器少的路由，例如下图中的网络结构中，RIP会认为蓝色的路由线路更优，即使其链路带宽都很小
    • 当到达同一目的网络有多条距离相等的路由时，可以实现等价负载均衡，即可以将通信量均衡地分布到多条等价的路由上

  • RIP工作的基本过程与更新规则

    • 路由器刚开始工作时，只知道自己到直连网络的距离为1

    • 每个路由器进周期性地和相邻路由器交换并更新路由信息

    • 若干次交换和更新后，每个路由器都知道到达本AS内各网络的最短距离和下一跳的地址，称为收敛

    • RIP信息交换的更新规则，以如下结构举例

      * 路由器C的信息在交换给路由器D时，路由器D并不关心路由器C的下一条是谁，这里直接用`?`​表示 * 路由器D在收到路由器C发来的路由表时，首先对其进行更新：将下一跳全部更新为C，路由距离+1，随后用更新后的表格与自己的表格进行比对
      * 在表格更新时，有如下更新理由： * 相同目的网络和相同下一跳，可能由于网络拓扑改变，需要更新距离 * 相邻路由器发现了新的网络，添加到自己的表格中 * 相同的目的网络，下一跳不同，则比较距离，新路由更短或相等时更新或添加新记录，新路由更长时则不更新
      • 习题

  • RIP存在坏消息传得慢的问题，如下图案例所示，

    • 当R1与N1网络连接出现故障，R1首先将路由表中的记录更改为16，意味不可达
    • 当到达下一次更新周期时，如果R2发送来的信息早于R1发出，那么R1就会被谣言误导，认为可以通过R2+1的距离达到改变网络
    • 随后该谣言会随着时间在两者间来回摆动，直到两者都达到16之后才收敛
    • 这期间，R1和R2之间会出现路由环路，历时数分钟
    • 该问题被称为““坏消息传得慢”，或者路由环路、距离无穷计数问题，是距离向量算法的固有问题，可以采取多种措施来减少该问题出现的频率或出现后的危害
      • 限制最大路径为15，16即表示不可达
      • 当路由表发生变化后，立即发送路由更新报文（触发更新），而不仅是周期性更新
      • 让路由器记录收到某特定路由信息的接口，且不让同一路由信息再通过此接口反向传送（水平分割）
    • 练习

  • 基本信息

    • 开放最短路径优先OSPF（Open Shortest Path First）是为克服RIP的缺点在1989年开发出来的
    • “开放”表明OSPF协议不是受某一家厂商控制，而是公开发表的
    • “最短路径优先”是因为使用了Dijkstra提出的最短路径算法SPF
    • OSPF是基于链路状态的，而不像RIP那样是基于距离向量的
    • OSPF采用SPF算法计算路由，从算法上保证了不会产生路由环路
    • OSPF不限制网络规模，更新效率高，收敛速度快

  • 基本工作原理

    • 链路状态是指本路由器都和哪些路由器相邻，以及相应链路的“代价”（cost）
    • “代价”用来表示费用、距离、时延、带宽，等等，这些都由网络管理人员来决定，例如在思科路由器中，其被定义为：100Mpbs/链路带宽，结果小于1的记为1，大于1的舍去小数部分
    • OSPF相邻路由器之间通过交换问候（hello）分组，建立和维护邻居关系
      • 问候分组封装在IP数据报中，发往组播地址224.0.0.5​
      • 其发送周期为10秒；若40秒未收到来自邻居路由器的Hello分组，则认为路由器不可达
      • 因而，每个路由器都会有一个邻居表，包含邻居ID、接口，以及死亡倒计时
    • 使用OSPF的每个路由器，都会产生链路状态通告LSA（Link State Advertisment），包含直连网络的链路状态信息和邻居路由器的链路状态信息，该信息被封装在链路状态更新分组LSU中，采用洪泛法发送，确保每个路由器都能收到该信息
    • 使用OSPF的每个路由器都有一个链路状态数据库LSDB，用于存储LSA
    • 通过各路由器洪泛发送封装有自己LSA的LSU分组，各路由器的LSDB最终将达到一致；使用OSPF的各路由器，基于LSDB进行最短路径优先SPF计算，构建出各自到达其他路由器的最短路径，即构建各自的路由表
      • ​image​

  • OSPF有五种分组类型

    • 问候分组Hello，用来发现和维护邻居路由器的可达性
    • 数据库描述分组Database description，向邻居路由器给出自己的链路状态数据库中的所有链路状态项目的摘要信息
    • 链路状态请求分组Link state request，向邻居路由器请求发送某些链路状态项目的详细信息
    • 链路状态更新分组Link state update，路由器使用这种分组，将其链路状态进行洪泛发送，全网更新链路状态
    • 链路状态确认分组Link state acknowledgement，是对链路状态更新分组的确认分组

  • 基本工作过程：其主要分为三个阶段，如下图所示

  • 当OSPF路由器在多点接入网络中建立邻居关系时，如果不采用其他机制，会产生大量的多播分组

    • 例如下图所示的网络结构，5台主机多点接入在网络中，他们之间任意两个路由器都互为邻居关系（数量为$\frac{n(n-1)}{2}$），此时如果他们周期性地发送问候分组以建立和维护邻居关系，消息就会很冗余
    • 为了减少所发送分组的数量，OSPF会选举出指定路由器DR和备用的指定路由器BDR，所有的非DR/BDR路由器，只与他们之间建立邻居关系，非DR/BDR之间必须通过DR/BDR交换信息。此时邻居关系可表示如下，此时的邻居关系数量为$2(n-2)+1$
    • 选举方法跟生成树协议选举根交换机类似

  • 为了使OSPF能够用于规模很大的网络，OSPF还把一个自治系统再划分为若干个更小范围的区域（Area）

    • 如下图所示的自治系统中，所有路由器使用OSPF协议
    • OSPF将该资质系统再划分为4个更小的区域，每个区域都有一个32比特的区域标识符，可以用点分十进制表示
      • 主干区域的标识符必须为0，可以表示为0.0.0.0​，其用于连通其他区域
      • 其他区域的标识符不能为0，且互不相同，其规模不应太大，通常不超过200个
      • 这样划分的好处是在使用洪泛法交换链路状态信息的范围局限于每一个区域，而不是整个自治系统，从而减少整个网络上的通信量
    • ​image​
    • 如果路由器的所有接口都在区域内，称为区域内路由器IR
    • 为了本区域能够和自治系统中的其他区域连通，每个区域都会有一个区域边界路由器ABR，其一个接口用于连接自身所在区域，另一个接口连接主干区域
    • 位于主干区域内的路由器称为主干路由器BBR，所有的区域边界路由器也是主干路由器
    • 主干区域内还需要一个路由器，专门和本自治系统外的其他路由器交换路由信息，称为自治系统边界路由器ASBR
  • 基本特征
    • 外部网关协议用于自治系统之间的路由选择，典型的协议为边界网关协议BGP
    • 在不同的自治系统内，度量路由的代价可能不同（如距离、带宽、费用等），因此，对于自治系统间的路由选择，使用代价作为度量来寻找最佳路由的策略是不可行的
    • 自治系统之间的路由选择，还必须考虑政治、经济、安全等相关策略
    • 因而，BGP的目标只能是力求选择一条能够到达目的网络且比较好的路由（不能兜圈子），而并非寻找一条最佳路由
  • BGP发言人
    • 在配置BGP时，每个自治系统的管理员，要选择至少一个路由器作为作为该自治系统的“BGP发言人”
    • 通常而言，两个BGP发言人都是通过一个共享网网络连接在一起的，而BGP发言人往往就是BGP边界路由器
    • 使用TCP连接交换路由信息的两个BGP发言人，彼此称为对方的邻站（neighbor）或对等站（peer）
    • 不同自治系统的BGP发言人要交换路由信息，必须先建立TCP连接，端口号为179，从而在此TCP连接上交换BGP报文以建立BGP会话
      • 利用BGP会话交换路由信息，如增加新的路由、撤销过时的路由、 报告出错的情况等
      • 这里是一个BGP发言人交换路径向量的例子
    • BGP发言人除了运行BGP外，还必须运行自己所在自治系统所使用的内部网关协议IGP，例如OSPF或RIP
    • BGP发言人交换网络可达性的信息后（要到达某个网络要经过的一系列自治系统），各BGP发言人就根据所采用的策略从收到的路由信息中，找出到达个自治系统的较好的路由；其所构建出的自治系统连同图是树形结构的、不存在回路
  • BGP-4中的四种报文
    • OPEN（打开）报文：用来与相邻的另一个BGP发言人建立关系，使通信初始化
    • UPDATE（更新）报文：用来通告某一路由的信息，以及列出要撤销的多条路由
    • KEEPALIVE（保活）报文：用来周期性地证实邻站的连通性
    • NOTIFICATION（通知）报文：用来发送检测到的差错
  • 练习

‍

更新于 2025-09-17
 | 主页