Basic Search / Detailed Display

Author: 江岳亭
Yueh-Ting Chiang
Thesis Title: 在雲、邊緣、使用者裝置聯合系統中考慮邊緣伺服器故障之卸載: 設計、分析與最佳化
Offloading in the Cloud, Edge, and UE Federated System with Consideration of Edge Server Failure: Design, Analysis, and Optimization
Advisor: 馮輝文
Huei­-Wen Ferng
Committee: 馮輝文
Huei­-Wen Ferng
范欽雄
Chin-Shyurng Fahn
葉生正
Sheng-Cheng Yeh
郭芳璋
Fang‑Chang Kuo
Degree: 碩士
Master
Department: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2021
Graduation Academic Year: 109
Language: 中文
Pages: 172
Keywords (in Chinese): 工作卸載邊緣伺服器故障服務品質違反機率多接取邊緣運算最佳化
Keywords (in other languages): Task Offloading, Edge Server Failure, QoS Violation Probability, Multi­-Access Edge Computing, Optimization
Reference times: Clicks: 365Downloads: 0
Share:
School Collection Retrieve National Library Collection Retrieve Error Report

工作卸載 (Task Offloading) 是多接取邊緣運算 (Multi-Access Edge Computing, MEC) 的一項關鍵技術,此項技術透過將使用者裝置 (User Equipment, UE)產生的工作卸載到其他資源更豐富的伺服器,以解決行動設備硬體條件不足及資源有限的問題。工作卸載能降低行動設備的工作處理時間,並減少電量的消耗。 目前工作卸載之研究大部分考慮如何最小化工作的延遲,少數研究考量工作延 遲的門檻限制; 另一方面,過去與工作卸載之研究均假設伺服器不會發生故障。因此,本論文除了同時針對工作延遲是否超過門檻做考量,更進一步考量邊緣 伺服器故障率是否超過門檻,以達更周延之考量; 並設計當邊緣伺服器故障時的 五種解決機制,第一種是替 [1] 考量邊緣伺服器故障所設計的一種基準機制,第 二、三種是則以 Wu 等人 [2] 的概念做延伸而設計之兩種機制,最後兩種方法為本論文全新提出的機制,採用備用伺服器,以解決主邊緣伺服器故障的問題。針對此五種機制,相關之數理分析均將提供,以利做最佳化之問題形成 (Problem Formulation)。在模擬驗證數理分析後,透過數理分析可獲大量之數值觀察與討論,我們全新提出的兩種機制相較於其他機制,更能滿足服務品質 (Quality of Service, QoS) 表現優越,最為被推薦使用。


Task offloading is a key technology of multi-access edge computing (MEC). This technology solves the problem of the user equipment (UE) with limited resources by offloading its tasks to the other servers with more resources. Task offloading can reduce the task delay of mobile devices and reduce the power consumption. Up to now, many studies consider how to minimize the task delay simply without consider whether the task delay has exceeded its associated threshold or not. On the other hand, those studies assume that the servers will not collapse. Therefore, this thesis will focus on whether the task delay exceeds its associated threshold and whether the edge server failure rate exceeds its associated threshold. Towards this goal, five schemes to solve the offloading problem with the edge server failure are to be proposed. The first one serves a benchmark mechanism designed for this issue extending the concept of \cite{hwang2021offloading} Two schemes are designed for this issue by extending the concept of \cite{wu2018performance}. As for the remaining two schemes are the brand new schemes by utilize the spare/dispatch edge server for this issue. For these five schemes, the corresponding mathematical analysis will be done to facilitate the corresponding optimization problem. After validation by simulations, our mathematical analysis afford extensive numerical results and observation to successfully demonstrate that our two brand new proposed schemes are more capable of satisfying the quality of service (QoS) than the other schemes and are highly recommended for use

