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.

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

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.