Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
Tech report, DS/0308041
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-24020Local ID: 959905f0-976f-11dc-ad7f-000ea68e967bOAI: oai:DiVA.org:ltu-24020DiVA: diva2:997070
Note
Godkänd; 2003; 20071120 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2017-11-24Bibliographically approved

Open Access in DiVA

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

Other links

http://arxiv.org/abs/cs.DS/0308041

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 76 downloads
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

urn-nbn

Altmetric score

urn-nbn
Total: 161 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf