SPEAKER: Anat Bremler-Barr (TAU)

Title: Algorithms for Efficient and Reliable routing in the Internet

Efficient protocols and algorithms that support fast and reliable routing in the Internet are presented. I will start with a quick overview of the main results of my PhD and then go into the details of "Routing with a clue".

The overview includes: * "Routing with a clue" - An efficient IP look up algorithm. * Fast restoration scheme in MPLS, by using path concatenation. * Introducing a new label switching scheme thatis more efficient than MPLS. * Improving the convergence time of BGP protocol. * Improving the routing protocol locally by choosing a route according to real performance measurements and not just based on routing protocol information.

Routing with a clue:

IP-lookup is the operation by which a router decides for each incoming packet to which outgoing interface to forward the packet. In the IP-lookup process, the router searches its forwarding table, that usually consists of 100,000 prefixes, for the best prefix match - the longest prefix that matches the packet's destination address.

In this work we provide a new architecture for an IP-lookup in which the IP-lookup reaches a speed that is as fast as that of switching techniques. In this new architecture, each router adds a clue to each packet, notifying its downstream router where it ended the IP-lookup. Since neighboring routers' forwarding tables are similar, the clue either directly determines the best prefix match for the downstream router, or provides the downstream router with a logical point to begin its IP lookup. This new scheme, entitled Distributed IP-Lookup, prevents repeated computations while distributing the IP-lookup process across the routers along the packet path. The speedup we achieve is about 10 times faster than current standard techniques. Ph.D. dissertation, work supervised by Prof Yehuda Afek.