Subject: Re: PQC and QOSPF

From: Yao-Min Chen <[email-masked]>
Date: Fri, 24 Jul 1998 13:52:52 -0700

Subject: Re: PQC and QOSPF
From: Yao-Min Chen <[email-masked]>
To: Masataka Ohta <[email-masked]>
Date: Fri, 24 Jul 1998 13:00:08 -0700

Ohta san, 

Masataka Ohta wrote:
> 
> Yao-Min;
> 
> > these messages follow the direction of a flow,
> > only downstream routers receive resource reservation
> > info of upstream routers but not the other way
> > around.  The problem with this is that upstream
> 
> Yes, it makes the QOS routing a little more stable and is not a problem.

Could you elaborate on the stability part? 

As for "not a problem" part, 
I hope I understand the protocol correctly but it 
seems there could be a potential problem.  Consider 
the following example: a bandwidth of b1 is reserved
for a multicast flow on the path S--A--B--C--R1. 
For simplicity, assume all links on the path have 
the same available (residual) bandwidth b2 (<b1)
after committing b1 bandwidth to the flow.  This 
info is flooded to all routers using some form of 
extension to link state advertisements (LSAs).  
(In QOSPF, the extension is called RES-LSA while
 in PQC, QoSLSAP messages) 

Using PQC, router A considers link (B,C) 
has only available bandwidth b2.  On the 
other hand, router C can 
"correct" the link bandwidth to b1+b2 as far 
as computing the route for the flow is concerned. 
Now suppose a new receiver R2 would like to join 
the multicast tree and links (A,R2) and (C,R2)
both exist (see Figure below).

S--A--B--C--R1
    \   / 
     \ /
      R2

Since router A thinks the available bandwidth b2 
of (B,C) is insufficient (recall b2<b1), it 
adds branch (A,R2) for the new multicast tree 
but router C may compute (C,R2) to reach  
the new receiver.  So we have an inconsistent 
calculation of the new multicast tree. 

My main concern is that a very fundamental 
premise of link state routing algorithm is 
that all routers see the same network status
(link states); or one could say all routers
should have consistent link state databases.  
PQC, by only notifying downstream routers the 
reservation status of upstream routers, seems
to break this premise.   
  
> 
> > I guess a simple fix would be to also
> > piggyback resource reservation on the
> > RESV messages.  Or maybe it is not
> > necessary because receiving successful
> > RSVP Resv message by a router would
> > imply the resource reservation info
> > on downstream links?
> 
> Yes, as the QoS routing is hop-by-hop, which is necessary for multicast
> and RESV merge, a router do not have to know the result of
> previous routing. The router can not, in case of multicast and RESV merge.

Yes indeed. 

> 
> Note that, to assist dynamic rerouting, it reduces rerouting delay, if
> upstream, NOT DOWNSTREAM, link state of the current path is carried
> back in RESV, which is an extension to PQC I'm thinking about now.

Are you saying that instead of using the _next_ refresh PATH 
message to propagate the resource reservation info, we use 
_current_ RESV so that we can reduce information propagation
delay? 

> 
> Note also that, with QoS routing, PATH must follow the result of
> QoS routing, if any, of RESV, because only RESV has the QoS information
> which is necessary for QoS routing.
> 
>                                         Masataka Ohta

Thanks,
-- 
Yao-Min Chen, Fujitsu Labs of America, [email-masked]  
595 Lawrence Expressway, Sunnyvale, CA 94086-3922
Phone: +1 408 530-4513 Fax: +1 408 530-4515

---

From: Masataka Ohta <[email-masked]>
Date: Sat, 25 Jul 98 16:27:19 JST

Yao-Min;

> Could you elaborate on the stability part? 

Underestimation of down stream resource makes the current path
(up stream) preffered.

> for a multicast flow on the path S--A--B--C--R1. 

OK. But note that you can't scalably propagate resource information
about all the receivers of the multicast.

> both exist (see Figure below).

OK.

> calculation of the new multicast tree. 

Wrong.

As the title of the paper says, routing is hop by hop.

Neither A nor C are volunteers to calculate the tree. They just
route RESV requests from down stream to upstream.

So, first, R2 joins a group with best effort. Then, PATH will
come and R2 can now QoS route RESV to A or C and a branch is added.

That's all.

> reservation status of upstream routers, seems

Yes, it is consistent.

The consistency requirement of any hop-by-hop routing, including but not
limited to LS one, is that the best path computed at some hop should
remain best at the next hop.

As I said "stable", this lack of information keep making the
best path best.

Also, the property of any flooding based algorithm, including
but not limited to that of *OSPF, is that all the perticipants
are deliverd the same data (though with some delay), which
is also the case with PQC.

> _current_ RESV so that we can reduce information propagation

No, it is a little more complicated problem.

In your previous figure, let's assume R1 is the only receiver. Then,
if A-C goes down and A-R2-C is the only available path from S
to R1, QoS routing at R2 should be able to know the corrected
link state of S-A, which can be suplied by RESV from C copied
from old PQC info in PATH.

							Masataka Ohta

---

From: Yao-Min CHEN <[email-masked]>
Date: Tue, 28 Jul 1998 01:31:34 -0700

> come and R2 can now QoS route RESV to A or C and a branch is added.

Interesting ... what you proposed is:
- resource reservation info is PUSHed to downstream nodes through 
  PATH messages; then
- QoS path is PULLed by downstream nodes through RESV messages
  (after each node computes its previous hop on this path)

>From another perspective, the proposed scheme separates
1) reachability calculation, and 2) path selection.  A best
effort routing protocol is used only to maintain reachability.
The above PUSH-PULL model is the one actually used for QoS 
path selection.

This model seems also suitable for "traffic engineering."  
Congestion info can be pushed to downstream nodes who then
pull an uncongested path.

Yao-Min