Luleå University of Technology
LTU home search department home white sqaure used as filling head



These pages are no longer maintained. Please visit www.csee.ltu.se instead.



Research Seminar Schedule 2004/5
white sqaure used as filling
Welcome

Contact

Education
 Undergraduate
 Graduate

Research
 Publications
 Seminar
 Projects

People

Open Positions

Internal pages
Research - Division of Computer Science and Networking

Every other Tuesday 1500-1600 in A3001, unless otherwise noted.

Next

Date Presenter Description
Apr 12 Johan Karlsson

cake: Micke
I will present "RAMBO Replaces the ALU using Reads and Writes only" which has been submitted to WADS 2005. I will also discuss how addition can be implemented in O(lg w) steps using an additional variant of RAMBO (will be submitted to some journal). The WADS paper can be found here.

Upcoming

Date Presenter Description
Apr 26 Helena Sandström

cake: Helena
Helena will give a practice presentation of "Adaptive Threshold-Based Admission Control," which will be presented at ICC 2005 in Seoul, South Korea during May 16-20, 2005.
May 10 Anna Hedman Presentation of ongoing work: Comparison of browsing techniques with a 3d mouse as input device. Focus will be interaction issues and design of the experiment.
May 24    
Jun 07    

Previous

Date Presenter Description
Mar 29 Mats Folke

cake: Mats
Mats will give a practice presentation of "On the TCP Minimum Retransmission Timeout in a High-speed Cellular Network," which will be presented at the 11th European Wireless Conference in Nicosia, Cyprus, during April 10-13, 2005.
Mar 15 Sara Landström

cake: Anders
Practice for Licentiate presentation. Abstract and link to Thesis.
Mar 01 Thomas Björklund

cake: Fredrik
The trie is an efficient data structure for storing strings. Several improvements of the original trie structure have been proposed by others, and during this presentation it will be explained how two of them can be used to create a trie that is optimal with respect to size. Further, the height of tries created with the method described can be controlled, which allows for queries in constant time.
Feb 15 Pierre Fransson

cake: Johan K.

Link-state routing based on Dijkstra's algorithm, has up till recently been fast enough in dealing with component failures to satisfy the requirements of traditional Internet applications (e.g., email, file transfer, etc). However, newer applications, such as Voice-over-IP, have more severe requirements. Outages in connectivity lasting several seconds are much larger that what is typical in the "telecom world", where network faults are typically repaired within a 100 milliseconds.

The two main problems in reaching fast reaction times in response to failure are, being able to detect network events rapidly, and that link-state information has to be flooded to all routers before a new shortest path tree can be used. Detection of networking events can quite easily be improved upon. Today, detection often takes place on the application layer (through the exchange of routing messages) resulting in detection delays on the order of seconds. If lower layer detection mechanisms are used (e.g., detection loss-of-light in fiber cables) the delay could be decreased to at least the order of micro seconds, if not better. Having to wait for news of the networking event to be flooded to the entire network is not either always necessary. By using precomputed fail-over paths it is possible to react to a networking event as soon as detection has occurred, enabling reaction times below the requirements of real-time applications.

Unfortunately the above suggested modifications may fail in yielding any improvements whatsoever in reaction times, due to the possibility of temporary routing loops forming during the flooding of link-state information. If temporary routing loops form during flooding then any traffic encountering such a loop will be delayed and will also most likely be lost. In the above described scheme it therefore becomes paramount to avoid formation of temporary routing loops.

As a remedy, a loop-avoidance algorithm is proposed that works in conjunction with "ordinary" link-state routing in order to assure the prevention of temporary routing loops during the flooding process. The algorithm can handle any single link or single router event (i.e., failure or addition of any single link or single router of/to the network, or a change in cost for any single link). The algorithm is based on each router querying its neighbors for loop-free paths. The worst case message complexity for a network event is O(n*n) which is the same as the worst case message complexity for a network event in ordinary link-state routing using flooding.

