Scalable Source Routing: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
<ref>{{cite |
<ref>{{cite book |last=Fuhrmann |first=Thomas |title=NETWORKING 2005 |chapter=A Self-organizing Routing Scheme for Random Networks |volume=3462/2005 |publisher=Springer Berlin / Heidelberg |series=Lecture Notes in Computer Science |year=2005 |month=May |pages=1366-1370 |doi=10.1007/11422778_116 |url=http://os.ibds.kit.edu/downloads/publ_2005_fuhrmann_routing-scheme.pdf |format=PDF |affiliation=University of Karlsruhe, Germany |accessdate=2010-04-15}}</ref> |
||
==Concepts== |
==Concepts== |
||
Revision as of 16:48, 16 April 2010
Scalable Source Routing (SSR) is a routing protocol for unstructured networks such as mobile ad hoc networks, mesh networks, or sensor networks. It is based on the idea of "pushing Chord into the underlay"[1]: SSR combines source routing with routing along a virtual ring.
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 knowledge about this common structure enables the nodes to route packets without having information about the global topology of the underlying physical network (cf. link state routing) or flooding to gather routing information (cf. distance-vector routing).
The distance metric in the virtual ring is simply the absolute difference of SSR addresses. Packets travel along the ring in one direction, usually towards ascending 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.
A route cache containing source routes to other nodes provides a node with short cuts in the virtual ring, corresponding to Chord's finger table.
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 poisoning of the nodes' route caches with outdated information.
DHT semantics
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].
Classification
SSR has reactive as well as proactive components, making it a hybrid routing protocol. Conceptually it is similar to Virtual Ring Routing.
See also
- List of ad-hoc routing protocols
- Virtual Ring Routing
- Mesh networks
- Wireless mesh network
- Mobile ad hoc network
References
- ^ Fuhrmann, Thomas (2006). "Pushing Chord into the Underlay: Scalable Routing for Hybrid MANETs" (PDF). System Architecture Group, Technical University of Karlsruhe (TH), Germany. Retrieved 2010-04-15.
{{cite journal}}: Cite journal requires|journal=(help); Unknown parameter|coauthors=ignored (|author=suggested) (help); Unknown parameter|month=ignored (help) - ^ Fuhrmann, Thomas (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 2010-04-15.
{{cite book}}: Unknown parameter|affiliation=ignored (help); Unknown parameter|month=ignored (help) - ^ Castro, Marcel C. (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.
{{cite book}}:|access-date=requires|url=(help); Unknown parameter|coauthors=ignored (|author=suggested) (help); Unknown parameter|month=ignored (help) - ^ Zahn, Thomas (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 2010-04-16.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Caesar, Matthew (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 2010-04-16.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help); Unknown parameter|month=ignored (help)