Method and apparatus for route discovery within a communication system

• US 7,466,665 B2
• Filed: 06/25/2003
• Issued: 12/16/2008
• 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.
• Primary Examiner(s): Chan; Wing F
• Assistant Examiner(s): SOL, ANTHONY M
• Application Number:
  US10/603,558
• Publication Number:
  US 20040264422A1
• Time in Patent Office: 2,001 Days
• Field of Search: None
• US Class Current: 370/255
• 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, wherein the first and the second nodes are part of an underlay ad-hoc communication system;

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 by the first node, from the overlay communication system, instructions to broadcast a route-discovery message;

broadcasting the route discovery message within the underlay communication system;

receiving by the first node, a message instructing nodes within the ad-hoc communication system to stop flooding route discovery messages; and

receiving by the first node 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 wherein the first node is a node to which a route is trying to be discovered;

determining that the first node'"'"'s identification is contained within the message; and

broadcasting the route discovery message within the underlay communication system.

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 message instructing nodes within an ad-hoc communication system to listen for a route discovery message from a first node and a route discovery message from a second node;

receiving the route-discovery message from a first node, wherein the first node is part of an underlay communication system;

receiving the route-discovery message from a second node, wherein the second node is part of the underlay communication system;

determining identifications of senders of the route-discovery messages;

determining if the identifications are contained within the message instructing the nodes to listen for the route discovery message;

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

transmitting the route information through an overlay communication system 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 cellular communication system.

8. A method comprising the steps of:

receiving at a base station in an overlay communication system, 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 by the base station, 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 by the base station a message from a third node in an underlay communication system, the message comprising route information;

transmitting by the base station, a message to stop flood messages; and

transmitting by the base station, the route information to the first node.

9. The method of claim 8 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.

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

11. An apparatus comprising:

means for determining that a first node needs to communicate with a second node, wherein the first and the second nodes are part of an underlay communication system;

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 by the first node, from the overlay communication system, instructions to broadcast a route-discovery message;

means for broadcasting by the first node, the route discovery message;

means for receiving by the first node, a message instructing nodes within the ad-hoc communication system to stop flooding route discovery messages; and

means for receiving by the first node route information from the overlay communication system.

12. 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 wherein the first node is a node to which a route is trying to be discovered;

means for determining that the first node'"'"'s identification is contained within the message; and

means for broadcasting the route discovery message within the underlay communication system.

13. An apparatus comprising:

means for receiving a message instructing nodes within an ad-hoc communication system to listen for a route discovery message from a first node and a route discovery message from a second node;

means for receiving the route-discovery message from a first node, wherein the first node is part of an underlay communication system;

means for receiving the route-discovery message from a second node, wherein the second node is part of the underlay communication system;

means for determining identifications of senders of the route-discovery messages;

means for determining if the identifications are contained within the message instructing the nodes to listen for the route discovery message;

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

means for transmitting the route information through an overlay communication system to the first and the second nodes.

14. An apparatus comprising:

means for receiving at a base station in an overlay communication system, 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 by the base station, 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 by the base station a message from a third node in an underlay communication system, the message comprising route information;

means for transmitting by the base station, a message to stop flood messages; and

means for transmitting by the base station the route information to the first node.