Subject: QOS Routing

From: [email-masked] (Bala Rajagopalan)
Date: Thu, 4 Apr 1996 13:46:42 -0500

I would like to solicit some responses to two questions
with regard to QOS routing. Just to start off, I'm giving some
possible answers. 

1. Is there a need for QOS routing in the internet?

Let us consider this issue in the intradomain routing context first.  
Some argue that a conventional routing scheme (e.g, 
OSPF), together with proper network engineering obviates the need for 
QOS routing. This may be the case, but at what cost? Economic network 
engineering depends on the use of an efficient routing scheme. For 
instance, with a traditional IP routing algorithm, a single fixed path 
is selected for all traffic between a pair 
of nodes (when the topology is stable). To assure the desired QOS, 
this path must be engineered to accommodate the peak traffic demand 
between the node pair. This results in the inefficient use of resources, 
since there may be other, underutilized paths between the same node pair. 
On the other hand, a QOS routing algorithm would allow the network 
capacity to be engineered efficiently, by virtue of its ability to take 
into account the current network state in making routing decisions. This 
is one of the reasons for the development of state-dependent routing 
schemes for long distance phone networks (see [1, 2]). 
Recent work on optimal ATM network design also illustrates the role of 
state-dependent routing schemes in the efficient use of resources [3]. 
In addition to efficient resource usage, a QOS routing 
scheme permits graceful performance degradation after 
adverse topological changes or traffic overloads [4]. 
For these reasons, it can be argued that QOS routing should be 
an essential component of the IP integrated services architecture.

2. Assuming that an IP QOS routing architecture is needed, what are the 
requirements for it? 

Given the organization of the internet, the nature of the traffic, and
the QOS classes being considered, some requirements on the routing 
architecture could be: 

- the ability to dynamically determine the QOS achievable on differnent types
of links, including over NBMA networks 

- the ability to dynamically determine paths satisfying multiple 
constraints (e.g., bandwidth and delay)

- the ability to route short-lived data flows with minimal overhead

- the ability to prioritize flows, and to permit high priority flows to 
be established with precedence over lower priority flows

- the ability to utilize network resources efficiently, both by
minimizing routing overheads and by routing data flows intelligently,
using load spreading, global admission control techniques [5] and the like

- the ability to support link sharing

- the ability to scale to large numbers of nodes and links, and

- separation between intradomain and interdomain routing, 
especially the ability to introduce constraints on routing information 
flow at the boundary between two organizations.

Clearly, many technical issues arise in considering these issues
(especially interdomain multipoint routing). In addition,
there is a question as to how QOS routing can
adjust to RSVP's style of doing things (e.g., receiver
initiated reservations, flow aggregation,
existence of a control path before the data flow begins, etc.)
 
Regards,

Bala Rajagopalan
([email-masked])

-------------------------------------------

REFERENCES

1. G. R. Ash, R. H. Caldwell, and R. P. Murray, "Design and Optimization of 
Networks with Dynamic Routing," The Bell System Technical Journal, 
pp. 1787-1820, October, 1981.

2. G. R. Ash, J. S. Chen, A. E. Frey and B. D. Huang, "Real-Time Network 
Routing in a Dynamic Class-of-Service Network," Proceedings of ITC 13, 1992.

