Subject: draft-wang-diff-serv-usd-00.txt

From: Zheng Wang <[email-masked]>
Date: Fri, 21 Nov 1997 16:57:54 -0500

Enclosed please find an I-D for the differentiated services BOF.

Thanks
Zheng
-------------------------

Networking Working Group				   Zheng Wang
Internet Draft				Bell Labs Lucent Technologies
Expiration: May	1998					     Nov 1997

		    User-Share Differentiation (USD)
       Scalable	bandwidth allocation for differentiated	services

Status of this 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. Internet Drafts may be updated, replaced, or	obsoleted by
   other documents at any time.	It is not appropriate to use Internet
   Drafts as reference material	or to cite them	other than as a	"working
   draft" or "work in progress."

   Please check	the 1id-abstracts.txt listing contained	in the
   internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net,
   nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to	learn the
   current status of any Internet Draft.

   Table Of Contents

   1.  Introduction ........................................ 2
   2.  Objective ........................................... 2
   3.  Related Proposals ................................... 3
   4.  User-Share Differentiation (USD)	.................... 4
   4.1.	 Overview .......................................... 5
   4.2.	 Per-User Traffic Isolation ........................ 5
   4.3.	 Flexible Aggregation .............................. 6
   4.4.	 Bottleneck Sharing ................................ 6
   4.5.	 Application Marking ............................... 7
   4.6.	 Implementation	and Deployment ..................... 8
   5.  Standardization Issues .............................. 8
   6.  Acknowledgments ..................................... 9
   7.  References .......................................... 9

Wang			  Expiration: May 1998		        [Page 1]

Internet Draft	       User-Share Differentiation		Nov 1997

1.  Introduction

   In this memo, we present a new differentiated service scheme	called
   "User-Share Differentiation (USD)". The USD scheme is based on the
   principle of	link sharing. The scheme allows	ISPs to	differentiate
   traffic flows on a per-user basis, providing	minimum	bandwidth guar-
   antee and share-based bandwidth sharing. We first look at the objec-
   tives of differentiated services, and the problems with the current
   proposals, then present the details of the USD scheme.  Finally we
   examine the implementation and standardization issues

2.  Objective

   The current Internet	is built on the	best-effort model where	all
   packets are treated as independent datagrams	and are	serviced on a
   FIFO	basis. The best	effort model does not provide any form of traf-
   fic isolation inside	the network and	the sharing of the resources
   essentially depends on how much users ask for.  Therefore the cooper-
   ation of the	end systems (such as TCP congestion control mechanisms)
   is vital to make the	system work.  In today's Internet, however, such
   dependence on the end systems' cooperation is increasingly becoming
   unrealistic.	Inevitably, some people	start to exploit the weakness of
   the current best effort model to gain more resource (e.g., Netscape
   browsers allow users	to open	multiple TCP connections). Another prob-
   lem with the	best effort model is that it is	difficult to make any
   guarantee, either explicit (e.g., x bps bandwidth) or relative (e.g.,
   a service package 5 times better than another package) as all traffic
   is aggregated into a	single flow.

   The problems	with the best effort model have	been long recognized.
   For the last	a couple of years, QoS provision has been one of the
   hottest areas in networking research, and various aspects of	the
   issue have been extensively studied including traffic analysis,
   admission control, resource reservation, scheduling,	QoS routing, and
   operating system support.  The architectures	of various proposed
   solutions differ in details.	 Nevertheless, the underlying model is
   similar. Generally, applications make resource reservation on an
   end-to-end session basis. In	the internet community,	RSVP and INT-
   SERV	are examples of	protocols and service models based on this end-
   to-end approach. However, research and experience have shown	a number
   of difficulties in deploying	end-to-end reservation in the global
   Internet.  The lacking of accounting	support, the high administrative
   overheads, and the complexity of inter-ISP settlement make it diffi-
   cult	for end-to-end reservation to be widely	deployed. There	are also
   scalability concerns	for fine granularity classification and	per-
   session signaling.

Wang			  Expiration: May 1998		        [Page 2]

Internet Draft	       User-Share Differentiation		Nov 1997

   The best effort model and the end-to-end model represent the	two
   extremes of the spectrum. The best effort model does	no traffic iso-
   lation at all whilst	the end-to-end model provides isolation	on the
   finest granularity (an end-to-end session identified	by the 5-tuple).
   The solution	may, therefore,	lie somewhere in between the two
   extremes.  For differentiated services, the general approach	is to
   deal	with the problem of QoS	provision through long-term contract-
   based service allocation rather than	per-session reservation. The key
   to achieve that is to choose	a proper level of granularity for traf-
   fic isolation that satisfies	users' and ISPs' needs,	and is also
   scalable in a global	Internet. We also need a solution that can offer
   immediate help to ISPs, and impose minimum conditions on ISPs' busi-
   ness	models and network infrastructures, yet	is flexible to allow
   further development as the Internet evolves.

