Bandwidth scheduling for multi-channel packet cable telephony

Cable networks have evolved from offering broadcast services to providing high rate two-way data services. In the next step, cable operators intend to use voice over IP (VoIP) to provide cable telephony services. In a cable network the users are connected to the headend through a cable modem. The headend is responsible for allocating upstream bandwidth to the various cable modems. Each cable modem has access to several upstream channels but can use only one upstream channel at any given time. The headend can direct a modem to switch from one upstream channel to another. We consider the problem of scheduling packet telephony calls in a cable network. We show that the scheduling problem is NP-hard even in the case where all the calls have the same characteristics. We then suggest several approximation algorithms for the problem and investigate their performance. We address the problem of maintaining the tolerated jitter when switching a modem from one channel to another and explore the effect of the tolerated jitter on the performance of the scheduling algorithms. We show that the ability to switch channels considerably improves the performance of the scheduling algorithms.