[网络协议]【计算机网络学习笔记14】路由选择与转发

【计算机网络学习笔记14】路由技术

选择转发

整个路由器的结构可以划分成两个部分：路由选择和分组转发。

分组到达路由器的时候，先通过物理层（接受比特流）、数据链路层（解析数据帧并收发MAC地址）、网络层（处理分组并解析分组头部的控制信息）。

典型的路由器结构如下图所示。

路由和转发这两个功能要注意区分：

路由是路径的确定、路由表的产生
转发是根据目的地址去查路由表确定输出端口的过程

说白了：路由是转发的前提，转发则是路由的使用。

路由选择

指在组成网络的众多节点之间找到一条从源节点到目的节点的最优路径的过程。

路由选择协议（用于交换网络信息）

路由表（用于指向目的网络）

路由表

记录：决定到某个子网去，下一站该送交哪一个路由器端口。

??注意：路由表并非为每个具体的目的主机IP地址指明路径，而是为目的主机所在的网络指明路径，以控制路由表的大小。即查找路由表的依据是目的主机的网络地址。

选择标准

跳数、地理距离、带宽、负载、通信成本、延迟

分组转发

指依据收发双方的IP地址查找转发表，将分组转发到相应的输出端口的过程。

转发表（用于指导分组转发输出）

路由算法

算法分类

静态路由算法、动态路由算法

静态路由算法

• 静态路由
• 预先设定，不会动态调整

💡补充：缺省路由，指在路由表中无法查到的目标网络，在路由表中明确指定一个出口的路由。

??注意：缺省（默认）路由是静态路由的一个特例，同样需要人工配置。

动态路由算法

• 根据网络状态调整路由表
• 需要收集网络信息（不定时或者间隔特定时间）

算法原则

最优化原则

从所有源端到目的端的最佳路由的集合，形成了以目的地为根的树，这样的一棵树成为汇集树，如下图所示。

其中距离度量单位为站数。需要指出的是汇集树并不唯一，所有的路由选择算法的目的就是为所有路由器找出并使用汇集树。

最短路径算法

• 思路：构建网络拓扑图，找出最短路径
• 路径开销
  • 跳数、距离、延迟（时延）、带宽、成本……
  • 加权组合
• 迪克斯特拉（Dijkstra）算法（使用(距离,上一跳)二元组对结点进行标记）

迪克斯特拉算法

求解单元点的最短路径，给定带权有向图G和源点v，求v到G中其他顶点的最短路径。

限制条件：图G中不存在负权值的边

操作步骤

创建一个表格，分别记录 节点、已标记、距离（指出发点0到节点）、经过点（从最小点到目的点要经过的点）；初始状态所有点的距离均为∞。

示例表格如下所示。

• 确定出发点0的标识，其距离为0（原点）。
• 检查所有节点中距离最短的节点（即0点），在已标记上打??，更新与其临近节点的距离、经过点。
• 在未标记的节点中，寻找距离出发点最小的节点，在以标记上??，更新与其临近节点的距离、经过点。（如果新距离小于旧距离，则更新；反之不更新。）
• 紧接着另一个节点（即第二步中剩下的未标记点），在 已标记上??，更新与其临近节点的距离、经过点。（如果新距离小于旧距离，则更新；反之不更新。）
• 重复步骤3，并检查距离变化（这里的距离指的是：从出发点到某目的点总距离），直到表格更新完毕。

距离矢量算法

DV（Distance Vector Routing ，距离矢量）算法要点：

• 仅和相邻路由器交换信息

• 路由器交换的内容是自己的路由表

• 周期性更新（例如，RIP协议间隔30秒）

常见的使用此算法的路由协议：RIP（使用跳数作为路径距离；每经过一个路由器，跳数加一）

链路状态算法

基本思想：

• 发现邻居

• 建立链路状态数据库

• 建立拓扑结构图

• 根据最短路径算法计算汇集树

• 生成路由表

常见的使用此算法的路由协议：OSPF（1988年开始制定，1990年成为标准，采用L-S路由算法）、IS-IS（由DEC公司于20世纪80年代后期开发，在ISO 10589中以标准形式发布）

优缺点

优点

• 路由信息的一致性好，坏消息也一样传播得快

• 状态分组的长度较短，传输所耗用的网络带宽不大

• 状态分组不会无限制扩散，可适用于大型网络

缺点

• 每个路由器需要有较大的存储空间，用以存储所收到的每一个节点的链路状态分组。

• 计算工作量大，每次都必须计算最短路径

算法比较

距离矢量算法与链路状态算法的区别如下表所示。

路由协议

RIP

使用的是距离矢量路由算法，使用跳数来衡量路由距离。

过程

• 路由器启动RIP协议，向周围邻居路由器广播发送请求报文（Request message）。

• 周围RIP路由器收到请求报文后，把自己的RIP路由表封装在Response报文内，进行回送。

• 路由器收到邻居路由器响应报文后，修改本地路由表。

路由

• 路由器收到响应报文后，会修改路由表信息，故路由表的开销值也发生改变。同时路由器会向相邻路由器以广播形式发送修改报文。

• 相邻路由器收到触发更新修改报文之后，会对各自相邻路由器发送触发更新修改报文，使各路由器都得到最新路由信息。

• 老化机制会对超时的路由进行老化处理。RIP分组以30s一次的频率通过广播的形式发送，若某路由在180s内未被刷新，则其相应的距离会被设定成无穷大，且从路由表中删除该表项。

优缺点

优点

• 简单方便
• 路由器开销小

缺点

