In an MPEG encoder, three types of frames (I, P. and B) are periodically generated according to a pre-specified compression pattern. As a result, an MPEG sequence is periodic in its compression pattern, and this periodicity can be used to reduce the bandwidth requirements of multiplexed MPEG streams. By exploiting the deterministic and periodic nature of the compression pattern, we show that it is possible to provide stringent deterministic guarantees (no cell losses and no queueing delay) to MPEG connections without the need to allocate the peak rates of individual sources. Instead, a stream is allocated its effective bandwidth, which is the aggregate peak rate of the multiplexed streams divided by the number of streams. The aggregate peak rate depends on the arrangement of the multiplexed streams which is a measure of the degree of synchronization among the compression patterns of different streams. It is found that in most cases, the effective bandwidth is smaller than the source peak rate. For a given arrangement, we provide a procedure to compute the effective bandwidth. We also give an expression for the 'best' arrangement that results in the 'optimal' effective bandwidth. Examples of real MPEG sequences are used to show the bandwidth gains that can be achieved through proper scheduling of the starting times of MPEG connections. (Also cross-referenced as UMIACS-TR-95-120)