臺灣博碩士論文加值系統

在最近幾年，網路功能模擬化的議題逐漸變得熱絡。過去這些網路功能都是配置在專屬且昂貴的硬體機器上，但如今已逐漸虛擬化且可以配置在一般用途的伺服器中，使得網路功能更具有彈性與拓展性能即時應付不同程度的需求。在資料中心中，這些網路功能能夠被有順序的連接起，進而提供不同功能的服務。換句話說，封包必須有順序性的經過這些被指定的網路功能。然而網路功能之間放置的遠近會影響頻寬的消耗多寡，並且將虛擬的網路功能放置的越分散越有機會使用到更多台的伺服器，這也是不能忽視的因素。有鑑於此，我們將網路功能服務鏈與放置問題視為是Multi-layer bin packing 問題，並用公式轉化成Integer Linear Programming。此外我們的觀點縱觀topology-unaware 與tree-like topology，前者即表示不考慮實際拓樸，後者我們則用樹狀的拓樸進行探討，並針對不同的環境考量分別對前後者提出Partition Best-fit 與 Multi-layer Best-fit 和 Multi-layer Worst-fit。Partition Best-fit與Multi-layer Best-fit皆已被證明相較於Best-fit，能夠有效的減少網路頻寬的消耗約15%與僅增加及1%的伺服器使用數即可達成。

Network function virtualization (NFV) has drawn much attention in recent years; some network functions used to be deployed on the specific hardware have become virtualized instances on general servers to achieve more scalability and flexibility. In data center, service function chaining (SFC) makes different workflow traverse different network functions in a specific ordering to provide different levels of the service for its customer. Since the distance between any adjacent network functions in a service chain will decide the total bandwidth consumption for that chain, the placement of the virtualized network functions in data center becomes a major issue. In this thesis, we treat this placement problem as multi-layer bin packing problem and formulate it as Integer Linear Programming. We propose three algorithms for different network topologies. Partition Best-fit is designed for the topology-unaware, and Multi-layer Best-fit and Multi-layer Worst-fit are designed for the tree-like network topology. The experiment results show that both Partition Best-fit and Multi-layer Best-fit can reduce bandwidth consumption in 15% while only increase a little number of used servers in 1% compare to traditional Best-fit algorithm.

中文摘要 i
Abstract ii
致謝 iii
Contents iv
List of Figures vi
Chapter 1 Introduction 1
Chapter 2 Related works 4
2.1 Network Function 4
2.2 Network Function Virtualization (NFV) 4
2.3 Service Function Chaining 5
2.3.1 Service Function Chaining configure problem using Software-Defined Networking 5
2.4 Some related works 6
Chapter 3 Network function placement and chaining problem 8
3.1 Multi-layer bin packing problem 8
3.2 Network function placement and chaining problem in the topology-unaware network 10
3.2.1 Problem formulation 10
3.2.2 Partitioned Best-fit 12
3.3 Network function placement and chaining problem in the network without link constraints 14
3.3.1 Problem formulation 14
3.3.2 Multi-layer greedy algorithms 17
3.3.3 Adding link constraints into tree-like topology 20
Chapter 4 Performance Simulation 21
4.1 Topology-unaware network simulation 23
4.2 Tree-like topology simulation without link constraints 26
4.2.1 Fat-Tree simulation 26
4.2.2 VL2 simulation 29
4.3 Comparison among different approaches in Fat-Tree 32
4.4 Tree-like topology simulation with link constraints 34
4.4.1 Fat-Tree simulation 34
4.4.2 VL2 simulation 35
4.5 Simulation using uniform distribution 37
Chapter 5 Conclusion 42
References 43

