Online Buffer Management in QoS Switches

Fei Li, Ph.D. Candidate
Computer Science Department
Columbia University

Abstract

Data over the Internet has the properties of streaming and diversity. They result in unpredictable packet flows and heterogeneous network traffic. Thus, scheduling different types of packets in an online manner becomes a critical issue for buffer management at network switches. In this talk, I will discuss designing effective buffer management policies for network switches supporting Quality of Service (QoS) guarantees. In the general model we consider, each packet is associated with a "deadline" by which it must be sent, as well as a "value" reflecting the payoff for sending it by its deadline. The goal of buffer management is to maximize the total value of the packets transmitted in an online setting.

In this talk, I will discuss several online packet scheduling algorithms for this model and its variants. In particular, I will present our work, which includes an optimal algorithm for a specific model and a recent algorithm that achieves a competitive ratio of 1.854 for the general case. Our analysis is different from the traditional online algorithm analysis methods. Moreover, the ideas in our algorithms can be generalized to various online scenarios for better algorithm design and analysis, such as online auction for search engines, online bipartite matching, and reliable lead-time quotation.

Speaker Bio

Fei Li is currently a PhD candidate in Computer Science Department at Columbia University. He is expected to receive his PhD in the summer of 2007, under the supervision of Prof. Cliff Stein and Prof. Jay Sethuraman, both in IEOR Department at Columbia University. Fei got his BS in Computer Science in 1997 from Jilin University, China and his MS in Computer Science in 2002 from Columbia University. His primary research interests are in combinatorial optimization and applied algorithms. He has done a lot of research in operating systems, networking optimization, and online buffer management. His webpage is at: http://www.cs.columbia.edu/~lifei.