Abstract: Packet switching in connection-oriented networks that may have multiple parallel links between pairs of switches is considered. An efficient packet-scheduling algorithm that guarantees a deterministic quality of service to connections with real-time constraints is proposed -- this algorithm is a generalization of some recent multiprocessor scheduling algorithms, and offers real-time performance guarantees similar to those offered by earlier fair-scheduling strategies such as Weighted Fair Queueing and proportional-share schemes.