Interdomain Routing Protocols - GBP Dr. Yingwu Zhu

Interdomain Routing Protocols - GBP Dr. Yingwu Zhu

Interdomain Routing Protocols - GBP Dr. Yingwu Zhu 1 Exterior Routing Protocols Problems: Topology: The Internet is a complex mesh of different ASs with very little structure. Autonomy of ASs: Each AS defines link costs in different ways, so not possible to find lowest cost paths. Trust: Some ASs cant trust others to advertise good routes (e.g. two competing backbone providers), or to protect the privacy of their traffic (e.g. two warring nations). Policies: Different ASs have different objectives (e.g. route over fewest hops; use one provider rather than another). Border Gateway Protocol (BGP-4) BGP is not a link-state or distance-vector routing

protocol. Instead, BGP uses Path vector BGP advertises complete paths (a list of ASs). Also called AS_PATH (this is the path vector) Example of path advertisement: The network 171.64/16 can be reached via the path {AS1, AS5, AS13}. Paths with loops are detected locally and ignored. Local policies pick the preferred path among options. When a link/router fails, the path is withdrawn. Autonomous Systems An autonomous system (AS) is a region of the Internet that is administered by a single entity and that has a unified routing policy Each autonomous system is assigned an Autonomous System Number

(ASN: 16-bit unique number). Stanford(AS32) Rogers Cable Inc. (AS812) Sprint (AS1239, AS1240, AS 6211, ) AT&T (AS 6431, ) Interdomain routing is concerned with determining paths between autonomous systems (interdomain routing) Routing protocols for interdomain routing are called exterior gateway protocols (EGP) 4 Internet Structure 5 Interdomain and Intradomain Routing

AS 2 AS 5 AS 1 AS 6 AS 7 AS 3 AS 4 Routing protocols for intradomain routing are called interior gateway protocols (IGP) Objective: shortest path Routing protocols for interdomain routing are called exterior gateway protocols (EGP) Objective: satisfy policy of the AS 6 Interdomain vs Intradomain

AS 2 AS 2 EGP (e.g., BGP) IGP (e.g., OSPF) IGP (e.g., RIP) Intradomain routing (OSPF, RIP) Routing is done based on metrics Routing domain is one autonomous system Routing on IP addresses Interdomain routing (BGP) Routing is done based on policies and business relations Routing domain is the entire Internet Routing is based on AS numbers 7 Interdomain Routing Interdomain routing is based on connectivity between autonomous

systems Interdomain routing can ignore many details of router interconnection AS 1 AS 2 AS 3 8 AS Graphs AT&T North America From: T. Griffin, BGP Tutorial, ICNP 2002 9 Multiple Routing Protocols Multiple routing protocols can run on the same router

Each routing protocol updates the routing table RIP Process BGP Process OSPF Process routing protocol routing protocol routing table updates routing table

routing table lookup incoming IP datagrams IP Forwarding outgoing IP datagrams 10 Autonomous Systems Terminology local traffic transit traffic Stub AS Multihomed AS Transit AS

= traffic with source or destination in AS = traffic that passes through the AS = has connection to only one AS, only carry local traffic = has connection to >1 AS, but does not carry transit traffic = has connection to >1 AS and carries transit traffic 11 Stub and Transit Networks AS 1 AS 1, AS 2, and AS 5 are stub networks

AS 2 is a multi-homed stub network AS 3 and AS 4 are transit networks AS 2 AS 3 AS 4 AS 5 12 Selective Transit Example: Transit AS 3 carries traffic between AS 1 and AS 4 and between AS 2 and AS 4 But AS 3 does not carry traffic

between AS 1 and AS 2 AS 2 AS 1 AS 3 The example shows a routing policy. AS 4 13 Customer/Provider AS 2 Customer/ Provider

Customer/ Provider AS 4 Customer/ Provider AS 6 AS 5 Customer/ Provider AS 6 Customer/ Provider AS 6

