Hazy Sighted Link State Routing Protocol
The Hazy-Sighted Link State Routing Protocol (HSLS) is an algorithm for computers communicating by digital radio in a mesh network to find each other, and send messages to each other along a reasonably efficient path. It was designed for, and promoted as working with wireless mesh networks. It is a Link-state routing protocol. Because it treats network overhead in a more comprehensive way, its inventors consider it to have substantial application as a more efficient protocol to route wired networks, as well.
HSLS's designers say it scales well to networks of over a thousand nodes, and on larger networks begins to exceed the efficiencies of the best-known other routing algorithms.
HSLS uses a carefully designed balance of update frequency, and update extent in order to propagate link state information optimally. It does not require each node to have the same view of the network.
The basic problem that HSLS tries to solve is that pure link-state algorithms have failed to effectively route radio networks with moving nodes. They fail because the connections between nodes change. To track these changes, conventional link-state routing floods the network with link-state information, using too much network capacity.
At the same time, link-state algorithms are theoretically attractive, because they find optimal routes, reducing waste of transmission capacity.
The inventors say 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.
HSLS is said to optimally balance the features of proactive, reactive and suboptimal routing approaches. The reactive routing occurs because nearby routes are rerouted whenever an adjacent link is lost. The proactive part is most of the paper, 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. The suboptimal routing occurs naturally as the side-effect of having less information about distant nodes. By definition, a link-state algorithm uses the available information to produce the best route, so this is as optimal as possible, given the available information.
By limiting the distance to which a proactive routing update should go, the amount of transmission capacity is reduced. By limiting the times that a proactive routing update is transmitted, several updates can be collected and transmitted at once, also saving transmission capacity.
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 or 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 routing information, and also the breadth of nodes that the routing information 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 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.
The algorithm has a few special features to cope with cases that are common in radio networks, such as unidrectional 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.
Advantages
The network establishes pretty good routes in real time, and substantially reduces the number of messages sent to keep the network connected, compared to many other protocols. Many of the simpler mesh routing protocols just flood the whole nework with routing information whenever a link changes.
The actual algorithm is quite simple.
The routing information is not at all centralized, and the data transfer is decentralized, and should therefore have good reliability and performance with no local hot spots.
The system requires capable nodes with large amounts of memory to maintain routing tables. Fortunately, these are becoming less expensive all the time.
The system gives a very quick, relatively accurate guess about whether a node is in the network, because complete, though out-of-date routing information is present in every node. However, this is not the same as knowing whether a node is in the network. This guess may be adequate for most tariff network use, like telephony, but it may not be adequate for safety-related military or avionic applications.
Critiques
The network does not have a reliable, low-overhead way to establish that a node is in the network. This means that it is questionable to use HSLS for tariff service such as telephones, or assured military communications.
Since the descriptions do not include distributed security and authentication, HSLS is subject to spoofing. Centralized security controls might negate much of the advantage of the cleverly tuned network update scheme. Attacks could divert and read messages by lying about the address, by establishing a false routing system, or by routing the network through a reader. Denial of service could occur by establishing false routing, and selectively denying connections, or by suboptimizing the routing.
See also
- DSR, AODV and OLSR are leading conventional public-domain solutions to the same problem.
- The Ad hoc protocol list describes more protocols.