《高级网络概论》第02讲网络路由技术

《高级网络概论》第02讲网络路由技术第一页，共53页。主要内容网络路由技术原理常用路由协议RIPOSPFBGP路由器技术第二页，共53页。路由原理⑴第三页，共53页。路由Routing为各个网络间的数据交换寻找最佳路径为给定的IP报文提供到指定目的地的转发服务第四页，共53页。路径的多样性ABCDABAD－DBAC－CBAC－CD－DBAD－DC－CB第五页，共53页。①我强烈BS不守时！ABCD街道小街高速街道高速高速AC－CD－DB第六页，共53页。②走捷径是我的人生哲学！ABCDAB7Km3Km8Km5Km3Km6Km第七页，共53页。③远离堵车，我要低碳！ABCDAC－CB堵塞！堵塞！车流量大第八页，共53页。④虽然不差钱，节俭是本色！ABCDAD－DB50￥10￥免费免费免费30￥第九页，共53页。路由技术思想第十页，共53页。路由表｛目的网络地址；下一跳网关地址｝IP报文目的IP地址若匹配成功转发…………………………思考：经过路由器后，IP报文的源地址和目的地址如何变化？第十一页，共53页。全网路由与子网路由可采用A/B/C类地址、子网、超网、AS等技术劣优第十二页，共53页。自治系统AutonomousSystem－AS因特网将整个网络划分为许多较小的自治系统AS一个AS是一个相对独立的网络，其最重要的特点就是AS有权自主地决定在本系统内采用何种路由选择协议一个AS内的所有网络都属于一个行政单位（例如：一个公司、一所大学、一个国家等）来管辖一个AS的所有路由器在本自治系统内都必须是连通的许多小的AS可组成更大的AS第十三页，共53页。路由算法的度量Metric链路长度/跳数带宽/吞吐量/某时段内的通信流量保密要求传播时延/时延抖动缓存被占用的程度/队列长度链路差错率等第十四页，共53页。路由算法要求第十五页，共53页。路由算法分类静态路由StaticRouting动态路由DynamicRouting内部网关协议（InteriorGatewayProtocol，IGP）在AS内部范围使用，如：RIP、OSPF，实现域内路由选择（IntradomainRouting）外部网关协议（ExternalGatewayProtocol，EGP）在AS之间使用，如：BGP，实现域间路由选择（InterdomainRouting）第十六页，共53页。路由协议⑵第十七页，共53页。RIP路由信息协议RoutingInformationProtocolRFC1058（RIP2－RFC2453）基于距离矢量算法，通过计算抵达目的地的最少距离（跳数）来选取唯一的最佳路径如果路由器与网络直接连接，则定义距离为0，可以进行报文直接交付如果路由器经过n台路由器与目的网络间接连接，则定义距离为n最多为15跳，适用于小规模网络（小型AS）第十八页，共53页。路由信息路由器X网络N1网络N2网络N3X3X1X2路由器Y网络N4路由器ZY1Y2Z1Z2网络N5〔X路由表〕N1，0，－N2，0，－N3，0，－N4，1，Y1N5，1，Z1｛目的地址，距离度量，下一结点｝一跳（1hop）（经过一台路由器）创建和维护AS内到达每个网络的距离矢量直接交付第十九页，共53页。最短路径定理Bellman-Ford(Ford-Fulkerson)定理若X是A→B最短路径上的结点，则A→X和X→B都是最短路径AXB第二十页，共53页。RIP算法初始情况下，若结点（路由器）直接连接网络Ni，则记为〔Ni，0，－〕每隔一个固定周期（如30s）与且仅与相邻的路由器交换路由信息当一个结点收到来自相邻结点（设其地址为Xj）的RIP报文（其中包含了Xj的路由表）后，执行以下步骤：修改RIP报文中的所有记录项，将“下一结点”字段均改为Xj，并将所有“距离”字段的值加1（≤16）对修改后的每个记录项，分别执行以下步骤：若“目的网络”不在路由表中，则添加该记录项，返回；否则若“下一结点”也相同，则替换原记录项，返回；否则若“距离”值小于路由表中的值，则进行更新，返回结束若规定时间内未收到相邻结点更新路由信息，则记为不可达（距离值16）为什么？第二十一页，共53页。RIP示例初始路由表示例网络N1，0，－N2，0，－N3，0，－N4，1，CN5，1，BN1，1，AN2，1，AN3，0，－N5，0，－N6，1，EN1，0，－N2，1，AN3，1，AN4，0，－N6，1，FN1，1，AN2，0，－N3，1，AN4，0，－N6，1，FN3，1，BN4，1，FN5，0，－N6，0，－N1，1，CN2，1，DN4，0，－N5，1，EN6，0，－首次收到相邻的路由表并更新后最终收敛的路由表ABCDEFN1，0，－N2，0，－N3，0，－N3，0，－N5，0，－N1，0，－N4，0，－N2，0，－N4，0，－N5，0，－N6，0，－N4，0，－N6，0，－网络N3N1，0，－N2，0，－N3，0，－N4，1，CN5，1，BN6，2，BN1，1，AN2，1，AN3，0，－N4，2，AN5，0，－N6，1，EN1，0，－N2，1，AN3，1，AN4，0，－N5，2，AN6，1，FN1，1，AN2，0，－N3，1，AN4，0，－N5，2，AN6，1，FN1，2，BN2，2，BN3，1，BN4，1，FN5，0，－N6，0，－N1，1，CN2，1，DN3，2，CN4，0，－N5，1，EN6，0，－A网络N1网络N2C网络N4DB网络N5E网络N6FB→AN3，1，BN5，1，BC→AN1，1，CN4，1，CD→AN2，1，DN4，1，D第二十二页，共53页。故障引起的路由更新示例示例网络故障时路由表B设置为N5不可达ABCDEF网络N3N1，0，－N2，0，－N3，0，－N4，1，CN5，1，BN6，2，BN1，1，AN2，1，AN3，0，－N4，2，AN5,16,－N6，1，EN1，0，－N2，1，AN3，1，AN4，0，－N5，2，AN6，1，FN1，1，AN2，0，－N3，1，AN4，0，－N5，2，AN6，1，FN1，2，BN2，2，BN3，1，BN4，1，FN5，0，－N6，0，－N1，1，CN2，1，DN3，2，CN4，0，－N5，1，EN6，0，－A网络N1网络N2C网络N4DB网络N5E网络N6F中断！B传播A得知N5不可达N1，0，－N2，0，－N3，0，－N4，1，CN5,16,BN6，2，BN1，1，AN2，1，AN3，0，－N4，2，AN5,16,－N6，1，EN1，0，－N2，1，AN3，1，AN4，0，－N5，2，AN6，1，FN1，1，AN2，0，－N3，1，AN4，0，－N5，2，AN6，1，FN1，2，BN2，2，BN3，1，BN4，1，FN5，0，－N6，0，－N1，1，CN2，1，DN3，2，CN4，0，－N5，1，EN6，0，－A传播C和D得知N5不可达N1，0，－N2，0，－N3，0，－N4，1，CN5,16,BN6，2，BN1，1，AN2，1，AN3，0，－N4，2，AN5,16,－N6，1，EN1，0，－N2，1，AN3，1，AN4，0，－N5,16,AN6，1，FN1，1，AN2，0，－N3，1，AN4，0，－N5,16,AN6，1，FN1，2，BN2，2，BN3，1，BN4，1，FN5，0，－N6，0，－N1，1，CN2，1，DN3，2，CN4，0，－N5，1，EN6，0，－F传播C和D得知N5可达N1，0，－N2，0，－N3，0，－N4，1，CN5,16,BN6，2，BN1，1，AN2，1，AN3，0，－N4，2，AN5,16,－N6，1，EN1，0，－N2，1，AN3，1，AN4，0，－N5，2，FN6，1，FN1，1，AN2，0，－N3，1，AN4，0，－N5，2，FN6，1，FN1，2，BN2，2，BN3，1，BN4，1，FN5，0，－N6，0，－N1，1，CN2，1，DN3，2，CN4，0，－N5，1，EN6，0，－最终收敛的路由表N1，0，－N2，0，－N3，0，－N4，1，CN5，3，CN6，2，BN1，1，AN2，1，AN3，0，－N4，2，AN5，4，AN6，1，EN1，0，－N2，1，AN3，1，AN4，0，－N5，2，FN6，1，FN1，1，AN2，0，－N3，1，AN4，0，－N5，2，FN6，1，FN1，2，BN2，2，BN3，1，BN4，1，FN5，0，－N6，0，－N1，1，CN2，1，DN3，2，CN4，0，－N5，1，EN6，0，－第二十三页，共53页。极端情况引起路由振荡网络N3网络N1网络N2AB①A、B原有路由表→N1，0，－故障！N1，1，AN1，16，－②A发现故障，更新路由表→N1，2，B③B发送路由信息（A未到发布周期）④A更新路由表→N1，3，A⑤A发送路由信息←⑥B更新路由表……N1，16，BN1，16，AA、B最终路由表→收敛过程漫长，N1网络故障无法及时反映，引起路由振荡第二十四页，共53页。RIP协议采用UDP协议传输，端口号520RIP协议数据单元：←―――――――――――4byte――――――――――→bit0bit31命令版本号=20x000x004byte报头地址类别（2：IP）路由标记（AS号）20byte路由信息可重复25次网络地址子网掩码下一结点（下一跳路由器地址）距离值命令字段：1:请求路由信息2:响应或未请求主动发送路由信息网络号第二十五页，共53页。RIP特点和应用RIP简单而有效，成为路由信息交换的标准之一所有IP路由器均支持RIP协议RIP适合网络状况较单纯和可预测的中小型网络单纯的以跳数作为选路的依据不能充分描述路径特征，可能导致所选的路径不是最优Internet计算机或子网接入路由器（支持RIP）路由器（支持RIP）接入线路第二十六页，共53页。OSPF开放式最短路径优先协议OpenShortestPathFirstOSPF2－RFC2328采用分布式的链路状态协议（LinkStateProtocol）每台OSPF路由器维护一个全网一致的链路状态数据库（LinkStateDatabase），即网络拓扑结构图使用该数据库可构造一棵最短路径树来计算路由表改进RIP协议简单化所带来的缺陷具备安全鉴别功能第二十七页，共53页。链路状态描述路由器各条链路的状况——表示结点与哪些结点相邻到达各相邻结点的距离、时延、带宽、费用等度量（或代价）度量值可由网络管理员灵活设定当且仅当链路状态发生变化时，才会发送更新路由信息第二十八页，共53页。OSPF区域OSPF将一个自治系统划分为若干个区域（Area）为保障协议执行效率，一个区域内的路由器应少于200台路由器仅了解本区域的完整拓扑结构，不知道其他区域网络拓扑情况采用层次化的区域划分实现区域间的通信网络N1A区域网络N2B网络N4CDEFG自治系统其他自治系统网络N5网络N6网络N7网络N8网络N9HK区域主干区域区域主干路由器自治系统边界路由器区域边界路由器网络N3第二十九页，共53页。洪泛法Flooding路由器向所有相邻的路由器发送信息相邻路由器又向所有相邻路由器转发每台路由器都可收到其他路由器发出的路由信息副本，且只收到一次路由信息路由信息路由信息路由信息路由信息路由信息路由信息路由信息路由信息第三十页，共53页。最短路径算法Dijkstra最短路径算法（SPF）令D(v)为源结点a到结点v的距离（包括从a到v的某一路径中所有链路距离之和）；再令d(i，j)为结点i到j之间的距离。执行：令N为网络结点集合，令N={a}，对所有不在N中的结点v：寻找一个不在N中的结点w，其D(w)的值为最小，把w加入到N中。对所有不在N中的结点v：D(v)=min[D(v),D(w)+d(w,v)]重复步骤②，直到所有结点都在N中第三十一页，共53页。SPF算法示例abdcef5212331152aad1ade11abde211abdce2111abdcef21112目的下一跳距离

