Open Shortest Path First (OSPF)

[PlAwAnSaI]

Introducing the OSPF Protocol

Link-State Protocols

Open Shortest Path First (OSPF) ถือเป็น Routing Protocol ตัวนึงที่นิยมกันอย่างแพร่หลายมากที่สุดในระบบ Network เนื่องจากมีจุดเด่นในหลายด้าน เช่น การที่ตัวมันเป็น Routing Protocol แบบ Link State, การที่มี Algorithm ในการค้นหาเส้นทางด้วยตัวเอง ซึ่งเปรียบเสมือนว่า ตัวของ Router ที่ Run OSPF ทุกตัวเป็น Root หรือจุดเริ่มต้นของระบบไปยังกิ่งย่อยๆ หรือ Node ต่างๆ ซึ่งเป็น Technique ในการลดเส้นทางที่วน Loop (Routing Loop) ของ Routing ได้เป็นอย่างดี รวมถึงความสามารถในการ Convergence หรือการรับรู้ถึงความเปลี่ยนแปลงใน Topology หรือเส้นทางของ Network ได้อย่างรวดเร็วจนกระทั่งพูดได้เลยว่า แทบจะทันทีที่มีการเปลี่ยนแปลง Topology ขึ้นในระบบ และความสามารถในการรองรับการขยายของระบบ (Scalable) ได้อย่างดีเยี่ยม ซึ่งข้อดีดังกล่าวนั้น ทำให้บรรดา Network Architect ต่างๆ นั้นนิยมเลือก OSPF มาเป็น Routing Protocol หลัก แทนที่ Routing Protocol แบบ Distance Vector เช่น RIP หรือ IGRP ซึ่งก่อนที่จะลงถึงรายละเอียดของ OSPF นั้น ก็จะมีการเกริ่นถึง คำที่เกี่ยวข้องภายใน Routing Protocol ของ OSPF เสียก่อน

Link-State Data Structures:

• Neighbor Table: ไว้เก็บรายชื่อ Router ที่ Form ความสัมพันธ์ และสถานะของ DR/BDR และสถานะของ Link, Hello และ Dead Time Interval
  
• Designated Router (DR) - เป็น Router ที่เป็นจุดศูนย์กลางในการแลกเปลี่ยนข้อมูลหรือสถานะระหว่าง Router ด้วยกัน เนื่องจากการมี Router ที่ทำหน้าที่เป็น Centralize ในระบบ จะสามารถช่วยลดปริมาณ Packet LSA ที่จะส่งกันระหว่าง Router ด้วยกันได้ ซึ่ง DR นี้ จะถูกใช้ใน Network ที่เป็น Broadcast (Multi-Access) และ Non-Broadcast Multi-Access (เช่น Ethernet หรือ Frame-Relay เท่านั้น)
  
• Backup Designated Router (BDR) - จะถือว่าเป็น Router ตัวแทน (Hot Stanby) ของ Designated Router (DR) โดยที่ BDR จะคอยรับ Routing Update จาก Router เพื่อนบ้าน แต่ตัวมันเองจะไม่ทำการ Flood LSA ออกไปเหมือนอย่างที่ DR ทำ จนกระทั่งหากว่า DR ในระบบล่มลงไป BDR จึงจะเข้ามาเป็น DR แทน
  • Also knows as the adjacency database
  • Contains list of recognized neighbors
    
• Topology Table: ไว้เก็บเส้นทางที่เป็นไปได้ทั้งหมดในการที่ Router จะส่ง Packet ไปยังปลายทาง ซึ่งใน OSPF สามารถที่จะทำการกระจายโหลด (Load Balance) ไปยังเส้นทางที่มี Cost เท่ากันได้ 6 เส้นทาง (4 เส้นทางโดยค่า Default)
  • Typically referred to as LSDB
  • Contains all routers and their attached links in the area or network
  • Identical LSDB for all routers within an area
• Routing Table: ไว้เก็บเส้นทางที่สั้นที่สุดที่ได้รับการคำนวณมาจาก SPF Algorithms เรียบร้อยแล้ว
  • Commonly named a forwarding database
  • Contains list of best paths to destinations

