数据通讯与计算机网络讲义 22章.ppt

第22章 1 Chapter22 NetworkLayer Delivery 交付 Forwarding 转发 andRouting 路由 第22章 2 转发 将分组放置到通向目的地的路径上去 源端和路由器需要具有路由表 22 2Forwarding 转发 如何使路由表的查找更加有效 第22章 3 Routemethodvs next hopmethod 转发策略 第22章 4 Host specificversusnetwork specificmethod 第22章 5 Defaultmethod 第22章 6 ForwardingProcess 第22章 7 例22 1 MakearoutingtableforrouterR1 第22章 8 ShowtheforwardingprocessifapacketarrivesatR1inthefigurewiththedestinationaddress180 70 65 140 例22 2 140 10 10001100 2 192 10 11000000 2 由 26 与 11000000 2 10000000 2 不匹配于 140 10 10001100 2 128 10 10000000 2 由 25 与 10000000 2 10000000 2 匹配于 因此从m0转发 第22章 9 ShowtheforwardingprocessifapacketarrivesatR1inthefigurewiththedestinationaddress201 4 22 35 例22 3 35 10 00100011 2 第22章 10 ShowtheforwardingprocessifapacketarrivesatR1inthefigurewiththedestinationaddress18 24 32 78 例22 4 第22章 11 Addressaggregation 地址聚合 减少表项数 第22章 12 Longestmaskmatching 最长掩码匹配 200 10 11001000 2 思考 将一个网络划分成2个子网 地址数比例为1 3 如何划分 路由器的两个出口对应这两个子网 表项内容 第22章 13 例22 5 Hierarchicalrouting 层次路由 第22章 14 RoutingTable 使用该表项的主机数目 使用该表项已转发的分组数目 第22章 15 第22章 16 第22章 17 第22章 18 Directvs IndirectDelivery 在22 2后讲 22 1Delivery 交付 第22章 19 22 3UnicastRoutingProtocols 路由算法的分类 使用全局信息还是局部信息 全局信息 每个路由器获取整个网络的拓扑 连通性 和链路代价信息 广播 链路状态 算法 LinkStateRouting OSPF 局部信息 每个路由器仅从相邻节点获取代价信息 距离向量 算法 DistanceVectorRouting RIP 静态还是动态 静态 路由表配置后不被自动改变动态 根据网络状态自动修改路由表周期性修正根据链路代价变化而修正 第22章 20 链路 x x 的代价记为c x x 代价可以由时延 带宽 差错率 费用 转跳数等度量 路径 x1 x2 x3 xp 的代价 c x1 x2 c x2 x3 c xp 1 xp Q 在u到z之间的最小代价路径是哪条 路由算法 用于发现最小代价路径的算法 代价 cost 第22章 21 Autonomoussystems Intra andInterdomainRouting 第22章 22 第22章 23 距离向量算法 DistanceVectorRouting 定义 c x v x至相邻节点v的代价dx y x至y的最小代价路径的总代价则有 v是x的所有相邻节点 dx y min c x v dv y v Bellman Ford公式 动态规划 第22章 24 dx y 从x至y的最小代价估计c x v x至相邻节点v的代价节点x记录自本节点至所有其它节点y的距离向量估计Dx dx y y N 节点x接收来自相邻节点v的距离向量Dv dv y y N 节点x从相邻节点v接收到新的 距离向量 后 使用B F公式修正自身的距离向量Dx dx y y N 对于x的每一个目的节点y N dx y minv c x v dv y 取得最小值的邻节点v 是x至y路径上的 nexthop 距离向量算法描述 第22章 25 距离向量算法示例1 同步运算 u节点有三个相邻节点 v x w 已知dv z 5 dx z 3 dw z 3 du z min c u v dv z c u x dx z c u w dw z min 2 5 v 1 3 x 5 3 w 4 x u作为源节点 从u到z的最小代价路径的 下一站 是x 由B F公式 第22章 26 Distancevectorroutingtables 距离向量算法示例2 异步运算 第22章 27 Initializationoftablesindistancevectorrouting 第22章 28 由接收的距离向量修正路由表 第22章 29 Two nodeloopinstability ProblemofDistanceVectorRouting 解决措施 设置 代价 的最大值 如100 B向A发路由表之前 删去 next 为 A 的行 对 next A 的项 B向A发 x 使得A重置x表项的timer 但不修正cost值 第22章 30 Three nodeinstability A C B 直至cost 第22章 31 RIP协议 RoutingInformationProtocol RIP采用 距离向量法 RIP的 代价 为 转跳数 每段链路的代价为1 RIP的最大转跳数为15 第22章 32 RIPupdatingalgorithm 异步运算 第22章 33 Linkstaterouting 每个节点知道整个网络拓扑以及各链路代价每个节点将自身邻域的链路状态信息向全网广播所有节点具有相同的 图 每个节点以自身为根 计算从根到各个其它节点的最小代价路径 Dijkstra算法 经过k次迭代 得到至k个节点的最小代价路径 作出该节点的路由表 第22章 34 第22章 35 链路状态法建立路由表的步骤 四步 步骤1 生成 linkstatepacket LSP 含 nodeID neighbor cost seq live time 周期性或发现网络状态发生变化时 步骤2 FloodingLSPs 各节点仅转发新版本的LSP 步骤3 构造 最短路径树 p 36示例 步骤4 根据 最短路径树 生成路由表 P 37示例 第22章 36 步骤3 构造 最短路径树 第22章 37 RoutingtablefornodeA 步骤4 根据 最短路径树 生成路由表 第22章 38 OSPF OpenShortestPathFirst intra AS 协议链路状态算法LS报文的分发 广播 每个节点具有相同的网络拓扑图采用Dijkstra算法计算路由OSPF报文广播到本AS中的所有路由器 OSPF分组直接封装在IP分组中 安全性 所有OSPF报文均进行认证 防止非法信息修改路由表 允许使用多条相同代价的路径 RIP仅支持一条路径 对于每一条链路 支持多种代价度量 支持单播和组播 组播OSPF MOSPF 使用同单播OSPF一样的拓扑数据 在OSPF最佳树基础上 剪裁成 组成员 路径树 在大的地理范围 采用分层式OSPF area OSPF的 先进 特点 在RIP中不具有的 第22章 39 Areas 两级的层次结构 局部区域 骨干区域内部路由器之间的 Link state 广播仅在局部区域中 每个内部路由器具有所在区域内的详细拓扑信息 区域边界路由器 汇总 本区域中到各网络的路径代价 将此信息告知其它区域的 区域边界路由器 骨干路由器 在骨干区域范围内运行OSPF路由协议 广播 运算 边疆路由器 实现同其它自治系统的连接 网关 第22章 40 Typesoflinks 1 Point to pointlink 第22章 41 2 Transientlink 3 Stublink 第22章 42 虚拟链路 非真实相邻的两个路由器间的一条通路 人工配置为虚拟 相邻 实际可能通过若干个路由器 4 Virtuallink TypesofPackets linkstatepacket LSP 含 nodeID neighbor cost seq live time 真实路由器发送Designatedrouter发送Areaborderrouter发送给相邻areaAreaborderrouter发送给ASboundaryrouterASboundaryrouter发送给本AS 第22章 43 graphicalrepresentationinOSPF Designatedrouter 第22章 44 因特网的 inter AS 路由协议 BGP 为何 Intra AS 和 Inter AS 使用不同的路由策略 政策性原因规模原因性能原因 Pathvectorrouting BGP BorderGatewayProtocol 第22章 45 在边界路由器中的BGP协议实体的功能 从相邻AS获取其它网络的可达性信息 将上述可达性信息传递给本AS中的所有路由器 基于可达性信息以及其它 选路策略 确定至其它AS中网络的 好 路径 第22章 46 1 BGP的基本概念 BGP路由器基于半永久性TCP连接 port179 交换路由信息 BGP 会话 sessions 在3a和1c之间进行 eBGP 会话 AS3发送经AS3的可达性信息给AS1 1c使用 iBGP 会话来分发新的可达性信息给AS1中的所有路由器 1b使用1b到2a的 eBGP 会话传递可达性信息给AS2 当各个路由器获知新的可达路径信息后 在自身的转发表中建立新的表项 第22章 47 2 路径属性 每个自治系统有唯一的 自治系统号 ASN 传递的报文中包含若干BGP属性 两种重要的BGP属性 AS PATH BGP报文传递过程中经过的AS集合的列表 如 AS6 AS7 可检测 防止路径循环 NEXT HOP 为到达下一个AS BGP网关转发报文的出口IP地址 示例 1d根据到3a的 出口地址j 的最短路径 确定到子网x的路由表项 目的网络x 出端口k 第22章 48 3 BGP报文 BGP报文封装在TCP报文段中 BGP报文类型 四种 OPEN 在对等方之间建立TCP连接 并对发送方进行认证 UPDATE 传送新的路径信息 或去除旧的路径信息 KEEPALIVE 在不传递UPDATE报文期间 保持已建立的连接 或对OPEN报文作确认 NOTIFICATION 报告前三种报文的差错 4 BGP路径选择 路由器从BGP报文可获知到子网x的不止一条的路径 路由器要从中选择 去除准则 按优先级排序 本AS的政策性选择 偏好值设置 最短的AS路径 AS跳数 最近的 NEXT HOP 路由器 端口 其它准则 第22章 49 22 4MulticastRoutingProtocols Unicasting Unicast Multicast andBroadcast 第22章 50 Multicasting Broadcasting 第22章 51 Multicastingvs multipleunicasting EfficiencyDelay 第22章 52 Commonmulticastprotocols RPFRPBRPM 第22章 53 MOSPF source basedtree MulticastingOSPF link staterouting Thetreeispremade prepruned andreadytobeused D站为根算出的tree B站为根算出的tree 各站均以A站为根算出的tree 一对 源 组 产生一棵树 第22章 54 比较 OSPF eachrouteruseDijkstraalgorithmtocreatealeast costtreeinthattherouterastherootandtherestofroutersasnodesofthetree MOSPF eachrouteruseDijkstraalgorithmtocreatealeast costtreeinthatthesourceastherootandwiththerouteritselfasanodeinthetree eachroutercreatesexactlythesametreeforthesamesource grouppair 第22章 55 MOSPF在原OSPF协议基础上 增加了一种新的 linkstateupdate 报文 groupmembershipLSA 用于传递 路由器单播地址同路由器组播地址的关联信息 含有组成员主机的网络表示为作为组成员的 designatedrouter 由此 在组播树的LSDB中 用组成员 由同一的组播地址判定 的单播地址由Dijkstra算法计算出该组成员构成的least costtree 当组成员关系变化时 也发送上述报文 更新least costtree MOSPFisdata driven thefirsttimeaMOSPFrouterreceivesamulticastpacketwithagivensourceandgroupaddress theroutercalculatesthetree andsavedinthecachememoryforfutureuse 第22章 56 DVMRP source basedtree DistanceVectorMulticastRoutingProtocol RPF Reversepathforwarding a b a b SourceIP 入端口a SourceIP 入端口b Broadcasting 第22章 57 ProblemwithRPF RPFeliminatestheloopinthefloodingprocess InRPF therouterforwards broadcasts onlythepacketsthathavetraveledtheshortestpathfromthesourcetotherouter allothercopiesarediscarded 第22章 58 RPB Reversepathbroadcasting 对特定的源和组 各Net仅选择一个router作为该源和组的 指定的父路由器 RPBcreatesashortest pathbroadcasttreefromthesourcetoeachdestination Itguaranteesthateachdestinationreceivesoneandonlyonecopyofthepacket 第22章 59 RPM Reversepathmulticasting RPMaddspruningandgraftingtoRPBtocreateamulticastshortestpathtreethatsupportsdynamicmembershipchanges 第22章 60 CBT core basedtree Group sharedprotocol Formationofthetree 第22章 61 selectacenterrouterforthegroup core everyotherroutergetsunicastaddressofthecenterrouterroutersconnectedwiththenetworksinwhichtherearegroupmemberssend joinmessage tothecenterroutereachintermediateroute