Routing algorithm for unstructured networks
Scalable Source Routing (SSR) is a routing protocol for unstructured networks such as mobile ad hoc networks, mesh networks, or sensor networks. It combines source routing with routing along a virtual ring, and is based on the idea of "pushing Chord into the underlay".
Concepts.
Virtual ring.
SSR operates on a flat address space which is organized as a virtual ring. This is a popular concept in peer-to-peer overlay networks like Chord. The common knowledge about the ring structure enables nodes to route packets without knowing the topology of the underlying physical network. While the physical network can be very dynamic, the structure of the virtual ring remains rather static. Therefore, flooding the physical network can be avoided.
Packets travel along the ring so that they decrease the virtual distance to the destination (that is, the absolute difference of the addresses). When each node knows its correct predecessor and successor in the virtual ring, delivery to the correct receiving node is guaranteed. The ring is said to be "consistent".
Often, routing is assumed to have a defined orientation in the ring, but that is merely a help to simplify theory. In practice, this is not necessary and even detrimental to performance.
The "finger table" in Chord, which provides shortcuts in the virtual ring, is replaced by a route cache.
Source routing.
In the physical network SSR utilizes source routing. Relaying nodes opportunistically cache the traversed part of the source route of a given packet. This facilitates the collection of routing information while inhibiting polluting of the nodes' route caches with outdated information.
Route aggregation.
A node does not need to have the complete path to the destination in its route cache to make use of a cache line. Instead, the message is routed towards the physical nearest node that makes progress in the virtual ring. When the message arrives at this intermediate node, that node adds information from its route cache to the source route. This step is repeated as needed. When the message arrives at the final destination, after path optimization (using Dijkstra's algorithm) a route update message is sent to the originator node, thus updating the originators route cache.
This technique facilitates the usage of fixed size route caches, which limits the per-node state and makes SSR a viable option for low memory environments.
Distributed Hash Table (DHT) functionality.
While SSR is a complete routing protocol (cf. OSI model's network layer), it also provides the semantics of a distributed hash table. This reduces the overhead to having an overlay protocol on top of a traditional routing protocol and greatly expedites lookup operations in MANETs which otherwise would rely on flooding, provided the application supports (or is modified to support) key-based routing. The provided DHT functionality also can be used to implement scalable network services in the absence of servers.
Algorithm overview.
Bootstrapping (starting the network).
Every node periodically broadcasts a "hello" message to its physical neighbors, notifying the neighbors of its existence. "Hello" messages include a list of the physical neighbors of each node. If the node finds itself included in the "hello" message of another node, it assumes a bidirectional connection, and adds the other node to its list of physical peers (to later use them for routing).
The node also sends a "neighbor notification" message to its assumed successor, to join the virtual ring. If the contacted node detects that it is not the correct successor, it replies with a message containing its best guess for the successor of the inquiring node. This is repeated until the correct virtual neighbors are found. (For a detailed description of this process, called ISPRP, see. Another way of bootstrapping is linearization.)
Routing.
When a node routes a message
Classification.
SSR has reactive as well as proactive components, making it a hybrid routing protocol. Virtual Ring Routing is conceptually similar, the biggest difference being the usage of source routing in SSR compared to building up per-node state (routing tables) in VRR.
References.
 ;templatestyles src="Reflist/styles.css" / ;