A stub network typically obtains access to the Internet through a transit network. Transit network that is a provider may be a customer for another network Customer pays provider for service 14 Customer/Provider and Peers AS 1 AS 2 Peers Peers Customer/ Provider Customer/

Provider AS 4 AS 5 Customer/Provider AS 3 Customer/ Provider AS 6 Customer/ Provider AS 6 AS 6

Transit networks can have a peer relationship Peers provide transit between their respective customers Peers do not provide transit between peers Peers normally do not pay each other for service 15 Shortcuts through peering AS 1 AS 2 Peers Customer/ Provider Customer/ Provider

AS 4 Peers AS 5 Peers Customer/Provider AS 3 Customer/ Provider AS 6 Customer/ Provider AS 6 AS 6 Note that peering reduces upstream traffic

Delays can be reduced through peering But: Peering may not generate revenue 16 Border Gateway Protocol (BGP) Border Gateway Protocol is the interdomain routing protocol for the Internet for routing between autonomous systems Currently in version 4 (1995) Network administrators can specify routing policies BGP is a distance vector protocol (However, routing messages in BGP contain complete routes) Uses TCP to transmit routing messages 17 Border Gateway Protocol (BGP) An autonomous system uses BGP to advertise its network address(es) to other ASs

BGP helps an autonomous system with the following: 1. Collect information about reachable networks from neighboring ASs 2. Disseminate the information about reachable networks to routers inside the AS and to neighboring ASs 3. Picks routes if there are multiple routes available 18 BGP interactions Router establishes a TCP connection (TCP port 175) Routers exchange BGP routes Periodically send updates BGP is executed between two routers BGP session BGP peers or BGP speakers

Note: Not all autonomous systems need to run BGP. On many stub networks, the route to the provider can be statically configured AS 1 BGP Session AS 2 19 Advertising a Prefix When a router advertises a prefix to one of its BGP neighbors: information is valid until first router explicitly advertises that the information is no longer valid BGP does not require routing information to be refreshed

if node A advertises a path for a prefix to node B, then node B can be sure node A is using that path itself to reach the destination. 20 BGP interactions AS 1 The networks that are advertised are network IP addresses with a prefix, E.g., 128.100.0.0/16 Prefixes reachable from AS 1 AS 2 Prefixes reachable from AS 3

AS 3 21 BGP interactions BGP peers advertise reachability of IP networks BGP Peer A advertises a path to a network (e.g., 10.0.0.0/8) to B only if it is willing to forward traffic going to that network Path-Vector: A advertises the complete path to the advertised network Path is sent as a list of ASs this avoids loops B

Advertise path to 10.0.0.0/24 A BGP Peer 10.0.0.0/24 22 BGP Sessions External BGP session (eBGP): Peers are in different ASes Internal BGP session (iBGP) Peers are in same ASes Note that iBGP sessions are going over routes that are set up by an intradomain routing protocol!

AS B eBGP session AS A iBGP session 23 iBGP sessions All iBGP peers in the same autonomous system are fully meshed Peer announces routes received via eBGP to iBGP peers Update from eBGP session But: iBGP peers do not announce

routes received via iBGP to other iBGP peers AS A 24 Hot Potato Routing Router R3 in autonomous system A receives two advertisements to network X Which route should it pick? Route to X Route to X Hot Potato Rule: Select the iBGP peer that has the shortest IGP route Analogy: Get the packet out of

ones own AS as quickly as possible, i.e., on the shortest path R2 R1 Route to X Route to X R3 AS A 25 Hot Potato Routing Finding the cheapest IGP route: Compare the cost of the two

paths R3 R1 R3 R2 according to the IGP protocol Here: R1 has the shortest path Route to X Route to X R1 R2 Cost=6 Cost=23 Add a routing table entry for destination X

R3 AS A 26 Hot Potato Routing can backfire! AS1 would serve its customer (source) better by not picking the shortest route to AS 2 In fact, customer may have paid for a high-bandwidth service! Source AS 1 Cost=20 Cost=5 High bandwidth network Low bandwidth network

