Internet网络层协议设计

Transcription

1

2 << 2 >> OUTLINE Internet intra-domain: RIP, OSPF inter-domain: BGP

3 What does router look like? << 3 >>

4 << 4 >> Structure of Router

5 << 5 >> 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

6 << 6 >> 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

7 << 7 >> 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 Typically <320Gb/s aggregate capacity

8 (CRS) Optical links 100s of metres Switch Core << 8 >> Linecards Tb/s routers in development

9 << 9 >>

10 (2.5 Gb/s) R1 R2 R5 R6 (2.5 Gb/s) R3 R4 R7 R8 (2.5 Gb/s) R9 << 10 >> R13 R15 R10 R14 R11 R16 R12 (2.5 Gb/s)

11 << 11 >> 1. Moore Moore 2. Moore

12 << 12 >> 1: Internet Spec95Int CPU results x / 18 months ,1 2x / 7 months TDM DWDM ,1 Fiber Capacity (Gbit/s)

13 << 13 >> DRAM Access Time (ns) Moore s Law 2x / 18 months

14 << 14 >> Juniper T640

15 << 15 >> OUTLINE Internet intra-domain: RIP, OSPF inter-domain: BGP

16 << 16 >> Network layer functions network layer protocols in every host, router three important functions: path determination: route taken by packets from source to dest. Routing algorithms Route Look up look up the route table and match the specific route for a packet forwarding: move packets from router s input to appropriate router output 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

17 Routing and Forwarding Default to upstream router A D R R1 R4 << 17 >> 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

18 << 18 >> 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?

19 << 19 >> 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

20 << 20 >> 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

21 << 21 >> 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

22 << 22 >> 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

23 << 23 >> Internet intra-domain: RIP, OSPF inter-domain: BGP

24 << 24 >> 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

25 << 25 >> 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

26 << 26 >> 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 C E good path: typically means minimum cost path F

27 << 27 >> 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

28 << 28 >> Routing Algorithm Classification Static or dynamic? Static: routes no change over time Dynamic: routes change more quickly periodic update in response to link cost changes

29 << 29 >> 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

30 << 30 >> 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): current node along path from source to dest 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

31 << 31 >> 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

32 << 32 >> 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

33 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 A B 2 D C E F F << 33 >> D,4

34 << 34 >> 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

35 << 35 >> 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

36 << 36 >> 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

37 << 37 >> 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

38 << 38 >> 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

39 << 39 >> 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

40 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 << 40 >>

41 << 41 >> 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

42 << 42 >> 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

43 << 43 >> 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!

44 << 44 >> 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

45 << 45 >> 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

46 << 46 >> Internet intra-domain: RIP, OSPF inter-domain: BGP

47 << 47 >> Internet intra-domain: RIP, OSPF inter-domain: BGP

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

49 << 49 >> 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)

50 << 50 >> Requirements for Intra-AS Routing Operational/Admin/Management (OAM) Complexity Low end: simple, self-configuring High end: Self-configuring Traffic engineering capabilities

51 << 51 >> 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)

52 << 52 >> 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

53 << 53 >> Internet AS Hierarchy Intra-AS border (exterior gateway) routers Inter-AS interior (gateway) routers

54 << 54 >> 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)

55 << 55 >> Internet intra-domain: RIP, OSPF inter-domain: BGP

56 << 56 >> 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

57 << 57 >> 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

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

59 << 59 >> 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)

60 << 60 >> 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

61 << 61 >> Internet intra-domain: RIP, OSPF inter-domain: BGP

62 << 62 >> 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 OSPFv3 RFC 2740 OSPFv2 update RFC 2328 OSPFv2 update RFC 2178 Becomes recommended

63 << 63 >> Hierarchical OSPF Backbone Area1 Area2 Area3 AS1 Internal Routers Area Border Routers Backbone Routers AS Border Routers

64 << 64 >> 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

65 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 << 65 >>

66 << 66 >> OSPF Motivation Original IGP used RIP Based on Distance Vector Algorithm Worked well in small systems Hop count limit of 15

67 << 67 >> 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

68 << 68 >> 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

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

70 << 70 >> 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

71 << 71 >> 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

72 << 72 >> OSPF Basics (Cont.) A "shortest path" algorithm is used to find best route(dijsktra) Every router calculate itself routing table independently

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

74 << 74 >> Period of Hello Exchange The protocol remains relatively quiet during steady-state conditions Periodic refresh is 30 minutes MaxAge is 60 minutes

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 >> 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

78 << 78 >> 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

79 << 79 >> Internet intra-domain: RIP, OSPF inter-domain: BGP

80 << 80 >> Internet AS Hierarchy Inter-AS border (exterior gateway) routers Intra-AS interior (gateway) routers

81 << 81 >> 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

82 << 82 >> Why different Intra- and Inter- AS routing? Policy: Inter-AS: admin wants to control over how its traffic routed, who routes through its net Intra-AS: single admin, so no policy decisions needed Performance: Intra-AS: can focus on performance Inter-AS: policy may dominate over performance

83 << 83 >> Autonomous Routing Domain A collection of physical networks glued together using IP, that have a unified administrative routing policy Campus networks Corporate networks ISP Internal networks

84 << 84 >> 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

85 << 85 >> AS Numbers (ASNs) 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

86 << 86 >> AS Numbers (ASNs) AS4789 NAP1 at CERNET AS9800 UNICOM AS4134 AS4538 CHINANET-BACKBONE ERX-CERNET-BKB

87 << 87 >> 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

88 << 88 >> 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

89 << 89 >> Customers and Providers provider provider customer IP traffic customer Customer pays provider for access to the Internet

90 << 90 >> Customer-Provider Hierarchy provider customer IP traffic

91 << 91 >> 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

92 << 92 >> 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

93 << 93 >> ISP 6 CERNET

94 ISP NAP 200 / G NAP NAP / G << 94 >>

95 << 95 >> 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

96 << 96 >> 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)

97 << 97 >> 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

98 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 << 98 >>

99 << 99 >> 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 Not all attributes need to be present in every announcement

100 << 100 >> 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!)

101 << 101 >> Route Selection Summary Highest Local Preference Shortest ASPATH Lowest MED i-bgp < e-bgp Lowest IGP cost to BGP egress Lowest router ID

102 << 102 >> Local Preference Attribute 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

103 AS PATH Attribute /16 AS Path = AS 1129 Global Access /16 AS Path = AS 1755 Ebone /16 AS Path = AS 1239 Sprint /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 << 103 >>

104 << 104 >> 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

105 << 105 >> 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

106 << 106 >> 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

107 << 107 >> 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 / /

108 << 108 >> 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

109 << 109 >> Attention BGP is not guaranteed to converge on a stable routing. Policy interactions could lead to livelock protocol oscillations

110 << 110 >> 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 LocPrf 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

111 << 111 >> 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

112 << 112 >> IP Internet intra-domain: RIP, OSPF inter-domain: BGP

113 << 113 >> END