On-Demand Loop-Free Multipath Routing

Background

Business activities are increasingly conducted over the internet, and thus, activities such as financial services, securities exchanges, and emergency services will require reliable Internet connectivity. On-demand routing protocols provide this reliability by providing multiple gateway links to the internet. These networks are useful in all tactical and commercial scenarios in which there is no base-station infrastructure present. However, one issue with using multiple links is the manual configuration of internal routers, which requires considerable planning and monitoring. The current systems also decrease network performance due to the counting-to-infinity problem. Flood search is a way to distribute routing information updates quickly to every node in a large network. Under current on-demand routing protocols, when a destination fails, the flood-search for the destination also fails, but the source is unable to determine whether it should start another flood search. This counting-to-infinity problem also causes the network to run a routing protocol that is susceptible to a unique form of attack. Moreover, a malicious router can indefinitely direct a network for a destination that does not exist, thus causing network congestion. Therefore, a need exists for an on-demand routing protocol that provides for bandwidth efficient routing without unnecessary search flooding.

Description

Scientists at the University of California have developed a novel on-demand routing protocol for wired and wireless networks.This routing on-demand acyclic multipath (ROAM) system establishes and maintains routes using diffusing computations. This on-demand protocol limits the amount of bandwidth consumed by maintaining routes to only those destinations for which a source has data traffic. ROAM provides loop-free paths using only distances to destinations. The invention also provides a solution to the “counting-to-infinity problem” within existing on-demand routing protocols. In ROAM, a search query in a connected component results in either the source requesting a route to the destination to obtain its answer, or all the routers determining that the destination is unreachable. Therefore, ROAM eliminates the need for application-level mechanisms to prevent excessive flooding or searching if destinations are not reachable. The present invention satisfies all routing needs, and overcomes the deficiencies of previously developed routing protocols.

Applications

This new invention has several applications in wired and wireless networks, such as:

• Mobile ad-hoc networks
• Wireless networks with static nodes
• Internet networks

Advantages

• Provides multiple loop-free paths without the need for complete path information, periodically refreshed sequence numbers, or time stamps
• Eliminates repeated flood searches by solving the search-to-infinity problem
• Limits the amount of bandwidth consumed

Patent Status