[1] A. Greenberg, J. Hamilton, D. A. Maltz, and P. Patel, "The cost of a cloud: research problems in data center networks," ACM SIGCOMM computer communication review, vol. 39, pp. 68-73, 2008.
[2] H. Moens and F. De Turck, "VNF-P: A model for efficient placement of virtualized network functions," in Network and Service Management (CNSM), 2014 10th International Conference on, 2014, pp. 418-423.
[3] S. Mehraghdam, M. Keller, and H. Karl, "Specifying and placing chains of virtual network functions," in Cloud Networking (CloudNet), 2014 IEEE 3rd International Conference on, 2014, pp. 7-13.
[4] A. Gember, A. Krishnamurthy, S. S. John, R. Grandl, X. Gao, A. Anand, et al., "Stratos: A network-aware orchestration layer for virtual middleboxes in clouds," arXiv preprint arXiv:1305.0209, 2013.
[5] M. C. Luizelli, L. R. Bays, L. S. Buriol, M. P. Barcellos, and L. P. Gaspary, "Piecing Together the NFV Provisioning Puzzle: Efficient Placement and Chaining of Virtual Network Functions," 2015.
[6] X. Li, J. Wu, S. Tang, and S. Lu, "Let's stay together: Towards traffic aware virtual machine placement in data centers," in INFOCOM, 2014 Proceedings IEEE, 2014, pp. 1842-1850.
[7] M. Al-Fares, A. Loukissas, and A. Vahdat, "A scalable, commodity data center network architecture," ACM SIGCOMM Computer Communication Review, vol. 38, pp. 63-74, 2008.
[8] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, et al., "VL2: a scalable and flexible data center network," in ACM SIGCOMM computer communication review, 2009, pp. 51-62.
[9] J. Sherry, S. Ratnasamy, and J. S. At, "A survey of enterprise middlebox deployments," 2012.
[10] D. A. Joseph, A. Tavakoli, and I. Stoica, "A policy-aware switching layer for data centers," ACM SIGCOMM Computer Communication Review, vol. 38, pp. 51-62, 2008.
[11] S. K. Fayazbakhsh, V. Sekar, M. Yu, and J. C. Mogul, "Flowtags: Enforcing network-wide policies in the presence of dynamic middlebox actions," in Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking, 2013, pp. 19-24.
[12] Z. A. Qazi, C.-C. Tu, L. Chiang, R. Miao, V. Sekar, and M. Yu, "SIMPLE-fying middlebox policy enforcement using SDN," in ACM SIGCOMM Computer Communication Review, 2013, pp. 27-38.
[13] J. Blendin, J. Ruckert, N. Leymann, G. Schyguda, and D. Hausheer, "Position paper: Software-defined network service chaining," in Software Defined Networks (EWSDN), 2014 Third European Workshop on, 2014, pp. 109-114.
[14] J. Sherry, S. Hasan, C. Scott, A. Krishnamurthy, S. Ratnasamy, and V. Sekar, "Making middleboxes someone else's problem: network processing as a cloud service," ACM SIGCOMM Computer Communication Review, vol. 42, pp. 13-24, 2012.
[15] A. Gember, P. Prabhu, Z. Ghadiyali, and A. Akella, "Toward software-defined middlebox networking," in Proceedings of the 11th ACM Workshop on Hot Topics in Networks, 2012, pp. 7-12.
[16] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, et al., "OpenFlow: enabling innovation in campus networks," ACM SIGCOMM Computer Communication Review, vol. 38, pp. 69-74, 2008.
[17] Y. Zhang, N. Beheshti, L. Beliveau, G. Lefebvre, R. Manghirmalani, R. Mishra, et al., "Steering: A software-defined networking for inline service chaining," in Network Protocols (ICNP), 2013 21st IEEE International Conference on, 2013, pp. 1-10.
[18] (2014). Network Service Header. Available: https://datatracker.ietf.org/doc/draft-quinn-sfc-nsh/
[19] OpenDaylight. Available: https://www.opendaylight.org/
[20] Ryu. Available: http://osrg.github.io/ryu/
[21] Floodlight. Available: http://www.projectfloodlight.org/floodlight/