Scalable Source Routing
Encyclopedia
Scalable Source Routing is a routing protocol
for unstructured networks such as mobile ad hoc network
s, 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".
overlay network
s 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.
. 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.
) 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.
(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 MANET
s 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.
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.)
in SSR compared to building up per-node state (routing tables) in VRR.
Routing protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
for unstructured networks such as mobile ad hoc network
Mobile ad hoc network
A mobile ad-hoc network is a self-configuring infrastructureless network of mobile devices connected by wireless links. ad hoc is Latin and means "for this purpose"....
s, mesh networks, or sensor networks. It combines source routing
Source routing
In computer networking, source routing allows a sender of a packet to partially or completely specify the route the packet takes through the network...
with routing along a virtual ring, and is based on the idea of "pushing Chord into the underlay".
Virtual ring
SSR operates on a flat address space which is organized as a virtual ring. This is a popular concept in peer-to-peerPeer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
overlay network
Overlay network
An overlay network is a computer network which is built on the top of another network. Nodes in the overlay can be thought of as being connected by virtual or logical links, each of which corresponds to a path, perhaps through many physical links, in the underlying network...
s 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
Flooding algorithm
A flooding algorithm is an algorithm for distributing material to every part of a connected network. The name derives from the concept of inundation by a flood....
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
Absolute difference
The absolute difference of two real numbers x, y is given by |x − y|, the absolute value of their difference. It describes the distance on the real line between the points corresponding to x and y...
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 routingSource routing
In computer networking, source routing allows a sender of a packet to partially or completely specify the route the packet takes through the network...
. 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
Cache pollution
Cache pollution describes situations where an executing computer program loads data into CPU cache unnecessarily, thus causing other needed data to be evicted from the cache into lower levels of the memory hierarchy, potentially all the way down to main memory, thus causing a performance...
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 algorithmDijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
) 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 protocolRouting protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
(cf. OSI model
OSI model
The Open Systems Interconnection model is a product of the Open Systems Interconnection effort at the International Organization for Standardization. It is a prescription of characterizing and standardizing the functions of a communications system in terms of abstraction layers. Similar...
's network layer
Network layer
The network layer is layer 3 of the seven-layer OSI model of computer networking.The network layer is responsible for packet forwarding including routing through intermediate routers, whereas the data link layer is responsible for media access control, flow control and error checking.The network...
), it also provides the semantics of a distributed hash table
Distributed hash table
A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table; pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key...
. This reduces the overhead to having an overlay protocol on top of a traditional routing protocol
Routing protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
and greatly expedites lookup operations in MANET
Manet
-MANET as an abbreviation:*MANET is a mobile ad hoc network, a self-configuring mobile wireless network.*MANET database or Molecular Ancestry Network, bioinformatics database-People with the surname Manet:*Édouard Manet, a 19th-century French painter....
s which otherwise would rely on flooding
Flooding algorithm
A flooding algorithm is an algorithm for distributing material to every part of a connected network. The name derives from the concept of inundation by a flood....
, 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.
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- it looks in its route cache. If a route to the destination exists, it is used.
- and no route to the destination is known, the node routes the message to a virtually close predecessor of the destination. This intermediate node then repeats the routing process.
- and the node's route cache does not yet contain a matching route, as a fallback the node hands the message to its successor in the virtual ring. The virtual successor may not be physically close to the node, but the bootstrapping process should have established a route to it. As this fallback step is repeated, the message travels along the ring, eventually reaching the destination or being timed out.
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 routingSource routing
In computer networking, source routing allows a sender of a packet to partially or completely specify the route the packet takes through the network...
in SSR compared to building up per-node state (routing tables) in VRR.
Advantages
- Message-Efficient: Only local broadcasts, no global flooding.
- Low memory requirement. Little and limited state per node.
- DHT functionality can expedite lookups or be used to build a server-less infrastructure.
Disadvantages
- The routes found may be longer than necessary.
- The source routes add to the header size of the messages. Thus, less space is left for the payload.
See also
- List of ad-hoc routing protocols
- Virtual Ring Routing
- Mesh networks
- Wireless mesh networkWireless mesh networkA wireless mesh network is a communications network made up of radio nodes organized in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gateways.The mesh clients are often laptops, cell phones and other wireless devices while the mesh routers forward traffic...
- Mobile ad hoc networkMobile ad hoc networkA mobile ad-hoc network is a self-configuring infrastructureless network of mobile devices connected by wireless links. ad hoc is Latin and means "for this purpose"....