DOC PREVIEW
Berkeley ELENG 122 - Interdomain Routing

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

11Interdomain RoutingReading: Sections P&D 4.3.{3,4}EE122: Intro to Communication NetworksFall 2006 (MW 4:00-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica and colleagues atPrinceton and UC Berkeley3Outline• Why does BGP exist?– What is interdomain routing and why do we need it?– Why does BGP look the way it does?• How does BGP work?– Boring details– Yuckpay more attention to the “why” than the “how”24Routing• Provides paths between networks• Previous lecture presented two routing designs– link-state– distance vector• Previous lecture assumed single domain– all routers have same routing metric (shortest path)– no privacy issues, no policy issues5Internet is more complicated.....• Internet not just unstructured collection of networks• Internet is comprised of a set of “autonomoussystems” (ASes)– independently run networks, some are commercial ISPs– currently around 20,000 ASes• ASes are sometimes called “domains”– hence “interdomain routing”36Internet: a large number of ASesLarge ISPLarge ISPDial-UpISPAccessNetworkSmall ISPStub StubStub7This adds another level in hierarchy• Three levels in logical routing hierarchy– networks: reaches individual hosts– intradomain: routes between networks– interdomain: routes between ASes• Need a protocol to route between domains– BGP is current standard• Different kinds of unification– IP unifies network technologies– BGP unifies network organizations48Who speaks BGP?Rborder router internal routerBGPR2R1R3AS1AS2 Two types of routers Border router (Edge), Internal router (Core)9Purpose of BGPRborder routerinternal routerBGPR2R1R3AAS1AS2you can reachnet A via metraffic to Atable at R1:dest next hopA R2Share connectivity information across ASes510I-BGP and E-BGPRborder routerinternal routerR1AS1R4R5BAS3E-BGPR2R3AAS2announce BIGP: Intradomain routingExample: OSPFI-BGPIGP11In more detailBorder routerInternal router1. Provide internal reachability (IGP)2. Learn routes to external destinations (eBGP)3. Distribute externally learned routes internally (iBGP)4. Select closest egress (IGP)624 92133612Rest of lecture...• Motivate why BGP is the way it is– driven by two salient aspects of AS structure• Discuss some problems with interdomain routing• Discuss (briefly!) what a new BGP might look like• Explain some of BGP’s details– not fundamental, just series of specific design decisions13#1 ASes are autonomous• Want to choose their own internal routing protocol– different algorithms and metrics• Want freedom to route based on policy– “my traffic can’t be carried over my competitor’s network”– “I don’t want to carry transit traffic through my network”– not expressible as Internet-wide “shortest path”!• Want to keep their connections and policies private– would reveal business relationships, network structure714#2 ASes have business relationships• Three kinds of relationships between ASes– AS A can be AS B’s customer– AS A can be AS B’s provider– AS A can be AS B’s peer• Business implications– customer pays provider– peers don’t pay each other• Policy implications– “When sending traffic, I prefer to route through customersover peers, and peers over providers”– “I don’t carry traffic from one provider to another provider”15AS-level topology–Destinations are IP prefixes (e.g., 12.0.0.0/8)–Nodes are Autonomous Systems (ASes) internals are hidden–Links are connections & business relationships1234567Client Web server816What routing algorithm can we use?• Key issues are policy and privacy• Can’t use shortest path– domains don’t have any shared metric– policy choices might not be shortest path• Can’t use link state– would have to flood policy preferences and topology– would violate privacy17What about distance vector?• Does not reveal any connectivity information• But is designed to compute shortest paths• Extend distance vector to allow policy choices?918Path-Vector Routing• Extension of distance-vector routing–Support flexible routing policies–Faster loop detection (no count-to-infinity)• Key idea: advertise the entire path–Distance vector: send distance metric per dest d–Path vector: send the entire path for each dest d32 1d“d: path (2,1)” “d: path (1)”data trafficdata traffic19Faster Loop Detection• Node can easily detect a loop–Look for its own node identifier in the path–E.g., node 1 sees itself in the path “3, 2, 1”• Node can simply discard paths with loops–E.g., node 1 simply discards the advertisement321“d: path (2,1)” “d: path (1)”“d: path (3,2,1)”1020Flexible Policies• Each node can apply local policies–Path selection: Which path to use?–Path export: Which paths to advertise?• Examples–Node 2 may prefer the path “2, 3, 1” over “2, 1”–Node 1 may not let node 3 hear the path “1, 2”23121Selection vs Export• Selection policies– determines which paths I want my traffic to take• Export policies– determines whose traffic I am willing to carry• Notes:– any traffic I carry will follow the same path my traffictakes, so there is a connection between the two– from a protocol perspective, decisions can be arbitrary can depend on entire path (advantage of PV approach)1122IllustrationRoute selectionRoute advertisementCustomerCompetitorPrimaryBackupSelection: controls traffic out of the networkExport: controls traffic into the network23Examples of Standard Policies• Transit network:– Selection: prefer customer to peer to provider– Export: only export customer’s routes to peers• Multihomed (nontransit) network:– Export: Don’t export routes for other domains– Selection: pick primary over backup1224Any Questions?25Issues with Path-Vector Policy Routing• Reachability• Security• Performance• Lack of isolation• Policy oscillations1326Reachability• In normal routing, if graph is connected thenreachability is assured• With policy routing, this does not always hold27Security• An AS can claim to serve a prefix that they actuallydon’t have a route to (blackholing traffic)– problem not specific to policy or path vector– important because of AS autonomy• Fixable: make ASes “prove” they have a path1428Performance• BGP designed for policy not


View Full Document

Berkeley ELENG 122 - Interdomain Routing

Documents in this Course
Lecture 6

Lecture 6

22 pages

Wireless

Wireless

16 pages

Links

Links

21 pages

Ethernet

Ethernet

10 pages

routing

routing

11 pages

Links

Links

7 pages

Switches

Switches

30 pages

Multicast

Multicast

36 pages

Switches

Switches

18 pages

Security

Security

16 pages

Switches

Switches

18 pages

Lecture 1

Lecture 1

56 pages

OPNET

OPNET

5 pages

Lecture 4

Lecture 4

16 pages

Ethernet

Ethernet

65 pages

Models

Models

30 pages

TCP

TCP

16 pages

Wireless

Wireless

48 pages

Load more
Download Interdomain Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Interdomain Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Interdomain Routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?