By analyzing the effect of cross traffic (CT) enforced on packet delay, an improved path capacity measurement method, pcapminp algorithm, was proposed. With this method, path capacity was measured by filtering probe s...By analyzing the effect of cross traffic (CT) enforced on packet delay, an improved path capacity measurement method, pcapminp algorithm, was proposed. With this method, path capacity was measured by filtering probe samples based on measured minimum packet-pair delay. The measurability of minimum packet-pair delay was also analyzed by simulation. The results show that, when comparing with pathrate, if the CT load is light, both pcapminp and pathrate have similar accuracy; but in the case of heavy CT load, pcapminp is more accurate than Pathrate. When CT load reaches 90%, pcapminp algorithm has only 5% measurement error, which is 10% lower than that of pathrate algorithm. At any CT load levels, the probe cost of pcapminp algorithm is two magnitudes smaller than that of pathrate, and the measurement duration is one magnitude shorter than that of pathrate algorithm.展开更多
The computational complexity of inverse mimimum capacity path problem with lower bound on capacity of maximum capacity path is examined, and it is proved that solution of this problem is NP-complete. A strong polynomi...The computational complexity of inverse mimimum capacity path problem with lower bound on capacity of maximum capacity path is examined, and it is proved that solution of this problem is NP-complete. A strong polynomial algorithm for a local optimal solution is provided.展开更多
Abstract:This paper addresses the problem of improving the optimal value of the Maximum Capacity Path(MCP)through expansion in a flexible network,and minimizing the involved costs.The only condition applied to the cos...Abstract:This paper addresses the problem of improving the optimal value of the Maximum Capacity Path(MCP)through expansion in a flexible network,and minimizing the involved costs.The only condition applied to the cost functions is to be non-decreasing monotone.This is a non-restrictive condition,reflecting the reality in practice,and is considered for the first time in the literature.Moreover,the total cost of expansion is a combination of max-type cost(e.g.,for supervision)and sum-type cost(e.g.for building infrastructures,price of materials,price of labor,etc.).For this purpose,two types of strategies are combined:(l)increasing the capacity of the existing arcs,and(l)adding potential new arcs.Two different problems are introduced and solved.Both the problems have immediate applications in Internet routing infrastructure.The first one is to extend the network,so that the capacity of an McP in the modified network becomes equal to a prescribed value,therefore the cost of modifications is minimized.A strongly polynomial-time algorithm is deduced to solve this problem.The second problem is a network expansion under a budget constraint,so that the capacity of an McP is maximized.A weakly polynomial-time algorithm is presented to deal with it.In the special case when all the costs are linear,a Meggido's parametric search technique is used to develop an algorithm for solving the problem in strongly polynomial time.This new approach has a time complexity of O(n^(4)),which is better than the time complexity of O(n4 log(n)of the previously known method from literature.展开更多
基金Projects(60473031, 60673155) supported by the National Natural Science Foundation of ChinaProject(2005AA121560) supported by the High-Tech Research and Development Program of China
文摘By analyzing the effect of cross traffic (CT) enforced on packet delay, an improved path capacity measurement method, pcapminp algorithm, was proposed. With this method, path capacity was measured by filtering probe samples based on measured minimum packet-pair delay. The measurability of minimum packet-pair delay was also analyzed by simulation. The results show that, when comparing with pathrate, if the CT load is light, both pcapminp and pathrate have similar accuracy; but in the case of heavy CT load, pcapminp is more accurate than Pathrate. When CT load reaches 90%, pcapminp algorithm has only 5% measurement error, which is 10% lower than that of pathrate algorithm. At any CT load levels, the probe cost of pcapminp algorithm is two magnitudes smaller than that of pathrate, and the measurement duration is one magnitude shorter than that of pathrate algorithm.
基金The authors gratefully acknowledge the partial support of national natural Founda-tion (Grant 70071011)
文摘The computational complexity of inverse mimimum capacity path problem with lower bound on capacity of maximum capacity path is examined, and it is proved that solution of this problem is NP-complete. A strong polynomial algorithm for a local optimal solution is provided.
文摘Abstract:This paper addresses the problem of improving the optimal value of the Maximum Capacity Path(MCP)through expansion in a flexible network,and minimizing the involved costs.The only condition applied to the cost functions is to be non-decreasing monotone.This is a non-restrictive condition,reflecting the reality in practice,and is considered for the first time in the literature.Moreover,the total cost of expansion is a combination of max-type cost(e.g.,for supervision)and sum-type cost(e.g.for building infrastructures,price of materials,price of labor,etc.).For this purpose,two types of strategies are combined:(l)increasing the capacity of the existing arcs,and(l)adding potential new arcs.Two different problems are introduced and solved.Both the problems have immediate applications in Internet routing infrastructure.The first one is to extend the network,so that the capacity of an McP in the modified network becomes equal to a prescribed value,therefore the cost of modifications is minimized.A strongly polynomial-time algorithm is deduced to solve this problem.The second problem is a network expansion under a budget constraint,so that the capacity of an McP is maximized.A weakly polynomial-time algorithm is presented to deal with it.In the special case when all the costs are linear,a Meggido's parametric search technique is used to develop an algorithm for solving the problem in strongly polynomial time.This new approach has a time complexity of O(n^(4)),which is better than the time complexity of O(n4 log(n)of the previously known method from literature.