dd1ed2bb2cd3fd4(1)(3)(2)第三十二页，共53页。SPF算法示例abdcef5212331152aad1ade11abde211abdce2111abdcef21112目的下一跳距离

dd1ed2bb2cd3fd4(1)(3)(2)D(b)=2第（1）步D(d)=1D(e)=∞D(f)=∞D(c)=5D(e)=2D(e)=4第三十三页，共53页。SPF算法示例abdcef5212331152aad1ade11abde211abdce2111abdcef21112目的下一跳距离

dd1ed2bb2cd3fd4(1)(3)(2)D(b)=2第（2）步D(d)=1D(e)=2D(f)=∞D(c)=4D(f)=4D(f)=3第三十四页，共53页。SPF算法示例abdcef5212331152aad1ade11abde211abdce2111abdcef21112目的下一跳距离

dd1ed2bb2cd3fd4(1)(3)(2)D(b)=2第（3）步D(d)=1D(e)=2D(f)=4D(c)=3第三十五页，共53页。SPF算法示例abdcef5212331152aad1ade11abde211abdce2111abdcef21112目的下一跳距离

dd1ed2bb2cd3fd4(1)(3)(2)D(b)=2第（4）步D(d)=1D(e)=2D(f)=4D(c)=3第三十六页，共53页。SPF算法示例abdcef5212331152aad1ade11abde211abdce2111abdcef21112目的下一跳距离

