清华大学：《计算机网络》课程教学资源（PPT课件讲稿）Lecture 4 Routing

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