| Author Name | Affiliation | | An-Yu Zhou | College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China | | Hui-Qiang Wang | College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China | | Pei-You Song | Dept.of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA |
|
| Abstract: |
| To determine CDN cache servers’ placement reasonably, an idea that using graph partitioning to solve the problem was put forward through theoretical analysis and the specific algorithm of partitioning was researched. The concept of graph partitioning for CDN was defined. The conditions of graph partitioning for CDN were demonstrated: the sum of the weights of the nodes in each subarea is as close as possible; edge cut between the subareas is as large as possible; internal nodes in each subarea are connected as far as possible. By reference to light vertex matching algorithm of graph partitioning for network simulation, a multilevel k-way algorithm of graph partitioning for CDN was proposed. The maximized edge cut k-way KL refinement algorithm was discussed. Graph partitioning is a feasible way to solve the problem of CDN servers’ placement. Multilevel k-way algorithm is a feasible algorithm for CDN graph partitioning. |
| Key words: graph partitioning CDN servers placement matching algorithm |
| DOI：10.11916/j.issn.1005-9113.2013.02.012 |
| Clc Number:TP393.07 |
| Fund: |