論文指導教授推薦書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 考試委員審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 英文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 表目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 圖目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii 第一章、緒論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 研究背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 行動雲端運算 (MCC) . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 多接取邊緣運算 (Multi­Access Edge Computing, MEC) . . . . . . . 2 1.3.1 MEC 架構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 5G 中的 MEC . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 工作卸載 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 研究動機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 論文組織 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 第二章、相關文獻回顧 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1 單一伺服器卸載之相關文獻 . . . . . . . . . . . . . . . . . . . . . . 12 2.2 聯合架構卸載之相關文獻 . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 卸載失敗之相關文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . 15 第三章、機制設計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1 問題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 環境架構及模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 回復機制設計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3.1 TDT 之機制設計 . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.2 RED 之機制設計 . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.3 REI 之機制設計 . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.4 SER 之機制設計 . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3.5 SDE 之機制設計 . . . . . . . . . . . . . . . . . . . . . . . . 29 第四章、系統效能分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1 服務品質違反機率分析 . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1.1 TDT 之服務品質違反機率分析 . . . . . . . . . . . . . . . . 33 4.1.2 RED 之服務品質違反機率分析 . . . . . . . . . . . . . . . . 36 4.1.3 REI 之服務品質違反機率分析 . . . . . . . . . . . . . . . . 37 4.1.4 SER 之服務品質違反機率分析 . . . . . . . . . . . . . . . . 40 4.1.5 SDE 之服務品質違反機率分析 . . . . . . . . . . . . . . . . 42 4.2 平均工作延遲分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2.1 TDT 之平均工作延遲分析 . . . . . . . . . . . . . . . . . . . 44 4.2.2 RED 之平均工作延遲分析 . . . . . . . . . . . . . . . . . . . 45 4.2.3 REI 之平均工作延遲分析 . . . . . . . . . . . . . . . . . . . 45 4.2.4 SER 之平均工作延遲分析 . . . . . . . . . . . . . . . . . . . 46 4.2.5 SDE 之平均工作延遲分析 . . . . . . . . . . . . . . . . . . . 48 4.3 平均服務停止時間分析 . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3.1 TDT 之平均服務停止時間分析 . . . . . . . . . . . . . . . . 49 4.3.2 RED、REI 之平均服務停止時間分析 . . . . . . . . . . . . 49 4.4 工作遺失機率分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4.1 TDT 之工作遺失機率分析 . . . . . . . . . . . . . . . . . . . 51 4.4.2 RED、REI 之工作遺失機率分析 . . . . . . . . . . . . . . . 51 第五章、數值分析結果與討論 . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.1 模擬與分析之間的驗證 . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2 參數設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.3 情境一: 高通訊鏈路容量 . . . . . . . . . . . . . . . . . . . . . . . . 57 5.3.1 在低故障率情況下之不同門檻參數設定之效能 . . . . . . . . 57 5.3.2 在高故障率情況下之不同門檻參數設定之效能 . . . . . . . . 75 5.4 情境二: 低通訊鏈路容量之效能 . . . . . . . . . . . . . . . . . . . . 90 5.4.1 在低故障率情況下之不同門檻參數設定之效能 . . . . . . . . 90 5.4.2 在高故障率情況下之不同門檻參數設定之效能 . . . . . . . . 107 5.5 不同故障率門檻 ϕ、不同工作延遲門檻 δ、不同平均故障率及不同 邊緣伺服器容量之效能影響 . . . . . . . . . . . . . . . . . . . . . . 122 5.5.1 不同故障率門檻 ϕ 設定之效能影響 . . . . . . . . . . . . . . 122 5.5.2 不同工作延遲門檻 δ 設定之效能影響 . . . . . . . . . . . . . 124 5.5.3 不同平均故障率設定之效能影響 . . . . . . . . . . . . . . . . 129 5.5.4 不同邊緣伺服器容量設定之效能影響 . . . . . . . . . . . . . 133 第六章、結論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 附錄 A:QoS violation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 A.1 單一節點佇列考量工作延遲的服務品質違反機率 . . . . . . . . . . . 143 A.2 三個節點串聯佇列考量工作延遲的服務品質違反機率 . . . . . . . . 143 A.3 四個節點串聯佇列考量工作延遲的服務品質違反機率 . . . . . . . . 144 A.4 五個節點串聯佇列考量工作延遲的服務品質違反機率 . . . . . . . . 145 附錄 B:次梯度搜尋 (Sub­Gradient Search, SGS) 演算法 . . . . . . . . . . 148 附錄 C:各機制平均工作延遲 . . . . . . . . . . . . . . . . . . . . . . . . . . 150 C.1 No f ailure 之各路徑平均工作延遲之推導結果 . . . . . . . . . . . . 150 C.2 TDT 之各路徑平均工作延遲之推導結果 . . . . . . . . . . . . . . . 151 C.3 RED 之各路徑平均工作延遲之推導結果 . . . . . . . . . . . . . . . 151 C.4 REI 之各路徑平均工作延遲之推導結果 . . . . . . . . . . . . . . . 152 C.5 SER 之各路徑平均工作延遲之推導結果 . . . . . . . . . . . . . . . 153 C.6 SDE 之各路徑平均工作延遲之推導結果 . . . . . . . . . . . . . . . 155

