Link Sizing by Observation of Carried Traffic on the Internet

(1)

2000年度目本オペレーションズ・リサーチ学会秋季研究発表会

1−F−5

LinkSi2：ingbyObservationofCarriedTramcontheInternet HiroshiToyoIZumi University ofAizu E−mail：tOyO＠u−aizu．ac．jp 2．OBSERVATION

Assumethen−thpacket，Whosesizeis Ln，

arrives at the buffer ofoutputlink ofa routeratthetime TL．Thepacketwaits to be．transmitted at the bufferifother packets occupy thelink． The router start＄tranSmittingthepackettothelink at the time S,. Here we assume thee FIFO−discipline at the output bufferfor Simplicity．

Generally，the arrivaltime 7Lis not Observable，Sincethearrivalattheoutput linkbuffercannotbeobservedoutsidethe

router．Ofcourse，We Can eStimate the

arrivaltime㌔byobservingalltheinput

link of router and gathering the packets to be transmitted to the outputlink． ButthisrequlreS mOretOOIs withpreci＄e Clocksynchromization，SOthisassumption

isnotpractical．Instead，WeCanObserve

the data（（Sn，Ln））n；．，2，…．

on the link

connected to the router quite easily．

〈（Sn，Ln））n＝l，2，…．

Canbe obtained bythe COnVentionalpacket−CaPturingtooIs．

3．QueueingIm鮎remce

Aswepointedoutearlier，inthequeueing theory，We need to specifythe amival PrOCeSS and service time distribution as we11 as the queueing discipline． However，WeCannOtbuilda modelofthe arrival process from the data

（（Sn，L”））〝＝l，2，．．，．directly，becauseitdoe＄ not have the information of the arrival

points． 1．INTRODUCTION

ThenextkillerapplicationoftheInternet would be streaming services such as

internet radio，VoIP，1ive video−image broadcasting and so on．In general， Streaming services requires high

bandwidth and strict delay guarantee． Ontheotherhand，manyinternetservice

providers are struggli血g to survive the

SeVere COmpetition by showing their qualityis better than their competitors， SOtheconceptoftheguaranteeofquality，

1ike Service LevelAgreement（SLA）is

becomingmoreandmoreimportant．

Toprovide the service qualityefBciently， weneedtoobserveandmodelthecurrent

traffic on the network，and then design the network according to some objective． Many works has been done for

observation ofthe trafficin theinternet

【1】．AIso，manyreSearChesfordesigming thelinkspeedhasbeendoneinthefield

of e脆ctive bandwidth（seefor example

【2，3】）．

One of the traditional and basic design methods ofnetworkis queueing theory． In general，queuing theory requlreS determining the arrival process and the service time distribution of the queueing

sytem．However，in theinternet，itis

not always possible to observe them

directly．So，We Shoulddevelop a design method using observable data only．

Hereinthis paper，We PrOpOSe a Simple link−Si21ing method by observing traffic onthelink．

−160−

(2)

where Cis the speed of thelink，

P＝＾／C（the utilization ofthelink），

and m＝E［M］（themeandatasizetobe

transmitted）．

So，given the average bu＄y Period，the meandatasizecanbeestimatedby

椚＝（1−β）β。Vgr喝ピC・

（2）

Moreover，We aSSume the data size to be

exponentially distributed．（This assumptionis quite artificial． Some

Studyindicates the data si2：ein the internetcanhaveinfinitevariance，butto get a tractable solution，We aSSumeit

here．）Then，We have anM／M／1system

withthearrivalrate Åandmeanservice

timel／FL SuChas

Å＝A／∽＝〆（哉ygr聯（トβ）〉

Moreover，the service time distribution mightnotbeestimatedbythepacketsize

Ln，becausethedatacanbesegmentedto multiple packets according to the

maxlmum tranSfer unit （MTU）

constraint．

Hereinour method，We uSe the average

busy periodlength Boverqge and the average date rate＾that can be easily

estimatedby（（Sn，Ln））n，．，2，．．．．・’Then，We calculate the required bandwidth of the

linksatisfyingtheservicelevelobjective，

With some assumptio聖S Of the arrival

