Scheduling data transfers in preemptive hierarchical switching systems with applications to packet radio networks

A communication switching system is considered where nodes communicate through transmitters and receivers that have the same bandwidth. Communication constraints are imposed so that the number of active transmitters or receivers on designated subsets of nodes is bounded by prespecified values. The constraints are assumed to have a hierarchical structure. An algorithm is given that produces minimal length schedules of data transfers through the system if transmission preemption is allowed. A variation of the switching system when nodes communicate through transceivers is also considered, and accompanying scheduling algorithms are presented. Applications to transmission scheduling in packet radio networks are discussed