On-demand loop-free multipath routing (ROAM)

• US 7,035,227 B2
• Filed: 10/09/2001
• Issued: 04/25/2006
• 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: Garcia-Luna-Aceves, Jose J., Raju, Jyoti
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): KHOO, FOONG LIN
• Application Number:
  US09/975,089
• Publication Number:
  US 20020101869A1
• Time in Patent Office: 1,659 Days
• Field of Search: 370/351, 370/254, 370/255, 370/256, 709/238, 709/222
• US Class Current: 370/254
• 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 receives a data packet for said destination; and

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

wherein the step of maintaining said routing table entry comprises;

time stamping a route when said route is entered into said routing table and 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.

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 further comprises sending a delete update with a negative reported distance to a neighboring router.

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

12. A method as recited in claim 10, 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.

13. 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 receives a data packet for said destination;

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

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

wherein said step of deleting said routing table entry comprises;

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

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.

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

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

16. A method as recited in claim 14, 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.

17. 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 and

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.

18. A method as recited in claim 17, 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.

19. A method as recited in claim 18, 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.

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

21. A method as recited in claim 20, 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.

22. A method as recited in claim 18:

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.

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

24. A method as recited in claim 23:

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.

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

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

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

28. A method as recited in claim 26, 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.

29. 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 and

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.

30. A method as recited in claim 29, 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.

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

32. A method as recited in claim 31, 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.

33. A method as recited in claim 29:

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.

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

35. A method as recited in claim 34:

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.

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

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

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

39. A method as recited in claim 37, 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.