3.  Related Proposals

   A number of proposals that have been	put forward for	differentiated
   services fall into two groups: drop priority	based and delay	priority
   based. In this section, we discuss some of the problems with	the
   related proposals.

   Profile-Based Tagging

   The profile-based tagging scheme uses drop priority in conjunction
   with	an admission control mechanism.	In the scheme, a user and its
   ISP agree on	a profile, and the traffic flowing into	the ISP	is
   checked at the entry	points [2]. When the traffic exceeds the pro-
   file, the packets are let through but tagged. When there is conges-
   tion	inside the network, the	routers	start to discard tagged	packets
   first.

   One issue is	how to determine a profile for a user. When a network
   does	not have uniform bandwidth provisioning, profiles are likely to
   be destination-specific. For	example, suppose that an ISP has a link
   to a	neighbor ISP with a capacity 600 Mbps and a link to the	Internet
   backbone with a capacity of 100 Mbps.  If a user is communicating
   with	another	user in	the neighbor ISP, the user can have a rate limit
   of 6	Mbps but only 1	Mbps if	the user's traffic goes	through	the
   backbone access link. In this case, a profile of either 6 Mbps or 1
   Mbps	is not appropriate for the user.  When an ISP have multiple bot-
   tleneck links with different	bandwidth provision, it	is difficult to
   choose a fixed profile for a	user.

   Another problem is to do with reserve traffic, i.e.,	the traffic that
   comes from the server towards the user, as it is the	case in	most
   web-based traffic. With reverse traffic, tagging packets at the

Wang			  Expiration: May 1998		        [Page 3]

Internet Draft	       User-Share Differentiation		Nov 1997

   user-ISP boundary has little	effects.

   The profile-based tagging only provides limited protection against
   mis-behaving	source.	Since profile-based tagging essentially	creates
   two classes:	tagged and un-tagged, the network deals	with the tagged
   packets in a	FIFO fashion. A	misbehaving source can still gain more
   bandwidth by	injecting excessive traffic.  The problem can be aggra-
   vated when the fixed	profiles are significantly over	(or below) the
   level appropriate for the congested links. In such a	case, the major-
   ity of the packets are not tagged (or tagged). Thus the tagging pro-
   vides little	information to enforce differentiation,	and network
   behavior will be close to simple FIFO best effort.

   Delay Priority Differentiation

   In a	delay priority based scheme, users are classified into two or
   more	classes	1, 3]. When the	traffic	enters the network, the	packets
   will	be set with appropriate	delay priority.	Under congestion, the
   packets with	higher priority	are transmitted	prior to the ones with
   lower priority.

   Delay priority schemes represent an extreme form of resource	alloca-
   tion, where lower priority classes suffer all the consequences of
   congestion. Unless the priority traffic only	accounts for a very
   small percentage of the link	capacity, lower	class traffic may expe-
   rience significant deterioration under congestion, and may be com-
   pletely starved from	any bandwidth. In fact,	TCP has	the tendency to
   grab	as much	bandwidth as it	can. Because the congestion is invisible
   to the upper	class, the network will	no longer to provide any conges-
   tion	signal for the upper class traffic. The	TCP windows in upper
   class flows may grow	to take	up all bandwidth and starve the	lower
   class traffic completely.

   Delay priority schemes provide isolation between different classes.
   Within a single class, however, there is no traffic isolation and
   therefore there is no protection against misbehaving	users.	Like the
   profile-based tagging, delay	priority schemes also have problems with
   reverse traffic where setting priority has to be done close to the
   sources rather than the users.

4.  User-Share Differentiation (USD)

   In this section, we present User-Share Differentiation (USD), a scal-
   able	bandwidth allocation scheme for	differentiated services, and
   discuss the key design principles behind the	scheme.

Wang			  Expiration: May 1998		        [Page 4]

Internet Draft	       User-Share Differentiation		Nov 1997

