Control information associated with data bursts to be switched on a burst-switched router is transmitted using payload envelopes (100) on one or more control channels (16). A control channel scheduling module (86) defines sets of contiguous payload envelopes, referred to as "frontiers" (110). A frontier contains a predetermined number of payload envelopes that could be transmitted over a maximum time difference from the time of arrival of a control packet to a latest time of departure for the control packet. After selecting a control packet, a current frontier is determined from a current time and a frontier index. Scheduling information for the current and next frontiers is stored in memory (116). The memory is searched for an available gap to accommodate the control packet (144) in one of either the current set or a next frontier based on the scheduling information.