Baked-Potato Routing

This paper presents scheduling of packet transmission schemes, called baked-potato schemes, which are used to avoid simultaneous arrival of packets at a switch. We present scheduling schemes for any capacity of links and switches. The schemes are evaluated by the maximal length of time between two successive schedulings of a processor. For the case of a single-capacity link and switch, our scheme is proved optimal by presenting a matching lower bound. Our baked-potato scheme does not assume any prior knowledge on the source-destination demands and can be used for sending control packets and broadcasting.