QoS routing via multiple paths using bandwidth reservation

摘要

The authors address the problem of computing a multipath, consisting of possibly overlapping paths, to transmit data from the source node s to the destination node d over a computer network while ensuring deterministic bounds on end-to-end delay or delivery rate. They consider two generic routing problems within the framework wherein bandwidth can be reserved, and guaranteed, once reserved, on various links of the communication network. The first problem requires that a message of finite length be transmitted from s to d within (tau) units of time. The second problem requires that a sequential message of r units be transmitted at a rate of (eta) such that maximum time difference between two units that are received out of order is no more than q. They propose a polynomial-time algorithm to the first problem based on an adaptation of the classical Ford-Fulkerson's method. They present simulation results to illustrate the applicability of the proposed algorithm. They show the second problem to be NP-complete and propose a polynomial-time approximate solution.