Jump to content

Scalable Source Routing

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Uanfala (talk | contribs) at 17:01, 3 June 2020 (typo). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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".[1]

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.[2]

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,[3][4] 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.[5]

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.[6] Another way of bootstrapping is linearization.[7])

Drawing of a virtual ring (upper half) and a physical network graph (lower half)
SSR: Routing without flooding. Node 1 routing a message via node 17, 32, 39 to destination node 42 (for a detailed description see [1]).

Routing

When a node routes a message

  1. it looks in its route cache. If a route to the destination exists, it is used.
  2. 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.
  3. 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 routing 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

References

  1. ^ a b Fuhrmann, Thomas; Pengfei Di; Kendy Kutzner; Curt Cramer (June 2006). "Pushing Chord into the Underlay: Scalable Routing for Hybrid MANETs" (PDF). System Architecture Group, Technical University of Karlsruhe (TH), Germany. Retrieved 15 April 2010. {{cite journal}}: Cite journal requires |journal= (help)
  2. ^ Fuhrmann, Thomas (May 2005). "A Self-organizing Routing Scheme for Random Networks". NETWORKING 2005 (PDF). Lecture Notes in Computer Science. Vol. 3462/2005. Springer Berlin / Heidelberg. pp. 1366–1370. doi:10.1007/11422778_116. Retrieved 15 April 2010.
  3. ^ Castro, Marcel C.; Andreas J. Kassler; Carla-Fabiana Chiasserini (March 2010). "Peer-to-Peer Overlay in Mobile Ad-Hoc Networks". Handbook of Peer-to-Peer Networking. Springer Verlag. pp. 1045–1080. doi:10.1007/978-0-387-09751-0_37. ISBN 978-0-387-09750-3.
  4. ^ Zahn, Thomas; Greg O'Shea; Antony Rowstron (2009). "An empirical study of flooding in mesh networks" (PDF). SIGMETRICS Perform. Eval. Rev. 37 (2). ACM: 57–58. doi:10.1145/1639562.1639584. Retrieved 16 April 2010.
  5. ^ Caesar, Matthew; Edmund B. Nightingale; Greg O'Shea; Antony Rowstron (September 2006). "Virtual Ring Routing: Network Routing Inspired by DHTs" (PDF). SIGCOMM Computer Communication Review. 36 (4). ACM: 351–362. doi:10.1145/1151659.1159954. Retrieved 16 April 2010.
  6. ^ Cramer, Curt; Fuhrmann, Thomas (31 January 2005). "Self-stabilizing ring networks on connected graphs" (PDF). Retrieved 26 April 2010. {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)
  7. ^ Kendy Kutzner; Thomas Fuhrmann (March 2007). "Using Linearization for Global Consistency in SSR" (PDF). Proceedings of the 4th Int. IEEE Workshop on Hot Topics in P2P Systems. Retrieved 20 April 2010. {{cite journal}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (help)

Retrieved from "https://en.wikipedia.org/w/index.php?title=Scalable_Source_Routing&oldid=960563409"