Show simple item record

dc.contributor.author
Erlebach, Thomas
dc.contributor.author
Jacob, Riko
dc.contributor.author
Mihalák, Matúš
dc.contributor.author
Nunkesser, Marc
dc.contributor.author
Szabó, Gábor
dc.contributor.author
Widmayer, Peter
dc.date.accessioned
2022-08-10T11:38:36Z
dc.date.available
2017-06-11T16:43:13Z
dc.date.available
2017-10-27T11:35:08Z
dc.date.available
2019-03-05T12:26:09Z
dc.date.available
2022-08-10T11:38:36Z
dc.date.issued
2003-08
dc.identifier.uri
http://hdl.handle.net/20.500.11850/99445
dc.identifier.doi
10.3929/ethz-a-004604617
dc.description.abstract
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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich, Computer Engineering and Networks Laboratory
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
An Algorithmic View on OVSF Code Assignment
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.journal.title
TIK Report
ethz.journal.volume
173
en_US
ethz.size
36 p.
en_US
ethz.code.ddc
DDC - DDC::6 - Technology, medicine and applied sciences::621.3 - Electric engineering
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340 - Widmayer, Peter / Widmayer, Peter
en_US
ethz.relation.isPreviousVersionOf
20.500.11850/51741
ethz.date.deposited
2017-06-11T16:43:49Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp5936530ae975d82032
ethz.identifier.importid
imp59366a71f07da37116
ethz.ecolpid
eth:26695
ethz.ecitpid
pub:155588
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-26T15:48:01Z
ethz.rosetta.lastUpdated
2023-02-07T05:12:36Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=An%20Algorithmic%20View%20on%20OVSF%20Code%20Assignment&rft.jtitle=TIK%20Report&rft.date=2003-08&rft.volume=173&rft.au=Erlebach,%20Thomas&Jacob,%20Riko&Mihal%C3%A1k,%20Mat%C3%BA%C5%A1&Nunkesser,%20Marc&Szab%C3%B3,%20G%C3%A1bor&rft.genre=report&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record