Home | Reports | Technical Documents | Tech-Blog | One-Shot Gallery | Korea ICT News | Korea Communication Market Data | List of Contributors | Become a Contributor |    
 
 
Section 5G 4G LTE C-RAN/Fronthaul Gigabit Internet IPTV/Video Streaming IoT SDN/NFV Wi-Fi KT SK Telecom LG U+ Network Protocol Samsung   Korean Vendors
 
CHANNELS     HFR    |  Mobile Fronthaul Solution  |  Carrier Ethernet Solution  | Resources        
CHANNELS     ZARAM    |  XGSPON 10G SFP+ ONT  |  Use cases  | Evolution of FTTH Access Network    

 

Quick Guide to OSPF: Part 1. Building Shortest Path Tree Topology
May 06, 2015 | By Chris Yoo (tech@netmanias.com)
Online viewer:
Comments (1)
11

Quick Guide to OSPF

 1. Building Shortest Path Tree Topology

    2. Redistributing External Network Routes into OSPF Network

 

This time, we will discuss how routers discover IP network topologies and build shortest path trees by using OSPF protocols.

Certainly, routing protocols like OSPF are based on operating principles that are hard to understand if you are not a routing expert. Many people are quite good at routing configuration using Command Line Interface (CLI), but only a few fully understand the operating principles of the protocols. To help you, routing novices, understand OSPF better, below we have provided lots of easy-to-understand illustrations.  

 

 

OSPF network topology

 

 

In the figure, there are five OSPF routers (R1 ~ R5), along with their respective interface IP address, OSPF cost and loopback address (e.g. 10.1.0.1 for R1).

  • Here OSPF cost means cost needed to deliver a packet to each link. From OSPF's perspective, a least cost path is the shortest path. In general, the cost of a link is determined based on its bandwidth. For example, the cost of 100Mbps link is greater than that of 1GE link, and the cost of 1GE of greater than that of 10GE (The system operator of a network configures link costs for each interface in a router, by using CLI)
  • In order for routers to exchange OSPF messages with each other, IP addresses for identifying routers (OSPF RID (Router ID)) are required. For the purpose, loopback addresses are usually used. IP addresses of physical links can also be used, but loopback addresses are preferred for the following reasons:
    • If a physical link IP address is used: The IP address disappears when the physical link is down. That is, an OSPF router that uses this address as OSPF RID can no longer communicate with its connected neighbor OSPFs.
    • If a loopback IP address is used: The IP address remains valid even when the physical link is down because loopback addresses are logical addresses that are not bound to a certain physical link.

 

Routers flooding their link IP addresses to other routers

 

1. R1 floods its link information to neighbor OSPF routers

 

 

R1 floods its link (interface) address and loopback address to R2 and R3, through Router-LSA message [t=1]. Upon receiving the message, R2 and R3 flood it through all the links except the one that the message was sent through, having both R4 and R5 receive the same Router-LSA message twice [t=2]. At this time, if the two messages have the same LSA identifiers, {LS Type, Link State ID, Advertising Router}, the one that arrived later is discarded.

  • LS Type: Identifies Router-LSA (1), Network-LSA (2), External-LSA (5), etc.
  • Link State ID: Same as Advertising Router value (10.1.0.1) in case of Router-LSA
  • Advertising Router: ID of the router that originated generated Router-LSA (OSPF RID, i.e. loopback address = 10.1.0.1) 

The Router-LSA message sent by R1 includes (see the table in the upper right corner of the figure above):

  • Link Type: Identifies link types. Values for Link ID and Link Data are determined according to this value.
    • Link Type = 1: Point-to-point connection (all the routers in the figure have this type of connection)
    • Link Type = 3: Stub network (loopback address of router)
  • Link ID
    • In case of Link Type = 1, Link ID is the Router ID of the OSPF Neighbor connected to R1 (Neighbor RIDs are known to each other while OSPF Neighbors exchange Hello message)
    • In case of Link Type = 3, Link ID is the loopback address of R1 
  • ​Link Data
    • ​In case of Link Type = 1, Link Data is the link IP address of R1
    • In case of Link Type = 3, Link Data is the subnet mask of R1's loopback address (/32 = 255.255.255.255)

Upon arrival of the Router-LSA message sent by R1, the receiving routers (i.e. R2 ~R5 here) store the information in their respective OSPF Link State DataBase (LSDB), and build an OSPF topology based on the information. With the information available so far, the routers now know: 

  • R1's loopback address (10.1.0.1/32)
  • R1's link address 1.1.1.1 is connected to R2 (10.1.0.2)
  • R1's link address 1.1.2.1 is connected to R3 (10.1.0.3)
 
2. R2 floods its link information to neighbor OSPF routers
 

 

