Distance Vector vs Link State

Types of Routing Static Dynamic (routers 互相交換資訊, 產生 routing table) 分類1 (依運作的範圍) EGP (Exterior Gateway Protocol) / BGP (Border Gateway Protocol) IGP (Interior Gateway Protocol) 分類2 (依搜集資訊及處理資訊的方法) Distance Vector Link State Hybrid 2019/5/6

Types of Dynamic Routing Protocol IGP (Interior Gateway Protocol) RIP / IGRP OSPF etc EGP (Exterior Gateway Protocol) BGP: Border Gateway Protocol) 2019/5/6

Autonomous System 獨立(自治)系統 Internet 是由數個獨立管理的獨立(自治)系統所組成 IBM 內部網路可能是一個 AS Hinet Seednet 2019/5/6

Autonomous System 每個 Autonomous System 有其內部的管理權限及 Routing 方法 IGP : Interior Gateway Protocol ASs 之間亦有 Routing 的標準 EGP : Exterior Gateway Protocol (BGP : Border Gateway Protocol) 2019/5/6

AS 之間的 Routing 2019/5/6

Distance-Vector A router periodically sends all of its neighbors two pieces of information about the destinations it knows how to reach how far away (it thinks) the destination is (distance) what direction to use to get to the destination (vector) 2019/5/6

Distance-Vector Protocol How many hops away from destination (sometimes, distance may be measured in time delay) Vector : 方向 Which way to some destination e.g., send packet to me if you want to reach some destination 2019/5/6

Distance Vector Routing Protocol 2019/5/6

Link State Routing Protocol 2019/5/6

Example of Distance Vector : RIPv1 Used in various UNIX box & NT routed (route daemon) Measuring performance of a path base on number of “hop” Hop Hop Net1 Net2 Net3 Router Router 2019/5/6

How does RIP work? Router2 Router3 Router1 127.162.2.0/24 127.16.1.0/24 2019/5/6

Link-State Protocol A router provides information about the topology of the network in its immediate vicinity links it attaches to state (functioning or not) of those links The information is then flooded to the network Each router computes its best path (bases on the above information) to all destinations 2019/5/6

OSPF “Open Shortest Path First” Uses several criteria to determine the best route to a destination These include cost metrics, which factor in such things as route speed, traffic, reliability, and security 2019/5/6

Link State 如何維護 State? (again) Router 透過 Hello 封包, 瞭解與其直接相連的其他 Routers 之狀態 Hello to its neighbors Router 經由 LSAs, 瞭解整個網路 (或某個區域內) 所有其他 Routers 的資訊 LSAs to all 2019/5/6

In more details 第一階段 第二階段 第三階段 收集 “相鄰” 之 Link State 資訊 (使用 Hello) 廣告 Link State 資訊給所有 routers (within area)  LSA (Link State Advertisement) 第三階段 使用 SPF (Shortest Path First) 演算法, 由收集之 LSA 資訊計算整體網路之 Topological Tree  Routing Table 2019/5/6

Shortest Path First Algorithm 由 B 的角度 Routing Table 2019/5/6

Distance Vector vs Link State 交換資訊之對象 交換資訊之時機 交換之資訊內容 計算路徑之方法 2019/5/6

Multi-Protocol Routing Routers are capable of supporting multiple independent routing protocols, and of maintaining routing tables for several routed protocols, concurrently This capability allows a router to deliver packets from several routed protocols over the same data links 2019/5/6

Multi-Protocol Routing 2019/5/6