SPEAKER: Anat Bremler-Barr (TAU)
<P>

Title: Algorithms for Efficient and Reliable routing in the Internet

<P>
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".
<P>
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.
<P>
Routing with a clue:
<P>
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.
<P>
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.