On-demand loop-free multipath routing (ROAM)

• US 20020101869A1
• Filed: 10/09/2001
• Published: 08/01/2002
• Est. Priority Date: 10/10/2000
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Raju, Jyoti, Garcia-Luna-Aceves, J. J.
• Granted Patent: US 7,035,227 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/023 Limited or focused flooding to selected areas of a network
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A method is described for distance vector routing of on-demand traffic between routers within an ad-hoc network maintaining multiple loop-free paths to destinations. Each router maintains routing table entries only for destinations associated with data flows through the router which reduce the amount of storage space and bandwidth required for routing table maintenance. Diffusing computations are utilized for establishing and maintaining the routes within the network. The sending of unnecessary flood searches and search-to-infinity problems are avoided, while the protocol decreases the vulnerability of the network to various service attacks along with router failures, fading, and drop outs.

Claims

1. A method for on-demand routing of data packets in a wired or wireless data network, comprising:

creating a routing table entry in a router from a source to a destination when said router receive a data packet for said destination; and

maintaining said routing table entry until said router no longer receives data traffic from said source.

2. A method as recited in claim 1, wherein said step of creating a routing table entry comprises:

starting a diffusing search if said router receives a data packet for routing to a destination for which it has no routing table entry.

3. A method as recited in claim 2, wherein said diffusing search propagates out on said network from said source on a hop-by-hop basis until it reaches a router that has a routing table entry for said destination.

4. A method as recited in claim 3, wherein a router that has a routing table entry for said destination replies with distance from said source to said router.

5. A method as recited in claim 4, wherein at the end of said diffusing search, said source either obtains a finite distance to said destination or all neighboring nodes determine that said destination is unreachable.

6. A method as recited in claim 2:

wherein said router has a routing table and a distance table; and

wherein at the start of said diffusing search said router adds the destination to its routing table and distance table, becomes active for the destination, and sends a query to a neighboring router.

7. A method as recited in claim 6, wherein said neighboring router reports a distance in response to said query.

8. A method as recited in claim 7:

wherein a neighboring router has a routing table and a distance table; and

wherein a neighboring router that receives a query for a destination but has no routing table entry for the destination adds the destination to its routing table and distance table, becomes active for the destination, and forwards the query to a neighboring router.

9. A method as recited in claim 8, wherein a reply to a query can make an active router passive.

10. A method as recited in claim 1, wherein said step of maintaining said routing table entry comprises:

time stamping a route when said route is entered into said routing table;

time stamping a route when a data packet for the destination is received by said router;

comparing the timestamp of a route to current time at the router; and

removing said route from the routing table if the difference between said time stamps exceeds a threshold.

11. A method as recited in claim 10, wherein said step of maintaining said routing table entry further comprises sending a delete update with a negative reported distance to a neighboring router.

12. A method as recited in claim 11, wherein an active router ignores a delete update from a neighboring router.

13. A method as recited in claim 11, wherein when a passive router receives a delete update, said passive router checks to determine if it has a successor other than the successor to which the delete update was sent;

if a successor exists, then said passive router does not change its routing table entries, but removes from the distance table the earlier distance reported by the neighboring router that sent the delete update; and

if a successor does not exist, then the destination entry is removed from the routing table of said passive router and said a passive router sends a delete update to a neighboring router.

15. A method as recited in claim 14, wherein said step of creating a routing table entry comprises:

starting a diffusing search if said router receives a data packet for routing to a destination for which it has no routing table entry.

16. A method as recited in claim 15, wherein said diffusing search propagates out on said network from said source on a hop-by-hop basis until it reaches a router that has a routing table entry for said destination.

17. A method as recited in claim 16, wherein a router that has a routing table entry for said destination replies with distance from said source to said router.

18. A method as recited in claim 17, wherein at the end of said diffusing search, said source either obtains a finite distance to said destination or all neighboring nodes determine that said destination is unreachable.

19. A method as recited in claim 15:

wherein said router has a routing table and a distance table; and

wherein at the start of said diffusing search said router adds the destination to its routing table and distance table, becomes active for the destination, and sends a query to a neighboring router.

20. A method as recited in claim 19, wherein said neighboring router reports a distance in response to said query.

21. A method as recited in claim 20:

wherein a neighboring router has a routing table and a distance table; and

wherein a neighboring router that receives a query for a destination but has no routing table entry for the destination adds the destination to its routing table and distance table, becomes active for the destination, and forwards the query to a neighboring router.

22. A method as recited in claim 21, wherein a reply to a query can make an active router passive.

23. A method as recited in claim 1, wherein said step of deleting said routing table entry comprises:

time stamping a route when said route is entered into said routing table;

time stamping a route when a data packet for the destination is received by said router;

comparing the timestamp of a route to current time at the router; and

removing said route from the routing table if the difference between said time stamps exceeds a threshold.

24. A method as recited in claim 23, wherein said step of maintaining said routing table entry further comprises sending a delete update with a negative reported distance to a neighboring router.

25. A method as recited in claim 24, wherein an active router ignores a delete update from a neighboring router.

