Internet网络层协议设计

Transcription

1 路由器结构及路由协议

2 << 上一页 2 下一页 >> OUTLINE 网络层服务 网络路由基本原理 层次化路由体系结构 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

3 << 上一页 3 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 IP 协议简介 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

4 << 上一页 4 下一页 >> Network layer functions transport packet from sending to receiving hosts network layer protocols in every host, router three important functions: path determination: route taken by packets from source to dest. Routing algorithms forwarding: move packets from router s input to appropriate router output call setup: some network architectures require router call setup along path before data flows application transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical

5 Routing and Forwarding Default to upstream router A D R R1 R4 << 上一页 5 下一页 >> R R2 B R5 E R3 R Net Forwarding: determine next hop Routing: find end-to-end paths A B C D E default C Nxt Hop Net R1 Direct R3 R1 R3 R1 A B C D E default Nxt Hop R4 R3 R3 R4 Direct R4 Net A B C D E default Nxt Hop R2 R2 Direct R5 R5 R2

6 << 上一页 6 下一页 >> Network service model service abstraction Q: What service model for channel transporting packets from sender to receiver? guaranteed bandwidth? preservation of interpacket timing (no jitter)? loss-free delivery? in-order delivery? congestion feedback to sender? The most important abstraction provided by network layer:??? virtual circuit or datagram?

7 Virtual circuits source-to-dest path behaves much like telephone circuit performance-wise network actions along source-to-dest path call setup for each call before data can flow each packet carries VC identifier (not destination host ID) every router on source-dest path maintains state for each passing connection link, router resources (bandwidth, buffers) may be allocated to VC << 上一页 7 下一页 >>

8 << 上一页 8 下一页 >> Virtual circuits: signaling protocols used to setup, maintain, teardown VC used in ATM, frame-relay, X.25 not used in today s Internet application transport network data link physical 5. Data flow begins 6. Receive data 4. Call connected 3. Accept call 1. Initiate call 2. incoming call application transport network data link physical

9 << 上一页 9 下一页 >> Datagram networks: the Internet model no call setup at network layer routers: no state about end-to-end packets forwarded using destination host address application transport network data link physical 1. Send data 2. Receive data application transport network data link physical

10 Datagram or VC network: why? Internet data exchange among computers elastic service, no strict timing req. smart end systems (computers) can adapt, perform control, error recovery simple inside network, complexity at edge many link types different characteristics uniform service difficult ATM evolved from telephony human conversation: strict timing, reliability requirements need for guaranteed service dumb end systems telephones complexity inside network << 上一页 10 下一页 >>

11 << 上一页 11 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

12 << 上一页 12 下一页 >> Structure of Router Router must complete three basic functions(rfc1812) 1. Routing building up the routing table by routing algorithms 2.Route Lookup giving the best choice for next hop by matching the route in the routing table 3. Forwarding switching the packet from input to output interface

13 << 上一页 13 下一页 >> Structure of Router 网络接口 完成网络报文的接收和发送 转发引擎 负责决定报文的转发路径 内部交换 为多个网络接口以及路由引擎模块之间的报文数据传送提供高速的数据通路 路由引擎 由运行高层协议 ( 特别是路由协议 ) 的内部处理模块组成 路由表 包含完成网络报文正确转发的路由信息 承上启下

14 << 上一页 14 下一页 >> Structure of Router 控制路径 (Control Path) 网络接口 (Interface) 路由引擎 (Routing Engine) 路由更新 (Update) 路由表 (Routing Table) 路由查找 (Search) 转发引擎 (Forwarding Engine) 内部交换 (Switching) 数据路径 (Data Path) 控制路径 (Control Path) 网络接口 (Interface) 路由器提供了两种不同的报文处理路径 数据路径 : 处理目的地址不是本路由器而需要转发的报文 是整个路由器的关键路径, 它直接影响路由器的整体性能 控制路径 : 处理目的地址是本路由器的高层协议报文 主要是各种路由协议报文和管理报文 虽然控制路径不是路由器的关键路径, 但是它负责完成路由信息的交互, 从而保证了数据路径上的报文沿着最优的路径转发

15 What does router look like? << 上一页 15 下一页 >>

16 << 上一页 16 下一页 >> Before We Go Any Further Usually, IP ROUTING PROTOCOLS DO NOT DYNAMICALLY ROUTE AROUND NETWORK CONGESTION IP traffic can be very bursty Dynamic adjustments in routing typically operate more slowly than fluctuations in traffic load Dynamically adapting routing to account for traffic load can lead to wild, unstable oscillations of routing system

17 Routing Routing protocol Goal: determine good path (sequence of routers) thru network from source to dest. Graph abstraction for routing algorithms: graph nodes are routers graph edges are physical links link cost: delay, $ cost, or congestion level A B D 2 C E good path: typically means minimum cost path F << 上一页 17 下一页 >>

