|
GRAND seminar Online Buffer Management Abstract As the Internet becomes more mature, there is a great demand of improving the performance of routers in handling streaming and diversified data. The diversity of applications results in unpredictable packet flows and heterogeneous network traffic. We characterize packets by their deadlines, their order dependency, and their payoffs when being sent. In most applications, however, we do not know the packet characteristics ahead of time. Thus, scheduling different types of packets in an online manner becomes a critical issue for buffer management at network switches. Our goal is to find online algorithms with good competitive ratio for Quality of Service (QoS) buffers in maximizing the total value of packets sent. In this talk, I will discuss designing effective buffer management policies for network switches supporting QoS guarantees. In particular, I will present a new method for competitive analysis, and the latest work on this topic of buffer management. The later part includes an optimal algorithm for a specific model, an algorithm that achieves a competitive ratio of 1.854 for the bounded-delay model, and an algorithm that achieves a competitive ratio of 1.732 for the FIFO model. Biography Fei Li is an assistant professor at Computer Science Department at George Mason University. He got B.S. in Computer Science from Jilin University in 1997, M.S. and MPhil in Computer Science from Columbia University in 2002 and 2007, respectively. He is getting his PhD in Computer Science from Columbia University in 2007. Fei Li's research areas are design and analysis of algorithms, especially, online algorithms, randomized algorithms, and combinatorial optimization for scheduling and networkings.
|
