第6章路由算法总结ppt课件.ppt

第6章 路由算法,图: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的连接,图抽象：边的代价,c(x,x)=链路的代价(x,x)-e.g.,c(w,z)=5 代价可能总为,或者是链路带宽的倒数,或者是拥塞情况的倒数,Cost of path(x1,x2,x3,xp)=c(x1,x2)+c(x2,x3)+c(xp-1,xp),问题:结点到结点的最小代价路径是什么？,路由算法:发现最小代价路径的算法,路由:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源结点到目标结点的较好路径较好路径:按照某种指标较小的路径路由算法(routing algorithm):网络层软件的一部分,完成路由功能路由的时机虚电路:在建立虚电路时使用(会话路由选择，session routing)数据报:每个分组独立路由,路由的概念,汇集树(sink tree)一个结点的汇集树:所有其它结点到此结点的最优路径形成的树路由算法就是为所有路由器找到并使用汇集树,最优化原则(optimality principle),正确性(correctness)：算法必须正确和完整，使分组一站一站接力，正确发向目的站点简单性(simplicity)：在计算机上，算法的实现应该简单。最优但复杂的算法，时间延迟很大，不实用，不应为了获取路由信息而增加很多的通信量健壮性(robustness)：算法应适应通信量和网络拓扑的变化，不向很拥挤的链路发送数据，不向中断的链路发送数据稳定性(stability)：产生的路由不应该摇摆公平性(fairness)：对每一个站点都公平最优性(optimality)：某一个指标的最优（时间、费用或综合指标）。实际上，获取最优的结果代价较高，可以选择次优的结果,路由算法的原则,路由算法的分类,自适应或者非自适应?非自适应算法(non-adaptive algorithm)：不能适应网络拓扑和通信量的变化,路由表是事先计算好的，也叫静态路由算法和非自适应路由算法自适应算法(adaptive algorithm)：能适应网络拓扑和通信量的变化，也叫动态路由算法和自适应路由算法,固定路由算法（fixed routing algorithm）洪泛法（flooding）随机走动法（random walk）基于流量的路由算法（flow-based routing）,非自适应路由算法,每个网络结点存储一张表格，表格的每一项记录到达某个目的结点的下一结点或链路，而不是记录到该目的结点的所有中间结点优点：简单，适合一个负载稳定和拓扑变化不大的网络缺点：灵活性较差，无法对网络的拥塞和故障作出反应,固定路由算法,结点收到不是发给它的分组时，就将该分组的副本向除输入链路之外的所有与此结点相连的链路转发出去当网络的通信量很小时，该方法使分组的时延为最小，因为在并行发送的路由中，肯定有一条为最佳该方法的缺点是网络中的分组数目会迅速增加，导致网络出现拥塞现象，应用并不广泛该方法可用于健壮性要求很高的地方，如军事网络,洪泛法,随即徘徊法当分组到达某个结点时，随机选择一条链路作为转发的路由；当某结点的输出链路有3条时，就以平均概率0.33选择任一条链路作为转发路由当结点或链路发生故障时，该方法可使路由算法有较好的稳健性,随机走动法,该方法不仅考虑网络的拓扑结构，还要考虑网络的负载因素对某一给定的线路，如果已知负载量与平均流量，那么可以根据排队论的知识计算出该线路上的平均分组延迟由所有的线路平均延迟，可直接计算出流量的加权平均值，从而得到整个网络的平均分组延迟这样找出网络的最小平均延迟就可以实现最优路由选择,基于流量的路由算法,孤立路由选择集中路由选择分布式路由选择,自适应路由算法,每个结点并不利用其它结点来的网络信息，仅仅根据它自己所看到的情况来确定路由最短等待法逆向学习算法,孤立路由选择,根据所有结点的网络信息来选择路由网络中设置了一个路由控制中心每隔一段时间，每个结点向路由控制中心发送状态信息，如链路连接情况、流量和队列长度等路由控制中心收集所有这些信息，然后根据它对整个网络的全局性了解，利用这些信息使用最短路径算法计算出每对结点之间的最佳路径，构造出路由表分发给对应的每个结点缺点：计算量大和路由控制中心的脆弱性,集中路由选择,根据来自于相邻结点的信息，通过一个最短花费路由算法计算出到每个目的地的路由分布式路由算法得到了广泛使用目前最流行的两个分布式路由算法距离矢量路由算法（distance vector routing）局部：路由器只知道与它有物理连接关系的邻居路由器和到该路由器的代价链路状态路由算法（link state routing）全局：所有的路由器拥有完整的拓扑和边的代价的信息,分布式路由选择,历史及应用情况由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)。如果VG，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的路由算法都转为LSLS的基本工作过程发现相邻结点，获知对方网络地址测量到相邻结点的的代价（延迟或开销）组装一个LS分组，描述它到相邻结点的代价情况将分组通过扩散的方法发到所有其它路由器通过Dijkstra算法找出最短路径,链路状态路由算法,发现相邻结点，获知对方网络地址一个路由器加电之后，向所有线路发送HELLO分组其它路由器收到HELLO分组，回送应答，在应答分组中告知自己的全局唯一的名字在LAN中，通过广播HELLO分组，获得其它路由器的信息,链路状态路由算法,测量到相邻结点的代价（延迟或开销）实测法，发送一个分组要求对方立即响应回送一个ECHO分组通过测量时间可以估算出延迟情况组装一个分组，描述相邻结点的情况发送者名称序号，年龄列表：给出它相邻结点，和它到相邻结点的延迟,链路状态路由算法,将分组通过扩展的方法发到所有其它路由器顺序号：用于控制无穷的扩散，每个路由器都记录（源路由器，顺序号），发现重复的或老的就不扩散具体问题1：循环使用问题具体问题2：路由器崩溃之后序号从0开始具体问题3：序号出现错误解决问题的办法：年龄字段(age)生成一个分组时，年龄字段不为0每过一个时间段，AGE字段减1AGE字段为0的分组将被抛弃,链路状态路由算法,通过Dijkstra算法找出最短路径路由器获得各站点LS分组和整个网络的拓扑通过Dijkstra算法计算出到其它各路由器的最短路径(汇集树)将计算结果记录到路由表中LS的应用情况OSPF协议，用于Internet上,链路状态路由算法,计算路由时，一般使用Dijkstra（迪杰斯特拉）算法Dijkstra算法为每条边赋予一个非负的权值，以两结点间路径权值的和作为该路径的距离在网络中，每个结点都要用Dijkstra算法计算出到其它各结点的最短路径，从而构造出该结点的路由表,最短路径算法,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);如果（C D(u)R(v)=R(u);D(v)=C+1;,最短路径算法,用Dijkstra算法，计算从源点1到其它每个结点的最短距离和下一站路由表,最短路径算法,初始化：S=2,3,4,5,6数组D（1到其它每个结点的最短距离）数组R（1到其它每个结点的下一站路由表）,最短路径算法,最短路径算法,最短路径算法,最短路径算法,链路状态路由算法,OSPF Development History,1987,1989,1991,1993,1995,1997,1999,OSPF Group formed,OSPFv1 published RFC 1131,OSPFv2 published RFC 1247,Becomes recommended,Cryptographic authentication,Point-to-multipoint interfaces,MOSPF,OSPFv2 update RFC 1583,CIDR,OSPFv2 update RFC 2178,OSPFv2 update RFC 2328,OSPFv3 RFC 2740,消息复杂度LS:有 n 结点，E 条链路，发送报文O(nE)个 DV:只和邻居交换信息收敛时间LS:O(n2)，算法需要O(nE)报文有可能震荡DV:收敛时间变化可能存在路由环路count-to-infinity 问题,健壮性:路由器发生故障会出现什么?LS:结点会通告不正确的链路代价DV:DV 结点可能通告不正确的路径代价每一个结点的路由表可能被其它结点使用,LS 和 DV 算法的比较,层次性路由,规模:有200M个目的主机不可能在路由表中存储全部的目的地路由器的路由表交换会淹没链路,自治管理internet=网间网每一个网络管理员可能希望控制自己网络内部的路由,我们前面讲的路由算法都比较理想化所有的路由器都是一样的 网络是平面的 实际的网络不是这样的,某个区域内的路由器集合，自治系统“autonomous systems”(AS)在同一个AS内的路由器运行相同的路由协议“intra-AS”routing protocol内部网关协议不同AS的路由器可能运行着不同的内部网关协议,网关路由器直接和其它AS的路由器有直接的链路相连,层次性路由,转发表由AS内部和AS间路由算法配置Intra-AS 设置AS内部的目标网络Inter-AS&Intra-As 设置AS外部目标网络,层次性路由,Inter-AS 任务,假设AS1 中的路由器收到了一个目标地址是AS1 外部的数据报路由器应该将它转发到其中的一个gateway routers中，但是是哪一个？,AS1 需要:获知哪一个目标可以通过AS2 到达，哪一个可以通过AS3 到达将这种可达性信息传播到AS1中的每一个路由器中inter-AS路由的工作!,Intra-AS and Inter-AS routing,Gateways:perform inter-AS routing amongst themselvesperform intra-AS routers with other routers in their AS,inter-AS,intra-AS routing in gateway A.c,network layer,link layer,physical layer,a,b,a,C,A,B,d,Host h2,Hosth1,Intra-AS routingwithin AS A,Intra-AS routingwithin AS B,Intra-AS and Inter-AS routing,Internet Routing Model,2 key features Dynamic routingIntra-and Inter-AS routing,AS=locus of admin controlInternet organized as“autonomous systems”(AS)AS is internally connectedInterior Gateway Protocols(IGPs)within AS.Eg:RIP,OSPFExterior Gateway Protocols(EGPs)for AS to AS routing.Eg:EGP,BGP-4,BGP Development History,1989:BGP-1 RFC 1105Replacement for EGP(1984,RFC 904)1990:BGP-2 RFC 11631991:BGP-3 RFC 12671995:BGP-4 RFC 1771 Support for Classless Interdomain Routing(CIDR),