This paper presents a scalable caching algorithm of proxy server with the finite storage size minimizing client’s buffer size and constant-bit-rate channel bandwidth. Under the general video traffic condition, it is observed that the amount of decreased client’s buffer size and channel bandwidth after caching a video frame depends on the relative frame position in the time axis as well as the frame size. Based on this fact, we propose an effective caching algorithm to select the cached frames by using the normalized buffer size. Finally, experimental results are provided to show the superior performance of the proposed algorithm.