26. A method as recited in claim 24, wherein when a passive router receives a delete update, said passive router checks to determine if it has a successor other than the successor to which the delete update was sent;

if a successor exists, then said passive router does not change its routing table entries, but removes from the distance table the earlier distance reported by the neighboring router that sent the delete update; and

if a successor does not exist, then the destination entry is removed from the routing table of said passive router and said a passive router sends a delete update to a neighboring router.

28. A method as recited in claim 27, wherein said step of creating a routing table entry comprises:

starting a diffusing search if said router receives a data packet for routing to a destination for which it has no routing table entry.

29. A method as recited in claim 28, wherein said diffusing search propagates out on said network from said source on a hop-by-hop basis until it reaches a router that has a routing table entry for said destination.

30. A method as recited in claim 29, wherein a router that has a routing table entry for said destination replies with distance from said source to said router.

31. A method as recited in claim 30, wherein at the end of said diffusing search, said source either obtains a finite distance to said destination or all neighboring nodes determine that said destination is unreachable.

32. A method as recited in claim 28:

wherein said router has a routing table and a distance table; and

wherein at the start of said diffusing search said router adds the destination to its routing table and distance table, becomes active for the destination, and sends a query to a neighboring router.

33. A method as recited in claim 32, wherein said neighboring router reports a distance in response to said query.

34. A method as recited in claim 33:

wherein a neighboring router has a routing table and a distance table; and

wherein a neighboring router that receives a query for a destination but has no routing table entry for the destination adds the destination to its routing table and distance table, becomes active for the destination, and forwards the query to a neighboring router.

35. A method as recited in claim 34, wherein a reply to a query can make an active router passive.

36. A method as recited in claim 27, further comprising sending a delete update with a negative reported distance to a neighboring router.

37. A method as recited in claim 36, wherein an active router ignores a delete update from a neighboring router.

38. A method as recited in claim 36, wherein when a passive router receives a delete update, said passive router checks to determine if it has a successor other than the successor to which the delete update was sent;

if a successor exists, then said passive router does not change its routing table entries, but removes from the distance table the earlier distance reported by the neighboring router that sent the delete update; and

if a successor does not exist, then the destination entry is removed from the routing table of said passive router and said a passive router sends a delete update to a neighboring router.

40. A method as recited in claim 39, wherein said diffusing search propagates out on said network from said source on a hop-by-hop basis until it reaches a router that has a routing table entry for said destination.

41. A method as recited in claim 40, wherein a router that has a routing table entry for said destination replies with distance from said source to said router.

42. A method as recited in claim 41, wherein at the end of said diffusing search, said source either obtains a finite distance to said destination or all neighboring nodes determine that said destination is unreachable.

47. A method as recited in claim 39, further comprising sending a delete update with a negative reported distance to a neighboring router.

14. A method for on-demand routing of data packets in a wired or wireless data network, comprising:

creating a routing table entry in a router from a source to a destination when said router receive a data packet for said destination; and

deleting said routing table entry if said router no longer receives data traffic from said source.

27. A method for on-demand routing of data packets in a wired or wireless data network, comprising:

creating a routing table entry in a router from a source to a destination when said router receive a data packet for said destination;

time stamping a route when said route is entered into said routing table;

time stamping a route when a data packet for the destination is received by said router;

comparing the timestamp of a route to current time at the router; and

deleting said route from said routing table if the difference between said time stamps exceeds a threshold.

39. A method for on-demand routing of data packets in a wired or wireless data network, comprising:

starting a diffusing search if a router receives a data packet for routing to a destination for which it has no routing table entry;

creating a routing table entry said router based on said diffusing search;

time stamping a route when said route is entered into said routing table;

time stamping a route when a data packet for the destination is received by said router;

comparing the timestamp of a route to current time at the router; and

deleting said route from said routing table if the difference between said time stamps exceeds a threshold.

43. A method as recited in claim 39:

wherein said router has a routing table and a distance table; and

wherein at the start of said diffusing search said router adds the destination to its routing table and distance table, becomes active for the destination, and sends a query to a neighboring router.

44. A method as recited in claim 43, wherein said neighboring router reports a distance in response to said query.

45. A method as recited in claim 44:

wherein a neighboring router has a routing table and a distance table; and

wherein a neighboring router that receives a query for a destination but has no routing table entry for the destination adds the destination to its routing table and distance table, becomes active for the destination, and forwards the query to a neighboring router.

46. A method as recited in claim 45, wherein a reply to a query can make an active router passive.

48. A method as recited in claim 47, wherein an active router ignores a delete update from a neighboring router.

49. A method as recited in claim 47, wherein when a passive router receives a delete update, said passive router checks to determine if it has a successor other than the successor to which the delete update was sent;

if a successor exists, then said passive router does not change its routing table entries, but removes from the distance table the earlier distance reported by the neighboring router that sent the delete update; and

if a successor does not exist, then the destination entry is removed from the routing table of said passive router and said a passive router sends a delete update to a neighboring router.