4.1.  Overview

   In USD, we treat the	problem	of service allocation as a form	of
   resource sharing: an	ISP as a pool of bandwidth resources shared by
   multiple users. The sharing of the bandwidth	resource is controlled
   with	two parameters,	user and share.	 A user	is the entity to which
   the resource	is allocated and the share quantifies the amount of
   resource allocated to a user.

   At the time when a user subscribes to its ISP for Internet services,
   the ISP determines the share	for the	user based on what the user has
   asked for or	the package the	user selects.  The USD scheme can guar-
   antee that:

1)   The user will have	a minimum mount	of bandwidth on	all or some of
     the links in the ISP

2)   For the bandwidth over the	minimum	amount,	the user shares	the
     bandwidth with other users	in proportion to its allocated share

For example, suppose that user A and B ask for 2 Mbps and 10 Mbps mini-
mum bandwidth respectively, and	the ISP	allocates share	of 1000	and 5000
to the two users in return. The	USD scheme guarantees that user	A and B
have 2 Mbps and	10 Mbps	minimum	bandwidth, and for bandwidth over the
minimum, the allocation	to user	A and B	follows	the ratio of 1:5.

We now discuss the key design decisions	behind the USD scheme.

4.2.  Per-User Traffic Isolation

   As we discussed early, the objective	of the differentiated services
   is to find a	granularity that meets users' and ISP's	needs and is
   also	scalable. When there is	contention of resources, we must deter-
   mine	a rule for allocating limited resources	to multiple users.  In a
   commercial Internet,	we believe that	the rule has to	be based on the
   contracts between the ISP and its users.

   In USD, we choose "user" as the basic working unit that defines the
   granularity.	A user is the entity with whom the service contract is
   signed, and it can be a dial-up customer, or	one corporate network or
   a group of individual customers or networks.	 In USD, all traffic
   originated from or destined to a user is aggregated into a single
   flow.

   The per-user	granularity within an ISP strikes a good balance between
   aggregation and isolation.  It provides real	traffic	isolation
   between different users yet it does not have	to deal	with individual

Wang			  Expiration: May 1998		        [Page 5]

Internet Draft	       User-Share Differentiation		Nov 1997

   sessions/flows within the per-user aggregated flow. Thus, the alloca-
   tion	can be done at the subscription	time and on a long-term	basis.

   The USD scheme creates a hierarchical management structure.	Inside
   an ISP's network, the traffic which belongs to a user is guaranteed
   by the ISP according	to the user-ISP	contract.  Within its share of
   the bandwidth, the user manages its own sessions/flows and decides
   how the resources should be utilized.

   Per-user traffic isolation provides full protection against mis-
   behaving users. If a	mis-behaving user ignores the congestion signal,
   and continues to send traffic at high rates,	it can only hurt itself.
   It gives a strong incentive for users to deploy intelligent control
   congestion mechanisms and make the best use of its allocated	share of
   bandwidth.

4.3.  Flexible Aggregation

   As the definition of	a user changes when traffic goes across	ISP
   boundaries, the level of traffic aggregation	also changes accord-
   ingly. For example, dial-up customers typically are users of	a retail
   ISP,	and the	retail ISP in turn becomes a user of a backbone	ISP.
   Within the retail ISP, traffic from or to a dial-up user is aggre-
   gated whilst	in the backbone	only the retail	ISP is visible.	Such
   variable level of aggregation ensures a great deal of scalability. In
   general, when packets are close to the source ISP, the sender's allo-
   cation has most influence and when the packets move close to	the des-
   tination, the receiver's allocation becomes more important.

   Incorporating the concept of	user into traffic isolation provides a
   very	flexible tool for ISPs to choose the level of traffic aggrega-
   tion	they want. Note	that a user can	represent one dial-up customer,
   or one corporate network or a group of individual customers or net-
   works.  While the maximum granularity is per	customer, ISPs can
   achieve different levels of aggregation by creating user classes.
   For example,	an ISP may create 3 user classes: premium users, basic
   users and best-effort users.	 The USD scheme	will allow the ISP to
   guarantee bandwidth allocation to the three classes.

4.4.  Bottleneck Sharing

   As we discussed in the previous section, admission control at the
   user-ISP boundaries does not	work very well since a fixed profile can
   not cater for multiple bottlenecks with different sizes. Essentially,
   each	user needs to have multiple profiles for different bottlenecks.
   For this reason, we believe that bandwidth allocation should	be done

Wang			  Expiration: May 1998		        [Page 6]

