2 Proactive routing protocols

Proactive routing protocols continuously try to maintain up-to-date routing information on every node in the network. This has as advantage that connection times are fast, because routing information is already available when the first packet is sent. A disadvantage of proactive protocols is that they continuously use resources to communicate routing information, even when there is no traffic.

2.1 Link State

In the link-state routing protocol (commonly abbreviated as LS), each forwarding node floods the network with information about its neighbours. Every other router updates its router table with this information and thus has a full overview of the network. The advantage of LS is that every router knows the shortest path to every destination, making forwarding packets easy.

Link-state works very well in static, wired networks. In a large wireless network, In large wireless networks, however, radio links are unreliable, nodes move and devices are shutdown. In such a situation, flooding the network every time the network topology changes is not practical. Providing every router with an up-to-date routing table is impossible, since the topology may change again before the message communicating the old change has reached every router.

2.2 Distributed Bellman-Ford

In distributed Bellman-Ford, on which many routing protocols are based, each node sends its neighbours a routing table periodically. In this routing table is information on the distance to each node in the network.

When a node receives routing tables from its neighbours, it updates its own routing table by using the shortest path to each destination. If node A advertises a distance of 30 to node C, while node B advertises a distance of 20 to node C, packets to node C will be routed through B.

Count to infinity
Figure 1: Count-to-infinity problem

This algorithm suffers from the count-to-infinity problem, which means that if a node goes down, it takes very long before this information spreads through the network. As seen in fig. 1, each node updates its information based on old information from other nodes, making the path longer on each update. This property makes it unsuitable for ad-hoc networks, where nodes may fail frequently. [Tan03] [Ace94]

2.3 Optimized Link State Routing

OSLR ([RFC3626], is very similar to link-state, with a few optimizations. Each node selects some nodes in its neighbourhood which are called multipoint relays (MPRs). Only these nodes will forward messages for the node. Update messages are flooded over the entire network just as in link-state, but now only the MPRs relay the messages, decreasing the overal bandwidth. A node chooses its MPR in such a way that it can reach the whole network.

Passive nodes
Figure 2: Node B does not have to forward messages

[Che01] also proposes to make some nodes play a passive role, with a protocol named Span. Although Span has the goal of limiting power usage, OSLR wants to decrease the overhead. As can be seen in fig. 2, node B does not have to relay messages. If it does anyway, it will interfere with other relaying nodes. Selecting active and passive nodes can decrease resource usage in any protocol.

OSLS, however, still floods the network and this incurs a large overhead. Moreover, in sparse networks many nodes will be selected as MPR, making the optimization technique useless.

2.4 Global State Routing

Because of the advantages of the link-state routing protocol, research has been done to make the link-state protocol more scalable. This is typically done by not flooding the network with routing information, but sending only a part or sending it only to some nodes.

[Ger98] describes a protocol (GSR) which only exchanges link-state information with neighbours, instead of flooding it over the network. Each node has a table of all nodes in the network. Periodically, each node sends its neighbours this list so that they can update their network topology information.

2.5 Fisheye State Routing

Fisheye routing is based on the assumption that routes to nodes which are far away do not have to be precise. The routing table is accurate for nodes close by, but approximate for nodes far away. When a packet is sent to a node, the route will become more precise when the packet closes in on the destination.

Fisheye state routing ([Iwa99]) is based on GSR and also only sends packets to neighbours. It works by not sending all available link-state information, but focussing on the network topology in the direct neighbourhood of the node. Changes in the network which occur close by are send at a high frequency. Distant changes are send in a lower frequency. Not knowing how to reach a distant destination exactly is not a problem, since the route becomes more accurate as the packet gets closer to its destination.

Since both GSR and FSR only transmit information to their direct neighbours, it may take a long time before a change in topology has been communicated through the network.

2.6 Hazy Sighted Link State

Hazy sighted link state (HSLS), as proposed in [San03], limits the spreading of topology information in space and time. It assumes that changes in the network close by are more important than changes far away, as in GSR. Instead of only sending updates to its neighbours, HSLS uses the a time-to-live (TTL) field to limit to which nodes the information spreads.

For example, each node within one hop is sent a Link State Update (LSU) packet each second. Nodes two hops away are sent a LSU each two seconds, etc. Using this scheme, a node will receive LSU packets each second from nodes within its range and it will recieve update packets each eight seconds from nodes which are eight hops away. This makes sure that a node has precise information on nodes close by, with the minimal overhead.

The optimal parameters for the timing and TTL can be calculated from variables such as mobility, size of the network and traffic. This makes it possible to optimize the protocol for each network, incurring the lowest overhead possible.

HSLS communicates routing information relatively fast throughout the network, without using flooding, which makes it scalable. Furthermore, being a proactive protocol, it does not have a delay when setting up a connection.