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

From: "Choudhury, Sanjaya" <[email-masked]>
Date: Mon, 16 Jun 2003 19:09:45 -0400

Comments in-line. 

> -----Original Message-----
> From: Thomas D. Nadeau [mailto:[email-masked]]
> Sent: Monday, June 16, 2003 2:05 PM
> To: 'Choudhury, Sanjaya'; [email-masked]
> Subject: RE: prequeal to WG lat call om the LSR mib
> module[mplsInSegmentTa ble]
> 
> 
> 
> 
> > -----Original Message-----
> > From: [email-masked] [mailto:[email-masked]] On Behalf 
> > Of Choudhury, Sanjaya
> > Sent: Friday, June 13, 2003 9:07 AM
> > To: [email-masked]
> > Subject: RE: prequeal to WG lat call om the LSR mib 
> > module[mplsInSegmentTa ble]
> > 
> > 
> > Hi! I am open to all changes that will make the MIB 
> > efficient for users, but I think it is not a bad 
> > idea to examine the alternative solutions. Here 
> > are some thoughts:
> > 
> > Some of the cases, where NMS might use a GetNext()
> > on mplsInSegment table:
> > -------------------------------------------------
> > 
> > Case-1:: If the aim of the NMS is to get the next 
> > 'best/free' label, to configure the next mplsInSegment,
> > then he may encounter a (potential) O(n) search of
> > the mplsInSegmentTable.
> >     
> >      We can resolve this issue, by adding a new table:
> >      mplsNextFreeLabelTable [indexed by ifIndex]
> > 
> > 	  If ifIndex == 0 : the row indicates the 
> > 	  next free platform-label-space label
> > 
> > 	  If ifIndex !=0  : the row indicates the 
> > 	  next free interface-label-space label for
> > 	  the specified interface.
> 
> >      This solution, will address the efficiency
> >      issue, without compromising the natural
> >      indexing of the mplsInSegmentTable.
> 
> 	I disagree. It seems that you consider 
> the old indexing efficient, which I clearly do not.
	
         Here I was just trying find an alternative solution
	   to the proposed index change for the 
	   mplsInSegmentTable.

	   [Note: Here we are talking about case-1 as described above.]

	   o Do you agree that the solution I proposed 
	   provides the users of mplsInSegmentTable
	   with an efficient solution for looking up
	   the next free/best label [O(C)] ?

	   o With the solution proposed in the latest
	   version of LSR-MIB, user for case-1 might 
	   get the similar efficiency (as the one 
	   I proposed); BUT it depends on the vendor
	   implementations. 
	   Unless, everybody implement the mplsInSegmentIndex
	   the same way, user will face the same inefficiencies.

	   o I think the solution I proposed has the
	   following advantages:
		(i) the solution does leaves the index
		as is [ifIndex,label], which is natural
		for the mplsInSegmentTable
		(ii) the solution is implementation 
		independent [does not depend on the way
		a vendor implements the new mplsInSegmentIndex]
	     
> 
> > Case-2: If the aim of the NMS is to show/list all 
> > the incoming-mpls-segments, on a per-interface basis, 
> > the GetNext() works perfectly with the original indexing
> > (ifIndex,label)
> 
> 	Only for a non-distributed implementation.
> Please see prior threads as to why this works at
> best O(N), and is more likely O(N^2) on distributed
> implementations.
> 
	Note that the case-2, is addressing the case 
      where the NMS is trying to display the insegments
      on a *per-interface* basis. 

	  o When NMS is trying to display/query insegments
	    on a per-interface basis, don't you think a 
	    (ifIndex,label) index is perfect ??

	  o The worst case here is for a node that supports
	  only per-platform labels i.e O(n). But this 
	  worst case number is same for both the solutions
	  (proposed in LSR-MIB-v10 and in this e-mail)
	
	  o In distributed cases, it may be O(n) * num-app
	  in the worst case. 

> > Case-3: If the aim of the NMS is to show ALL the
> > incoming segments or access ALL the incoming
> > segments, he will need to walk the whole table
> > and indexing does not matter.
> 
> 	Indexing always matters! If I care about this
> case and can walk the entire table in 1 hour versus
> 2-4 minutes, that makes a BIG difference.  The 
> compromise that Adrian and I sent out addresses 
> all of these concerns AND is efficient.
> 

   Please note: Case-3 captures the case where the 
   user is NMS is trying to show _ALL_ the insegments.

	o If a table has n rows and one wants to 
	query all the n rows, the cost will be 
	O(n). Correct ?

	o How can I query _ALL_ the n rows from a table
	more efficiently by the choice of indexing??
	[i.e better than O(n)]	
	
  Thanks,
  sanjay

