西安电子科技大学：《通信网络基础》课程教学资源（讲义）第五章 路由算法 路由算法概述

2 Xidian University 第五章路由算法 王玺钧 通信工程学院信息科学研究所

第五章 路由算法 王玺钧 通信工程学院信息科学研究所

Xidian University 5.1路由算法概述

5.1 路由算法概述

Xidian University 回顾OS协议的体系结构 第三层：网络层（network layer) 应用层 为用户提供接入0S1的环境，还提供分布式信息服务 网络层的基本功能是把网络中的节 点和数据链路有效地组织起来，为 表示层 定义信息的表示方法，向应用程序和终端处理程序 提供一系列的数据转换服务。从而使应用程序与数 终端系统提供透明的传输通路（路 据表示的差异性无关。 径)。网络层通常分为两个子层： 会话层 负责控制应用程序间的通信，为协同工作的应用程 序之间建立、管理和终止连接（会话) 网内子层和网际子层。 运输层 在两个端点之间提供可靠透明的数据传输，提供端 网内子层解决子网内分组的路由、 到端的差错恢复和流量控制 网络层 寻址和传输问题；网际子层解决分 使高层的功能独立于用来连接网路节点的传输和交 换技术，负责建立、维护和终止连接。 组跨越不同子网的路由选择、寻址 数据链路层 和传输问题。 为信息跨越物理链路提供可靠的传输，发送带有必 要的同步、差错控制和流控制信息的数据块（帧） 物理层 它还包括不同子网之间速率匹配、 关注在物理媒介上（非结构化）比特流的传输，处 理接入物理媒介的机械、电气、功能和过程特性 流量控制、不同长度分组的适配、 连接的建立、保持和终止等问题

会话层 负责控制应用程序间的通信，为协同工作的应用程 序之间建立、管理和终止连接（会话） 物理层 关注在物理媒介上（非结构化）比特流的传输，处 理接入物理媒介的机械、电气、功能和过程特性 应用层 为用户提供接入OSI的环境，还提供分布式信息服务 表示层 定义信息的表示方法，向应用程序和终端处理程序 提供一系列的数据转换服务。从而使应用程序与数 据表示的差异性无关。 运输层 在两个端点之间提供可靠透明的数据传输，提供端 到端的差错恢复和流量控制 数据链路层 为信息跨越物理链路提供可靠的传输，发送带有必 要的同步、差错控制和流量控制信息的数据块（帧） 网络层 使高层的功能独立于用来连接网路节点的传输和交 换技术；负责建立、维护和终止连接。 回顾OSI协议的体系结构 第三层：网络层（network layer） 网络层的基本功能是把网络中的节 点和数据链路有效地组织起来，为 终端系统提供透明的传输通路（路 径）。网络层通常分为两个子层： 网内子层和网际子层。 网内子层解决子网内分组的路由、 寻址和传输问题；网际子层解决分 组跨越不同子网的路由选择、寻址 和传输问题。 它还包括不同子网之间速率匹配、 流量控制、不同长度分组的适配、 连接的建立、保持和终止等问题

Xidian University 的 路由算法概述 源带点 口在通信网络中，网络层主要负责将两个终端系统 经过网络中的节点用数据链路连接起来，组成通 信通路，实现两个终端系统之间数据的透明传送 口所谓透明传输是指发端发送到网络接口的任何信 息都会按照其原始的形式传送到接收端，网络不 会修改其内容或将与该信息无关的内容送给接收 者 口网络层的功能包括寻址和选择路由，建立、保持 和终止网络连接等

在通信网络中，网络层主要负责将两个终端系统 经过网络中的节点用数据链路连接起来，组成通 信通路，实现两个终端系统之间数据的透明传送 所谓透明传输是指发端发送到网络接口的任何信 息都会按照其原始的形式传送到接收端，网络不 会修改其内容或将与该信息无关的内容送给接收 者 网络层的功能包括寻址和选择路由，建立、保持 和终止网络连接等。 路由算法概述 2 S 9 7 5 6 3 8 D 4 目的节点 源节点

