For single-source, single-tree based peer-to-peer live media streaming, it is generally believed that a short (and wide) tree has a good comprehensive performance in terms of tree reliability and service delay. While the short tree directly benefits delay optimization, it is unclear whether such a structure maximizes tree reliability, which is sometimes more critical for a streaming Internet service.

This paper studies several prevalent overlay construction algorithms in terms of (1) service reliability; (2) service delay and (3) protocol overhead. Two types of peer layout, bandwidth-ordered layout and time-ordered layout, are identified and their performance is evaluated. The analytical results show that, by appropriately placing peers according to their time properties, the tree can be much more reliable than a depth-optimized tree.

We therefore propose a heap algorithm, which aims for combining the strengths of both bandwidth ordering and time ordering. It dynamically moves peers between difference layers of the tree according to a simple metric, and gradually adjusts the tree toward a layout partially ordered in time and partially ordered in bandwidth. In so doing the tree has advantages in both service reliability and delay, and maintains small protocol overheads. Extensive simulations demonstrate the effectiveness of this new algorithm.