Multipath routing for video delivery over bandwidth-limited networks

The delivery of quality video service often requires high bandwidth with low delay or cost in network transmission. Current routing protocols such as those used in the Internet are mainly based on the single-path approach (e.g., the shortest-path routing). This approach cannot meet the end-to-end bandwidth requirement when the video is streamed over bandwidth-limited networks. In order to overcome this limitation, we propose multipath routing, where the video takes multiple paths to reach its destination(s), thereby increasing the aggregate throughput. We consider both unicast (point-to-point) and multicast scenarios. For unicast, we present an efficient multipath heuristic (of complexity O(|V|/sup 3/)), which achieves high bandwidth with low delay. Given a set of path lengths, we then present and prove a simple data scheduling algorithm as implemented at the server, which achieves the theoretical minimum end-to-end delay. For a network with unit-capacity links, the algorithm, when combined with disjoint-path routing, offers an exact and efficient solution to meet a bandwidth requirement with minimum delay. For multicast, we study the construction of multiple trees for layered video to satisfy the user bandwidth requirements. We propose two efficient heuristics on how such trees can be constructed so as to minimize the cost of their aggregation subject to a delay constraint.