臺灣博碩士論文加值系統

隨著5G以及物聯網的推出，新興的服務通常對網路條件有多種嚴格的需求。而在結合網絡功能虛擬化(NFV)的彈性及可擴展性和多接取邊緣計算(MEC)技術的超低延遲特性的環境下，這些服務的需求可以被滿足。然而，邊緣伺服器供給商(ESP)若單獨行動，通常會因資源容量、成本、佈署地理位置等限制，使得可接受服務請求有限且無法有效利用資源，造成效益低落。若形成供應商能夠聯盟則可以互取所需，創造全體最大效益。在本文中，我們建立ESP之間的合作模型，並提出一種鬆弛問題的方案來解決聯盟建立過程中遭遇的外部性問題。另外我們提出了基於利潤的貪婪式演算法以及模擬退火的方式使ESP之間能夠合適的結盟，模擬實驗結果呈現出這兩種方法在大部分的情況下的全體利益能勝過其他單純的策略。最後，我們分析了在聯盟賽局中不同的利益分配方法在我們的模型中的表現，在具有外部性以及不具有外部性的情況下，這些方法的優劣不同。

Emerging network services usually have a variety of service requirements. These requirements can be met by coupling scalability and flexibility of network function virtualization (NFV) and ultra-low latency ability of multi-access edge computing (MEC). However, a single edge service provider (ESP) alone can serve only a limited number of service requests due to resource capacity, cost, geographical location and other constraints. If two or more ESPs can be federated for resource and payoff sharing, they may collectively earn more profit than the sum of individual profits when they operate independently. In this thesis, we study profit-optimal resource allocation for network services in every possible federation of ESPs, for which we propose a relaxation strategy to deal with possible conflicts of allocations among federations. Based on that, we propose a profit-based greedy algorithm and simulated annealing method to partition a set of ESPs into disjoint federations such that the total profit is maximized. The results of simulation show that the total profit of our methods outperformed other simple strategies in most cases. Finally, we analyzed the payoff satisfaction level of each ESP using three well-known payoff distribution rules in coalitional game. The results indicate that the performance of these methods depends on the existence of externalities.

1 Introduction 1
2 Related Work 4
3 System Model and Problem Formulation 7
3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Social Welfare Maximization . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2 Minimizing the Level of Dissatisfaction . . . . . . . . . . . . . . . . 12
4 Proposed Mechanisms 14
4.1 Characteristic Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.1 Externalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.2 Relaxed Characteristic Function (RCF) . . . . . . . . . . . . . . . 16
4.2 Forming a Coalition Structure . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2.1 Coalition Value-based Greedy with RCF . . . . . . . . . . . . . . . 18
4.2.2 Simulated Annealing with RCF . . . . . . . . . . . . . . . . . . . . 19
4.3 Profit Allocation Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3.1 Shapley Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3.2 Normalized Banzhaf Value . . . . . . . . . . . . . . . . . . . . . . . 22
4.3.3 Nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 Simulation Results 24
5.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2.1 Method Errors of the Relaxation . . . . . . . . . . . . . . . . . . . 25
5.2.2 Simulation of Scattered Resources . . . . . . . . . . . . . . . . . . . 26
5.2.3 Effects of Uneven Resources Distribution . . . . . . . . . . . . . . . 27
5.2.4 Effects of Maintenance Cost of Cooperation . . . . . . . . . . . . . 29
5.2.5 Effects of Resources Costs With Different Standard Deviations . . . 29
5.2.6 The Effect of the Number of Requests . . . . . . . . . . . . . . . . 30
5.2.7 Coalitions’ Dissatisfaction Levels Under Three Different Mechanisms 31
6 Conclusion 33
References 34