AS 2 Destination 27 BGP Message Types Open: Establishes a peering session Keep Alive: Handshake at regular intervals to maintain peering session Notification: Closes a peering session Update: Advertises new routes or withdraws

previously announced routes. Each announced route is specified as a network prefix with attribute values 28 Content of Advertisements BGP routers advertise routes Each route consists of a network prefix and a list of attributes that specify information about a route Mandatory attributes: ORIGIN AS_PATH NEXT_HOP Many other attributes 29 ORIGIN attribute

Originating domain sends a route with ORIGIN attribute ORIGIN attributes also specifies if the origin is internal to the AS or not 10.0.1.0/8, ORIGIN {1} AS 2 AS 4 10.0.1.0/8, ORIGIN {1} AS 1 10.0.1.0/8, ORIGIN {1} 10.0.1.0/8, ORIGIN {1}

AS 5 AS 3 10.0.1.0/8, ORIGIN {1} 30 AS-PATH attributes Each AS that propagates a route prepends its own AS number AS-PATH collects a path to reach the network prefix Path information prevents routing loops from occurring Path information also provides information on the length of a path (By default, a shorter route is preferred)

Note: BGP aggregates routes according to CIDR rules 10.0.1.0/8, AS-PATH {1} AS 2 AS 4 10.0.1.0/8, AS-PATH {4,2,1} 10.0.1.0/8, AS-PATH {2,1} AS 1 10.0.1.0/8, AS-PATH {1} AS 5

AS 3 10.0.1.0/8, AS-PATH {3,1} 31 NEXT-HOP attributes Each router that sends a route advertisement it includes its own IP address in a NEXT-HOP attribute The attribute provides information for the routing table of the receiving router. 128.143.71.21 128.100.11.1 AS 1

AS 5 AS 3 10.0.1.0/8, NEXT-HOP {128.100.11.1} 10.0.1.0/8, NEXT-HOP {128.143.71.21} 32 Connecting NEXT-HOP with IGP information 192.0.1.2 128.100.11.1/24 AS 1 eBGP IGP router

R1 AS 3 iBGP 10.1.1.0/8, NEXT-HOP {128.100.11.1} 10.1.1.0/8, NEXT-HOP {128.100.11.1} At R1: Routing table Dest. Next hop 128.100.11.0/24

192.0.1.2 BGP info Dest. Next hop 10.1.1.0/8 128.100.11.1 Routing table Dest. Next hop 128.100.11.0/24

192.0.1.2 10.1.1.0/8 192.0.1.2 33 Local Preference Attribute 34 Use of Local Preference 35 Multi-Exit Discriminator (MED) Attribute 36 BGP route selection

Router may learn about more than 1 route to some prefix. Router must select route. Elimination rules: 1. Local preference value attribute: policy decision 2. Shortest AS-PATH 3. Closest NEXT-HOP router: hot potato routing 4. Additional criteria Importing and Exporting Routes An AS may not accept all routes that are advertised An AS may not advertise certain routes Route policies determines which routes are filtered If an AS wants to have less inbound traffic it should adapt its export rules

If an AS wants to control its inbound traffic, it adapts its import rules (When gateway router receives route advert, uses import policy to accept/decline.) Control Inbound traffic Change export rules AS A Control Outbound traffic Change import rules

38 Import Policy: Local Preference 39 Import Policy: Filtering 40 Export Policy: Filtering 41 Export Policy: Attribute Manipulation 42 Routing Policies

Since AS 5 is a stub network it should not advertise routes to networks other than networks in AS 5 AS 3 AS 4 When AS 3 learns about the path {AS1, AS4}, it should not advertise the route {AS3, AS1, AS4} to AS 2. AS 1

Peers Customer/ Provider AS 6 AS 2 Customer/Provider Customer/Provider AS 5 43 Traffic Often Follows ASPATH In many cases, packets

