Re: [mpls] draft-atlas-mpls-te-express-path-02 (was MPLS-RT review of ...)

[Alia Atlas <[e-mail]>]

Hi Xiaohu,

No, there is no retreating.  I think you're describing something based on a depth-first-search that's cost aware??? I don't know but it's not based on a normal SPF.  The pseudo-code I gave is correct.  

Here's the brief example -  I mean an SPF where links aren't explored if they result in a path that is too long.

Step 1 CSPF:   A has cost 0, delay 0   - explore A's links
          B.cost = 1  B.delay= 1  insert B into the fibheap ordered by cost
          C.cost = 10  C.delay = 1   insert C into the fibheap ordered by cost

Step 2 CSPF:  remove first node from fibheap - it is B  - explore B's links
          Via B->D would give D.delay to be 11 - over bound so don't save 
          Via B->E would give E.delay to be 11 - over bound so don't save

Step 3 CSPF: remove first node from fibheap  - it is C - explore C's links
            Via C->F would give F.delay=2 -under bound so save
                 F.cost = 11   F.delay = 2  insert F into fibheap

Step 4 CSPF:  remove first node from fibheap - it is F
         CSPF was from A to F and F is now minimized so terminate.

Alia                   

-----Original Message-----
From: Xuxiaohu [mailto:[e-mail]] 
Sent: Thursday, July 11, 2013 10:52 PM
To: Alia Atlas; [e-mail]; MPLS WG Mailing List; draft-atlas-mpls-te-express-path authors; The Great and Mighty MPLS Co-Chairs
Subject: 答复: [mpls] draft-atlas-mpls-te-express-path-02 (was MPLS-RT review of ...)

Hi Alia,

Let me give an example as illustrated below:

A--------(Metric:1; Delay:1)-------B---(Metric:1; Delay:10)---D-----------F
|                        |                           / |
|                        +---(Metric:2; Delay:10)---E--------/  |
|                                                     |
|                                                     |
+-------(Metric:10; Delay:1)------C--------(Metric:1; Delay 
+1)--------------+

Assume A wants to find an optimal path to F with delay upper bound of 10. In step 1, A selects B among all of its adjacent routers as the next_router since its distance to other adjacent routers (i.e., C) is larger than that to B. in step 2, B finds that neither of its adjacent routers (i.e., D and E) could be selected as next_router since the latency of the either path (i.e., A->B->D and A->B->E) is already beyond the e2e delay bound. At a result, in step 3, A has to give up B and then explore its other adjacent routers. Is that the heuristic algorithm you meant? If so, it would be better to describe the step 3 (i.e., a retreat step) as well in your pseudo-code while mentioning that retreat step may be performed multiple times back and forth.

Best regards,
Xiaohu
   
> -----邮件原件-----
> 发件人: Alia Atlas [mailto:[e-mail]]
> 发送时间: 2013年7月10日 2:13
> 收件人: Xuxiaohu; [e-mail]; MPLS WG Mailing List; 
> draft-atlas-mpls-te-express-path authors; The Great and Mighty MPLS 
> Co-Chairs
> 主题: RE: [mpls] draft-atlas-mpls-te-express-path-02 (was MPLS-RT review 
> of ...)
> 
> Can you clarify why you think constraining the links explored based 
> upon a latency isn't a practical approach?  It is still O(n log n) - 
> granted, it's a heuristic and may not find a path.
> 
> Alia
> 
> -----Original Message-----
> From: Xuxiaohu [mailto:[e-mail]]
> Sent: Tuesday, April 23, 2013 9:44 PM
> To: [e-mail]; MPLS WG Mailing List; 
> draft-atlas-mpls-te-express-path authors; The Great and Mighty MPLS 
> Co-Chairs
> Subject: re: [mpls] draft-atlas-mpls-te-express-path-02 (was MPLS-RT 
> review of ...)
> 
> >     s/While it has been possible to compute a CSPF/It is possible to
> >     compute a CSPF/
> >     s/Instead of this approach to minimize path latency, an/An
> >     alternative to this approach to minimize path latency is an
> >     approach to place a upper bound on path latency.  An/
> >     Note: both approaches are valid.
> 
> I think the alternative approach (i.e., to compute a CSPF path based 
> on the TE metric while placing a upper bound on the path latency) is 
> not a practical approach due to computationally complexity.
> 
> Best regards,
> Xiaohu
> 
>