链路状态路由协议（PPT讲稿）LINK STATE ROUTING PROTOCOLS

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