An adaptive offloading decision scheme in two-class mobile edge computing systems

Abstract

˙Internet'e ba˘glı cihaz sayısında ve toplam veri trafi˘ginde görülen önemli artı¸slabirlikte bulut servislerinin yakın gelecekte ciddi yüklerle kar¸sı kar¸sıya kalmasıbeklenmektedir. Bunun üstesinden gelinebilmesi amacıyla kenar bili¸sim sistemleriönerilmi¸stir. Kenar bili¸sim sistemlerinde, a˘gın kenarında yer alan eri¸sim noktası veyabaz istasyonu gibi cihazların mobil cihazlarda ortaya çıkan hesaplama i¸slerinin birbölümünü yürüterek, sonucunu cihazda kullanılması gerekti˘gi durumda cihaza, bulutagönderilmesi gerekti˘gi durumda ise buluta yönlendirmesi öngörülmektedir. Hesaplamakaynaklarının merkezi buluttan a˘g kenarına do˘gru getirildi˘gi bu yöntemle birlikte hembuluttaki i¸s yükünün azaltılması, hem de gecikme sürelerinin azaltılması mümkünolabilecektir.Aktarma problemi, bir mobil cihazda ortaya çıkan bir hesaplama i¸sinin lokalolarak mobil cihazda mı yoksa kenar sunucuda mı yürütülece˘gi kararının verilmesiproblemidir. Literatürde çe¸sitli parametreleri göz önüne alan aktarma algoritmalarıönerilmi¸stir. Sık kullanılan parametreler arasında gecikme zamanı, enerji tüketimi,ve bunların hibrit olarak eniyilenmesi sayılabilir. Literatürde yer alan çalı¸smalarıayıran farklılıklar, eniyileme hedef fonksiyonunun yanı sıra, incelenen sistemdede yatmaktadır. Bir i¸slem, aktarım yapıldı˘gında tamamen kenar sunucusunadevrediliyorsa, bu ikili aktarım olarak adlandırılır. Öte yandan, bazı i¸slemler, parçalaraayrılarak kısmen mobil cihazda, kısmen de kenar sunucusunda yürütülebilir. Buyöntem ise kısmi aktarım olarak adlandırılır. Kısmi aktarımın verimli i¸slemesi içinhesaplama i¸sinin karakteristi˘ginin detaylı olarak bilinmesi gereklidir. Bu amaç için,hesaplama i¸sinin alt parçalarının birbirlerine ba˘gımlılıklarını gösteren ça˘grı çizgelerikullanılır. Verili bir ça˘grı çizgesi için en iyi kısmi aktarım çözümü üretmeyi hedefleyenalgoritmalar literatürde mevcuttur. Bunun yanısıra, birden fazla kenar sunucusuoldu˘gunu varsayan, mobil kullanıcı davranı¸sının statik veya rassal oldu˘gunu varsayan,sunucunun ve/veya mobil kullanıcıların enerji tüketimini azaltmayı önceleyen, vefarklı enerji tüketim modelleri kullanan çe¸sitli çalı¸smalar da bulunmaktadır. Tümbu çalı¸smalarda matematiksel araç olarak genellikle eniyileme kuramı veya oyunkuramından yararlanıldı˘gı görülmektedir.Bu çalı¸smada, tek kenar sunucusu olan bir sistemde, hesaplama i¸si üretme bakımındanrassal davranan mobil cihazların, yüksek ve dü¸sük öncelikli iki sınıfa ayrıldıkları birsenaryo incelenmi¸stir. ˙Ikili aktarım uygulandı˘gı varsayılmı¸stır. Aktarım kriteri olarakhesaplama i¸sinin üretildikteki andan itibaren, hesaplanıp kenar sunucusuna aktarıldı˘gıana kadar geçen sürenin enküçüklenmesi seçilmi¸stir. Bu senaryoda artırılmı¸sgerçeklik, sanal gerçeklik, çevrimiçi oyun, veya video görü¸sme gibi bir çokluortamuygulamasının video kodlama i¸sleri üretti˘gi varsayılmı¸stır. Kodlama sonucu ortayaçıkan veri, ham veriden küçüktür. Dolayısıyla, aktarım yapılmadı˘gı durumdahesaplama i¸sinin sistemde geçirdi˘gi süre, videonun mobil cihazda kodlanması ve kodlanmı¸s verinin kenar sunucusuna gönderilmesi için geçen süredir. Buna kar¸sılık,aktarım yapıldı˘gında bu süre, ham videonun kenar sunucusuna gönderilmesi ve buradakodlanmasından olu¸sacaktır.Kenar sunucusunda a˘gırlıklı round-robin çizelgeleme yapıldı˘gı varsayılmı¸stır. Bunagöre sunucuda servis alan aynı sınıfa ait hesaplama i¸sleri, küçük periyotlarda e¸sitmiktar servis alırlar. Buna kar¸sılık yüksek öncelikli i¸sler, her roundda dü¸sük öncelikliolanların h katı kadar hizmet alır. Round robin çizelgeleme, zaman biriminin sıfıragitti˘gi limit durumunda i¸slemci-payla¸sımı modeline dönü¸sür. Kuyruk kuramındanbilindi˘gi üzere, i¸slemci-payla¸sımı sistemlerinde herbir i¸sin sistemde kalma zamanı, i¸sinuzunlu˘gu ile do˘gru orantılıdır. Bu bakımdan, her bir i¸s için aktarım kararı verilirkenhesaplanması gereken sunucuda geçen hesaplama zamanı, bir kuyruklama katsayısıile modellenebilir. Bu kuyruklama katsayısı, dü¸sük öncelikli kullanıcılar için yükseköncelikli kullanıcılara göre h kat büyük alınmaktadır. Böylece bu katsayı ile hem birkabul mekanizması, hem de servis ayrımı gerçekle¸stirilmi¸stir.Bu sistem modeli için bir benzetim programı yazılmı¸s ve çe¸sitli senaryolar için sayısalsonuçlar elde edilmi¸stir. Öncelikli olarak iki sınıf arasında hizmet kalitesi ayrımınısa˘glayabilecek, ancak yüksek öncelikli i¸slerin performansını dü¸sürmeyecek en iyikuyruklama katsayısının bulunması için, bu katsayını çe¸sitli de˘gerleri için sistemdekalınan ortalama süre istatisti˘gi elde edilmi¸stir. Buna göre örnek bir senaryoda bukatsayının alması gereken de˘ger hakkında çıkarımlar yapılmı¸stır. Ayrıca aynı senaryoiçin mobil cihazın enerji tüketimi grafikleri de elde edilmi¸stir. Bu senaryoda hparametresinin ba¸sarıma etkisi de incelenmi¸s ve bir üst sınır bulunmu¸stur.Her senaryo için bu katsayının en iyi de˘gerinin de˘gi¸sece˘gi açıktır. Bu bakımdan buen iyi de˘geri yakalayan uyarlanır bir algoritma önerilmi¸stir. Bu algoritmaya göre,bu katsayı ilk de˘geri 1 olmak üzere çalı¸smaya ba¸slanır. Her bir i¸slem sistemi terketti˘ginde, sistemde kaldı˘gı süre, i¸sin uzunlu˘guna bölünerek bu i¸sin deneyimledi˘gikatsayı de˘geri elde edilir. Bu de˘ger kullanılarak, katsayı de˘geri güncellenir. Buyöntemin sistem dinamiklerini yakaladı˘gı ve de˘gi¸sken senaryolarada uyum gösterdi˘gigösterilmi¸stir. Bu senaryoda, de˘gi¸sen i¸s yükleri, yüksek öncelikli mobil kullanıcı sayısıve h parametresi de˘gerleri için sonuçlar elde edilmi¸stir.Daha gerçekçi i¸s üretim modellerinin yer aldı˘gı modeller, ve enerji tüketiminin deaktarım kararına entegre edildi˘gi algoritmalar, gelecek çalı¸smaların konusu olacaktır.