18 << 上一页 18 下一页 >> Routing Algorithm Classification Global or decentralized information? Global: all routers have complete topology, link cost info link state algorithms Decentralized: router knows physically-connected neighbors, link costs to neighbors iterative process of computation, exchange of info with neighbors distance vector algorithms

19 Routing Algorithm Classification Static or dynamic? Static: routes change slowly over time Dynamic: routes change more quickly periodic update in response to link cost changes << 上一页 19 下一页 >>

20 A Link-State Routing Algorithm Dijkstra s algorithm net topology, link costs known to all nodes accomplished via link state broadcast all nodes have same info computes least cost paths from one node ( source ) to all other nodes gives routing table for that node iterative: after k iterations, know least cost path to k destinations Idea: at each iteration increase spanning tree by the node that has least cost path to it A B D C E F << 上一页 20 下一页 >>

21 A Link-State Routing Algorithm Notation: c(i,j): link cost from node i to j. cost infinite if not direct neighbors D(v): current value of cost of path from source to dest. V p(v): predecessor node along path from source to v N: set of nodes already in spanning tree (least cost path known) Examples: c(b,c) = 3 D(E) = 2 p(b) = A N = { A, B, D, E } 2 A B 2 3 D E 1 C F << 上一页 21 下一页 >>

22 << 上一页 22 下一页 >> Dijsktra s Algorithm 1 Initialization: 2 N = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(a,v) 6 else D(v) = infinity 7 8 Loop 9 find w not in N and D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w which not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N

23 << 上一页 23 下一页 >> Dijkstra s algorithm: example Step N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F) A 2,A 5,A 1,A infinity,- infinity,- AD 2,A 4,D 1,A 2,D infinity,- ADE 2,A 3,E 1,A 2,D 4,E ADEB 2,A 3,E 1,A 2,D 4,E ADEBC 2,A 3,E 1,A 2,D 4,E ADEBCF 2,A 3,E 1,A 2,D 4,E 5 2 A 1 B 2 D C E F

24 Spanning tree gives routing table Step N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F) ADEBCF 2,A 3,E 1,A 2,D 4,E Result from Dijkstra s algorithm Routing table: destination B C D E Outgoing link to use, cost B,2 D,3 D,1 D,2 2 A 1 5 B 2 D C E F F << 上一页 24 下一页 >> D,4

25 << 上一页 25 下一页 >> Dijkstra s algorithm performance Algorithm complexity (n nodes and l links) Computation n iterations each iteration: need to check all nodes, w, not in N n*(n+1)/2 comparisons: O(n 2 ) more efficient implementations possible: O(n log n) Messages network topology and link cost known to all nodes each node broadcasts its direct link cost O(l) messages per broadcast announcement O(n l)

26 Distance Vector Routing Algorithm iterative: continues until no nodes exchange info self-terminating: no signal to stop asynchronous: nodes need not exchange info/iterate in lock step! distributed: each node communicates only with directly-attached neighbors Distance Table data structure each node has its own row for each possible destination column for each directlyattached neighbor to node example: in node X, for dest. Y via neighbor Z: X D (Y,Z) = = distance from X to Y, via Z as next hop Z c(x,z) + min {D (Y,w)} w << 上一页 26 下一页 >>

27 << 上一页 27 下一页 >> Distance Table: example A 1 7 E D (C,D) E D (A,D) E D (A,B) B E C D D = c(e,d) + min {D (C,w)} w = 2+2 = 4 D = c(e,d) + min {D (A,w)} w = 2+3 = 5 loop! 2 B c(e,b) + min {D (A,w)} w = = 8+6 = 14 loop! destination E D () A B C D cost to destination via A B D

28 << 上一页 28 下一页 >> Distance table gives routing table E D () cost to destination via A B D E Outgoing link to use, cost A A A,1 destination B C destination B C D,5 D,4 D D D,2 Distance table Routing table

29 Distance Vector Routing: overview Iterative, asynchronous: each local iteration triggered by: local link cost change message from neighbor: its least cost path change from neighbor Distributed: each node notifies neighbors only when its least cost path to any destination changes neighbors then notify their neighbors if necessary Each node: wait for (change in local link cost of msg from neighbor) recompute distance table if least cost path to any dest has changed, notify neighbors << 上一页 29 下一页 >>

30 << 上一页 30 下一页 >> Distance Vector Algorithm: At all nodes, X: 1 Initialization: 2 for all adjacent nodes v: 3 D X(*,v) = infinity /* the * operator means "for all rows" */ X 4 D (v,v) = c(x,v) 5 for all destinations, y X 6 send min D (y,w) to each neighbor /* w over all X's neighbors */ w

