Subject: PQC in draft-ietf-qosr-framework-06.txt

From: FUJIKAWA Kenji <[email-masked]>
Date: Fri, 17 Jul 1998 11:53:09 +0900

Dear QoSR Framework Authors;

draft-ietf-qosr-framework-06.txt says in Page 6:

----
Path
QoS Computation (PQC) method, proposed in [GOA97], propagates bandwidth
allocation information in RSVP PATH messages. A router receiving the PATH
message gets an indication of the resource allocation only on those links in
the path to itself from the source.  Allocation for the same flow on other
remote branches of the multicast tree is not available. Thus, the PQC method
may not be sufficient to find feasible QoS-accommodating paths to all
receivers.
----

PQC is the abbreviation of "Path QoS Collection." (^^;
Please correct this.

> Thus, the PQC method
> may not be sufficient to find feasible QoS-accommodating paths to all
> receivers.

If you are saying
"the PQC method may not be sufficient for a router 
 to find feasible QoS-accommodating paths to all
 receivers,"
this is true, 
since there is no need at all for each route 
(even on the path) to find such paths.

Otherwise, not ture.
The PQC method is sufficient to find feasible QoS-accommodating 
paths to all receivers, 
cooperating with RSVP and a QoS link state advertisement protocol.
All the routers on a network are not needed to know all
information.

Again in page 6:
----
The best granularity is found when routing is based on individual flows
but this incurs a tremendous cost in terms of the routing state.  Each QoS
flow can be routed separately between any source and destination. PQC
[GOA97] 
and alternate path routing [ZES97], are examples of solutions which operate
at the flow level.
----

The routing besed on individual flows does not incur a 
tremendous cost in terms of the routing state in case of PQC.
The fact that each router only calculates routing
for flows flowing through the router should be pointed out.

Sincerely Yours,
---------------------------------------------------------------
FUJIKAWA, Kenji @ Grad. Sch. of Informatics, Kyoto Univ., Japan
              WWW http://camino.kuis.kyoto-u.ac.jp/index-e.html
                        TEL +81 75-753-5387 FAX +81 75-751-0482
                             e-mail [email-masked]
                             e-mail [email-masked]

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 17 Jul 98 12:54:23 JST

Fujikawa san;

> (even on the path) to find such paths.

Right. It is not only necessary but also harmful.

A router MUST NOT have multicast state information, the amount of
which is proportional to the number of multicast receivers.

> cooperating with RSVP and a QoS link state advertisement protocol.

Of course.

> but this incurs a tremendous cost in terms of the routing state.

That is tremendous only with poor protocols such as QOSPF which
floods state of all the flows over all the routers.

> Each QoS

The cost for state holding with PQC on a router is merely proportional
to the number of flows which is actually running over the router.

The cost is equivalent to the cost to assure QoS. That is, the cost
is already paid and is not a problem.

The more serious mistake of the current draft is that it ignore the
cost of aggregation and seggregation.

It is simply easy to aggregate flows by ignoring all the important
differences.

However, the ignorance makes latter seggregation impossible.

Finally, aggregation of routing states of multicasted flows is proven
to be impossible that persueing aggregation is not meaningful.

							Masataka Ohta

---

From: Yao-Min Chen <[email-masked]>
Date: Wed, 22 Jul 1998 18:40:13 -0700

A criticism on QOSPF made in the PQC paper
(http://www.isoc.org/inet97/proceedings/F4/F4_2.HTM) 
was the scaling issue with the Resource Reservation
Advertisements (RRAs).  RRA, being per-flow 
information, is flooded thoughput an OSPF area. 

The approach proposed in PQC is to have the resource 
reservation information for a flow only propagated 
to routers that are on the path of the flow.   
The propagation mechanism uses RSVP.  

Is there a compelling reason in the design of 
QOSPF to have RRAs flooded throughout an area?  
 
-- 
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: Zhaohui Zhang <[email-masked]>
Date: Thu, 23 Jul 1998 08:38:27 -0400

Yao-Min,

I have not read the paper yet, so my response is based your email only.

> The propagation mechanism uses RSVP.  

Flooding RRAs anywhere does cause the scaling problem, but from day one
we proposed an alleviation - use Explicit Routing.

With ER, reservation information is sent only to the "first hop"
routers - even better than sending to routers on the path of the flow.

We also tried to put it into RSVP so that only routers on the path would
get the info, but RSVP folks did not think that was a good idea, so we
had to give up.

> QOSPF to have RRAs flooded throughout an area?  

The resource information is needed to deal with "step over your own
shadow" problem. Any router involved in the calculation of the path for
a flow needs to know the reservation info for the flow - I believe you
share the same view.

Flooding them anywhere does not scale and is not necessary, yet it is easy
to understand and simple to implement, so we did not put ER up front but
put it in the appendix instead.

Thanks.

Jeffrey

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 24 Jul 98 3:24:43 JST

Jeffry;

> I have not read the paper yet, so my response is based your email only.

I think you have.

> we proposed an alleviation - use Explicit Routing.

Nope. ER does not work with large scale multicast.

Note also that multicast routing table can not be aggregated,
which makes inter-/intra- domain separation of QoSR
meaningless.

That is, you can't say you can ignore scalability issues of QOSPF
by flow aggregation.

> get the info, but RSVP folks did not think that was a good idea, so we

It, of course, is a bad idea to use RSVP to let multicast members
know about all the pathes to all the other members.

						Masataka Ohta

---

From: Yao-Min Chen <[email-masked]>
Date: Thu, 23 Jul 1998 15:52:33 -0700

Jeffrey, 

Thank you for the prompt and authoritative reply from 
the QOSPF point of view. 

Summarizing from your response, RRA flooding is needed
to avoid "stepping over your own shadow" but such 
flooding indeed leads to a scaling problem.  Possible 
approaches to alleviate the problem:
- Let RRA info be propagated only to routers on the data 
  path, possibly using RSVP.  But RSVP camp did not like 
  the idea.  
- Use ER, so that the info is only needed at the first 
  hop routers.  

Using RSVP to carry routing related info does appear
to violate the separation between reservation and 
routing.  Now, if we use ER, still there needs to be a 
way to propagate the resource reservation info to the 
first-hop (source) routers.  For this purpose, 
EROSPF (Explicit Routing OSPF) proposed in in 
draft-zhang-qospf uses RRAs but limits the 
flooding destination only to the first-hop 
routers (but these RRAs have to be propagated 
through intermediate routers anyway).  The 
complexity analysis in the draft seems to indicate 
the same message complexity as PQC.  Let me know 
if this comparison is incorrect. Thanks. 

Yao-Min 

Zhaohui Zhang wrote:
> > information, is flooded throughout an OSPF area.
> >

---

From: Yao-Min Chen <[email-masked]>
Date: Thu, 23 Jul 1998 17:57:12 -0700

Ohta-san, 

I checked the PQC paper again and have a question 
about its use of RSVP Path messages.  The resource 
reservation info (equivalent of qospf RRAs) is 
piggybacked in the Path messages.  However, since 
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
and downstream routers see different network
status.  For example, if S-R1-R2-R3-D is the 
path taken by a flow, R1 tells R2  
resource reservation info on link (R1,R2), 
and R2 tells R3 the resource reservation 
info on links (R1,R2) and (R2,R3).
However, R2 and R3 do not communicate their
resource reservation info 
(on links (R2,R3) and (R3,D)) to R1.  

Using the terminilogy of the paper,
R1 can "correct" the "generic" link state
of link (R1,R2);  R2 can correct 
generic link states of (R1,R2) and 
(R2,R3); and R3 can correct 
the generic link states of (R1,R2), 
(R2,R3) and (R3,D).  So different
routers see inconsistent link states.  
(Let me know if I miss anything in this 
reasoning.) 

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?

Regards,

---

From: FUJIKAWA Kenji <[email-masked]>
Date: Fri, 24 Jul 1998 10:51:17 +0900

Yao-Min Chen;

From: Yao-Min Chen <[email-masked]>
Subject: Re: PQC and QOSPF
Date: Thu, 23 Jul 1998 15:52:33 -0700

> routing.  

Why do you think the separation is preferable?
QoS routing won't be achieved without reservation,
since QoS parameters are not informed.
QoS routing is tightly associated with reservation 
from the beginning.
---------------------------------------------------------------
FUJIKAWA, Kenji @ Grad. Sch. of Informatics, Kyoto Univ., Japan
              WWW http://camino.kuis.kyoto-u.ac.jp/index-e.html
                        TEL +81 75-753-5387 FAX +81 75-751-0482
                             e-mail [email-masked]
                             e-mail [email-masked]

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 24 Jul 98 15:21:57 JST

Yao-Min;

> around.  The problem with this is that upstream

Yes, it makes the QOS routing a little more stable and is not a problem.

> imply the resource reservation info 

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.

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.

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

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 24 Jul 98 15:51:20 JST

Fujikawa san;

> QoS routing is tightly associated with reservation 

Yes. Packets, such as PATH, which does not carry information on
required QoS, can not be QoS routed.

The bottom line is that we can't have much freedom on QoS routing, if we have
to do it scalably and preserve the semantics of RSVP.

							Masataka Ohta

---

From: Zhaohui Zhang <[email-masked]>
Date: Fri, 24 Jul 1998 09:13:25 -0400

Yao-Min,

Yes that's my understanding.

Jeffrey

---

From: Jon Crowcroft <[email-masked]>
Date: Fri, 24 Jul 1998 18:33:00 +0100

>>to violate the separation between reservation and 

well if you do qos (load related) routing, then you HAVE to update the
route state somehow - there's 3-ish ways
1/ add load information to link state or other router-router update  -
this means that route state is out of date w.r.t the actual traffic -
if traffic is increasing, this may be ok since it will damp
call acceptance, but if its decreasing it may block unnecessarily

2/ use reservation/signaling to update route state (and therefore ifg
you want to do alternate path routing, you have to propogate the
reservation messages down more paths than the subsequent flow itself)
but at least you are potentially up to date - for high rates of
signaling, this may cause a lot of load on the rsvp handling modules
(but on the other hand at busy times, whether high call rate or high
flow rate, maybe you want to put dynamic call gapping into rsvp
anyhow....or do some sort of distributed congestion control - i.e.
slow start rsvp path and resvs....)

3/ have a third party distriburted entity that uses traffic
measurement and is neither signaling protocol
nor route protocol dependent

the latter approach seems to me to be the best option sicne we can
then evolve routing signaling and admission control (and charging) all
seperately...

 >>> > Phone: +1 408 530-4513 Fax: +1 408 530-4515

 cheers

   jon

---

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

Fujikawa-san,

> QoS routing is tightly associated with reservation

Jon Crowcroft answered very well in his message.  
Please refer to his complete message but I'd 
like to quote the following portion which points
out an alternative to "QoS routing is 
tightly associated with reservation."

> then evolve routing signaling and admission control (and charging) all

Although still not quite sure about the traffic measurement 
part (have yet to investigate what such a technique can do), 
I pretty much agree that we should "evolve routing, signaling, 
and admission control (and charging) all separately."

---

From: Masataka Ohta <[email-masked]>
Date: Sat, 25 Jul 98 3:14:11 JST

Jon;

> route state somehow - there's 3-ish ways

3/ is like reimplementing TCP over UDP.

And, it is always the case that the implementation is poor.

> then evolve routing signaling and admission control (and charging) all

The protocol to do it distributed way is called a routing protocol.

Of course, all the distributed protocol is subject to delay.

							Masataka Ohta

---

From: Kenneth CARLBERG <[email-masked]>
Date: Sat, 25 Jul 1998 11:39:58 +0200

> and admission control (and charging) all separately."

one aspect to keep in mind in the separation model is that time and
resources are needed to coordinate the separate activities.  if routing
schema (A) is dependent on signaling schema (B), then (probably) care
might have to be taken for potential race conditions.

-ken

---

From: Masataka Ohta <[email-masked]>
Date: Mon, 27 Jul 98 17:29:12 JST

Ken;

> might have to be taken for potential race conditions.

The very basic problem of QoS routing of stepping on one's own
shadow is the dependency loop between the routing schema and
signaling schema.

To break the loop, counter-dependency is the MUST.

An example of poor schema is an ER schema which places the routing
schema in receivers.

							Masataka Ohta

---

From: Kenneth CARLBERG <[email-masked]>
Date: Mon, 27 Jul 1998 10:35:38 +0200

ohta-san,

> To break the loop, counter-dependency is the MUST.

that is sort of dependent on the design and realization (implementation)
of the architecture -- in some cases yes/probably, in some no.

> An example of poor schema is an ER schema which places the routing

an interesting opinion.  if i may be allowed to recommend some reading,
two papers come to mind:

   http://www.acm.org/sigcomm/ccr/archive/ccr-toc/ccr-toc-97.html 
     -- sometimes refered to as YAM, and the precursor to...

   http://www.acm.org/sigcomm/sigcomm98/tp/abs_12.html 
     -- also known as QoSMIC (a presentation was given at the last IETF)

cheers,

-ken

---

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

Ken,

Good point. 

If dependency were one-way then we would probably be okay 
but what's troublesome is the cross-dependency between 
RSVP and path computation.  To break the dependency it seems one
could use a measurement based appraoch as mentioned by Jon.
Alternatively, it is proposed in PQC to take QoS path computation
away from routing to merge with RSVP. 

Yao-Min