A Complete LTE Mathematical Framework for the Network Slice Planning of the EPC

THIS IS AN AUTHOR-CREATED POSTPRINT VERSION. Disclaime : This wo k has been accep ed o publica ion in he IEEE T ansac ions on Mobile Compu ing. Ci a ion in o ma ion: DOI 10.1109/TMC.2018.2890235 Copy igh : © 2019 IEEE. Pe sonal use o his ma e ial is pe mi ed. Pe mission om IEEE mus be ob ained o all o he uses, in any cu en o u u e media, including ep in ing/ epublishing his ma e ial o ad e ising o p omo ional pu poses, c ea ing new collec i e wo ks, o esale o edis ibu ion o se e s o lis s, o euse o any copy igh ed componen o his wo k in o he wo ks. 1 A Comple e LTE Ma hema ical F amewo k o he Ne wo k Slice Planning o he EPC Jona han P ados-Ga zon, Abdelquoddouss Lagh issi, Miloud Bagaa, Ta ik Taleb, and Juan M. Lopez-Sole Abs ac —5G is he nex elecommunica ions s anda ds ha will enable he sha ing o physical in as uc u es o p o i- sion ul a sho -la ency applica ions, mobile b oadband se ices, In e ne o Things, e c. Ne wo k slicing is he i ualiza ion echnique ha is expec ed o achie e ha , as i can allow logical ne wo ks o un on op o a common physical in as uc u e and ensu e se ice le el ag eemen equi emen s o di e en se ices and applica ions. In his ein, ou pape p oposes a no el and comple e solu ion o planning ne wo k slices o he LTE EPC, ailo ed o he enhanced Mobile B oadBand use case. The solu ion de ines a amewo k which consis s o : i) an abs ac ion o he LTE wo kload gene a ion p ocess, ii) a compound a ic model, iii) pe o mance models o he whole LTE ne wo k, and i ) an algo i hm o join ly pe o m he esou ce dimensioning and ne wo k embedding. Ou esul s show ha he agg ega ed signaling gene a ion is a Poisson p ocess and he da a a ic exhibi s sel -simila i y and long- ange-dependence ea u es. The p oposed pe o mance models o he LTE ne wo k ely on hese esul s. We o mula e he join op imiza ion p oblem o esou ces dimensioning and embedding o a i ualized EPC and p opose a heu is ic o sol e i . By using simula ion ools, we alida e he p ope ope a ion o ou solu ion. Index Te ms—LTE, EPC, Ne wo k Slicing, NFV, So wa ized Ne wo ks, Mobile Ne wo ks, T a ic cha ac e iza ion, Resou ces dimensioning, and Ne wo k embedding. I. INTRODUCTION FIFTH Gene a ion (5G) mobile ne wo ks play a pa amoun ole in he o hcoming global indus ial digi aliza ion. 5G will co e all he e ical ma ke needs in a cos e ec i e manne . Compa ed o i s p edecesso (i.e., he Long-Te m E olu ion (LTE) echnology), he equi emen s o 5G sys ems include, among many o he s, highe ne wo k lexibili y and scalabili y, as well as x100 inc ease in cos e ec i eness [1]– [4]. To mee hese challenging goals, ne wo k so wa iza- ion (NS) is en isaged as he co ne s one o build he 5G echnology [5], [6]. The concep o NS is mainly based on i) Ne wo k Func ion Vi ualiza ion (NFV), which decouples ne wo k unc ions om p op ie a y ha dwa e enabling hem o un as so wa e on i ualiza ion con aine s such as i ual machines (VMs) [7], and ii) So wa e De ined Ne wo king Jona han P ados-Ga zon and Juan M. Lopez-Sole a e wi h he Resea ch Cen e o In o ma ion and Communica ions Technologies o he Uni e si y o G anada (CITIC-UGR); and he Depa men o Signal Theo y, Telema ics and Communica ions o he Uni e si y o G anada, G anada, 18071 Spain (email: jpg@ug .es, juanma@ug .es). Abdelquoddouss Lagh issi, Miloud Bagaa, and Ta ik Taleb a e wi h he Depa men o Communica ions and Ne wo king, School o Elec ical En- ginee ing, Aal o Uni e si y, Espoo, Finland. Ta ik Taleb is also wi h he Cen e o Wi eless Communica ions (CWC), Uni e si y o Oulu, 90014 Oulu, Finland, and also wi h he Compu e and In o ma ion Secu i y Depa men , Sejong Uni e si y, 143-747 Seoul, AQ3 Sou h Ko ea. (emails: abdelquod- [email p o ec ed], [email p o ec ed], [email p o ec ed]). (SDN), which ully sepa a es con ol and da a planes in ne wo k nodes allowing ne wo k p og ammabili y. Unde he NS app oach, isola ed, ully au oma ed, p o- g ammable, lexible, and se ice-cus omized ne wo ks known as ne wo k slices can be deployed on op o a common physical in as uc u e [8]–[10]. This app oach is e e ed o as ne wo k slicing. I will allow he mobile ope a o s o co e he di e en ma ke scena ios and use cases ha demand he e ogeneous, di e se and possibly mu ually incompa ible equi emen s [5]. The adop ion o ne wo k slicing in 5G mobile ne wo ks equi es op imal solu ions o planning he slices acco ding o he di e en use cases equi emen s. This mainly in ol es he dimensioning o he esou ces and i s embedding in a gi en in as uc u e. Fu he mo e, hese p ocesses ha e o be done in a manne ha ensu es he Quali y o Se ice (QoS) equi emen s o each use case. Likewise, aced wi h a dec easing A e age Re enue Pe Use (ARPU), ope a o s a e challenged o educe, o e en op imize, i) he acqui emen and main enance o he physical in as uc u e (i.e., capi al expen- di u es -CAPEX-), and ii) he ongoing expenses o p ope ly ope a e he ne wo k equipmen (i.e., ope a ing expendi u es - OPEX-). Many echno-economic models ha e been p oposed o educe he CAPEX and OPEX such as in [11], [12]. Ou wo k aims o design a comple e solu ion o ne wo k slices planning o he LTE E ol ed Packe Co e (EPC), which is ailo ed o he enhanced Mobile B oadBand (eMBB) use case [7], [13]. To ha end, we p opose a amewo k consis ing o he ollowing componen s: •An abs ac ion o he LTE wo kload gene a ion p o- cess, o bo h Con ol Plane (CP) and Da a Plane (DP), along wi h a compound a ic model ha includes he mos ep esen a i e se ices consumed in cu en cellu- la ne wo ks. This is equi ed o es ima e he se ice consump ion when he e is no p e ious knowledge o he wo kload demand. This componen is also use ul o gene a e syn he ic wo kloads o expe imen a ion (e.g., o s ess a i ualized LTE ne wo k). •Holis ic analy ical models o p edic he pe o mance (e.g., packe loss p obabili y and esponse ime) o a i ualized EPC ( EPC). We apply queuing heo y and s ochas ic ne wo k calculus o de elop he CP and DP models, espec i ely. Fo a gi en wo kload and a se o QoS equi emen s, ou models acili a e esou ces dimensioning. •The co esponding o mula ion and heu is ic o sol e he join op imiza ion p oblem o esou ces dimensioning and embedding o he EPC. We ha e sugges ed a mul i- objec i e op imiza ion p oblem ha minimizes he wo k- 2 load imbalances among a se o candida e Edge Clouds (ECs) (i.e., Da a Cen e s (DCs) deployed close o end use s) and maximizes he esou ces u iliza ion, on he ne wo k side, and Quali y o Expe ience (QoE), on he end use ’s side. These objec i es a e subjec o mee a se o QoS equi emen s. Fo he CP, he QoS equi emen s a e de ined as an uppe bound on he a e age elapsed ime o mo e a Use Equipmen (UE) om IDLE o ACTIVE s a es. Fo he DP, he QoS equi emen s conside ed a e he limi on he maximum one-way ne wo k delay and a maximum packe loss p obabili y a he EPC. Addi ion- ally, we impose a condi ion o limi he maximum numbe o Cen al P ocessing Uni (CPU) co es o be assigned o a single Vi ual Ne wo k Func ion Componen (VNFC) ins ance. Tha is o ake in o accoun he ac ual limi a ion on he numbe o CPU co es o he Physical Machines. Sha ing ne wo k esou ces be ween di e en use s has p o en o educe CAPEX and OPEX [14]–[16]. The abo e- men ioned ea u es, namely he pe o mance-p edic i e mod- els, he load balancing among ECs, and he maximiza ion o esou ce u iliza ion will ce ainly induce conside able cos sa ings. Also, he maximum numbe o CPU co es cons ain will ha e an impac on educing he cos s due o OPEX [17]. Las , al hough he NS pa adigm enables ope a o s o dynamically adap he esou ces alloca ed o each ne wo k slice and se ices [18], he on-demand plans o e ed by in- as uc u e p o ide s a e mo e expensi e han he ese a ion plans. Speci ically, esou ces can be pu chased as a ese a ion o up o 70% o he on-demand p ice [19]. Thus, he ne wo k slices planning is c ucial o ope a o s o sa e money. As a s a ing poin , his wo k is mean o enhance he “Ne wo k Slice Planne ” (NSP) [20]. NSP is a simula ion ool ha implemen s accu a e models o he use s’ beha io , mo- bili y, and da a consump ion in cellula ne wo ks. Speci ically, we ex end i s da a consump ion model o include he mos ep esen a i e se ices consumed in cu en mobile ne wo ks. Then, by using NSP we cha ac e ize s ochas ically he ag- g ega ed wo kload gene a ion p ocesses o he CP and DP. Unde ou wo kload gene a ion model, he esul s show ha he agg ega ed signaling gene a ion p ocess ollows a Poisson dis ibu ion and he agg ega ed DP wo kload exhibi s Sel - Simila i y (SS) and Long-Range Dependence (LRD) ea u es. Based on he a o esaid esul s, we de elop holis ic pe - o mance models o a i ualized LTE ne wo k. The CP is modeled ollowing he same echnique as in [21] o chains o Vi ual Ne wo k Func ions (VNFs). The model includes he main LTE en i ies and hei messages exchange. The DP is modeled as a queue ed by a ac ional B ownian Mo ion ( Bm) p ocess [22]. These comp ehensi e models allow us o de ine e icien esou ces dimensioning algo i hms. Finally, he heu is ic p oposed in his wo k o sol e he planning o EPC elies on he a o emen ioned pe o mance models. The algo i hm is dubbed “Planne o he EPC as a Se ice” (PES). By using a sys em-le el LTE simula o , we alida e he co ec ope a ion o PES. We also show ha PES embedding algo i hm educes he wo kload imbalances among candida e ECs in con as o o he baseline echniques. The emainde o he pape is o ganized as ollows. Sec ion II b ie ly e iews he ela ed li e a u e. Sec ion III desc ibes he sys em model. Sec ion IV includes he o mula ion o he join op imiza ion p oblem o esou ce dimensioning and em- bedding o he EPC. In Sec ion V, he modeling and analysis o es ima e he pe o mance o he CP and DP a e p esen ed. Nex , in Sec ion VI, we in oduce he p oposed heu is ic o pe o m he planning o he EPC. Sec ion VII explains he expe imen al se up. Sec ion VIII p o ides nume ical esul s ha show he p ope ope a ion o ou solu ion. Finally, Sec ion IX summa izes he main conclusions. II. RELATED WORKS This sec ion b ie ly e iews he ela ed li e a u e. In pa - icula , we ocus on pe o mance models and embedding algo i hms (i.e., on how o map VNFC ins ances o physical in as uc u es) o he EPC. A. Modeling o he EPC Analy ical models cons i u e an agile way o p edic he pe - o mance o a sys em in ad ance. The e a e se e al p oposals in he li e a u e ackling he analy ical modeling o pa s o he en i e EPC [21], [23]–[27]. In a iably, hese wo ks employ queuing heo y. In [24], Rajan e al. model he EPC as a D/D/m node. They conclude ha when simply eplacing exis ing EPC elemen s wi h i ualized equi alen s, se e e pe o mance bo lenecks occu . In [26], [27], P ados e al. analyze he pe o mance o a i ualized Mobili y Managemen En i y ( MME) wi h a h ee- ie design, inspi ed by web se ices, and using a Jackson’s ne wo k (i.e., a ne wo k o M/M/m queues). Each queue ep e- sen s a ie o VNFC o he MME. The au ho s show ha he p oposed model p o ides ai ly good esul s o compu a ional esou ces dimensioning. In [21], he same au ho s enhance he p e ious model by ex ending i s applicabili y domain o any chain o VNFs, inc easing i s lexibili y, and using a mo e accu a e echnique o analysis. Speci ically, each VNFC ins ance is modeled as a G/G/m queue. The esul ing ne wo k o queues is sol ed by using he app oxima ed echnique p oposed by Whi e al. in [28] o he Queuing Ne wo k Analyze e e ed o, he eina e , as he QNA me hod. Fo he abo emen ioned use case (a h ee- ie ed MME), he au ho s show he QNA me hod ou pe o ms Jackson’s ne wo ks and Mean Value Analysis echniques in e ms o he esponse ime es ima ion e o . Tanabe e al. p opose in [23] a bi- class (i.e., Machine- o-Machine and Mobile B oadband -MBB- communica ions) queuing model o he EPC. The CP and DP o he EPC a e modeled as M/M/m/m and M/D/1 nodes, espec i ely. This model cons i u es he co e o he EPC-ORA me hod which aims o op imize he esou ce assignmen o he CP and DP o he EPC. Finally, in [25], Ren e al. p opose a dynamic esou ce p o isioning algo i hm o he EPC conside ing he capaci y o legacy ne wo k equipmen al eady deployed. To e alua e he pe o mance o hei solu ion, hey model each EPC elemen as a M/M/m/K queue and assume ha he VNF ins an ia ion ime is exponen ially dis ibu ed. The a o emen ioned wo ks only model pa s o he EPC and/o do no cap u e he in e ac ions among i s elemen s. 3 In his pape , his gap is co e ed. We conside he main elemen s o he LTE ne wo k CP (i.e., UE, e ol ed Node B -eNB-, MME, Se ing Ga eway -SGW-, Packe Da a Ne wo k Ga eway -PGW-, Home Subsc ibe Se e -HSS-, and Policy and Cha ging Rules Func ion -PCRF-) as well as hei in e ac- ions. In his way, i is possible o p edic he pe o mance o he whole LTE CP om he agg ega ed signaling gene a ion p ocess. In [23], [25], he esou ces dimensioning o he EPC is also isi ed. Ne e heless, hese wo ks add ess he dimensioning o each componen in an isola ed way. Only hen, i is necessa y o de ine a p ocessing delay budge o each en i y o be dimensioned in ad ance. Ou holis ic model o an LTE ne wo k o e comes his limi a ion by enabling he esou ces dimensioning algo i hm o conside an o e all p ocessing delay budge o he whole EPC. This leads o esou ces sa ings. Fo he DP, we le e age he esul s ob ained o he analysis o he LTE da a a ic aces o de i e i s pe o mance me ics. Speci ically, he EPC DP is modeled as a single queue ed by a Bm p ocess. To he bes knowledge o he au ho s, his is he i s wo k ha uses s ochas ic ne wo k calculus esul s o analyzing he pe o mance o a EPC. B. Algo i hms o he EPC embedding The e is a ich li e a u e p oposing algo i hms o embed he whole EPC o some o i s en i ies in a physical in as uc u e [29]–[38]. In [29], Taleb e al. p opose a heu is ic algo i hm o i ualized SGWs ( SGWs) embedding. The algo i hm ies o minimize he equency o mobili y ga eway eloca ions while ensu ing ha a maximum capaci y o each SGW, which handles he a ic load o a se ing a ea, is no exceeded. This wo k is ex ended in [32] whe e some addi ional objec i es and es ic ions a e conside ed. Rega ding he objec i es, he pa h be ween UEs and PGWs is minimized, and he o e all ne wo k esou ce u iliza ion is op imized. Conce ning he es ic ions, his wo k was a pionee in conside ing some ele an hi d gene a ion pa ne ship p ojec (3GPP) cons ain s. In [30], Bagaa e al. add ess he embedding o he i u- alized PGW ( PGW). The embedding p oblem is o mula ed as a mul i-objec i e non-linea op imiza ion p oblem which minimizes he cos s o he ne wo k ope a o s, maximizes he ne wo k pe o mance, and balances he load equally among he PGW ins ances. To sol e he p oblem, h ee heu is ic algo i hms a e p oposed o achie e nea -op imal solu ions. In [31], Bas a e al. in es iga e di e en app oaches o deploy he co e ga eways (i.e., SGW and PGW) in he DCs. Speci ically, hey conside a ully and pa ially i ualiza ion app oaches o he ga eways. The o me consis s in mo ing he CP and DP unc ionali ies o each ga eway o a DC. The la e decou- ples CP and DP unc ionali ies by using he SDN pa adigm and only he CP pa is hos ed wi hin a DC. In he same con ex ; elying on an SDN amewo k ha decouples he CP om he DP, Da sika e al. p opose in [39] a Ma ching Theo e ic Flow P io i iza ion algo i hm ha aims o imp o e he g ade o se ice le el and delay induced by he co e ne wo k conges ion. This app oach allows o e he op se ice p o ide s o in e ene in he i ual slices alloca ion p ocess. TABLE I: No a ion. No a ion Desc ip ion m(c) l Numbe o dedica ed physical CPU co es alloca ed o ins ance lo he VNFC c∈C. mmax Maximum numbe o dedica ed physical CPU co es o be alloca ed o a single i ualiza ion con aine . TeAc ual mean esponse ime o he CP en i y e∈E. Ti Ac ual mean esponse ime o he LTE in e ace i ∈IF . T(SR)Ac ual mean delay o he CP o ca y ou an SR p ocedu e. T(CP ) budge Mean delay budge o he CP. T(max) uAc ual maximum esponse ime o he DP en i y u∈U= {UE, eNB, DP GW}. T(max) i Ac ual maximum esponse ime o he LTE DP in e ace i ∈IF U ={Uu, S1−U}. T(DP ) max Ac ual maximum delay o he DP. T(DP ) budge Maximum delay budge o he DP. P(EP C)Ac ual EPC packe loss p obabili y. P(EP C) budge EPC packe loss p obabili y budge . I has pe mi ed o achie e e icien lows p io i iza ion wi h espec o he se ice p o ide s’ policies and QoS demands. In [33], Ma ini e al. o mula e he p oblem o choosing he VNF ins ances p o ided by a dis ibu ed se o DCs o se e a gi en se ice chain eques . The objec i e is o minimize he o e all la ency o he chain. This op imiza ion p oblem can be o mula ed as a esou ce cons ained sho es pa h p oblem. In [34] [35], Baumga ne e al. o mula e he join op imiza ion p oblem o he i ual mobile co e ne wo k opol- ogy composi ion and embedding. The o mula ion gua an ees a maximum end- o-end la ency and akes in o accoun he p ocessing, queuing, and p opaga ion delays. In [36], Bagaa e al. add ess he placemen o i ual ins ances o 4G (MME, SGW, PGW) and 5G (AMF, SMF and AUSF) co e ne wo k elemen s o e a ede a ed cloud based on Mixed In ege Linea P og amming and coali ional o ma ion game. Finally, Die ich e al. [37] o mula e a mixed-in ege linea p og am o he SGW and MME embedding. To educe i s ime complexi y, hey ans o m i in o a linea p og am by employing elaxa ion and ounding echniques. Thei p oposal mi iga es he load imbalance in oday’s mobile ne wo ks, which imp o es eques accep ance and esou ce u iliza ion. The esou ces dimensioning and embedding a e ea ed h oughou he li e a u e as sepa a e p oblems. These wo s ages o esou ces alloca ion a e closely ela ed and pe o m- ing hem in a coo dina ed way b ings bene i s. Fo ins ance, he e is a ade-o be ween he wo kload balance among a se o candida e DCs (i.e., p opaga ion delays) and he esou ces u iliza ion (i.e., p ocessing delays) when an o e all delay budge o be me is pa i ioned among hese wo s ages. He ein, we o mula e he join op imiza ion p oblem o planning he EPC o add ess his ade-o . III. SYSTEM MODEL A. Sys em A chi ec u e Le us assume an e ol ed uni e sal e es ial adio access ne wo k (E-UTRAN), al eady deployed wi h IeNBs, which p o ides connec i i y o a se o JUEs o he LTE EPC (see Fig. 1). Each UE jis a ached o an eNB i. 4 Fig. 1: E-UTRAN deploymen and ECs si es. Fig. 2: Assumed LTE ne wo k a chi ec u e. Le uji be a bina y a iable indica ing whe he he UE jis a ached o he eNB i(uji = 1) o no (uji = 0). We conside he co e age map o his E-UTRAN as a ec angula a ea A wi h heigh hand wid h w. Wi hin A, he e a e al eady deployed KECs (see Fig. 1). Le (eNB) i= (x(eNB) i, y(eNB) i)∀i∈N∩ {1, .., I}, (UE) j= (x(UE) j, y(UE) j)∀j∈N∩{1, .., J}, and (EC) k= (x(EC) k, y(EC) k)∀k∈N∩{1, .., K}deno e wo dimensional ec o s ep esen ing he posi ions o eNBs, UEs, and ECs wi hin A, espec i ely. The MME, SGW, and PGW o he EPC will be implemen ed as a se o VNFs ha makes up a ne wo k se ice [18], he ea e e e ed o as EPC, and deployed on he candida e ECs. We disca d he op ion o deploying he EPC as a single VNF wi h se e al componen s (VNFCs), since, in his wo k, we will assume ha he LTE EPC in e nal in e aces such as S11 and S5 will emain unchanged. O he EPC en i ies, such as he HSS and he PCRF, migh be loca ed ou side o he ECs and implemen ed ei he as VNFs o physical ne wo k unc ions (PNFs). The agg ega ed wo kload gene a ed by he JUEs a ached o he E-UTRAN is dis ibu ed among he Kcandida e ECs. This wo kload dis ibu ion is pe o med a he g anula i y o eNBs (i.e., each eNB iis assigned o a candida e EC k). Le ik be a bina y a iable indica ing whe he he eNB iis assigned o he EC k(i.e., ik = 1) o no (i.e., ik = 0). To se e i s co esponding wo kload, a EPC is ins an ia ed on each EC. The LTE ne wo k a chi ec u e deemed in his wo k is depic ed in Fig. 2. We conside ha he CP and DP o he EPC a e ully decoupled. Also, we assume he in e aces, be ween he CP unc ional en i ies, as he ones de ined in he 3GPP LTE s anda ds. Consequen ly, each CP en i y (e.g., Fig. 3: Wo kload gene a ion model. he MME, and he con ol unc ionali ies o he SGW and PGW -cSGW and cPGW-) a e implemen ed sepa a ely as a single VNF wi h a single componen (VNFC). The DP unc ionali ies o he SGW and PGW a e in eg a ed on a single VNF, wi h only one VNFC, ha exposes he LTE S1-U and SGi in e aces. We assume ha all VNFCs o he EPC execu e CPU-in ensi e asks. Each VNFC migh ha e mul iple ins ances. Conside ing he ETSI NFV a chi ec u al amewo k and e minology [40][18] and wi hou loss o gene ali y, each VNFC ins ance is supposedly unning on an isola ed i ual- iza ion con aine such as a VM. Le m(c) ldeno e he numbe o dedica ed physical CPU co es alloca ed o he ins ance l o he VNFC c∈C={MME, cSGW, cPGW, DP GW}. Since he numbe o CPU co es o a physical se e is ini e and he la e a e sha ed among se e al VMs, we conside ha m(c) lis limi ed o mmax (i.e., m(c) l≤mmax). B. Wo kload gene a ion model In his pape , we add ess he eMBB use case. In his con ex , he UEs un applica ions ha gene a e and consume DP a ic. We conside he abs ac ion p esen ed in [27] o such a p ocess (see Fig. 3). A session wi h du a ion Tsd is de ined as he use ’s ac i i y beginning om he ime an applica ion is launched o he ime i closes. A session consis s o Napplica ion ac i i y pe iods (AAPs) o leng h Ton sepa a ed by N−1 eading imes o du a ion D. An AAP is a ime pe iod in which he applica ion gene a es o consumes all necessa y ne wo k a ic o pe o m a gi en ask (e.g., download he p o ile o a iend, o send an ins an message). A eading ime is he empo al in e al du ing which he use pe o ms any ac ion ha does no equi e o gene a e ne wo k a ic such as deciding which iend’s p o ile o isi nex o eading a message. Rega ding he signaling wo kload, he use s’ ac i i y and mobili y igge he LTE CP p ocedu es. In his wo k, we only conside he UE- igge ed se ice eques (SR), S1-Release (S1R), X2-based Hando e (HO), and acking a ea upda e (TAU) p ocedu es. Al hough o he p ocedu es such as a ach and S1-based hando e a e hea ie in e ms o compu a ional esou ces consump ion, hey do no occu equen ly in LTE ne wo ks [41]. Once he UE is egis e ed in he ne wo k, an SR p ocedu e is igge ed du ing i s idle- o-connec ed (i.e., IDLE o ACTIVE) ansi ions. Then, whene e an AAP s a s while he UE is in idle mode, an SR p ocedu e akes place (see Fig. 3). 5 Con e sely, an S1R p ocedu e occu s du ing UE’s connec ed- o-idle ansi ions du ing which he ne wo k eleases he UE’s esou ces. We also ake in o accoun he e ec s o an inac i i y ime . I s alue is deno ed as I. The ne wo k wai s Iuni s o ime a e ha an AAP inishes be o e igge ing an S1R (see Fig. 3). A HO p ocedu e is igge ed when a UE is in connec ed mode and pe o ms a cell change, bu he a ge cell is a ached o he same MME as he sou ce cell’s. Finally, we assume ha a TAU p ocedu e is igge ed whene e a UE ca ies ou a T acking A ea (TA) change. These TAs a e p ede ined and a e he same o any UE. C. Pe o mance Requi emen s The LTE ne wo k has o mee a se o pe o mance e- qui emen s in e ms o la ency and packe loss p obabili y [42]. Fo he CP, he conside ed pe o mance equi emen is an uppe bound on he mean CP la ency T(CP ) budge de ined by he 3GPP, i.e., he a e age elapsed ime o mo e an UE om IDLE s a e o ACTIVE s a e [42]. In his wo k, we ansla e his speci ica ion as he equi ed a e age ime o ca y ou a se ice eques p ocedu e. Mo eo e , we conside he wo s - case scena io o he se ice eques p ocedu e, whe e he UE au hen ica ion, NAS (Non-Access S a um) secu i y se up, and he EPS (E ol ed Packe Sys em) session modi ica ion s eps occu du ing he SR. Le Teand Ti deno e, espec i ely, he mean esponse imes o he CP en i y e∈E= {UE, eNB, MME, cSGW, cPGW, HSS, PCRF}and he LTE in e ace i ∈IF ={Uu, S1−C, S11, S6a, S5, Gx}. The mean ime equi ed o ca y ou an SR, T(SR), in he wo s -case scena io can be compu ed as: T(SR)= 5 ·TUE + 8 ·TeNB + 5 ·TMME + 2 ·TcSGW + 2 ·TcP GW +THSS +TP CRF + 8 ·TUu + 7 ·TS1−C + 2 ·TS11 + 2 ·TS6a+ 2 ·TS5+ 2 ·TGx (1) The abo e equa ion means ha du ing an SR call low in he wo s case scena io he UE, eNB, MME, cSGW, cPGW, HSS, and PCRF en i ies ha e o p ocess, espec i ely, 5, 8, 5, 2, 2, 1, and 1 con ol messages. Also, 8, 7, 2, 2, 2, and 2 con ol messages ha e o a e se, espec i ely, he LTE Uu, S1-C, S11, S6a, S5, and Gx in e aces [43]. Then, he CP delay equi emen can be exp essed as T(SR)≤T(CP ) budge . Fo he DP, he pe o mance equi emen s conside ed a e he maximum DP delay budge T(DP ) budge and he packe loss p obabili y a he EPC P(EP C) budge . We conside T(DP ) budge as he maximum ime i akes o a packe o a el om he SGi in e ace a he SGW/PGW VNFC o he UE applica ion. The P(EP C) budge is he maximum allowable packe loss a he DPGW VNFC ecei e bu e . Le T(DP ) max and P(EP C)deno e he ac ual maximum delay o he DP and he packe loss p obabili y o he EPC, espec i ely. We can compu e T(DP ) max as: T(DP ) max =T(max) UE +T(max) eNB +T(max) DP GW +T(max) Uu +T(max) S1−U (2) whe e: T(max) UE ,T(max) eNB , and T(max) DP GW a e espec i ely he ac ual maximum DP packe p ocessing delay a he UE, eNB, and DPGW. And T(max) Uu and T(max) S1−Ua e he ac ual maximum delays o he DP adio and backhaul in e aces, espec i ely. Then, he DP equi emen s can be exp essed as T(DP ) max ≤T(DP ) budge and P(EP C)≤P(EP C) budge . IV. PROBLEM FORMULATION In his sec ion, we o mula e he join op imiza ion p oblem o dis ibu e he agg ega ed wo kload gene a ed by he E- UTRAN among he candida e ECs and o pe o m he di- mensioning o he equi ed esou ces o each EPC ins ance. Taking in o accoun he de ined sys em model, i can be o mula ed as ollows: Objec i es : minimize   |K| X k=1  |I| X i=1 |J| X j=1 ikuij −|J| |K| (3a) minimize   |K| X k=1 |I| X i=1 ik ·dik (3b) minimize   |K| X k=1 X c∈CX l m(c) l m(c) l∈N(3c) whe e dik =|| (eNB) i− (EC) k|| is he Euclidean dis ance be ween eNB iand EC k. Cons ain s : CP : C1 : T(SR) k≤T(CP ) budge ,(3d) DP : C2 : max T(DP )≤T(DP ) budge ,(3e) C3 : P(EP C)≤P(EP C) budge ,(3 ) O he s C4 : m(c) l≤mmax ∀k∈[1,|K|]∩N(3g) C5 : |K| X k=1 |I| X i=1 ik =|I|, ik ∈ {0,1}(3h) The decision a iables o he op imiza ion p oblem a e ik and m(c) l. Objec i e (3a) aims o dis ibu e he wo kload as equally as possible o o minimize he wo kload imbalances ac oss he candida e ECs. The goal is op imally achie ed when he same numbe o use s (|J|/|K|) is assigned o e e y EC k∈K. Objec i e (3b) aims o minimize he p opaga ion delays. The co esponding objec i e unc ion is minimized when e e y eNB i∈Iis assigned o he nea es EC k∗∈K, whe e k∗=a gmink∈K(dik). Las , objec i e (3c) in ends o minimize he o al numbe o CPU ins ances alloca ed o he EPC o , equi alen ly, o maximize he u iliza ion o he compu a ional esou ces. Cons ain s (3d), (3e), and (3 ) gua an ee ha he QoS equi emen s a e ul illed. Speci ically, Cons ain (3d) ensu es 6 Fig. 4: LTE con ol plane model. ha he ac ual mean delay o ca y ou a se ice eques o he EPC k(i.e., EPC ins ance unning on EC k) is lowe o equal han he mean CP la ency T(CP ) budge . Cons ain (3e) and (3 ) ensu e ha he maximum DP delay budge and he packe loss p obabili y a he EPC a e me , espec i ely. Cons ain (3g) limi s he maximum numbe o physical co es eques ed o a single VNFC ins ance. Ha ing a single VNFC ins ance would be op imal o minimizing he amoun o equi ed esou ces (s a is ical mul iplexing). Howe e , each physical se e has a maximum numbe o physical co es, i.e., he numbe o physical co es we can eques pe VNFC ins ance is limi ed. Mo eo e , in gene al, he highe is he numbe o physical co es eques ed o a VNFC ins ance, he lowe is i s a ailabili y. Finally, Cons ain (3h) gua an ees ha all eNBs a e assigned o a candida e EC k(o EPC ins ance k). V. ANALYSIS AND MODELING A. LTE CP modeling We model he CP o he LTE as an open ne wo k o G/G/m1 queues (see Fig. 4), whe e each queuing node ep esen s an ins ance o a gi en en i y o he LTE ne wo k. The MME, cSGW, and cPGW migh ha e se e al ins ances, each o which is modeled as a G/G/m queuing node wi h m(c) lse e s. The se e s o a queuing node ep esen he CPU ins ances, alloca ed o he en i y ins ance, p ocessing con ol messages in pa allel. As s a ed in Sec ion III-A, m(C) l≤mmax. Fo he sake o simplici y, only one ins ance is conside ed o he es o LTE CP en i ies (e.g., UE, eNB, HSS, and PCRF). The co esponding G/G/m queuing node ha models he ins ance o hese en i ies migh ha e an a bi a y numbe o se e s as hey migh be deployed as PNFs. The a ic sou ces a e loca ed a he eNB and he UE, since he LTE signaling p ocedu es conside ed in his wo k (e.g., SR, S1R, HO, and TAU) a e igge ed by hese en i ies. Speci ically, he TAU and SR p ocedu es a e igge ed by he UE and he S1R and HO p ocedu es a e igge ed by he eNB. In he same way, he a ic sinks a e placed a he MME ins ances. To sol e he ne wo k o queues, we employ he QNA me hod [28] which is desc ibed in Appendix A. This echnique 1In Kendall’s no a ion, a G/G/m queue is a queuing node wi h mse e s, a bi a y a i al and se ice p ocesses, FCFS (Fi s -Come, Fi s -Se ed) discipline, and in ini e capaci y and calling popula ion. was applied and alida ed in [21] o es ima e he mean esponse ime o a VNF wi h se e al VNFCs. In his wo k, we use he QNA me hod o es ima e he mean esponse imes o he LTE CP en i ies Te∀e∈E. To ha end, he QNA me hod uses a educed se o he ollowing inpu pa ame e s: •The s eady s a e ansi ion p obabili ies ma ix P= [pki], whe e pki deno es he p obabili y o a packe o lea e node k o node iand p0k= 1 −Pipki deno es he p obabili y o a packe a node k o lea e he ne wo k. In his wo k, we p o ide he exp essions o compu e P o he LTE CP ( e e o Appendix B). •The mean and squa ed coe icien o a ia ion (SCV) o he ex e nal a i al p ocesses a node k,λ0k, and c2 0k. Please no e ha only he UE and he eNB ha e ex e nal a i al p ocesses in ou model (see Fig. 4). Conside ing he abs ac ion desc ibed in sec ion III-B o he signaling gene a ion p ocess, we ound ha hese a i al p ocesses a e Poissonian (see Sec ion VIII-A). Then, c2 0k= 1 ∀k. •The mean and he SCV o he se ice p ocesses a each queue k,µkand c2 sk. B. LTE DP modeling Fo he conside ed a chi ec u e, he LTE DP consis s o h ee ne wo k en i ies namely, UE, eNB, and DPGW, which a e connec ed in andem. Since he ocus is on he EPC dimensioning, we assume ha he UE and eNB en i ies ha e cons an maximum delays. The same me hodology as applied o model he LTE CP canno be used o model he EPC DP as i can only p o ide o e all mean pe o mance me ics o a queuing ne wo k, bu no he pe o mance bounds such as hose de ined in Sec ion III-C (e.g., T(DP ) max and P(EP C)) o he DP. Mo eo e , he s ochas ic cha ac e iza ion o he agg ega ed DP a ic ca ied ou in his wo k (see Sec ion VIII-A) shows ha he EPC DP wo kload a i al p ocess exhibi s SS and LRD ea u es. Con en ional queuing heo y does no comp ise such kind o a i al p ocess [44]. Then, we model he DPGW as a single queue ed by a Bm p ocess. Mo e p ecisely, we use he model ha was i s epo ed in [22] and also de i ed in [44] om s ochas ic ne wo k calculus esul s. This model can p o ide he pe o mance bounds o a andem o queues wi h SS and LRD inpu in an e ec i e and simple way. To cha ac e ize he a i al p ocess, we adop he model p oposed in [22]. Le A deno e he cumula ing a i al p ocess o he DPGW queue, i.e., he cumula i e amoun o a ic (i.e., in numbe o packe s) a i ing a he DPGW in he ime in e al [0, ]. The ollowing model is conside ed o A [22]: A =λ· +√λ·α·Z (4) whe e Z is a no malized Bm pa ame e wi h Hu s pa ame e H∈(1/2,1],λ > 0is he mean inpu a e, and α > 0is a a iance coe icien . Unde he abo e packe a i al model and conside ing a cons an a e se e wi h capaci y C, he iola ion p obabili y =P[B > b]o a backlog bound bcan be app oxima ed as [22], [44]: ≈exp −(C−λ)2H 2·κ(H)2·λ·αb2−2H(5) 7 whe e κ(H) = HH(1 −H)1−H. The abo e equa ion gi es us an app oxima ion o he p obabili y o sa u a ion o a bu e o size bpacke s o equi alen ly he packe loss p obabili y a a queue ed wi h a Bm a i al p ocess. Finally, he maximum esponse ime o a queuing node wi h bu e size band cons an a e se e wi h capaci y Ccan be compu ed as: T(max)=b+ 1 C(6) By using (5) and (6), we can pe o m he dimensioning o he equi ed capaci y o he DPGW. VI. PES: PLANNER FOR THE EPC AS A SERVICE Algo i hm 1 PES Algo i hm Inpu : eNBs posi ions (eNB) ialong wi h he numbe o UEs hey se e NUE eNB(i) = Pjuji, and he QoS specs T(DP ) budge , P(EP C) budge , and T(CP ) budge . Ou pu : eNBs assigmen (i.e., ik), and o al numbe o p ocessing ins ances alloca ed o each EPC en i y pe EC (e.g., mMME,mcSGW ,mcP GW , and mDP GW ). 1: [NUE EC, ik]⇐Pa i ioning( (eNB),NUE eNB) 2: o each k∈Kdo 3: Compu e he p ocessing delay budge s o he EPC CP and DP, T(CP ) p oc−budge and T(DP ) p oc−budge , using (7) and (8). 4: Fo NU=NUE EC(k), es ima e he ex e nal a i al p o- cesses (λ(CP ),λ(DP ),α(DP ), and H(DP )) using (9)-(15) 5: [mMME(k),mcSGW (k),mcP GW (k),mDP GW (k)] ⇐Dimensioning(λ(CP ),λ(DP ),α(DP ),H(DP ), T(CP ) p oc−budge ,T(DP ) p oc−budge ,P(EP C) budge ) 6: end o In his sec ion, we p opose a heu is ic me hod o ind a sub-op imal solu ion o he p oblem o mula ed in Sec ion IV. To achie e a me hod wi h low-complexi y, we decouple he p ocess o wo kload dis ibu ion among he candida e ECs and he esou ces dimensioning o he EPC a each EC. The heu is ic me hod, depic ed in Algo i hm 1, p oceeds as ollows. Ini ially, he pa i ioning algo i hm assigns each eNB o a candida e EC (see Algo i hm 2). The idea in his algo i hm is o dis ibu e he wo kload as equally as possible among he candida e ECs, while gua an eeing a maximum p opaga ion delay o he backhaul ne wo k (max) p op−backhaul. The algo i hm ini ializes he wo kload assigned o each EC kNUE EC(k), which is measu ed as he numbe o assigned UEs, o ze o. Then, i i e a i ely inds he candida e EC k∗wi h he lowes wo kload alloca ed and i s nea es eNB i∗being no assigned ye . I he p opaga ion delay limi be ween he EC k∗and he eNB i∗is no iola ed, hen, he eNB i∗is a ached o he EC k∗( i∗k∗= 1). O he wise, he EC k∗is excluded om he se o candida e ECs K. The algo i hm ends when all eNBs a e alloca ed. Obse e ha , in he wo s case scena io, he algo i hm equi es NeNB +NEC i e a ions o assign all eNBs. Please no e ha he numbe o UEs a ached o each eNB is assumed o be known. On he one hand, i he E-UTRAN is in he ope a ion phase, he ope a o can know accu a ely he a e age numbe o UEs a ached o each eNB. On he o he hand, i he E-UTRAN is no in he ope a ion phase, he ope a o can es ima e he a e age numbe o UEs a ached o each eNB om he popula ion densi y map o he co e age geog aphical a ea and he expec ed ma ke sha es. Algo i hm 2 E-UTRAN Pa i ioning Algo i hm Requi e: All eNBs o he se Iha e o be assigned o an EC o he se K. Inpu : eNBs posi ions (eNB) ialong wi h he numbe o UEs hey se e NUE eNB(i) = Pjuji, he ECs posi ions (EC) k, and he maximum p opaga ion ime o he backhaul ne wo k (max) p op−backhaul. Ou pu : eNBs assigmen , i.e., ik 1: Ini ializa ion NUE EC =−→ 0, ik = 0 2: while I6=∅do 3: k∗= a g min k∈K (NUE EC(k)) 4: i∗= a g min i∈I|| (EC) k∗− (eNB) i|| 5: i || (EC) k∗− (eNB) i∗|| ≤ (max) p op−backhaul ·c hen 6: I⇐I i∗, i∗k∗= 1 7: NUE EC(k∗)⇐NUE EC(k∗) + NUE eNB(i∗) 8: else K⇐K k∗ 9: end i 10: end while Once he eNBs assignmen is ca ied ou , he p ocess- ing ime budge s o he EPC CP T(CP ) p oc−budge and DP T(DP ) p oc−budge can be compu ed. To ha end, we can e alua e T(SR)and T(DP ) max , in (1) and (2), o TMME,TcSGW , TcP GW , and T(max) DP GW , equal o ze o, espec i ely. Fo mally, T(SR) 0=T(SR)(TMME = 0, TcSGW = 0, TcP GW = 0) and T(DP ) max0=T(DP ) max (T(max) DP GW = 0). Then, T(CP ) p oc−budge =T(CP ) budge −T(SR) 0(7) T(DP ) p oc−budge =T(DP ) bugde −T(DP ) max0(8) Then, once he e is an es ima ion o he numbe o UEs o be se ed by each EC, we can also es ima e he agg ega ed ex e nal a i al p ocesses, o bo h he LTE CP and DP, which a e inpu s o he esou ces dimensioning algo i hm. We use an abs ac ion o he LTE wo kload gene a ion p ocess, along wi h a compound a ic model, o pe o m such an es ima ion. We cha ac e ize s ochas ically hese a i al p ocesses in Sec- ion VIII-A, whe e he cu e i ings a e p o ided o es ima e he main pa ame e s o model hem as a unc ion o he use s’ numbe . Finally, he esou ces dimensioning is ca ied ou (see Algo i hm 3). The dimensioning o he EPC CP and DP is pe o med sepa a ely. Since we a e conside ing only one VNFC o he EPC DP, i s dimensioning simply equi es sol ing nume ically (5). Fo he CP, we p opose a no el algo- i hm which sea ches o he minimum numbe o p ocessing ins ances o be alloca ed o he EPC CP o a gi en EC so ha a p ocessing delay budge T(CP ) p oc−budge is me . The algo i hm 8 Algo i hm 3 Dimensioning Algo i hm Inpu : P ocessing delay budge s o he EPC CP T(CP ) p oc−budge and DP T(DP ) p oc−budge ;P(EP C) budge ; Ex e nal a i al p ocesses cha ac e iza ion o CP and DP (λ(CP ), λ(DP ),α(DP ), and H(DP )). Ou pu : numbe o physical co es alloca ed o each EPC en i y mMME,mcSGW ,mcP GW , and mDP GW 1: {DATA PLANE:} 2: Sol e (5) nume ically o b≤T(DP ) p oc−budge ·C−1and ≈P(EP C) budge o ob ain he equi ed DP p ocessing capaci y C. Then, mDP GW =dC/µDP GW e. 3: {CONTROL PLANE:} 4: Ini ializa ion mMME =dλMME/µMMEe,mcSGW = dλcSGW /µcSGW e,mcP GW =dλcP GW /µcP GW e, MCP =mMME +mcSGW +mcP GW ,T(CP ) p oc = 8·TMME(mMME)+3·TcSGW (mcSGW )+2· TcP GW (mcP GW ); 5: while T(CP ) p oc > T(CP ) p oc−budge do 6: MCP ⇐MCP + 1 7: o each m∈ {mMME, ..., MCP −mcSGW − mcP GW }∩Ndo 8: o each n∈ {mcSGW , ..., MCP −mMME − mcP GW }∩Ndo 9: l=MCP −m−n 10: Taux = 8·TMME(m)+3·TcSGW (n)+2·TcP GW (l) 11: i T(CP ) p oc > Taux hen 12: T(CP ) p oc ⇐Taux,mMME ⇐m,mcSGW ⇐n, mcP GW ⇐l 13: end i 14: end o 15: end o 16: end while i e a es un il he p ocessing delay budge is ul illed. A each i e a ion, i inc emen s by one he numbe o p ocessing ins ances MCP alloca ed o he EPC CP. Fo a gi en MCP , he algo i hm explo es di e en combina ions o dis ibu e hese ins ances among he di e en VNFCs o be dimensioned (e.g., MME, cSGW, cPGW), and choose he one p o iding he lowes p ocessing delay. To achie e he linea complexi y, he sea ch space is limi ed a each i e a ion (see line 12 o Algo i hm 3). In he algo i hm, Tmme(m),TcSGW (n), and TcP GW (l)deno e, espec i ely, he mean esponse imes o he MME, cSGW, and cPGW o a gi en numbe o alloca ed p ocessing ins ances m,n, and l. These mean esponse imes a e es ima ed by using he QNA me hod ( e e o Appendix A). Please no e ha , al hough i is no explici ly included in Algo i hm 3, o each ‘p ocessing ins ances alloca ion (m, n,l), i is necessa y o e-es ima e bo h he in e nal low pa ame e s a each queue, using (16)-(22), and he ansi ion p obabili y ma ix, using (31)-(41). The numbe o ins ances o , equi alen ly, he num- be o i ualiza ion con aine s o each EPC en i y a a gi en EC can be simply compu ed as ollows: dmMME/mmaxe,dmcSGW /mmaxe, and dmcP GW /mmaxe, and dmDP GW /mmaxe. Fig. 5: Ma ko chain based model o social ne wo king. Fig. 6: Scena io ealiza ion wi h a popula ion densi y o 1000 use s pe km2. VII. EXPERIMENTAL SETUP To alida e he models de eloped in his wo k and o assess ou solu ion o EPC slices planning, we employed wo so wa e ools: i) he NSP [20], and ii) a sys em-le el simula o o an LTE ne wo k. A. Ne wo k Slice Planne We used he NSP [20] o gene a e he syn he ic signaling and da a a ic in an LTE ne wo k. We ex ended he compound a ic model o his ool by including he a ic models employed in [27]. The se up o each se ice ype (see Table II and Fig. 5) elies on models aken om he li e a u e, which a e de i ed om eal aces. Speci ically, he main e e ences used o he di e en se ices se up a e [46] o social ne wo king; [47] o Mobile Ins an Messaging; [48] o web b owsing; [49] and [45] o ideo s eaming; and [50] and [51] o ideo calls. Acco ding o [52], he se ices conside ed accoun o mo e han 70% o he peak agg ega e a ic in he Ame ican mobile access ne wo ks. The ou pu aces o he NSP we e used o cha ac e ize he agg ega e packe a i al p ocesses a he LTE CP and DP. These aces a e also used as inpu s o ou sys em-le el LTE ne wo k simula o . B. LTE ne wo k simula o The sys em-le el LTE ne wo k simula o was de eloped wi hin he NS3 en i onmen . I implemen s he messages exchange be ween he main LTE ne wo k en i ies. The aces gene a ed om he NSP a e used as inpu s o he simula o 15 APPENDIX A QNA METHOD This appendix desc ibes he main s eps ollowed by he QNA me hod o es ima e he mean esponse ime o each indi idual queue in a ne wo k o G/G/m queues. A. In e nal lows pa ame e s es ima ion As in he case o Jackson’s ne wo ks, he mean a i al a e o each queue λkcan be compu ed by sol ing he low balance equa ions: λk=λ0k+ K X i=1 λi·pik (16) The mos in e es ing aspec o he QNA me hod is ha i es ima es he Squa ed Coe icien o Va ia ion (SCV) o he agg ega ed a i al p ocess o each queue c2 ak om he ollowing se o linea equa ions: c2 ak =ak+ K X i=1 c2 aibik,1≤k≤K(17) ak= 1 + ωk(q0kc2 0k−1) + K X i=1 qik[(1 −pik) + pikρ2 ixi](18) bik =ωkqikpik(1 −ρ2 i)(19) xi= 1 + m−0.5 i(max{c2 si,0.2}−1) (20) ωk=1 + 4(1 −ρk)2(γk−1)−1(21) γk= K X i=0 q2 ik!−1 (22) whe e q0k=λ0k/λkand qik = (λi··pik)/λka e espec i ely he p opo ion o a i als o he node kcoming om i s ex e nal a i al p ocess and node i, and ρk=λk/(µk·mk)is he u iliza ion o he node k. B. Mean esponse ime compu a ion pe node Once he λkand c2 ak o he agg ega ed a i al p ocess o each node ka e es ima ed, we can compu e he mean esponse ime o each node k. I node khas only one se e (mk= 1), Tkcan be es ima ed as: Tk=ρk·(c2 ak +c2 sk)·β 2·µk(1 −ρk)+1 µk (23) wi h β=(exp(−2·(1−ρk)·(1−c2 ak )2 3·ρk·(c2 ak +c2 sk ))c2 ak <1 β= 1 c2 ak ≥1(24) I , by con as , he node kis a GI/G/m queue (mk=m), Tkcan be es ima ed as: Tk= 0.5·c2 ai +c2 si·WM/M/m k+1 µk (25) whe e WM/M/m kis he mean wai ing ime o a M/M/m queue, and can be compu ed as: WM/M/m k=C(mk,λk µk) mkµk−λk (26) and C(m, ρ) ep esen s he E lang’s C o mula which has he ollowing o mula ion: C(m, ρ) = (m·ρ)m m!·1 1−ρ Pm−1 k=0 (m·ρ)k k!+(m·ρ)m m!·1 1−ρ(27) APPENDIX B TRANSITION PROBABILITIES FOR THE LTE CP QUEUING MODEL This appendix includes exp essions o compu e he ansi- ion p obabili ies o he p oposed LTE CP queuing model. Le VEdeno e he isi a io o he CP en i y E∈ {UE, eNB, MME, cSGW, cP GW, HSS, PCRF}which is de ined as he a e age numbe o isi s o en i y Eby a sig- naling p ocedu e du ing i s li e ime in he ne wo k. Fo mally, VE=λE/PEλ0E=λE/(λ0UE +λ0eNB). Please no e ha VEis equal o he a e age numbe o packe s o be p ocessed by he LTE CP en i y Epe con ol p ocedu e. Then, VE=PCP λCP ·n(E) CP PCP λCP (28) whe e n(E) CP is he numbe o packe s o be p ocessed by he LTE CP en i y E o he con ol p ocedu e CP ∈ {SR, S1R, HO, TAU}. The isi a ios and he ansi ion p obabili ies a e ela ed h ough (16) ( low balance equa ions): VE=λ0E PEλ0E +X E VE·pE1→E2(29) The ansi ion p obabili ies also sa is y p0E1+X E2 pE1→E2= 1 (30) Assuming ha he wo kload is dis ibu ed among he ins ances o he VNFCs (e.g., MME, cSGW, and cPGW), acco ding o hei capaci ies, i.e., VEl=m(E) l/(Plm(E) l)·VE, and using (29) and (30), we can compu e he ansi ion p obabili ies o ou LTE CP queuing model by he ollowing equa ions: peNB UE = VUE −λ(U E) 0 PEλ(E) 0 VeNB (31) peNB MMEl=m(MME) l Plm(MME) l·(1 −peNB UE )(32) pMMEl eNB = VeNB −λ(eN B) 0 PEλ(E) 0−VUE VMME (33) pMMEl cSGWl= m(cSGW ) l Plm(cSGW ) n·1−pMMEl eNB −pMMEl HSS −1 VMME (34) 16 pMMEl HSS =VHSS VMME (35) pcSGWl MMEl=m(MME) l Pmm(MME) m· 1−X l pcSGWl cP GWl!(36) pcSGWl cP GWl=m(cP GW ) l Pmm(cP GW ) m·(VP GW −VP CRF ) VSGW (37) pcP GWl cSGWl=m(cSGW ) l Pmm(cSGW ) m·1−VP CRF VP GW (38) pP GWl P CRF =VP CRF VP GW (39) pHSS MMEl=m(MME) l Pmmm (40) pP CRF cP GWl=m(cP GW ) l Pnm(cP GW ) n (41) Please no e ha he ansi ion p obabili ies depend on he a e age numbe o packe s o be p ocessed o each LTE CP en i y pe con ol p ocedu e, which is equal o he isi a io o he en i y; he ex e nal a i al p ocesses λ0UE and λ0eNB; and he numbe o p ocessing ins ances assigned o each VNFC ins ance m(C) l.