With the huge growth of data exchange and the increasing number of connecteddevices to the Internet, Mobile Cloud Computing (MCC) paradigm with its centralizedapproach will face tremendous loads. Therefore; the European TelecommunicationStandard Institute (ETSI) came up with a new idea to overcome the problem of latencymainly and decrease the consumed energy of transmission. This new approach, MobileEdge Computing (MEC), is proposed to use the capacity at the edge of the networksuch as Base Station (BS) or Access Point (AP). In this way, the amount of sent datato the cloud will be significantly reduced by having the edge server executing all theoffloaded tasks on behalf of mobile users.In mobile edge computing, the system can be modelled as a single-class MEC systemwhich considers all the tasks as the same (no differentiation in terms of priorities),or a multi-class system. In a multi-class system, the tasks originating from differentmobiles may have different priorities. In case of a two-class system, there will be highand low priorities.In this study, we investigate the offloading problem in the presence of two user classes:one is high priority and the other is low priority. The tasks are generated by mobileusers and are offloaded to the edge server to be executed. We assume that the serveris in charge of making offloading decisions. A task is decided to be offloaded or notbased on the comparison between sojourn time in case of local execution (at the mobiledevice) and sojourn time in case of remote execution (at the edge server). The task isoffloaded if the sojourn time in case of remote execution is smaller.We assume that the edge server employs weighted Round-Robin (WRR) processorscheduling, which can be modeled as a priority Proessor Sharing (PS) queue if thetime slots are considered to be small. (WRR) uses the same principle of Round Robin,which is basically sharing the CPU service among all the packets for a specific numberof time slots (Machine Cycles (MC) in case of CPU scheduling) without consideringthe priorities of arrived tasks. On the other hand, WRR takes into account the prioritiesof the tasks. In WRR, a high priority task is served more frequently than others. Toput it another way, a high priority task receives more MCs than lower priority tasks.It is known that the expected sojourn time in a PS queue is linearly proportional tothe task size. Therefore; we use a factor (queueing delay multiplier) that accuratelycaptures the sojourn time of an offloaded task. The queueing delay multiplier bothmodels and affects the queueing delay, and thus acts as an admission rule parameter. Ifthe multiplier is too high, tasks are discouraged to offload, resulting in a lightly loadedMEC server which entails a low multiplier value. On the other hand, a too low value forthe multiplier will result in more offloads, yielding high queueing delays. Therefore,there should be an optimal queueing delay multiplier value that balances the demandfor the MEC server.We propose an adaptive scheme that finds an optimum value for the queueing delaymultiplier on the fly, using damped averaging. We show that high priority usersexperience much lower average sojourn times compared to the low priority users. Wealso illustrate the effect of our method on the energy consumption of the mobile. Usinga stand-alone simulator, we demonstrate the performance of the proposed method inseveral different scenarios with numerical experimentation.