31 Distance Vector Algorithm (cont.): 8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 if (c(x,v) changes by d) 13 /* change cost to all dest's via neighbor v by d */ 14 /* note: d could be positive or negative */ 15 for all destinations y: D X(y,V) = D X(y,V) + d else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its min wd V (Y,w) */ 20 /* call this received new value is "newval" */ 21 for the single destination y: D X(Y,V) = c(x,v) + newval if we have a new min D X w (Y,w) for any destination Y 24 send new value of min D X (Y,w) to all neighbors w 25 forever << 上一页 31 下一页 >>

32 << 上一页 32 下一页 >> Distance Vector Algorithm: example X 2 Y 7 1 Z X D (Y,Z) X D (Z,Y) Z = c(x,z) + min {D (Y,w)} w = 7+1 = 8 Y = c(x,y) + min {D (Z,w)} w = 2+1 = 3

33 << 上一页 33 下一页 >> Distance Vector: link cost changes Link cost changes: node detects local link cost change updates distance table (line 15) if cost change in least cost path, notify neighbors (lines 23,24) good news travels fast 1 X 4 Y 50 1 Z algorithm terminates

34 Distance Vector: link cost changes Link cost changes: 60 good news travels fast bad news travels slow - count to infinity problem! X 4 Y 50 1 Z algorithm continues on! << 上一页 34 下一页 >>

35 Distance Vector: poisoned reverse If Z routes through Y to get to X : 60 Z tells Y its (Z s) distance to X is infinite (so Y won t route to X via Z) will this completely solve count to infinity problem? X 4 Y 50 1 Z algorithm terminates << 上一页 35 下一页 >>

36 << 上一页 36 下一页 >> Comparison of LS and DV algorithms Message complexity LS: with n nodes, E links, O(nE) msgs sent each DV: exchange between neighbors only convergence time varies Speed of Convergence LS: O(n 2 ) algorithm requires O(nE) msgs DV: convergence time varies may be routing loops count-to-infinity problem

37 << 上一页 37 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

38 << 上一页 38 下一页 >> Hierarchical Routing Our routing study too idealization all routers identical network flat not true in practice

39 << 上一页 39 下一页 >> Hierarchical Routing scale: with 500 million destinations can t store all dest s in routing tables! routing table exchange would swamp links! administrative autonomy internet = network of networks each network admin may want to control routing in its own network

40 Hierarchical Routing aggregate routers into regions, autonomous systems (AS) routers in same AS run same routing protocol intra-as routing protocol routers in different AS can run different intra-as routing protocol gateway routers special routers in AS run intra-as routing protocol with all other routers in AS also responsible for routing to destinations outside AS run inter-as routing protocol with other gateway routers << 上一页 40 下一页 >>

41 << 上一页 41 下一页 >> Intra-AS and Inter-AS routing a C C.b b d A A.a a b A.c c B.a a B c b Gateways: perform inter-as routing amongst themselves perform intra-as routing with other routers in their AS inter-as, intra-as routing in gateway A.c network layer link layer physical layer

42 << 上一页 42 下一页 >> Intra-AS and Inter-AS routing a Host h1 C C.b b A.a Inter-AS routing between A and B A.c a d A b c Intra-AS routing within AS A B.a a B c b Host h2 Intra-AS routing within AS B

43 << 上一页 43 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

44 << 上一页 44 下一页 >> Internet Routing Model 2 key features: Dynamic routing Intra- and Inter-AS routing, AS = locus of admin control Internet organized as autonomous systems (AS) AS is internally connected Interior Gateway Protocols (IGPs) within AS. Eg: RIP, OSPF, IS-IS Exterior Gateway Protocols (EGPs) for AS to AS routing. Eg: EGP, BGP-4

45 << 上一页 45 下一页 >> Requirements for Intra-AS Routing Should scale for the size of an AS Low end: 10s of routers (small enterprise) High end: 1000s of routers (large ISP) Different requirements on routing convergence after topology changes Low end: can tolerate some connectivity disruptions High end: fast convergence essential to business (making money on transport)

46 << 上一页 46 下一页 >> Requirements for Intra-AS Routing Operational/Admin/Management (OAM) Complexity Low end: simple, self-configuring High end: Self-configuring, but operator hooks for control Traffic engineering capabilities

47 << 上一页 47 下一页 >> Requirements for Inter-AS Routing Should scale for the size of the global Internet Focus on reachability, not optimality Use address aggregation techniques to minimize core routing table sizes and associated control traffic At the same time, it should allow flexibility in topological structure (eg: don t restrict to trees etc)

48 << 上一页 48 下一页 >> Requirements for Inter-AS Routing Allow policy-based routing between autonomous systems Policy refers to arbitrary preference among a menu of available options (based upon options attributes) Fully distributed routing (as opposed to a signaled approach) is the only possibility Extensible to meet the demands for newer policies