processandservicetimedistribution．

There have beenstudies calledQueueing Inference problem，Which deals with estimation of performance of queueing systems with the limited observation of

queues【4，5，6］．In［4】，the authors deals with the similar problem to ours in the

COnteXt Ofauto−teller machines，inwhich thereis no data ofarrivalto the queue

but only the start time ofservice．The differenceisthattheyassumetheyknow theservicetimesequence，butweassume theinformation we knowis only the lengthofbusyperiod．

4．MODELINGTHESYSTEM

Assume a userdemands tosendherdata

Of the size M〃 at the time Un， according to the Poisson process．Note

the data might be segmented into the packetstobetransmitting，SO Unisnot alwaysequaltoん・

Hencethe outputlink andits buffercan

be modeled by an M／G／1queue．The

meanbusyperiodlength Boverage canbe

1／〃＝椚／C＝（1−β）β。Vg叩・（3）

ThisM几〟1queueingmodelhasthesame

meandatarateandbusyperiodlengthas thetrafficobserved． 5．SIZINGTHELINK Assumetheinputtothelink（meandata rate，meandatasize）tobe（＾，m）．Let

W（C）bethesqjourntimeofthesystem

（the delayin the queue plus the processing timein thelink）given the linkspeedC． Weneedtoknowthenew linkspeed Cnewsatisfying

ぢ＝巧Ⅳ（qew）＞カ，

（4）

for some predetermined threshold y and theobjectiveprobabilityろ・

We know that the distribution of the

SqjourntimefortheM／M／1queue【7】，i．e．タ（肝＞γ）＝e●バトル＝e￣γ（C￣人）′椚．（5）

Hencetherequiredspeed C〝eWSatisfying

（4）canbeobtainedby

estimatedbythefo1lowing【7】． C／肌

色叩

(3)

4．OE＋07 3．5E＋07 3．OE十07 ︻監已■苫血れメu．1H 2．5E＋07 2．OE＋07 1．5E＋07 1．OE十07 5．OE十06 0．OE＋00

1．00E＿03 1．00E−04 1．00E−05 1．00E−06 1．00E−07

0bjcective probability

Figurel．Required Link Speed

longer mean busy period requires the more bandwidthsincethelongerbusy period meanS the corresponding data sizemight belarger， evenifthemeandatarateissame． C脚＝A＋∽logろ／γ

＝∧−（C。′。一人吼veⅦelogろ／γ’

where C。／disthecurrentlinkspeed・（6） Also，WeCanSeethatthedi脆renceamongthe required speed for each B,,,, increase as theobjective probabilityincreases・This means that we should pay much more

attentiononthetrafficwhenbusyperiods

becomelonger． 6．NUMERIC＾LEX＾MPLES

Figurelshows numericalexamples of our method． Here we assume y （the

predetermined sojourn time threshold）＝

1sec，the currentlink speedislO Mbs． Moreover，We aSSume that the observed

mean data rateis2Mbps，Eachline corresponds to the different observed

mean busy periodlength（Baveroge＝0・2，

0．4，0．6 sec）with various objective

probability ろ・ The ngure shows the

RE『ERENCES

【1］CAIDA，WWW．Caida．org

［2］FP．Kelly，“E脆ctive bandwidth at multi− Class queues，”Queueing Systems，9，pp・5−16，

ー162−

(4)

1991

［3］FP．Kelly，“†ariffiande飴ctivebandwidth

inmultiservicenetworks，”ITC14，pP．40ト410，

1991

【4］R．C．Larson，“Thequeueinfbrenceengine：

deducing queue statistics form transactional

data，“ManagementScience，Vol．36，No．5， pp586−60l，1990

【5］D・Daley and L．Servi，“Exploiting

Markov chain toinfbr queuelength 危・Om

transactionaldata，，．Appl．Prob．，Vol．29，Pp．

713−832，1992

【6］H．Toyoizumi，“A simple method of

estimatingmeandelaybycountingarrivalsand

departures，IEEErNFOCOM’93，pp．823．834，

1993

【7］L・Kleinrock，Queueing Systems Vol．l， JohnWiley＆Sons，1975．

−163−