Subject: RE: Label Intersection

From: Naren <[email-masked]>
Date: Wed, 8 Dec 1999 12:14:32 +0530

Hi ,

The first algorithm works only for the one range. 

For the second example (For more than one range) should be different.

One algorithm to get the intersection of more than one range is as follows:

Let us assume the ranges of respective LSR's:

LSR1 has following label range : ( This I have not modified)
Min VPI Max VPI      Min VCI Max VCI
      20   - 100          35    - 140             ===> A1
    150  - 250          160   - 200	         ===>A2	
    250  - 350          400   - 500	         ===>A3	
 
LSR 2 has following Label Range  :

     Min VPI Max VPI      Min VCI Max VCI
         175  - 220          130   - 250       ===>B1
         230  - 450          475   - 525       ===> B2
          30   - 120          50    - 160        ===>B3

Prepare the intersection table
----------------------------------------
					Min Vpi 	Max Vpi 	Miv Vci		Max Vci
 Intersection of  (A1 & B1)  =          -		-		130		140
			A1 & B2  = 	  -                      -		-		-
			A1 & B3  =	  30		100		50		140
			
			A2 & B1  = 	-		-		130		200
			A2 & B2  =	230		250		-		-
			A2 & B3  = 	-		-		-		-

			A3 & B1 =	-		-		-		-
			A3 & B2 = 	250		350		475		500
			A3 & B3 = 	-		-		-		-
=========================================================================

Step 2: Now Take the ranges which have entries both in the VPI's and VCI's in the table

So the intersection rages are :    (VPI=30 - 100, VCI= 50-140) & (VPI=250-350, VCI= 475-500)

Hop this algorithm works .....

Thanks and Regards
Naren

****************************************************************
B Narendra Reddy, SSE,
Future S/W Pvt. Ltd.,
480-481 Mount Road,
Nandanam, Chennai - 600 035
Ph: 91-44-4330550 (Ext. 412)
E mail : [email-masked] &
            [email-masked]
****************************************************************

-----Original Message-----
From:	manikantan [SMTP:[email-masked]]
Sent:	Wednesday, December 08, 1999 10:06 AM
To:	'Eric Gray'; [email-masked]
Cc:	[email-masked]'; [email-masked]'; [email-masked]'; [email-masked]'; [email-masked]'
Subject:	RE: Label Intersection
Importance:	High

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: manikantan <[email-masked]>
Date: Wed, 8 Dec 1999 18:25:58 +0530

Hello Eric

Thank you very much for your reply.

I have a doubt, can you please clarify.
The doubt is with regard to the practical deployment of the MPLS.

My understanding is, When MPLS/LDP  is deployed and the interface type is ATM, 
the links are point-to-point in nature. As the Labels in the ATM are VPI/VCI, there
must be sufficient number of VCs allocated/supported when we specify a label range.
Now when the LSRs exchange messages and perform the label 
intersection, a part of their label range will not be out of the
intersection space and will not be allocated as labels.
(i.e.) those set of VCs will not be used.

Wont this be a overhead?

To avoid this overhead, should the "Managers" of the LSRs
agree upon and configure label spaces such that they
intersect 100%. Can you please give your comments.

Thanks in advance.
with best regards
mani

-----Original Message-----
From:	Eric Gray [SMTP:[email-masked]]
Sent:	Wednesday, December 08, 1999 5:04 PM
To:	manikantan
Cc:	T M Kishore; Bob Thomas; Loa Andersson; Paul Doolan; Nancy Feldman; MPLS Mail List; Andre Fredette
Subject:	Re: Label Intersection

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:
> ... << File: ewgray.vcf >>

---

From: [email-masked]
Date: Thu, 9 Dec 1999 12:12:36 +0800

Mani,

All implementation issues, right ?

When you say "those set of VCs will not be used", hmmm.... I think it
sounds more evil than it needs to be.   I suppose it is fair to assume that
the implementation contains  some entity (which you may call label space
manager or partition manager or perhaps logical port manager) that allows
partitioning of the label space among different "applications"  that share
the link (one of which is MPLS).  A correct implementation could (should?)
return the unused portion of the VC range to this entity.  The hope is that
some other application might be able to make use of this portion.  That's
probably good enough.

As regards possible misconfiguration -- if the intersection is less than
100% it will be useful to notify the operator with an informative message,
but I think that's about all there is to it.

-- Ajith

|   Ajith Narayanan
|   IBM Emerging Technology Centre
|   [email-masked]   Tel: (65) 320-1939     Fax: (65) 224-5260
|   IBM Singapore Pte Ltd, IBM Towers, 80 Anson Rd, Singapore 079907
--

manikantan <[email-masked]> on 12/08/99 08:55:58 PM

To:   "[email-masked]'" <[email-masked]>, manikantan
      <[email-masked]>
cc:   T M Kishore <[email-masked]>, Bob Thomas
      <[email-masked]>, Loa Andersson
      <[email-masked]>, Paul Doolan
      <[email-masked]>, Nancy Feldman <[email-masked]>, Andre
      Fredette <[email-masked]>, "'narenr'"
      <[email-masked]>, "[email-masked]'" <[email-masked]>
      (bcc: Ajith Narayanan/Singapore/IBM)
Subject:  RE: Label Intersection

Hello Eric

My understanding is, When MPLS/LDP  is deployed and the interface type is
ATM,
the links are point-to-point in nature. As the Labels in the ATM are
VPI/VCI, there
must be sufficient number of VCs allocated/supported when we specify a
label range.
Now when the LSRs exchange messages and perform the label
intersection, a part of their label range will not be out of the
intersection space and will not be allocated as labels.
(i.e.) those set of VCs will not be used.

Wont this be a overhead?

Thanks in advance.
with best regards
mani

-----Original Message-----
From:     Eric Gray [SMTP:[email-masked]]
Sent:     Wednesday, December 08, 1999 5:04 PM
To:  manikantan
Cc:  T M Kishore; Bob Thomas; Loa Andersson; Paul Doolan; Nancy Feldman;
MPLS Mail List; Andre Fredette
Subject:  Re: Label Intersection

Mani and Naren,

--
Eric Gray