CS3103 Computer Networks Practice PDF

CS3103: Computer Networks Practice Routing - OPSF (Open Shortest Path First) Link state routing OSPF Dr. Anand Bhojan COM3-02-49, School of...

CS3103: Computer Networks Practice Routing - OPSF (Open Shortest Path First) Link state routing OSPF Dr. Anand Bhojan COM3-02-49, School of Computing [email protected] ph: 651-67351 [email protected] Routing Protocols  Distance Vector Routing  Link State Routing Let us start with a QUIZ: https://pollev.com/banand Make sure you LOGIN using your NUSNET ID. 2 CS3103/(c) Anand Bhojan 10/7/2024 LINK STATE ROUTING In distance vector (DV) routing, router knows only cost to each destination o hides information, causing problems In link state (LS) routing, router knows entire network topology o computes shortest path by itself using well known algorithm - Dijkstra’s algorithm o independent computation of routes Concept of Link state routing Forming shortest path tree for router A in a graph (Dijsktra’s Algorithm) … Continued … Continued Iteration Destination added to Candiadte List Shortest Path Destination (cost, next hop) 1 A (0,A) B (2,B) (Another Example) C(5,C) D(1,D) 2 A (0,A) B(2,B,; 3, D-B) D(1,D) C(5,C; 10, D-C) E(10, D-E) 5 3 A (0,A) C(5,C; 10, D-C; 5,B-C) B C D(1,D) E(10, D-E) Router 3 Router B(2,B) 2 5 F 4 A (0,A) E(10, D-E; 6,C-E) Router 2 9 Router D(1,D) F(10,C-F) A 1 B(2,B) 1 C(5,C) Router 9 2 Router 5 A (0,A) F(10,C-F; 8, C-E-F) D E D(1,D) B(2,B) C(5,C) E(6, C-E) Shortest path (SP) to every destination in the network can be 6 A (0,A) D(1,D) calculated using Dijsktra’s SP B(2,B) C(5,C) Algorithm E(6, C-E) F(8, C-E-F) Dijkstra’s Algorithm  Let Di be shortest path length from node i to node S where, S is start node. [Initially Di ’s are infinite (unknown)]  Let cij be the cost of link (i,j); infinity if (i,j) is not an arc of the graph  Initialise P(path) = {S}, Ds = 0, Dj = cjs for j not equal to S  Step 1 (Find closest node): Find i not in P such that  Di = min j not in P Dj, set P = P U {i}.  If P contains all nodes, END  Step 2 (Update Dj): For all j not in P  Dj = min [Dj,cji+Di], goto step 1 Q: The entire network topology should be known to compute shortest path & build routing table. How routers learn about the entire network topology? OSPF The Open Shortest Path First (OSPF) protocol is an intradomain routing protocol based on link state routing. Its domain is also an autonomous system (AS). Key elements topology dissemination uses link state routing to compute shortest routes Some additional materials from reference book: Computer Networking A Top Down Approach Featuring the Internet- by James Kurose and Keith Ross, Addison Wesley, 6rd Edition Areas in an autonomous system Within an OSPF area, all routers maintain the same topology database; they have no knowledge of network topology outside the area; Area Border Routers (ABRs) and AS Boundary Routers (ASBRs) summarize information about the area and send it to other areas. Area concept limits the amount of link-state info exchanged (flooded), size of database stored, and amount of processing carried out by each router.  PGP SoC core (Layer 3) C FYI Overview C Border1-CC-L3 only core-j core-k HSRP Vlan 211 OSPF area 3 standby IP OSPF OSPF area 0 COM3 area 71 COM0 core-P CZ Firewall E &F standby IP Vlan 213 HSRP core-e core-e core-f OSPF core-f OSPF area 1 area 2 COM1 COM2 x.x.x.x/30 x.x.x.x/30 Vlan 200 Vlan 400 core-g x.x.x.x/30 x.x.x.x/30 core-h core-m core-n OSPF (cont)  Every Router in an area computes the shortest path to every other router  Two problems in building OSPF routing table  PROBLEM 1: to determine a router’s local environment  PROBLEM 2: to exchange information with the rest of the routers to maintain identical database that define the Network Topology OSPF (cont)  Local environment information:  neighboring routers  links to connected networks  cost of the links (metric) - delay, $ cost, transmission time, max throughput, etc.,  Link-state protocol:  link-state packets are sent to all routers in the area.  they contain list of network links (links to networks and routers) and their associated costs  RFC 2328 Prob. 1: Neighbour Discovery and Maintenance  Who are the neighbors is found out by Hello messages.  For every network interface a router has, Hello messages are generated. Content includes  router’s IP address for that interface, subnet mask (a.b.c.d/n)  Hello interval  a list of neighbors whose Hellos the sender has already heard.  Hellos are multicast to all OSPF routers using the address 224.0.0.5 every 10 secs. Tests the status of link to its neighbors.  Failure to receive any Hellos from a neighbor for 40 secs - link to that neighbor failed or that neighbor crashed.  Hello, IP1/24, Ø N1 R1’s Routing Table N1 IP1 U IP1 N2 IP2 U R1 IP2 Hello, IP3/24, Ø N2 R2’s Routing Table Hello, IP2/24, R2 N2 IP3 U Hello, IP5/24, Ø IP3 N3 IP4 U IP5 N4 IP5 U R2 N4 IP4 Hello, IP4/24, Ø N3 Prob. 2: Exchange of Link-state Information  Each entity in an area (eg., a router, a broadcast network/ ABR) distributes information about its local environment in packets called Link State Advertisements (LSAs). Prob. 2: Exchange of Link-state Information ◼ LSA’s are normally sent only under the following circumstances: ◼ a router discovers a new neighbor ◼ a link to a neighbor goes down ◼ cost of a link changes ◼ basic refresh packets are sent every 30min ◼ LSAs are distributed to all routers in the area by reliable flooding - to synchronize ◼ explicitly ACKed, sequenced, and time-stamped Example (Cont’d) N1 R1’s Routing Table N1 IP1 U IP1 N2 IP2 U R1 LSA: R1 R1’s LSA Database R2 on N2 (cost), IP2 R1 LSA: … N1 (cost) R2 LSA: … N2 R2 LSA: R2’s Routing Table R1 on N2 (cost), N2 IP3 U N3 (cost), IP3 N4 (cost) N3 IP4 U IP5 N4 IP5 U R2 N4 IP4 R2’s LSA Database R1 LSA: … Note: R1, R2 R2 LSA: … N3 are in same OSPF Area  R1’s Routing Table N1 N1 IP1 U N2 IP2 U N3 IP3 UG IP1 N4 IP3 UG R1 R1’s LSA Database IP2 R1 LSA: … R2 LSA: … N2 R2’s Routing Table N2 IP3 U N3 IP4 U IP3 N4 IP5 U IP5 R2 N4 N1 IP2 UG IP4 R2’s LSA Database R1 LSA: … R2 LSA: … N3  R1’s Routing Table N1 N1 IP1 U N2 IP2 U IP1 N3 IP3 UG R1 N4 IP3 UG IP2 R1’s LSA Database R3’s Routing Table R1 LSA: … N4 IP6 U R2 LSA: … N5 IP7 U N2 R2’s Routing Table N2 IP3 U N3 IP4 U IP3 N4 IP5 U IP5 R2 N4 IP6 N1 IP2 UG IP4 R3 R2’s LSA Database IP7 R1 LSA: … R2 LSA: … N3 N5  R1’s Routing Table N1 N1 IP1 U N2 IP2 U IP1 N3 IP3 UG R1 N4 IP3 UG IP2 R1’s LSA Database R3’s Routing Table R1 LSA: … N4 IP6 U R2 LSA: … N5 IP7 U N2 R2’s Routing Table N2 IP3 U Hello, IP6/24, Ø N3 IP4 U IP3 N4 IP5 U IP5 R2 N4 IP6 N1 IP2 UG IP4 R3 R2’s LSA Database IP7 R1 LSA: … R2 LSA: … N3 Hello, IP7/24, Ø N5  R1’s Routing Table N1 IP1 U N1 R3’s LSA Database N2 IP2 U R1 LSA: … N3 IP3 UG N4 IP3 UG R2 LSA: … IP1 R3 LSA: … N5 IP3 UG R1 R3’s Routing Table R1’s LSA Database IP2 N4 IP6 U R1 LSA: … N5 IP7 U R2 LSA: … N1 IP5 UG R3 LSA: … N2 IP5 UG N2 N3 IP5 UG R2’s Routing Table N2 IP3 U N3 IP4 U N4 IP5 U IP3 N1 IP2 UG IP5 N5 IP6 UG R2 N4 IP6 IP4 R3 R2’s LSA Database IP7 R1 LSA: … R2 LSA: … R3 LSA: … N3 N5 Quiz Make sure you LOGIN using your NUSNET ID. https://pollev.com/banand 24 CS3103/(c) Anand Bhojan 10/7/2024 OSPF (cont) For your own reading  Every router in an area receives the LSAs generated by other routers in the area (that contain the respective router’s local environment information) and builds a database of LSAs that describes the topology of the area.  The database of LSAs maintained by all routers in an area are identical.  Each router then constructs the shortest path with itself as the root and using metric as the cost, to build its routing table. OSPF (cont) Hello Packets Adjacency DB Share copies of LSAs Link State DB Apply Dijkstra’s Algorithm Incoming Forwarded Forwarding Table Packets Packets OSPF uses IP directly IP datagram OSPF packet IP Header OSPF Header Hello packet body 20 bytes 24 bytes IP datagram OSPF packet IP Header OSPF Header LSA Header LSA body 20 bytes 24 bytes 20 bytes Types of OSPF packets Link State Advertisements (LSAs). Hello messages and LSAs are encapsulated in OSPF packets for transmission Transient Link  In a Transient link (Network with multiple routers) lots of LSAs messages are flooded to synchronize the LSA databases.  Q: Can we minimize this traffic? Other OSPF links R1 R2 R3 10.4.7.2 10.4.7.1 10.4.7.3 Transient link 10.4.7.4 10.4.7.5 R4 R5 Other OSPF links Other OSPF links 29 CS3103/(c) Anand Bhojan 10/7/2024  Transient Link In a Transient link (network with Other OSPF links several routers attached to it), Instead of each router flooding the entire network with LSAs, they only send it to the DR and R1 R2 R3 BDR. 10.4.7.2 10.4.7.1 10.4.7.3 That is, each router will have only 10.4.7.4 10.4.7.5 DR and BDR as neighbor.The DR and BDR will have all routers in R4 R5 the network as neighbors. Other OSPF links Other OSPF links Eg. If R5 receives a LSA from 10.4.7.1 other OSPF link then it conveys the same to DR and BDR using 224.0.0.6 multicast address 10.4.7.2 10.4.7.3 BDR DR Q: DR/BDR 10.4.7.4 10.4.7.5 election policy? Initialising DB for a Newly Joining Router in transient Link Link State Advertisements (LSAs). 1. DR sends a summary of its database of LSAs to the new router - database description packets 2. The new router responds with a list of LSAs that it does not have or that are outdated - link-state request packet 3. DR forwards the full LSAs in the list to the new router - link-state update (or Network Link Advertisement) packet 4. New router responds with link-state-ACK packet 5. After initialisation, the newly joined router's new LSA should be sent to all routers in the area. First the new router sends its LSA to DR and BDR. Then, DR, DBR multicasts them to other routers. 31 CS3103/(c) Anand Bhojan 10/7/2024 Other LSAs LSAs In general, it is Router Link LSA or Network Link LSA Router Link LSA is sent by every router in the area In this LSA you will find a list with all the directly connected links of this router. Network Link LSA is sent by DR or BDR only in a Transient link In this LSA we will find all the routers that are connected to the Transient link. OTHER LSAs Summary Link to Network Provide information on routers/networks outside the area, provided by ABR. [Note: within same AS] Summary Link to AS Boundary Router What is this for? (Flooded to all routers by ABR) External Link Information about network outside the AS Types of links Link Type Description Link ID Point-to-point connection to 1 – Point-to-Point Neighbor router ID another router. 2 – Transient Connection to transit network. IP address of DR 3 – Stub Connection to stub network. IP Network 4 – Virtual Virtual Link Neighbor router ID Q: What is the use of Virtual Link? Routing Information maintained at Router  Router maintains much more information than a host system.  The routing table on the following page is that of router 137.132.90.1.  Only a part of the table is given below.  Please note some sub-subnet destination network addresses.  Observe that network mask is stored as part of the information. -------------------------------IP Routing Table-------------------------------- Total Routes = 185, Total Direct Networks = 5 Destination Mask Gateway Metric Status TTL Source 137.132.1.0 255.255.255.0 137.132.90.253 2 Up -- OSPF-Inter-* 137.132.2.0 255.255.255.224 137.132.90.253 12 Up -- OSPF-Inter-* 137.132.2.32 255.255.255.224 137.132.90.253 22 Up -- OSPF-Inter-* 137.132.2.64 255.255.255.224 137.132.90.253 7 Up -- OSPF-Inter-* 137.132.4.0 255.255.255.0 137.132.90.253 12 Up -- OSPF-Inter-* 137.132.84.0 255.255.255.0 137.132.90.253 12 Up -- OSPF-Inter-* 137.132.85.0 255.255.255.0 137.132.90.254 11 Up -- OSPF-Intra-* 137.132.90.253 11 Up -- OSPF-Intra-* 137.132.86.0 255.255.255.0 137.132.90.254 11 Up -- OSPF-Intra-* 137.132.90.253 11 Up -- OSPF-Intra-* 137.132.87.0 255.255.255.0 137.132.90.254 11 Up -- OSPF-Intra-* 137.132.90.253 11 Up -- OSPF-Intra-* 37.132.88.0 255.255.255.0 137.132.88.1 0 Up -- Connected 137.132.89.0 255.255.255.224 137.132.89.1 0 Down -- Connected 137.132.89.64 255.255.255.224 137.132.89.65 0 Down -- Connected 137.132.90.0 255.255.255.0 137.132.90.1 0 Up -- Connected 137.132.91.0 255.255.255.0 137.132.91.1 0 Up -- Connected 137.132.92.0 255.255.255.0 137.132.90.253 12 Up -- OSPF-Inter-* 137.132.98.0 255.255.255.0 137.132.90.253 2 Up -- OSPF-Inter-* Quiz Make sure you LOGIN using your NUSNET ID. https://pollev.com/banand 36 CS3103/(c) Anand Bhojan 10/7/2024 Summary  OSPF Uses Dijkestra’s Algorithm to find SP from Source to All nodes  To use Dijkestra’s algorrithm, the Network Topology should be known.  Hello to Discover Neighbours  Link-State Protocol is used to share the Link States  Database of Link States (LSAs), describes the Topology  In transient networks, normal routers send LSAs to only DR and BDR. DR/BDR sends LSAs to all Routers. Reminder: Assignment 4 will be released soon! Group Work END Anand Bhojan/CS3103/Sem-2/2013-14 37