Subject: RE: Label Intersection

From: manikantan <[email-masked]>
Date: Wed, 8 Dec 1999 10:05:42 +0530

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.
For example 
Label range advertised by LSR1 - 
MinVPI - Xmin = 20
Max VPI - Xmax = 100
Min VCI - Ymin   = 35
Max VCI - Ymax = 140.

Label range advertised by LS21 - 
MinVPI - Amin = 30
Max VPI - Amax = 120
Min VCI - Bmin   = 50
Max VCI -Bmax = 160.

Intersection is calculated as - Intersected MinVpi =  MAX of ( Xmin, Amin) = MAX of ( 20, 30) = 30
Intersection is calculated as - Intersected MaxVpi =  MIN of ( Xmax, Amax) = MIN of ( 100,120) = 100
Intersection is calculated as - Intersected MinVci =  MAX of ( Ymin, Bmin) = MAX of (35, 50) = 50
Intersection is calculated as - Intersected MaxVci =  MIN of ( Ymax, Bmax) = MIN of (140, 160) = 140

This looks fine, However on what basis the intersection to be done is not clear.

I mean in the example sent earlier, three set of label ranges has been specified for each LSR and in the same the order in which
the label range is specified in the first LSR set it has been intersected with the order specified in the second LSR Set.

However If a one on one label range intersection is done in the order specified, and if the order is changed the answers will be  
entirely different.

If the specified example is re-arranged as follows.
LSR1 has following label range : ( This I have not modified)
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
         175  - 220          130   - 250
         230  - 450          475   - 525
          30   - 120          50    - 160

If on the above same lines ( one on one comparison if the intersection is performed)
the results will be like 

         Min VPI Max VPI      Min VCI Max VCI
          175   - 100          130    - 140  <- Erroneous as MIN VPI is greater than MAX VPI
         230 - 250         475   - 200      < - Erroneous as MINVCI is greater than MAX VPI
         250  - 120          400   - 160   <- Erroneous as both MIN VPI and MIN VCI are greater
                                                        than the corresponding MAX VPI and MAX VCI.

does this mean the intersection is NULL? 
Hence the computation done as above does not hold.

Secondly if LSR1 has given three label ranges as below
Min VPI Max VPI      Min VCI Max VCI
      20   - 100          35    - 140
    150  - 250          160   - 200
    250  - 350          400   - 500

and LSR2 has given a single label range as below
Min VPI Max VPI      Min VCI Max VCI
      50   - 300          50    - 450

How should the label intersection be done? 

                                                                                           MIN VPI MAX VPI - MIN VCI MAX VCI
Intersection of label range  1 of LSR1 with that of LSR2 will yield 50,          100 -       50,          140  
Intersection of label range  2 of LSR1 with that of LSR2 will yield 150,         250 -      160,          200        
Intersection of label range  3 of LSR1 with that of LSR2 will yield 250,          300 -       400,          450
From what intersected label range should LSR 1 assign labels? What should be considered by LSR2?

The method to do intersection is not clear?

Can you provide some more help?

Awaiting your response

thanks in advance
with best regards
mani
 
/*-------------------------------------------------------------------*/
S.Manikantan
Future Software Private Limited
480-481, Anna salai, Nandanam,
Chennai, Tamil Nadu, 600 035,
India.
Phone	: +91-44-4330550
Fax	: +91-44-4344157.
Email	: [email-masked]
http://www.futsoft.com
/*--------------------------------------------------------------------*/

-----Original Message-----
From:	Eric Gray [SMTP:[email-masked]]
Sent:	Tuesday, December 07, 1999 9:45 PM
To:	[email-masked]
Cc:	[email-masked]'; [email-masked]'; [email-masked]'; [email-masked]'; [email-masked]'
Subject:	Re: Label Intersection

Kishore,

	Certainly.  When an ATM LSR indicates
that a range of VPI and VCI values are okay,
all other VPI/VCI values are not okay.

	So the intersection function must be
applied to both VPI and VCI seperately - just
as you have done.

You wrote:
> 
> Hi,
>      I have one doubt regarding calculation of Intersection of  ATM label range components   .
>     Draft ldp-06 says  as follows :
>         " A receiving LSR MUST calculate the intersection between the
>          received range and its own supported label range.  The
>          intersection is the range in which the LSR may allocate and accept labels. "
> My doubt is how to calculate Intersection of ATM Label range.
> For example,
>        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
> 
> 
> LSR1 is received  LSR2 label range.
> LSR1 will found Intersection of Label range as follows  :
> 
>             Min VPI Max VPI      Min VCI Max VCI
>               30   - 100          50    - 140
>               175  - 220          160   - 200
>               230  - 350          475   - 500
>          Is the Intersection of label range like above  ?
> 
> Regards,
> Kishore
> 
> T M Kishore,
> Senior Software Engineer,
> HDF, Future Software Pvt Ltd,
> 480 - 481, Anna Salai, Nandanam,
> Chennai - 600 035
> India.
> Phone : +91-44-4330550 Ext.412

-- 
Eric Gray		Email: mailto:[email-masked]
Voice: (978)960-6162	Fax: (978)960-1101
In Person:MV 21-2E33	1600 Osgood St., N. Andover, MA 01845

---

From: Eric Gray <[email-masked]>
Date: Wed, 08 Dec 1999 06:33:52 -0500

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.

>             Min VPI Max VPI      Min VCI Max VCI 

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

---

From: Eric Gray <[email-masked]>
Date: Wed, 08 Dec 1999 08:57:41 -0500

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