Feb 01 Thomas Bladh Animated transitions are so plentiful in user interfaces today that we hardly notice them. Complex animated transitions such as fades and morphs, previously confined to games and specialty applications, are becoming more and more commonplace. Yet the impact of the use of such transitions has been a relatively neglected area of empirical research. To help remedy this shortcoming we conducted a user study with 16 volunteers from a human computer interaction course at Luleå University of Technology. In this study we focused on whether animated transitions between directories in a 3D visualization of file system hierarchies might help users better grasp the spatial organization of the visualized structure they are navigating. We also wished to uncover any negative effects that animated transitions might have on navigation in general. Our results show that the use of animated transitions does have a rather profound effect on navigation behavior on tasks consisting of returning to a previously visited directory. Participants in the study who were exposed to animated transitions took a significantly greater number of shortcuts on this type of task. This effect does not however translate into a statistically significant difference in task times. One intriguing indication from the data collected is that animations may even be harmful, as the use of animation seems to increase the number as well as the severity of navigational errors.
Jan 18 Christer Åhlund This talk will present multi-homed mobile IP and a connectivity solution between ad hoc networks and wired IP networks. In future wireless access networks, connectivity to wired infrastructure will be provided through multiple access points with possibly different capabilities and utilization. The demand for increased network performance requires the ability to predict the best overall performance of those access points and to switch access point when the performance changes. Then there is the demand for mobility between networks with maintained connectivity which requires the ability to switch the point of attachment. Mobile IP support is needed to allow mobile hosts to move between networks with maintained connectivity. Multi-homed mobile IP enables performance discovery at the networks layer and the capability to decide what AP to use. Multi-homed mobile IP enables mobile hosts to register multiple care-of addresses at the home agent, to enhance the performance of wireless network connectivity.

Ad hoc networks have thus far been regarded as stand-alone networks without assumed connectivity to wired IP networks and the Internet. With wireless broadband communications and portable devices with appropriate CPU, memory and battery performance, ad hoc connectivity will become more feasible and demand for global connectivity through ad hoc networking is likely to grow. This talk presents an approach and describes a prototype for connectivity between an ad hoc network running the Ad Hoc On-Demand Distance-Vector Protocol and a wired IP network where multi-homed mobile IP is used for mobility management.
Dec 13 Stefan Nilsson
Extra Seminar
13:00 in A1549
Title: När algoritmen möter hårdvaran

Abstract: Man säger ofta att mjukvara är böjlig och lätt att modifiera medan hårdvara ses som huggen i sten och oföränderlig. Men paradoxalt nog så är livslängden för mjukvara ofta mycket längre än för hårdvara - det är inte ovanligt att man använder samma program i tiotals år medan datorn sällan överlever mer än ett par år. Trollerikonsten utförs med hjälp av ett isolerande lager bestående av en kompilator och ett runtimesystem som gör att programmeraren oftast inte behöver ta hänsyn till hårdvaruspecifika detaljer. Den här uppdelning är nästan bara av godo. Men man betalar ändock ett pris: det kan vara svårt eller omöjligt att fullt ut tillvarata hårdvarans möjligheter.

Hur utnyttjar man bäst en modern processor som är superskalär, djupt pipelinad och har flera nivåer av cacheminne? Vilka optimeringar kan kompilatorn göra? Måste högnivåprogrammeraren kunna datorarkitektur för att skriva effektiva program? Hur skriver man program som är effektiva och samtidigt flexibla och portabla?
Dec 14 Fredrik Bengtsson
10:15 in A1545
Fredrik will present his Licentiate thesis.

ABSTRACT: As computers are developing rapidly and become more available to the modern information society, the possibility and ability to handle large data sets in database applications increases. The demand for efficient algorithmic solutions to process huge amounts of information increases as the data sets become larger. In this thesis, we study the efficient implementation of aggregate operations on the data cube, a modern and flexible model for data warehouses. In particular, the problem of computing the k largest sum subsequences of a given sequence is investigated. An efficient algorithm for the problem is developed. Our algorithm is optimal for large values of the user-specified parameter k. Moreover, a fast in-place algorithm with good tradeoff between update- and query-time, for the multidimensional orthogonal range sum problem, is presented. The problem studied is to compute the sum of the data over an orthogonal range in a multidimensional data cube. Furthermore, a fast algorithmic solution to the problem of maintaining a data structure for computing the k largest values in a requested orthogonal range of the data cube is also proposed.

A copy of the thesis can be found here.

Note the time and location are different.
Nov 30 Anders Magnusson TITLE: Internet Land Speed Record

ABSTRACT: On September 12, 2004, SUNET transferred around 1831 Gigabytes of data (corresponding to approx. 2800 CD:s) in about one hour, using a single TCP stream between one host at the Luleå University of Technology and one host connected to a Sprint PoP in San Jose, CA, USA. The network path used is the GigaSunet backbone - shared with other users of the Swedish universites, and the SprintLink core network, used by all the customers of Sprintlink.

