Change search
ReferencesLink to record
Permanent link

Direct link
Static data structure for discrete advance bandwidth reservations on the internet
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
2003 (English)Report (Other academic)
Abstract [en]

In this paper we present a discrete data structure for reservations of limited resources. A reservation is defined as a tuple consisting of the time interval of when the resource should be reserved, $I_R$, and the amount of the resource that is reserved, $B_R$, formally $R=\{I_R,B_R\}$. The data structure is similar to a segment tree. The maximum spanning interval of the data structure is fixed and defined in advance. The granularity and thereby the size of the intervals of the leaves is also defined in advance. The data structure is built only once. Neither nodes nor leaves are ever inserted, deleted or moved. Hence, the running time of the operations does not depend on the number of reservations previously made. The running time does not depend on the size of the interval of the reservation either. Let $n$ be the number of leaves in the data structure. In the worst case, the number of touched (i.e. traversed) nodes is in any operation $O(\log n)$, hence the running time of any operation is also $O(\log n)$.

Place, publisher, year, edition, pages
Luleå, 2003.
, Tech report, DS/0308041
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-24020Local ID: 959905f0-976f-11dc-ad7f-000ea68e967bOAI: diva2:997070
Godkänd; 2003; 20071120 (ysko)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

fulltext(276 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 276 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Search in DiVA

By author/editor
Brodnik, AndrejNilsson, Andreas
By organisation
Embedded Internet Systems Lab

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 2 hits
ReferencesLink to record
Permanent link

Direct link