System and method for collecting routing information in a mesh network

• US 20060209720A1
• Filed: 03/21/2005
• Published: 09/21/2006
• Est. Priority Date: 03/21/2005
• Status: Active Grant

• Current Assignee: RF Monolithics, Inc. (Murata Manufacturing Co Limited)
• Original Assignee: RF Monolithics, Inc. (Murata Manufacturing Co Limited)
• Inventors: Nelson, Dan R.
• Granted Patent: US 7,606,169 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/036 Updating the topology between route computation elements, e.g. between OpenFlow controllers
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

A method includes receiving a request to identify any communication paths visible to a first router in a mesh network and broadcasting the request. The method also includes identifying one or more second routers that broadcast information received by the first router, where the one or more identified second routers are associated with the communication paths visible to the first router. The method further includes receiving at least one first response from at least one of the second routers, where the at least one first response identifies the communication paths visible to at least one of the second routers. In addition, the method includes broadcasting a second response at the first router, where the second response identifies the communication paths visible to at least one of the second routers and to the first router.

Claims

1. A method, comprising:

receiving a request to identify any communication paths visible to a first router in a mesh network;

broadcasting the request to identify the communication paths;

identifying one or more second routers that broadcast information received by the first router, the one or more identified second routers associated with the communication paths visible to the first router;

receiving at least one first response from at least one of the second routers, the at least one first response identifying the communication paths visible to at least one of the second routers; and

broadcasting a second response at the first router, the second response identifying the communication paths visible to at least one of the second routers and to the first router.

2. The method of claim 1, wherein:

the at least one first response comprises a first link list, the first link list comprising an entry for each of the routers, at least one of the entries in the first link list identifying the communication paths visible to at least one of the second routers; and

the second response comprises a second link list, the second link list comprising an entry for each of the routers, a plurality of the entries in the second link list identifying the communication paths visible to at least one of the second routers and to the first router.

3. The method of claim 1, further comprising:

synchronizing the first router to a plurality of time slots using the request to identify any communication paths.

4. The method of claim 3, wherein synchronizing the first router comprises incrementing a network reference value at each time slot up to a maximum value and then decrementing the network reference value at each time slot down to a minimum value, the incrementing and decrementing repeated a plurality of times.

5. The method of claim 4, wherein:

each of the routers is associated with a unique identifier, each unique identifier associated with a specific value of the network reference value; and

each of the routers is capable of broadcasting only when the network reference value has the specific value associated with the router'"'"'s unique identifier.

6. The method of claim 5, wherein:

broadcasting the request to identify the communication paths comprises broadcasting the request during the time slot in a selected one of a plurality of first sequences, each first sequence associated with time slots when the network reference value is incremented up to the maximum value or with time slots when the network reference value is decremented down to the minimum value; and

broadcasting the second response comprises broadcasting the second response during a selected one of a plurality of second sequences, the selected second sequence corresponding to the selected first sequence.

7. The method of claim 1, further comprising:

identifying at least one additional router that becomes visible to the first router after the second response is broadcast;

setting a flag indicating that visibility for the first router has changed;

receiving a message at the first router;

embedding in the message an indication that visibility for the first router has changed; and

broadcasting the message containing the embedded indication.

8. A computer program embodied on a computer readable medium and operable to be executed, the computer program comprising computer readable program code for:

receiving a request to identify any communication paths visible to a first router in a mesh network;

broadcasting the request to identify the communication paths;

identifying one or more second routers that broadcast information received by the first router, the one or more identified second routers associated with the communication paths visible to the first router;

receiving at least one first response from at least one of the second routers, the at least one first response identifying the communication paths visible to at least one of the second routers; and

broadcasting a second response at the first router, the second response identifying the communication paths visible to at least one of the second routers and to the first router.

9. The computer program of claim 8, wherein:

the at least one first response comprises a first link list, the first link list comprising an entry for each of the routers, at least one of the entries in the first link list identifying the communication paths visible to at least one of the second routers; and