• 交换的路径信息量大
• 路径信息不一致
• 收敛速度慢（坏消息的时间变长）
• 不适合大型网络（最长为15跳）

OSPF

使用的是链路状态路由算法，以链路开销值判断路径长短。

过程

• 一台路由器刚启动，首先要做的就是发现它有哪些邻居，并且与邻居建立关系。

路由器发送HELLO包给所有邻居，邻居也会发回HELLO包进行应答。每隔10秒发送HELLO包发现、建立并维持邻居关系。

• 与邻居建立关系后，路由器根据与邻居间链路的类型、状态设置参数。

OSPF协议里最重要的链路参数就是链路开销值，用于计算最短路径；它是与带宽相关的，链路带宽越大则开销值越小。

常用的计算公式为：接口开销=带宽参考值÷接口带宽。（小于1的开销取1表示）

• 发现邻居节点

  当一个路由器启动后，向每个点到点线路发送HELLO分组（携带自己的网络地址），另一端的路由器发送回来一个应答来说明它是谁，即通报其网络地址

• 测量线路开销

  发送一个ECHO分组要求对方立即响应，通过测量一个来回时间再除以2，发送方就可以得到一个延迟估计值，想要更精确些，可以重复这一过程，取其平均值

• 构造分组

  子网及其节点到其邻节点（路由器）的线路开销测量值（即时延，假设以毫秒计）

  

• 发布链路状态分组

  用扩散法（向邻接的节点）发布链路状态分组 （以B为例，B的邻接点有A、C、F）

  

网关协议

术语概念

自治系统（AS，Autonomous System）

• 概念：每个组织运营的网络内部，可以使用自己的内部路由算法形成的独立网络。

内部网关协议（IGP，Interior Gateway Protocol）

• 概念：自治系统内部使用的路由协议

• 例子：OSPF/IS-IS/RIP

外部网关协议（EGP，Exterior Gateway Protocol）

• 概念：自治系统之间使用的路由协议
• 例子：BGP

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

• 概念
  • 自治系统外部路由协议，用来在AS之间传递路由信息
• 特性
  • 路径矢量路由协议，避免环路；
  • 支持CIDR和路由聚合；
  • 路由附带丰富的属性；
  • TCP承载（179端口），天然可靠性；
  • 路由过滤和路由策略

内外区别

内部网关（IGP）与外部网关（EGP）的区别如下表所示。

其中外部网关（EGP）关注的路由策略有：

• 政治：国家与国家
• 经济：企业与企业
• 安全：军事区
• 费用：运营商

多协议标签交换

MPLS概述

MPLS位于TCP/IP协议栈中的链路层和网络层之间，用于向IP层提供连接服务，同时又从链路层得到服务。

MPLS非常接近虚电路交换，采用面向连接的工作方式，故场与异步传递方式（ATM）联系起来。

路由器根据数据包标签而非数据包目的地址实施转发；通过标签作为一个内部表的索引，实现快速且正确的线路查找。

需要注意的是，MPLS工作机制的核心是路由仍然使用第三层的路由协议解决，交换则是第二层的硬件区完成。

MPLS原理

体系结构：指运行MPLS的单个设备内部的独立工作原理

网络结构：指运行MPLS的多个设备互连的联合工作原理

体系结构

网络结构

MPLS在网络结构中的基本工作原理如下图所示。

转发过程

MPLS转发数据包的过程如下图所示。

MPLS标签

MPLS标签有四个区域：

• Label：20bit，标签值域。
• Exp：3bit，用于扩展。现在通常用做CoS（Class of Service，服务类别），与Ethernet802.1p的作用类似。
• BoS：1bit，栈底标识。MPLS支持多层标签，即标签嵌套。S值为1时表明为最底层标签。
• TTL：8bit，与IP分组中的TTL（Time To Live）意义相同。

MPLS特点

• 提供面向连接与QoS服务
• 支持流量工程、平均网络负载
• 支持虚拟专用网络（VPN）
• 支持多协议

Internet组播

术语

单播：单点发送多点接收的点对点传输。（一对一）

组播：允许一个或多个发送方发送单一数据报到多个接收方的网络传输方式。无论组员数量，只发一次数据包；采用组播地址寻址，只向需要数据包的主机或网络发送。（一对一组）。

广播：由路由器或交换机将同一个信息无条件地发送给每一条路径中的节点，由接收者决定接收还是丢弃。（一对多）

组播

IP组播（多播）的概念提出于1988年。

• Internet组管理协议（IGMP）的定义是1989年RFC1112
• 从IGMPv2（RFC2276，1997年）开始为Internet标准协议
• 最新版本是IGMPv3（RFC3376，2002年10月）

多播数据包使用D类IP地址作为目的地址（每个D类地址标识一组主机，有28位可用于标识组播，故网络中可同时存在250万个组），且部首中的协议字段值为2，表明使用IGMP协议。

RFC3330对D类地址的命名空间作出如下表所示的规定。（组播地址示例表）

本地组播地址示例表如下所示。

组播示意图如下所示。

特点

1. 需要相同数据流的客户端加入相同的组共享一条数据流，节省了服务器的负载。具备广播所具备的优点。
2. 由于组播协议是根据接受者的需要对数据流进行复制转发，所以服务端的服务总带宽不受客户接入端带宽的限制。IP协议允许有2亿6千多万个（268435456）组播，所以其提供的服务可以非常丰富。
3. 此协议和单播协议一样允许在Internet宽带网上传输。

总结

知识体系

作者： 陈诺
排版： 胖虎
初审： 正山小种
复审： 二月二

更多视频课程请访问 “CSDN 正月十六工作室讲师学院首页”

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生