49 << 上一页 49 下一页 >> Internet AS Hierarchy Intra-AS border (exterior gateway) routers Inter-AS interior (gateway) routers

50 << 上一页 50 下一页 >> Intra-AS Routing Also known as Interior Gateway Protocols (IGP) Most common Intra-AS routing protocols: RIP:Routing Information Protocol OSPF:Open Shortest Path First IS-IS:Intermediate System to Intermediate System IGRP:Interior Gateway Routing Protocol (Cisco proprietary)

51 << 上一页 51 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

52 << 上一页 52 下一页 >> RIP (Routing Information Protocol) Distance vector algorithm Included in BSD-UNIX Distribution in 1982 Distance metric: # of hops (max = 15 hops) Distance vectors: exchanged among neighbors every 30 sec via Response Message (also called advertisement) Each advertisement: list of up to 25 destination nets within AS

53 << 上一页 53 下一页 >> RIP: Example z w x y A D B Destination Network C Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x Routing table in D

54 RIP: Example Dest Next hops w - - x - - z C 4 Advertisement from A to D z w x y A D B Destination Network << 上一页 54 下一页 >> C Next Router Num. of hops to dest. w A 2 y B 2 z B A 7 5 x Routing table in D

55 << 上一页 55 下一页 >> RIP: Link Failure and Recovery If no advertisement heard after 180 sec --> neighbor/link declared dead routes via neighbor invalidated new advertisements sent to neighbors neighbors in turn send out new advertisements (if tables changed) link failure info quickly propagates to entire net poison reverse used to prevent pingpong loops (infinite distance = 16 hops)

56 << 上一页 56 下一页 >> RIP Table processing RIP routing tables managed by applicationlevel process called route-d (daemon) advertisements sent in UDP packets, periodically repeated routed routed Transprt (UDP) network routing (IP) table link physical routing table Transprt (UDP) network (IP) link physical

57 << 上一页 57 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

58 << 上一页 58 下一页 >> OSPF Development History CIDR OSPF Group formed OSPFv1 published RFC 1131 OSPFv2 published RFC 1247 Cryptographic authentication Point-to-multipoint interfaces MOSPF OSPFv2 update RFC 1583 OSPFv2 update RFC 2178 OSPFv3 RFC 2740 OSPFv2 update RFC 2328 Becomes recommended

59 << 上一页 59 下一页 >> Hierarchical OSPF Backbone Area1 Area2 Area3 AS1 Internal Routers Area Border Routers Backbone Routers AS Border Routers

60 << 上一页 60 下一页 >> OSPF OSPF: Open Shortest Path First protocol Preferred IGP Evolved from IS-IS protocol Link state protocol Distribution of LSA using reliable flooding, LSA flooding is bounded by area

61 OSPF Use IP as transport, IP protocol 89 Utilize IP multicast when sending/receiving the updates , All OSPFRouters , All DRs Support for CIDR, Authentication and Multi-path Employ Dijkstra s Shortest Path First (SPF) algorithm to calculate the path tree << 上一页 61 下一页 >>

62 << 上一页 62 下一页 >> OSPF Motivation Original IGP used RIP Based on Distance Vector Algorithm Worked well in small systems Hop count limit of 15

63 << 上一页 63 下一页 >> OSPF Motivation (Cont.) Suffered from problems of Distance Vector Protocol Count to Infinity Problem Slow Convergence Large update packets Slow response to topological changes Need for a Link State Protocol

64 << 上一页 64 下一页 >> Functional Requirements of OSPF Faster Convergence and less consumption of network resources A more descriptive routing metric Configurable Value ranges between 1 and 65,535 No restriction on network diameters Equal-cost multipath A way to do load balancing

65 << 上一页 65 下一页 >> Functional Requirements of OSPF (Cont.) Routing Hierarchy Support large routing domains Separate internal and external routes Support of flexible sub netting schemes

66 << 上一页 66 下一页 >> OSPF Operation Establishing router adjacencies (which are neighbors with two way communication) Electing DR and BDR (represent routers in one area) Discovering Routes (get link states by exchanging) Choosing Routes (SPF algorithm) Maintaining Routing Information

67 << 上一页 67 下一页 >> OSPF Basics Distributed, replicated database model Each router builds a topology database Describes complete routing topology Link state database Identical for all the routers LSA: Link State Advertisements Information about adjacencies sent to all routers

68 << 上一页 68 下一页 >> OSPF Basics (Cont.) A "shortest path" algorithm is used to find best route(dijsktra) converge as quickly as databases can be updated Every router calculate itself routing table independently

69 << 上一页 69 下一页 >> OSPF Basics (Cont.) OSPF has 3 sub-protocols: Hello protocol Exchange protocol Flooding protocol Destination IP address: Neighbors IP address or AllOSPFRouters ( ) or AllDRouters ( )

