An Optimal Randomized Online Algorithm for QoS Buffer Management

• DOI: 10.1145/3154494
• Publication Date: 2018-03-23T18:28:08Z
• Authors: Lin Yang; Wing Shing Wong; Mohammad H. Hajie...
• Keywords: Competitive Analysis; Online algorithm; Buffer (optical fiber); Admission control

The QoS (Quality of Service) buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic admission control problem the presence constraints. In its basic setting, packets different values according to their requirements, arrive fashion switching node limited size. Then, switch needs make an immediate decision either admit or reject incoming packet based on value availability. objective maximize cumulative profit admitted packets, while respecting constraint. Even though was proposed more than decade ago, no optimal solution has been literature. This paper contributes this by proposing: 1) A fixed threshold-based algorithm smaller competitive ratio existing results; 2) deterministic under fractional model which could be partially; 3) randomized for general problem. We consider last result being main contribution paper.