Some of the material in is restricted to members of the community. By logging in, you may be able to gain additional access to certain collections or items. If you have questions about access or logging in, please use the form on the Contact Page.
IP Networks have become an integral part of our daily lives. As we become more dependent on this technology, we realize the importance and use of networks that can be configured to cater to various classes of services and users. Given the potential scalability in providing Quality of Services (QoS), core-stateless packet scheduling algorithms have attracted lot of attention in recent years. Unlike traditional stateful packet schedulers that require routers to maintain per-flow state and perform per-flow operations, core-stateless packet schedulers service packets based on some state carried in packet headers (such as reservation rate of a flow), and as a consequence, no per-flow state needs to be maintained at core routers, and no per-flow operations performed, which significantly reduce the complexity and improve the scalability of the packet scheduling algorithms. On the other hand, although core-stateless packet schedulers remove the requirement of per-flow state and operations, they aim to emulate the scheduling operations of the corresponding stateful packet schedulers. An important implication of this emulation is that they need to sort packets according to the control state carried in the packet headers and service packets in that order. This sorting operation can be quite expensive when the packet queue is long, which may not be acceptable in high-speed backbone networks. In this thesis, we present a bin-based core-stateless packet scheduling algorithm, BCQ, to overcome this problem. Like other core-stateless packet scheduling algorithms, BCQ does not require core routers to maintain per-flow state and perform per-flow operations. It schedules packets based on the notion of virtual time stamps. Virtual time stamps are computed using only some control state that can be carried in packet headers (and a few constant parameters of the scheduler). However, unlike current core-state packet scheduling algorithm, a BCQ scheduler maintain a number of packet bins, each representing a range of virtual times. Arriving packets at a BCQ scheduler are classified into the packet bins maintained by the BCQ, based on the virtual time stamps of the packets. Bins are serviced according to the range of virtual times they represent, packets in bins with earlier virtual times are serviced first. Packets within each bin are serviced in FIFO order. We formally present the BCQ scheduler in this thesis and conduct simulations to study its performance. Our simulation results show that BCQ is a scalable and flexible packet scheduling algorithm. By controlling the size of bins (therefore the cost of BCQ), BCQ can achieve different desirable performances. For example, when the bin size is sufficient large, all arriving packets will be falling in one bin, and no packet sorting is conducted (BCQ becomes a FIFO scheduler). On the other hand, as we gradually decrease the bin size, BCQ can provide different QoS performance (at greater cost). When the bin size is sufficient small, BCQ can provide the same end-to-end delay performance as other core-stateless schedulers.