Internet Draft	       User-Share Differentiation		Nov 1997

   at the bottleneck links instead of the edges. In USD, we use	share-
   based allocation scheme that	works both for minimum bandwidth alloca-
   tion	and proportional bandwidth sharing.

   To allocate bandwidth of a single link to multiple users, we	can
   describe the	allocation with	actual bandwidth or as relative	sharing.
   For example,	suppose	that an	ISP has	4 users	A, B, C	and D, sharing
   an access link of 30	Mbps.  The agreed allocation is	4 Mbps,	6 Mbps,
   8 Mbps and 12 Mbps respectively. This allocation can	be described
   with	the actual bandwidth,  4 Mbps, 6 Mbps, 8 Mbps and 12 Mbps.
   Alternatively, the allocation can also be expressed with relative
   sharing, 2:3:4:6. When the bandwidth	is allocated in	proportion to
   the relative	sharing, the two representation	leads to the same band-
   width allocation.

   However, the	relative sharing representation	has a number of	advan-
   tage.  First	of all,	it can guarantee the same minimum bandwidth
   allocation as an explicit allocation	does. In addition to that, it
   allows the bandwidth	above the minimum to be	shared in proportion to
   the minimum allocation. For example,	suppose	that user A and	B in the
   previous example are	not using their	allocated bandwidth during a
   period.  Now	user C and D can share the extra bandwidth in proportion
   to their relative ratio.  The final allocation to user C and	D
   becomes 12 Mbps and 18 Mbps.	Most importantly, the relative sharing
   representation allows proportional allocation on multiple bottle-
   necks.

   More	importantly, the relative sharing representation works works
   well	with multiple bottlenecks with different bandwidth provision.
   For example,	suppose	the ISP	of the 4 users has another link	with 600
   Mbps	bandwidth.  the	4 users	who have shares	of 2, 3, 4, and	6 will
   have	minimum	guaranteed bandwidth automatically scaled up to	80 Mbps,
   120 Mbps, 160 Mbps and 240 Mbps respectively.

   The relative	sharing	can be viewed as a flexible profile as it scales
   up and down according to the	bandwidth available whilst guaranteeing
   the minimum bandwidth.  In practice,	the unit of share can be defined
   as certain bandwidth	so that	the share for a	user can be easily
   derived from	the minimum bandwidth allocated. For example, if we
   define the unit of share is 1 Kbps, a user with 4 Mbps minimum band-
   width has a share of	4000.

4.5.  Application Marking

   As we discussed before, USD provides	traffic	isolation on a per-user
   basis, and does not manage flows/sessions within the	per-user aggre-
   gated flow. However,	a user or an application may indicate

Wang			  Expiration: May 1998		        [Page 7]

Internet Draft	       User-Share Differentiation		Nov 1997

   preferences or the nature of	the packets through application	marking.
   For example,	a user may prioritize its traffic or an	application may
   mark	some packets as	important thus should be last dropped.

   It is important to note that	the use	of packet marking here is very
   different from that in profile-based	tagging	and priority-based
   schemes, where packet marking is used for admission control and traf-
   fic isolation. The in/out profile bit or the	delay class are	primar-
   ily used to enforce the contractual agreement.  When	packets	enter a
   new ISP, packets may	be re-tagged or	re-classified based on the new
   contractual agreement.

   In application marking, the drop priority or	the delay priority
   reflect only	users' preferences and application characteristics and
   allow the network make application-friendly actions.	 How the packets
   are marked are entirely decided by the users	and the	applications,
   and the marking is meaningful only among the	flows of the same user.

   Traffic isolation and application marking can be viewed as two levels
   of traffic management in USD. Traffic isolation guarantees bandwidth
   sharing among different users, and the application marking allows a
   user	to manage its own traffic flows.

4.6.  Implementation and Deployment

   To support USD, routers need	to implement a scheduler that is capable
   of enforcing	proportional bandwidth sharing.	There is a wide	range of
   scheduling algorithms that can provide such functions. Examples of
   such	schedulers include Class-Based Queuing (CBQ) [4], a scheduling
   algorithm originally	designed for hierarchical link sharing,	Weighted
   Fair	Queuing	(WFQ), one of the most studied scheduling algorithms in
   recent years	[9].  Although the original WFQ	is expensive to	imple-
   ment, several variations of WFQ have	been proposed that support band-
   width sharing in similar fashion but	are optimized for software and
   hardware implementation [5, 6, 7, 8]. Some of the algorithms	can emu-
   late	WFQ closely with O(1) complexity [8]. A	complete analysis of
   those algorithms and buffer management can be found in [5, 10].

   USD enforces	bandwidth sharing locally on the bottleneck links.  Thus
   it does not require any changes to the end systems and any admission
   control at the user-ISP boundaries.	Consequently, USD can be
   deployed an incremental fashion.  In	fact, routers can be upgraded to
   support USD individually and	each upgrade gives incremental improve-
   ment	to the whole network.  For example, when USD is	installed on the
   router connected to the access link to the backbone,	bandwidth allo-
   cation is enforced immediately for all traffic that going through the
   access link.

