The division of Computer Science and Networking covers research in Algorithms,
Computer Networking, and Human-Computer Interaction. Our research interests
include: communication architectures, resource reservation, queuing strategies,
routing protocols, wireless networking protocols, algorithms for knowledge
management, algorithms for alternate architectures, computational geometry,
information visualization, user interfaces for mixed reality, and usability of
mobile devices. The following is a list of current research projects in the
- Algorithms for Knowledge Management - Investigates data structures
to improve access into constrained sets, perform range sums, and perform
range queries. These problems occur in the domains of information and
- Algorithms for Fast, Compressed Router Tables - Investigates data
structures and algorithms to rapidly access routing tables. In addition to
algorithm theoretic issues, actual implementation is taken into account.
As a result, router tables must be compressed so that they fit inside of
the on-chip cache. Trade-offs between compression and incremental update
efficiency are being explored, as well as traditional algorithmic issues
such as lower bounds for space and time.
- Alternate Computer Architectures - Investigates computation in the RAMBO
model, which extends the ordinary RAM model so that a bit in memory occurs
in several words. A hardware implementation of the RAMBO model can be used
to improve performance of priority queues and prefix sums. These have
applications in high-speed routers and other special purpose computers.
- AVT - This project studies methods for computing paths for
autonomous transport vehicles. Specifically, the project investigates
methods to compute safe paths for vehicles in narrow, confined
environments such as ore loading vehicles in a mine. (Support provided
- Performance Optimization in Mixed Fixed/Cellular Data Networks -
New cellular radio networks erected according to WCDMA release 5 (3G),
maintains support for a shared high speed data channel. The common resource,
the channel, is shared primarily in the time domain which is suitable for
most congestion controlled flows, since they probe for bandwidth and thus
only periodically can take advantage of the entire capacity of a dedicated
channel. Simulation techniques, different congestion control mechanisms,
buffer strategies and radio channel characteristics are being studied.
(Support provided by
Vinnova and by
the European Commission's Goal 1
structural fund program for northern Norrland, vITal project.)
- Predictable Services in Future Networks - One of the major
challenges for Internet research and development is to provide routing
protocols that can handle increasing network density and interconnection.
Current inter-domain routing protocols (the Border Gateway Protocol, BGP,
included), and current configuration practices have problems handling
increased interconnection. (Support provided by
Research focuses on:
- BGP is divided into two parts. The external part E-BGP defines
exchange of routing information among autonomous systems (large
operators). The internal part I-BGP handles exchanges within
autonomous systems. The E-BGP protocol enables operators to define
routing policies independently of each other. This results in metrics
that does 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. Algorithms that detect
disputing policies do not consider timing issues that are common in
BGP routing. We extended the algorithms with time synchronization
- Work on I-BGP continues in parallel with the research on E-BGP.
Inside one autonomous system, where Internal BGP works, the routers
can be organized either to confederations or route reflectors. We
designed a modification to the Internal Border Gateway Protocol that
prevents oscillation in I-BGP
- The third subproject in Inter-domain routing is examining the
influence of the Ghost flushing mechanism to the routing convergence.
The Ghost Flushing rule proposes a way to eliminate from the beginning
the Ghost Information, which is the update that might be obsolete.
- Winternet - Winternet is a research initiative together with three
other Swedish network reserach groups at the Royal Institute of
Technology (KTH), the Swedish Institute of Computer Science (SICS), and
Uppsala University. Winternet has seven subprojects of which we are working
on four: Autonomous Security Management, Application Service Overlays,
Scalable & Robust Routing, and New Architectures. For more details, see
the Winternet home page.
(Support provided by
Specific current work within this project includes:
- Studying and developing new routing approaches to allow better
aggregation of routing information. We developed a scheme for
fail-over routing to meet the robustness needs of interactive
real-time applications in case of link failures. Slow convergence and
even divergence under configured routing policies is a severe problem
in inter-domain routing. A goal is to design a new routing
architecture and to deploy mathematical analysis to address types of
policies that are incompatible across domain boundaries and cause
divergence of routing.
- Developing a mechanism that enables load-sensitive use of multiple
paths. The mechanism will probably need to work on a rather long
time-scale (hours) and within the local scope controlled by one
- Introducing and studying the notion of infrastructure ad hoc networks
that are intended for a different scenario than traditional ad hoc
networks, namely as an extension of infrastructure wireless networks.
Protocols for routing and network partitioning in ad-hoc networks
- Other Networking Research - The division has also conducted research
- Designing a pipeline architecture that implements efficient
forwarding-table lookup algorithms.
- Measuring the effect of IP options on message delivery. IP options are
often proposed as a means to implement extensions to current Internet
protocols. If the presence of options adversely affects message deliver,
they are not an effective means to implement extensions.
- Assuring quality of service using "Bandwidth Brokers". Different types
of traffic have different tolerances to lost packets and delay jitter.
Bandwidth Brokers are agents that manage the admission of streams with
different QoS requirements. Specific work includes improvements to data
structures for handling the reservations and methods to dynamically
adapt to changing network conditions so as to ensure that QoS promises
Human Computer Interaction
Visualization - Investigates the design and effectiveness of methods
to present information using interactive graphics. The project is
investigating a three-dimensional, space-filling visualization for
hierarchical data sets (StepTree) and comparing it to similar
two-dimensional methods (Tree-maps). The project has also studied
visualization as a method to understand the dynamic behavior and to tune
large distributed systems.
- PhyVir - Blending
the Physical and the Virtual in Human-Computer Interaction -
Investigates how to integrate virtual things with physical. One part
of the project deals with electronic bulletin boards, and how these
could be used for various purposes in everyday life. Aspects that we
are studying include alternative ways to find information by browsing
thumbnails, linking physical objects such as notes to virtual
representations in remote locations, and alternate views of the
bulletin board depending on display capabilities. (Support provided by
the European Commission's
Goal 1 structural fund program for northern Norrland, vITal project.)
- Usability of Mobile Devices - Investigates the construction of
cognitive models for the use of mobile devices such as cellular phone and
conducts usability studies to determine aspects of mobile device design
that enhance or detract from easy operation.