dd1ed2bb2cd3fd4(1)(3)(2)D(b)=2第（5）步D(d)=1D(e)=2D(f)=4D(c)=3第三十七页，共53页。SPF分步计算表步骤ND(b)D(c)D(d)D(e)D(f)初始{a}251∞∞1{a,d}24(1)2∞2{a,d,e}23

(2)43{a,b,d,e}(2)3

44{a,b,c,d,e}

(3)

45{a,b,c,d,e,f}

(4)abdcef5212331152思考：如果把度量值都设为1，比较OSPF和RIP协议第三十八页，共53页。OSPF协议直接通过IP报文传送（IP协议字段值89）←―――――——―――――4byte――——―――――――→bit0bit31版本号=2类型报文总长度（byte）24byteOSPF报头发送方路由器的接口IP地址区域标识符校验字鉴别类型1:口令；0:N/A鉴别（8字符口令或全0）类型1～5报文的数据可变长数据字段OSPF报文类型：（1）类型1，问候（2）类型2，数据库描述（3）类型3，链路状态请求（4）类型4，链路状态更新（5）类型5，链路状态确认●每两个相邻结点每隔10s交换一次Hello（心跳信号）●采用数据库描述报文与相邻结点交换链路状态摘要信息，指出已有的信息（及其序号）●结点采用链路状态请求报文要求对方发送自己所缺少的链路状态项目的详细信息第三十九页，共53页。OSPF技术特点根据IP报文的不同ToS设置不同代价（1～65535）可计算不同的路由例如，高带宽的卫星链路，对文件传输业务可分配较低的代价，而对时延敏感的业务则可设定很高的代价最为常用的是以链路带宽为代价如果到达同一目的地有多条相同代价路径，可以把通信量均匀分配给这几条路径，获得负载平衡（LoadBalance）OSPF报文是可鉴别的，保障了路由信息交换的安全性OSPF支持VLS和CIDROSPF为每一个链路状态带上32bit序号，序号越大则状态越新，有利于协议机判别第四十页，共53页。BGP边界网关路由协议BorderGatewayProtocolBGP4－RFC1771和1772BGP使用TCP作为传输协议，端口号为179用于自治系统间的路由协议不同的AS具有各不相同的路由策略，无法采用一致的度量依据来构造穿越多个AS的最佳路径大规模的网络中情况十分复杂，要维持所有的链路状态非常困难，不仅路由表过于庞大，效率低下，且更新时间必然相当长BGP把每个AS看成一个整体，只负责为各AS需要送往其他AS的报文指出有效的路径，通向正确的目的地第四十一页，共53页。BGP算法设计原则允许使用多种路由选择策略，灵活应对各种互连需求，综合考虑技术、经济、安全、政治等因素尽力寻找一条较好的路由，而非所谓的最佳路由避免循环路由（回路）以CIDR为基础，支持路由信息的聚合和削减第四十二页，共53页。BGP技术概要以数据交换的可达性作为目标，采用路径矢量(PathVector)计算路由每个自治系统都要选择一台路由器作为BGP发言人(BGPSpeaker)，运行BGP协议，代表整个AS和其他AS交换路由信息两个互连的BGP路由器彼此称为对方的邻居(Neighbor)或对等体(Peer)对等体的连接有两种模式：IBGP－InternalBGPEBGP－ExternalBGP第四十三页，共53页。采用BGP互连AS示意图RAS1SSSSRRSSAS2AS3AS4AS5AS6RRSSRRouterAS7BGPSpeakerAS8IBGPEBGPEBGPOSPF第四十四页，共53页。BGP协议←―――――――――4byte―――――――――→bit0bit31BGP报头19byte鉴别标记报文总长度（2byte）类型1～4可变长度BGP数据

类型1：打开（Open）

类型2：更新（Update）

类型3：保活（Keep-Alive）类型4：通知（Notification）第四十五页，共53页。BGP、OSPF、RIP关系图主干网AS0国家网AS1国家网AS2地区网AS3地区网AS4地区网AS5地区网AS6地区网AS7城域网AS8城域网AS9城域网AS10城域网AS11城域网AS13园区网AS14城域网AS12园区网AS15园区网AS16园区网AS17园区网AS18园区网AS19InternetBGPBGPBGPBGPBGPBGPBGPBGPBGPBGPBGPBGPBGPBGPBGP