A connection-oriented virtual work-conserving packet scheduling architecture for broadband ISDN

Broadband Integrated Service Digital Networks (Broadband-ISDNs) that are being deployed offer many distinct advantages over conventional circuit switching or time division multiplexed networks. The advantages include uniform network access, economics of scale, and improved bandwidth utilization due to statistical multiplexing gain. On the other hand, the introduction of broadband-ISDN also presents many new technical challenges in the design of network control and management functions, especially in terms of providing quality of service (QoS) guarantees to individual network connections. Since many consider it is beyond current technology to provide QoS guarantees to hundreds of thousands of network connections, many packet scheduling designs discussed in the literature have mainly focused on providing QoS guarantees on the basis of traffic classes. Unfortunately, there are still many unanswered questions under this paradigm such as: (1) How many traffic classes are adequate; (2) What exact criteria should be used to decide which traffic class a connection should belong to.;From the network users' point of view, they have no concerns as to how networks categorize their connections as long as they are satisfied that networks can deliver the QoS guarantees sufficient for their individual connections. Therefore, we feel it is the ultimate goal of the broadband-ISDN design to provide QoS guarantees for their network users on a connection basis.;In this dissertation, we study the fundamental packet scheduling structure underlying the recently proposed QoS-driven connection-oriented packet scheduling disciplines including Virtual Clock, Fair Queueing, Earliest Due Date, and General Processor Sharing. We conclude that although the connection-oriented work-conserving packet scheduling disciplines may exhibit different packet scheduling characteristics, they share a common packet scheduling framework based on a sorted priority queue structure. However, the infeasibility of the sorted priority queue design has prevented the proposed packet scheduling disciplines from being implemented in the broadband-ISDNs. To overcome the design complexity in the sorted priority queue structure and, at the same time, provide a flexible and expandable hardware platform for packet scheduling disciplines, we propose a new and, yet, feasible packet scheduling architecture as a part of the alternate broadband-ISDN switching system hardware architectures. The proposed packet scheduling architecture can handle hundreds of thousands of packets and network connections at the same time and, still, exhibit almost identical packet scheduling characteristics as a work-conserving packet scheduler. We, therefore, name the proposed packet scheduling architecture the Virtual Work-Conserving (VWC) packet scheduling architecture.;To obtain an intuitive understanding of the fundamental packet scheduling characteristics, we perform two packet waiting time analyses with a Poisson packet arrival process on the VWC packet scheduling architecture. From analyses and simulations studies, we establish an operating range for the VWC packet scheduling architecture and transform the VWC packet scheduling architecture into a unique hardware design, which explores concurrent pipeline structures of the packet scheduling architecture and exploits the high device density characteristics of CMOS memory technologies. (Abstract shortened by UMI.).