Scheduling protocols for switches with large envelopes

Traditionally, switches make scheduling decisions on the granularity of a packet. However, this is becoming increasingly difficult since network bandwidth is growing rapidly whereas packet sizes remain largely unchanged. Therefore the service time of an individual packet is decreasing rapidly. In this paper we study switches that make scheduling decisions on the granularity of an envelope which can be much larger than a packet in size. For an output-queued switch with envelope size E, each output chooses one input every E time steps and transmits packets from this chosen input during the next E steps. For an input-queued switch with envelope size E, one matching from the inputs to the outputs is computed every E steps and only the input–output pairs that are defined by this matching are allowed to transmit packets during the next E steps. Traditional switches correspond to envelope size E = 1 and almost all previous scheduling work deals with this case exclusively. We first show how some stable protocols for scheduling networks of output-queued switches with E = 1 fail for arbitrary E when these protocols are generalized in the most straightforward manner. We then present an extremely simple protocol that does guarantee network stability for output-queued switches for any E ⩾ 1. For input-queued switches we first present a max-weight matching protocol that is stable for a single switch with arbitrary E. We then present a more complex protocol that achieves stability for a network of input-queued switches for any E ⩾ 1.