The MPLS WG Archive

["Choudhury, Sanjaya" <Sanjaya.Choudhury@marconi.com>]

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.

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