路由协议基础

0
0
0

动态路由

动态路由选择协议不仅执行路径决策和路由表更新功能，而且还要在最优路径不可用时决策下一条最优路径。通常，一种路由算法是一个逐步解决问题的过程，一种路由算法至少应该指明一下内容：

  • 向其他路由器传送网络可达性信息的过程。
  • 从其他路由器接收可达性信息的过程。
  • 基于现有可达性信息决策最优路由的过程以及在路由表中记录这些信息的过程。
  • 响应、修正和通告网络中拓扑变化的过程。

对于所有路由协议来说，几个共同的问题是路径决策、度量、收敛与负载均衡。

  1. 路径决策，
  2. 度量，包括“跳数”、“带宽”、“负载”、“时延”、“可靠性”与“代价”。
  3. 收敛，对于路由选择协议来说，另一个标准是网络上所有路由器的路由表中的可达性信息必须一致。使所有路由表都达到一致状态的过程叫做收敛（convergence）。全网实现信息共享以及所有路由器计算最优路径所花的时间总和就是收敛时间。
  4. 负载均衡，为了有效地使用带宽，负载均衡作为一种手段，将流量分配到相同目标网络的多条路径上。

距离矢量路由选择协议

大多数路由选择协议都是如下两类的其中之一：距离矢量（Distance Ventor）和链路状态（Link State）。大多是距离矢量算法是以R.E.Bellman、L.R.Ford和D.R.Fulkerson所做的工作为基础的，因此，距离矢量又称Bellman-Ford算法或Ford-Fulkerson算法。

距离矢量路由选择协议是“根据传闻进行路由选择的”路由协议。

距离矢量名称的由来是因为路由是以矢量（距离，方向）的方式被通告出去的，其中距离是根据度量定义的，方向是根据下一跳路由器定义的。

距离矢量路由选择协议包括：IP路由选择信息协议（RIP）、Internet网关路由选择协议（IGRP）和增强型Internet网关路由协议（EIGRP）等。

通用属性：典型的距离矢量路由选择协议通常会选择一个路由选择算法，算法中路由器通过广播整个路由表，定期地向所有邻居发送路由更新信息：

  • 定期更新：每经过特定时间周期就发送更新消息。这个时间一般为10s-90s。
  • 邻居： 向邻接路由器发送更新消息，信息逐跳更新。
  • 广播更新： 路由器首次激活时，广播发送更新信息。
  • 全路由选择表更新： 路由器广播整个路由表。邻居在收到这些更新信息后，收集自己需要的信息，而丢弃其他信息。

困难与改进算法：

  • 路由失效计时器：为处理部分网络拓扑发生变化时的重新收敛困难，距离矢量路由选择协议为每个路由表项设置路由失效计时器，计时器超时就删除该表项。路由超时其的典型周期为3-6个更新周期。
  • 水平分隔：为切断邻居路由器之间的环路，阻止两台路由器之间逆向路由。其分为两类：
    • 简单水平分隔：从某接口发送的更新消息不能包含从该接口收到的更新所包含的网络。
    • 毒性逆转水平分隔：当更新信息被发送出某接口时，信息中将指定从该接口收到的更新信息中获取的网络是不可达的。
  • 计数到无穷大：为切断网络中的环路，大多数距离矢量路由选择协议定义无穷大为16跳。
  • 触发更新：当一个度量变好或者变坏时，路由器将立即发送更新信息，而不等更新计时器超时。从而减少收敛时间。
  • 抑制计时器：为了降低接受错误路由选择信息的可能性，抑制计数器引入了某种程度的怀疑量。如果一个目标的距离增加，路由器将为该路由设置抑制计时器，直到计时器超时，路由器才接受有关此路由的更新信息。
  • 异步更新：每个路由器的更新计时器独立与路由选择进程，且每个更新周期中加入一个小的随机时间，防止路由器计时器同步产生更新数据碰撞。

链路状态路由选择协议

距离矢量路由协议所使用的信息可以比拟为由路标提供的信息。链路状态路由选择协议像是一张公路线路图。

不同于距离矢量依据传闻进行路由选择的工作方式，链路状态路由器从对等路由器那里获得第一手信息。每台路由器产生一些关于自己、本地直连链路、这些链路的状态和所有直接相连邻居的信息。这些信息从一台路由器传送到另一台路由器，每台路由器都做一份信息拷贝，但是决不改动信息。最终目的是每台路由器都有一个相同的有关网络的信息，并且每台路由器可以独立计算各自的最优路径。

