路由器与路由算法

路由算法

第五章 路由器与路由算法 路由器的结构 路由算法– 算法的分类

– 距离矢量算法– 链路状态算法

– 移动路由算法

路由算法

5.1 路由器概述5.1.1 路由器在因特网中的地位 局域网(LAN)和拨 号用户需要通过路由 器接入因特网 因特网的通信子网由 各种路由器互连而成 路由器是上网的“必 由之路”

路由算法

5.1.2

路由器结构概述

路由器的两个关键功能： 运行路由算法/协议 (RIP,OSPF,BGP) 交换分组于输入链路到输出链路之间

路由算法

输入端口功能

物理层： 位流级的接收 数据链路层： e.g., Ethernet 分散化的交换： 按照给出的分组信宿，使用输入端口的内 存中存储的路由选择表，查找输出端口 目标: 以“线路速度”完成输入端口的处 理 排队: 假如分组到达的数度快于转发到交 换网络的( switch fabric)速度时缓存

路由算法

三类交换网络

路由算法

内存交换(Switching Via Memory) 第一代路由器: 分组通过系统的(单个)CPU拷贝 速度受到内存带宽的限制 (每个分组需2次穿越 系统总线)Input Port Memory Output Port

System Bus

路由算法

总线交换(Switching Via Bus) 分组通过一条共享的总线从输入端口的内存传递 到输出端口的内存 总线竞争：交换速率受限于总线的带宽 1 Gb/s总线，Cisco 1900:对访问接入和企业级 的路由器已经足够 (但还不适应在区域或主干级 线路上使用)

路由算法

通过内联网络交换(Switching Via An Interconnection Network) 克服了总线带宽的限制 Banyan networks,内联网络技术在发展初期是 用来连接多处理器系统中的处理器 设计先进：把分组分割成固定长度的单元, 再把这 些单元送入交换网络 Cisco 12000:通过内联网络交换速度可达若干 Gb/s

路由算法

输出端口的功能

缓存：当来自交换网络的分组到达速度高于传输速率时，需要进行缓存 调度原则：从队列中的分组中选择传输

路由算法

5.2 路由算法路由选择协议目标: 在收发双方的通信过程 中为分组(所经由的一系列路 由器中)确定一条“好” 的路 径5

B A1

3 2 3 1

C1

2

5

路由选择算法抽象: 图中的结点是路由器 图中的线条为物理链 路– 链路成本：延迟，费 用￥,或拥塞的程度

F2

D

E

“好” 路:– 一般为费用最低的路径 – 也可以另行定义

路由算法

5.2.1 路由算法应具有的特性 路由算法是网络层软件的一部分 – 通信子网采用数据报分组交换方式，每个包都 要做路由选择； – 通信子网采用虚电路分组交换方式，只需在建 立连接时做一次路由选择。 路由算法应具有的特性 – 正确性(correctness) – 简单性(simplicity) – 健壮性(robustness) – 稳定性(stability) – 公平性(fairness) – 最优性(optimality)

路由算法

5.2.2 路由算法分类全局或分散的信息? 全局: 所有路

由器都有完整的拓扑 逻辑,链路成本信息 LS (Link State) 算法 分散: 路由器只了解物理上邻接的 路由器，了解到达这些路由 器的链路成本 DV (Distance Vector) 算法 静态或动态的? 静态: 路由变化较少的 情况 动态: 路由变化较快的 情况 – 定期更新 – 为了响应链路 成本的变化

路由算法

静态路由 – 由管理员手工配置。在网络结构简单、到目标 点只有一条路径的网络中，只配置静态路由就 可正常工作。 – 路由算法简单。 – 无自适应功能。当网络出现问题或因其他原因 引起拓扑变化时，静态路由不会自动发生改变， 必须要有网络管理员的介入。 动态路由 – 路由器根据给定的路由算法，通过自学习，构 造路由表。 – 具有自适应功能。 – 算法比较复杂。

路由算法

5.2.3 Internet路由表

128.1.0.0

128.2.0.0

128.3.0.0

128.4.0.0 路由器C

路由器A128.1.0.2

路由器B128.2.0.3

128.3.0.3

端口1端口2 128.2.0.2

端口1端口2 128.3.0.2

端口1端口2 128.4.0.2

路由算法

路由器A的路由表目的网络号 128.1.0.0 128.2.0.0 128.3.0.0 128.4.0.0 下一个转发路由器端口或IP地址 直接端口1 直接端口2 128.2.0.3(RB) 128.2.0.3(RB) 度量(转发次数) 0 0 1 2

路由器B的路由表目的网络号 128.1.0.0 128.2.0.0 128.3.0.0 128.4.0.0 下一个转发路由器端口或IP地址 128.2.0.2(RA) 直接端口1 直接端口2 128.3.0.3(RC) 度量(转发次数) 1 0 0 1

路由器C的路由表目的网络号 下一个转发路由器端口或IP地址 度量(转发次数)

128.1.0.0128.2.0.0 128.3.0.0 128.4.0.0

128.3.0.2 (RB)128.3.0.2 (RB) 直接端口1 直接端口2

21 0 0

路由算法

路由算法

Internet 路由表包含内容

目的或网络掩码 协议 优先级 优先权 下一跳地址 输出接口 影响路由权的属性， 如右图。越小，路径 越好。

带宽 时延 负载 可靠性 跳数 开销

路由算法

Internet路由协议路由协议或路由种类 DIRECT OSPF INTERNAL EIGRP 优先级缺省值 路由算法 0 10 链路状态算法 50 距离矢量算法 60 80 距离矢量算法 100 距离矢量算法

STATIC IGRP RIP IBGP OSPF ASE EXTERNAL EIGRP EBGP UNKNOWN

130 150 160 170 255

距离矢量算法 链路状态 距离矢量算法 距离矢量算法

路由算法

5.2.4 最短路径路由算法属于静态路由算法 基本思想 – 构建子网的拓扑图，图中的每个结点代表一个路由器， 每条弧代表一条通信线路。为了选择两个路由器间的 路由，算法在图中找出最短路径。 5 测量路径长度的方法 3 – 结点数量 B C 5 – 地理距离 A 2 2 F 1 3 – 传输延迟 1 2 D E – 距离、信道带宽等参数的加权函数 1 计算方法：Dijkstra算法

路由算法

5.2.5

洪泛算法(Flooding)

属于静态路由算法 基本思想 – 把收到的每一个包，向除了 该包到来的线路外的所有输 出线路发送。 主要问题 – 洪泛要产生大量重复包。 解

决措施 – 每个包头包含站点计数器， 每经过一站计数器减1,为 0时则丢弃该包； – 记录包经过的路径

A

B

C

D

E

F

G

J

K

路由算法

选择性洪泛算法(selective flooding)

基本思想 – 洪泛法的一种改进。将进来的每个包仅发送到 与正确方向接近的线路上；或者按一定得概率 选择发送。 应用情况 – 对路由器和线路的资源过于浪费，实际很少直 接采用； – 具有极好的健壮性，可用于军事应用； – 作为衡量标准评价其它路由算法。

本文来源：https://www.bwwdw.com/article/08nm.html