Providing smooth playback capabilities for video servers, which must support potentially thousands of on-demand users, has been an area of active research. From a user's perspective. VCR func- tions of fast-forward and rewind (FF/Rew), are desirable features in video-on-demand. But FF/Rew at n times the regular playback rate requires n times the regular playback bandwidth from architec- tural components of the video server. Thus, guaranteeing sufficient bandwidth to enable users to perform FF/Rew reduces the number of supportable users by a factor of n. In this paper we propose an alternative, effective FF/Rew service, which provides FF/Rew capabilities with an associated statistical quality-of-service (QoS) guarantee. This service provides immediate access to full-resolution FF/Rew bandwidth with high probability. When bandwidth is not available, service is either delayed or provided immediately but with a loss in resolution. In addition, we specify several QoS metrics to characterize the delay or loss experienced by a FF/Rew request. We show that using effective FF/Rew with statistical guar- antees on these QoS metrics results in a significant increase in the number of supportable users, when compared to systems in which FF/Rew bandwidth is statically reserved for each user. Moreover, a playback-only video server can be extended to provide FF/Rew service by reserving only a small portion of its total bandwidth. which is dynamically shared among FF/Rew requests.