The transfer was done with the ttcp program, available for many different platforms. We have chosen to use NetBSD for our tests, due to the scalability of the TCP code. ttcp is usually included in Unix and Linux systems. Windows users can download a Win32 version from pcusa.

The focus of the seminar is to discuss some of the problems encountered both in the TCP protocol and in some of the common TCP/IP stack implementations that are available today, and how the problems were solved to obtain the result.
Nov 16 Andreas Jonsson Andreas will give a practice presentation of End-to-End Measurements on Performance Penalties of IPv4 Options by Pierre and himself. The paper has been accepted at Globecom 2004 in Dallas.
Nov 02 Tomas Johansson Tomas will present his current research on topology control algorithms.
Oct 19 Sara Landström TCP-like is currently up for standardization as part of the Datagram congestion Control Protocol (DCCP) in the IETF. DCCP offers an unreliable transport service with congestion control to upper layers and TCP-like is one of two algorithms that can be chosen to manage the send rate. Sara will present the results of an evaluation of  the TCP-like algorithm. Performance differences between TCP-like congestion control and the congestion control and avoidance mechansims in TCP SACK will also be highlighted and possible improvements discussed.
Oct 05 Tomas Klockar

Tomas will give a practice presentation of Preventing Oscillations in I-BGP with Route Reflectors, which will be presented at ICCCN 2004.

Sep 21 Anders Lindgren

Anders will present a talk entitled "Multi-path Admission Control for Mobile Ad hoc Networks", which is based on his work at UCSB with Elizabeth Belding-Royer. An abstract follows:

To enable the use of applications that require real-time communication in ad hoc networks, congestion must be prevented since it results in reduced quality of service for applications. An admission control mechanism can be used for this purpose. However, current admission control solutions encounter problems during mobility, often resulting in unacceptable disruptions in communication. To solve this problem, we apply multi-path routing mechanisms that maintain alternate paths to the destination and propose a new admission control protocol. We show through simulation that our solution is able to prevent communication disruptions and meet the QoS needs of applications better than previous solutions.

Sep 07 Johan Nykvist

Johan will present results from his research on policy disputes and discuss ideas for future research. An abstract follows:

Routing between domains in Internet is accomplished by the Border Gateway Protocol (BGP). BGP enables operators to define routing policies independently of each other. This results in metrics that do not keep monotonic and isotonic properties, and therefore, the routing algorithm may not converge. One way to solve the problem is to identify policies that cause divergence.

Griffin and Wilfong have proposed an algorithm that detects disputing policies by recording histories of selected routes. When they crafted the algorithm, they did not consider the send-rate constraint that is applied in BGP. This constraint is crucial for BGP as it limits the number of routing messages and decreases convergence time.

We show that conclusions made by Griffin and Wilfong about the algorithm do not hold when it is combined with a routing message send-rate mechanism.

We prove that the consistency property of a pipe connecting two nodes is broken when message timing is applied. The route history may not show the whole causal chain of changes in routing tables and may give rise to false conclusions. These results are confirmed by simulation.

Aug 24 Fredrik Bengtsson Fredrik will give a practice talk for his paper entitled: Space-Efficient Range-Sum Queries in OLAP. The paper will be presented at DaWaK 2004 in Spain, Zaragoza, September, 2004.
Aug 10 Gonzalo Rodrigo

Gonzalo will present his master's thesis entitled: Convergence Time Reduction in the BGP4 Routing Protocol Using the "Ghost-Flushing" Technique and Other Proposals. An abstract follows:

BGP4 (Border Gateway Protocol) is the language that makes possible to keep up to date the road maps in the internet. This routing protocol is the one used by the "big networks" to exchange routing information. Thus, its performance is critical for the internet.

In some situations the behavior of this protocol is not the desired one. This thesis intends to analyze one of this problems together with some proposed solutions. This analysis will involve a review of the theory behind the proposals and a later simulation to test the performance of them. After the analysis is done, the proposals considered as "useful" will be implemented over an open source, free routing software, GNU Zebra.

2003/4   Seminars presented during the 2003/4 school year can be seen on last year's page.

Last modified 2005-05-09
Page owner is Johan Karlsson

  link symbol  



LULEÅ UNIVERSITY OF TECHNOLOGY