The MPLS-OPS Archive

[Ronald & Serena Travasso <serenaronald@bigpond.com>]

Can anyone help me with a small problem.

I have just started on a report  on " Conventional IP routing vs MPLS label
switching" with a particular reference to table lookup delay.

This is where I have a small problem which I sincerely hope you somone would
take the time to help me out.

Here it is:

I've got a Pentium IV 3GHz machine to be used as a core router maintaining
1000 entries in its routing table, and a visit to an entry in the routing
table takes 1 ms.

My main query is:

"How would you calculate the table lookup delay for an incoming packet if
conventional IP routing is used, and what would the table lookup delay be if
MPLS label switching is used."

These are my thoughts:

Table lookup delay depends on a number of factors - size of the routing
table, speed of the processor where the lookup is taking place and the
lookup algorithm. (cisco ref)
I've been through a number of algorithms ( Patricia Tree, binary search
etc. ) and I've noticed that the worst case scenario is O(WlogN) where N is
the number of prefixes and W the depth of the tree. (Gupta, Varghese) You
have to go through the entire routing table of 1000 (W) entries to find the
longest match. I'm not sure if I'm on the right track here. Where does the
speed of the processor fit in here??

For MPLS when a packet with label 123 is received, the router simply has to
lookup line 123 of it's label forwarding table. So where's and what could be
the delay here?

Further as I understand, MPLS label switching might not make routing faster
but definitely efficient, in terms of reduced route lookup time. If one has
large number of routes in the forwarding table and next hop for all of them
is same, I understand that one single label replaces this entire table.

Any help with calculating the lookup delay would be very helpful.   It's a
small but integral part of my report which would ensure its completedness -
comparison of IP routing vs MPLS label switching.

Looking forward to your reply, and once more I would like to take this
opportunity to thank you for taking the time to read this e-mail.


Thank you and have a good day.

Ronald Travasso

-------
The MPLS-OPS Mailing List
Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
Archive: http://www.mplsrc.com/mpls-ops_archive.shtml