Evaluating feasible transmission paths in a packet network
View Patent ↗A technique is disclosed that attempts to improve the evaluation of a network path's signal quality, as well as the selection of a network path for transmission purposes, without some of the costs and disadvantages of doing so in the prior art. In accordance with the illustrative embodiment, a node with access to the packet network, such as a VoIP telephone endpoint, evaluates the quality of service that is associated with each of multiple network paths. The evaluation process is iterative, in which the number of candidate paths is successively reduced from one iteration of the technique to the next. The multiple paths that remain as candidates in any given iteration are evaluated concurrently and at an evaluation bit rate that i) is less than the full transmission rate of the real-time traffic (VoIP) packets to be sent and ii) varies as a function of the number of candidate paths remaining under consideration.
1. A method comprising:
establishing an evaluation bit budget that is based on a predetermined transmission rate at which a first packet stream is to be transmitted from a first node to a second node;
iteratively evaluating signal quality that is associated with each network path P n of N i network paths for each iteration i, from the first node to the second node, N i being an integer greater than one and n being an integer between 1 and N i , wherein the evaluation of at least one path P n involves transmitting bits at an evaluation rate that is based on the evaluation bit budget, and wherein the total number of bits transmitted for all evaluations is based on the evaluation bit budget;
after each iteration i of the evaluation, selecting an i th subset of network paths from the N i network paths, wherein the selection is based on the signal quality results from the evaluation of the N i network paths; and
transmitting, at the predetermined transmission rate, the first packet stream from the first node to a third node, wherein the third node is in path P s that is selected after the final iteration.
2. The method of claim 1 wherein the evaluation rate in effect for iteration i is less than or equal to one-half of the predetermined transmission rate.
3. The method of claim 2 wherein the evaluation rate in effect for iteration i is less than or equal to the predetermined transmission rate divided by N i .
4. The method of claim 3 wherein the number of network paths in the i th subset is less than or equal to one-half of the value of N i .
5. The method of claim 1 wherein at least two of the N i network paths are evaluated concurrently for iteration i.
6. The method of claim 5 wherein all of the N i network paths are evaluated concurrently for iteration i.
7. The method of claim 1 wherein the selection of the i th subset of network paths is based on the network paths that have the best quality-of-service results from the evaluation at iteration i.
8. A method comprising:
evaluating signal quality that is associated with each network path P n of N network paths from a first node to a second node, in support of a first packet stream to be transmitted at a predetermined transmission rate from the first node to the second node, N being an integer greater than one and n being an integer between 1 and N, wherein the evaluation of at least one path P n involves transmitting bits at an evaluation rate that is i) less than the predetermined transmission rate and ii) inversely proportional to N, and wherein at least one of the paths fails to provide a quality-of-service guarantee;
selecting M network paths from the N network paths, M being a positive integer that has a value less than N, wherein the selection is based on the signal quality results from the evaluation of the N network paths; and
transmitting, at the predetermined transmission rate, the first packet stream from the first node to a third node, wherein the third node is in selected path P s that is one of the M network paths.
9. The method of claim 8 wherein the evaluation rate is less than or equal to one-half of the predetermined transmission rate.
10. The method of claim 9 wherein the evaluation rate is less than or equal to the predetermined transmission rate divided by N.
11. The method of claim 10 wherein the value of M is less than or equal to one-half of the value of N.
12. The method of claim 8 wherein at least two of the N network paths are evaluated concurrently.
13. The method of claim 12 wherein all of the N network paths are evaluated concurrently.
14. The method of claim 8 wherein the selection is based on the M network paths having the best quality-of-service results from the evaluation.
15. The method of claim 8 further comprising:
evaluating quality-of-service that is associated with each network path P m of the M network paths; and
selecting Q network paths from the M network paths, Q being a positive integer that has a value less than or equal to the value of M, wherein the selection is based on the Q network paths having the best quality-of-service results from the evaluation of the M network paths.
16. A method comprising:
evaluating quality-of-service that is associated with each network path P n of N network paths from a first node to a second node, in support of a first packet stream to be transmitted at a predetermined transmission rate from the first node to the second node, N being an integer greater than one and n being an integer between 1 and N, each path P n comprising relay node R n that defines path P n , wherein the evaluation of at least one path P n involves transmitting bits at an evaluation rate that is less than or equal to the predetermined transmission rate divided by N, and wherein at least one path P n fails to provide a quality-of-service guarantee;
selecting M network paths from the N network paths, M being a positive integer that has a value less than or equal to one-half of the value of N, wherein the selection is based on the quality-of-service results from the evaluation of the N network paths; and
transmitting, at the predetermined transmission rate, the first packet stream from the first node to relay node R s in selected path P s that is one of the M network paths.
17. The method of claim 16 wherein the evaluation rate is equal to the predetermined transmission rate divided by N.
18. The method of claim 17 wherein the value of M is equal to one-half of the value of N.
19. The method of claim 16 wherein at least two of the N network paths are evaluated concurrently.
20. The method of claim 19 wherein all of the N network paths are evaluated concurrently.
21. The method of claim 16 wherein the selection is based on the M network paths having the best quality-of-service results from the evaluation.
22. The method of claim 16 further comprising:
evaluating the quality of service associated with each network path P m of the M network paths; and
selecting Q network paths from the M network paths, Q being a positive integer that has a value less than or equal to the value of M, wherein the selection is based on the Q network paths having the best quality-of-service results from the evaluation of the M network paths.
23. A method comprising:
performing a first evaluation of quality-of-service that is associated with each network path P n of network paths P 1 through P 4 from a first node to a second node, in support of a first packet stream to be transmitted at a predetermined transmission rate from the first node to the second node, each path P n of paths P 1 through P 4 comprising relay node R n that defines path P n , wherein the evaluation of at least one path P n involves transmitting bits at a first evaluation rate that is equal to one-quarter of the predetermined transmission rate, and wherein at least one path P n fails to provide a quality-of-service guarantee;
selecting two network paths P 1 and P 2 from paths P 1 through P 4 , wherein the selection is based on paths P 1 and P 2 having the best quality-of-service results from the first evaluation;
performing a second evaluation of the quality of service associated with paths P 1 and P 2 at a second evaluation rate that is equal to one-half of the predetermined transmission rate;
selecting one network path P 1 from paths P 1 and P 2 , wherein the selection is based on path P 1 having the best quality-of-service results from the second evaluation; and
transmitting, at the predetermined transmission rate, the first packet stream from the first node to relay node R 1 in path P 1 .
24. The method of claim 23 wherein at least two of network paths P 1 through P 4 are evaluated concurrently in the first evaluation.
25. The method of claim 24 wherein all of network paths P 1 through P 4 are evaluated concurrently in the first evaluation.
26. The method of claim 23 further comprising:
performing a third evaluation of the quality of service associated with each network path P n of N network paths from the first node to the second node, N being an integer greater than four; and
selecting the four network paths P 1 through P 4 from the N network paths, wherein the selection is based on paths P 1 through P 4 having the best quality-of-service results from the third evaluation.
27. The method of claim 26 wherein all of the N network paths are evaluated concurrently in the third evaluation.