R2 floods its link (interface) address and loopback address to R1, R4 and R5, through Router-LSA message [t=1]. Upon receiving the message, R1, R4 and R5 flood it through all the links except the one that the message was sent through [t=2].
R1, R3, R4 and R5 store the information (Router-LSA) in their respective LSDB. Now another "OSPF network topology" is obtained as seen in the figure above.
 
3. R3 floods its link information to neighbor OSPF routers
 

 

Again, R3 floods its link (interface) address and loopback address to R1, R4 and R5, through Router-LSA message [t=1]. Upon receiving the message, R1, R4 and R5 flood it through all the links except the one that the message was sent through [t=2].

R1, R2, R4 and R5 store the information (Router-LSA) in their respective LSDB. Now again another "OSPF network topology" is obtained as seen in the figure above.

 

4. R4 floods its link information to neighbor OSPF routers

 

 

R4 floods its link (interface) address and loopback address to R2 and R3, through Router-LSA message [t=1]. Upon receiving the message, R2 and R3 flood it through all the links except the one that the message was sent through [t=2].
R1, R2, R3 and R5 store the information (Router-LSA) in their respective LSDB. Now again, another "OSPF network topology" is obtained as seen in the figure above.

 

5. R5 floods its link information to neighbor OSPF routers

 

 

Same thing again. R5 floods its link (interface) address and loopback address to R2, and R3, through Router-LSA message [t=1]. Upon receiving the message, R2 and R3 flood it through all the links except the one that the message was sent through [t=2].
R1 ~ R4 store the information (Router-LSA) in their respective LSDB. Now another "OSPF network topology" is obtained as seen in the figure above.

 

Note 1: In real networks, all routers flood their Router-LSA to their neighbor OSPFs all at the same time. In this post, however, we assumed all the flooding are sequential, for easier understanding.
Note 2: In order for routers to send Router-LSA, their link types should be configured as point-to-point. If configured otherwise (e.g. broadcast), Network-LSA is sent instead. Most of link connections among routers are of point-to-point type. So, we will not further discuss other types of link connections than point-to-point as this particular post is for routing novices like you.

 

 

Routers building OSPF Topologies

 

 

As a result of exchanging Router-LSA messages with each other, all the five OSPF routers end up having the same LSDB, and thus the same OSPF topology map built based on the LSDB as seen above.

 

 

Calculating shortest path tree

 

 

Using the OSPF topology generated above, each router calculates the shortest path tree, i.e. the shortest path to their respective destinations. The shortest path information is installed at the Routing Information Base (RIB) and Forwarding Information Base (FIB) of each router (Note: RIB is a routing table managed in the control plane where routing protocols like OSPF are used while FIB is a routing table located in the data plane where wire-speed packet forwarding by packet processors takes place).

 

 

Achille Foti 2015-05-16 22:43:29

Well done. I really hope to read the part.2 !

Thank you for visiting Netmanias! Please leave your comment if you have a question or suggestion.
View All (819)
4.5G (1) 5G (88) AI (6) AR (1) ARP (3) AT&T (1) Akamai (1) Authentication (5) Big Data (2) Blockchain (3) C-RAN/Fronthaul (17) CDN (4) CPRI (4) Carrier Ethernet (3) China (1) China Mobile (2) Cisco (1) Cloud (5) CoMP (6) Connected Car (4) DHCP (5) Edge Computing (1) Ericsson (2) FTTH (6) GSLB (1) GiGAtopia (2) Gigabit Internet (19) Google (7) Google Global Cache (3) HLS (5) HSDPA (2) HTTP Adaptive Streaming (5) Handover (1) Huawei (1) IEEE 802.1 (1) IP Routing (7) IPTV (21) IoST (3) IoT (55) KT (42) Korea (19) Korea ICT Market (1) Korea ICT Service (13) Korea ICT Vendor (1) LG U+ (18) LSC (1) LTE (78) LTE-A (16) LTE-B (1) LTE-H (2) LTE-M (3) LTE-U (4) LoRa (7) MEC (3) MPLS (2) MPTCP (3) MWC 2015 (8) NB-IoT (6) Netflix (2) Network Protocol (21) Network Slicing (4) New Radio (9) Nokia (1) OSPF (2) OTT (3) PCRF (1) Platform (2) QoS (3) RCS (4) Roaming (1) SD-WAN (17) SDN/NFV (71) SIM (1) SK Broadband (2) SK Telecom (34) Samsung (5) Security (16) Self-Driving (1) Small Cell (2) Spectrum Sharing (2) Switching (6) TAU (2) UHD (5) VR (2) Video Streaming (12) VoLTE (8) VoWiFi (2) Wi-Fi (31) YouTube (6) blockchain (1) eICIC (1) eMBMS (1) iBeacon (1) security (1) telecoin (1) uCPE (2)
Password confirmation
Please enter your registered comment password.
Password