Change search
Link to record
Permanent link

Direct link
BETA
Nilsson, Andreas
Publications (8 of 8) Show all publications
Brodnik, A., Karlsson, J., Munro, I. & Nilsson, A. (2006). An O(1) solution to the prefix sum problem on a specialized memory architecture (ed.). In: (Ed.), Gonzalo Navarro; Leopoldo Bertossi; Yoshiharu Kohayakawa (Ed.), PFourth IFIP International Conference on Theoretical Computer Science - TCS 2006: IFIP 19th World Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago, Chile. Paper presented at IFIP International Conference on Theoretical Computer Science : 01/08/2006 - 02/08/2006 (pp. 103-114). New York: Encyclopedia of Global Archaeology/Springer Verlag
Open this publication in new window or tab >>An O(1) solution to the prefix sum problem on a specialized memory architecture
2006 (English)In: PFourth IFIP International Conference on Theoretical Computer Science - TCS 2006: IFIP 19th World Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago, Chile / [ed] Gonzalo Navarro; Leopoldo Bertossi; Yoshiharu Kohayakawa, New York: Encyclopedia of Global Archaeology/Springer Verlag, 2006, p. 103-114Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the problem can be solved optimally in Θ(lgN) time under the comparison based model of computation.

Place, publisher, year, edition, pages
New York: Encyclopedia of Global Archaeology/Springer Verlag, 2006
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-32407 (URN)6e7788c0-96ca-11dc-ad7f-000ea68e967b (Local ID)9780387346335 (ISBN)6e7788c0-96ca-11dc-ad7f-000ea68e967b (Archive number)6e7788c0-96ca-11dc-ad7f-000ea68e967b (OAI)
Conference
IFIP International Conference on Theoretical Computer Science : 01/08/2006 - 02/08/2006
Note

Godkänd; 2006; 20071119 (ysko)

Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-02-23Bibliographically approved
Nilsson, A. (2004). Data structures for bandwidth reservations and quality of service on the Internet (ed.). (Licentiate dissertation). Paper presented at . Luleå: Luleå tekniska universitet
Open this publication in new window or tab >>Data structures for bandwidth reservations and quality of service on the Internet
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 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.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2004. p. 6
Series
Licentiate thesis / Luleå University of Technology, ISSN 1402-1757 ; 2004:21
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-18000 (URN)655b3510-aec8-11db-803d-000ea68e967b (Local ID)655b3510-aec8-11db-803d-000ea68e967b (Archive number)655b3510-aec8-11db-803d-000ea68e967b (OAI)
Note
Godkänd; 2004; 20070128 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved
Brodnik, A. & Nilsson, A. (2003). A static data structure for discrete advance bandwidth reservations on the Internet (ed.). In: (Ed.), (Ed.), Proceedings of Swedish National Computer Networking Workshop: SNCNW 2003. Paper presented at Swedish National Computer Networking Workshop : 01/09/2003 - 02/09/2003. Stockholm
Open this publication in new window or tab >>A static data structure for discrete advance bandwidth reservations on the Internet
2003 (English)In: Proceedings of Swedish National Computer Networking Workshop: SNCNW 2003, Stockholm, 2003Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Stockholm: , 2003
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-37050 (URN)aec3baf0-96cc-11dc-ad7f-000ea68e967b (Local ID)aec3baf0-96cc-11dc-ad7f-000ea68e967b (Archive number)aec3baf0-96cc-11dc-ad7f-000ea68e967b (OAI)
Conference
Swedish National Computer Networking Workshop : 01/09/2003 - 02/09/2003
Note
Godkänd; 2003; 20071119 (ysko)Available from: 2016-10-03 Created: 2016-10-03 Last updated: 2018-01-14Bibliographically approved
Brodnik, A. & Nilsson, A. (2003). Data structure for a time-based bandwidth reservations problem (ed.). Paper presented at . Ljubljana, Slovenia: IMFM
Open this publication in new window or tab >>Data structure for a time-based bandwidth reservations problem
2003 (English)Report (Other academic)
Abstract [en]

We discuss a problem of handling resource reservations. The resource can be reserved for some time, it can be freed or it can be queried what is the largest amount of reserved resource during a time interval. We show that the problem has a lower bound of $\Omega(\log n)$ per operation on average and we give a matching upper bound algorithm. Our solution also solves a dynamic version of the related problems of a prefix sum and a partial sum.

Place, publisher, year, edition, pages
Ljubljana, Slovenia: IMFM, 2003. p. 10
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-23900 (URN)8dd5e990-9770-11dc-ad7f-000ea68e967b (Local ID)8dd5e990-9770-11dc-ad7f-000ea68e967b (Archive number)8dd5e990-9770-11dc-ad7f-000ea68e967b (OAI)
Note
Godkänd; 2003; 20071120 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved
Karlsson, J., Bodin, U., Brodnik, A., Nilsson, A. & Schelén, O. (2003). Extended expedited forwarding: the in-time PHB group (ed.). In: (Ed.), (Ed.), Computers and Communication, 2003. (ISCC 2003): Proceedings of the Eighth IEEE International Symposium on Computers and Communications. Paper presented at IEEE International Symposium on Computers and Communications : 30/06/2003 - 03/07/2003 (pp. 291-298). : IEEE Computer Society Press, 1
Open this publication in new window or tab >>Extended expedited forwarding: the in-time PHB group
Show others...
2003 (English)In: Computers and Communication, 2003. (ISCC 2003): Proceedings of the Eighth IEEE International Symposium on Computers and Communications, IEEE Computer Society Press , 2003, Vol. 1, p. 291-298Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents a new set of forwarding behaviorsthat fits rate-adaptive and delay-sensitive applications withlimited loss tolerance. We consider an application to havelimited loss tolerance if it needs loss-free forwarding of specificpackets up to a certain rate. The new set of forwardingbehaviors are attractive for developing real-time applicationsfor the Internet. In particular, such applications canbe designed to use reserved forwarding capacity efficientlyand compete for more bandwidth while being fair to best-efforttraffic. To provide the new set of forwarding behaviors,we define a scheduling mechanism that can be implementedefficiently. Through simulations, we show that thismechanism supports the defined forwarding behaviors.

