藉由通話圖分割改善電信業批價系統的效能

Improve Performance of Telecommunication Billing System by Call Graph Partitioning

賴宏宜(Hong-Yi Lai)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201602368

摘要

在這篇論文中，我們為一個分散式且基於 NoSQL 資料庫的批價系統開發一套資料分散策略。我們先定義一個名為通話圖分割的最佳化問題，這個問題的目標在於平衡傳輸成本並提高資料本地性。我們證明這是一個 NP-complete 的問題，並設計一個貪婪演算法來解決這個問題。然後我們把通話圖分割技術應用於一個分散式且基於 NoSQL 資料庫的批價系統。我們藉由平衡機器間的傳輸並提高資料本地性來改善系統效能。

關鍵字

圖分割 ； 通話圖 ； 平衡傳輸成本 ； 資料本地性 ； 資料分散策略

並列摘要

In this thesis, we develop a data distribution policy for a distributed NoSQLbased billing system. We define an optimization problem which is call graph partitioning problem. The objective of the problem is to balance communication while enhancing data locality. We prove that the problem is NP-complete and design a greedy algorithm to partition a call graph. Then we apply the call graph partitioning technique to a distributed NoSQL-based billing system. We improve system performance by balancing communication across servers and enhancing data locality.

並列關鍵字

Graph Partitioning ； Call Graph ； Balance Communication ； Data Locality ； Data Distribution Policy

參考文獻

[6] Ralf Diekmann, Robert Preis, Frank Schlimbach, and Chris Walshaw. Shapeoptimized mesh partitioning and load balancing for parallel adaptive {FEM}. Parallel Computing, 26(12):1555 – 1581, 2000. Graph Partitioning and Parallel Computing.

[7] C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Design Automation, 1982. 19th Conference on, pages 175–181, June 1982.

[8] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.

[9] Alan George and Joseph W. Liu. Computer Solution of Large Sparse Positive Definite. Prentice Hall Professional Technical Reference, 1981.

[11] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359–392, December 1998.