A video-on-demand (VoD) is a system in which each client requests to receive a hot video and the video server immediately responds its request. In VoD system, bandwidth requirement is one of the most important measures, e.g., the maximum bandwidth and the total bandwidth, and it is known that online stream merging can reduce the bandwidth requirement. Recently, Chan et al. proposed the modified greedy algorithm MGRD{sub}λ with catch-up parameterλ≥1 and showed that for any integerλ≥1, it is (2+ε)-competitive w.r.t. the maximum bandwidth and is 2.5-competitive w.r.t. the total bandwidth. In this paper, we precisely analyze the competitive ratio of the modified greedy algorithm MGRD{sub}λ, and show that w.r.t. the maximum bandwidth, (1) the competitive ratio of the algorithm MGRD{sub}λ is at most 2 for any integerλ≥1; (2) the competitive ratio of the algorithm MGRD{sub}λ is at least 2 for any integerλ≥1; and that w.r.t. the total bandwidth, (3) the competitive ratio of the algorithm MGRD{sub}λ is at most 2 for any integerλ≥2; (4) the competitive ratio of the algorithm MGRD{sub}λ is at least (5λ+4)/(3λ+3)≥1.5 for any integer λ≥1.
展开▼
