Subject: Re: Label Intersection

From: Bob Thomas <[email-masked]>
Date: Wed, 08 Dec 1999 13:44:13 -0500

I'd like to try to clarify the intent of the LDP spec on this issue.

The intent is that each label range component in the ATM Session
Parameters TLV represents a rectangle in VPI-VCI space, where the
corner of a given rectange is specified by the 4 points:

   (min VPI, min VCI),
   (min VPI, max VCI),
   (max VPI, min VCI),
   (max VPI, max VCI)

To determine the legal set of labels for a given LDP session an LSR
computes the intersection of the rectangles it supports with the
rectangles its peer proposes.

Thanks,
Bob

> Folks,
> 
> 	In reviewing this discussion, and re-reading applicable
> sections of the current MPLS-ATM and LDP specifications, I found
> that it is important to realize that there is some ambiguity in
> the specifications which must be cleared up in LDP (I believe).
> 
> 	First, comparisons made below are between the advertised
> range of the peer LSR and the supported range of the local LSR
> - not (as may have been implied in this discussion) between the
> ranges advertised by each LSR.  
> 
> 	Consequently, the ranges available for use at each LSR,
> may not end up being the same.
> 
> 	Sorry if this caused any confusion.
> 
> 	Second, however, is that there is another issue: are
> VPI/VCI ranges treated separately (as has been suggested) or
> are they treated as a concatenated value?  I believe that the
> same argument applies - i.e. - it is difficult to unmake the 
> assumption that they are concatenated values if this is not 
> the case (it can be done, however - see below).  Hence - when 
> the range proposed by an LSR is meant to be inclusive of all 
> values in the range of concatenated VPI/VCI values, this must 
> be explicitly indicated as well.
> 
> 	This is messy when multiple VPI values are given in
> a single VPI/VCI range.  Given the range 20-100/35-140 - if
> intended to be inclusive - would require explicitly listing
> the following ranges:
> 
> 	20-20/35-<max VCI>
> 	21-99/<min VCI>-<max VCI>
> 	100-100/<min VCI>-140
> 
> One advantage of requiring this to be explicitly stated in
> LDP parameter negotiation is that this eliminates the need
> for the local LSR to determine the values <min VCI> and
> <max VCI> from information that may or may not be available
> to the LDP protocol engine about the peer LSR.  Another, as
> implied above, is that it is very much harder/uglier to try
> to communicate the opposite intent if this requirement is
> not clearly stated.  That is, the list to explicitly state
> that VPI/VCIs are not treated as a concatenated quantity -
> for the above example - is:
> 
> 	20-20/35-140
> 	21-21/35-140
> 	...
> 	100-100/35-140
> 
> Given the choice between these two beauties, I would prefer
> that LDP clearly states that the VPI and VCI are treated as
> separate (un-concatenated) quantities in determining the
> intersection range(s).
> 
> --
> Eric Gray
> 
> Earlier, I wrote:
> > 
> > Mani and Naren,
> > 
> >         I think we're making this sound harder than it
> > is.
> > 
> >         The intersection of numerical ranges is determined
> > very simply as by taking the maximum of the minimums and
> > the minimum of the maximums as the minimum and maximum of
> > the intersection.  In other words:
> > 
> >         MINi = MAX(MIN1, MIN2[, ...])
> >         MAXi = MIN(MAX1, MAX2[, ...])
> > 
> > As long as MINi is less than or equal to MAXi, a non-empty
> > intersection exists.
> > 
> >         If you realize that there are probably reasons why
> > an LSR says "I can use these VPI values and these VCI values"
> > then it is apparent that, when two or more are determining a
> > common set, the intersection function must be applied to the
> > VPI and VCI separately.
> > 
> >         When there are multiple ranges given, this becomes
> > somewhat more complicated.  The over all intersection is
> > the union of the individual intersections.  In the ATM case,
> > there is the additional complication of _agreeing_ on what
> > it means to have separate intersection calculations (for VPI
> > and VCI) in each individual intersection.  Can the results
> > of an intersection of VPIs be used in cross-product fashion
> > with the results of intersections of _all_ VCIs, or does it
> > only apply to the intersection of the VCIs with which it is
> > part of a VPI/VCI pair.  The latter is approach is simpler
> > and more intuitive - and is therefore more likely correct.
> > However, the ranges (as VPI/VCI pairs) are compared for
> > determination of any intersection in cross-product fashion.
> > 
> >         In other words, when either LSR proposes multiple
> > ranges, each LSR must determine if there is a non-empty
> > intersection between each of the ranges it proposes and
> > any of the ranges proposed to it.
> > 
> >         In the example given by Kishore:
> > 
> > >        LSR1 has following label range :
> > >             Min VPI Max VPI      Min VCI Max VCI
> > >               20   - 100          35    - 140
> > >               150  - 250          160   - 200
> > >               250  - 350          400   - 500
> > >
> > >        LSR 2 has following Label Range  :
> > >
> > >             Min VPI Max VPI      Min VCI Max VCI
> > >               30   - 120          50    - 160
> > >               175  - 220          130   - 250
> > >               230  - 450          475   - 525
> > >
> > 
> > You make the following comparisons
> > 
> > I(20-100/35-140, 30-120/50-160) = 30-100/50-140
> > I(20-100/35-140, 175-220/130-250) = <empty>/130-140   (not usable)
> > I(20-100/35-140, 230-450/475-525) = <empty>/<empty>   (not usable)
> > 
> > I(150-250/160-200, 30-120/50-160) = <empty>/160-160   (not usable)
> > I(150-250/160-200, 175-220/130-250) = 175-220/160-200
> > I(150-250/160-200, 230-450/475-525) = 230-250/<empty> (not usable)
> > 
> > I(250-350/400-500, 30-120/50-160) = <empty>/<empty>   (not usable)
> > I(250-350/400-500, 175-220/130-250) = <empty>/<empty> (not usable)
> > I(250-350/400-500, 230-450/475-525) = 250-350/475-500
> > 
> > The three remaining ranges, in this example are as Kishore
> > suggested in his original question.
> > 
> > Assuming that any existing intersection of VCI values may
> > be used with any existing intersection of VPI values implies
> > that the original list of ranges had this relationship as
> > well.  In other words, from the example, if the first LSR
> > was able to use all possible VPI/VCI values then can it
> > interpret the ranges advertised by LSR 2 to actually include
> > 30-120/130-250 and 175-220/50-160?  The answer must be NO!
> > The reason for this is that there is no way to unmake this
> > assumption when it is not true.
> > 
> > Hence, if an LSR wants to advertise that several ranges of
> > VCIs may be used with any of several ranges of VPIs, then
> > the advertised ranges must explicitly include each such
> > combination.
> > 
> > --
> > Eric Gray
> > 
> > manikantan wrote:
> > >
> > > Hello Eric
> > >
> > > >From the Example Kishore has indicated it is not clear as how to determine the label intersection.
> > >
> > > The algorithm or assumption that had been adopted in his calculation is as follows.
> > > ...

---

From: Eric Gray <[email-masked]>
Date: Wed, 08 Dec 1999 13:51:23 -0500

Folks,

	This should put to bed any remaining confusion
on this issue.  I suggest we move on to other issues,
because:

o	Bob's explanation is logical and very clear

o	On thinking about it, most people will agree
	it's the only reasonable interpretation of the 
	current specification and

o	Bob's position as the editor of the draft and
	a driving force in Cisco's implementation of
	LDP makes his interpretation pragmatically
	significant :-)

--
Eric Gray