Ant-based method for discovering a network path that satisfies a quality of service equipment

• US 7,466,655 B1
• Filed: 09/16/2003
• Issued: 12/16/2008
• Est. Priority Date: 09/16/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Zhao, Fuyong
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): SINKANTARAKORN, PAWARIS
• Application Number:
  US10/665,190
• Time in Patent Office: 1,918 Days
• Field of Search: 370229-238, 370252-253, 370/389, 370/392, 709/223, 709/224, 709/238, 709/241, 709/242
• US Class Current: 370/238
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

An ant-based method for discovering a network path that satisfies a quality of service (QoS) requirement is disclosed. A “forward QoS ant,” which indicates a destination and a QoS requirement, is received at a particular router. The forward QoS ant is updated to indicate the particular router'"'"'s identity. Given a metric “X,” such as delay, jitter, etc., it is determined whether a least-“X” path from the particular router to the destination satisfies the QoS requirement, and whether the forward QoS ant has visited any other routers in the least-“X” path. If the least-“X” path satisfies the QoS requirement and the forward QoS ant has not visited any other router in the least-“X” path, then the forward QoS ant is sent to the next router in the least-“X” path. Later, a “backward QoS ant,” which indicates the path taken by the forward QoS ant, is received at the particular router.

Claims

1. A computer-implemented method of discovering a network path that satisfies a quality of service (QoS) requirement, the method comprising:

receiving, at a first router, a first data packet that indicates a destination and said QoS requirement;

updating said first data packet to indicate an identity of said first router;

determining whether a least-delay path from said first router to said destination satisfies said QoS requirement;

determining whether said first data packet has visited any router in said least-delay path other than said first router;

wherein a first set of routers that are on said least-delay path is in a pheromone table on the first router, and wherein a second set of routers that have been visited by said first data packet is indicated in said first data packet;

if said least-delay path satisfies said QoS requirement and said first data packet has not visited any router in said least-delay path other than said first router, then sending said first data packet to a second router in said least-delay path; and

receiving, at said first router, a second data packet that indicates a path taken by said first data packet to said destination.

2. The method of claim 1, wherein said first router has links, and further comprising:

if said least-delay path does not satisfy said QoS requirement, then performing steps comprising;

determining one or more of said first router'"'"'s links that satisfy said QoS requirement; and

sending a copy of said first data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement.

3. The method of claim 1, wherein said first router has links, and further comprising:

if said first data packet has visited a router in said least-delay path other than said first router, then performing steps comprising;

determining one or more of said first router'"'"'s links that satisfy said QoS requirement; and

sending a copy of said first data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement.

4. The method of claim 1, further comprising:

in response to receiving said first data packet, updating a table to indicate that said first router has received a copy of said first data packet.

5. A computer-implemented method of discovering a network path that satisfies a quality of service (QoS) requirement, the method comprising:

receiving, at a first router, a data packet that indicates a destination and said QoS requirement;

determining whether said data packet indicates that a path to said destination has been found;

determining whether a least-delay path from said first router to said destination satisfies said QoS requirement;

wherein a first set of routers that are on said least-delay path is in a pheromone table on the first router, and wherein a second set of routers that have been visited by said first data packet is indicated in said first data packet;

if said data packet indicates that a path to said destination has been found, and if said least-delay path from said first router to said destination does not satisfy said QoS requirement, then eliminating said data packet; and

if said data packet does not indicate that a path to said destination has been found, and if said least-delay path from said first router to said destination satisfies said QoS requirement, then performing steps comprising;

updating said data packet to indicate that a path to said destination has been found; and

sending said data packet through said link that leads to said second router on said least-delay path.

6. A computer-implemented method of discovering a network path that satisfies a quality of service (QoS) requirement, the method comprising:

receiving, at a first router that has links, a data packet that indicates a destination and said QoS requirement;

determining whether said first router previously has received a copy of said data packet;

if said first router previously has received a copy of said data packet, then eliminating said data packet; and

if said first router previously has not received a copy of said data packet, then performing steps comprising;

updating a table to indicate that said first router has received a copy of said data packet;

determining whether said data packet indicates that a path to said destination has been found;

determining whether a least-delay path from said first router to said destination satisfies said QoS requirement;

if said data packet indicates that a path to said destination has been found, then performing steps comprising;

if said least-delay path from said first router to said destination does not satisfy said QoS requirement, then eliminating said data packet; and

if said least-delay path from said first router to said destination satisfies said QoS requirement, then sending said data packet through a link that leads to a second router on said least-delay path; and

if said data packet does not indicate that a path to said destination has been found, then performing steps comprising;

determining one or more of said first router'"'"'s links that satisfy said QoS requirement;

if said least-delay path from said first router to said destination does not satisfy said QoS requirement, then sending a copy of said data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement; and

if said least-delay path from said first router to said destination satisfies said QoS requirement, then performing steps comprising;

determining whether said data packet has visited any router in said least-delay path other than said first router;

if said data packet has visited a router in said least-delay path other than said first router, then sending a copy of said data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement; and

if said data packet has not visited any router in said least-delay path other than said first router, then performing steps comprising;

 

updating said data packet to indicate that a path to said destination has been found; and

 

sending said data packet through said link that leads to said second router on said least-delay path.

