A graph theoretic approach to bounding delay in proxy-assisted, end-system multicast

Abstract

End-system multicast provides a low-cost solution to scalably broadcast information to groups of users. However, last-mile bandwidth limitations constrain tree fanouts; leading to high end-to-end delivery delays. These delays can be reduced if the network provides forwarding proxies with high fanout capabilities at an additional cost. We use simple graph theoretic network models to explore the problem of building hybrid proxy/end-system application layer multicast trees that meet fixed end-to-end delay bounds. Our goal is to meet a fixed delay bound while minimizing costs associated with the utilization of proxies. We provide an algorithm and formally prove its optimality in a fully-connected overlay network with uniform-length edges. We then adapt this algorithm into a heuristic and evaluate the heuristic for simulated transit-stub networks with variable-delay edges. We compare our heuristic in a proxy-free environment to previously developed heuristics and show that our heuristic typically yields further reductions in the maximum session end-to-end delay.