链路状态协议，又叫最短路径优先协议或分布式数据库协议，基于图论中的一个著名算法E.W.Dijkstra的最短路径算法设计的。链路状态协议有以下几种：OSPF、IS-IS与NLSP等。

基本步骤：链路状态协议的基本步骤如下：

  1. 每个路由器与它的邻居之间建立联系，这种联系叫做邻接关系。
  2. 每台路由器向每个邻居发送被称为链路状态通告（LSA）的数据单元。每个邻居在收到通告之后将依次向它的邻居转发（泛洪）这些通告。
  3. 每台路由器要在数据库中保存一份它收到的LSA的备份。如果所有工作正常，所有路由器的数据库应该相同。
  4. 完整的拓扑数据库，也叫链路状态库，Dijkstra算法使用它对网络图进行计算得出每台路由器的最短路径。接着链路状态协议对链路状态数据库进行查询找到每台路由器所连接的子网，并把这些信息输入到路由表中。

具体说明如下：

  1. 邻居
    邻居发现是建立链路状态环境并运转的第一步。这一步使用Hello协议。Hello协议定义了一个Hello数据包的格式和交换数据包并处理数据包信息的过程。
    两台路由器已经互相发现并视对方为邻居时，它们要进行数据库同步过程，即交换和确认数据库信息直到数据库相同为止。
    除了建立邻接关系之外，Hello数据包还可以作为监视邻接关系的握手信号。在特定时间内没有收到邻接路由器的Hello数据包，则认为邻居路由器不可达，随即邻接关系被解除。典型的Hello数据包交换间隔为10s，典型的死忙周期是数据包交换间隔的4倍。

  2. 链路状态泛洪扩散
    在建立邻接关系之后，路由器开始发送LSA。通告被发送给每个邻居，路由器保存接收到的LSA，并依次向每个邻居转发。
    LSA几乎是立刻被转发，而距离矢量在发送路由更新之前必须运行算法并更新自身的路由表，甚至对于触发路由更新也是如此。因此，当网络拓扑改变时，链路状态协议收敛速度远远快于距离矢量协议

    泛洪扩散总有两个过程对泛洪扩散是极其重要的：

    • 排序：LSA格式中包含一个序列号字段。路由器每发送LSA1次，LSA中的序列号递增1。路由器转发LSA时，每个拷贝中的序列号都是一样的。序列号的命名方法有：线性序列号空间、循环序列号空间与棒棒糖形序列号空间等。
      -老化：LSA格式中包含一个用于通告年龄的字段。当LSA被创建时，路由器将该字段设置为0.随着数据包的扩散，每台路由器都会增加通告中的年龄。老化过程为泛洪扩散过程增加了另一层可靠性。

  3. 链路状态数据库
    链路状态数据库把LSA作为一连串记录保存下来。虽然LSA还包括序列号、年龄和其他信息，但这些变量主要用于管理泛洪扩散进程。对于最短路径决策进程来说，其主要使用LSA包含的两类通用信息：

    • 路由器链路信息：使用三元组（路由器ID、邻居ID、代价）通告路由器的邻居路由器。
    • 末梢网络信息：使用三元组（路由器ID、网络ID、代价）通过路由器直接相连的末梢网络。

距离矢量与链路状态-比较

  • 信息传播方式：
    运行距离矢量路由协议的路由器，将处理后的所有路由信息通告给邻居节点。且仅通告给邻居。
    运行链路状态路由协议的路由器，将与它直连的链路的状态通告给整个域。

  • 路由算法：

    • 距离矢量路由协议使用Bellman-Ford(Ford-Fulkerson)算法。容易产生路由环路（loop）和计数到无穷大，由于每台路由器都必须在将从邻居学到的路由转发给其它路由器之前，运行路由算法，所以网络的规模越大，其收敛速度越慢。
    • 链路状态路由协议使用了强健的SPF算法，如OSPF的dijkstra，不易产生路由环路，或是一些错误的路由信息。路由器在转发链路状态包时（描述链路状态、拓扑变化的包），没必要首先进行路由运算，再给邻居进行发送，从而加快了网络的收敛速度。

  • 路由条目更新方式：

    • 距离矢量路由协议，更新的是“路由条目”！一条重要的链路如果发生变化，意味着需通告多条涉及到的路由条目！
    • 链路状态路由协议，更新的是“拓扑”！每台路由器上都有完全相同的拓扑，他们各自分别进行SPF算法，计算出路由条目！一条重要链路的变化，不必再发送所有被波及的路由条目，只需发送一条链路通告，告知其它路由器本链路发生故障即可。其它路由器会根据链路状态，改变自已的拓扑数据库，重新计算路由条目。

  • 更新周期性：

    • 距离矢量路由协议发送周期性更新、完整路由表更新（periodic & full）
    • 链路状态路由协议更新是非周期性的（nonperiodic），部分的（partial）