ความแตกต่างระหว่าง Link State Routingและ (vs.) Distance Vector Routing:

• รู้เส้นทางทั้งหมดใน Network จากแผนภาพ Topology ของตนใน Topology Table
  • Each router has a full picture of the topology.
  • Consequently, link-state routers tend to make more accurate decisions. vs.
  รู้เส้นทางของ Network โดยผ่านทาง Router เพื่อนบ้าน
  
• คำนวณเส้นทางที่สั้นที่สุดผ่านทาง SPF Algorithms ของตนเอง vs.
  ส่ง Packet ผ่านเส้นทางที่สั้นที่สุดที่ Router เพื่อนบ้านประกาศออกมา
  
• Update เฉพาะเมื่อมีการเปลี่ยนแปลง Topology เท่านั้น (Triggered Update) และ Speed ในการ Converged ที่เร็วมาก vs.
  Update Routing Table เป็นระยะๆ และมีการเข้าสู่สภาวะคงที่ (Converged) ที่ช้า
  
• ส่งสถานะของ Link ตนเอง ออกไปให้ Router เพื่อนบ้าน vs.
  ส่งตาราง Routing Table ทั้งตารางออกไปให้ Router เพื่อนบ้าน
  
• Link-state routers recognize more information about the network than their distance vector counterparts.

ข้อดีของ OSPF:

• สนับสนุนการแบ่ง Network เป็นลำดับขั้น (Hierarchical Network)
• ใช้ Algorithm ของ Diijkstra (Link State) ในการค้นหาเส้นทาง และป้องกัน Routing Loop
• สนับสนุน Classless Routing และ CIDR (Classless Interdomain Routing)
• สามารถทำ Route Summarization เพื่อลดขนาดของ Routing Table ได้
• Routing Update สามารถที่จะควบคุมการส่งได้ ไม่เหมือน Routing Protocol แบบ Distance Vector ที่ต้องส่ง Routing Table ทั้งตารางออกไป ตามช่วงเวลาที่กำหนด ทำให้สูญเสีย Bandwidth ไปโดยไม่จำเป็น
• ในการส่ง Routing Update จะทำผ่าน Multicast Address ซึ่งมีข้อดี คือลดผลกระทบต่อ Host หรือ Client อื่นๆ จากการ Broadcast
• สนับสนุนการทำ Authentication ทั้งแบบ Clear Text และ MD5
  

OSPF Overview:

• Instances หรือ Process ของ OSPF สามารถเริ่มได้ตั้งแต่ 1 - 65,535 แต่ไม่สมควร Run OSPF มากกว่า 1 Process พร้อมๆ กัน หากไม่จำเป็น
• Area ของ OSPF สามารถมีได้ถึง 2^32 หรือประมาณ 4,200,000 Area
• ใน Router ที่ Run OSPF จะต้องมี Area 0 อยู่เสมอ ถือว่าเป็น Backbone Area
• หากกว่า Network นั้นๆ มีหลาย Area ทุกๆ Area จะต้อง Connect เข้าหา Area 0 เสมอ อาจจะเป็นการต่อ Interface เข้าหา Area 0 หรือทำ Virtual Links วิ่งเข้าหา Area 0 ก็ได้
• Default Administrative Distance ของ OSPF คือ 110

Link-State Data Structure: Network Hierarchy:

• Link-state routing requires a hierachical network structure that is enforced by OSPF
  
• This two-level hierarchy consists of the following:
  • Transit area (backbone or area 0)
  • Regular areas (non-backbone areas)

OSPF Areas - ในความหมายของ Area ใน OSPF จะคล้ายๆ กับเป็น Autonomous System (AS) หนึ่งๆ ซึ่งเหมือนกับเป็นกลุ่มของ Router ที่ Run OSPF ด้วยกัน และมีขอบเขตในการแลกเปลี่ยน Routing Table กันภายในกลุ่มของตัวเองเท่านั้นโดย Default

OSPF Areas characteristics:

