第6章路由算法.

第6章路由算法uyxwvz2213112535图:G=(N,E)N=路由器集合={u,v,w,x,y,z}E=链路集合={(u,v),(u,x),(v,x),(v,w),(x,w),(x,y),(w,y),(w,z),(y,z)}图抽象标注：图抽象在其它网络上下文中也十分有用例如:P2P,N是peer结点，E是TCP的连接图抽象：边的代价uyxwvz2213112535•c(x,x’)=链路的代价(x,x’)-e.g.,c(w,z)=5•代价可能总为１,或者是链路带宽的倒数,或者是拥塞情况的倒数Costofpath(x1,x2,x3,…,xp)=c(x1,x2)+c(x2,x3)+…+c(xp-1,xp)问题:结点ｕ到结点ｚ的最小代价路径是什么？路由算法:发现最小代价路径的算法路由:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源结点到目标结点的较好路径较好路径:按照某种指标较小的路径路由算法(routingalgorithm):网络层软件的一部分,完成路由功能路由的时机虚电路:在建立虚电路时使用(会话路由选择，sessionrouting)数据报:每个分组独立路由路由的概念汇集树(sinktree)一个结点的汇集树:所有其它结点到此结点的最优路径形成的树路由算法就是为所有路由器找到并使用汇集树最优化原则(optimalityprinciple)正确性(correctness)：算法必须正确和完整，使分组一站一站接力，正确发向目的站点简单性(simplicity)：在计算机上，算法的实现应该简单。最优但复杂的算法，时间延迟很大，不实用，不应为了获取路由信息而增加很多的通信量健壮性(robustness)：算法应适应通信量和网络拓扑的变化，不向很拥挤的链路发送数据，不向中断的链路发送数据稳定性(stability)：产生的路由不应该摇摆公平性(fairness)：对每一个站点都公平最优性(optimality)：某一个指标的最优（时间、费用或综合指标）。实际上，获取最优的结果代价较高，可以选择次优的结果路由算法的原则路由算法的分类自适应或者非自适应?非自适应算法(non-adaptivealgorithm)：不能适应网络拓扑和通信量的变化,路由表是事先计算好的，也叫静态路由算法和非自适应路由算法自适应算法(adaptivealgorithm)：能适应网络拓扑和通信量的变化，也叫动态路由算法和自适应路由算法固定路由算法（fixedroutingalgorithm）洪泛法（flooding）随机走动法（randomwalk）基于流量的路由算法（flow-basedrouting）非自适应路由算法每个网络结点存储一张表格，表格的每一项记录到达某个目的结点的下一结点或链路，而不是记录到该目的结点的所有中间结点优点：简单，适合一个负载稳定和拓扑变化不大的网络缺点：灵活性较差，无法对网络的拥塞和故障作出反应固定路由算法结点收到不是发给它的分组时，就将该分组的副本向除输入链路之外的所有与此结点相连的链路转发出去当网络的通信量很小时，该方法使分组的时延为最小，因为在并行发送的路由中，肯定有一条为最佳该方法的缺点是网络中的分组数目会迅速增加，导致网络出现拥塞现象，应用并不广泛该方法可用于健壮性要求很高的地方，如军事网络洪泛法随即徘徊法当分组到达某个结点时，随机选择一条链路作为转发的路由；当某结点的输出链路有3条时，就以平均概率0.33选择任一条链路作为转发路由当结点或链路发生故障时，该方法可使路由算法有较好的稳健性随机走动法该方法不仅考虑网络的拓扑结构，还要考虑网络的负载因素对某一给定的线路，如果已知负载量与平均流量，那么可以根据排队论的知识计算出该线路上的平均分组延迟由所有的线路平均延迟，可直接计算出流量的加权平均值，从而得到整个网络的平均分组延迟这样找出网络的最小平均延迟就可以实现最优路由选择基于流量的路由算法孤立路由选择集中路由选择分布式路由选择自适应路由算法每个结点并不利用其它结点来的网络信息，仅仅根据它自己所看到的情况来确定路由最短等待法逆向学习算法孤立路由选择根据所有结点的网络信息来选择路由网络中设置了一个路由控制中心每隔一段时间，每个结点向路由控制中心发送状态信息，如链路连接情况、流量和队列长度等路由控制中心收集所有这些信息，然后根据它对整个网络的全局性了解，利用这些信息使用最短路径算法计算出每对结点之间的最佳路径，构造出路由表分发给对应的每个结点缺点：计算量大和路由控制中心的脆弱性集中路由选择根据来自于相邻结点的信息，通过一个最短花费路由算法计算出到每个目的地的路由分布式路由算法得到了广泛使用目前最流行的两个分布式路由算法距离矢量路由算法（distancevectorrouting）•局部：路由器只知道与它有物理连接关系的邻居路由器和到该路由器的代价链路状态路由算法（linkstaterouting）•全局：所有的路由器拥有完整的拓扑和边的代价的信息分布式路由选择历史及应用情况由Bellman、Ford和Fulkerson等提出用于ARPANET，Internet和Novell基本思想每个结点都保存一张到目的地的路由表•到目的地的下一结点•测量出到目的地的度量值（metric）：初始化时，直接连接的目的地置为0（表示无需经过别的路由器），其它置为每个结点把它的路由表定期向它直接连接的相邻结点传递距离矢量路由算法当结点K从结点J接收一个更新消息后，它对到每个目的地的路由和距离度量进行检查•如果J知道一条到目的地的更短的路径，结点K更新该目的地对应的下一结点标识和距离度量•如果J列出了一个K还没有记录的某个目的地的路径，结点K会向表中增加一项•如果K记录的下一结点标识为J，并且J所报告的到目的地的距离改变了，也会更新路由表中的距离度量距离矢量路由算法算法表示初始化。对于每个结点G，对所有它直接连接的目的地N，路由表中的表项用三元组(N,G,0)来表示，即从结点G到目的地N无需经过转发结点G定期发送它的路由表给相邻结点。更新信息中对应着每一个目的地N用一个三元组来表示（N,V,D），即到目的地N的路由上的下一结点为V，G到N的距离为D距离矢量路由算法结点G收到G’送来的路由信息，对于更新信息中给出的每个目的地，在G的路由表中查找相对应的表项，设它为（N,V,D），而更新信息中的三元组为（N,V’,D’），C为结点G和G’之间的距离•如果找不到相应的表项，在G的路由表中增加一项：(N,G’,D’+C)•如果V=G’，G中路由表对应的表项根据D’+C和D的比较获得–如果D’+CD，G中表项更新为(N,G’,D’+C)–否则G中表项保持原状，仍为(N,V,D)距离矢量路由算法正确的算法如果找不到相应的表项，在G的路由表中增加一项：(N,G’,D’+C)如果V=G’，G中路由表对应的表项根据D’+C和D的比较获得–如果D’+CD，G中表项更新为(N,G’,D’+C)–否则G中表项保持原状，仍为(N,V,D)改为：如果找不到相应的表项，在G的路由表中增加一项：(N,G’,D’+C)如果V=G’，那么无条件的把G中的项目更新为G’中的(N,G’,D’+C)。如果V≠G’，G中路由表对应的表项根据D’+C和D的比较获得–如果D’+CD，G中表项更新为(N,G’,D’+C)–否则G中表项保持原状，仍为(N,V,D)该改为：如果V=G’，那么无条件的把G中的项目更新为G’。理由是：要以最新消息为准。见谢希仁第五版《计算机网络》148页距离矢量路由算法距离矢量路由算法路由器1的更新前的路由表路由器2发给路由器1的报文路由器1的更新后的路由表DV的无穷计算问题DV的特点•好消息传的快坏消息传的慢好消息的传播以每一个交换周期前进一个路由器的速度进行•好消息：某个路由器接入或有更短的路径•举例距离矢量路由算法DV的无穷计算问题坏消息的传播速度非常慢（无穷计算问题）例子•第一次交换之后，B从C处获得信息，C可以到达A(C-A,要经过B本身)，但是路径是2，因此B变成3，从C处走•第二次交换，C从B处获得消息，B可以到达A，路径为3。因此，C到A从B走，代价为4•无限此之后，到A的距离变成INF，不可达距离矢量路由算法LS的背景DV的问题•代价没有考虑线路带宽因素，认为所有线路带宽一样•慢速收敛问题（无穷计算问题）1979年后ARPANET的路由算法都转为LSLS的基本工作过程1.发现相邻结点，获知对方网络地址2.测量到相邻结点的的代价（延迟或开销）3.组装一个LS分组，描述它到相邻结点的代价情况4.将分组通过扩散的方法发到所有其它路由器5.通过Dijkstra算法找出最短路径链路状态路由算法1.发现相邻结点，获知对方网络地址一个路由器加电之后，向所有线路发送HELLO分组其它路由器收到HELLO分组，回送应答，在应答分组中告知自己的全局唯一的名字在LAN中，通过广播HELLO分组，获得其它路由器的信息链路状态路由算法2.测量到相邻结点的代价（延迟或开销）实测法，发送一个分组要求对方立即响应回送一个ECHO分组通过测量时间可以估算出延迟情况3.组装一个分组，描述相邻结点的情况发送者名称序号，年龄列表：给出它相邻结点，和它到相邻结点的延迟链路状态路由算法4.将分组通过扩展的方法发到所有其它路由器顺序号：用于控制无穷的扩散，每个路由器都记录（源路由器，顺序号），发现重复的或老的就不扩散•具体问题1：循环使用问题•具体问题2：路由器崩溃之后序号从0开始•具体问题3：序号出现错误解决问题的办法：年龄字段(age)•生成一个分组时，年龄字段不为0•每过一个时间段，AGE字段减1•AGE字段为0的分组将被抛弃链路状态路由算法5.通过Dijkstra算法找出最短路径路由器获得各站点LS分组和整个网络的拓扑通过Dijkstra算法计算出到其它各路由器的最短路径(汇集树)将计算结果记录到路由表中LS的应用情况OSPF协议，用于Internet上链路状态路由算法计算路由时，一般使用Dijkstra（迪杰斯特拉）算法Dijkstra算法为每条边赋予一个非负的权值，以两结点间路径权值的和作为该路径的距离在网络中，每个结点都要用Dijkstra算法计算出到其它各结点的最短路径，从而构造出该结点的路由表最短路径算法1543262213112535Dijkstra算法首先建立一个除源点外的所有结点的集合S，集合S保存尚未被删除的结点Dijkstra算法使用两个数组D和R，每个结点在这两个数组中都各有一项数组D的第i项存储从源点到结点i的最短距离数组R的第i项存储从源点到结点i路径上的下一站用Weight(i,j)作为从结点i到结点j的权值，如果从结点i到结点j没有边，则权值为无穷大(∞)最短路径算法随后，开始循环每次都从S中删除一个与源点之间有最短路径的结点u，然后检查从源点到仍然在S中并与u相邻的每个结点的距离如果从源点通过u到某结点的权值之和，比此前源点到该结点的最短距离小，则更新该值当所有结点都从S中删除后，就能计算出到每个结点的最短距离，同时也构造出路由表最短路径算法具体算法初始化集合S，为除源点外的所有结点。初始化数组D，如果从源点到v有边存在，则D(v)为该边的权值，否则为无穷大。初始化数组R，如果从源点到v有边存在，则R(v)=v，否则为0。While(集合S非空){从S中选一结点u，使D(u)最小；如果D(u)无穷大{错误，S中无路径存在，退出}把u从S中删除；最短路径算法对(u,v)为边的每个结点v{如果（v仍在S中）{C=D(u)+Weight(u,v);如果（CD(u)){R(v)=R(u);D(v)=C+1;}}}}最短路径算法用Dijkstra算法，计算从源点1到其它每个结点的最短距离和下一站路由表最短路径算法15