《域内路由收敛问题》由会员分享，可在线阅读，更多相关《域内路由收敛问题（28页珍藏版）》请在金锄头文库上搜索。
1、IntradomainIntradomain Routing Convergence Routing Convergence大纲 Routing-protocol convergence 针对链路失效采取的步骤 对数据分组的影响 Intradomain routing protocols 使路由收敛的步骤 实现开销和定时器 降低收敛过程的负面影响的一些现实办法 Multiple shortest paths between routers 将预定需要维护的链路的代价升高(到一个很大的 值),使得它不会出现在任何路由器间的最短路之上Routing Convergence (路由收敛) 唯一永恒的
2、是变化 设备失效, 或新设备的引入 路由协议配置的变化 预定的网络维护 自适应路由协议 变化检测 扩散(控制)消息 以将”变化”扩散出去 计算新的路径 更新转发表(forwarding tables)一次失效(failure)之后的收敛过程涉及到的因素 Failure detection Router recognizes an incident link has failed Failure notification Router informs other routers about the change Path re-computation Routers compute new pa
3、ths avoiding the link Forwarding-table update Routers update their forwarding tables Data traffic starts to flow over the new pathRouting convergenceForwarding convergence路由收敛过程中可能发生的坏事 瞬间不协调性 不同路由器可能对网络存在不同的看法 不同路由器的分组转发决断可能是不一致的 对数据流的效果 黑洞: 分组丢失 环路: 分组走入到一个环路之上 延迟: 分组走在一个非常长的路径之上 乱序: 新的分组可能先于就的分组到
4、达 希望最小化路由收敛时延 尤其是对数据流的影响Example: 黑洞引起分组丢失 路由器向”死”链路上转发分组 因为它还不知道该链路已经”死”了 或者, 还没有完成新的路由表计算丢弃sd幸运的是, IP网络只承诺了 “尽力传送”!Example: 转发环路 路由器的决定不一致 One router acting on old information Another router acting on new informationsxdabLoop!Intradomain Routing ConvergenceInterior Gateway Protocols (IGPs) (内部网关协议)
5、 一个执行 OSPF 或 IS-IS协议的路由器: 泛洪链路状态公告 (Flood link-state advertisements (LSAs) Compute shortest paths from link weights Determine “next hop” to other routers3221131453Knowing a Link is Dead: Heart-Beats Periodic “hello” packets (hello_interval, 10sec) Timeout if not received (dead_interval, 40 sec) Decl
6、are failure and flood the info to others Small values lead to faster detection, but also: Higher bandwidth consumption for “hellos” False detection during congestion interval False detection if router CPU falls a little behind hellohelloKnowing the Link is Dead: Interface Support Smart interface har
7、dware (智能接口硬件) Detects loss of connectivity at lower layer Interrupts the router CPU about the failure 这在IP over SDH体系结构中是常见的一种检测技术 E.g. Sprint白皮书规定了100 msec的 But Some media dont support it (e.g., Ethernet, ATM) so, you often need heartbeats anyway Also, want heartbeats to detect failures, the hardw
8、are cannot detect on its ownFlooding the Link-State Advertisement After detecting the failure Router sends LSA out each link Each router does the same and so on Flooding delay (CPU delay at each hop) * (diameter of the network)Computing the Shortest Paths Each router re-computes Shortest-path tree r
9、ooted at router G Determine next-hop to every other routerABD CEFIGHJ1 111121321111ABD CEFIGHJ111121111Reducing the Computational Overhead Good system Fast processor High-speed memory Good algorithms Traditional approach computes from scratch Incremental algorithms compute only the changes Especiall
10、y nice if only one edge changes Pre-computation Pre-compute effects of certain failure scenarios E.g., all single-link or single-router failuresUpdating the Forwarding Table Forwarding table Map destination prefix to outgoing link(s) Copy of table on each interface card Highly optimized for fast loo
11、kups Updating the forwarding table Computing the new forwarding table Making updates to the copy of the line card Important source of delay Sprint end-to-end study: around 1 second AT&T router-level study: 100 msec 300 msecAll Together: Looking Inside the RouterRoute Processor (CPU)FIBInterface card
12、Interface cardForwardingSwitching FabricData packetData packetTopology ViewSPF CalculationOSPF ProcessLSALS AckLSAForwardingLSA ProcessingLSA FloodingSPF CalculationFIB UpdateSignificance of Protocol Timers Hello and dead intervals Failure-detection delay vs. false diagnosis Pacing the link-state ad
13、vertisements Combining LSAs vs. longer convergence delay Some routers wait till after re-running Dijkstra! Delaying start of shortest-path computation ( 推迟最短路径的计算) Reducing # computations vs. convergence delay Especially useful if failure affects multiple links (当 多链路同时失效时特别有效)Operational PracticesR
14、educing the Effects of Convergence Long convergence delay is bad Transient problems with loss and delay Disruptive for VoIP and online gaming Solution #1: better equipment Interfaces that detect failures automatically Cranking down the values of the timers Faster CPUs and path-computation algorithms
15、 Solution #2: network design and operation Improve forwarding-plane convergence Improve convergence during maintenanceEqual-Cost Multi-Path (ECMP) Multiple shortest paths Router can compute multiple shortest paths Forwarding table has multiple outgoing links Router splits traffic evenly over the links3221131353xy aECMP Reduces Forwarding-Plane Convergence Suppose one of the outgoing link fails Incident router detects the failure Quick recomputation of paths without this link Local forwarding table updated to use other link Other routers have no forwarding-table