Place, publisher, year, edition, pages
IEEE Computer Society Press, 2003
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-26768 (URN)10.1109/ISCC.2003.1214136 (DOI)000184416200044 ()2-s2.0-84883895752 (Scopus ID)001e8d90-b2a2-11db-bf9d-000ea68e967b (Local ID)0-7695-1961-X (ISBN)001e8d90-b2a2-11db-bf9d-000ea68e967b (Archive number)001e8d90-b2a2-11db-bf9d-000ea68e967b (OAI)
Conference
IEEE International Symposium on Computers and Communications : 30/06/2003 - 03/07/2003
Note
Godkänd; 2003; 20060922 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-07-10Bibliographically approved
Brodnik, A. & Nilsson, A. (2003). Static data structure for discrete advance bandwidth reservations on the internet (ed.). Paper presented at . Luleå
Open this publication in new window or tab >>Static data structure for discrete advance bandwidth reservations on the internet
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:nbn:se:ltu:diva-24020 (URN)959905f0-976f-11dc-ad7f-000ea68e967b (Local ID)959905f0-976f-11dc-ad7f-000ea68e967b (Archive number)959905f0-976f-11dc-ad7f-000ea68e967b (OAI)
Note
Godkänd; 2003; 20071120 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved
Brodnik, A. & Nilsson, A. (2002). An efficient data structure for advance bandwidth reservations on the Internet (ed.). In: (Ed.), (Ed.), Proceedings of CSEE 2002: Second Annual Conference on Computer Science and Electrical Engineering. The third Annual Symposium on Computer Science and Electrical Engineering. Paper presented at Annual Conference on Computer Science and Electrical Engineering : 27/05/2002 - 28/05/2002.
Open this publication in new window or tab >>An efficient data structure for advance bandwidth reservations on the Internet
2002 (English)In: Proceedings of CSEE 2002: Second Annual Conference on Computer Science and Electrical Engineering. The third Annual Symposium on Computer Science and Electrical Engineering, 2002Conference paper, Published paper (Refereed)
Abstract [en]

In this contribution we present a problem of resource reservation during some time. We show that the problem has a lower bound of Ω (log n) per operation on average and also give a matching upper bound algorithm.

National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-34214 (URN)859bd300-9772-11dc-ad7f-000ea68e967b (Local ID)859bd300-9772-11dc-ad7f-000ea68e967b (Archive number)859bd300-9772-11dc-ad7f-000ea68e967b (OAI)
Conference
Annual Conference on Computer Science and Electrical Engineering : 27/05/2002 - 28/05/2002
Note
Godkänd; 2002; 20071120 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-01-14Bibliographically approved
Schelén, O., Nilsson, A., Norrgård, J. & Pink, S. (1999). Performance of QoS agents for provisioning network resources (ed.). In: (Ed.), 1999 Seventh International Workshop on Quality of Service: IWQoS '99, London, England, May 31 - June 4, 1999. Paper presented at International IWQoS conference : 01/06/1999 - 04/06/1999 (pp. 17-26). Piscataway, NJ: IEEE Communications Society
Open this publication in new window or tab >>Performance of QoS agents for provisioning network resources
1999 (English)In: 1999 Seventh International Workshop on Quality of Service: IWQoS '99, London, England, May 31 - June 4, 1999, Piscataway, NJ: IEEE Communications Society, 1999, p. 17-26Conference paper, Published paper (Refereed)
Abstract [en]

We have designed an agent-based architecture for quantitative service provisioning in differentiated services capable networks. For each link-state routing domain in the network there is a topology-aware QoS agent (also known as a bandwidth broker) responsible for admission control. The architecture provides resource reservations for aggregated virtual leased lines between network domains. In this paper, we present performance measurements for resource provisioning in a prototype QoS agent. This includes an evaluation of two data structures for advance reservations and accompanying algorithms. We also compare the cost for on-demand route computations with pre-computation of routes. The objective in this paper is to evaluate the performance of end-to-end admission control within a single link-state routing domain. In a domain with 15 routers, 28 transition networks and 64 stub networks, our prototype performs approximately 25000 end-to-end admission decisions per second. The results show that an ordinary PC can be used for running a QoS agent that performs path-sensitive admission control and maintains per link resource reservations in a link-state routing domain.

Place, publisher, year, edition, pages
Piscataway, NJ: IEEE Communications Society, 1999
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-27247 (URN)10.1109/IWQOS.1999.766474 (DOI)000081719000005 ()09c777a0-9774-11dc-ad7f-000ea68e967b (Local ID)0-7803-5671-3 (ISBN)09c777a0-9774-11dc-ad7f-000ea68e967b (Archive number)09c777a0-9774-11dc-ad7f-000ea68e967b (OAI)
Conference
International IWQoS conference : 01/06/1999 - 04/06/1999
Note

Godkänd; 1999; 20071120 (ysko)

Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-09-03Bibliographically approved
Organisations

Search in DiVA

Show all publications