System, method and program for network routing

• US 8,085,799 B2
• Filed: 06/19/2007
• Issued: 12/27/2011
• Est. Priority Date: 06/19/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Curtis, Richard Scott, Forrester, Jason Davis
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Kaur, Pamit
• Application Number:
  US11/765,099
• Publication Number:
  US 20080317056A1
• Time in Patent Office: 1,652 Days
• Field of Search: 370/409, 370/351, 370/395.21
• US Class Current: 370/409
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04W 40/16 based on interference

Abstract

Computer system, method and program for making routing decisions. A best routing path according to an OSPF, IGRP, EIGRP, BGP or other routing function that can provide multiple routing paths is determined. A first multiplicity of routers in the best routing path is determined. If each of the first multiplicity of routers had a degree of availability and/or quality of signal during a predetermined prior interval that met predetermined respective thresholds, the message packet is forwarded to a next hop in the best routing path. If not, a second multiplicity of routers in a second best routing path determined according to said OSPF, IGRP, EIGRP, BGP or the other routing function is identified. If each of the second multiplicity of routers had a degree of availability and/or quality of signal during a predetermined prior interval that met respective thresholds, the message packet is forwarded to a next hop in the second best routing path.

Claims

1. A method for routing a message packet which has been received, the method comprising the steps of:

a computer determining a best routing path according to an Open Shorted Path First (OSPF), Interior Gateway Routing Protocol (IGRP), Enhanced Interior Gateway Routing Protocol (EIGRP), Border Gateway Protocol (BGP) or other routing function;

the computer identifying a first multiplicity of routers in the best routing path, and determining if all routers of the first multiplicity of routers had, at increments in time during a predetermined prior time interval, respective signal strengths that exceeded a predetermined threshold;

if so, the computer forwarding the message packet to a next hop in the best routing path, and

if not, the computer identifying a second multiplicity of routers in a second best routing path determined according to the OSPF, IGRP, EIGRP, BGP or the other routing function, and the computer determining if all routers of the second multiplicity of routers had, during a predetermined prior interval, signal strengths that exceeded the predetermined threshold, and if so, forwarding the message packet to a next hop in the second best routing path.

17. The method of claim 1, wherein said determining comprises determining that said all routers had, during the predetermined prior interval, signal strengths that exceeded the predetermined threshold.

2. A method for routing a message packet which has been received, said method comprising:

a first router, after having received the message packet, determining a next best routing path comprising a next set of routers comprising a first set of routers for routing the message packet from the first router to a destination address;

said first router ascertaining whether the next set of routers satisfies at least one criterion comprising a first criterion, said first criterion is that each router of the next set of routers had a percent availability at or above a specified percent availability threshold over a specified time interval;

if said ascertaining ascertains that the next set of routers satisfies the at least one criterion, said first router forwarding the message packet to a next hop in the next best routing path;

if said ascertaining ascertains that the next set of routers does not satisfy the at least one criterion;

said first router determining another best routing path comprising another set of routers for routing the message packet to the destination address;

said first router setting said next best routing path and said next set of routers to said another best routing path and said another set of routers, respectively; and

after said setting, said first router iteratively looping back to said ascertaining whether the next set of routers satisfies at least one criterion, until said forwarding the message packet is performed.

3. The method of claim 2, wherein the at least one criterion comprises a second criterion, said second criterion is that each router of the next set of routers has received a signal having a magnitude of signal strength at or above a specified signal strength threshold at increments in time during the specified time interval.

4. The method of claim 2, wherein the at least one criterion comprises a second criterion, said second criterion is that each router of the next set of routers has received a signal having a magnitude of noise level at or below a specified noise level threshold at increments in time during the specified time interval.

5. The method of claim 2, wherein for the next set of routers comprising the first set of routers, said ascertaining ascertains that the next set of routers satisfy the at least one criterion.

6. The method of claim 2, said method further comprising:

said first router broadcasting a HELLO advertisement to each neighbor router of a plurality of neighbor routers of the first router;

said first router receiving a response to the broadcasted HELLO advertisement from one or more neighbor routers of the plurality of neighbor routers;

said first router not receiving any response to the broadcasted HELLO advertisement from at least one neighbor router of the plurality of neighbor routers;

said first router sending, to each neighbor router responding to the broadcasted HELLO advertisement, a historical availability record of the first router and a historical quality of connection record of the first router;

said first router not sending, to each neighbor router not responding to the broadcasted HELLO advertisement, the historical availability record of the first router and the historical quality of connection record of the first router;

wherein the historical availability record of the first router includes a percent availability of the first router during a specified time period; and

wherein the historical quality of connection record of the first router includes a signal strength of signals received by the first router during the specified time period and a level of noise at the first router during the specified time period.

7. A computer program product for routing a message packet which has been received, said computer program product comprising:

a computer readable tangible storage device;

first software for execution in a first router, after having received the message packet, for determining a next best routing path comprising a next set of routers comprising a first set of routers of for routing the message packet from the first router to a destination address;

second software for execution in said first router ascertaining whether the next set of routers satisfies at least one criterion comprising a first criterion, said first criterion is that each router of the next set of routers had a percent availability at or above a specified percent availability threshold over a specified time interval