[1] R.¬H. Hwang, Y.¬C. Lai, and Y.¬D. Lin, “Offloading optimization with delay distribution in the 3-¬tier federated cloud, edge, and fog systems,” IEEE, Nov. 2019.
[2] H. Wu, “Performance modeling of delayed offloading in mobile wireless environments with failures,” IEEE Communications Letters, vol. 22, no. 11, pp. 2334–2337, Aug. 2018.
[3] U. Cisco, “Cisco annual internet report (2018–2023) white paper,” Mar. 2020.
[4] T. F. da Silva Pinheiro, F. A. Silva, I. Fé, S. Kosta, and P. Maciel, “Performance prediction for supporting mobile applications’ offloading,” Journal of Supercomputing, vol. 74, no. 8, pp. 4060–4103, May. 2018.
[5] Z. Wang, Z. Zhao, G. Min, X. Huang, Q. Ni, and R. Wang, “User mobility aware task assignment for mobile edge computing,” Future Generation Computer Systems, vol. 85, pp. 1–8, Aug. 2018.
S. K. uz Zaman and M. A. Tahir Maqsood and K. Bilal, “A load balanced task scheduling heuristic for large¬scale computing systems,” Comput. Syst. Sci. Eng., vol. 34, no. 2, pp. 79–90, Mar. 2019.
[7] H. Guo and J. Liu, “Collaborative computation offloading for multiaccess edge computing over fiber–wireless networks,” IEEE Transactions on Vehicular Technology, vol. 67, no. 5, pp. 4514–4526, Jan. 2018.
[8] F. Liu, P. Shu, H. Jin, L. Ding, J. Yu, D. Niu, and B. Li, “Gearing resource poor mobile devices with powerful clouds: Architectures, challenges, and applications,” IEEE Wireless Communications, vol. 20, no. 3, pp. 14–22, July. 2013.
[9] B. Liu, X. Xu, L. Qi, Q. Ni, and W. Dou, “Task scheduling with precedence and placement constraints for resource utilization improvement in multi¬user MEC environment,” Journal of Systems Architecture, vol. 114, no. 6, DEC. 2020.
[10] P. Ranaweera, A. D. Jurcut, and M. Liyanage, “Realizing multi¬access edge computing feasibility: Security perspective,” in Proc. IEEE Conference on Standards for Communications and Networking (CSCN), pp. 1–7, Oct. 2019.
[11] M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies, “The case for VM-based cloudlets in mobile computing,” IEEE Pervasive Computing, vol. 8, no. 4, pp. 14–23, Oct. 2009.
[12] Y. C. Hu, M. Patel, D. Sabella, N. Sprecher, and V. Young, “Mobile edge computing ¬A key technology towards 5G,” ETSI white paper, vol. 11, no. 11, pp. 1–16, Sept. 2015.
[13] S. Kekki, W. Featherstoneand Y. Fang, P. Kuure, A. Liand A. Ranjan, D. Purkayastha, F. Jiangping, D. Frydman, G. Verin, K.¬W. Wen, K. Kim, R. Arora, A. Odgers, L. Contreras, and S. Scarpina, “MEC in 5G networks,” ETSI white paper, vol. 28, no. 28, pp. 1–28, June 2018.
[14] P. Mach and Z. Becvar, “Mobile edge computing: A survey on architecture and computation offloading,” IEEE Communications Surveys & Tutorials, vol. 19, no. 3, pp. 1628–1656, Jan. 2017.
[15] M. ETSI, “Mobile edge computing (MEC): Framework and reference architecture,” ETSI, DGS MEC, vol. 3, no. 3, Mar. 2016.
[16] I. Parvez, A. Rahmati, I. Guvenc, A. I. Sarwat, and H. Dai, “A survey on low latency towards 5G: RAN, core network and caching solutions,” IEEE Communications Surveys & Tutorials, vol. 20, no. 4, pp. 3098–3130, May. 2018.
[17] 3GPP, “Release 14 Description; Summary of Rel¬14 Work Items,” Technical Specification (TS) TR 21.914, 3rd Generation Partnership Project (3GPP), May. 2018.
[18] Y. Wang, X. Tao, X. Zhang, P. Zhang, and Y. T. Hou, “Cooperative task offloading in three-¬tier mobile computing networks: An ADMM framework,” IEEE Transactions on Vehicular Technology, vol. 68, no. 3, pp. 2763–2776, Jan. 2019.
[19] W. Fang, S. Ding, Y. Li, and W. Zhouand N. Xiong, “OKRA: Optimal task and resource allocation for energy minimization in mobile edge computing systems,” Wireless Networks, vol. 25, no. 5, pp. 2851–2867, May 2019.
[20] Y. Li and C. Jiang, “Distributed task offloading strategy to low load base stations in mobile edge computing environment,” Computer Communications, vol. 164, no. 2, pp. 240–248, Dec. 2020.
[21] H. Wang, X. Li, H. Ji, and H. Zhang, “Federated offloading scheme to minimize latency in mec¬enabled vehicular networks,” in Proc. IEEE Globecom Workshops (GC Wkshps), pp. 1–6, Dec. 2018.
[22] C. Shu, Z. Zhao, Y. Han, G. Min, and H. Duan, “Multi¬user offloading for edge computing networks: A dependency¬-aware and latency-¬optimal approach,” IEEE Internet of Things Journal, vol. 7, no. 3, pp. 1678–1689, Sept. 2019.
[23] J. Liang, K. Li, C. Liu, and K. Li, “Joint offloading and scheduling decisions for DAG applications in mobile edge computing,” Neurocomputing, vol. 424, no. 99, pp. 160–171, Feb. 2021.
[24] T. Mori, Y. Utsunomiya, X. Tian, and T. Okuda, “Queueing theoretic approach to job assignment strategy considering various inter¬arrival of job in fog computing,” in Proc. IEEE Asia¬Pacific Network Operations and Management Symposium (APNOMS), pp. 151–156, Sept. 2017.
[25] M. Adhikari, M. Mukherjee, and S. N. Srirama, “DPTO: A deadline and priority-aware task offloading in fog computing framework leveraging multilevel feedback queueing,” IEEE Internet of Things Journal, vol. 7, no. 7, pp. 5773–5782, Oct. 2019.
[26] M. Mukherjee, S. Kumar, C. X. Mavromoustakis, G. Mastorakis, R. Matam, V. Kumar, and Q. Zhang, “Latency¬-driven parallel task data offloading in fog computing networks for industrial applications,” IEEE Transactions on Industrial Informatics, vol. 16, no. 9, pp. 6050–6058, Dec. 2019.
[27] R.¬H. Hwang, M. M. Islam, M. A. Tanvir, M. S. Hossain, and Y.¬D. Lin, “Communication and computation offloading for 5G V2X: Modeling and optimization,” in Proc. IEEE Global Communications Conference (GLOBECOM), pp. 1–6, Dec. 2020.
[28] P. Le Nguyen, R.¬H. Hwang, P. M. Khiem, K. Nguyen, and Y.¬D. Lin, “Modeling and minimizing latency in three¬-tier V2X networks,” in Proc. IEEE Global Communications Conference (GLOBECOM), pp. 1–6, Dec. 2020.
[29] M. Chen, S. Guo, K. Liu, X. Liao, and B. Xiao, “Robust computation offloading and resource scheduling in cloudlet¬-based mobile cloud computing,” IEEE Transactions on Mobile Computing, vol. 20, no. 5, pp. 2025–2040, Feb. 2020.
[30] Q. Wang and K. Wolter, “Accelerating task completion in mobile offloading systems through adaptive restart,” Software & Systems Modeling, vol. 17, no. 2, pp. 397–413, May 2018.
[31] A. P. Van Moorsel and K. Wolter, “Analysis of restart mechanisms in software systems,” IEEE Transactions on Software Engineering, vol. 32, no. 8, pp. 547–558, Sept. 2006.
[32] Y. Xiao, Z. Ren, H. Zhang, C. Chen, and C. Shi, “A novel task allocation for maximizing reliability considering fault¬-tolerant in vanet real time systems,” in Proc. IEEE Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), pp. 1–7, Feb. 2017.
[33] K. V. Vishwanath and N. Nagappan, “Characterizing cloud computing hard ware reliability,” in Proc. SoCC ’10, pp. 193–204, 2010.
[34] A. M. Law, Simulation Modeling & Analysis. New York, NY, USA: McGraw Hill, 4 ed., 2015.
[35] C. Chen, G. Eisenhauer, S. Pande, and Q. Guan, “CARE: Compiler¬-assisted recovery from soft failures,” in Proc. International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’19, Nov. 2019.

無法下載圖示 Full text public date 2024/10/29 (Intranet public)
Full text public date 2024/10/29 (Internet public)
Full text public date 2024/10/29 (National library)
QR CODE