the second response comprises a second link list, the second link list comprising an entry for each of the routers, a plurality of the entries in the second link list identifying the communication paths visible to at least one of the second routers and to the first router.

10. The computer program of claim 8, further comprising computer readable program code for:

synchronizing the first router to a plurality of time slots using the request to identify any communication paths.

11. The computer program of claim 10, wherein the computer readable program code for synchronizing the first router comprises computer readable program code for incrementing a network reference value at each time slot up to a maximum value and then decrementing the network reference value at each time slot down to a minimum value, the incrementing and decrementing repeated a plurality of times.

12. The computer program of claim 11, wherein:

each of the routers is associated with a unique identifier, each unique identifier associated with a specific value of the network reference value; and

the computer readable program code for broadcasting is capable of broadcasting only when the network reference value has the specific value associated with the router'"'"'s unique identifier.

13. The computer program of claim 12, wherein:

the computer readable program code for broadcasting the request to identify the communication paths comprises computer readable program code for broadcasting the request during the time slot in a selected one of a plurality of first sequences, each first sequence associated with time slots when the network reference value is incremented up to the maximum value or with time slots when the network reference value is decremented down to the minimum value; and

the computer readable program code for broadcasting the second response comprises computer readable program code for broadcasting the second response during a selected one of a plurality of second sequences, the selected second sequence corresponding to the selected first sequence.

14. The computer program of claim 8, further comprising computer readable program code for:

identifying at least one additional router that becomes visible to the first router after the second response is broadcast;

setting a flag indicating that visibility for the first router has changed;

receiving a message at the first router;

embedding in the message an indication that visibility for the first router has changed; and

broadcasting the message containing the embedded indication.

15. A mesh network, comprising:

a plurality of routers capable of communicating with a plurality of user endpoints, each router capable of communicating with at least one other router over at least one communication path; and

a central controller capable of broadcasting a request to identify any communication paths visible to at least one of the routers;

each router further capable of;

broadcasting the request to identify the communication paths;

identifying the at least one communication path used by that router;

receiving at least one first response from at least one other router, the at least one first response identifying the communication paths visible to the at least one other router; and

broadcasting a second response, the second response identifying the communication paths visible to the at least one other router and to that router.

16. The mesh network of claim 15, wherein:

the at least one first response comprises a first link list, the first link list comprising an entry for each of the routers, at least one of the entries in the first link list identifying the communication paths visible to at least one other router; and

the second response comprises a second link list, the second link list comprising an entry for each of the routers, a plurality of the entries in the second link list identifying the communication paths visible to at least one other router and to the router broadcasting the second response.

17. The mesh network of claim 16, wherein the central controller is capable of receiving the second link list from one of the routers, the second link list received by the central controller identifying the communication paths visible to all routers in the mesh network

18. The mesh network of claim 15, wherein each router is further capable of:

synchronizing the router to a plurality of time slots using the request to identify any communication paths.

19. The mesh network of claim 18, wherein:

each router is capable of synchronizing to the time slots by incrementing a network reference value at each time slot up to a maximum value and then decrementing the network reference value at each time slot down to a minimum value, the incrementing and decrementing repeated a plurality of times;

each router is associated with a unique identifier, each unique identifier associated with a specific value of the network reference value;

each router is capable of broadcasting the request to identify the communication paths during the time slot in a selected one of a plurality of first sequences, each first sequence associated with time slots when the network reference value is incremented up to the maximum value or with time slots when the network reference value is decremented down to the minimum value; and

each router is capable of broadcasting the second response during a selected one of a plurality of second sequences, the selected second sequence corresponding to the selected first sequence.

20. The mesh network of claim 15, wherein:

each router is further capable of;

identifying at least one additional router that becomes visible after the second response is broadcast;

setting a flag indicating that visibility has changed;

receiving a message destined for the central controller;

embedding in the message an indication that visibility for the first router has changed; and

broadcasting the message containing the embedded indication; and

the central controller is capable of receiving the messages containing the embedded indications and using the embedded indications to determine whether to broadcast a second request to identify any communication paths.