70 << 上一页 70 下一页 >> Period of Hello Exchange The protocol remains relatively quiet during steady-state conditions Periodic refresh is 30 minutes MaxAge is 60 minutes

71 << 上一页 71 下一页 >> OSPF Metric 16-bit positive number 1 65,535 Cost on all router link paths The lower the more desirable Route decisions made on total cost of path

72 << 上一页 72 下一页 >> OSPF Packet Header Every OSPF packet starts with a standard 24 bytes header

73 << 上一页 73 下一页 >> Steps to OSPF Operation with OSPF States Establishing router adjacencies Down State Init State Two-way State (ExStart State unless DR/BDR election needed) Electing DR and BDR ExStart State with DR and BDR Two-way State with all other routers

74 << 上一页 74 下一页 >> Steps to OSPF Operation with OSPF States (Cont.) Discovering Routes ExStartState Exchange State Loading State Full State Choosing Routes Maintaining Routing Information

75 << 上一页 75 下一页 >> Neighbor Discovery and Maintenance OSPF Hello Protocol Multicast on all router interfaces Hello packets sent out periodically (10 sec. LAN, 30 sec. )Help to detect if neighbors are up or down

76 << 上一页 76 下一页 >> Neighbor Bi-directional OSPF communication Result of OSPF hello packets Need not exchange routing information

77 << 上一页 77 下一页 >> Broadcast Media - problems N neighbors - order of N square adjacency Not optimal Wasted bandwidth Does not scale

78 << 上一页 78 下一页 >> Broadcast Media - solution Select a neighbor - Designated Router(DR) All routers become adjacent to DR Exchange routing information with the DR DR updates all the neighbors Scales Backup Designated Router (BDR)

79 Discovering Routes and Reaching Full State adjacent OSPF Type-2 (DBD) OSPF Type-2 (DBD) OSPF Type-2 (DBD) OSPF Type-2 (DBD) OSPF Type-5 (LSAck) OSPF Type-3 (LSR) OSPF Type-4 (LSU) OSPF Type-5 (LSAck) << 上一页 79 下一页 >>

80 << 上一页 80 下一页 >> Choosing Routes Dijkstra - Shortest Path First (SPF) Algorithm Link state database Created with Link State Packets (LSPs) from each router Forwarding database The Routing Table

81 << 上一页 81 下一页 >> Maintaining routes When a Link Changes State

82 << 上一页 82 下一页 >> Scaling OSPF Rule of thumb no more than 150 routers /area Reality no more than 500 routers/area Backbone area is an area that glue all the other areas always marked as area 0 proper use of areas reduces bandwidth summarized routes instability is limited within the area

83 << 上一页 83 下一页 >> OSPF Summary Why OSPF is needed in the Internet? The basics of the protocol The operation of the protocol Neighbor Discovery (Hello Protocol) The Link state Advertisements Database Synchronization and reliable flooding Hierarchical Routing in OSPF OSPF Areas and Area Organization

84 << 上一页 84 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

85 << 上一页 85 下一页 >> Internet AS Hierarchy Inter-AS border (exterior gateway) routers Intra-AS interior (gateway) routers

86 << 上一页 86 下一页 >> Why different Intra- and Inter- Policy: AS routing? Inter-AS: admin wants control over how its traffic routed, who routes through its net Intra-AS: single admin, so no policy decisions needed Scale: hierarchical routing saves table size, reduced update traffic Performance: Intra-AS: can focus on performance Inter-AS: policy may dominate over performance

87 << 上一页 87 下一页 >> Autonomous Routing Domains A collection of physical networks glued together using IP, that have a unified administrative routing policy Campus networks Corporate networks ISP Internal networks

88 << 上一页 88 下一页 >> Autonomous Systems (ASes) An autonomous system is an autonomous routing domain that has been assigned an Autonomous System Number (ASN) the administration of an AS appears to other ASes to have a single coherent interior routing plan and presents a consistent picture of what networks are reachable through it RFC 1930: Guidelines for creation, selection, and registration of an Autonomous System

89 AS Numbers (ASNs) << 上一页 89 下一页 >> ASNs are 16 bit values through are private Currently over 41,000 in use Genuity: 1 MIT: 3 Harvard: 11 UC San Diego: 7377 AT&T: 7018, 6341, 5074, UUNET: 701, 702, 284, 12199, Sprint: 1239, 1240, 6211, 6242, ASNs represent units of routing policy

90 << 上一页 90 下一页 >> Nontransit vs. Transit ASes ISP 1 ISP 2 Internet Service providers (often) have transit networks Traffic NEVER flows from ISP 1 through NET A to ISP 2 (At least not intentionally!) NET A Nontransit AS might be a corporate or campus network. Could be a content provider IP traffic

