第5章路由器与路由算法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 路由器与路由算法,路由器的结构,路由算法,算法的分类,距离矢量算法,链路状态算法,移动路由算法,.,第五章 路由器与路由算法路由器的结构.,1,5.1 路由器概述,局域网（LAN）和拨号用户需要通过路由器接入因特网,因特网的通信子网由各种路由器互连而成,路由器是上网的“必由之路”,5.1.1 路由器在因特网中的地位,.,5.1 路由器概述局域网（LAN）和拨号用户需要通过路由器,2,5.1.2 路由器结构概述,路由器的两个关键功能：,运行路由算法/协议(RIP，OSPF，BGP),交换,分组于输入链路到输出链路之间,.,5.1.2 路由器结构概述路由器的两个关键功能：.,3,输入端口功能,分散化的交换：,按照给出的分组信宿，使用输入端口的内存中存储的路由选择表，查找输出端口,目标:以“线路速度”完成输入端口的处理,排队:假如分组到达的数度快于转发到交换网络的（switch fabric）速度时缓存,物理层,：,位流级的接收,数据链路层：,e.g.,Ethernet,.,输入端口功能分散化的交换：物理层：数据链路层：.,4,三类交换网络,.,三类交换网络.,5,内存交换（Switching Via Memory）,第一代路由器:,分组通过系统的（单个）CPU拷贝,速度受到内存带宽的限制(每个分组需2次穿越系统总线),Input,Port,Output,Port,Memory,System Bus,.,内存交换（Switching Via Memory）第一代路,6,总线交换（Switching Via Bus）,分组通过一条共享的总线从输入端口的内存传递到输出端口的内存,总线竞争：,交换速率受限于总线的带宽,1 Gb/s总线，Cisco 1900：对访问接入和企业级的路由器已经足够(但还不适应在区域或主干级线路上使用),.,总线交换（Switching Via Bus）分组通过一条共,7,通过内联网络交换,（Switching Via An Interconnection Network）,克服了总线带宽的限制,Banyan networks，内联网络技术在发展初期是用来连接多处理器系统中的处理器,设计先进：把分组分割成固定长度的单元,再把这些单元送入交换网络,Cisco 12000：通过内联网络交换速度可达若干Gb/s,.,通过内联网络交换（Switching Via An Inte,8,输出端口的功能,缓存：,当来自交换网络的分组到达速度高于传输速率时，需要进行缓存,调度原则：,从队列中的分组中选择传输,.,输出端口的功能缓存：当来自交换网络的分组到达速度高于传输速率,9,路由选择算法抽象:,图中的结点是路由器,图中的线条为物理链路,链路成本：延迟，费用￥，或拥塞的程度,目标:,在收发双方的通信过程中为分组（所经由的一系列路由器中）确定一条“好”的路径,路由选择协议,A,E,D,C,B,F,2,2,1,3,1,1,2,5,3,5,“好”路:,一般为费用最低的路径,也可以另行定义,5.2路由算法,.,路由选择算法抽象:目标:在收发双方的通信过程中为分组（所经,10,路由算法是网络层软件的一部分,通信子网采用数据报分组交换方式，每个包都要做路由选择；,通信子网采用虚电路分组交换方式，只需在建立连接时做一次路由选择。,路由算法应具有的特性,正确性（correctness）,简单性（simplicity）,健壮性（robustness）,稳定性（stability）,公平性（fairness）,最优性（optimality）,5.2.1 路由算法应具有的特性,.,路由算法是网络层软件的一部分5.2.1 路由算法应具有的特性,11,5.2.2 路由算法分类,全局或分散的信息?,全局:,所有路由器都有完整的拓扑逻辑，链路成本信息,LS(Link State)算法,分散:,路由器只了解物理上邻接的路由器，了解到达这些路由器的链路成本,DV(Distance Vector)算法,静态或动态的?,静态:,路由变化较少的情况,动态:,路由变化较快的情况,定期更新,为了响应链路成本的变化,.,5.2.2 路由算法分类全局或分散的信息?静态或动态的?.,12,静态路由,由管理员手工配置。在网络结构简单、到目标点只有一条路径的网络中，只配置静态路由就可正常工作。,无自适应功能。当网络出现问题或因其他原因引起拓扑变化时，静态路由不会自动发生改变，必须要有网络管理员的介入。,路由算法简单。,动态路由,路由器根据给定的路由算法，通过自学习，构造路由表。,具有自适应功能。,算法比较复杂。,.,静态路由.,13,5.2.3 Internet路由表,端口1,端口2,端口1,端口2,端口1,端口2,128.2.0.0,128.1.0.0,128.3.0.0,128.4.0.0,128.1.0.2,128.2.0.2,128.2.0.3,128.3.0.2,128.3.0.3,128.4.0.2,路由器A,路由器B,路由器C,.,5.2.3 Internet路由表端口1端口2端口1端口2端,14,目的网络号,下一个转发路由器端口或IP地址,度量（转发次数）,128.1.0.0,直接端口1,0,128.2.0.0,直接端口2,0,128.3.0.0,128.2.0.3（RB）,1,128.4.0.0,128.2.0.3（RB）,2,目的网络号,下一个转发路由器端口或IP地址,度量（转发次数）,128.1.0.0,128.2.0.2（RA）,1,128.2.0.0,直接端口1,0,128.3.0.0,直接端口2,0,128.4.0.0,128.3.0.3（RC）,1,目的网络号,下一个转发路由器端口或IP地址,度量（转发次数）,128.1.0.0,128.3.0.2（RB）,2,128.2.0.0,128.3.0.2（RB）,1,128.3.0.0,直接端口1,0,128.4.0.0,直接端口2,0,路由器A的路由表,路由器B的路由表,路由器C的路由表,.,目的网络号下一个转发路由器端口或IP地址度量（转发次数）12,15,.,.,16,Internet 路由表包含内容,目的或网络掩码,协议,优先级,优先权,下一跳地址,输出接口,影响路由权的属性，如右图。越小，路径越好。,带宽,时延,负载,可靠性,跳数,开销,.,Internet 路由表包含内容目的或网络掩码带宽.,17,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,.,Internet路由协议路由协议或路由种类优先级缺省值路由算,18,5.2.4 最短路径路由算法,属于静态路由算法,基本思想,构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。,测量路径长度的方法,结点数量,地理距离,传输延迟,距离、信道带宽等参数的加权函数,计算方法：Dijkstra,算法,A,E,D,C,B,F,2,2,1,3,1,1,2,5,3,5,.,5.2.4 最短路径路由算法属于静态路由算法AEDCBF22,19,5.2.5 洪泛算法（Flooding）,属于静态路由算法,基本思想,把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。,主要问题,洪泛要产生大量重复包。,解决措施,每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包；,记录包经过的路径,.,5.2.5 洪泛算法（Flooding）属于静态路由算法,20,选择性洪泛算法（selective flooding）,基本思想,洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上；或者按一定的概率选择发送。,应用情况,对路由器和线路的资源过于浪费，实际很少直接采用；,具有极好的健壮性，可用于军事应用；,作为衡量标准评价其它路由算法。,.,选择性洪泛算法（selective flooding）基本思,21,5.2.6 基于流量的路由算法（Flow-Based Routing）,属于静态路由算法,基本思想,既考虑拓扑结构，又兼顾网络负荷；,前提：每对结点间平均数据流是相对稳定和可预测的；,根据网络带宽和平均流量，可得出平均包延迟，因此,路由选择问题归结为找产生网络最小延迟的路由选择算法,。,提前离线（off-line）计算。,.,5.2.6 基于流量的路由算法（Flow-Based Ro,22,需要预知的信息,网络拓扑结构；,通信量矩阵F,ij,；,线路带宽矩阵C,ij,；,路由算法（可能是临时的）。,.,需要预知的信息.,23,.,.,24,1/,=800 bits,根据排队论，平均延迟 T=1/(C-),.,1/=800 bits.,25,5.2.7 距离矢量路由算法（Distance Vector Routing）,属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP协议采用。,基本思想,每个路由器维护一张表，表中给出了到每个目的地的已知,最佳距离,和,线路,，并通过与,相邻路由器,交换距离信息来更新表；,.,5.2.7 距离矢量路由算法（Distance Vecto,26,每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；,邻居结点X发来的表中，X到路由器i的距离为Xi，,本路由器到X的距离为m，则路由器经过X到i的距离为Xi+m。根据不同邻居发来的信息，计算Xi+m，并取最小值，更新本路由器的路由表；,注意：本路由器中的老路由表在计算中不被使用,.,每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离,27,.,.,28,5.2.8 链路状态路由算法（Link State Routing）,距离向量路由算法的主要问题,选择路由时，没有考虑线路带宽；,路由收敛速度慢。,链路状态路由算法,发现邻居结点，并学习它们的网络地址,路由器启动后，通过发送HELLO包发现邻居结点,两个或多个路由器连在一个LAN时，引入人工结点,.,5.2.8 链路状态路由算法（Link State Rout,29,.,.,30,测量到每个邻居结点的延迟或开销,一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。,将所有学习到的内容封装成一个包,包以发送方的标识符开头，后面是序号、寿命和一个邻居结点列表；,列表中对应每个邻居结点，都有发送方到它们的延迟或开销；,链路状态包定期创建或发生重大事件时创建。,.,测量到每个邻居结点的延迟或开销.,31,.,.,32,将这个包发送给所有其它路由器,基本思想：,洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对(源路由器，序号)，当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；,存在的问题与改进,序号循环使用会混淆，解决办法：使用32位序号；,路由器崩溃后，序号重置；,序号出错；,.,将这个包发送给所有其它路由器.,33,第二、三问题的解决办法：增加年龄（age）域，每秒钟年龄减1，为零则丢弃。,链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；,链路状态包需要应答；,计算到每个其它路由器的最短路径,根据Dijkstra算法计算最短路径,实用协议,OSPF,IS-IS,.,第二、三问题的解决办法：增加年龄（age）域，每秒钟年龄减1,34,5.2.9 链路状态算法（LS）和距离向量算法（DV）的比较,算法复杂性,LS,路由信息向全网发送,N节点，E个连接的情况下，每个节点发送O(nE)的报文,DV,仅在邻居节点之间交换,.,5.2.9 链路状态算法（LS）和距离向量算法（DV）的比较,35,收敛（Convergence）速度,LS,使用最短路径优先算法，算法复杂度为O(n*2),n个结点（不包括源结点），需要n*(n+1)/2 次比较,使用更有效的实现方法，算法复杂度可以达到O(nlogn),可能存在路由振荡（oscillations）,（研究热点问题）,DV,收敛时间不定,可能会出现路由循环,count-to-infinity问题,.,收敛（Convergence）速度.,36,健壮性:如果路由器不能正常工作会发生什么?,LS,结点会广播错误的链路开销,每个结点只计算自己的路由表,DV,结点会广播错误的路径开销,每个结点的路由表被别的结点使用，错误会传播到全网,.,健壮性:如果路由器不能正常工作会发生什么?.,37,