Drop counters are enough

Small Flow Completion Time (FCT) of short-lived flows, and fair bandwidth allocation of long-lived flows have been two major, usually concurrent, goals in the design of resource allocation algorithms. In this paper we present a framework that naturally unifies these two objectives under a single umb...

Full description

Saved in:
Bibliographic Details
Main Authors: Stanojevic, R., Shorten, R.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Analytical models
Channel allocation
Counting circuits
History
Proposals
Random access memory
Resource management
Scheduling algorithm
TCPIP
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Small Flow Completion Time (FCT) of short-lived flows, and fair bandwidth allocation of long-lived flows have been two major, usually concurrent, goals in the design of resource allocation algorithms. In this paper we present a framework that naturally unifies these two objectives under a single umbrella; namely by proposing resource allocation algorithm Markov Active Yield (MAY). Based on a probabilistic strategy: " drop proportional to the amount of past drops ", MAY achieves very small FCT among short-lived flows as well as max-min fair bandwidth allocation among long-lived flows, using only the information of short history of already dropped packets. It turns out that extremely small amount of on-chip SRAM (roughly 1 bit per flow in Pareto-like flow size distributions) is enough for storing this drop history. Analytical models are presented and analyzed and accuracy of results is verified experimentally using packet level ns2 simulations.
ISSN:1548-615X
DOI:10.1109/IWQOS.2007.376557