Achieving Per-Flow Weighted Rate Fairness in a Core Stateless Network

Achieving Per-Flow Weighted Rate Fairness in a Core Stateless NetworkRaghupathy Sivakumar Tae-Eun KimNarayanan Venkitaraman Jia-Ru Li Vaduvur BharghavanUniversity of Illinois at Urbana-ChampaignEmail:sivakumr,tkim,murali,juru,bharghav@AbstractCorelite is a Quality of Service architecture that pro-vides weighted max-min fairness for rate amongflows in a network without maintaining any per-flow state in the core routers.There are three key mechanisms that work in con-cert to achieve the service model of Corelite:(a)the in-troduction of markers in a packetflow by the edge routers to reflect the normalized rate of theflow,(b)weighted fair marker feedback at the core routers upon incipient con-gestion detection,and(c)linear increase/multiplicative de-crease based rate adaptation of packetflows at the edge routers in response to marker feedback.1.IntroductionThe current Internet supports a single service model-simple best effort service.However,the increasing diver-sity of applications using the Internet has led to the emer-gence of Quality of Service(QoS)as a critical issue to be addressed in the future Internet.Two broad paradigms that have been proposed in the last few years for support-ing quality of service in the Internet are Integrated services (Intserv)and Differentiated services(Diffserv).The Intserv approach supports absolute per-flow quality of service mea-sures but requires a substantial amount of per-flow state to be maintained in the routers of the network[10].Since high speed routers in the core of backbone networks typically serve hundreds of thousands offlows simultaneously,it has been argued that Intserv is not a scalable solution for provid-ing QoS support in the Internet.Diffserv,on the other hand, proposes a scalable service discrimination model without requiring any per-flow state management at the routers in the network core[8,13,14].Diffserv is gaining some pop-ularity as the QoS paradigm of the future Internet,in large part because it moves the complexity of providing quality of service out of the core and into the edges of the network, where it is feasible to maintain a restricted amount of per-flow state1.Although Diffserv scores over the Intserv approach in terms of scalability,the key question is:what kind of service model can the Diffserv approach support?.Existing instan-tiations of the Diffserv model support coarse service dif-ferentiation focusing primarily on aggregates offlows,and differentiating between service classes rather than providing per-flow QoS measures.However,recent works in core-stateless networks[4,5,11]have proposed approaches to achievefiner grained service differentiation in an attempt to emulate the richer Intserv service model within the frame-work of the scalable Diffserv network model.In this paper,we present the Corelite QoS architecture with a focus on the set of edge router and core router mech-anisms for achieving per-flow weighted rate fairness in a core-stateless network.Weighted rate fairness achievesfine grained service discrimination on the end-to-end rate al-located toflows,and has been previously used in state-intensive Intserv-like networks as a sophisticated service model for providing QoS.However,we believe that Corelite is among thefirst approaches to achieve weighted rate fair-ness in a core stateless network[5,6].Corelite is broadly based on the Diffserv approach,and the key tenets that form the basis of the Corelite design are:(i)no per-flow state in the core of the network,(ii)a simple forwarding behavior for the core routers,(iii)a low overhead(weighted)fair-feedback scheme at the core routers to provide early con-gestion feedback to the edge routers,and(iv)rate adapta-tion(at the edges)without any packet loss in the network. Guided by the above principles,Corelite supports weighted rate fairness amongflows in the network.Briefly,eachflow in the network can choose to belong to one of many rate classes(each rate class has an associated rate weight)and the rate alloted to aflow is in accordance with a weighted version of the max-min fairness[1]algorithm given the flows in the network and their respective rate weights.The rest of the paper is organized as follows.Sec-tion2describes the weighted rate fairness service model,and presents the high level Corelite approach for achiev-ing weighted rate fairness.Section3explores the key core router functionality in Corelite in greater detail.Section 4evaluates the performance of Corelite and compares its quantitatively with related work.Section5discusses some related work.Section6concludes the paper.2.The Corelite ArchitectureThe Internet can be viewed as an agglomeration of au-tonomous heterogeneous network clouds.Each network cloud consists of core routers at the center and edge routers at the fringes.An end host to end host connection can po-tentiallyflow through multiple network clouds.However, the mechanisms proposed in Corelite are for a single net-work cloud and hence can be deployed in a network cloud independently of other network clouds.Further,since Core-lite proposes mechanisms for a single network cloud as op-posed to an inter-network in general,its mechanisms are edge-to-edge mechanisms and not end-to-end mechanisms. Thus,any reference to aflow in the rest of this paper sig-nifies an edge to edgeflow that can potentially comprise of several end to end microflows.There are two key components to be addressed in such a setup:(a)edge router-core router interaction within a network cloud,and(b)edge router-edge router interaction across neighboring network clouds.In this paper we will only focus on thefirst component:interaction between the edge router and core router in a network cloud.Towards this end,we will consider a single network cloud,and show how we can achieve weighted rate fairness among theflows in that traverse the cloud without maintaining any per-flow state in the core routers.We now define weighted rate fair-ness formally.2.1Weighted Rate FairnessIn Corelite,eachflow is assigned a rate weight,and the network bandwidth is distributed among competingflows in accordance with their rate weights in order to achieve weighted rate fairness.We define weighted rate fairness as a weighted version of max-min fairness,where twoflows that share the same bottleneck link are allocated the link bandwidth in the ratio of their rate weights.Letdenote a rate allocation vector,whereis the rate allocated toflow,and let denote the rate weight offlow.A weighted fair rate allocation vectorof rate thus satisfies the following condition:for any other distinct rate allocation vector,.We define to be the normalized rate offlow.The goal of weighted rate fairness is thus to achieve max-min fairness of the normalized rates rather than the actual rates offlows.While Corelite does not place any bounds on the number or range of the distinct rate weights that can be supported,we expect that a network administrator will typ-ically provide a small number of rate classes for a network, and associate a rate weight with each class.Eachflow will then select a rate class.Max-min fairness is a well known concept[1],and weighted max-min fairness is a fairly straightforward ex-tension.Unfortunately,achieving weighted max-min fairness without maintaining per-flow state routers is no easy task.In a Diffserv-like network,no core router knows about whichflows are traversing through it,let alone their rate weights,no edge router knows which otherflows are shar-ing the path traversed by aflow that is controlled by it,there is no centralized knowledge,and decisions for rate adapta-tion are made for eachflow based purely on the feedback received for thatflow.2.2Achieving Weighted Rate Fairness in CoreliteLet us now look at the basic operation of Corelite.There are three main steps as illustrated in Figure2:1.Shaping and Marking at the Edge Router:Each(ingress)edge router maintains the allowed transmis-sion rate for everyflow passing through it(intothe network cloud),and shapes theflow’s traffic ac-cording to its current.In addition to shaping,the edge router periodicallyintroduces marker packets in theflow transparent tothe sender and receiver of the packetflow,such thatthe rate of transmission of the marker packets reflectsthe normalized rate of the packetflow.Specifically,an edge router introduces a marker packet after ev-ery data packets(or bytes)of the packetflow,where,is a constant and is theweight class of theflow.Thus,aflow that trans-mits at the rate of has a marker packet rate of.Recall that is the nor-malized rate of theflow.In Figure2.(1),.Thusflow A has a marker packet inserted after eachdata packet,andflow B has a marker packet insertedafter every alternate data packet.Note that the markerrates reflect the normalizedflow rates.The marker packet is logically distinct though it maybe physically piggybacked to a data packet.The sourceaddress of the marker is the edge router that generatedit,and the contents of the marker identify the packetflow to which it corresponds uniquely within the edgerouter.22.Marker Caching and Feedback at the Core Router:When a core router receives a data packet,it forwards the packet according to its standard forwarding behav-ior.When it receives a marker packet,it forwards the packet likewise,but also copies the marker packet intoa local marker cache(which is a circular queue).Themarker cache thus contains the recent history of packet transmissions,and the number of markers of a packet flow in the marker cache is proportional to the nor-malized rate of theflow.The marker cache in Figure 2illustrates this fact.It is important to note that the core router does not inspect the contents of the marker packets and performs no per-flow processing or state management at all2.Periodically,each core router detects incipient con-gestion by checking for queue buildup in the packet queue(s).Upon detecting incipient congestion,the core router does not drop queued packets.Instead, it computes how many marker notifications it must send back,randomly selects markers from the marker cache,and sends each selected marker back to the edge router that generated the marker(based on the source address of the marker).The expected number of mark-ers selected for aflow is proportional to its normalized transmission rate.In Figure2.(2),flows A and B trans-mit at the same absolute rate;thus the normalized rate offlow A is twice that offlow B,and A receives twice as many marker feedbacks as B does.Of course,the core router does not know or care whichflows it gen-erates markers for.Note that the feedback is generated on the basis of markers in the cache rather than packets currently in the queue or incoming packets in the next epoch.Thus the feedback mechanism in Corelite is designed to be independent of the scheduling discipline at the core router and fairly insensitive to burstyflows.3.Rate Adaptation at the Edge Router:Periodically(once everyfixed size“epoch”),each edge router checks for marker feedback from core routers.For eachflow that traverses through it,if the edge router received markers for theflow in the last period,it throt-tles back the rate for theflow proportional to the num-ber of received markers;otherwise it increases the rate for theflow by a constant(to probe for additional ratereceived markers(i.e.).In effect,we execute an enhanced LIMD algorithm at the edge routers where the feedback is known to be fair.This leads to weighted rate fairness,as we show through both simulations and analysis.Thus far,we have presented a high level overview of Corelite.Several important details remain to be addressed: (a)how is incipient congestion detected,(b)how many markers are selected upon detection of congestion,(c)how big does the marker cache need to be,and(d)can we get rid of the marker cache altogether and come up with a much simpler scheme for fair marker selection.In the next sec-tion,we address the issues raised above.Specifically,we explore an alternative approach for marker feedback selec-tion at the core router that does not require the maintenance of marker caches,thereby reducing the memory overhead of Corelite and making it trulyflow stateless.3.Marker Management in CoreliteIn Corelite,the edge router is responsible for two func-tions:(a)shaping and marker injection,and(b)rate adapta-tion,and the core router is responsible for two functions:(a) incipient congestion detection,and(b)marker management and weighted fair marker feedback.Since the uniqueness in Corelite is the ability of core routers to provide weighted fair feedback without maintaining per-flow state,we now focus on the two core router mechanisms.3.1Incipient Congestion DetectionEach core router monitors its packet queues,and upon detecting incipient congestion,sends back sufficient num-ber of markers to the edge routers,so that the consequent rate throttling performed by the edge routers will reduce the aggregate input traffic into the core router in the future, and thus alleviate congestion before queues become full and packets are dropped.In Corelite,the core router detects incipient congestion by monitoring the length of its packet queues.A core router may have multiple packet queues depending on its forward-ing behavior.For purposes of congestion detection,we only care about the aggregate queue size over all the queues cor-responding to a link.The congestion detection function is performed periodically,once every congestion epoch.The core router maintains the average of the aggregate queue size,,during the epoch.At the end of every epoch, the core router checks to see if exceeds a predefined congestion threshold queue size.If, then the core router concludes that there is incipient con-gestion and that it must send back markers to initiate rate throttling at the edge routers.The remaining question is how many markers to send back?Consider that the sending of each marker causes arate throttling by at least.Then,the number of markers sent back,,is computed by the following equation:)and the desired expected arrival rate that corresponds to the average queue size of(i.e.markers toflow.The 4scheme requires no marker caches,and additionally only sends feedback selectively for thoseflows whose input traf-fic is larger than their weighted fair share(i.e.flow re-ceives no feedback if weighted fair share,and re-ceives,where is the running average of the number of markers observed in each epoch.Additionally,a deficit variable is maintained,reset to0at the start of each epoch. When the core router sees a marker,itfirst selects the marker for feedback with a probability of:(a)if the marker is selected and its labelled rate,the marker is sent back to the edge router that generated it;(b)other-wise if the marker is selected but its labeled rate, the marker is not sent back as feedback,but the deficit vari-able is incremented;(c)otherwise,if the marker is not se-lected,but the deficit variable is positive and the labelled rate,then the marker is sent as feedback and the deficit variable is decremented.In summary,the deficit vari-able ensures that if a marker corresponding to aflow with normalized rate lower than the running average happens to be selected,then it is swapped with a future marker corre-sponding to aflow whose normalized rate is at or above the average.The above approach has the advantage of selectively throttling misbehavingflows without maintaining per-flow state,which is a very powerful feature.However,there are some issues associated with the approach.First,weonlyR10R13R9R20 work Topologyconsider the incoming markers in the current epoch when selecting markers for feedback.This makes the approach susceptible to bursts in packet/marker arrival.Second,there is no guarantee that the required number of markers will in fact be selected in the current epoch.In summary,the algorithm is similar to CSFQ,but improves on CSFQ:it does not depend on the accuracy of explicit fair share measurement unlike CSFQ.In the performance evaluation section,we show how and why this approach performs better than CSFQ.Over the last two sections,we have described the key mechanisms that enable Corelite to achieve weighted rate fairness in a core-stateless network.These include traffic shaping,marking and rate adaptation mechanisms of edge routers(discussed in Section2)and the congestion esti-mation and marker selection mechanisms of core routers (discussed in Sections2and3).In the next section,we will evaluate the performance of Corelite.4.Performance EvaluationIn this section,we use simulations to evaluate our model and compare the weighted rate fairness obtained in the con-text of Corelite,against the weighted version of CSFQ[5]. The simulations3,performed using the ns-2.1b4a simula-tor[12],serve to justify the validity of the mechanisms used in Corelite.In this section we present two sets of re-sults.In thefirst set of results,we illustrate the efficacy of the mechanisms used to provide minimum rate contracts and weighted rate fairness in Corelite by computing the ex-pected values and comparing it with the actual rates allo-cated()toflows.For the next set of results,we compare the weighted rate fairness obtained in the context of Core-lite,against the weighted version of CSFQ4.In this case we compare their behavior in steady state and whenflows dynamically enter and exit the network.The topology used for the simulations is shown in Figure204060801001200100200300400500600700800a l l o t e d _r a t etime in secondsAlloted rateflow1flow2flow3flow4flow5flow6flow7flow8flow9flow10flow11flow12flow13flow14flow15flow16flow17flow18flow19flow20Figure 3.Instantaneous Rate1000020000300004000050000600000100200300400500600700800t o t a l _s e n ttime in secondsNumber of packets successfully sentflow1flow2flow3flow4flow5flow6flow7flow8flow9flow10flow11flow12flow13flow14flow15flow16flow17flow18flow19flow20Figure 4.Cumulative Service2.It consists of three congested links and has flows that tra-verse different number of congested links.Flows in topol-ogy 1also have high and varying round trip times ranging from 240ms to 400ms.The source agents that we have used to obtain the results for Corelite and CSFQ use similar rate adaptation schemes viz.decrease the sending rate propor-tional to the number of congestion indication messages re-ceived (losses in case of CSFQ)or increase the sending rate by one every epoch.After startup,the agents remain in the slow-start phase (doubling the sending rate every second)until they receive the first congestion notification or until the out-of-profile rate exceeds ss-thresh (set to 32packets per second)at which point they reduce their rate by half and switch to the linear increase phase.All the simulations presented in this section use a fixed packet size of 1KB,(used for generating markers)of 1,and (used for rate adaptation)of 1,a queue size of 40packets,conges-tion detection threshold of 8packets,and an epoch size of 100ms at the core router.All the links have a bandwidth of 4Mbps(500packets per second)and a latency of 2ms.For CSFQ,(used in estimating flow rate)and (average interval for computing rateTotal)were set to 100ms.In all the cases,we assume that the flows always have packets to send.4.1Weighted Rate Fairness with Network Dy-namicsIn this scenario,we illustrate how Corelite can effec-tively support weighted rate fairness in a core stateless net-work.We consider a total of 20flows with flows 1to 5,11to 12and 16to 20passing through only a single con-gested link between C1-C2,C2-C3and C3-C4respectively and have a round trip time of 240ms.Flows 6to 8and 13to 15traverse two congested links and have a round trip time of 320ms while flows 9and 10traverse three congested links and have a round trip time of 400ms.Flows 5and 15have a rate weight of 3,and flows 1,11and 16have a weight of 1each.All other flows have their weights set to2.Flows 1,9,10,11and 16start at time t=250seconds and stop at time t=500seconds.All other flows start at time t=0seconds and stop at time t=750seconds.The results from this scenario are shown in Figures 3and 4.We will first calculate the expected rate for the flows and then compare it with the rates obtained by the flows.To calculate the expected rates for the flows 1to 20,ob-serve that all the links have a bandwidth of 500packets per second.Initially,when flows 1,9,10,11and 16are not in the network,each flow should get a rate of 33.33pack-ets per second per unit weight.In Figure 3flows 5and 15have an alloted rate of 99.99packets per second (33.33*3)since they have a rate weight of 3.The other flows in the network have rate weights of 2and hence have an alloted rate of 66.66packets per second.At time t=250seconds,when flows 1,9,10,11and 16are introduced,the fair share per unit weight drops down to 25packets per second.Con-sequently,flows 5and 15have an alloted rate of 75packets per second,flows 1,11and 16have an alloted rate of 25packets per second and all other flows have an alloted rate of 50packets per second.Finally,when flows 1,9,10,11and 16stop,the other flows climb up to their original rate allocations.Figures 3and 4show the results of the simulations and they conform to the expected values.In Figure 3we ob-serve that all flows except 1,9,10,11and 16start at time 0,and converge rapidly to their fair share.When flows1,9,10,11,16start at time,other flows fall back almost instantaneously.The new flows receive no conges-tion notifications until they reach a point close to its fair-share.The 3flows at the bottom of Figure 3are flows 1,11and 16,having a weight of 1.Although these flows tra-verse different paths they all approximately get their fair share of 25packets per second.The largest bunch of flows right above these three flows are the flows with a weight of 2.They receive approximately twice the amount of excess bandwidth compared to flows with weight 1.This set again has flows traversing different number of congested links and610203040506070809001020304050607080a l l o t e d _r a t etime in secondsAlloted rateflow1flow2flow3flow4flow5flow6flow7flow8flow9flow10Figure 5.Corelite Instantaneous rate10203040506070809001020304050607080a l l o t e d _r a t etime in secondsAlloted rateflow1flow2flow3flow4flow5flow6flow7flow8flow9flow10Figure 6.CSFQ Instantaneous ratehence with different round trip times.The closely spaced parallel lines in the cumulative ser-vice graph shown in Figure 4shows that the total service obtained by flows having the same weight is the same irre-spective of their round trip times and the number of con-gested links they traverse (recall that our fairness model is maxmin rather than proportional or min-potential delay).4.2Weighted Fair Rate Allocation (Corelite vsCSFQ)In the remaining sections,we compare the performance of Corelite against the weighted version of CSFQ.In this section we start multiple flows with different weights at the same time,and compare the startup and steady state behav-ior of Corelite and CSFQ.We use topology 1,with 10flows having five different weights such that flow has a weight.The results for this scenario obtained with Corelite and CSFQ are shown in Figures 5and 6respectively.Both the mechanisms achieve results that closely approx-imate the ideal values in steady state.However,their startup behaviors differ with Corelite converging faster than CSFQ.In this scenario,with Corelite,none of the flows experi-enced packet drops and flows sending at a rate lower than its fair share never received congestion notifications.However,with CSFQ,when many flows startup simultaneously the estimated fair rate deviates from its correct value because it does not track the rapidly changing fair share correctly.If the fair share is underestimated,then packets from flows that are sending below the actual fair share can be dropped.On the other hand,if the fair share is overestimated then more packets will be accepted than the router can transmit,resulting in queue buildups and potential overflows.This re-sults in flows observing losses even before they reach their fair share.Thus in CSFQ the drop behavior degenerates into a tail-drop behavior when the buffer overflows.This occurs when the estimated fair-share at the core router is higher than the correct value.In Figure 6,flows 7and 8,move into linear decrease phase when their rates are only30,though their weighted fair share rate is around 70pack-ets per second.Also,note that these flows experience more packet drops along the way -between times-before they reach their fair rate.The selective marker feed-back mechanism used with Corelite does not try to estimate the fair rate.Instead,it only computes an average of thenormalized rates observed in themarked packets and throttles only those flows that send more than this computed average.In Figure 5,flows 7to 10,with weights 4and 5,complete their slow-start phase and move into the linear in-crease phase at time.They receive congestion notifications only after they are close to their respective fair share rates.This results in Corelite converging more than 30seconds faster than CSFQ.4.3Weighted Fairness with Network Dynamics(Corelite vs CSFQ)In this section we compare the behavior of the two schemes,when flows with different weights enter the net-work one after another in rapid succession.We use the topology in Figure 2with 20flows,flows 1,11and 16hav-ing a weight of 1and flows 5,10and 15having a weight of 3.All other flows have a weight of 2.Figures 7and 8correspond to Corelite and CSFQ respec-tively when flows start apart in ascending order of flow number.Clearly,convergence is faster in Corelite than in CSFQ.This is because unlike Corelite,where all flows move to the linear increase phase only after reaching a point close to their final rate,in CSFQ,flows observe losses early in their life time resulting in slower convergence.As we mentioned in the previous section,when flows enter in the network in rapid succession,the estimated fair share in CSFQ will not converge to the correct value instantaneously and the core router can degenerate into tail dropping.How-ever,in Corelite,even if there are packet drops,the feedback generation is still fair.As edges react only to congestion in-dications,the rates allocated to flows remains fair.Figures 9and 10show the results obtained with Corelite7102030405001020304050607080a l l o t e d _r a t time in secondsflow14flow15flow16flow17flow18flow19flow20Figure 7.Corelite Instantaneous rate102030405001020304050607080a l l o t e d _r a t time in secondsflow14flow15flow16flow17flow18flow19flow20Figure 8.CSFQ Instantaneous rateand CSFQ respectively,when flows 1to 20start apart in ascending order and after a life of stop one second apart in the same order.The flows then restart,5seconds after they had stopped.Thus there are flows simul-taneously entering and leaving the system during the time between 65and 80.The figures clearly show that Corelite adapts gracefully to the dynamics of the network,where as with CSFQ the difference in performance obtained especially by flows with higher weights and that are short-lived is significant because flows have a greater chance of exiting their slow-start prematurely.Corelite avoids this and provides improved fairness even for short-lived flows.4.4Summary of Performance EvaluationThe results that we have presented here serve as a proof of concept for the Corelite mechanisms and justify to some extent the claims made in this paper.Our initial results show that Corelite provides per-flow rate contracts and weighted fair allocation of bandwidth without any per-flow state in the core,the system is stable and adapts itself gracefully to the network parisons with CSFQ indicate that though both the mechanisms perform well in steady state,Corelite performs significantly better than CSFQ when the fair share at the core router varies rapidly.In the multiple-hop case,flows traversing multiple congested links in CSFQ experience more losses and hence get a lower cu-mulative throughput than the ones traversing a single con-gested link.This is not the case in Corelite because the edge router can distinguish the congestion indications generated from different core routers.Our simulations with differ-ent core router epoch sizes,different marking thresholds,and channels with large latencies indicate that Corelite is not very sensitive to these parameters.The simulations are however,by no means comprehensive.Simulations using different adaptation schemes at the edge router and differ-ent congestion estimation schemes at the core router,and using agents like TCP which involve interaction between the edge router and end-host are part of ongoing work.5.Related WorkAlthough Corelite is based on the Diffserv philosophy of maintaining no per-flow state in the core,it differs signifi-cantly from the existing approaches in terms of the seman-tics of marking,specific functionalities of the core and the edge router,and the service profiles it offers to users.A ser-vice in Diffserv is typically for traffic aggregates,not indi-vidual flows [8].Most existing Diffserv approaches [13,14]use a mechanism of marking,where packets are marked based on whether they are in-profile or out-of-profile.In particular,packets belonging to in-profile traffic are marked while the others are left unmarked.Marked packets receive preferential treatment as they are forwarded in the network,in terms of a lower drop priority and/or higher scheduling priority.Core routers drop best effort traffic before drop-ping marked packets.However,there is no explicit support for fairness between flows.There has been a lot of work done on incipient conges-tion detection mechanisms [7,9].In [7]when a packet ar-rives,the router calculates the average queue length for the last busy+idle period and the current busy period.When the average queue length exceeds one,it sets the congestion indication bit in the arriving packets.In RED[9],the router maintains an exponentially-weighted moving average of the queue length which is used to detect congestion.It main-tains two thresholds.If the average queue length is less than the ,no packet is dropped and when it is greaterthanall packets are dropped.When the aver-age queue length is in between these two values,packet are dropped with a probability that is a function of the average queue length.However,it provides no fairness guarantees.FRED[2]extends RED to provide some degree of fair bandwidth allocation.However,it maintains state for all flows that have at least one packet in the buffer.Also it deviates from the ideal case in a number of scenarios as pointed out in [5].In CSFQ [5],the core router dynamically calculates the fair-share for flows,and on congestion prob-8。