Routes from node a Table for a Dest CostNext 上 3 op ABCDEF 046725 ABEBEE 6 3 D A 4 Properties Some set of shortest paths forms tree Shortest path spanning tree for each node Solution not unique 2021/2/8 * E.g, A-E-F-C-D also has cost 7
Routes from Node A Properties Some set of shortest paths forms tree Shortest path spanning tree for each node Solution not unique 2021/2/8 E.g., A-E-F-C-D also has cost 7 11 A E F C D B 2 3 6 4 1 1 1 3 Table for A Dest Cost Next Hop A 0 A B 4 B C 6 E D 7 B E 2 E F 5 E
Ways to Compute Shortest Paths centralized Collect graph structure in one place Use standard graph algorithm Disseminate routing tables Partially Distributed Every node collects complete graph structure Each computes shortest paths from it Each generates own routing table * "Link-state"algorithm 2021/2/8 12
Ways to Compute Shortest Paths Centralized Collect graph structure in one place Use standard graph algorithm Disseminate routing tables Partially Distributed Every node collects complete graph structure Each computes shortest paths from it Each generates own routing table “Link-state” algorithm 2021/2/8 12
Ways to Compute Shortest Paths (Cont Fully Distributed No one has copy of graph Nodes construct their own tables iteratively k each sends information about its table to neighbors *“ Distance-Vector” algorithn 2021/2/8 3
Ways to Compute Shortest Paths (Cont.) Fully Distributed No one has copy of graph Nodes construct their own tables iteratively Each sends information about its table to neighbors “Distance-Vector” algorithm 2021/2/8 13
Internet Routing Internet organized as a two level hierarchy First level-autonomous systems (ASs) as-region of network under a single administrative domain ASs run an intra-domain routing protocols Distance Vector, e.g., Routing Information Protocol (RIP) Link State, e.g., Open Shortest Path First(OSPF) Between AS's runs inter-domain routing protocols, e.g., Border gateway Routing(BGP) De facto standard today, BGP-4 2021/2/8 14
Internet Routing Internet organized as a two level hierarchy First level – autonomous systems (AS’s) AS – region of network under a single administrative domain AS’s run an intra-domain routing protocols Distance Vector, e.g., Routing Information Protocol (RIP) Link State, e.g., Open Shortest Path First (OSPF) Between AS’s runs inter-domain routing protocols, e.g., Border Gateway Routing (BGP) De facto standard today, BGP-4 2021/2/8 14
Exampl ple Interior router BGP router 国 S-3 AS-2 2021/2/8 15
Example 2021/2/8 15 AS-1 AS-2 AS-3 Interior router BGP router