• Minimizes routing table entries - ลดปริมาณหน่วยความจำที่ใช้ในการจัดเก็บ Routing Table เพราะตาราง Routing Table ที่เกิดขึ้นบน Router แต่ละตัวสามารถได้รับการปรับแต่งให้มีขนาดเล็กลงได้ ด้วยการ Configure route summarization บน Router ตัวริมที่เชื่อมต่อระหว่าง Area หรือเรียกว่า Area Border Router (ABR)
  
• Localizes impact of a topology change within an area - จำกัดความถี่ในการคำนวณ Algorithm SPF ใหม่ เมื่อมีการเปลี่ยนแปลง Topology ของ Router แต่ละตัว เพราะ Router จะคำนวณอัลกอริทึม SPF ใหม่ ก็ต่อเมื่อได้รับ LSA Update จาก Router ภายใน Area เดียวกันเท่านั้น การคำนวณ SPF ใหม่จะมีผลต่อภาระ Load ของ CPU ของ Router

Link State Advertisement (LSA) - เป็น Packet ข้อมูลที่ OSPF Process ใช้ในการแลกเปลี่ยนสถานะของ Interface และ Link ใน Router ที่ Run OSPF ด้วยกัน:

• Detailed LSA flooding stops at the area boundary - จำกัดปริมาณ Packet ที่เกิดขึ้นอันเนื่องมาจากการส่ง LSA Update ให้อยู่ภายในขอบเขตของ Area เดียวกัน (LSA Update จะไม่ถูกส่งข้ามไป Area อื่น)
• Requires a hierarchical network design

 

[PlAwAnSaI]

OSPF Operation - กระบวนการของ OSPF จะเกิดขึ้นตามลำดับต่อไปนี้:

1. OSPF Adjacencies - การ Form ความสัมพันธ์กันระหว่าง Router เพื่อนบ้าน (Neighbor - ในที่นี้จะหมายถึง Router ที่ Run Process ของ OSPF ซึ่งทำการเชื่อมต่ออยู่กับ Router ตัวอื่นๆ ที่ Run OSPF อยู่ด้วยเช่นกัน หรือที่เรียกว่า Adjacent Router (Router ที่เชื่อมต่อกัน) ซึ่ง Router เพื่อนบ้านกันนี้ จะคอยค้นหากันและกันผ่าน Hello Packet ซึ่งข้อมูลที่เกี่ยวข้องในการ Routing จะไม่ถูกส่งผ่านกันจนกว่าจะมีการ Form ความสัมพันธ์ระหว่างกันและกัน (Adjacency Forms))
   
   
   
   • Routers discover neighbours by exchanging hello packets. - ค้นหา Router ที่ Run OSPF และ Form ความสัมพันธ์ด้วย Hello Packet
   • Routers declare neighbours to be up after checking certain parameters or options in the hello packet.
     
2. Router ต่างเก็บชื่อและสถานะของ Link ไว้ที่ Neighbor Table
   
3. เลือก DR/BDR (หากเป็น Point-to-Point, Point-to-Multipoint จุดนี้จะถูกข้ามไป)
   
4. ทำการ Flood LSA เพื่อแลกเปลี่ยนสถานะของ Link (การเรียกถึง Network ที่ Run OSPF อยู่ หรืออาจหมายถึง Interface ที่ทำการรัน OSPF อยู่ด้วยก็ได้) และ Interface (Port ที่เชื่อมต่ออยู่กับ Router ซึ่งอาจจะเป็น Physical Port (เช่น Ethernet) หรืออาจจะเป็น Logical Port (เช่น Sub-Interface ในการ Set Frame-Relay) เมื่อ Interface นั้นๆ ถูก Set ให้อยู่ใน Process ของ OSPF แล้ว และ Interface อยู่ในสถานะที่ Up ตัว Process ของ OSPF จะทำการสร้าง Link State Database โดยผ่านทาง Link นี้) โดยทำการ Copy LSA และทำการเพิ่มสถานะของตน จากนั้น Flood ออกไปยัง DR ที่ Multicast Address 224.0.0.6 และให้ DR เป็นผู้ Flood LSA ต่อไปยัง Router ทุกๆ ตัวที่ Multicast Address 224.0.0.5
   
