Data structures for bandwidth reservations and quality of service on the Internet

Sammanfattning: 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 et.al. 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.