91 << 上一页 91 下一页 >> Selective Transit NET B NET C NET A DOES NOT provide transit between NET D and NET B NET A NET A provides transit between NET B and NET C and between NET D and NET C NET D IP traffic Most transit networks transit in a selective manner

92 << 上一页 92 下一页 >> Customers and Providers provider provider customer IP traffic customer Customer pays provider for access to the Internet

93 << 上一页 93 下一页 >> Customers Don t Always Need BGP provider Nail up routes /24 pointing to customer Nail up default routes /0 pointing to provider. customer /24 Static routing is the most common way of connecting an autonomous routing domain to the Internet This helps explain why BGP is a mystery to many

94 << 上一页 94 下一页 >> Customer-Provider Hierarchy provider customer IP traffic

95 << 上一页 95 下一页 >> The Peering Relationship peer provider traffic allowed peer customer traffic NOT allowed Peers provide transit between their respective customers Peers do not provide transit between peers Peers (often) do not exchange $$$

96 Peering Provides Shortcuts Peering also allows connectivity between the customers of Tier 1 providers. << 上一页 96 下一页 >> peer provider peer customer

97 Peering Wars Peer Reduces upstream transit costs Can increase endto-end performance May be the only way to connect your customers to some part of the Internet ( Tier 1 ) Don t Peer You would rather have customers Peers are usually your competition Peering relationships may require periodic renegotiation Peering struggles are by far the most contentious issues in the ISP world! Peering agreements are often confidential << 上一页 97 下一页 >>

98 << 上一页 98 下一页 >> 国内 ISP 互联状态 经营性的互联单位 6 家 中国电信和中国网通 ( 称为 大网 ) 中国移动 中国联通和中国铁通 ( 称为 中网 ) 其他非经营性互联单位 ( 称为 小网 ), 如 CERNET 大网之间互不结算

99 国内 ISP 互联状态 中网与大网之间的结算方式包括直联和经 NAP 点转接 直联方式 目前大网向中网收取直联带宽价格为 200 万元 / 月 G NAP 点转接方式 北京 上海 广州建有国家级互联网交换中心 (NAP 点 ) 国家级交换中心采取政府定价, 根据信息产业部 2006 年 11 月颁布的 互联网交换中心网间结算办法, 中网按照双向流量的平均值向大网交结算费, 折合约为 160 万元 / 月 G << 上一页 99 下一页 >>

100 << 上一页 100 下一页 >> BGP-4 BGP = Border Gateway Protocol Is a Policy-Based routing protocol Is the de facto EGP of today s global Internet Relatively simple protocol, but configuration is complex and the entire world can see, and be impacted by, your mistakes Pakistan Telecom and YouTube

101 << 上一页 101 下一页 >> Pakistan Telecom and YouTube 2008 年 2 月,YouTube 出现反伊斯兰教视频 Pakistan Telecom 接获最高当局封杀命令後, 开始广播自己是 YouTube 所属 IP 网络空间 256 个地址的正确路径 正牌 YouTube 是广播 1024 台主机的地址空间, 因此几分钟后, 所有流量都开始流向这个错误的地方 根据即时网路流量监控公司 Renesys 的时间表, 亚太地区 ISP 在 15 秒内就开始将 YouTube.com 的流量导向这家巴基斯坦的 ISP, 而其他地区的路由器也在 45 秒后就开始跟进

102 << 上一页 102 下一页 >> Pakistan Telecom and YouTube YouTube 在数分钟后开始进行反制, 首先把自己原先广播的 1024 个地址降至 256 个 11 分钟后,YouTube 又加入更精确的广播, 限缩至 64 个地址, 由于依据 BGP 协议, 后者更为精确, 因此会推翻原来巴基斯坦的版本 历经两小时的错误路由后,Pakistan Telecom 才终 于终止该行为

103 << 上一页 103 下一页 >> BGP : BGP-1 [RFC 1105] Replacement for EGP (1984, RFC 904) 1990 : BGP-2 [RFC 1163] 1991 : BGP-3 [RFC 1267] 1995 : BGP-4 [RFC 1771] Support for Classless Interdomain Routing (CIDR)

104 << 上一页 104 下一页 >> BGP Operations (Simplified) Establish session on TCP port 179 AS1 Exchange all active routes Exchange incremental updates BGP session AS2 While connection is ALIVE exchange route UPDATE messages

105 Four Types of BGP Messages Open : Establish a peering session Keep Alive : Handshake at regular intervals Notification : Shuts down a peering session Update : Announcing new routes or withdrawing previously announced routes announcement = prefix + attributes values << 上一页 105 下一页 >>

