Subject: New Internet Draft (resend)

From: Steven Berson <[email-masked]>
Date: Thu, 27 Mar 1997 11:24:38 -0800 (PST)

We have submitted the following entitled ``A `Classy'
Approach to Aggregation for Integrated Services' as
an Internet Draft.

Steven Berson
Subramaniam Vincent

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

Internet Draft                                                 S. Berson
Expiration: September 1997                                           ISI
File: draft-berson-classy-approach-00.txt                     S. Vincent
                                                                     ISI

      A ``Classy'' Approach to Aggregation for Integrated Services

                             March 26, 1997

Status of Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   To learn the current status of any Internet-Draft, please check the
   linebreak "1id-abstracts.txt" listing contained in the Internet-
   Drafts Shadow Directories on ds.internic.net (US East Coast),
   nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au
   (Pacific Rim).

Abstract

   The current Integrated Services (IS) architecture has a fundamental
   scaling problem in that per flow state is maintained everywhere.  Our
   approach is to use aggregation as a technique to address this
   problem.  There is a wide spectrum of approaches towards aggregation
   of IS state, with different tradeoffs in the amount of state
   required.  This draft describes one promising approach to aggregating
   IS state within defined regions of a network.  Service classes are
   configured on all of the routers in a region.  At the edges of the
   region, routers keep detailed IS state and map packets into the
   configured traffic service classes.  In the interior of this region,
   routers need keep only a bounded amount of IS state.

Table of Contents

Berson, Vincent        Expiration: September 1997               [Page 1]


Internet Draft            "Classy" Aggregation                March 1997

1. Introduction

   In order to deploy Integrated Services (IS) in the Internet,
   resources are needed in the routers to keep state and to process
   packets.  As currently defined [1], this state is on a per session
   basis, where a session is a unicast destination or a multicast group.
   Thus, widespread use of IS would mean a large amount of state at
   routers in the core of the internet.  This large amount of state and
   related processing could overwhelm routers, so aggregation models
   that do not require per-session state need to be explored.  This memo
   describes a particular approach to reducing this IS state.

   Several types of per-session state are used with integrated services.
   First, there is scheduling state that consists of the different
   traffic service queues for packet forwarding.  Second, there is
   packet classifier state.  Classifier state is used to assign each
   arriving packet to a packet scheduling queue for forwarding.  Third,
   there is the state for the setup protocol, e.g. state carried in RSVP
   PATH and RESV messages.  Finally, current multicast routing
   algorithms also store state, either per source and session (e.g.
   DVMRP, PIM-DM) or per session shared-tree (e.g. CBT, PIM-SM).  While
   approaches to aggregation of routing state are similar to aggregation
   of RSVP state, they are beyond the scope of this note.

   Any aggregation scheme entails some tradeoffs.  Keeping full
   integrated services state at all routers allows the resources
   dedicated to the flow of packets from each admitted session to be
   isolated from the resources for packets from all other sessions.
   This isolation means that resources reserved for one session, if
   needed, will be used only on the reserving session.  The disadvantage
   of doing aggregation is the lesser degree of flow isolation,
   since with aggregation many flows would share the same traffic
   service class.  The benefits of additional flow isolation achievable
   from keeping full IS state is unknown.

2. Framework

   This draft proposes an approach to reducing the amount of IS state
   based on configured traffic service classes within aggregating
   regions.  Configuring a fixed number of traffic service classes
   bounds the amount of scheduler state.  Establishing aggregating
   regions (described below) and storing full IS state only at the edges
   reduces the classifier state and setup protocol state.

   We make several assumptions:

   1.   We assume that an explicitly definable region (e.g. one or more

Berson, Vincent        Expiration: September 1997               [Page 2]


Internet Draft            "Classy" Aggregation                March 1997

        contiguous autonomous systems), called an "aggregating region",
        will aggregate and will implement supporting mechanisms at its
        boundary points.

   2.   We assume that the choice to aggregate and the mechanism used to
        do so is an intra-domain issue, not an inter-domain issue and
        therefore there can be variability across regions so long as at
        the boundaries routers continue to pass along adequate messages
        to support RSVP upstream and downstream.

   3.   We assume current multicast and unicast routing within the
        aggregating region; but with no other enhancements.

3. Approach

   In our approach, traffic service classes are defined at all routers
   in an aggregating region.  While the exact form of these traffic
   service classes is the subject of continuing research, the scheduling
   algorithms used by these service classes could include features such
   as priority queueing and/or weighted fair queueing.  Each traffic
   service class is subject to admission control and traffic policing
   (additional subjects of continuing research) but only at the ingress
   to the region.  Note that no changes to packet forwarding are needed
   in the interior of the aggregating region.  Similarly, no RSVP
   processing is needed in the interior of the region.  When an RSVP
   reservation message arrives at an ingress to the region (from an
   egress), and that reservation passes admission control, then packets
   from that flow are assigned to a traffic service class.  Data packets
   belonging to a traffic class are "tagged" on entry to the aggregating
   region with some identifier indicating which class of service the
   packets should receive.  This identifier can consist of some bits in
   the packet header (e.g. type of service bits) or the packet could be
   encapsulated.  The tag (or encapsulation) encodes the traffic service
   class that this packet will receive across the aggregating region.
   Tagging or encapsulating each packet minimizes the classifier state
   in the interior of the aggregating region.

   In summary our approach provides for reduction of packet scheduler
   state, packet classifier state, and setup protocol (e.g. RSVP) state
   in the following ways.  A bounded amount of packet scheduler state at
   all routers in an aggregating region is achieved by using
   preconfigured traffic service classes.  A bounded amount of packet
   classifier state at all interior routers in the aggregating region is
   accomplished by tagging or encapsulating each packet with its traffic
   service class.  No setup protocol state at interior routers is
   achieved by doing admission control and policing only at the edges of
   the aggregating region.

Berson, Vincent        Expiration: September 1997               [Page 3]


Internet Draft            "Classy" Aggregation                March 1997

4. Open Issues

   Aggregation provides opportunities for increased multiplexing and
   resource usage efficiency, but it also brings up several challenges
   in admission control and policing.  First there is an issue of how
   many service classes are to be used and of how to configure the
   service classes on the routers.  Second, there is an issue of how and
   when to assign flows to the service classes, i.e. aggregate admission
   control.  Finally, there is the issue of how and when to police an
   aggregate reservation.  Good solutions to these problems will provide
   integrated services across aggregating regions with greatly reduced
   state requirements.

5. Acknowledgements

   This draft is the result of discussions with many people particularly
   Bob Braden, Deborah Estrin, and Daniel Zappala.

REFERENCES

[1] Braden, R., Zhang, L., Berson, S., Herzog, S., and Jamin, S.,
    "Resource ReSerVation Protocol (RSVP) -- Version 1 Functional
    Specification," Internet Draft, November 1996.

[2] Floyd, S., and Jacobson, V., "Link-sharing and Resource Management
    Models for Packet Networks," IEEE/ACM Transactions on Networking,
    Vol. 3 No. 4, pp. 365-386, August 1995.

[3] Rampal, S., "Flow Grouping for Reducing Reservation Requirements for
    Guaranteed Delay Service," Internet Draft, December 1996.

Security Considerations

   Security considerations have not been addressed in this draft.

Author's Address

Berson, Vincent        Expiration: September 1997               [Page 4]


Internet Draft            "Classy" Aggregation                March 1997

   Steven Berson
   USC Information Sciences Institute
   4676 Admiralty Way
   Marina del Rey, CA 90292

   Phone: +1 310 822 1511
   EMail: [email-masked]

   Subramaniam Vincent
   USC Information Sciences Institute
   4676 Admiralty Way
   Marina del Rey, CA 90292

   Phone: +1 310 822 1511
   EMail: [email-masked]

Berson, Vincent        Expiration: September 1997               [Page 5]

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 28 Mar 97 18:33:06 JST

Dear Steve and Subramaniam;

>    routers need keep only a bounded amount of IS state.

It is not a scalability problem that flows consume resource
on routers proportional to the number of flows.

Thus, it is OK that flows need some constant amount of state
on each router.

So, what is the point of this kind of aggregation, even though
flows still consume resource on routers proportional to the
number of unaggregated flows.

Is it your point to have constant amount of improvement?

If so, it seems to me that, if you severly restrict available
service classes, you can reduce the amount of state a lot
without introducing aggregation.

Note that you somewhat increased the complexity of routing
as the virtual link needs its own LSA.

							Masataka Ohta

---

From: Steven Berson <[email-masked]>
Date: Fri, 28 Mar 1997 13:50:09 -0800 (PST)

> as the virtual link needs its own LSA.

Ohta,

If N is the number of flows in an aggregating region, then our
scheme reduces an order O(N) problem to and O(1) problem.  That
seems like a goal worth pursuing.

Your suggestion about restricting the available service classes
is already part of our scheme.

I do not understand your comment about increasing the complexity
of routing.  Could you please elaborate?

Thanks,
Steve

---

From: Subramaniam Vincent <[email-masked]>
Date: Fri, 28 Mar 1997 17:09:08 -0800 (PST)

> > number of unaggregated flows.

This is definitely not what has been suggested. The idea has been to
reduce the proportionality/dependency from the number of unaggregated
flows, to a more scalable unit of resource consumption. A restricted
number of classes of  service, is a direction we chose to explore, within
the framework of the intserv model.

---

From: Masataka Ohta <[email-masked]>
Date: Sat, 29 Mar 97 12:01:47 JST

Steve;

> > number of unaggregated flows.

You disagree with the point above?

When the complexity is O(N)+O(N)+O(N)+..., it is just a constant
amount of improvement to reduce the first O(N) to O(1).

> scheme reduces an order O(N) problem to and O(1) problem.

Hmmm, you still don't understand what *RESOURCE* means...

No. Not at all. The O(N) flows still consume O(N) bandwidth resource.

Moreover, between the end points of the virtual path, O(N) RSVP
packets of O(1) size or O(1) RSVP packets of O(N) size (which
does not scale and is fragmented to be O(N) packets of O(1)
size, anyway) must be exchanged.

This is yet another O(N) factor between (but not necessarily along
the virtual path between) the end points.

If you think the amount of RSVP packets is small and does not
matter, we hadn't needed receiver initiated join from the beginning.

> of routing.  Could you please elaborate?

If you want to make use of the virtual link, you must advertise
it, especially if you want QoS routing, which means additional
overhead of new LSA.

This is not a so serious problem if virtual links are not used
so widely. But if you have R routers almost fully connected,
the number of LSA is O(R**2).

Finally, the virtual pathes badly interact with multicast.

If the virtual path between R0 and R1 and between R0 and R2
shares several initial physical links, duplicated data is
sent twice on the same physical links.

		R0----------RB-----------R1
                             \
                              \
                               ----------R2

You may be able to introduce very complex multicast routing
architecture to somehow distinguish virtual and physical pathes
and let R0 use virtual path only to the first branch point of RB.
          
But, then, please don't assume that R0 and the multicast branch
point (RB) always have a virtual link without introducing O(R**2)
LSA overhead. Without LSA advertisement, there can be no special
complex multicast routing protocol to make use of the virtual
links.

> is already part of our scheme.

That's already more than enough.

						Masataka Ohta

---

From: Subramaniam Vincent <[email-masked]>
Date: Sat, 29 Mar 1997 11:14:42 -0800 (PST)

I have tagged this mail with a more relevant subject, in the hope it will 
cause a larger multitude to participate. ;->

> amount of improvement to reduce the first O(N) to O(1).

No. I sense a disconnect in this discussion. This approach is about 
reduction of IS state in routers, using configured classes of traffic. The 
amount of IS state reduction within such an aggregating region is 
proportional to the number of service classes configured in the routers 
in the region. This is where the IS state savings come from. We are not 
making any assumptions about constant/variable amount of state reduction. 
I interpret the O(N) to O(1) abstraction  to loosely depict the shift from 
maintaining per flow state to per-class or per-aggregate state.

Secondly, N (say, the number of flows requiring a particular kind of 
service), will depend on the traffic flow through the aggregating 
region. Different routers will have differing aggregate/class sizes. The 
bandwidth configurations per class, and traffic models used will 
restrict the number of flows that can be *admitted* into a class to some 
known maximum. The  challenge however, is to do aggregate traffic servicing, 
while not hurting the utility a well-behaving flow expects from the network.

> size, anyway) must be exchanged.

Is this the disconnect I see ? We are trying to deal with reduction of 
IS state IN THE ROUTERS, and not with reduction of bandwidth consumed by 
the user flows ON THE LINKS. That is a different issue. The reservation 
and path messages are not aggregated. They just pass through the  
aggregating region, and continue installing and maintaining *classical* 
reservations outside the region. 

An aggregating region is LIKE one big Non-RSVP hop in the classical sense;
but the difference is that it must adhere to the intserv framework. (again , 
this is the challenge, and therein all the open issues come from).

Vince

---

From: Masataka Ohta <[email-masked]>
Date: Mon, 31 Mar 97 10:38:14 JST

Vincent;

> flows, to a more scalable unit of resource consumption.

You shouldn't call just an improvement on constant factor "scalable".

Note that O(N)+O(N)=O(1)+O(N)=O(N).

> A restricted

It may be OK, though may not be so meaningful, to restrict the number
of classes of service only to enjoy the constant factor of improvement,
as long as you don't call it "scalable", make protocol too much complex,
create new scalability issues.

							Masataka Ohta

---

From: Masataka Ohta <[email-masked]>
Date: Mon, 31 Mar 97 11:15:41 JST

Vince;

> No.

Do you disagree the plain mathematical fact that O(N)+O(N)=O(1)+O(N)?

> I sense a disconnect in this discussion.

Yes.

The disconnection is in your formalization of the problem.

The problem is O(N)+O(N) and but your disconnected goal is to
reduce the first O(N) to O(1).

> This approach is about 
> reduction of IS state in routers, using configured classes of traffic.

But, the goal is the reduction of complexity in routers.

With N flows, O(N) bandwidth is consumed regardless of whatever
aggregation you might perform.

Your disconnection of the goal that the problem is only in "IS state"
created a meaningless goal.

Moreover, as the price paied will be mostly proportional to the
bandwidth and distance (which is mostly proportional to the number
of hops, unless you assume tree like topology with points of
inscalable congestion), there is no point in reducing the
complexity less than O(N).

Thus, the goal is the reduction of complexity in routers is to reduce
it to O(N) and is already reached.

> Is this the disconnect I see ?

Yes, that's the disconnection you created.

> We are trying to deal with reduction of 
> the user flows ON THE LINKS.

We must deal with recource comsumption on routers, including resource
on router interface ports.

Don't say you solve scalability problem, when you make O(N)+O(N)
to O(1)+O(N).

> That is a different issue. The reservation 
> and path messages are not aggregated.

Thus, the overall complexity of resource consumption on routers
between the end points of virtual path (not necessaryly along
the virtual path) is still O(N).

I admit the constant factor, this time, is not so large and is
not so much a problem, as long as N is small, say, 100.

> An aggregating region is LIKE one big Non-RSVP hop in the classical sense;

Wrong. It is LIKE one big *RSVP* hop.

> this is the challenge, and therein all the open issues come from).

It is a meaningless challenge. Don't do that, as you have newly
created scalability issues

	> > the number of LSA is O(R**2).

	Note that, with O(R**2) LSA advertisement on O(R) virtual
	links, the load on routers is O(R**3).

						Masataka Ohta