文档介绍：第五章 路由器与路由算法
路由器的结构
路由算法
算法的分类
距离矢量算法
链路状态算法
移动路由算法
.
路由器概述
局域网（LAN）和拨号用户需要通过路由器接入因特网
（RB）
1
（RB）
2
目的网络号
下一个转发路由器端口或IP地址
度量（转发次数）
（RA）
1
直接端口1
0
直接端口2
0
（RC）
1
目的网络号
下一个转发路由器端口或IP地址
度量（转发次数）
（RB）
2
（RB）
1
直接端口1
0
直接端口2
0
路由器A的路由表
路由器B的路由表
路由器C的路由表
.
.
Internet 路由表包含内容
目的或网络掩码
协议
优先级
优先权
下一跳地址
输出接口
影响路由权的属性，如右图。越小，路径越好。
带宽
时延
负载
可靠性
跳数
开销
.
Internet路由协议
路由协议或路由种类
优先级缺省值
路由算法
DIRECT
0
OSPF
10
链路状态算法
INTERNAL EIGRP
50
距离矢量算法
STATIC
60
IGRP
80
距离矢量算法
RIP
100
距离矢量算法
IBGP
130
距离矢量算法
OSPF ASE
150
链路状态
EXTERNAL EIGRP
160
距离矢量算法
EBGP
170
距离矢量算法
UNKNOWN
255
.
最短路径路由算法
属于静态路由算法
基本思想
构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。
测量路径长度的方法
结点数量
地理距离
传输延迟
距离、信道带宽等参数的加权函数
计算方法：Dijkstra算法
A
E
D
C
B
F
2
2
1
3
1
1
2
5
3
5
.
洪泛算法（Flooding）
属于静态路由算法
基本思想
把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
主要问题
洪泛要产生大量重复包。
解决措施
每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包；
记录包经过的路径
.
选择性洪泛算法（selective flooding）
基本思想
洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上；或者按一定的概率选择发送。
应用情况
对路由器和线路的资源过于浪费，实际很少直接采用；
具有极好的健壮性，可用于军事应用；
作为衡量标准评价其它路由算法。
.
基于流量的路由算法（Flow-Based Routing）
属于静态路由算法
基本思想
既考虑拓扑结构，又兼顾网络负荷；
前提：每对结点间平均数据流是相对稳定和可预测的；
根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。
提前离线（off-line）计算。
.
需要预知的信息
网络拓扑结构；
通信量矩阵Fij；
线路带宽矩阵Cij；
路由算法（可能是临时的）。
.
.
1/ = 800 bits
根据排队论，平均延迟 T = 1/ (C - )
.
距离矢量路由算法（Distance Vector Routing）
属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP协议采用。
基本思想
每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表；
.
每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；
邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新本路由器的路由表；
注意：本路由器中的老路由表在计算中不被使用
.
.
链路状态路由