Lecture 4 Routing Dan li CS Department, Tsinghua University 2021/1/31
Lecture 4 Routing 2021/1/31 1 Dan LI CS Department, Tsinghua University
Today's Lecture Inter-Domain Routing Reading list 2021/1/31
Today’s Lecture Inter-Domain Routing Reading list 2021/1/31 2
Inter-Domain Routing Routing hierarchy Internet structure EXternal BGP(E-BGP) Internal BGP (I-BGP 2021/1/31
Inter-Domain Routing Routing hierarchy Internet structure External BGP (E-BGP) Internal BGP (I-BGP) 2021/1/31 3
Routing Hierarchies Flat routing doesn'tscale Storage> Each node cannot be expected to store routes to every destination (or destination network) Convergence times increase Communication Total message count increases w Key observation Need less information with increasing distance to destination k Need lower diameters networks Solution area hierarchy 2021/1/31 4
Routing Hierarchies Flat routing doesn’t scale Storage → Each node cannot be expected to store routes to every destination (or destination network) Convergence times increase Communication → Total message count increases Key observation Need less information with increasing distance to destination Need lower diameters networks Solution: area hierarchy 2021/1/31 4
Areas Divide network into areas k areas can have nested sub-areas Hierarchically address nodes in a network Sequentially number top-level areas k Sub-areas of area are labeled relative to that area k nodes are numbered relative to the smallest containing area 2021/1/31
Areas Divide network into areas Areas can have nested sub-areas Hierarchically address nodes in a network Sequentially number top-level areas Sub-areas of area are labeled relative to that area Nodes are numbered relative to the smallest containing area 2021/1/31 5
Area Hierarchy Addressing 2 2.1 2.2 222 1.2 22 121 1.22 3.1 3.2 2021/1/31
Area Hierarchy Addressing 2021/1/31 6 1 2 3 1.1 1.2 2.1 2.2 3.1 3.2 2.2.1 2.2.2 1.2.1 1.2.2
Routing Hierarchy Area-Border Backbone areas Router Lower-evel areas Partition Network into“ Areas” k Within area k each node has routes to every other node k Outside area Each node has routes for other top-level areas only Inter-area packets are routed to nearest appropriate border router Constraint: no path between two sub-areas of an area can 2021/1/exit that area
Routing Hierarchy Partition Network into “Areas” 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 Constraint: no path between two sub-areas of an area can 2021/1/31exit that area 7 Backbone Areas Lower-level Areas Area-Border Router
Path Sub-optimality 2 2.2 1.1 1.2 ×22 start end 3.2.1 3 hop red path VS 3.1 3.2 2 hop green path 2021/1/31
Path Sub-optimality 2021/1/31 8 8 1 2 3 1.1 1.2 2.1 2.2 3.1 3.2 2.2.1 3 hop red path vs. 2 hop green path start end 3.2.1 1.2.1
Inter-Domain Routing Routing hierarchy Internet structure EXternal BGP(E-BGP) Internal BGP (I-BGP 2021/1/31
Inter-Domain Routing Routing hierarchy Internet structure External BGP (E-BGP) Internal BGP (I-BGP) 2021/1/31 9
Internet's Area Hierarchy What is an autonomous System (As)? *a set of routers under a single technical administration Using an interior gateway protocol( GP)and common metrics to route packets within the as Using an exterior gateway protocol(EGP)to route packets to other AS's Sometimes AS's use multiple iGPs and metrics but appear as single as's to other Ass k Each as assigned unique ID AS's peer exchanges information 2021/1/31
Internet’s Area Hierarchy What is an Autonomous System (AS)? A set of routers under a single technical administration Using an interior gateway protocol (IGP) and common metrics to route packets within the AS Using an exterior gateway protocol (EGP) to route packets to other AS’s Sometimes AS’s use multiple IGPs and metrics, but appear as single AS’s to other AS’s Each AS assigned unique ID AS’s peer exchanges information 2021/1/31 10