Double Neighborhood Search Algorithm in Multicast Aggregation
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The problem of aggregated multicast in optical transmission networks has been known to be a complete NP-hard problem. A double neighborhood search algorithm (DNSA) for solving the multicast aggregation problem is presented. The objective of this algorithm is to minimize the bandwidth wastage ratio that is subject to the constraints that the number of multicast aggregation tree is affected by the amount of wavelength. In this paper, a priority aggregate rule based on the greedy strategy is proposed to generate initial solution: two kind neighborhood structures are proposed to search effectively, and some off-trap strategies are proposed to jump from local optimal solution and carry the search to the feasible areas in promising directions. Simulation experiments show the double neighborhood search algorithm can aggregate multicast trees effectively. The multicast group blocking ratio is 0 at light load. Compared with other algorithms at heavy load, the average bandwidth wastage ratio has decreased more than 25%. The results indicate that improvements may be obtained in different network condition.

    Reference
    Related
    Cited by
Get Citation

汪学舜,余少华,戴锦友.双邻域查找组播聚合算法.软件学报,2013,24(2):243-254

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:January 23,2011
  • Revised:April 16,2012
  • Adopted:
  • Online: February 02,2013
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063