Hazy Sighted Link State Routing Protocol

Last updated September 18, 2023

The Hazy-Sighted Link State Routing Protocol (HSLS) is a wireless mesh network routing protocol being developed by the CUWiN Foundation. This is an algorithm allowing computers communicating via digital radio in a mesh network to forward messages to computers that are out of reach of direct radio contact. Its network overhead is theoretically optimal,^[1] utilizing both proactive and reactive link-state routing to limit network updates in space and time. Its inventors believe it is a more efficient protocol to route wired networks as well. HSLS was invented by researchers at BBN Technologies.

Efficiency

HSLS was made to scale well to networks of over a thousand nodes, and on larger networks begins to exceed the efficiencies of the other routing algorithms. This is accomplished by using a carefully designed balance of update frequency, and update extent in order to propagate link state information optimally. Unlike traditional methods, HSLS does not flood the network with link-state information to attempt to cope with moving nodes that change connections with the rest of the network. Further, HSLS does not require each node to have the same view of the network.

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^{[ citation needed ]} 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.

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.

Advantages

The network establishes pretty good routes in real time, and substantially reduces the number and size of messages sent to keep the network connected, compared to many other protocols. Many of the simpler mesh routing protocols just flood the whole network with routing information whenever a link changes.

The actual algorithm is quite simple.

The routing information and the data transfer are 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 avionics.

HSLS has good scalability properties. The asymptotic scalability of its total overhead is $O(N^{1.5})$ compared to standard link state which scales as $O(N^{2})$ , where N is the number of nodes in the network.

Critiques

Because HSLS sends distant updates infrequently, nodes do not have recent information about whether a distant node is still present. This issue is present to some extent in all link state protocols, because the link state database may still contain an announcement from a failed node. However, protocols like OSPF will propagate a link state update from the failed nodes neighbors, and thus all nodes will learn quickly of the failed node's demise (or disconnection). With HSLS, one can't disambiguate between a node that is still present 10 hops away and a failed node until former neighbors send long-distance announcements. Thus, HSLS may fail in some circumstances requiring high assurance.

While the papers describing HSLS do not focus on security, techniques such as digital signatures on routing updates can be used with HSLS (similar to OSPF with Digital Signatures), and BBN has implemented HSLS with digital signatures on neighbor discovery messages and link state updates. Such schemes are challenging in practice because in the ad hoc environment reachability of public key infrastructure servers cannot be assured. Like almost all routing protocols, HSLS does not include mechanisms to protect data traffic. (See IPsec and TLS.)

Related Research Articles

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet.

A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass; one router counts as one hop. Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route. To determine the best route across a network, routers using a distance-vector protocol exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information. Distance-vector routing protocols also require that a router inform its neighbours of network topology changes periodically.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network.

<span class="mw-page-title-main">Optimized Link State Routing Protocol</span> IP routing protocol optimized for mobile ad hoc networks

The Optimized Link State Routing Protocol (OLSR) is an IP routing protocol optimized for mobile ad hoc networks, which can also be used on other wireless ad hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.

Topology broadcast based on reverse-path forwarding (TBRPF) is a link-state routing protocol for wireless mesh networks.

Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting node requests one. However, it uses source routing instead of relying on the routing table at each intermediate device.

The OrderOne MANET Routing Protocol 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.

Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman–Ford algorithm. It was developed by C. Perkins and P. Bhagwat in 1994. The main contribution of the algorithm was to solve the routing loop problem. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.

In wireless networking, On-Demand Multicast Routing Protocol is a protocol for routing multicast and unicast traffic throughout Ad hoc wireless mesh networks.

A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, each node participates in routing by forwarding data for other nodes. The determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.

The Better Approach to Mobile Ad-hoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR).

A routing protocol specifies how routers communicate with each other to distribute information that enables them to select routes between nodes on a computer network. Routers perform the traffic directing functions on the Internet; data packets are forwarded through the networks of the internet from router to router until they reach their destination computer. Routing algorithms determine the specific choice of route. Each router has a prior knowledge only of networks attached to it directly. A routing protocol shares this information first among immediate neighbors, and then throughout the network. This way, routers gain knowledge of the topology of the network. The ability of routing protocols to dynamically adjust to changing conditions such as disabled connections and components and route data around obstructions is what gives the Internet its fault tolerance and high availability.

The Wireless Routing Protocol (WRP) is a proactive unicast routing protocol for mobile ad hoc networks (MANETs).

Extremely Opportunistic Routing (ExOR) is a combination of routing protocol and media access control for a wireless ad hoc network, invented by Sanjit Biswas and Robert Morris of the MIT Artificial Intelligence Laboratory, and described in a 2005 paper. A very similar opportunistic routing scheme was also independently proposed by Zhenzhen Ye and Yingbo Hua from University of California, Riverside and presented in a paper in 2005. Previously open source, ExOR was available in 2005 but is no longer obtainable. The broadcast and retransmission strategies used by the algorithm were already described in the literature. ExOR is valuable because it can operate available digital radios to use some previously impractical algorithmic optimizations.

Routing in delay-tolerant networking concerns itself with the ability to transport, or route, data from a source to a destination, which is a fundamental ability all communication networks must have. Delay- and disruption-tolerant networks (DTNs) are characterized by their lack of connectivity, resulting in a lack of instantaneous end-to-end paths. In these challenging environments, popular ad hoc routing protocols such as AODV and DSR fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routing protocols must take to a "store and forward" approach, where data is incrementally moved and stored throughout the network in hopes that it will eventually reach its destination. A common technique used to maximize the probability of a message being successfully transferred is to replicate many copies of the message in hopes that one will succeed in reaching its destination.

The ETX metric, or expected transmission count, is a measure of the quality of a path between two nodes in a wireless packet data network. It is widely utilized in mesh networking algorithms.

IEEE 802.11s is a wireless local area network (WLAN) standard and an IEEE 802.11 amendment for mesh networking, defining how wireless devices can interconnect to create a wireless LAN mesh network, which may be used for relatively fixed topologies and wireless ad hoc networks. The IEEE 802.11s task group drew upon volunteers from university and industry to provide specifications and possible design solutions for wireless mesh networking. As a standard, the document was iterated and revised many times prior to finalization.

Fisheye State Routing (FSR) is a proposal for an implicit hierarchical routing protocol targeted to ad hoc networks. The basic principles of FSR are shared with other proactive, link-state routing protocols. In proactive link-state protocols every network node constantly updates a topology map that makes it possible to compute the shortest path to any destination in the network. The originality of FSR is inspired by the "fisheye" technique to reduce the size of information required to represent graphical data: The eye of a fish captures with high detail the pixels near the focal point, while the detail decreases as the distance from the focal point increases.

References

↑ "Hazy Sighted Link State (HSLS) Routing: A Scalable Link State Algorithm" (PDF). BBN Technologies. Archived from the original (PDF) on 2008-07-06. Retrieved 2008-02-20.

External links

OLSR fisheye - OLSR from olsr.org implemented the "fisheye" algorithm which is equivalent to HSLS
NRLOLSR Prototype - extended OLSR to provide an optional HSLS capability

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Hazy Sighted Link State (HSLS) Routing: A Scalable Link State Algorithm" (PDF). BBN Technologies. Archived from the original (PDF) on 2008-07-06. Retrieved 2008-02-20.

[1]