System and method for collecting routing information in a mesh network

• US 7,606,169 B2
• Filed: 03/21/2005
• Issued: 10/20/2009
• Est. Priority Date: 03/21/2005
• Status: Expired due to Fees

• Current Assignee: RF Monolithics, Inc. (Murata Manufacturing Co Limited)
• Original Assignee: RF Monolithics, Inc. (Murata Manufacturing Co Limited)
• Inventors: Nelson, Dan R.
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Rutkowski; Jeffrey M
• Application Number:
  US11/085,427
• Publication Number:
  US 20060209720A1
• Time in Patent Office: 1,674 Days
• Field of Search: 370/351, 370/338, 370/216, 370/254, 370/255, 370/310, 370/312, 370/349, 370/389, 370/390, 370/392, 370/393, 370/432, 370/248, 709/238, 709/244, 709/242
• 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 associated with 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 one or more first communication paths directly visible to the first router;

receiving at least one first response from at least one of the one or more second routers, the at least one first response containing at least one first entry, each first entry identifying one of the first communication paths visible to one of the one or more second routers, at least one first entry also identifying one or more second communication paths visible to at least one of the one or more second routers, each second communication path involving one second router and one of one or more third routers, the one or more third routers not directly visible to the first router; and

broadcasting a second response at the first router, the second response combining the at least one first entry and a second entry, the second entry identifying the one or more first communication paths directly visible 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 including the at least one first entry generated by at least one of the one or more second routers and a blank second entry associated with the first router; and

the second response comprises a second link list, the second link list comprising an entry for each of the routers including the at least one first entry generated by at least one of the one or more second routers and the second entry generated by 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 configured to broadcast 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 readable medium comprising a computer program, the computer program comprising computer readable program code for:

receiving a request to identify any communication paths associated with 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 one or more first communication paths directly visible to the first router;

receiving at least one first response from at least one of the one or more second routers, the at least one first response containing at least one first entry, each first entry identifying one of the first communication paths visible to one of the one or more second routers, at least one first entry also identifying one or more second communication paths visible to at least one of the one or more second routers, each second communication path involving one second router and one of one or more third routers, the one or more third routers not directly visible to the first router; and

broadcasting a second response at the first router, the second response combining the at least one first entry and a second entry, the second entry identifying the one or more first communication paths directly visible to the first router.

9. The computer readable medium 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 including the at least one first entry generated by at least one of the one or more second routers and a blank second entry associated with the first router; and

the second response comprises a second link list, the second link list comprising an entry for each of the routers including the at least one first entry generated by at least one of the one or more second routers and the second entry generated by the first router.

10. The computer readable medium 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 readable medium 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 readable medium 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 configured to broadcast only when the network reference value has the specific value associated with the router'"'"'s unique identifier.

13. The computer program readable medium 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 readable medium 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 configured to communicate with a plurality of user endpoints, each router configured to communicate with at least one other router over at least one communication path; and

a central controller configured to broadcast a request to identify the communication paths in the mesh network;

wherein a first router is further configured to;

receive the request to identify the communication paths;

broadcast the request to identify the communication paths;

identify one or more second routers that broadcast information received by the first router;

identify one or more first communication paths directly visible to the first router, the one or more identified second routers associated with the one or more first communication paths;

receive at least one first response from at least one of the one or more second routers, the at least one first response containing at least one first entry, each first entry identifying one of the first communication paths visible to one of the one or more second routers, at least one first entry also identifying one or more second communication paths visible to at least one of the one or more second routers, each second communication path involving one second router and one of one or more third routers, the one or more third routers not directly visible to the first router; and

broadcast a second response, the second response combining the at least one first entry and a second entry, the second entry identifying the one or more first communication paths directly visible to the first 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 including the at least one first entry generated by at least one of the one or more second routers and a blank second entry associated with the first router; and

the second response comprises a second link list, the second link list comprising an entry for each of the routers including the at least one first entry generated by at least one of the one or more second routers and the second entry generated by the first router.

17. The mesh network of claim 16, wherein the central controller is configured to receive the second link list from the first router, 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 configured to:

synchronize 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 configured to synchronize 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 configured to broadcast 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 configured to broadcast 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 configured to;

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

set a flag indicating that visibility has changed;

receive a message destined for the central controller;

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

broadcast the message containing the embedded indication; and

the central controller is configured to receive the messages containing the embedded indications and to use the embedded indications to determine whether to broadcast a second request to identify any communication paths.