System and method for managing a list of entries containing routing information
| Title: | System and method for managing a list of entries containing routing information |
|---|---|
| Patent Number: | 8,798,048 |
| Publication Date: | August 05, 2014 |
| Appl. No: | 13/334188 |
| Application Filed: | December 22, 2011 |
| Abstract: | A system and method adds and manages entries on a list of entries of routing information to allow the top entry to be used for routing to a destination corresponding to the list. Costs of a wireless link may be a function of the success rate experienced on that wireless link. |
| Inventors: | Hui, Jonathan W. (Foster City, CA, US); Woo, Alec (Union City, CA, US); Culler, David E. (Berkeley, CA, US) |
| Assignees: | Cisco Technology, Inc. (San Jose, CA, US) |
| Claim: | 1. A method comprising: receiving, at a first network node, a beacon message from a second network node, wherein the beacon message includes an advertised cost of routing messages to a destination through the second network node; measuring, based on receiving the beacon message, a signal quality associated with the beacon message; determining, based on information included in the beacon message, whether the second network node is a next hop node of the first network node for routing messages to the destination; based on determining that the second network node is a next hop node of the first network node for routing messages to the destination, selecting a candidate next hop list of entries corresponding to the destination; determining whether the signal quality exceeds a threshold; determining whether the second network node is present in the candidate next hop list; based on determining that the signal quality exceeds the threshold and determining that the second network node is not present in the candidate next hop list, determining at least one of whether the candidate next hop list is empty and whether a timer is active; and based on determining that at least one of the candidate next hop list is empty and the timer is active, adding to an entry in the candidate next hop list information from the beacon message, including at least one of an identifier of the second network node, a hop count from the second network node to the destination and a list of identifiers of nodes in a routing path from the second network node to the destination. |
| Claim: | 2. The method of claim 1 , wherein the second network node is a neighboring node of the first network node. |
| Claim: | 3. The method of claim 1 , wherein determining whether the second network node is a next hop node of the first network node for routing messages to the destination comprises: determining at least one of whether the list of identifiers of nodes in the routing path includes the first network node and whether the hop count included in the beacon message is at most greater by a predetermined percentage compared to a hop count from the first network node to the destination. |
| Claim: | 4. The method of claim 1 , wherein determining whether the second network node is a next hop node of the first network node for routing messages to the destination comprises determining whether the first network node is tracking next hop nodes for routing messages to the destination. |
| Claim: | 5. The method of claim 1 , further comprising: based on determining that the signal quality exceeds the threshold and the second network node is present in the candidate next hop list, determining whether cost information associated with an entry for the second network node in the candidate next hop list has changed, wherein the cost information is determined as changed if at least one of a difference in the advertised cost included in the beacon message and a total cost stored in the corresponding entry is greater than a first predetermined threshold, and a difference between the measured signal quality and a signal quality stored in the corresponding entry is greater than a second predetermined threshold. |
| Claim: | 6. The method of claim 5 , further comprising: based on determining that the cost information has changed, computing whether a change in the cost information is within a predetermined change threshold; and based on computing that the change in the cost information is within the predetermined change threshold, updating an entry corresponding to the second network node in the candidate next hop list with the advertised cost included in the beacon message. |
| Claim: | 7. The method of claim 6 , further comprising: comparing a total cost of the updated entry with total costs of adjacent entries in the candidate next hop list; and based on the comparing, swapping the updated entry with the adjacent entries such that the updated entry and the adjacent entries are arranged in the candidate next hop list in an order of increasing total cost. |
| Claim: | 8. The method of claim 1 , wherein adding to an entry in the candidate next hop list comprises: storing a measure of the signal quality in the entry; and sorting entries in the candidate next hop list such that the entries are arranged in a sorted order of advertised cost. |
| Claim: | 9. The method of claim 1 , further comprising: determining whether the candidate next hop list is full; based on determining that the candidate next hop list is full, establishing whether the advertised cost included in the beacon message is lower by at least a predetermined level compared to a cost included in a bottom entry at an end of the candidate next hop list; and based on establishing that the advertised cost is lower by at least the predetermined level compared to the cost included in the bottom entry, replacing information in the bottom entry with information included in the beacon message, including an identifier of the second network node, the advertised cost and a measure of the signal quality. |
| Claim: | 10. The method of claim 9 , further comprising: based on establishing that the advertised cost is within the predetermined level compared to the cost included in the bottom entry, determining whether a measure of signal quality is included in the bottom entry; based on determining that a measure of signal quality is included in the bottom entry, deciding whether the signal quality associated with the beacon message is better by at least a predetermined level compared to the signal quality included in the bottom entry; and based on deciding that the signal quality associated with the beacon message is better by at least the predetermined level, replacing information in the bottom entry with information included in the beacon message, including the identifier of the second network node, the hop count, the advertised cost and the measure of the signal quality. |
| Claim: | 11. A method comprising: sending, by a network node, a message to a first next hop node for routing to a destination, wherein the first next hop node is selected from a candidate next hop list associated with the destination; based on establishing that sending the message to the first next hop node for routing to the destination is an unsuccessful attempt, incrementing a first attempt counter associated with the first next hop node; based on determining that a value of the first attempt counter exceeds a predetermined threshold value, including an indication of the unsuccessful attempt in a first entry associated with the first next hop node in the candidate next hop list; selecting a second entry from the candidate next hop list; initializing a second attempt counter associated with the second entry; sending the message for routing to the destination to a second next hop node corresponding to the second entry; based on receiving an acknowledgement from the second next hop node indicating successful reception of the message, determining, using a value of the second attempt counter, a number of attempts for successfully sending the message to the second next hop node; computing a cost of routing messages to the destination using the second next hop node based on the determined number of attempts; and storing, in the second entry, the computed cost of routing messages to the destination using the second next hop node. |
| Claim: | 12. The method of claim 11 , further comprising: comparing the cost included with the second entry with costs associated with adjacent entries in the candidate next hop list; based on the comparing, determining that the cost included in the second entry is less than the cost corresponding to the entry above the second entry by at least a predetermined threshold level; and based on the determining, moving the second entry up one position in the candidate next hop list, and moving the entry previously above the second entry down one position below the second entry. |
| Claim: | 13. The method of claim 12 , wherein comparing the cost included with the second entry with costs associated with adjacent entries in the candidate next hop list comprises: based on the comparing, determining that the cost included in the second entry is greater than the cost corresponding to the entry below the second entry by at least a predetermined threshold level; and based on the determining, moving the second entry down one position in the candidate next hop list, and moving the entry previously below the second entry up one position above the second entry. |
| Claim: | 14. A method comprising: selecting, by a network node, a candidate next hop list associated with a destination stored at the network node; examining an entry in the candidate next hop list corresponding to a default next hop node for routing messages to the destination; based on information included in the entry corresponding to the default next hop node, determining a total cost of routing messages to the destination using the default next hop node, a hop count for the routing and a list of identifiers of a predetermined number of nodes in a path of routing messages using the default next hop node; computing an adjusted hop count by incrementing the hop count by one; forming an adjusted list of nodes for routing messages to the destination by adding an identifier of the default next hop node to the list of identifiers of the predetermined number of nodes; forming a beacon message by including in the beacon message the total cost, the adjusted hop count, the adjusted list of nodes and an identifier of the next node; and broadcasting the beacon message. |
| Claim: | 15. The method of claim 14 , further comprising: forming a beacon message for each destination by including in the beacon message the total cost, the adjusted hop count, the adjusted list of nodes, an identifier of the next node and the destination; and broadcasting the beacon message for each destination. |
| Claim: | 16. The method of claim 14 , wherein determining a total cost of routing messages to the destination using the default next hop node comprises: determining a factor associated with a physical characteristic of the network node, wherein the physical characteristic is based on a capacity of a power source associated with the network node; and computing the total cost by multiplying a link cost included in the entry corresponding to the default next hop node and adding a result of the multiplying to the link cost. |
| Claim: | 17. A computer program product embodied in a computer-readable non-transitory medium including instructions executable by a processor and configured to cause the processor to perform operations comprising: receiving, at a first network node, a beacon message from a second network node, wherein the beacon message includes an advertised cost of routing messages to a destination through the second network node; measuring, based on receiving the beacon message, a signal quality associated with the beacon message; determining, based on information included in the beacon message, whether the second network node is a next hop node of the first network node for routing messages to the destination; based on determining that the second network node is a next hop node of the first network node for routing messages to the destination, selecting a candidate next hop list of entries corresponding to the destination; determining whether the signal quality exceeds a threshold and whether the second network node is present in the candidate next hop list; based on determining that the signal quality exceeds a threshold and the second network node is not present in the candidate next hop list, determining at least one of whether the candidate next hop list is empty and whether a timer is active; and based on determining that at least one of the candidate next hop list is empty and the timer is active, adding to an entry in the candidate next hop list information from the beacon message, including at least one of an identifier of the second network node, a hop count from the second network node to the destination and a list of identifiers of nodes in a routing path from the second network node to the destination. |
| Claim: | 18. The computer program product of claim 17 , wherein the instructions cause the processor to perform operations comprising: based on determining that the signal quality exceeds a threshold and the second network node is present in the candidate next hop list, determining whether cost information associated with an entry for the second network node in the candidate next hop list has changed, wherein the cost information is determined as changed if at least one of a difference in the advertised cost included in the beacon message and a total cost stored in the corresponding entry is greater than a first predetermined threshold, and a difference in the measured signal quality and a signal quality stored in the corresponding entry, is greater than a second predetermined threshold. |
| Claim: | 19. The computer program product of claim 18 , wherein the instructions cause the processor to perform operations comprising: based on determining that the cost information has changed, computing whether a change in the cost information is within a predetermined threshold; and based on computing that the change in the cost information is within the predetermined threshold, updating an entry corresponding to the second network node in the candidate next hop list with the advertised cost included in the beacon message. |
| Claim: | 20. The computer program product of claim 17 , wherein the instructions cause the processor to perform operations comprising: determining whether the candidate next hop list is full; based on determining that the candidate next hop list is full, establishing whether the advertised cost included in the beacon message is lower by at least a predetermined level compared to a cost included in a bottom entry at an end of the candidate next hop list; and based on establishing that the advertised cost is lower by at least the predetermined level compared to the cost included in the bottom entry, replacing information in the bottom entry with information included in the beacon message, including an identifier of the second network node, the advertised cost and a measure of the signal quality. |
| Claim: | 21. The computer program product of claim 20 , wherein the instructions cause the processor to perform operations comprising: based on establishing that the advertised cost is within the predetermined level compared to the cost included in the bottom entry, determining whether a measure of signal quality is included in the bottom entry; based on determining that a measure of signal quality is included in the bottom entry, deciding whether the signal quality associated with the beacon message is better by at least a predetermined level compared to the signal quality included in the bottom entry; and based on deciding that the signal quality associated with the beacon message is better by at least the predetermined level, replacing information in the bottom entry with information included in the beacon message, including the identifier of the second network node, the hop count, the advertised cost and the measure of the signal quality. |
| Current U.S. Class: | 370/389 |
| Patent References Cited: | 6260072 July 2001 Rodriguez-Moral 6370119 April 2002 Basso et al. 6584500 June 2003 Arkko 6606303 August 2003 Hassel et al. 6904275 June 2005 Stanforth 7002917 February 2006 Saleh 7058016 June 2006 Harper 7423995 September 2008 Elliott et al. 7961740 June 2011 Flammer et al. 8085768 December 2011 Hui et al. 8184632 May 2012 Hui et al. 8571030 October 2013 Hui et al. 2002/0090949 July 2002 Stanforth 2002/0191573 December 2002 Whitehill et al. 2003/0128690 July 2003 Elliott et al. 2004/0073678 April 2004 Border et al. 2004/0116141 June 2004 Loven et al. 2004/0219922 November 2004 Gage et al. 2005/0249122 November 2005 Wheeler et al. 2006/0215588 September 2006 Yoon 2006/0221927 October 2006 Yamada et al. 2007/0121503 May 2007 Guo et al. 2008/0095075 April 2008 Monier 2009/0190481 July 2009 Kobayashi et al. 2012/0224487 September 2012 Hui et al. |
| Other References: | Notice of Allowance issued Feb. 24, 2012 in U.S. Appl. No. 12/290,848, 8 pages. cited by applicant Non-final Office Action issued Nov. 21, 2012 in U.S. Appl. No. 12/290,822, 21 pages. cited by applicant Non-final Office Action issued Feb. 29, 2012 in U.S. Appl. No. 12/290,850, 12 pages. cited by applicant Final Office Action issued Aug. 14, 2012 in U.S. Appl. No. 12/290,850, 12 pages. cited by applicant Non-final Office Action issued Feb. 16, 2011 in U.S. Appl. No. 12/290,848, 12 pages. cited by applicant Non-final Office Action issued Jul. 15, 2010 in U.S. Appl. No. 12/290,848, 14 pages. cited by applicant Non-final Office Action issued Feb. 18, 2011 in U.S. Appl. No. 12/290,843, 18 pages. cited by applicant Non-final Office Action issued Jul. 12, 2010 in U.S. Appl. No. 12/290,843, 18 pages. cited by applicant Final Office Action issued Feb. 16, 2011 in U.S. Appl. No. 12/290,822, 15 pages. cited by applicant Non-final Office Action issued May 26, 2010 in U.S. Appl. No. 12/290,822, 12 pages. cited by applicant Non-final Office Action issued Sep. 26, 2013 in U.S. Appl. No. 131476,716, 17 pages. cited by applicant Notice of Allowance issued Jul. 8, 2013 in U.S. Appl. No. 12/290,822, 10 pages. cited by applicant Non-final Office Action issued May 23, 2011 in U.S. Appl. No. 12/290,850, 15 pages. cited by applicant Final Office Action issued Sep. 15, 2011 in U.S. Appl. No. 12/290,850, 11 pages. cited by applicant Notice of Allowance issued Aug. 21, 2013 in U.S. Appl. No. 12/290,850, 8 pages. cited by applicant |
| Assistant Examiner: | Preval, Lionel |
| Primary Examiner: | Ton, Dang |
| Attorney, Agent or Firm: | Fish & Richardson P.C. |
| Accession Number: | edspgr.08798048 |
| Database: | USPTO Patent Grants |
| Language: | English |
|---|