DOC PREVIEW
Berkeley COMPSCI 268 - Lecture Notes

This preview shows page 1-2-3-22-23-24-45-46-47 out of 47 pages.

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

Unformatted text preview:

CS 268 Computer Networking L 3 BGP Next Lecture Interdomain Routing BGP Assigned Reading MIT BGP Class Notes Gao00 On Inferring Autonomous System Relationships in the Internet 2 Outline Need for hierarchical routing BGP ASes Policies BGP Attributes BGP Path Selection iBGP Inferring AS relationships Problems with BGP Convergence Sub optimal routing 3 Routing Hierarchies Flat routing doesn t scale Each node cannot be expected to have routes to every destination or destination network Key observation Need less information with increasing distance to destination Two radically different approaches for routing The area hierarchy The landmark hierarchy 4 Areas Divide network into areas 1 2 2 1 1 1 2 2 2 2 2 2 2 1 1 2 1 2 1 1 2 2 3 3 1 3 2 Areas can have nested sub areas Constraint no path between two sub areas of an area can exit that area Hierarchically address nodes in a network Sequentially number toplevel areas Sub areas of area are labeled relative to that area Nodes are numbered relative to the smallest containing area 5 Routing Within area Each node has routes to every other node Outside area Each node has routes for other top level areas only Inter area packets are routed to nearest appropriate border router Can result in sub optimal paths 6 Path Sub optimality 1 2 2 1 1 1 2 2 2 2 1 1 2 1 2 1 start end 3 2 1 3 3 hop red path vs 2 hop green path 3 1 3 2 7 A Logical View of the Internet National Tier 1 ISP Default free with global reachability info Eg AT T UUNET Sprint Regional Tier 2 ISP Regional or country wide Eg Pacific Bell Local Tier 3 ISP Tier 3 Tier 2 Tier 2 Customer Provider Tier 1 Tier 1 Eg Telerama DSL Tier 2 8 Landmark Routing Basic Idea Source wants to reach LM0 a whose address is c b a Source can see LM2 c so sends packet towards c Entering LM1 b area first router diverts packet to b Entering LM0 a area packet delivered to a Not shortest path Packet may not reach landmarks r1 b LM0 a r0 a LM1 b LM2 c r2 c Network Node Path Landmark Radius 9 Landmark Routing Example d d f d i k d i g d d e d i i d d d d d a d i w d d j d d b d i v d d c d d l d d k d i u d n h d n x d n t d n n d n q d n s d n o d n p d n r 10 Routing Table for Router g Landmark Level Next hop LM2 d LM1 i 2 1 f LM0 e 0 f LM0 k LM0 f 0 0 k k d d f Router g d d e f d i i d d d d d a d i k d i g d i w d d j r0 2 r1 4 r2 8 hops How to go from d i g to d n t g f e d u t How does path length compare to shortest path g k I u t d d b d d c d d l d d k d n h d i u d n x Router t d n t d n n d n q d n s d n o d n p d n r 11 Outline Need for hierarchical routing BGP ASes Policies BGP Attributes BGP Path Selection iBGP Inferring AS relationships 12 Autonomous 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 in routing Has an unique 16 bit ASN assigned to it and typically participates in 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 exchanged 13 Nontransit vs Transit ASes ISP 2 ISP 1 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 14 Customers and Providers provider provider customer IP traffic customer Customer pays provider for access to the Internet 15 The Peering Relationship A peer provider B peer customer C Peers provide transit between their respective customers Peers do not provide transit between peers traffic allowed traffic NOT allowed Peers often do not exchange 16 Peering Wars Peer Reduces upstream transit costs Can increase end to 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 17 Routing 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 s 18 Solution 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 protocol ensures no loops 19 BGP 4 BGP Border Gateway Protocol Is a Policy Based routing protocol Is the 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 1989 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 20 BGP Operations Simplified Establish session on TCP port 179 AS1 BGP session Exchange all active routes AS2 Exchange incremental updates While connection is ALIVE exchange route UPDATE messages 21 Interconnecting BGP Peers BGP uses TCP to connect peers Advantages Simplifies BGP No need for periodic refresh routes are valid until withdrawn or the connection is lost Incremental updates Disadvantages Congestion control on a routing protocol Inherits TCP vulnerabilities Poor interaction during high load 22 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 23 Policy with BGP BGP provides capability for enforcing various policies Policies are not part of BGP they are provided to BGP as configuration information BGP enforces policies by choosing paths from multiple alternatives and controlling advertisement to other AS s Import policy What to do with routes learned …


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?