[1] M. Chiosi, D. Clarke, P. Willis, A. Reid, J. Feger, M. Bugenhagen, W. Khan, M.
Fargano, C. Cui, H. Deng, et al., “Network functions virtualisation introductory
white paper,” in SDN and OpenFlow World Congress, 2012.
[2] T. Taleb, K. Samdanis, B. Mada, H. Flinck, S. Dutta, and D. Sabella, “On multiaccess
edge computing: A survey of the emerging 5g network edge cloud architecture
and orchestration,” IEEE Communications Surveys & Tutorials, vol. 19, no. 3,
pp. 1657–1681, 2017.
[3] S. Mehraghdam, M. Keller, and H. Karl, “Specifying and placing chains of virtual
network functions,” in 2014 IEEE 3rd International Conference on Cloud Networking
(CloudNet), 2014, pp. 7–13.
[4] A. Leivadeas, M. Falkner, I. Lambadaris, and G. Kesidis, “Optimal virtualized network
function allocation for an sdn enabled cloud,” Computer Standards & Interfaces,
vol. 54, pp. 266–278, 2017.
[5] D. Li, P. Hong, K. Xue, and j. Pei, “Virtual network function placement considering
resource optimization and sfc requests in cloud datacenter,” IEEE Transactions on
Parallel and Distributed Systems, vol. 29, no. 7, pp. 1664–1677, 2018.
[6] I. Benkacem, T. Taleb, M. Bagaa, and H. Flinck, “Performance benchmark of
transcoding as a virtual network function in cdn as a service slicing,” in 2018 IEEE
Wireless Communications and Networking Conference (WCNC), 2018, pp. 1–6.
[7] C. Pham, N. H. Tran, S. Ren, W. Saad, and C. S. Hong, “Traffic-aware and energyefficient
vnf placement for service chaining: Joint sampling and matching approach,”
IEEE Transactions on Services Computing, vol. 13, no. 1, pp. 172–185, 2020.
[8] Y.-C. Chen and L.-H. Yen, “An approach based on matching theory to distributed
deployment of nfv-based network services to geo-distributed edge computing systems,”
2019.
[9] F. Ben Jemaa, G. Pujolle, and M. Pariente, “Qos-aware vnf placement optimization
in edge-central carrier cloud architecture,” in 2016 IEEE Global Communications
Conference (GLOBECOM), 2016, pp. 1–7.
[10] H. Guo, Z. L. Ying Wang, H. A. Xuesong Qiu, and L. Rui, “Cost-aware placement
and chaining of service function chain with vnf instance sharing,” 2018.
[11] R. Cziva, C. Anagnostopoulos, and D. P. Pezaros, “Dynamic, latency-optimal vnf
placement at the network edge,” in IEEE INFOCOM 2018 - IEEE Conference on
Computer Communications, 2018, pp. 693–701.
[12] A. Leivadeas, G. Kesidis, M. Ibnkahla, and I. Lambadaris, “Vnf placement optimization
at the edge and cloud,” Future Internet, vol. 11, no. 3, Jan. 2019.
[13] Z. Zhou, Q. Wu, and X. Chen, “Online orchestration of cross-edge service function
chaining for cost-efficient edge computing,” IEEE Journal on Selected Areas in
Communications, vol. 37, no. 8, pp. 1866–1880, 2019.
[14] I. Benkacem, T. Taleb, M. Bagaa, and H. Flinck, “Optimal vnfs placement in cdn
slicing over multi-cloud environment,” IEEE Journal on Selected Areas in Communications,
vol. 36, no. 3, pp. 616–627, 2018.
[15] D. Dietrich, A. Abujoda, A. Rizk, and P. Papadimitriou, “Multi-provider service
chain embedding with nestor,” IEEE Transactions on Network and Service Management,
vol. 14, no. 1, pp. 91–105, 2017.
[16] L.-H. Y. Chi-Han Chang and Y.-C. Chen, “Profit maximization by forming federations
of geo-distributed mec platforms,” in Seventh Int’l Workshop on Cloud
Technologies and Energy Efficiency (CLEEN 2019), CLEEN, 2019.
[17] V. Sciancalepore, F. Giust, K. Samdanis, and Z. Yousaf, “A double-tier mec-nfv
architecture: Design and optimisation,” in 2016 IEEE Conference on standards for
communications and networking (CSCN), IEEE, 2016, pp. 1–6.
[18] Tosca simple profile for network functions virtualization (nfv) version 1.0, http:
//docs.oasis- open.org/tosca/tosca- nfv/v1.0/csd04/tosca- nfv- v1.0-
csd04.html, Accessed: 2017-05-11.
[19] L. S. Shapley, “On balanced sets and cores,” Naval Research Logistics Quarterly,
vol. 14, no. 4, pp. 453–460, 1967.
[20] T. Sandholm, K. Larson, M. Andersson, O. Shehory, and F. Tohmé, “Coalition
structure generation with worst case guarantees,” Artificial Intelligence, vol. 111,
no. 1, pp. 209 –238, 1999.
[21] D. Berend and T. Tassa, “Efficient bounds on bell numbers and on moments of sums
of random variables,” Probability and Mathematical Statistics, vol. 30, Jan. 2010.
[22] T. Rahwan, T. P. Michalak, M. Wooldridge, and N. R. Jennings, “Coalition structure
generation: A survey,” Artificial Intelligence, vol. 229, pp. 139 –174, 2015.
[23] L. S. Shapley, “A value for n-person games,” Contributions to the Theory of Games,
pp. 307–317, 1953.
[24] ——, “Cores of convex games,” International Journal of Game Theory, pp. 11–26,
1971.
[25] E. Lehrer, “An axiomatization of the banzhaf value,” International Journal of Game
Theory, pp. 89–99, 1988.
[26] R. Brink and G. Laan, “The normalized banzhaf value and the banzhaf share function,”
May 1998.
[27] D. Schmeidler, “The nucleolus of a characteristic function game.,” SIAM Journal
on Applied Mathematics, vol. 17, no. 6, pp. 1163–1170, 1969.