Xidian University 路由算法概述 口路由算法是网络层的核心问题，其主要功能是指 引分组通过通信子网到达正确的目的节点。 口它包括两个方面的功能： -为不同的源节点和目的节点对（SD)选择一条传输路径； 一在路由选择好以后，将用户的消息正确地送到目的节点。 目的节点 8 5

路由算法是网络层的核心问题，其主要功能是指 引分组通过通信子网到达正确的目的节点。 它包括两个方面的功能： –为不同的源节点和目的节点对（SD）选择一条传输路径； –在路由选择好以后，将用户的消息正确地送到目的节点。 路由算法概述 2 S 9 7 5 6 3 8 D 4 目的节点 源节点

Xidian University 路由算法概述 网络设计者面临的问题是： 1.采用什么策略来选择合适的路由？ 2.依据什么信息来进行这种选择？ 3.应该如何执行这种选择的策略？ 4.用什么标准来评判所选路径的好坏？

网络设计者面临的问题是： 1.采用什么策略来选择合适的路由？ 2.依据什么信息来进行这种选择？ 3.应该如何执行这种选择的策略？ 4.用什么标准来评判所选路径的好坏？ 路由算法概述

Xidian University 路由算法概述 例5.1网络中有两个源节点和一个目的节点。所有链路 的容量为10个单位，两个源节点1和2的输入业务量分 别为几1和2，试讨论：①人1=2=5单位时；②九1=5单位， 2=15单位时，路由选择对网络性能的影响。 九2 源节点 源节点 3 所有链路的容量均为10单位 目的节点

• 例5.1网络中有两个源节点和一个目的节点。所有链路 的容量为10个单位，两个源节点1和2的输入业务量分 别为λ1和λ2，试讨论：① λ1=λ2=5单位时；② λ1=5单位， λ2=15单位时，路由选择对网络性能的影响。 1 2 3 4 5 6 λ1 λ 2 所有链路的容量均为10单位 源节点 源节点 目的节点 路由算法概述

Xidian University 路由算法概述 ①11=12=5单位时 ①如果节点1选择 1→3→6，节点2选 源节点 源节点 择2→5→6，则由 于每条链路的业务 量都只有信道容量 的一半，因而时延 很小。 所有链路的容量均为10单位 目的节点

1 2 3 4 5 6 λ1 λ 2 所有链路的容量均为10单位 源节点 源节点 目的节点 ① 如果节点1选择 136，节点2选 择256，则由 于每条链路的业务 量都只有信道容量 的一半，因而时延 很小。 ① λ1=λ2=5单位时 路由算法概述

Xidian University 路由算法概述 源节点 源节点 如果节点1选择 1→4→6，节点2选择 2→4→6，则链路4→6 运载的业务量为10个 单位，达到了链路的 最大容量，因而时延 会很大。 所有链路的容量均为10单位 目的节点

1 2 3 4 5 6 λ1 λ 2 所有链路的容量均为10单位 源节点 源节点 目的节点 路由算法概述 如果节点1选择 146，节点2选择 246，则链路46 运载的业务量为10个 单位，达到了链路的 最大容量，因而时延 会很大

Xidian University 路由算法概述 ②此时1=5单位， 源节点 源节点 2=15，节点2的输入业 务量为15个单位。由于 每条链路的容量仅为10 个单位，在仅使用一条 路径的情况下，节点2至 少要丢弃5个单位的业务 量。 所有链路的容量均为10单位 目的节点

路由算法概述 ② 此时λ1=5单位， λ2=15 ，节点2的输入业 务量为15个单位。由于 每条链路的容量仅为10 个单位，在仅使用一条 路径的情况下，节点2至 少要丢弃5个单位的业务 量。 1 2 3 4 5 6 λ1 λ 2 所有链路的容量均为10单位 源节点 源节点 目的节点