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. / A Thesis submitted to the Department of Computer Science in partial fulfillment of
the requirements for the degree of Master of Science. / Degree Awarded: Fall Semester, 2005. / Date of Defense: September 23, 2005. / Quality of Service, Core Stateless, BCQ / Includes bibliographical references. / Zhenhai Duan, Professor Directing Thesis; Xin Yuan, Committee Member; Kartik Gopalan, Committee Member.
| Identifer | oai:union.ndltd.org:fsu.edu/oai:fsu.digital.flvc.org:fsu_168620 |
| Contributors | Purnachandra, Karthik P. (authoraut), Duan, Zhenhai (professor directing thesis), Yuan, Xin (committee member), Gopalan, Kartik (committee member), Department of Computer Science (degree granting department), Florida State University (degree granting institution) |
| Publisher | Florida State University |
| Source Sets | Florida State University |
| Language | English, English |
| Detected Language | English |
| Type | Text, text |
| Format | 1 online resource, computer, application/pdf |
Page generated in 0.0011 seconds