Current Research Projects

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 group.

Algorithms

• 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 knowledge management.


• 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 by Norrbottens Forskningsråd.)

Computer Communications

• 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 Vinnova.)
  
  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 mechanisms.
  
  
  • 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 Stiftelsen för Strategisk Forskning.)
  
  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 network operator.
  
  
  • 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 under research.


• Other Networking Research - The division has also conducted research on:
  
  
  • 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 are met.

Human Computer Interaction

• Information 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.