路由算法

Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

Bellman-Ford 算法采用动态规划进行设计，实现的时间复杂度为 O(V*E)，其中 V 为顶点数量，E 为边的数量。Dijkstra 算法采用贪心算法（Greedy Algorithm）范式进行设计，普通实现的时间复杂度为 O(V2)，若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 O(E + VlogV)。

Bellman-Ford 算法

贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达$O(VE)$。但算法可以进行若干种优化，提高了效率。

算法描述：

  • 数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；
  • 以下操作循环执行至多n-1次，n为顶点数：
    对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
    若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
  • 为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说该图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

Bellman－Ford算法可以大致分为三个部分
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：
d（v） > d (u) + w(u,v)

贝尔曼-福特算法的最多运行O（|V|·|E|)次，|V|和|E|分别是节点和边的数量）。

/*
* About:  Bellman-Ford算法
* Author: Tanky Woo
* Blog:   www.WuTianqi.com
*/

#include 
using namespace std;
const int maxnum = 100;
const int maxint = 99999;

// 边，
typedef struct Edge{
    int u, v;    // 起点，重点
    int weight;  // 边的权值
}Edge;

Edge edge[maxnum];     // 保存边的值
int  dist[maxnum];     // 结点到源点最小距离

int nodenum, edgenum, source;    // 结点数，边数，源点

// 初始化图
void init()
{
    // 输入结点数，边数，源点
    cin >> nodenum >> edgenum >> source;
    for(int i=1; i<=nodenum; ++i)
        dist[i] = maxint;
    dist[source] = 0;
    for(int i=1; i<=edgenum; ++i)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].weight;
        if(edge[i].u == source)          //注意这里设置初始情况
            dist[edge[i].v] = edge[i].weight;
    }
}

// 松弛计算
void relax(int u, int v, int weight)
{
    if(dist[v] > dist[u] + weight)
        dist[v] = dist[u] + weight;
}

bool Bellman_Ford()
{
    for(int i=1; i<=nodenum-1; ++i)
        for(int j=1; j<=edgenum; ++j)
            relax(edge[j].u, edge[j].v, edge[j].weight);
    bool flag = 1;
    // 判断是否有负环路
    for(int i=1; i<=edgenum; ++i)
        if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
        {
            flag = 0;
            break;
        }
    return flag;
}
int main()
{
    //freopen("input3.txt", "r", stdin);
    init();
    if(Bellman_Ford())
        for(int i = 1 ;i <= nodenum; i++)
            cout << dist[i] << endl;
    return 0;
}

补充:
考虑：为什么要循环V-1次？
答：因为最短路径肯定是个简单路径，不可能包含回路的，
如果包含回路，且回路的权值和为正的，那么去掉这个回路，可以得到更短的路径
如果回路的权值是负的，那么肯定没有解了

图有n个点，又不能有回路
所以最短路径最多n-1边

又因为每次循环，至少relax一边
所以最多n-1次就行了

SPF算法

设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组：

  • 第一组为已经求出最短路径的顶点集合，用S表示。

  • 第二组为其余未确定最短路径的顶点集合，用U表示。
    初始时，S中只有一个源点v，按最短路径长度的递增次序依次把U中的顶点加入S中，在加入过程中，总保持从源点v到S中的各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入S中，算法结束。

    算法步骤如下：

  • 初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
  • 从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
  • 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

  • 重复步骤b和c直到所有顶点都包含在S中。

    执行动画过程如下：


    ![](http://pic002.cnblogs.com/images/2012/426620/2012073019540660.gif)

内部路由选择协议

路由选择信息协议（RIP）

RIP作为最早的距离矢量型IP路由选择协议，是基于Bellman、Ford和Fulkerson开发的路由选择算法。当前，RIP存在两个版本:RIPv1,RIPv2. RIPv1为有类别路由选择协议； RIPv2为无类别路由选择协议。另外，RIPng协议为RIPv2协议为支持IPv6协议而设计的修订版本。

RIP协议的处理是通过UDP 520 端口来操作的。所有的RIP消息都被封装在UDP用户数据报协议中，源和目的端口字段的值被设置为520。

参考文献

Was this helpful?

0 / 0

发表回复 0