106 << 上一页 106 下一页 >> BGP Attributes Value Code Reference ORIGIN [RFC1771] 2 AS_PATH [RFC1771] 3 NEXT_HOP [RFC1771] 4 MULTI_EXIT_DISC [RFC1771] 5 LOCAL_PREF [RFC1771] 6 ATOMIC_AGGREGATE [RFC1771] 7 AGGREGATOR [RFC1771] 8 COMMUNITY [RFC1997] 9 ORIGINATOR_ID [RFC2796] 10 CLUSTER_LIST [RFC2796] 11 DPA [Chen] 12 ADVERTISER [RFC1863] 13 RCID_PATH / CLUSTER_ID [RFC1863] 14 MP_REACH_NLRI [RFC2283] 15 MP_UNREACH_NLRI [RFC2283] 16 EXTENDED COMMUNITIES [Rosen] reserved for development We will cover these attributes Not all attributes need to be present in every announcement

107 << 上一页 107 下一页 >> Attributes are Used to Select Best Routes /24 pick me! /24 pick me! /24 pick me! /24 pick me! Given multiple routes to the same prefix, a BGP speaker must pick at most one best route (Note: it could reject them all!)

108 << 上一页 108 下一页 >> Two Types of BGP Neighbor Relationships AS1 ebgp External Neighbor (ebgp) in a different Autonomous Systems Internal Neighbor (ibgp) in the same Autonomous System ibgp is routed (using IGP!) ibgp AS2

109 << 上一页 109 下一页 >> ibgp Peers Must be Fully Meshed ebgp update ibgp updates A consistent view of the routes exterior to the AS can be provided by having all BGP speakers within the AS maintain direct BGP connections with each other

110 << 上一页 110 下一页 >> BGP Next Hop Attribute AS 6431 AT&T Research AS 7018 AT&T AS RIPE NCC RIS project /16 Next Hop = /16 Next Hop = Every time a route announcement crosses an AS boundary, the Next Hop attribute is changed to the IP address of the border router that announced the route

111 << 上一页 111 下一页 >> Join EGP with IGP For Connectivity /16 Next Hop = / Forwarding Table destination next hop / destination + EGP next hop / AS 1 AS /30 Forwarding Table destination next hop / /

112 << 上一页 112 下一页 >> BGP Route Processing Receive BGP Updates Apply Policy = filter routes & tweak attributes Based on Attribute Values Best Routes Apply Policy = filter routes & tweak attributes Transmit BGP Updates Apply Import Policies Best Route Selection Best Route Table Apply Export Policies Install forwarding Entries for best Routes IP Forwarding Table

113 << 上一页 113 下一页 >> Back to Frank Local preference only used in ibgp peer provider peer customer AS 4 local pref = 80 local pref = 90 AS 3 local pref = 100 Higher Local preference values are more preferred AS 2 AS /16

114 << 上一页 114 下一页 >> Implementing Backup Links with Local Preference (Outbound Traffic) AS 1 primary link backup link Set Local Pref = 100 for all routes from AS 1 AS Set Local Pref = 50 for all routes from AS 1 Forces outbound traffic to take primary link, unless link is down. We ll talk about inbound traffic soon

115 << 上一页 115 下一页 >> Multihomed Backups (Outbound Traffic) AS 1 provider AS 3 provider primary link backup link Set Local Pref = 100 for all routes from AS 1 AS 2 Set Local Pref = 50 for all routes from AS 3 Forces outbound traffic to take primary link, unless link is down.

116 ASPATH Attribute /16 AS Path = AS 1129 Global Access /16 AS Path = AS 1239 Sprint AS 1755 Ebone /16 AS Path = /16 AS Path = AS RIPE NCC RIS project /16 AS Path = 6341 AS 6341 AT&T Research /16 AS7018 AT&T /16 AS Path = /16 AS Path = AS 3549 Global Crossing Prefix Originated << 上一页 116 下一页 >>

117 << 上一页 117 下一页 >> Interdomain Loop Prevention AS 7018 BGP at AS YYY will never accept a route with ASPATH containing YYY Don t Accept! /16 ASPATH = AS 1

118 << 上一页 118 下一页 >> Traffic Often Follows ASPATH /16 ASPATH = AS /16 AS 2 AS 3 AS 4 IP Packet Dest =

119 << 上一页 119 下一页 >> But It Might Not AS / /16 ASPATH = /25 ASPATH = 5 AS 2 AS 2 filters all subnets with masks longer than /24 AS /16 ASPATH = AS 4 IP Packet Dest = AS /25 From AS 4, it may look like this packet will take path 3 2 1, but it actually takes path 3 2 5

120 << 上一页 120 下一页 >> Shorter Doesn t Always Mean Shorter In fairness: could you do this right and still scale? AS 3 Mr. BGP says that path 4 1 is better than path Duh! AS 4 Exporting internal state would dramatically increase global instability and amount of routing state AS 2 AS 1

121 << 上一页 121 下一页 >> Attention BGP is not guaranteed to converge on a stable routing. Policy interactions could lead to livelock protocol oscillations Corollary: BGP is not guaranteed to recover from network failures

122 How Many ASNs are there? << 上一页 122 下一页 >>

123 << 上一页 123 下一页 >> BGP Routing Tables show ip bgp BGP table version is , local router ID is Status codes: s suppressed, d damped, h history, * valid, > best, i - internal Origin codes: i - IGP, e - EGP,? - incomplete Network Next Hop Metric LocPrf Weight Path... *>i i *>i i *>i i *>i i *>i i *>i i *>i i *>i i *>i i *>i / i... Thanks to Geoff Huston. on July 6, 2001 Hey, we can use these paths to draw cool graphs!

124 << 上一页 124 下一页 >> BGP Dynamics How many updates are flying around the Internet? How long Does it take Routes to Change? The goals of (1) fast convergence (2) minimal updates (3) path redundancy

125 << 上一页 125 下一页 >> Q: Why All the Updates? Networks come, networks go There s always a router rebooting somewhere Hardware failure, flaky interface cards, backhoes digging, floods in Houston, This is normal --- exactly what dynamic routing is designed for

126 << 上一页 126 下一页 >> BGP Summary BGP = RFC optional extensions RFC 1997 (communities) RFC 2439 (damping) RFC 2796 (reflection) RFC3065 (confederation) + routing policy configuration languages (vendor-specific) + Current Best Practices in Management of Interdomain Routing

127 << 上一页 127 下一页 >> BGP Summary BGP is a fairly simple protocol but it is not easy to configure BGP is running on more than 100K routers, making it one of world s largest and most visible distributed systems Global dynamics and scaling principles are still not well understood

128 << 上一页 128 下一页 >> 提纲 网络层服务 网络路由基本原理 层次化路由体系结构 IP 协议简介 Internet 路由协议 intra-domain: RIP, OSPF inter-domain: BGP 高性能路由器体系结构

129 << 上一页 129 下一页 >> 为什么需要高性能路由器? 1. 防止路由器成为 Internet 的瓶颈 2. 并降低成本

130 高性能路由器的位置 (2.5 Gb/s) R1 R2 R5 R6 (2.5 Gb/s) R3 R4 R7 R8 (2.5 Gb/s) R9 R13 R15 R10 R14 R11 R16 R12 (2.5 Gb/s) << 上一页 130 下一页 >>

131 Juniper T 年 12 月推出扩展结构的 T640 采用矩阵技术 : 双面结构, 消除低密度扩容限制 单机支持 32 个 OC-192c/STM- 64, 或提供 8 个 40 Gbps 的插槽 单机提供 640 Gbps 的交换容量 通过光背板扩展装置从底盘背部提供 1280 Gbps 的带宽 多个 T640 能够相互连接, 并作为单个路由器工作, 提供 2.5 Tbps 甚至更高的吞吐量 << 上一页 131 下一页 >>

132 << 上一页 132 下一页 >> 为什么需要高性能路由器? 1: 防止路由器成为 Internet 的瓶颈 分组处理能力 链路速率 Spec95Int CPU results x / 18 months ,1 2x / 7 months TDM DWDM ,1 Fiber Capacity (Gbit/s)

133 << 上一页 133 下一页 >> 为什么需要高性能路由器? 1. 难以跟上 Moore 定律的速度 瓶颈是内存访问速度 内存访问速度跟不上 Moore 定律的速度 2. Moore 定律本身太慢 路由器能力的增长必须比 Moore 定律更快

134 << 上一页 134 下一页 >> 商用 DRAM 的发展速度慢 Access Time (ns) Moore s Law 2x / 18 months

135 << 上一页 135 下一页 >> 第一代路由器 Shared Backplane CPU Route Table Buffer Memory CPU Memory Line Interface Line Interface Line Interface Line Interface MAC MAC MAC Typically <0.5Gb/s aggregate capacity

136 << 上一页 136 下一页 >> 第二代路由器 CPU Route Table Buffer Memory Line Card Line Card Line Card Buffer Memory Fwding Cache MAC Buffer Memory Fwding Cache MAC Buffer Memory Fwding Cache MAC Typically <5Gb/s aggregate capacity

137 第三代路由器 Switched Backplane Line Card CPU Card Line Card Line Interface CPU Local Buffer Memory Routing Table Local Buffer Memory Memory Fwding Table Fwding Table MAC MAC << 上一页 137 下一页 >> Typically <320Gb/s aggregate capacity

138 第四代路由器 (CRS) Optical links 100s of metres Switch Core << 上一页 138 下一页 >> Linecards Tb/s routers in development