Fuzzy routing

• US 20050255848A1
• Filed: 05/10/2005
• Published: 11/17/2005
• Est. Priority Date: 05/11/2004
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: OPNET Technologies Incorporated (Riverbed Technology Incorporated)
• Inventors: Cohen, Alain J.
• Granted Patent: US 8,005,019 B2
• Time in Patent Office: Days
• US Class Current: 455/445
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A system and method optimizes the information flow regarding node location across a network by controlling the propagation of this information based on distance from the node. Location servers that are near to a node receive detailed information regarding the node'"'"'s location; location servers that are farther from the node receive less detailed information. In like manner, periodic updates are provided less frequently to distant location servers, and preferably also based on the velocity of a mobile node, or on a priority associated with the mobile node. The location information provided in a message addressed to a node can be minimal when the message is transmitted, and additional detail can be added to this location information by routing nodes as the message is routed closer to its destination, based on information provided by the location servers.

Claims

1. A router comprising:

a receiver that is configured to receive a message having a destination ID and a destination location,

a locator that is configured to;

determine an updated location corresponding to the destination ID, and

update the destination location in the message with the updated location, and

a transmitter that is configured to transmit the message, based on the destination location in the message.

2. The router of claim 1, wherein

the locator is further configured to determine the updated location and update the destination location based on a status of the destination location in the message.

3. The router of claim 2, wherein

the status of the destination location in the message includes:

a resolution associated with the destination location,

a time associated with the destination location, and

a number of transmissions of the message by other routers.

4. The router of claim 2, wherein

the locator is further configured to update the status of the destination location when it updates the destination location in the message.

5. The router of claim 1, wherein

the router is configured to:

store the updated location information corresponding to the destination ID, and

update the destination location in the other messages that are addressed to the destination ID with the updated location information.

6. The router of claim 1, further including

a location server that is configured to:

receive the updated location corresponding to the destination ID,

store the updated location corresponding to the destination ID, and

provide the updated location to the locator upon request.

7. The router of claim 6, wherein

the location server is further configured to forward an abstract location corresponding to the destination ID to at least one other location server.

8. The router of claim 1, wherein

the transmitter is further configured to transmit the message based on a route followed by the message thus far.

9. The router of claim 1, wherein

the transmitter is further configured to transmit the message based on characteristics associated with one or more other routers along a path to the destination location.

10. The router of claim 9, wherein

the characteristics associated with each other router of the one or more other routers include one or more of:

a location of the other router,

neighbors of the other router,

location servers associated with the other router, and

a location database associated with the other router.

11. A server comprising:

a receiver that is configured to receive a location corresponding to a node,

a processor that is configured to determine an abstract location corresponding to the node, based on the location, and

a transmitter that is configured to transmit the abstract location corresponding to the node to one or more other servers.

12. The server of claim 11, wherein

the processor is further configured to provide the location corresponding to the node to other nodes upon request.

13. The server of claim 11, wherein

the processor is further configured to determine a status of the node, and

the transmitter is configured to transmit one of the location and the abstract location to each of the one or more other servers based on the status of the node.

14. The server of claim 13, wherein

the status includes at least one of:

a priority of the node,

a velocity of the node, and

a time of a prior communication from the node.

15. The server of claim 11, wherein

the node, the server, and the one or more other servers are included in a network that is partitioned into zones, and

the processor is configured to determine the abstract location corresponding to the node based on the zones associated with the node and each of the one or more other servers.

16. The server of claim 15, wherein

the zones include a hierarchy of partitions of the network, and

the abstract location is configured to correspond to the hierarchy of the partitions of the network.

17. The server of claim 15, wherein

the processor is further configured to select the one or more other servers from among a plurality of servers in the network, based on a transition of the node from one of the zones to another of the zones.

18. The server of claim 11, wherein

the processor is further configured to select the one or more other servers from among a plurality of servers in the network, based on at least one of:

a flooding parameter,

a priority of the node,

a change of location of the node,

a bandwidth requirement of the node, and

a time of a prior communication from the node.

19. The server of claim 11, wherein

the processor is further configured to select the one or more other servers from among a plurality of servers in the network, based on at least one of:

a flooding parameter,

a location of the other server, and

capabilities of the other server.

20. A method of routing, comprising:

receiving a message having a destination ID and a destination location,

determining an updated location corresponding to the destination ID, and

updating the destination location in the message with the updated location, and

transmitting the message, based on the destination location in the message.

21. The method of claim 20, wherein

determining and updating the updated location is based on a status of the destination location in the message.

22. The method of claim 21, wherein

the status of the destination location in the message includes:

a resolution associated with the destination location,

a time associated with the destination location, and

a number of transmissions of the message by other routers.

23. The method of claim 20, wherein

updating the destination location in the message includes updating a status of the destination location.

24. The method of claim 20, including:

storing the updated location information corresponding to the destination ID, and

updating the destination location in the other messages that are addressed to the destination ID with the updated location information.

25. The method of claim 20, including:

receiving the updated location corresponding to the destination ID,

storing the updated location corresponding to the destination ID.

26. The method of claim 25, including

forwarding an abstract location corresponding to the destination ID to a node in a network.

27. The method of claim 20, wherein

transmitting the message is based on a route followed by the message thus far.

28. The method of claim 20, wherein

transmitting the message is based on characteristics associated with one or more routers along a path to the destination location.

29. The method of claim 28, wherein

the characteristics associated with each router of the one or more routers include one or more of:

a location of the router,

neighbors of the router,

location servers associated with the router, and

a location database associated with the router.

30. A method of communicating location information, comprising:

receiving a location corresponding to a node,

determining an abstract location corresponding to the node, based on the location, and

transmitting the abstract location corresponding to the node to one or more servers.

31. The method of claim 30, including

providing the location corresponding to the node to other nodes upon request.

32. The method of claim 30, including

determining a status of the node, and

transmitting the abstract location to each of the one or more servers based on the status of the node.

33. The method of claim 30, wherein

the status includes at least one of:

a priority of the node,

a velocity of the node, and

a time of a prior communication from the node.

34. The method of claim 30, including:

partitioning a network into zones, and

determining the abstract location corresponding to the node based on the zones associated with the node and each of the one or more servers.

35. The method of claim 34, wherein

the zones include a hierarchy of partitions of the network, and

the abstract location is configured to correspond to the hierarchy of the partitions of the network.

36. The method of claim 30, including

selecting the one or more servers from among a plurality of servers in the network based on a transition of the node from one of the zones to another of the zones.

37. The method of claim 30, wherein

selecting the one or more servers from among a plurality of servers in the network based on at least one of:

a flooding parameter,

a priority of the node,

a velocity of the node,

a bandwidth requirement of the node, and

a time of a prior communication from the node.

38. The method of claim 30, including

selecting the one or more servers from among a plurality of servers in the network based on at least one of:

a flooding parameter,

a location of each server, and

capabilities of each server.