Hazy Sighted Link State Routing Protocol - Why A Link-state Protocol?

Why A Link-state Protocol?

Link-state algorithms are theoretically attractive because they find optimal routes, reducing waste of transmission capacity. The inventors of HSLS claim that routing protocols fall into three basically different schemes: proactive (such as OLSR), reactive (such as AODV), and algorithms that accept sub-optimal routings. If one graphs them, they become less efficient as they are more purely any single strategy, and the network grows larger. The best algorithms seem to be in a sweet spot in the middle.

The routing information is called a "link state update." The distance that a link-state is copied is the "time to live" and is a count of the number of times it may be copied from one node to the next.

HSLS is said to optimally balance the features of proactive, reactive, and suboptimal routing approaches. These strategies are blended by limiting link state updates in time and space. By limiting the time to live the amount of transmission capacity is reduced. By limiting the times when a proactive routing update is transmitted, several updates can be collected and transmitted at once, also saving transmission capacity.

• By definition, a link-state algorithm uses the available information to produce the best route, so routing is as optimal as possible, given the available information.
• The suboptimal routing happens naturally because distant nodes get information less frequently.
• Minimizing proactive updates is the tricky part. The scheme is adapted from two limited link-state routing algorithms. One, "Near-Sighted Link-State Routing" is limited in space, in the number of node-hops that routing information may be transmitted. The other routing algorithm, "Discretized Link-State Routing" limits the times that the routing information may be transmitted. Since the optimal update attenuation in both space and time is about two, the result is a periodic proactive update, with fractal power-of-two node hop distances for the data (e.g. hop distances of 1, 2, 1, 4, 1, 2, 1, 8...).
• The reactive routing occurs because a failed attempt to use an adjacent link causes the next timer to expire, probably drawing in the information to find an alternate route. On each successive failure, a retry escalates the reaction to wider audiences of meshed nodes.