Change search
ReferencesLink to record
Permanent link

Direct link
Data structures for bandwidth reservations and quality of service on the Internet
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
2004 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis deals firstly with ways to solve the problem of limited resource reservations over time, and secondly, handling conforming traffic in routers. At first glance these topics seem a bit unrelated, they are both related to quality of service (QoS) on the Internet and are cases of Algorithm Engineering applied in the field of Computer Networking. In order to provide Quality of Service (QoS) for the users of mainly real time applications on the Internet, the need to make a reservation of bandwidth over the Internet has arisen. The idea of QoS is to provide the same quality of the service on the Internet as it is provided in the ordinary circuit switched telephone network. This means that an opened connection will never be disturbed by another connections no matter how many users there are using the phone network at the same time. Internet on the other hand is a packet switched network. That is a network in which small packets with address tags are transported from the source to the destination by several connected subnetworks. On the Internet there are no guarantees regarding unchangeable quality of service; packets may be dropped, delayed or reordered depending on the current load. This is undesirable for users of real time applications. One solution to achieve QoS on the Internet can be to reserve sufficient amount of bandwidth for a time period of resource use --- for instance, the time of a phone call. Olov Schelén used the differentiated services approach to design a new architecture to provide QoS called "bandwidth brokers". In this architecture they provide virtual leased lines using the differentiated services to perform admission control through a system of bandwidth brokers. The bandwidth brokers work on per-hop basis and each bandwidth broker needs to maintain a database of the reservations made on its hop. It must be quick to: insert more reservations in the database remove reservations already made to query the amount of reserved bandwidth during a given interval in order to see if another reservation can be made so that not more bandwidth are reserved than the link capacity can carry. We talk about a "Bandwidth Reservation Problem" ("BRP"). Our solution to the problem is more general than just to be used with the bandwidth brokers. In the thesis I present two different solutions to the BRP; one static data structure using constant space and O(log n) worst case time for all operations, and a dynamic solution using Theta(n) space and Theta(log n) time for all operations, where n is the number of leaves in the tree. Note that the running time of the operations are not depending on the number of reservations, connections, or amount of reserved bandwidth. I also present an application of the dynamic solution in the field of chemistry where it is used to analysis of large spectral data sets. I also present a paper where a new set of forwarding behaviors is presented. That is a set of packet scheduling principles that can be used on the Internet to better achieve QoS.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2004. , 6 p.
Licentiate thesis / Luleå University of Technology, ISSN 1402-1757 ; 2004:21
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-18000Local ID: 655b3510-aec8-11db-803d-000ea68e967bOAI: diva2:991006
Godkänd; 2004; 20070128 (ysko)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Nilsson, Andreas
By organisation
Embedded Internet Systems Lab

Search outside of DiVA

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

Total: 29 hits
ReferencesLink to record
Permanent link

Direct link