Data transmission across a network using constant-bit-rate (CBR) service simplifies admission control and resource management techniques. We consider lossless, starvation- free, streaming CBR transmission of compressed digital video, which is known to exhibit significant, multi-time- scale rate variability. This transmission uses work-ahead transfer into available client buffers to send data at a rate significantly below the peak rate of the original video. The goal of any video transmission scheme is to minimize resources requirements such as client buffer, transmission rate, channel holding time and playback startup latency. We identify, for CBR video transmissions, formal structural properties of the tradeoffs among these resources. Specifically, we show that, (i) the minimum feasible client buffer requirement as a function of playback startup latency is unimodal with one minimal value, (ii) the minimum feasible CBR rate is a convex decreasing function of the startup latency, and (iii) the corresponding channel holding time is piecewise linear concave increasing function of the startup latency. Using these structural properties, we then develop an O(N log N) algorithm that computes the minimum client buffer size and the associated CBR rate and playback startup latency required to transmit a VBR video. This is a significant improvement over an existing O(N2 log N) algorithm to solve the same problem. We next quantitatively examine the resource tradeoffs using MPEG-1 traces, and find that both the CBR transmission rate and minimum client buffering requirement can be substantially reduced by requiring only very small playback startup latencies.