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

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.

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.

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.

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.

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.