Subject: [IPTEL] Path Aggregation

From: "William Parton" <[email-masked]>
Date: Wed, 10 Oct 2001 18:18:22 +0100

I'm trying to get to grips with Path aggregation and, being unfamiliar with
BGP, I'd like to check my understanding with someone knowledgeable in this
area (I couldn't find any discussion in the IPTEL mailing list).

The TRIP spec gives an example path aggregation algorithm in 5.4.4.3:

An example algorithm to aggregate two paths works as follows: 
(A)- Identify the ITADs (as defined in Section 5.4.1) within each path
attribute that are in the same relative order within both path attributes.
Two ITADs, X and Y, are said to be in the same order if either X precedes Y
in both paths, or if Y precedes X in both paths.
(B)- The aggregated path consists of ITADs identified in (a) in exactly the
same order as they appear in the paths to be aggregated. If two consecutive
ITADs identified in (a) do not immediately follow each other in both of the
paths to be aggregated, then the intervening ITADs (ITADs that are between
the two consecutive ITADs that are the same) in both attributes are combined
into an AP_SET path segment that consists of the intervening ITADs from both
paths; this segment is then placed in between the two consecutive ITADs
identified in (a) of the aggregated attribute. If two consecutive ITADs
identified in (a) immediately follow each other in one attribute, but do not
follow in another, then the intervening ITADs of the latter are combined
into an AP_SET path segment; this segment is then placed in between the two
consecutive ITADs identified in (a) of the aggregated path. 
If as a result of the above procedure a given ITAD number appears more than
once within the aggregated path, all, but the last instance (rightmost
occurrence) of that ITAD number should be removed from the aggregated path. 

Running this algorithm over two example Paths:
Pa = AP_SEQ[x1, x2, x3] AP_SET[x4, x5] AP_SEQ[x6, x7, x8]
Pb = AP_SET[x1, x2] AP_SEQ[x4, x7]

From my reading of step (A) the AP_SET or AP_SEQUENCE associated with an
ITAD ID is ignored, it is the relative order that matters (correct?). If
this is true can I not legitimately rewrite AP_SET[x4, x5] as AP_SET[x5, x4]
and perhaps gain some benefit in step (B).

This produces four ITAD IDs with the same relative order in both Pa and Pb
=> x1, x2, x4, x7

The resultant aggregated Path from step (B) then becomes
Pagg = AP_SEQ[x1, x2] AP_SET[x3] AP_SEQ[x4] AP_SET[x5, x6] AP_SEQ[x7]
AP_SET[x8]

- Am I interpreting the algorithm correctly? 
- Are the singleton sets and sequences that result correct? 
- Is the allocation of AP_SET and AP_SEQ in Pagg correct? 
- Is a singleton sequence meaningless and could (should?) the sequence 
AP_SET[x3] AP_SEQ[x4] AP_SET[x5, x6] AP_SEQ[x7] AP_SET[x8]
be replaced by AP_SET[x3, x4, x5, x6, x7, x8] without any loss of
information?

Will

---

From: Manjunath Bangalore <[email-masked]>
Date: Tue, 16 Oct 2001 23:49:36 -0700

Hi William,

    Please refer inline -

William Parton wrote:

>
>
> I'm trying to get to grips with Path aggregation and, being unfamiliar
> with BGP, I'd like to check my understanding with someone
> knowledgeable in this area (I couldn't find any discussion in the
> IPTEL mailing list).
>
> attribute that are in the same relative order within both path
> attributes. Two ITADs, X and Y, are said to be in the same order if
> either X precedes Y in both paths, or if Y precedes X in both paths.
>
> (B)- The aggregated path consists of ITADs identified in (a) in
> exactly the same order as they appear in the paths to be aggregated.
> If two consecutive ITADs identified in (a) do not immediately follow
> each other in both of the paths to be aggregated, then the intervening
> ITADs (ITADs that are between the two consecutive ITADs that are the
> same) in both attributes are combined into an AP_SET path segment that
> consists of the intervening ITADs from both paths; this segment is
> then placed in between the two consecutive ITADs identified in (a) of
> the aggregated attribute. If two consecutive ITADs identified in (a)
> immediately follow each other in one attribute, but do not follow in
> another, then the intervening ITADs of the latter are combined into an
> AP_SET path segment; this segment is then placed in between the two
> If as a result of the above procedure a given ITAD number appears more
> than once within the aggregated path, all, but the last instance
> (rightmost occurrence) of that ITAD number should be removed from the
> aggregated path.
>

[Manjax] Firstly, the path Pb is inconsistent for the following reason:

     The AP_SET in Pb shouldn't appear at the beginning of the
AdvertisementPath but the neighbor's ITAD from whom the route was learnt
should be at the beginning

So, let us say, I modify the AdvertisementPaths to the following:

Pa = AP_SEQ[x0, x1, x2, x3] AP_SET[x4, x5] AP_SEQ[x6, x7, x8]
Pb = AP_SEQ[x0] AP_SET[x1, x2] AP_SEQ[x4, x7]

>
> From my reading of step (A) the AP_SET or AP_SEQUENCE associated with
> an ITAD ID is ignored, it is the relative order that matters
> (correct?). If this is true can I not legitimately rewrite AP_SET[x4,
> x5] as AP_SET[x5, x4] and perhaps gain some benefit in step (B).
>

[Manjax] I think the type is important, it has to be considered for
correctness. The definition in step (A) refers to section 5.4.1 for
identifying ITADs where definition of an ITAD encompasses the type but I
feel the text matter in step (A) should be made more explicit to point
out consideration of the type

>
> This produces four ITAD IDs with the same relative order in both Pa
> and Pb => x1, x2, x4, x7
>

[Manjax] With that, step (A) gives us:

    x0 x7

> Pagg = AP_SEQ[x1, x2] AP_SET[x3] AP_SEQ[x4] AP_SET[x5, x6] AP_SEQ[x7]

[Manjax] From Step B, we have:

Pagg = AP_SEQ[x0] AP_SET[x1, x2, x3, x4, x5, x6] AP_SEQ[x7] AP_SET[x8]

> - Are the singleton sets and sequences that result correct?

[Manjax]  For singleton path segments, AP_SETs or AP_SEQs are okay

> be replaced by AP_SET[x3, x4, x5, x6, x7, x8] without any loss of

[Manjax]
It is not meaningless, because there is an implicit relative ordering
between
the different path segments; in this case an AP_SET would result in loss
of information

From sec 10.3.4.1,

    An AP_SET implies that the destinations advertised in the UPDATE
    message can be reached through paths that traverse at least some of
    the constituent ITADs.

 The example path AP_SEQ[x4] AP_SET[x5, x6] AP_SEQ[x7] represents two
possible "real" paths : x4, x5, x7 and x4, x6, x7.

 This information would be lost if just an AP_SET was advertised.

--Manjax

> Will

_______________________________________________
IPTEL mailing list
[email-masked]
http://lists.bell-labs.com/mailman/listinfo/iptel