Balanced Scheduling toward LossFree Packet Queuin

Authors: Rudolf Fleischer Hisashi Koga

Publish Date: 2003/10/10

Volume: 38, Issue: 2, Pages: 363-376

PDF Link

Abstract

In current networks packet losses can occur if routers do not provide sufficiently large buffers This paper studies how many buffers should be provided in a router to eliminate packet losses We assume a network router has m incoming queues each corresponding to a single traffic stream and must schedule at any time online from which queue to take the next packet to send out To exclude packet losses with a small amount of buffers the maximum queue length must be kept low over the entire scheduling period We call this new online problem the balanced scheduling problem BSP By competitive analysis we measure the power of online scheduling algorithms to prevent packet losses We show that a simple greedy algorithm is Θlog mcompetitive which is asymptotically optimal while RoundRobin scheduling is not better than mcompetitive as actually is any deterministic online algorithm for BSP We also give a polynomial time algorithm for solving offline BSP optimally We also study another online balancing problem that tries to balance the delay among the m traffic streams

Keywords: