Schemes in a DiServ Router
Guidance
Professor Masao Fukushima
Associate Professor Tetsuya Takine
Yujin Imagawa
2000 Graduate Course
in
Department of Applied Mathematics and Physics
Graduate Scho ol of Informatics
Kyoto University
KYOTO UNIVERS ITY
FO
UKYOTON DED 1JAPAN897
February 2002
TheInternetwasoriginallydevelop edtoprovidebesteortservice,whichsupportsnoQuality
of Service (QoS) guarantees. To provideQoS guaranteesfor applications which need real-time
control, Integrated Service (IntServ) was prop osed. This service is implemented by use of
architectures such asRSVP whichreservesper-ow based bandwidth. However,IntServ has a
scalabilityproblem. Tosolvethisproblem,DierentiatedService(DiServ)wasprop osed. The
basic idea of DiServ is to fo cus onaggregate of packetsby tagging them and to dierentiate
betweenserviceclasses. DiServcan providesimpleandscalableservice. Currentproposalsfor
DiServarchitectures,however,donotquantifytheservicetheywouldprovideforapplications.
Thus quantifyingQoSs oered by DiServ isthe goal of this thesis.
In this thesis, we propose a new service scheme for a DiServ router, which aims for
dierentiationof twoQoSs, i.e., throughput and meandelay,at the same time. In this service
scheme, arriving packets are divided intofour service classes and dierentiated by one of two
buer management schemes, i.e., separated buer management scheme and shared buer
management scheme. To reect properties of trac, we model these two buer management
schemes withinput streamschangingtheir transferrates reactivelytonetworkcongestion. We
describethesystemdynamicsbyaMarkovchain,andthenprop oseanecientwaytocompute
thesteady stateprobabilities. Intheoverloadedsituation,we examinequalitativep erformance
of the two QoSs through numerical exp eriments. As a result, we show that the proposed
DiServ router can work wellregardless of experimental scenarios.
1 Intro duction 1
2 Proposals for a DiServ Router 2
2.1 Packetclassication : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2
2.2 Buer managementschemes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3
3 Mathematical Mo deling 4
3.1 Phase : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4
3.2 Dropmechanisms : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6
3.3 Eective arrival rate : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8
4 Analysis 8
4.1 Problemformulation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8
4.2 Algorithmic procedureto solve the steady state probabilities : : : : : : : : : : : 11
5 Numerical Results 14
5.1 Scenario : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14
5.2 Basiccharacteristics of the proposed DiServ router : : : : : : : : : : : : : : : : 14
5.2.1 Situation 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16
5.2.2 Other situations : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19
5.3 Impact of buer size : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22
5.3.1 Totalbuer size : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22
5.3.2 Ratio of buer sizes in the separated buer model : : : : : : : : : : : : : 23
5.4 Ratio of arrivalrates between DP classes : : : : : : : : : : : : : : : : : : : : : : 25
6 Conclusion 26
In recentyears, the Internetwasdevelop ed and spread overthe world. The Internet is simply
designed forpacketdelivery. It isbasedonasingleserviceclass, i.e., besteortservice. Inthis
service, allpacketsare treatedin the sameway withoutany discrimination orexplicit delivery
guarantees. This service is implemented simply and inexpensively because of simple packet
forwarding. With improvement of network technology, in addition to traditional applications
such as HTML, e-mail and FTP, new applications which need real-time control, e.g., audio
and movie, have appeared. In these situations, there is new service requirement that oers
Quality of Service (QoS) guarantees for provisions of diverse service classes. To provide QoS
guarantees, IETF investigationmainly focusedontwodierentapproaches: Integrated Service
(IntServ) and DierentiatedService (DiServ).
IntServ [2] was prop osed to integrate non-real-time service and real-time service over the
Internet. Inthisservice,eachowreservesbandwidthbyuseofResourceReSerVationProtocol
(RSVP) [10]. However,IntServhas ascalabilityproblem. Sinceeachowmakesreservationat
intermediaterouters,itisdiculttohandleanumb erofowsinlarge-scalenetworks. Also,the
cost of large-scalerouters becomeshigh. Thus, itisnecessary toprop ose asimplearchitecture
that is applicable to widespread high-speed networks. To solve the problems in IntServ, the
IETF prop osed a new architecture, calledDiServ [1].
ThebasicideaofDiServistofo cusonaggregateofpacketsbytaggingthemandtodieren-
tiatebetweenserviceclassesratherthanprovideabsoluteper-owQoSguarantees[9]. DiServ
can provide simple and scalable service. There are two service schemes, Assured Service and
Premium Service, proposed mainly in DiServ [7]. The Assured Service scheme [3] is argued
that a guaranteed throughput isthe one quality of service feature of interestto most applica-
tions,andthusthatthereisaneedforamechanismthatdirectlyreectsusers' desiresinterms
of transfer time. One way to achievethis objective is to dene a service prole atthe source,
which deneshowpackets shouldbe sent soas to meet the rate objective,and to incorporate
aprolemeter. The prolemetermonitors thetransfer inprogressand tags eachpacketof the
date stream. Thetag issetto1if the packetissentaccording totheprole; the taggedpacket
isalso referredtoasanIN packet. The tag issetto0otherwise; thenon-tagged packetisalso
referred to as anOUT packet. The tag information is used by intermediate routersin case of
congestion. OUT packets are preferentially selected to receive a congestion push-back noti-
cation, which typically means that they are dropped. When buering/scheduling mechanism
is implemented, it is intuitively clear that IN packets will get higher throughput than OUT
packets. On the otherhand, the Premium Service scheme[8]is expected toprovidesignicant
delay reduction for the subscribers. To provide the Premium Service, routers implement two
levels of priority queueing. Tagged (Premium) packets are sent rst; non-tagged (b est-eort)
packetsarequeuedandsentonlywhenalltaggedpacketshaveb eensent. Thereisconsequently
averylimitedqueuemanagementatthe networkno de level. Then, thePremium classb ehaves
as aow aggregation,and doesnot require the controlof eachow withinthe network.
In any case, DiServ architectures based on tagging packets are attractive because they
appear to be simple to implement. However, current prop osals for DiServ architectures do
notquantifytheservice theywouldprovideforapplications. Thusquantifyingthe QoSsoered
In this thesis, we propose a new service scheme for a DiServ router, which aims for
dierentiationof twoQoSs, i.e., throughput and meandelay,at the same time. In this service
scheme, arriving packets are divided intofour service classes and dierentiated by one of two
buermanagementschemes,i.e., separatedbuer managementschemeandsharedbuer man-
agementscheme. Toreectpropertiesoftrac,wemodelthesetwobuermanagementschemes
with inputstreamschangingtheir transferrates reactivelytonetworkcongestion. Wedescrib e
the system dynamics by a Markov chain, and then prop ose an ecient way to compute the
steady state probabilities. In the overloaded situation, weexamine qualitative performance of
the twoQoSs through numerical exp eriments.
The rest of this thesis is organized as follows. In section 2, we describe a new service
scheme for aDiServ router, and two buer managementschemes. In section 3,we considera
mathematical mo del of the prop osed new service scheme. In section 4, we analyze the model
and deriveexpressions for performance measures. In section 5,we show numerical results and
quantify the QoSs to examine performance of the proposed DiServ router. Finally, section 6
concludes the thesis.
2 Proposals for a DiServ Router
In this section, weprop ose a new service schemefor a DiServ router. Throughput and mean
delayarequalitiesofservicefeatureofinteresttomostapplications. Inthenewservice scheme,
aDiServ router aims fordierentiationof these twoQoSs atthe same time. The new service
schemeneedsasimplearchitecturebecauseDiServshouldprovidesimpleandscalableservice.
Inwhatfollows,we showthearchitecturefor dierentiationofQoSs inthe newservice scheme.
2.1 Packet classication
To implement DiServ, a service provider makes a contract with each user. The contract
species the mean transfer rate and the maximum burst length that the user should keep.
According to the contract, the router tags arriving packets. DiServ focuses on aggregate of
packetsby taggingthem and dierentiates b etween service classes. In the new service scheme,
packets are divided into two classes relevant to delay priority. We denote two delay priority
classes by DP1 and DP2, respectively. Packets of D P1 are served by priority, while packets
of D P2 are served onlywhen there are nopacketsof D P1 inthe system. This priority rule is
expected toprovidesignicantdelayreduction forD P1packets. Ineachdelaypriorityclass, if
packetsare sentaccording to the service specication, theyare setto IN,and otherwise, they
are settoO UT. WedenoteIN packetsofDPi (i=1;2)byi-IN packetsand OUT packetsof
DPi (i=1;2)by i-O UT packets. The routerdierentiates between IN and OUT packetsby
drop mechanisms. In anydrop mechanism,O UT packetsare preferentially selectedtodropby
routersincaseof congestion. Usingsuchselectivedrop mechanisms,throughputofIN packets
will b e higher than that of O UT packetsin eachD P class.
We argue a way to dierentiate the four service classes in this subsection. As mentioned in
section 2.1, we use a drop mechanism for throughput discrimination b etween IN and OUT
packets. There are two p opular ways to implement a selective drop scheme, a RED with IN
andO UT packets(RIO)mechanismandathresholddropmechanism. RIO[4]extendsRandom
Early Detection (RED) to handle two classes of packets. RED [5] is designed for congestion
avoidance in packet switched networks. RED detects incipient congestion by computing the
average queue size. When the queue size exceeds a given threshold parameter, RED drops
arriving packetswith a certain probability dependingon the averagequeue size. RIO has two
sets of drop parameters, one is for IN packets and the other for O UT packets. Throughput
dierentiationb etweenIN andO UT packetscanbeachievedbyusingtwothresholds,wherethe
thresholdforOUT packetsissetlowerthanthat forIN packets,orbyusingdropprobabilities
that increase at dierent rates as the average queue length increases. On the other hand, in
the threshold drop mechanism, when buer occupancy reaches a preset threshold, incoming
OUT packetsare discarded, whereasIN packetsare still admitted in the queue aslong as the
buer is not full. Wedenote this mechanism asTHRESH. Ifno sp ecic buer managementis
implemented, arouter uses TAIL drop[6], whichacceptsb oth of IN and OUT packetsunless
thebuer isfull. Ifarouteruses eitherRIOorTHRESHmechanism,itisintuitivelyclear that
IN packets will get higher throughput than O UT packets. In numerical results in section 5,
we make sure of this intuition.
In the new service scheme, we use the service priority discipline to dierentiate mean delay
between D P1 and D P2. A router serves DP1 packets preferentially, and DP2 packets get
service onlywhenthere are noDP1packetsinthe system. Wehandletwobuer management
schemes for delay discrimination. We call one separated buer management scheme, and the
other shar ed buer managementscheme.
In theseparatedbuer managementscheme(showedinFigure1), wehavetwonite queues,
eachhavingcapacityK
i
(i=1;2). Theithqueue isaccessible onlybyDP class ipackets, e.g.,
the1stqueue isaccessibleonlyby1-IN and 1-OUT packets. Ineachqueue, packetsare served
in order of arrival. When the ith queue is full, arriving packets of DP class i are discarded,
evenif the other queue is not full. Packetsof DP1 are served successively untilthe 1st queue
becomes empty. When that queue becomesempty,waitingpacketsof DP2 get service.
Inthesharedbuer managementscheme(showedinFigure2),the routerhas onlyonebuer
of size K, which is accessible by both of DP classes. However, in this buer management
scheme, packetsof DP1are lined up aheadof packetsof DP2. In the same D P class, packets
are servedon a rst-come rst-served basis. If the queue is full, arriving packets are rejected
regardless of their DP class. In a similar fashion of the separated buer managementscheme,
packets of DP1 are served preferentially. Packets of DP2 are served only when there is no
packetof D P1 inthe queue.
the 1st buffer
the 2nd buffer
DP1DP2
server
Figure 1: Separated buer
managementscheme.
DP1
DP2 server
Figure 2: Shared buer
managementscheme.
3 Mathematical Modeling
3.1 Phase
In the Internet, there are various sorts of trac. Trac is roughly classied into two sorts.
Most of trac is TCP-like trac which controls the transfer rate of packets by reacting to
network congestion. We denote this trac by t-trac. In recent years, with appearance of
real-time applications, UDP-like trac has increased, which sends packets indep endently of
network congestion. We call this trac u-trac. To reect the eects of trac, we introduce
phase structure.
The source state is expressed by apair of two phase numbers (m
1
;m
2 ). m
1
denotesa D P1
phase number and represents the source state regarding transmission of DP1 trac, and we
refertom
2
asaDP2phasenumb erandshowthestateaboutDP2tractransfer. DP1phases
are numb ered from 1 to M
1
, and DP2 phases are numb ered from 1 to M
2
. In each phase, we
dene the arrivalrates of four service classes and the transition rates between phases.
First,weargueab outthe arrivalratesoffourserviceclassesineachphase. Whenthestateof
asource is inphase (m
1
;m
2
),sending rate of packets b elonging toD P1 isgivenbya function
of m
1
, while that of DP2 packetsis given by a function of m
2
. Sending rates of each service
class are showedin Table 1.
Table 1: Notation of sendingrates when the source state is in(m
1
;m
2 ).
service class 1-IN 1-OUT 2-IN 2-OUT
notation (1)
IN (m
1
)
(1)
O UT (m
1
)
(2)
IN (m
2
)
(2)
O UT (m
2 )
Wemake following assumptionon the arrivalrate.
Assumption 1 In each D P class i (i=1;2), if m<n,
(i)
IN
(m)
(i)
IN (n);
(i)
OUT
(m)
(i)
O UT (n):
sources send. Weconsidertwosorts of trac, i.e., t-trac and u-trac. Forsimplicity, weas-
sumethatphasetransitionsare dividedintoD P1phasetransitionsandDP2phasetransitions,
andthesephasetransitionsareskip-free,thatis,whenthe sourcestateisin(m
1
;m
2
),allowable
transition istof(m
1
+1;m
2 );(m
1
01;m
2 );(m
1
;m
2
+1);(m
1
;m
2
01)g. Wereferto transition
from (m
1
;m
2
) to (m
1
+1;m
2
) as a DP1 upward transition and transition from (m
1
;m
2 ) to
(m
1
01;m
2
)asaD P1downwardtransition. Inasimilarway,wecall transition from(m
1
;m
2 )
to(m
1
;m
2
+1)aDP2 upward transition and transitionfrom(m
1
;m
2
)to (m
1
;m
2
01)aDP2
downward transition. The relation between the sorts of trac and the transition rates are
showedasfollows.
t-trac (Figure 3)
While there is a buer space to enter packets of DPi (i = 1;2), the state of the source
which sends t-trac transits upward at rate
i (m
1
;m
2
) except that m
i
= M
i
. On the
other hand, when buer occupancy is full, the state of the source makes DPi (i = 1;2)
downward transition at rate ~
i (m
1
;m
2 ) if m
i
6= 1. By setting D Pi (i =1;2) downward
transition rate ~
i (m
1
;m
2
) as DPi arrivalrate at (m
1
;m
2 ),
(i)
IN (m
i )+
(i)
OUT (m
i
), we can
model that lossof DPi packetstriggers downward transition of the source state.
u-trac(Figure 4)
Regardless of buer occupancy, the state of the source whichsends u-trac can transit
toboth upwardanddownwarddirections if 1<m
i
<M
i . Ifm
i
=1,the sourcestate can
transit only upward, whereas if m
i
= M
i
, the source state can transit only downward.
The rate of upward transition is denoted by
i (m
1
;m
2
) and that of downward transition
by ~
i (m
1
;m
2 ).
While there is buffer space
server phase
upward transition
When buffer occupancy is full
server phase
downward transition enter loss
2 3
1 2 1 2 3
Figure 3: Transition oft-trac.
Regardless of buffer occupancy
server phase
transit both direction
2 3
1 2
enter
server loss
Figure4: Transition of u-trac.
Assumption 2 When the source state is in (m
1
;m
2
), an arriving packet belongs to DPi t-
trac(i =1;2) with probability p
i (m
1
;m
2
) and D Pi u-trac with probability 10p
i (m
1
;m
2 ).
The transition rate of a sourceis expressed by the sum of transition rates multiplied by the
correspondingprobability. Letg
n
1
;n
2 ((m
1
;m
2 );(m
0
1
;m 0
2
))denotethe phasetransition ratefrom
(m
1
;m
2
)to (m 0
1
;m 0
2
), given thatn
1
packetsof DP1and n
2
packetsof DP2 are inthe system.
