DOC PREVIEW
Berkeley COMPSCI 268 - Lecture Notes

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 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 24 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 24 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 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 268: Computer NetworkingL-3 BGP2Next Lecture: Interdomain Routing• BGP• Assigned Reading• MIT BGP Class Notes• [Gao00] On Inferring Autonomous SystemRelationships in the Internet3Outline• Need for hierarchical routing• BGP• ASes, Policies• BGP Attributes• BGP Path Selection• iBGP• Inferring AS relationships• Problems with BGP• Convergence• Sub optimal routing4Routing Hierarchies• Flat routing doesn’t scale• Each node cannot be expected to have routesto every destination (or destination network)• Key observation• Need less information with increasing distanceto destination• Two radically different approaches forrouting• The area hierarchy• The landmark hierarchy5Areas• Divide network into areas• Areas can have nestedsub-areas• Constraint: no pathbetween two sub-areas ofan area can exit that area• Hierarchically addressnodes in a network• Sequentially number top-level areas• Sub-areas of area arelabeled relative to that area• Nodes are numberedrelative to the smallestcontaining area1 231.11.22.12.23.13.22.2.12.2.21.2.11.2.26Routing• Within area• Each node has routes to every other node• Outside area• Each node has routes for other top-level areasonly• Inter-area packets are routed to nearestappropriate border router• Can result in sub-optimal paths7Path Sub-optimality1 231.11.22.12.23.13.22.2.13 hop red pathvs.2 hop green pathstartend3.2.11.2.1A Logical View of the Internet8Tier 1 Tier 1Tier 2Tier 2Tier 2Tier 3• National (Tier 1 ISP)– “Default-free” with globalreachability infoEg: AT & T, UUNET, Sprint• Regional (Tier 2 ISP)– Regional or country-wideEg: Pacific Bell• Local (Tier 3 ISP)Eg: Telerama DSLCustomerProvider9•Source wants to reachLM0[a], whose address isc.b.a:•Source can see LM2[c], sosends packet towards c•Entering LM1[b] area, firstrouter diverts packet to b•Entering LM0[a] area,packet delivered to a•Not shortest path•Packet may not reachlandmarksLandmark Routing: Basic IdeaLM2[c]LM1[b]r0[a]LM0[a]r2[c]r1[b]Network NodePathLandmarkRadius10Landmark Routing: Exampled.d.ad.d.bd.d.cd.d.ed.d.dd.d.fd.i.kd.i.gd.d.jd.i.id.i.wd.i.ud.d.kd.d.ld.n.hd.n.xd.n.nd.n.od.n.pd.n.qd.n.td.n.sd.n.rd.i.v11Routing Table for Router gLandmark Level Next hopLM2[d]LM0[e]LM1[i]LM0[k]LM0[f]21000fkfkfRouter gRouter tr0 = 2, r1 = 4, r2 = 8 hops• How to go from d.i.g tod.n.t? g-f-e-d-u-t• How does path lengthcompare to shortest path?g-k-I-u-td.d.ad.d.bd.d.cd.d.ed.d.dd.d.fd.i.kd.i.gd.d.jd.i.id.i.wd.i.ud.d.kd.d.ld.n.hd.n.xd.n.nd.n.od.n.pd.n.qd.n.td.n.sd.n.r12Outline• Need for hierarchical routing• BGP• ASes, Policies• BGP Attributes• BGP Path Selection• iBGP• Inferring AS relationships13Autonomous Systems (ASes)• Autonomous Routing Domain• Glued together by a common administration, policies etc• Autonomous system – is a specific case of an ARD• ARD is a concept vs AS is an actual entity that participates inrouting• Has an unique 16 bit ASN assigned to it and typically participatesin inter-domain routing• Examples:• MIT: 3, CMU: 9• AT&T: 7018, 6341, 5074, …• UUNET: 701, 702, 284, 12199, …• Sprint: 1239, 1240, 6211, 6242, …• How do ASes interconnect to provide global connectivity• How does routing information get exchangedNontransit vs. Transit ASes14ISP 1ISP 2Nontransit ASmight be a corporateor campus network.Could be a “contentprovider”NET ATraffic NEVER flows from ISP 1through NET A to ISP 2(At least not intentionally!)IP trafficCustomers and Providers15Customer pays provider for access to the InternetprovidercustomerIP trafficprovider customerThe Peering Relationship16peer peercustomerproviderPeers provide transit between their respective customersPeers do not provide transit between peersPeers (often) do not exchange $$$trafficallowedtraffic NOTallowedABC17Peering Wars• Reduces upstream transitcosts• Can increase end-to-endperformance• May be the only way toconnect your customersto some part of theInternet (“Tier 1”)• You would rather havecustomers• Peers are usually yourcompetition• Peering relationships mayrequire periodicrenegotiationPeering struggles are by far the most contentious issues in the ISP world!Peering agreements are often confidential.Peer Don’t Peer18Routing in the Internet• Link state or distance vector?• No universal metric – policy decisions• Problems with distance-vector:• Bellman-Ford algorithm may not converge• Problems with link state:• Metric used by routers not the same – loops• LS database too large – entire Internet• May expose policies to other AS’s19Solution: Distance Vector with Path• Each routing update carries the entire path• Loops are detected as follows:• When AS gets route check if AS already in path• If yes, reject route• If no, add self and (possibly) advertise route further• Advantage:• Metrics are local - AS chooses path, protocolensures no loopsBGP-4• BGP = Border Gateway Protocol• Is a Policy-Based routing protocol• Is the EGP of today’s global Internet• Relatively simple protocol, but configuration iscomplex and the entire world can see, and beimpacted by, your mistakes.201989 : 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)BGP Operations (Simplified)21Establish session on TCP port 179 Exchange all active routes Exchange incremental updatesAS1AS2While connection is ALIVE exchangeroute UPDATE messagesBGP session22Interconnecting BGP Peers• BGP uses TCP to connect peers• Advantages:• Simplifies BGP• No need for periodic refresh - routes are valid untilwithdrawn, or the connection is lost• Incremental updates• Disadvantages• Congestion control on a routing protocol?• Inherits TCP vulnerabilities!• Poor interaction during high loadFour 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 orwithdrawing previously announced routes.23announcement = prefix + attributes values24Policy with BGP• BGP provides capability for enforcing various policies• Policies are not part of BGP: they are provided to BGP asconfiguration information• BGP enforces policies by choosing paths from multiplealternatives and controlling advertisement to other


View Full Document

Berkeley COMPSCI 268 - Lecture Notes

Documents in this Course
Lecture 8

Lecture 8

33 pages

L-17 P2P

L-17 P2P

50 pages

Multicast

Multicast

54 pages

Load more
Download Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?