Subject: RE: prequeal to WG lat call om the LSR mib module[mplsInSegmentTa ble]

From: "Choudhury, Sanjaya" <[email-masked]>
Date: Tue, 10 Jun 2003 12:05:48 -0400

Hi! Few comments in-line regarding the indexing of the 
mplsInSegmentTable

> -----Original Message-----
> From: Thomas D. Nadeau [mailto:[email-masked]]
> 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: [email-masked] [mailto:[email-masked]] 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.

  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)

Thanks,
sanjay

> 	Now consider how most implementations store the outgoing 
> label.  It is my understanding that most implementations do
> not index on the outgoing label; rather only on the incoming
> one since they do not own the outgoing label. This means
> that to find the outgoing label, you have a search
> that requires you do search first through all of the
> incoming labels, and then for each one, search make
> sure that the outgoing label is "best". This results
> in O(N^2).
> 
> 	My operational experience with this MIB and
> my customers who are using it over the past 3 or so
> years is that such searches translate into is essentially
> an unusable MIB considering how many entries are
> often contained -- O(100,000+) on a P router -- and 
> how long it will take to download each entry * the 
> number of entries in the table.
> 
> 	Now consider if you had used Adrian's
> original approach of (applicationId, ifIndex, label):
> The searhes would be vastly faster -- O(N)
> in all cases -- because you would quickly know if 
> you were in the right collection of labels or not, 
> and then search through its list of labels. If not
> in the right collection, you simply move on to the next
> one and search there. The only problem with this approach
> is that you have do do at least an O(N) search to find 
> the "next" best label. Using more indexing space allows
> implementations to customize the index to match EXACTLY
> how they index internally, thus giving the potential
> for searches to happen in O(1) time, so no matter how
> large the table is, you can get the data returned
> to you very, very quickly with minor extra overhead on
> the wire to achieve this.
> 
> 	So as you can see, some extra bits on the wire
> can go a long, long way to making this MIB extremely
> useful.
> 
> 	--Tom
> 
> 
> > Thanks,
> > Bert 
> > 
>

---

From: "Thomas D. Nadeau" <[email-masked]>
Date: Wed, 11 Jun 2003 10:34:47 -0400

> Of Choudhury, Sanjaya
> Sent: Tuesday, June 10, 2003 12:06 PM
> To: [email-masked]'
> Subject: RE: prequeal to WG lat call om the LSR mib 
> module[mplsInSegmentTable]
> 
> 

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

>      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