5. Copy LSA ลงไปใน Topology Table ของตน
   
6. ทำการคำนวณ Shortest Path First ด้วย Dijkstra Algorithms
   
7. นำเส้นทางที่สั้นที่สุดมาใส่ลงใน Routing Table
   
8. หากมีการเปลี่ยนแปลง Topology ในระบบ จะทำการ Flood LSA ออกไปทันที (Triggered Update)

Forming OSPF Adjacencies:

• Point-to-point WAN links:
  • Both neighbours become fully adjacent.
• LAN links:
  • Neighbours form a full adjacency with the DR and BDR.
  • Routers maintain a two-way state with the other routers (DROTHERs).
• Routing updates and topology information is passed only between adjacent routers.
• Once an adjacency is formed, LSDB is synchronized by exchanging LSAs.
• LSAs are flooded reliably throughout the area (or network).

OSPF Calculation:

ใน OSPF จะใช้ Algorithm ของ Dijkstra (Link State) ในการคำนวณหาเส้นทางที่สั้นที่สุด โดยพิจารณาจากเส้นทางที่สั้นที่จุดจากจุดหนึ่งไปยังอีกจุดหนึ่ง และเมื่อไปถึงปลายทางแล้ว ก็จะนำ Cumulative Cost หรือค่าของ Link หรือ Bandwidth โดยรวมมาเปรียบเทียบกัน ซึ่งหากว่า เส้นทางใดที่มองจากต้นทางไปยังปลายทางแล้ว มีค่า Cost ที่ดีที่สุด จะถือว่าเส้นทางนั้นเป็นเส้นทางที่ Shortest Path ซึ่งใน Cisco Routers นั้น สูตรในการคำนวณเส้นทางแต่ละเส้นทางของ OSPF จะนำมาจากสูตร
Cost = (10^8/Bandwidth)

ซึ่งการค้นหาเส้นทางที่สั้นที่สุด ก็จะนำเอา Cost จากขาออกของ Interface จุดหนึ่งไปถึงอีก Interface จุดหนึ่งมาบวกต่อๆ กัน จนกระทั่งถึง Interface ของ Router ปลายทาง และนำมาเปรียบเทียบกันกับเส้นทางอื่นๆ เราเรียกผลรวมในลักษณะนี้ว่า "Cumulative Cost"
Routers find the best paths to destinations by applying Dijkstra's SPF algorithm to the link-state database as follows:

• Every router in an area has the identical link-state database.
• Each router in the area places itself into the root of the tree that is built.
• The best path is calculated with respect to the lowest total cost of links to a specific destination.
• Best routes are put into the forwarding database (routing table).

SPF Calculation:

Assume all links are Ethernet, with an OSPF cost of 10.
Link-State Data Structures - LSA Operation:

สรุปค่า Cost บน Interface ที่มีผลในการคำนวณ Cumulative Cost:

• Ethernet 10 Mbps - Cost 10
• FastEthernet 100 Mbps - 1
• Serial T1 (1.544 Mbps) - 64
• Serial 128 kbps - 781
• Serial 64 kbps - Cost 1,562

OSPF Packet Types:

1. Hello
2. Database Description
3. Link-State Request
4. Link-State Update
5. Link-State Acknowledgment

OSPF Packet Header Format:

Neighborship: The Hello Packet ภายใน Hello Packet ของ OSPF ถูกบรรจุด้วยข้อมูลดังต่อไปนี้:

• Router ID - หมายถึง IP Address ที่ได้ทำการ Assign เพื่อเป็นการ Identify ให้กับ Router ในการเลือก DR, BDR โดยที่ปกติแล้ว Router ใน OSPF จะเลือก DR จาก Router ID ที่ IP Address ที่สูงที่สุดที่ Set ใน Loopback Interface แต่ถ้าหากว่า Loopback Interface ไม่ถูก Set ไว้ ก็จะทำการเลือก IP Address ที่สูงสุดของ Physical Interface แทน
• Hello and dead intervals*
• Neighbors
• Area ID*
• Router priority
• DR IP address
• BDR IP address
• Authentication password*
• Stub area flag*

ในการ Form ความสัมพันธ์กันนั้น ค่าที่มี * จะต้องเท่ากัน มิเช่นนั้นจะ Form ความสัมพันธ์กันไม่ได้

OSPF Neighbour States:

Establishing Bidirectional Communication:

• Down State
  R1: E0 172.27.6.1/24 :R2 E1 172.27.6.2/24
  ไม่มี Router ตัวไหนที่รับส่ง Hello Packet กัน
  
• Init State
  R1: Hello -> I am router ID 1.1.1.1, and I see no one. -> to 224.0.0.5 :R2
  Hello Packet ถูกส่งไปยัง Router เพื่อนบ้าน แต่เป็นการส่งกันทางเดียว Router อีกฝั่งจะยังไม่เห็น Router เพื่อนบ้านอื่นๆ
  
• Two-Way State
  R2 Neighbor List 1.1.1.1/32, Int E1
  R1: Unicast to R1

 

[PlAwAnSaI]

Configuring OSPF in a Single Area:

1. Use the command router ospf [vrf ] to start OSPF.
   router ospf 1
2. Use the network command to enable the interfaces.
3. Identify area assignments area .
   network 0.0.0.0 255.255.255.255 area 0 (all interfaces; not recommend)
   or
   Enable explicitly on an interfaces ip ospf area [secondaries none]
4. (Optional) Assign the router ID.

OSPF process id บน Cisco router:

• www.bloggang.com/viewblog.php?id=likecisco&date=11-06-2011&group=3&gblog=1

Advertising loopback network as /24 instead of /32:
(config-if)# ip ospf network point-to-point
learningnetwork.cisco.com/thread/71259

ประเภทของ OSPF Router:

• Backbone Router - เป็น Router ที่ทำงานอยู่ใน Area 0 หรือเรียกอีกอย่างว่า Backbone Area
  Backbone routers make up area 0.
• Area Border Router (ABR) - หมายถึง Router ที่ Run OSPF ที่มี Interface อยู่มากกว่า 1 Area และถูกใช้เป็นทางเข้าสำหรับ Routing Table ของภายนอก Area ที่จะเข้ามา Update ภายใน Area ด้านใน
  ABRs attach all other areas to area 0.

[li]Autonomous System Border Router (ASBR) - หมายถึง เราเตอร์ที่มีอินเทอร์เฟซที่ นอกเหนือจากรัน OSPF แล้ว ยังรันเราติ้งโปรโตคอลอื่นๆ ด้วย เช่น EIGRP, RIP, IS-IS (เราถือว่า เราติ้งโปรโตคอลอื่นๆ เป็น External Autonomous System) และหน้าที่ของ ASBR ก็คือ การถ่ายทอดเราติ้งเทเบิลเข้ามาใน OSPF Area ในทำนองเดียวกัน เมื่อเราเตอร์ตัวใดก็แล้วแต่ต้องการส่งแพ็กเก็ตไปยังเราเตอร์ภายนอกที่อยู่ภายใต้ขอบเขตของเราติ้งโปรโตคอลอื่นๆ มันก็จะต้องส่งแพ็กเก็ตมาหา ASBR ก่อน เพื่อให้ ASBR ดำเนินการต่อให้[/li]
[li]Internal Router - หมายถึง เราเตอร์ที่รัน OSPF แต่ทุกๆ Interface อยู่ภายใน Area ของตนเท่านั้น หรือไม่มี Interface ใดๆ อยู่ภายใน Area อื่น หรือ Routing Protocol อื่นๆ เมื่อมันต้องการส่งแพ็กเก็ตไปยังเราเตอร์ตัวอื่นที่อยู่ต่าง area กับมัน มันจะต้องส่งแพ็กเก็ตไปยังเราเตอร์ที่ทำหน้าที่เป็น ABR ใน area ของตนก่อน เพื่อให้ ABR ของตนทำการส่งแพ็กเก็ตต่อไปยังเราเตอร์ที่ทำหน้าที่เป็น Backbone Router ใน area 0 จากนั้น Backbone Router จะช่วยส่งแพ็กเก็ตไปยัง ABR ของ area ปลายทาง เมื่อ ABR ได้รับแพ็กเก็ตแล้ว มันจะค่อยส่งต่อไปให้ internal router ภายในอีกครั้ง[/li][/list]

