An Optical Distribution Network Partitioning Method Based on the Branch-and-Bound

Abstract:

Optical Distribution Network is a kind of optical transmission path connecting Optical Line Terminal and Optical Network Unit. This article mainly studies how to optimize broadband loan problems of the backbone network. In order to get the best allocation scheme of the Optical Distribution Network problems, we propose a solution which is converting the Optical Distribution Network partitioning problem into a graph partitioning model, and solve the problem by adopting Graph partitioning algorithms. Graph partitioning is about the undirected graph , is the collection of all vertexes. is the collection of all sides. Any vertex in the vertex set has weight value of a positive integer. Any side in a side set has weight value of a positive integer. The vertex set is divided into non-intersecting subsets , and .As to every subset , it has ,,.What we need to solve is to get the minimum sum of weight values between m non-intersecting subsets. The experimental results show that Graph partitioning algorithm is efficient.

• Periodical: Applied Mechanics and Materials (Volumes 427-429)
• Pages: 2399-2402
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.427-429.2399
• Online since: September 2013
• Authors: Ya Gao*, Xia Gao
• Keywords: Branch-and-Bound, Graph Partitioning, Optical Distribution Network

References

[1] Goldschmidt, O. and Hochbaum, D. S. Polynomial algorithm for the k-cut problem [A]. On Foundations of Comput. SCI [C]. IEEE Computer Society, 1988, p.444–451.

[2] Andreev, Konstantin and Räcke, Harald. Balanced Graph Partitioning [A]. Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures [C]. Barcelona, Spain, 2004: 120124, doi: 10. 1145/1007912. 1007931, ISBN 1-58113-840-7.

DOI: 10.1145/1007912.1007931

[3] Mechthild Stoer Televerkets Forskningsinstitutt, Kjeller. Norway Frank Wagner Freie Univ. Berlin. Berlin-Dahlem, Germany, A simple min-cut algorithm. Volume 44 Issue 4, July 1997. Pages585-591. ACM. New York NY. USA table of contents doi>10. 1145/263867. 263872.

DOI: 10.1145/263867.263872

[4] Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness [M]. W. H. Freeman & Co, 1979, ISBN 0-7167-1044-7.

[5] Effenberger, F.; Clearly, D.; Haran, O.; Kramer, G.; Ruo Ding Li; Oron, M. ; Pfeiffer, T. An introduction to PON technologies IEEE Communications Magazine EI. SCI. 2007, 45(3).

DOI: 10.1109/mcom.2007.344582

[6] Minglai Liu Rujian Lin Jun Huang Design and FPGA implementation of VLAN in EPON. Network Architectures, Management, and Applications II pt. 1. 2004. 1. 1. Beijing, China.

DOI: 10.1109/icasic.2005.1611426

[7] Hamada Alshaer1, Raed Shubair2, Mohamed Alyafei3. A framework for resource dimensioning in GPON access networks. International journal of network management EI. SCI. 2012, 22(3).

[8] Ito, Yusuke; Shigemori, Suguru; Sato, Takashi; Shimazu, Tomoyuki; Hatano, Konomi; Otani, Hajime; Kitazawa, Haruki; Shimosato, Takeshi. Class I/II hybrid inhibitory oligodeoxynucleotide exerts Th1 and Th2 double immunosuppression. FEBS Open Bio, 2013, Vol. 3, pp.41-45.

DOI: 10.1016/j.fob.2012.11.002