LINK STATE ROUTING PROTOCOLS Dr. Rocky K C Chang 22 November 2010
LINK STATE ROUTING PROTOCOLS Dr. Rocky K. C. Chang 22 November 2010 1
nk state approac o In the dv approach, each router discovers the network topology through the distance vectors received from its neighbors. o In the ls approach each router discovers the network topology through link state advertisements (LSAS) n Each router is responsible for discovering its neighbors and the states of the links between them, and informs other routers a Upon receiving all the link states, a router can form a local view of the entire network
Link state approach 2 In the DV approach, each router discovers the network topology through the distance vectors received from its neighbors. In the LS approach, each router discovers the network topology through link state advertisements (LSAs). Each router is responsible for discovering its neighbors and the states of the links between them, and informs other routers. Upon receiving all the link states, a router can form a local view of the entire network
An example [from [3]) 口R。 outers connected by point-to- point links a Networ ks connected to the routers are omitted a Link states are generally asymmetric 5 A C D E
An example [from [3]) 3 Routers connected by point-to-point links Networks connected to the routers are omitted. Link states are generally asymmetric. A B C E D 4 3 1 1 5 2 3
After exchanging LSAs with neighbors (from [1]) 口 For router a B Link a4 A c Link b4 HA3 C|3 E1 E Link A|1
After exchanging LSAs with neighbors (from [1]) 4 For router A 4 3 1 A Link B C E 4 3 1 E Link A 1 C Link A 3 B Link A 4
After receiving all LSAs(from [1]) 5 o After the protocol converges the routers' link state databases are identical B Link a 4 D 2 A D Link BCE 431 3 ADE B 5 E 253 E C 1 D|3
After receiving all LSAs (from [1]) 5 After the protocol converges, the routers’ link state databases are identical. 4 3 1 1 5 2 3 A Link B C E 4 3 1 E Link A C D 1 1 3 C Link A D E 3 5 1 D Link B C E 2 5 3 B Link A D 4 2
nk state routing protocols 6 a Therefore there are two main parts in a link state routing protocol a(Topology dissemination) Construct and maintain a consistent link state database in all routers n( Route computation) Each router computes minimum-cost paths to all destinations in the network
Link state routing protocols 6 Therefore, there are two main parts in a link state routing protocol. (Topology dissemination) Construct and maintain a consistent link state database in all routers. (Route computation) Each router computes minimum-cost paths to all destinations in the network
Topology dissemination 口 Neighbor discovery a Use hello protocols to discover neighbors and to elect a designated router on a shared medium. a Bringing up adjacencies in a point-to-point network n a set of protocols database description, link state request update)to synchronize the link state databases of the two routers o On a shared medium, a designated router a forms adjacency with other routers and a responsible for advertising the link states
Topology dissemination 7 Neighbor discovery Use Hello protocols to discover neighbors and to elect a designated router on a shared medium. Bringing up adjacencies in a point-to-point network A set of protocols (database description, link state request/update) to synchronize the link state databases of the two routers On a shared medium, a designated router forms adjacency with other routers, and responsible for advertising the link states
Topology dissemination 8 A B A D D Shared medium N(N12 adjacencies A A B LAN D D adjacencies advertisements
Topology dissemination 8 A B C D A B C D A B C D LAN Shared medium N(N-1)/2 adjacencies A B C D (N-1) adjacencies Link advertisements
Link state advertisements o A link-state router generates a link state advertisement(LSA)when discovering aa new neighbor router, or the cost of the link to an existing neighbor changes (including link failure). a The lsa describes the latest changes in the network topology and must be transmitted to all other routers as soon as possible a Dissemination cannot be based on the routing information. Why not?
Link state advertisements 9 A link-state router generates a link state advertisement (LSA) when discovering a new neighbor router, or the cost of the link to an existing neighbor changes (including link failure). The LSA describes the latest changes in the network topology and must be transmitted to all other routers as soon as possible. Dissemination cannot be based on the routing information. Why not?
An example 10 a If b fails, a needs to update the link state for a->B a But the spanning tree computed based on the original topology does not reach all nodes. A
An example 10 A B If B fails, A needs to update the link state for A->B. But the spanning tree computed based on the original topology does not reach all nodes