Scalable Source Routing

Last updated

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]

Contents

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.

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

SSR: Routing without flooding. Node 1 routing a message via node 17, 32, 39 to destination node 42 (for a detailed description see ). Pushing2006-routing-fuhrmann.png
SSR: Routing without flooding. Node 1 routing a message via node 17, 32, 39 to destination node 42 (for a detailed description see ).

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

Disadvantages

See also

Related Research Articles

Gnutella is a peer-to-peer network protocol. Founded in 2000, it was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model.

<span class="mw-page-title-main">Peer-to-peer</span> Type of decentralized and distributed network architecture

Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the network. This forms a peer-to-peer network of nodes.

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

<span class="mw-page-title-main">Distributed hash table</span> Decentralized distributed system with lookup service

A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. Keys are unique identifiers which map to particular values, which in turn can be anything from addresses, to documents, to arbitrary data. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

<span class="mw-page-title-main">Wireless mesh network</span> Radio nodes organized in a mesh topology

A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network.

<span class="mw-page-title-main">Optimized Link State Routing Protocol</span> IP routing protocol optimized for mobile ad hoc networks

The Optimized Link State Routing Protocol (OLSR) is an IP routing protocol optimized for mobile ad hoc networks, which can also be used on other wireless ad hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.

An overlay network is a computer network that is layered on top of another network. This concept of overlay networking is distinct from the traditional concept of OSI layered networks, and almost always assumes that the underlay network is an IP network of some kind.

Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting node requests one. However, it uses source routing instead of relying on the routing table at each intermediate device.

The Neighbor Discovery Protocol (NDP), or simply Neighbor Discovery (ND), is a protocol of the Internet protocol suite used with Internet Protocol Version 6 (IPv6). It operates at the link layer of the Internet model, and is responsible for gathering various information required for network communication, including the configuration of local connections and the domain name servers and gateways.

<span class="mw-page-title-main">Flooding (computer networking)</span> Simple routing algorithm sending incoming packets to all other links than the sender

Flooding is used in computer network routing algorithms in which every incoming packet is sent through every outgoing link except the one it arrived on.

<span class="mw-page-title-main">Computer network</span> Network that allows computers to share resources and communicate with each other

A computer network is a set of computers sharing resources located on or provided by network nodes. Computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are made up of telecommunication network technologies based on physically wired, optical, and wireless radio-frequency methods that may be arranged in a variety of network topologies.

Pastry is an overlay network and routing network for the implementation of a distributed hash table (DHT) similar to Chord. The key–value pairs are stored in a redundant peer-to-peer network of connected Internet hosts. The protocol is bootstrapped by supplying it with the IP address of a peer already in the network and from then on via the routing table which is dynamically built and repaired. It is claimed that because of its redundant and decentralized nature there is no single point of failure and any single node can leave the network at any time without warning and with little or no chance of data loss. The protocol is also capable of using a routing metric supplied by an outside program, such as ping or traceroute, to determine the best routes to store in its routing table.

Tapestry is a peer-to-peer overlay network which provides a distributed hash table, routing, and multicasting infrastructure for distributed applications. The Tapestry peer-to-peer system offers efficient, scalable, self-repairing, location-aware routing to nearby resources.

A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, each node participates in routing by forwarding data for other nodes. The determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.

<span class="mw-page-title-main">B.A.T.M.A.N.</span> Routing protocol for multi-hop mobile ad hoc networks

The Better Approach to Mobile Ad-hoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR).

Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. In the area of packet radio networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

A social VPN is a virtual private network that is created among individual peers, automatically, based on relationships established by them through a social networking service. A social VPN aims at providing peer-to-peer (P2P) network connectivity between a user and his or her friends, in an easy to set up manner that hides from the users the complexity in setting up and maintaining authenticated/encrypted end-to-end VPN tunnels.

IEEE 802.11s is a wireless local area network (WLAN) standard and an IEEE 802.11 amendment for mesh networking, defining how wireless devices can interconnect to create a wireless LAN mesh network, which may be used for relatively fixed topologies and wireless ad hoc networks. The IEEE 802.11s task group drew upon volunteers from university and industry to provide specifications and possible design solutions for wireless mesh networking. As a standard, the document was iterated and revised many times prior to finalization.

References

  1. 1 2 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. ISBN   978-3-540-25809-4 . 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. hdl:11693/38342. ISBN   978-0-387-09750-3. S2CID   16386810.
  4. ↑ Zahn, Thomas; Greg O'Shea; Antony Rowstron (2009). "An empirical study of flooding in mesh networks" (PDF). SIGMETRICS Perform. Eval. Rev. ACM. 37 (2): 57–58. doi:10.1145/1639562.1639584. S2CID   11285886 . Retrieved 16 April 2010.
  5. ↑ 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)
  6. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.