Back to search

Carleton University

Experimental Evaluation of Reordering Buffer Management Algorithms

Abstract

dc:description.abstract

In the Reordering Buffer Management (RBM) problem, we are given an input sequence of size N and a buffer B of size k (k < N). Each item in the input sequence is characterized by its "colour''. The defining characteristic of this problem is that a cost is incurred when we switch from one colour to another in the resulting output sequence. Our goal is to permute the input sequence using the buffer B such that the cost of switching between colours is minimized. In the online version, the input sequence is not known in advance. We propose a new algorithm in this thesis, Accelerated Threshold (Acc-T) for the online version of the RBM problem with non-uniform costs. This thesis also presents experimental results for several existing uniform and non-uniform cost algorithms and compares them against different combinations of input sequence types, cost functions, buffer sizes and number of colours.

Degree

thesis:*
Name thesis:degree_name
Master of Computer Science (M.C.S.)
Level thesis:degree_level
Master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Carleton University
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Vasanth, Medha

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Copyright © 2015 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Carleton University
Base URL
carleton.scholaris.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Vasanth, Medha. Experimental Evaluation of Reordering Buffer Management Algorithms. Master's thesis, Carleton University, 2015. https://hdl.handle.net/20.500.14718/39267