are routed according to the AS-PATH 128.100.0.0/16, AS-PATH {3,2,1} AS 1 AS 2 AS 3 AS 5 128.100.0.0/16 However, in some cases this is not true (Here: AS 2 filters

routes with a long prefix) 128.100.0.0/16, AS-PATH {1} AS 1 128.100.0.0/16, AS-PATH {2, 1} AS 2 128.100.0.0/16, AS-PATH {3,2,1} AS 3 AS 5 128.100.0.0/16

Does not advertise /24 networks 128.100.22.0/24, AS-PATH {4} AS 4 128.100.22.0/24 44 Short AS-PATH does not mean that route is short From AS 6s perspective Path {AS2, AS1} is short Path {AS5, AS4, AS3, AS1} is long AS 1 AS 3

But the number of traversed routers is larger when using the shorter AS-PATH AS 2 AS 4 AS 5 AS 6 45 BGP Table Growth Source: Geoff Huston. http://www.telstra.net/ops/bgptable.html on August 8, 2001 46 BGP Issues

BGP is a simple protocol but it is very difficult to configure BGP has severe stability issue due to policies BGP is known to not converge As of July 2005, 39,000 AS numbers (of available 64,510) are consumed 47

Recently Viewed Presentations

  • An Access Point That Moves - 3G AP

    An Access Point That Moves - 3G AP

    Title: An Access Point That Moves - 3G AP Last modified by: IBM USER Created Date: 10/22/2006 2:08:52 PM Document presentation format: 如螢幕大小
  • Prezentacja programu PowerPoint - ACK CYFRONET AGH

    Prezentacja programu PowerPoint - ACK CYFRONET AGH

    After three years of Centre activities: - Full integration with ERA, - Continuation of the project ? 6 FP „Transfer of Knowledge" projects Further calls ? 7 FP „Centres of Excellence" one of the objectives * Cracow Research Centre of...
  • Early Years & Childcare Briefing Ofsted update 28.6.16

    Early Years & Childcare Briefing Ofsted update 28.6.16

    Iters, Ecers, Fccers, Sacers, Ecers E, Ecat environmental . audits, Communication friendly spaces audit, Development matters enabling environments / positive relationships . Undertook observations of all practice or reflected on practice if you work alone? How do you ensure consistency...
  • Regions - Ms. A de Boer

    Regions - Ms. A de Boer

    Regions Regions Def: An area of the earth's surface defined by a set of characteristics or a single characteristic. There are 2 main types of regions: Homogenous or Functional 1. Homogeneous Regions Characteristics within this region type are similar; and...
  • Unit 1 Test - Mrs. Campbell's Teacher Webpage

    Unit 1 Test - Mrs. Campbell's Teacher Webpage

    Unit 1 Test. Review Game. Sophomore Language Arts. Which of these archetypal settings is best illustrated in the opening paragraph of Genesis? A. a plant that connects heaven and earth. B. a universe of opposites. C. a great sea that...
  • La Maestra Thompson

    La Maestra Thompson

    Como la mayor parte de los profesores, ella miraba a sus alumnos les decía que a todos los quería por igual. Pero eso no era posible, porque ahí en la primera fila, desparramado sobre su asiento, estaba un niño llamado:...
  • Portraits in Caring - Virginia DEQ

    Portraits in Caring - Virginia DEQ

    Water supply. Clean, safe, and adequate supply of drinking water. Cooling water for power plants and other industries. Salt water intrusion. Longer usage projections in planning and permitting for ground water and surface water withdrawals
  • Pump Theory - Bill Salmon Learning Associates

    Pump Theory - Bill Salmon Learning Associates

    Pump Theory Darley & Co. Serving the World Fire Industry for more than 95 years Pump Theory Darley & Co. Introduction to Pumps Types of Pumps Piston Pumps Positive Displacement Pumps Rotary Vane Pumps Centrifugal Pumps 2 Stage Pumps High...