The MPLS WG Archive

["Thomas D. Nadeau" <tnadeau@cisco.com>]

> -----Original Message-----
> From: owner-mpls@UU.NET [mailto:owner-mpls@UU.NET] On Behalf 
> Of Choudhury, Sanjaya
> Sent: Tuesday, June 10, 2003 12:06 PM
> To: 'mpls@UU.NET'
> Subject: RE: prequeal to WG lat call om the LSR mib 
> module[mplsInSegmentTable]
> 
> 
> Hi! Few comments in-line regarding the indexing of the 
> mplsInSegmentTable
> 
> > -----Original Message-----
> > From: Thomas D. Nadeau [mailto:tnadeau@cisco.com]
> > Sent: Saturday, June 07, 2003 9:13 AM
> > To: 'Wijnen, Bert (Bert)'; 'MPLS WG'
> > Subject: RE: prequeal to WG lat call om the LSR mib module
> > > -----Original Message-----
> > > From: owner-mpls@UU.NET [mailto:owner-mpls@UU.NET] On Behalf
> > > Of Wijnen, Bert (Bert)
> > > Sent: Friday, June 06, 2003 11:14 AM
> > > To: MPLS WG
> > > Subject: RE: prequeal to WG lat call om the LSR mib module
> > > 
> >
> <snip...>
> 
> > 	Application		Incoming Labels Owned by Application
> > 	LDP			{ 15, 29, 45 }
> > 	VPN			{ 30, 31, 32 }
> > 	TE  			{ 16, 17, 18 }
> > 	
> > 	Using the original indexing of (ifIndex, mplsLabel)
> > worked for the above example, but as VERY inefficient
> > for a GetNext operation. Think about what happens when
> > the manager issues a GetNext(14). In this case, I first
> > have to visit each application and ask it if it has a
> > label that is greater than 14. This costs O(N)* num appliations
> > in the worse case. 
> >   	
>   Comments on the indexing of the mplsInSegmentTable:
> 
>   1. O(N)*num-applications cost for a getNext() on 
>      mplsInSegmentTable, appears to be an artifact
>      of specific agent implementations. [when the 
>      underlying container is distributed.]
> 
>   2. Description for the mplsInSegmentTable, points out
>      that the new indexing structure is designed to 
>      handle multiple implementations.
> 
>      I think this is not a good idea to design MIB tables 
>      to fit individual implementations. In my personal
>      opinion the original indexing for the 
>      mplsInSegmentTable was more natural and appropriate.

	The problem with designing in the ideal is that
real implementations will have issues with it. The
IETF generally considers implementation and deployment 
experience highly over the ideal. I have provided some 
real world feedback that indicates that a single Unsigned32 
index is insufficient. I also have about 300 customers 
that have provided me with the same feedback. I think that
it has little to do with my specific style of implementation
either (see below).

>   3. It is true that there is always a memory and speed
>      tread-off in real world designs. However, this
>      tread-off should be a choice of the individual 
>      implementations. Boxes with higher amount of
>      memory might choose an implementation approach
>      that provides relatively efficient GetNext(), even
>      with the original indexing (ifIndex,label)

	It is not that easy. If you look at a distributed
label management versus one with single label mamanagement
you will see that even in your ideal picture there are
issues of finding labels based on a single, simple 
Unsigned32 when you consider how many operations it will
take to find the labels. In the non-distributed method,
implementations must either provide some hash function
that maps the Unsigned32 to the internal data structure,
use the actual label as the index (which doesn't
work in the outsegment case), use a memory address or 
assign some other arbitrary GUID value to the entry.
In all of these cases, GetNext operations will be at best
O(N) and can multiples worse. This means that MIB Walks will 
be O(N^2) when you finally add things up.  On a P router
with 150k TFIB entries, this is a serious amount of time! 

	Now consider the distributed approach. The analysis is 
much worse for distributed label management with a single
Unsigned32. When doing a GetNext you need to make sure that 
each "bag" of labels doesn't have a better label than the one
you currently have. This is probably an N^2 search when it is 
all said and done. This results in N^3 MIB Walks too, which
is even worse. This has little to do with my specific 
implementation.

	Now consider using a larger opaque index such as the
one I have proposed. This allows implementations to use
the above indexing as I just described. If they want to use
just 4 bytes, you get the EXACT same result and if your
implementation can somehow do better than the results
I showed above, then more power to it. Other implementations
are however free to use more bytes to index if they need
them to make the searches more efficient. I see real
benefit in this -- like making the MIB useful versus
useless.

	--Tom