Research - Division of Computer Science and Networking
Every other Tuesday 1500-1600 in A3001, unless otherwise noted.
|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
|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.
|| 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.
|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
|Practice for Licentiate presentation.
Abstract and link to
|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.
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
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.
||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.
||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.
13:00 in A1549
|Title: När algoritmen möter hårdvaran
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?
10:15 in A1545
|Fredrik will present his Licentiate thesis.
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
Note the time and location are different.
||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
||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.
||Tomas will present his current research on topology control
||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.
Tomas will give a practice presentation of Preventing Oscillations in I-BGP
with Route Reflectors, which will be presented at ICCCN 2004.
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.
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
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
||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.
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.
||Seminars presented during the 2003/4 school year
can be seen on last year's