3. D. Mitra, J. Morrison, and K. G. Ramakrishnan, "ATM Network Design and 
Optimization: A Multirate Loss Network Framework," Proceedings of IEEE 
INFOCOM `96, 1996.

4. J. M. Akinpelu, "The Overload Performance of Engineered Networks with 
Non-Hierarchical Routing," AT&T Technical Journal, Vol. 63, pp. 1261-1281, 
1984.

5. H. Ahmadi, J. Chen, and R. Guerin, "Dynamic Routing and Call Control 
in High-Speed Integrated Networks," Proceedings of ITC-13, pp. 397-403, 1992.

---

From: Jon Crowcroft <[email-masked]>
Date: Sun, 07 Apr 1996 14:34:32 +0100

>with regard to QOS routing. 
 
 >1. Is there a need for QOS routing in the internet?

yes - the diffeence between modern traffic patterns and traditional
POTS ones is that the rate of change of the traffic matrix is so fast
that we cannot rely on classical approaches to placing the switches
and links and dimensioning the net - we need adaptive, distributed
multi-path routing....

 >2. Assuming that an IP QOS routing architecture is needed, what are the 
 
i believe that (as i said in my other response) multipath routing
should
i) first select a path set based on link capacity and effective spare
capacity
ii) select aparticular path based on propogation delay constraint
iii) iff reservation/guarantee needed, pin the path (and possibly mark
some of the alternates above as possible fall back paths)

this is do-able within the current Internet routing framework with
modest extensions...
 
 >adjust to RSVP's style of doing things (e.g., receiver

add that there are interesting problems with mobile and reservations
that stress the routing infrastructure (and mobile+multicast, and
mobile+multicast+secure and mobile+multicast+no denial of service, etc
etc etc)

however, i think theat our current framework (IP style routing with
multi-path extensions - e,g ,incremental pre-calaculation of alternate
paths), is a good approach...

 jon

---

From: Yakov Rekhter <[email-masked]>
Date: Sun, 07 Apr 96 12:40:50 PDT

Bala,

> QOS routing. This may be the case, but at what co
t? Economic network 
> into account the current network state in making routing decisions. 

It seems that you argue in favor of load sensitive routing, as such
routing would allow (at least in theory) more efficient resource utilization
without increasing the risk of network overload (and congestion).
So, to paraphrase your question, is there a need for load sensitive
routing in the Internet.

Yakov.

---

From: Jon Crowcroft <[email-masked]>
Date: Mon, 08 Apr 1996 14:01:17 +0100

>So, to paraphrase your question, is there a need for load sensitive
 
Yakov,

iff we have usage based billing, there is a related issue

 - there are policies at the moment due to
the settlement/biulling free nature of the internet, that lead to
absurd imbalances in capacity and traffic - for example, we have the
scandinavian 34Mbps link going thru london to get to the US, and the
UK link (11.5 or 18.5 mbps depending on the date you read this),
totally overloaded going the same way-ish - we can manauallly
application level route traffic (e.g .web/email traffic ) via the
scandinavian sites and get wonderful performance  ... proving that
there is spare capacity - but we cannot buy into it

if there was usage based billing, then we might be able to buy
caapcity from them - but to make the routing work, we'd need an
interaction between paying=>routing=>reservation....(policies
will remain irrational and annoying...unavoidably, but perhaps less
so)

i think that it is likely that if the net is largely highly
redundently connected mesh which is preferablte for current IP 
router performance limits and for ISPs to continue to exist in such
numbers, then load sensitive routing will be very important....

if the global grid were made out of terrabit switches and was managed
as a single entity, then no, we wouldn't need load
sensitive routing...

 jon

---

From: Curtis Villamizar <[email-masked]>
Date: Mon, 08 Apr 1996 16:10:57 -0400

In message <[email-masked]>, Bala Rajagopalan writes
> an essential component of the IP integrated services architecture.

According to this argument the current unicast Internet should not
exist since it would have to be engineered in a manner that was not
cost effective.

What you are really talking about is load sensitive routing.  If you
can do load sensitive route and keep it stable, more power to you.
You can't claim that the Internet can't exist and operate cost
effectively without load sensitive routing because it already does
exist and operate cost effectively.  Providers already engineer to
keep circuit load above peak (a little behind at this point).
Introducing QoS sensitive traffic will not change that.  As long as
a sufficient portion of the traffic is elastic, operating somewhat
over capacity in parts of the Internet will not be a problem.

I don't disagree that load sensitive routing is desirable.  I disagree
with any claim that it is essential.  Simplicity has proven more
desirable so far.

Curtis

REFERENCES

1.  First hand experience with the NSFNET backbone and a major
commercial Internet backbone after that.  :-)

---

From: [email-masked] (Bala Rajagopalan)
Date: Tue, 9 Apr 1996 11:39:57 -0400

>    From: Curtis Villamizar <[email-masked]>
>
effectively
>    without load sensitive routing because it already does exist and
operate
>    cost effectively.
>
>Yes, but for what kinds of applications? As long as all we want to do is
>elastic stuff like FTP, etc, maybe the current architecture (hotted up
with
>some fair queueing to punish bad guys) will suffice. So, saying "it
already
>works" is not as telling a point, when you think about *new*
applications.
>
>    As long as a sufficient portion of the traffic is elastic, operating
>    somewhat over capacity in parts of the Internet will not be a
problem.
>
>Sure, I don't think anyone disagrees with that. In fact, elastic
applications
>are great for making it possible to have less over-provisioning than in a
net
>with only fixed-resource-usage applications! :-)
>
>	Noel
>
>

I just would like to add this to Noel's statement: of course, the
internet "works" by definition, even when I can't reach another
machine. The issue is, how do we guarantee some level of performance
that the users will pay for, and the providers can selectively charge for?
Even as we debate about the need for QOS mechanisms,
complaints are mounting about poor performance. Over provisioning,
at least currently, does not seem to be a cost-effective solution.

>Providers already engineer to
>Introducing QoS sensitive traffic will not change that.

To the contrary, I hear that many providers have horrendously
over-subscribed their networks.

Bala Rajagopalan
([email-masked])