7. A computer-readable storage medium carrying one or more sequences of instructions for discovering a network path that satisfies a quality of service (QoS) requirement, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

receiving, at a first router, a first data packet that indicates a destination and said QoS requirement;

updating said first data packet to indicate an identity of said first router;

determining whether a least-delay path from said first router to said destination satisfies said QoS requirement;

determining whether said first data packet has visited any router in said least-delay path other than said first router;

wherein a first set of routers that are on said least-delay path is in a pheromone table on the first router, and wherein a second set of routers that have been visited by said first data packet is indicated in said first data packet;

if said least-delay path satisfies said QoS requirement and said first data packet has not visited any router in said least-delay path other than said first router, then sending said first data packet to a second router in said least-delay path; and

receiving, at said first router, a second data packet that indicates a path taken by said first data packet to said destination.

8. The computer-readable storage medium of claim 7, wherein said first router has links, and wherein said instructions, when executed by the one or more processors, cause the one or more processors to carry out the steps of:

if said least-delay path does not satisfy said QoS requirement, then performing steps comprising;

determining one or more of said first router'"'"'s links that satisfy said QoS requirement; and

sending a copy of said first data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement.

9. The computer-readable storage medium of claim 7, wherein said first router has links, and wherein said instructions, when executed by the one or more processors, cause the one or more processors to carry out the steps of:

if said first data packet has visited a router in said least-delay path other than said first router, then performing steps comprising;

determining one or more of said first router'"'"'s links that satisfy said QoS requirement; and

sending a copy of said first data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement.

10. The computer-readable storage medium of claim 7, wherein said instructions, when executed by the one or more processors, cause the one or more processors to carry out the steps of:

in response to receiving said first data packet, updating a table to indicate that said first router has received a copy of said first data packet.

11. An apparatus for discovering a network path that satisfies a quality of service (QoS) requirement, comprising:

means for receiving, at a first router, a first data packet that indicates a destination and said QoS requirement;

means for updating said first data packet to indicate an identity of said first router;

means for determining whether a least-delay path from said first router to said destination satisfies said QoS requirement;

means for determining whether said first data packet has visited any router in said least-delay path other than said first router;

wherein a first set of routers that are on said least-delay path is in a pheromone table on the first router, and wherein a second set of routers that have been visited by said first data packet is indicated in said first data packet;

means for sending said first data packet to a second router in said least-delay path if said least-delay path satisfies said QoS requirement and said first data packet has not visited any router in said least-delay path other than said first router; and

means for receiving, at said first router, a second data packet that indicates a path taken by said first data packet to said destination.

12. The apparatus of claim 11, wherein said first router has links, and further comprising:

means for determining one or more of said first router'"'"'s links that satisfy said QoS requirement if said least-delay path does not satisfy said QoS requirement; and

means for sending a copy of said first data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement if said least-delay path does not satisfy said QoS requirement.

13. The apparatus of claim 11, wherein said first router has links, and further comprising:

means for determining one or more of said first router'"'"'s links that satisfy said QoS requirement if said first data packet has visited a router in said least-delay path other than said first router; and

means for sending a copy of said first data packet through said one or more of said first router'"'"'s links that satisfy said QoS requirement if said first data packet has visited a router in said least-delay path other than said first router.

14. The apparatus of claim 11, further comprising:

means for updating, in response to receiving said first data packet, a table to indicate that said first router has received a copy of said first data packet.

15. An apparatus for discovering a network path that satisfies a quality of service (QoS) requirement, comprising:

a network interface that is coupled to a data network for receiving one or more packet flows therefrom;

a processor;

one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of;

receiving, at said apparatus, a first data packet that indicates a destination and said QoS requirement;

updating said first data packet to indicate an identity of said apparatus;

determining whether a least-delay path from said apparatus to said destination satisfies said QoS requirement;

determining whether said first data packet has visited any router in said least-delay path other than said first router;

wherein a first set of routers that are on said least-delay path is in a pheromone table on the first router, and wherein a second set of routers that have been visited by said first data packet is indicated in said first data packet;

if said least-delay path satisfies said QoS requirement and said first data packet has not visited any router in said least-delay path other than said apparatus, then sending said first data packet to a router in said least-delay path; and

receiving, at said apparatus, a second data packet that indicates a path taken by said first data packet to said destination.

16. The apparatus of claim 15, wherein said apparatus has links, and wherein said instructions, when executed by the processor, cause the processor to carry out the steps of:

if said least-delay path does not satisfy said QoS requirement, then performing steps comprising;

determining one or more of said apparatus'"'"' links that satisfy said QoS requirement; and

sending a copy of said first data packet through said one or more of said apparatus'"'"' links that satisfy said QoS requirement.

17. The apparatus of claim 15, wherein said apparatus has links, and wherein said instructions, when executed by the processor, cause the processor to carry out the steps of:

if said first data packet has visited a router in said least-delay path other than said apparatus, then performing steps comprising;

determining one or more of said apparatus'"'"' links that satisfy said QoS requirement; and

sending a copy of said first data packet through said one or more of said apparatus'"'"' links that satisfy said QoS requirement.

18. The apparatus of claim 15, wherein said instructions, when executed by the processor, cause the processor to carry out the steps of:

in response to receiving said first data packet, updating a table to indicate that said apparatus has received a copy of said first data packet.