Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Static data structure for discrete advance bandwidth reservations on the internet
Luleå tekniska universitet, Institutionen för system- och rymdteknik, EISLAB.
2003 (engelsk)Rapport (Annet vitenskapelig)
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)$.

sted, utgiver, år, opplag, sider
Luleå, 2003.
Serie
Tech report ; DS/0308041
HSV kategori
Forskningsprogram
Kommunikations- och beräkningssystem
Identifikatorer
URN: urn:nbn:se:ltu:diva-24020Lokal ID: 959905f0-976f-11dc-ad7f-000ea68e967bOAI: oai:DiVA.org:ltu-24020DiVA, id: diva2:997070
Merknad
Godkänd; 2003; 20071120 (ysko)Tilgjengelig fra: 2016-09-29 Laget: 2016-09-29 Sist oppdatert: 2018-01-10bibliografisk kontrollert

Open Access i DiVA

fulltekst(276 kB)151 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 276 kBChecksum SHA-512
17db9282c6f5f46c05fb4600744a1553a6ecdfcab8dcbe27e10988a9a28bf26561ae1124152d7e4fcfeb3bffbc5bade5e1a93474dbc89d0cfae6ea908fb91ccf
Type fulltextMimetype application/pdf

Andre lenker

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

Person

Brodnik, AndrejNilsson, Andreas

Søk i DiVA

Av forfatter/redaktør
Brodnik, AndrejNilsson, Andreas
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 151 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 197 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf