---
# System prepended metadata

title: Ch10 Open Shortest Path First(OSPF)

---

Ch10 Open Shortest Path First(OSPF)
===

* Link-state Routing Protocol
    * Open Shortest Path First(OSPF)
    * Intermediate System to Intermediate System(IS-IS)
    * 流程
        1. 所有 node 都有每個 node 的鄰居的資訊
        2. 計算最短路徑
        3. 轉成 routing table
* OSPF
    * Defined in RFC 2328 (RFC, Request for comments)
    * A link-state routing protocol
    * Dijkstra’s (Shortest Path) Algorithm
    * An Interior Gateway Protocol
    * Fast convergence and excellent scalability
    * Every router computes its own routing table
    * Commonly used in large enterprise networks
* Link-state Operation
    1. 找相鄰鄰居
    2. Exchange Link-State Advertisements (LSAs)
    3. Build the Topology Table
        * Topology table 包含所有 routing table
    4. 執行 SPF (Shortest Path First) Algorithm
    5. 修改 routing table
        * 有 OSPF 的資訊
* OSPF 封包格式
    * 要建立 OSPF 的廣播封包
    * Data Link Ethernet Frame Header
        * Destination multicast MAC address: 規定的
            1. 01:00:5E:00:00:05
            2. 01:00:5E:00:00:06
    * IPv4 Packet Header
        * destination address: 規定的
            1. 224.0.0.5
            2. 224.0.0.6
        * protocol field: 89 for OSPF
    * OSPF Packet Header
        * OSPF packet type
        * router ID
        * area ID
    * OSPF Packet Type Specific Data
        * The content differs depending on the packet type
* OSPF 使用 link-state packet (LSP)
    * Hello packet
        * 跟鄰居保持關係
    * Database Descriptor (DBD) packet
        * 有 LSDB(Link-State Database) 簡略資訊
        * 確認資料庫同步
    * LSR(Link-State Request) packet
        * 詢問更詳細的 DBD
    * LSU(Link-State Update) packet
        * 回覆 LSR
    * LSAck(Link-State Acknowledgment) packet
        * 確認接收 LSU
* OSPF operation state
    * Establish Neighbor Adjacencies
        1. down state
            * 要開始看看有沒有其他 OSPF 的 router
            * 廣播 Hello packet
            * 交換 router ID
        2. init state
            * 接收到 Hello packet 後，如果那個 router ID 不在表裡，就跟它交朋友
        3. Two-Way state
    * Synchronize OSPF Database
        1. ExStart state
            * 要交換 database，所以在這裡決定誰先送 DBD packet
            * router ID 較高的先送
        2. Exchange state
            * 開始換 DBD
            * Link type
            * address of advertising router
            * sequence number
        3. Loading state
            * 更新需要更新的 entry
    * Full state
        * 同步狀態
* OSPF Designated Router
    * Multiaccess network 的狀況
        * 剛開始交朋友的時候，封包會造成 flooding
        * 更新 database 的時候，也會 flooding
    * 解決方案: DR(Designated Router)
        * 選舉出 DR 來當收集、發散點
        * BDR(Backup Designated Router) 要備份以免 DR 出狀況
        * 其他人是 DROTHER