Method and apparatus for route discovery within a communication system

• US 20040264422A1
• Filed: 06/25/2003
• Published: 12/30/2004
• Est. Priority Date: 06/25/2003
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Calcev, George, Fonseca, Benedito J. Jr., Bonta, Jeffrey D.
• Granted Patent: US 7,466,665 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

An overlay communication system (120) aides determining a route between nodes (101-103) in an underlay communication system (110). In particular, when a first node (102) wishes to discover a route to a second node (103), the first node notifies the overlay communication system, which notifies all nodes in the underlay communication system of the desire. Both the first and the second nodes begin flooding the underlay system simultaneously. When a node in the underlay system hears both the flood messages from the first and the second node, the overlay communication system is notified and stops all flooding. The route information is then provided to the first and the second nodes via the overlay communication system.

Claims

1. A method for route discovery, the method comprising the steps of:

determining that a first node needs to communicate with a second node;

sending, by the first node, a message to an overlay communication system notifying the overlay communication system of the need to communicate with the second node;

receiving, from the overlay communication system, instructions to broadcast a route-discovery message;

broadcasting the route discovery message; and

receiving route information from the overlay communication system.

2. The method of claim 1 wherein the step of sending the message to the overlay communication system comprises the step of sending the message to a cellular communication system.

3. The method of claim 1 wherein the step of receiving route information comprises the step of receiving a sequenced list of IP addresses.

4. A method comprising the steps of:

receiving, by a first node, from an overlay communication system, a message instructing the first node to broadcast a route discovery message, wherein the first node exists within an underlay communication system; and

broadcasting the route discovery message.

5. The method of claim 4 wherein the step of receiving from the overlay communication system comprises the step of receiving from a cellular communication system.

6. A method for operating a node within an underlay communication system, the method comprising the steps of:

receiving a route-discovery message from a first node;

receiving a route-discovery message from a second node;

determining route information based on the route-discovery messages; and

transmitting the route information to the first node.

7. The method of claim 6 wherein the step of transmitting the route information comprises the step of transmitting the route information through an overlay communication system.

8. The method of claim 6 wherein the step of transmitting the route information comprises the step of transmitting the route information through the underlay communication system.

9. The method of claim 6 wherein the step of transmitting the route information comprises the step of transmitting the route information through an overlay cellular communication system.

10. A method comprising the steps of:

receiving a message from a first node in an underlay communication system, the message indicating a need to discover a route to a second node;

broadcasting a message to nodes within the underlay communication system, the message instructing the nodes to monitor for flood messages from the first and the second nodes;

receiving a message from a third node in an underlay communication system, the message comprising route information; and

transmitting the route information to the first node.

11. The method of claim 10 wherein the step of receiving the message comprises the step of receiving the message by an overlay communication system.

12. The method of claim 10 wherein the step of receiving the message comprises the step of receiving the message by an overlay cellular communication system.

13. The method of claim 10 wherein the step of receiving the route information from the third node comprises the step of receiving a sequenced list of IP addresses from the third node.

14. The method of claim 10 further comprising the step of transmitting a flood stop message causing nodes within the underlay communication system to cease transmission of flood messages.

15. An apparatus comprising:

means for determining that a first node needs to communicate with a second node;

means for sending, by the first node, a message to an overlay communication system notifying the overlay communication system of the need to communicate with the second node;

means for receiving, from the overlay communication system, instructions to broadcast a route-discovery message;

means for broadcasting the route discovery message; and

means for receiving route information from the overlay communication system.

16. An apparatus comprising:

means for receiving, by a first node, from an overlay communication system, a message instructing the first node to broadcast a route discovery message, wherein the first node exists within an underlay communication system; and

means for broadcasting the route discovery message.

17. An apparatus comprising:

means for receiving a route-discovery message from a first node;

means for receiving a route-discovery message from a second node;

means for determining route information based on the route-discovery messages; and

means for transmitting the route information to the first and the second nodes.

18. An apparatus comprising:

means for receiving a message from a first node in an underlay communication system, the message indicating a need to discover a route to a second node;

means for broadcasting a message to nodes within the underlay communication system, the message instructing the nodes to monitor for flood messages from the first and the second nodes;

means for receiving a message from a third node in an underlay communication system, the message comprising route information; and

means for transmitting the route information to the first nodes.