An Algorithmic View on OVSF Code Assignment

Orthogonal Variable Spreading Factor (OVSF) codes can be used to share the radio spectrum among several connections of possibly different bandwidth, which is used for example in UMTS. The combinatorial core of the OVSF code assignment problem is to assign some nodes of a complete binary tree of height h (the code tree) to n simultaneous connections, such that no two assigned nodes (codes) are on the same root-to-leaf path. A connection that uses 2-d of the total bandwidth requires some code at depth d in the tree, but this code assignment is allowed to change over time. Requests for connections that would exceed the total available bandwidth are rejected. We consider the one-step code assignment problem: Given an assignment, reassign a minimum number of codes to serve a new request. Minn and Siu propose the so-called DCA algorithm to solve the problem optimally. We show that DCA does not always return an optimal solution, and that the problem is NP-hard. We give an exact nO(h)-time algorithm, and a polynomial time greedy algorithm that achieves approximation ratio Theta(h). We also consider the online code assignment problem, where future requests are not known in advance. Our objective is to minimize the overall number of code reassignments. We present a Theta(h)-competitive online algorithm and show that no deterministic online algorithm can achieve a competitive ratio better than 1.5. We show that the greedy strategy (minimizing the number of reassignments in every step) is not better than Omega(h)-competitive. We give a 2-resource augmented online algorithm that achieves an amortized constant number of (re-)assignments.
TIK Report, 173