How It Works
The designers started the tuning of these items by defining a measure of global network waste. This includes waste from transmitting route updates, and also waste from inefficient transmission paths. Their exact definition is "The total overhead is defined as the amount of bandwidth used in excess of the minimum amount of bandwidth required to forward packets over the shortest distance (in number of hops) by assuming that the nodes had instantaneous full-topology information."
They then made some reasonable assumptions and used a mathematical optimization to find the times to transmit link state updates, and also the breadth of nodes that the link state updates should cover.
Basically, both should grow to the power of two as time increases. The theoretical optimal number is very near to two, with an error of only 0.7%. This is substantially smaller than the likely errors from the assumptions, so two is a perfectly reasonable number.
A local routing update is forced whenever a connection is lost. This is the reactive part of the algorithm. A local routing update behaves just the same as the expiration of a timer.
Otherwise, each time that the delay since the last update doubles, the node transmits routing information that doubles in the number of network-hops it considers. This continues up to some upper limit. An upper limit gives the network a global size and assures a fixed maximum response time for a network without any moving nodes.
The algorithm has a few special features to cope with cases that are common in radio networks, such as unidirectional links, and looped-transmission caused by out-of-date routing tables. In particular, it reroutes all transmissions to nearby nodes whenever it loses a link to an adjacent node. It also retransmits its adjacency when this occurs. This is useful precisely because the most valuable, long-distance links are also the least reliable in a radio network;
Read more about this topic: Hazy Sighted Link State Routing Protocol
Famous quotes containing the word works:
“Any balance we achieve between adult and parental identities, between children’s and our own needs, works only for a time—because, as one father says, “It’s a new ball game just about every week.” So we are always in the process of learning to be parents.”
—Joan Sheingold Ditzion, Dennie, and Palmer Wolf. Ourselves and Our Children, by Boston Women’s Health Book Collective, ch. 2 (1978)