Fisheye State Routing

Last updated

Fisheye State Routing (FSR) is a proposal for an implicit hierarchical routing protocol targeted to ad hoc networks. [1] 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 (and thus the next hop) 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.

Contents

In routing, the fisheye approach translates into maintaining an updated information set about distance and path quality information for the immediate neighborhood of a node, against a progressively less updated information as the distance increases. Fisheye represents a valid trade-off between the accuracy of the routing function and the overhead due to the generation of control messages by the routing protocol.

FSR was never released to the public as a stand-alone routing protocol, and its specification was never finalized. [2] The base principle was included in the widely used OLSRd daemon (an open source implementation of the OLSR routing protocol [3] ).

Protocol working principle

FSR is a link-state routing protocol, thus it is made of three tasks:

  1. Neighbor Discovery: every node sends an HELLO message every δ seconds to its one-hop neighbours, in order to establish and maintain neighbour relationships.
  2. Information Dissemination: every node disseminates Link State Announcements messages (LSA) every Δ seconds (with Δ > δ), that contain neighbour link information, to all other nodes in the network.
  3. Route Computation: from the information contained in the LSA messages the node can reconstruct the whole network topology and use Dijkstra's algorithm to compute the routes to any node in the network.

The peculiarity of FSR is that LSA messages are generated every Δ seconds using a sequence of distinct Time-To-Live (TTL) values. Take as an example the sequence 1, 3, 8, 64, the 1-hop neighbours receive the LSA every Δs, so they have the most updated information. 2-hop neighbours receive the LSA with TTL 3, 8, 24. Nodes at a distance from 4 to 8 hops receive only the LSA with TTL 8 and 64. All the others receive only the LSA with TTL 64. As a consequence every node has progressively less updated information on the network topology as the distance increases.

The protocol exploits the fact that when a packet moves from a source to a destination, the nodes encountered on the shortest path have an increasingly precise topology information about the topological position of the destination (as their distance to the destination decreases), so the loss of accuracy in the shortest path computation from the source node is compensated along the path to the destination.

FSR thus decreases the overall quantity of information spread in the network, since LSA are not sent with a fixed maximum TTL.

Drawbacks

One of the typical issues with link-state protocols is that when a node or link breaks, temporary loops can be created. This is due to the fact that HELLO messages are sent with a higher frequency than LSA messages, so if a node fails, its neighbors sense the broken link way before the other nodes. They immediately recompute their routing tables, which can conflict with the routing table of the other nodes, and a loop can be created. This can happen when two nodes have information with a different age and thus they compute their routing tables on two different network topologies. FSR does this by design, it introduces areas in the network with potentially different information sets, so it increases the probability of creating temporary loops. [4]

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.

Time to live (TTL) or hop limit is a mechanism which limits the lifespan or lifetime of data in a computer or network. TTL may be implemented as a counter or timestamp attached to or embedded in the data. Once the prescribed event count or timespan has elapsed, data is discarded or revalidated. In computer networking, TTL prevents a data packet from circulating indefinitely. In computing applications, TTL is commonly used to improve the performance and manage the caching of data.

Intermediate System to Intermediate System is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices. It accomplishes this by determining the best route for data through a packet switching network.

Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous system (AS).

Enhanced Interior Gateway Routing Protocol (EIGRP) is an advanced distance-vector routing protocol that is used on a computer network for automating routing decisions and configuration. The protocol was designed by Cisco Systems as a proprietary protocol, available only on Cisco routers. In 2013, Cisco permitted other vendors to freely implement a limited version of EIGRP with some of its associated features such as High Availability (HA), while withholding other EIGRP features such as EIGRP stub, needed for DMVPN and large-scale campus deployment. Information needed for implementation was published with informational status as RFC 7868 in 2016, which did not advance to Internet Standards Track level, and allowed Cisco to retain control of the EIGRP protocol.

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).

<span class="mw-page-title-main">Mesh networking</span> Network with multiple links between nodes

A mesh network is a local area network topology in which the infrastructure nodes connect directly, dynamically and non-hierarchically to as many other nodes as possible and cooperate with one another to efficiently route data to and from clients.

<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.

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 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, 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.

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.

<span class="mw-page-title-main">Flooding (computer networking)</span> Simple routing algorithm sending incoming packets to all other links than the sender

Flooding is used in computer network routing algorithms in which every incoming packet is sent through every outgoing link except the one it arrived on.

<span class="mw-page-title-main">B.A.T.M.A.N.</span> Routing protocol for multi-hop mobile ad hoc networks

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) as OLSR did not meet the performance requirements of large-scale mesh deployments.

A routing protocol specifies how routers communicate with each other to distribute information that enables them to select paths 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).

In wired computer networking a hop occurs when a packet is passed from one network segment to the next. Data packets pass through routers as they travel between source and destination. The hop count refers to the number of network devices through which data passes from source to destination.

IEEE 802.1aq is an amendment to the IEEE 802.1Q networking standard which adds support for Shortest Path Bridging (SPB). This technology is intended to simplify the creation and configuration of Ethernet networks while enabling multipath routing.

RPL is a routing protocol for wireless networks with low power consumption and generally susceptible to packet loss. It is a proactive protocol based on distance vectors and operates on IEEE 802.15.4, optimized for multi-hop and many-to-one communication, but also supports one-to-one messages.

References

  1. ↑ http://nrlweb.cs.ucla.edu/publication/download/203/05_75_fisheye-state-routing-in.pdf Archived 2010-07-21 at the Wayback Machine [ bare URL PDF ]
  2. ↑ "Draft-ietf-manet-FSR-03". Ietf Datatracker.
  3. ↑ https://github.com/OLSR/olsrd/blob/master/unmaintained/README-Link-Quality-Fish-Eye.txt [ bare URL plain text file ]
  4. ↑ Yasir Faheem, Jean Louis Rougier: Loop avoidance for Fish-Eye OLSR in sparse wireless mesh networks
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.