ABSTRACT: To guarantee quality of service (QoS), the requirements for video transmission, such as delay and cell loss rate (CLR), are very stringent. These constraints are difficult to meet if high net work utilization is desired. In this paper, on-line dynamic bandwidth allocation algorithms, in which the bandwidth is adjusted based on the current frame size, are proposed to improve the bandwidth utilization. When the bandwidth deviation is large enough, the bandwidth renegotiation process is triggered. Compared with CBR service, network utilization can be improved significantly for the same CLR. In general, to achieve a very low CLR and high bandwidth utilization, the renegotiation frequency may become high. Algorithms, which are proven to be effective in reducing the renegotiation frequency while keeping the bandwidth utilization at a reasonable level, are also proposed.