| Link-State Routing
				In distance-vector routing, the information about the topology of the
				network is distributed among the routers, which achieves efficiency
				but also creates problems.
				 
				An alternate approach, used in link-state routing, is to
				give each router complete information about the graph of the network.
				Then, each router independently computes the optimal path to every
				destination.
				 
				Thus, the main questions to be answered in order to make
				this approach work are:
				 
				How will knowledge of the network's topology be distributed to every
				router in the network?
				
				Once the topology has been disseminated, how will the shortest paths
				be computed?
				
 Topology Dissemination
				The link-state algorithm periodically distributes
				link-state packets (LSPs), which are
				developed at every router participating in the network.  The contents
				of an LSP include:
				 
					That router's ID.
					
					The ID of one of the router's neighbors.
					
					The cost of the link to that neighbor.
					
 
				
				(Every router thus will send a quantity of LSPs equal to the number of
				neighbors it has.)
				
				 
				When a router receives an LSP, it tries to store
				it in its own LSP database.  If the information contained
				in the LSP just received already exists in the database, no action is
				taken.  Otherwise, the router stores it in its own database and
				forwards a copy of the LSP it just received to every neighboring
				router (except the one from which it just
				received the packet).
				 
				When every router in the network has a consistent LSP database, each
				router individually computes the optimal paths to all other network
				nodes. The algorithm used to do this usually is Dijkstra's algorithm.
				 
				What do you think are some of the network conditions under which the
				strategy just described might fail? Jot down a few on a piece of
				paper. Choose the one which you think is the most serious before going
				on to the next page.
				 |