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

[Xuxiaohu <[e-mail]>]

Oh, yes, you are right. Sorry for my confusion.

Best regards,
Xiaohu

> -----邮件原件-----
> 发件人: Alia Atlas [mailto:[e-mail]]
> 发送时间: 2013年7月12日 13:05
> 收件人: 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 ...)
> 
> 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
> >
> >