third software for execution in said first router, and responsive to said second software ascertaining that the next set of routers satisfies the at least one criterion, said first router forwarding the message packet to a next hop in the next best routing path;

fourth software for execution in said first router, and responsive to said second software ascertaining that the next set of routers does not satisfy the at least one criterion;

said first router determining another best routing path comprising another set of routers for routing the message packet to the destination address;

said first router setting said next best routing path and said next set of routers to said another best routing path and said another set of routers, respectively; and

after said setting, said first router iteratively looping back to said ascertaining whether the next set of routers satisfies at least one criterion, until said forwarding the message packet is performed,

wherein the first software, the second software, the third software, and the fourth software are stored on the computer readable tangible storage device.

8. The computer program product of claim 7, wherein the at least one criterion comprises a second criterion, said second criterion is that each router of the next set of routers has received a signal having a magnitude of signal strength at or above a specified signal strength threshold at increments in time during the specified time interval.

9. The computer program product of claim 7, wherein the at least one criterion comprises a second criterion, said second criterion is that each router of the next set of routers has received a signal a signal having a magnitude of noise level at or below a specified noise level threshold at increments in time during the specified time interval.

10. The computer program product of claim 7, wherein for the next set of routers comprising the first set of routers, said ascertaining ascertains that the next set of routers satisfy the at least one criterion.

11. The computer program product of claim 7, said computer program product further comprising fifth software for:

said first router broadcasting a HELLO advertisement to each neighbor router of a plurality of neighbor routers of the first router;

said first router receiving a response to the broadcasted HELLO advertisement from one or more neighbor routers of the plurality of neighbor routers;

said first router not receiving any response to the broadcasted HELLO advertisement from at least one neighbor router of the plurality of neighbor routers;

said first router sending, to each neighbor router responding to the broadcasted HELLO advertisement, a historical availability record of the first router and a historical quality of connection record of the first router;

said first router not sending, to each neighbor router not responding to the broadcasted HELLO advertisement, the historical availability record of the first router and the historical quality of connection record of the first router;

wherein the historical availability record of the first router includes a percent availability of the first router during a specified time period; and

wherein the historical quality of connection record of the first router includes a signal strength of signals received by the first router during the specified time period and a level of noise at the first router during the specified time period,

wherein the fifth software is stored on the computer readable storage medium for execution in the first router.

12. A system for routing a message packet which has been received, said system comprising:

a first router including a CPU, a computer-readable memory and a computer readable tangible storage device;

first software for execution in said first router, after having received the message packet, determining a next best routing path comprising a next set of routers comprising a first set of routers of for routing the message packet from the first router to a destination address;

second software for execution in said first router ascertaining whether the next set of routers satisfies at least one criterion comprising a first criterion, said first criterion is that each router of the next set of routers had a percent availability at or above a specified percent availability threshold over a specified time interval;

third software for execution in said first router, and responsive to said second software ascertaining ascertains that the next set of routers satisfies the at least one criterion, said first router forwarding the message packet to a next hop in the next best routing path;

fourth software for execution in said first router, and responsive to said second software ascertaining ascertains that the next set of routers does not satisfy the at least one criterion;

said first router determining another best routing path comprising another set of routers for routing the message packet to the destination address;

said first router setting said next best routing path and said next set of routers to said another best routing path and said another set of routers, respectively; and

after said setting, said first router iteratively looping back to said ascertaining whether the next set of routers satisfies at least one criterion, until said forwarding the message packet is performed,

wherein the first software, the second software, the third software, and the fourth software are stored on the computer readable tangible storage device for execution by the CPU via the computer-readable memory in the first router.

13. The system of claim 12, wherein the at least one criterion comprises a second criterion, said second criterion is that each router of the next set of routers has received a signal having a magnitude of signal strength at or above a specified signal strength threshold at increments in time during the specified time interval.

14. The system of claim 12, wherein the at least one criterion comprises a second criterion, said second criterion is that each router of the next set of routers has received a signal having a magnitude of noise level at or below a specified noise level threshold at increments in time during the specified time interval.

15. The system of claim 12, wherein for the next set of routers comprising the first set of routers, said ascertaining ascertains that the next set of routers satisfy the at least one criterion.

16. The system of claim 12, said system further comprising fifth software for:

said first router broadcasting a HELLO advertisement to each neighbor router of a plurality of neighbor routers of the first router;

said first router receiving a response to the broadcasted HELLO advertisement from one or more neighbor routers of the plurality of neighbor routers;

said first router not receiving any response to the broadcasted HELLO advertisement from at least one neighbor router of the plurality of neighbor routers;

said first router sending, to each neighbor router responding to the broadcasted HELLO advertisement, a historical availability record of the first router and a historical quality of connection record of the first router;

said first router not sending, to each neighbor router not responding to the broadcasted HELLO advertisement, the historical availability record of the first router and the historical quality of connection record of the first router;

wherein the historical availability record of the first router includes a percent availability of the first router during a specified time period;

wherein the historical quality of connection record of the first router includes a signal strength of signals received by the first router during the specified time period and a level of noise at the first router during the specified time period,

wherein the fifth software is stored on the computer readable storage medium for execution in the first router.