> 	--Tom
> 
>  
> > Thanks,
> > sanjay	  	      
> > 	 
> >     
> > 
> > > -----Original Message-----
> > > From: Shevenell, Michael (Mike) [mailto:[email-masked]]
> > > Sent: Thursday, June 12, 2003 10:11 AM
> > > To: [email-masked]'; 'Choudhury, Sanjaya'; [email-masked]
> > > Subject: RE: prequeal to WG lat call om the LSR mib 
> > > module[mplsInSegmentTa ble]
> > > 
> > > 
> > > As a provider of management solutions... We'd "prefer"
> > > to have a simple solution but we MUST have a working solution. 
> > > Although the proposed change makes the instancing a bit 
> > more complex, 
> > > the getnext performance of the current mplsXCTable is so 
> > slow that its 
> > > practically unreadable in any reasonably sized network.
> > > 
> > > 	Mike Shevenell
> > > 	Aprisma Management Technologies
> > > 
> > > -----Original Message-----
> > > From: Thomas D. Nadeau [mailto:[email-masked]]
> > > Sent: Wednesday, June 11, 2003 10:35 AM
> > > To: 'Choudhury, Sanjaya'; [email-masked]
> > > Subject: RE: prequeal to WG lat call om the LSR mib 
> > > module[mplsInSegmentTable]
> > > 
> > > > -----Original Message-----
> > > > From: [email-masked] [mailto:[email-masked]] On Behalf
> > > > 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]
> > > > 
> > > > 
> > > > 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...>
> > > > 
> > > > stuff deleted...
> > > 
> > > 	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).
> > > more stuff deleted..
> > > 
> > > 	--Tom
> > > 
> > > 
> > 
> 
>

---

From: "Thomas D. Nadeau" <[email-masked]>
Date: Wed, 18 Jun 2003 10:16:37 -0400

> Sent: Monday, June 16, 2003 7:10 PM
> To: [email-masked]

	Yes, this solution will indeed work with
the proposed indexing changes.
 
> 		a vendor implements the new mplsInSegmentIndex]

	But this is at the crux of the problem. There have
been several NMS vendors that have chimed in already
stating that they are okay with the new proposed
indexing of a single octet string. They have stated
that they don't care about "natural" indexing; rather,
they want fast, efficient retrieval from this MIB because
it can potentially contain hundreds of thousands of entries.
 	     
> > best O(N), and is more likely O(N^2) on distributed implementations.
> > 
	
	The NMS can do this using the new indexing, but
it has been my experience that this is rarely done if
ever due to the size of the LSR MIB and the rate
at which entries change therein.  It is more likely
that the NMS will want to display entries from the
MIB for trouble-shooting based on information
it gathered elsewhere (i.e.: PPPVPN-MPLS-VPN MIB)
and then use this to "walk" the LSP, or look at
counters for the IGP label.
 
> 	    (ifIndex,label) index is perfect ??

	No. It is not something that I have seen
as being anything adventageous in the 4 years I have
had an implementation. As a matter of fact, it has
been a problem because it makes returning the
entire table less efficient due to the fact that
the implementation has to a) do more work to return
entries in this way, and b) returns redundant entries.
For example, when using LDP DoD unordered, you often
distribute the same labels to all LDP neighbors
for the same FEC. This means that you can receive
traffic from that FEC's label on any per-platform
interface. Thus, the MIB needs to return numIfs * numLabels
things, while it really should just return ifIndex=0 *
numLabels things. 

> 	  o In distributed cases, it may be O(n) * num-app

	Yup, and this is significant on a box that
contains LDP labels for each of the internet routes,
plus VPNv4, VPNv6, TE, and PWE3 labels. In this case
N = 2-300,000. You must surely consider O(N) the
to be be pretty big. This is why I
am advocating a longer index so that appliations
are free to return items in O(1). O(1) is SIGNIFICANTLY
faster than O(N) time for real LSR implementations!

> 	more efficiently by the choice of indexing??

	Because if each query is O(1), then your
mib walk will take O(1) * O(N). If your MIB
walk takes O(N) * num applications, then
your MIB walks will take you O(N) * O(N) -> O(N^2).
Now remember how big N gets for a large implementation
like mine. Then you will quickly realize why I 
(and the NMS vendors who have chimed in) want
me to return my entires in O(1) time!

	--Tom