Routing – Spray and wait routing protocol

protocol-theoryrouting

What is the basic difference between spray and wait routing protocol and other routing protocols? And what is the main benefit of using the spray and wait protocol?

Best Answer

Most network routing protocols are designed for use in fairly stable networks where paths can be known, but they have the ability to change dynamically as the network changes. These protocols are deterministic, and they are optimized for the accurate, speedy delivery of network traffic.

The Spray and Wait algorithm is designed to work where paths may be unknown and may frequently change. These networks are tolerant of delay in delivery of traffic.

The abstract for Spray and Wait describes it pretty well:

Intermittently connected mobile networks are sparse wireless networks where most of the time there does not exist a complete path from the source to the destination. These networks fall into the general category of Delay Tolerant Networks. There are many real networks that follow this paradigm, for example, wildlife tracking sensor networks, military networks, inter-planetary networks, etc. In this context, conventional routing schemes would fail.To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. Furthermore, proposed efforts to significantly reduce the overhead of flooding-based schemes have often be plagued by large delays. With this in mind, we introduce a new routing scheme, called Spray and Wait, that "sprays" a number of copies into the network, and then "waits" till one of these nodes meets the destination.Using theory and simulations we show that Spray and Wait outperforms all existing schemes with respect to both average message delivery delay and number of transmissions per message delivered; its overall performance is close to the optimal scheme. Furthermore, it is highly scalable retaining good performance under a large range of scenarios, unlike other schemes. Finally, it is simple to implement and to optimize in order to achieve given performance goals in practice.

http://dl.acm.org/citation.cfm?id=1080143

Related Solutions

Routing – Difference Between Routing Protocols and Routed Protocols

Routing protocols allow routers to exchange routing information so they can learn about networks from other routers. A router in Barcelona can learn about networks in Zagreb via a routing protocol, so that it can forward traffic to Zagreb. Your ISP learns about networks from other ISPs via a routing protocol, so you can watch funny cat videos on YouTube.

Examples of routing protocols are OSPF, EIGRP, BGP and IS-IS.

A routed protocol is a protocol for sending data between end hosts. To be "routed," it has to have a hierarchical addressing scheme that indicates "where" the host is. The hierarchy lets a router (or host) determine where the packet should be sent in order to reach it's destination.

Practically speaking, there is only one routed protocol in use, and that is IP (version 4 and version 6). IP addresses have a network portion and a host portion (the subnet mask tells you how to separate the two). The network portion of the address lets the host look in its routing table to determine what is the best way to forward the packet.

Non-routed protocols are essentially obsolete in the age of the Internet, but NetBIOS might be one you're somewhat familiar with.

Changing routing protocols administrative distance

According to your first question, the answer is not as easy as you might think.

When there are multiple routing protocols configured, all of them will run and form adjacencies to their next hop routers and exchange routing information. Most if not each routing protocol has a routing protocol specific information database, containing routes exchanged by this routing protocol. On cisco gear you can view them for example with sh ip ospf database or sh ip rip database.

Now, the router has to decide which routes are placed in his actual routing information base (also called RIB or routing table). Here, the most important factor is the "precision" of a route. That is: the higher the prefix length is, the more exact is the route and the more preferred. Only if there are two identical routes, that is same subnet address and same subnet mask or prefix length, the administrative distance comes into play.

Suppose the following example (note that ADs are default values from Cisco):

192.168.100.0/24 learned by OSPF, AD is 110
192.168.100.128/25 learned by RIP, AD is 120
192.168.200.0/24 directly connected, AD is 0
192.168.200.0/24 static route, AD is 1

In this example, the first route learned by OSPF will be placed in the routing table. As the second one is more specific (25 bit prefix instead of 24) it is also added to the routing table. Note that while the second route is included in the first one, they are not equal due to the different prefix length. The third and fourth routes are identical, but the AD of directly connected routes is always 0 and hence this route is preferred.

So basically you can influence routing decision in at least three ways:

In each routing protocol, you can tweak metrics
Change the AD of routing protocols
Advertise more specific routes which are always preferred.

Changing the AD

For Cisco gear, you can change the AD of routing protocols like this:

! static routes - the last optional value (50) is the AD
ip route 192.168.100.0 255.255.255.0 1.2.3.4 50

! OSPF - can be changed in the OSPF routing process, is slightly more complicated
! The generic command is: distance <AD> <source addr> <wildcard-mask> <ACL>
! AD is configured per source router, and an additional ACL is required
! To change AD of all routes to 85 (instead of default 110)
access-list 10 permit any

router ospf 1
    distance 85 0.0.0.0 255.255.255.255 10

! RIP
! For RIP, the command is:
! distance admin-distance [ prefix prefix-length | prefix mask ]
! The command needs to be entered inside the routing process, where the last 
! elements are not required but can be used to conditionally change the distance

router rip
    distance 50

Beware that you can never change the AD to be lower than or equal to 0, hence routing protocols cannot compete with directly connected routes using the administrative distance. If you need a routing protocol to override directly connected routes you should ask yourself why you need the direct connection. Technically however you could advertise more specific routes.

Best Answer

Related Solutions

Routing – Difference Between Routing Protocols and Routed Protocols

Changing routing protocols administrative distance

Related Topic