OSPF Network Types
The three types of networks defined by OSPF are:


[li]Point-to-point: A network that joins a single pair of routers. - การเชื่อมต่อแบบ จุดต่อจุด เช่น Dedicated Link (T1), PPP เป็นต้น[/li]
[li]Broadcast (Broadcast multiaccess;BMA): A multiaccess broadcast network, such as Ethernet.[/li]
[li]Nonbroadcast multiaccess (also called NBMA): A network that interconnects more than two routers but that has no broadcast capability. Frame Relay, ATM, and X.25 are examples of NBMA network. - เน็ตเวิร์กที่มีการเชื่อมต่อกันมากกว่า 2 router แต่ไม่มีการ Broadcast Packet
[/list]


[li]Five modes of OSPF operation are available for NBMA networks.[/li][/list]
[/li]

Link State Advertisement Types
Type 1 Router LSAs - เป็น LSA ที่ใช้ในการแชร์กันระหว่างเราเตอร์ที่รัน OSPF ใน AREA เดียวกัน
Type 2 Network LSAs
Type 3 or 4 Summary LSAs
Type 5 Autonomous system external LSAs
Type 6 Multicast OSPF LSA
Type 7 Defined for not-so-stubby areas
Type 8 External attributes LSA for Border Gateway Protocol (BGP)
Type 9, 10, 11 Opaque LSAs

ospf มีขั้นตอนในการคัดเลือก router id อย่างไร, change router id


Code:
http://forum.siamnetworker.com/index.php?topic=492



Troubleshooting


Code:
http://www.cisco.com/networkers/nw00/pres/2206_7-5.pdf



สงสัยตรงไหนถามได้เลยคับ

Credit: MSIT@MUT&Cisco


Both stub area & totally stubby area allow an ABR to inject a default route. The main difference between these 2 types of areas is:


[li]Stub area replaces LSA Type 5 (External LSA - created by an ASBR to advertise network from another autonomous system) with a default route[/li]
[li]Totally stubby area replaces both LSA Type 5 and LSA Type 3 (Summary LSA - created by an ABR to advertise network from other areas, but still within the AS, sometimes called interarea routes) with a default route.[/li][/list]

Below summarizes the LSA Types allowed and not allowed in area types:

Area Type	Type 1 & 2 (within area)	Type 3 (from other areas)	Type 4	Type 5	Type 7
Standard & backbone	Yes	Yes	Yes	Yes	No
Stub	Yes	Yes	No	No	No
Totally stubby	Yes	No	No	No	No
NSSA	Yes	Yes	No	No	Yes
Totally stubby NSSA	Yes	No	No	No	Yes

The 7 states to fulfill an OSPF adjacency between two routers are:

• Down - neighbor has not been discovered
  If adjacency is stuck here, there is a mismatch regarding parameters exchanged in Hello messages:
  • Subnet mask or IP address mismatch
  • Authentication configuration mismatch
  • Mismatched timer parameters (Hello, Dead intervals)
  • Area ID mismatch
  • Area type mismatch (Normal, Stub, NSSA)
  • Duplicate router-id
    
• Initializing - one-way communication verified
  If adjacency is stuck here, there is a mismatch in the interface type (point-to-point vs broadcast)
  
• 2-way - two-way communication verified
  
• Exstart - MTU compatibility being verified
  
• Exchange - database description (LSA list) being exchanged
  If adjacency is stuck either in the Exstart or in the Exchange state, there is an MTU mismatch
  
• Loading - exchanging LSAs
  
• Full - link-state database fully synchronized