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.

Additional Metadata
Journal Journal of Algorithms
Citation
Dolev, S. (Shlomi), Kranakis, E, & Krizanc, D. (Danny). (1999). Baked-Potato Routing. Journal of Algorithms, 30(2), 379–399.