In this paper, we analyze the throughput of interconnection networks, viewed as multi-stage queueing networks with infinite input queues, but finite internal cross-stage ones. We find that for very general arrival processes and arbitrarily fixed network topology, the stability region with finite internal buffers is identical to that for the corresponding network with infinite internal buffers, and is achievable via special scheduling policies. In particular, we define and study a class of throughput maximizing policies, known as projective cone scheduling (PCS) algorithms, which activate a set of concurrent service rates to all queues in the network based on observed backlog levels.

Recent research in packet switch scheduling algorithms has moved beyond throughput maximization to quality of service (QoS) control. Several classes of algorithms have been shown to achieve maximal throughput under certain system conditions. Between classes and within each class, QoS performance varies based on arrival traffic and properties of the scheduling algorithm being utilized. Here we compare two classes of throughput-maximizing algorithms and their performance with respect to buffer sizes. These classes are randomized algorithms, which can be characterized as offline algorithms, and projective cone scheduling algorithms, which are online since they respond to the current workload in the system. In each class, parameters can be fine-tuned to reflect the priorities of individual switch ports. We show how the online algorithms lead to significantly better quality of service performance.

Recently, extensive analytic research into packet scheduling in crossbar switches has yielded interesting throughput maximizing algorithms. Surprisingly, however, quality of service (QoS) performance associated with these algorithms has only been approximated through simulation. We present here certain randomized algorithms with analytic QoS. These are simple to implement and possess closed form expressions for various performance measures. By fine tuning particular parameters of these algorithms, one can vary the QoS associated with the individual ports as desired. This allows cost and utility optimization, a feature which was not feasible under previously studied packet scheduling algorithms.

We consider the (generalized) packet switch scheduling problem, where the switch service configuration has to be dynamically chosen based on observed queue backlogs, so as to maximize the throughput. A class of recently developed 'projective' scheduling algorithms, which substantially generalize the well-known maximum weight matching (MWM) algorithms for crossbar switches, are explored from the perspective of complexity. The typically huge number of possible switch configurations that the scheduler has to consider in each timeslot has been previously observed to lead to an impractical computational requirement. We introduce a new class of projective schedules based on 'local search' concepts. In particular, rather than searching the entire (typically huge) set of available service configurations to find the best one, the new scalable scheduling algorithms search 'locally' over a small neighborhood of service configurations to find a 'better' one in each time slot. We show that local projective scheduling algorithms can provide dramatic reduction in complexity without causing any loss of throughput (although they may observe higher delay). We explore the nature and structure of such schedules, which show a much higher promise for practical implementation than their global versions.

A time-domain wavelength interleaved network (TWIN) (Widjaja, I. et al., IEEE Commun. Mag., vol.41, 2003) is an optical network with an ultrafast tunable laser and a fixed receiver at each node. We consider the problem of scheduling bursts of data in a TWIN. Due to the high data rates employed on the optical links, the burst transmissions typically last for very short times compared with the round trip propagation times between source-destination pairs. A good schedule should ensure that: 1) there are no transmit/receive conflicts; 2) propagation delays are observed; 3) throughput is maximized (schedule length is minimized). We formulate the scheduling problem with periodic demand as a generalization of the well-known crossbar switch scheduling. We prove that even in the presence of propagation delays, there exist a class of computationally viable scheduling algorithms which asymptotically achieve the maximum throughput obtainable without propagation delays. We also show that any schedule can be rearranged to achieve a factor-two approximation of the maximum throughput even without asymptotic limits. However, the delay/throughput performance of these schedules is limited in practice. We consequently propose a scheduling algorithm that exhibits near optimal (on average within ∼7% of optimum) delay/throughput performance in realistic network examples.