Wang			  Expiration: May 1998		        [Page 8]

Internet Draft	       User-Share Differentiation		Nov 1997

   Moreover, USD only needs to be deployed at the points in the	network
   that	are heavily congested. Once bandwidth sharing is enforced at
   those points, other links may not require further policing.

5.  Standardization Issues

   Very	little of USD needs to be standardized.	One addition to	the cur-
   rent	system is the distribution of user IDs and its associated shares
   to the routers. This	can be achieved	through	network	management such
   as SNMP. Therefore, we need to agree	on a common MIB	for network man-
   agement systems to install user-specific shares on the routers.

6.  Acknowledgments

   I would like	to thank G. Armitage, T. V. Lakshman, S. Mithal, D.
   Stiliadis, B. Suter for their feedback and discussion.

7.  References

   [1]	K. Kilkki, "Simple Integrated Media Access," Internet
	Draft, June 1997, <draft-kalevi-simple-media-acccess-01.txt>

   [2]	D. Clark, J. Wroclawski, "An Approach to Service Allocation
	in the Internet," Internet Draft, July 1997,
	<draft-clark-diff-svc-alloc-00.txt>

   [3]	P. Ferguson, "Simple Differential Services: IP TOS and
	Precedence, Delay Indication, and Drop Preference,"
	Internet Draft,	Nov 1997, <draft-ferguson-delay-drop-00.txt>

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

   [5]	D. Stiliadis, "Traffic Scheduling in Packet Switched Networks:
	Analysis, Design and Implementation," Ph.D. Thesis, UC Santa
	Cruz, June 1996,
	<http://www.cse.ucsc.edu/research/hsnlab/publications/
	publications_theses_dissertations.html>

   [6]	S. Golestani, "A self-clocked fair queuing scheme for broadband
	applications," IEEE INFOCOM'94,	pp. 636-646, April, 1994.

   [7]	J. Bennett and H. Zhang, "WF2Q:	Worst-acse fair	weighted fair

Wang			  Expiration: May 1998		        [Page 9]

Internet Draft	       User-Share Differentiation		Nov 1997

	queuing," IEEE INFOCOM'96, March 1996.

   [8]	M. Shreedhar and G. Varghese, "Efficient Fair Queueing using
	Deficit	Round Robin," ACM SIGCOMM'95, Sept 1995.
	<http://dworkin.wustl.edu/~varghese/PAPERS/fg.ps>

   [9]	A. K. Parekh, R. G. Gallager, "A generalized processor sharing
	apporach to flow control - the single node case", IEEE
	INFOCOM'92, Vol	2, pp 915-924, May 1992.

   [10] B. Suter, T. V. Lakshman, D. Stiliadis, A. Choudhury, "Efficient
        Active Queue Management for Internet Routers", submitted to INTEROP,
        November 1997 

Authors' Address:

   Zheng Wang
   Bell	Labs Lucent Technologies
   101 Crawfords Corner	Road
   Holmdel, NJ 07733
   Email: [email-masked]

Wang			  Expiration: May 1998	               [Page 10]

---

From: Jean-Yves Le Boudec <[email-masked]>
Date: Wed, 26 Nov 1997 12:41:45 +0200

with the USD scheme, you guarantee a fair share to user flows. Now on which
principle do you base packet classification ? For example, is a packet from
user A to user B classified in the flow of A or B ? How about multicast
packets ?

____________________________________________________________________
JL                         Bien faire, laisser braire (Prov., Bret.)

---

From: Zheng Wang <[email-masked]>
Date: Wed, 26 Nov 1997 14:49:49 -0500

> user A to user B classified in the flow of A or B ? How about multicast

A router checks the src address and dest addess.
If either src or dest matches a entry, the allocation of
the matched entry will be used. If both src and dest
match, it means both the sender and receiver are customers
of the ISP. In this case, the minimum of the two matched
entries should be used. For multicast, an ISP can also
allocate bandwidth to a particular mcast session so that
the session is also isolated from other traffic in the same
way as unicast. Thus, mcast does not require any additional
mechanisms except that the allocation needs to be done
when the mcast address is allocated.

Cheers
Zheng