会议专题

Research the dynamical large file transmitting in optical network using Lagrangian relaxation

In today’s distributed computing systems, a large amount files contain huge data need to be transferred to their destination as soon as possible or else the quality of these systems will be seriously affected, and these transfer requests arrived dynamically. We propose some effective heuristic algorithm to this problem with the purposes of minimizing the maximal file transmitting time, and we can get some primal results from the algorithm. However, as we known, the problem of routing and scheduling for the dynamic arriving files in the optical network has a large number of constrains and the exact solution is computationally expensive, so it is hard to get the optimal result about this problem and we can not know whether the heuristic results is good or how closed it closed to its optimal result. In order to get some more detail results, we apply the approach called Lagrangian relaxation combined with subgradient-based method and utility the heuristic result to compute the lower bound of the optimal solution, and we consider the optimal target of minimizing the maximal file transmitting complete time for it’s an important aspect with the file transmitting problem. We mainly use Lagrangian relaxation (LR) to research the dynamical lager file transmitting problem. Firstly, in order to apply the LR method we formulation our dynamic file routing scheduling and distributing problem in WDM optical network into mathematic model with some corresponding constraints. Secondly, change the formulation with some added variables to let it more suitable for LR and then introduce the Lagrangian multipliers into the model to obtain the Lagrangian function. With this function we can divided it into some small independent problems that could let it be solved more easily and at last we utilize the result received from the heuristic algorithm to solve the Lagrangian multiplier problem with subgradient-based method in order to getting the sharpest possible lower bound. With the comparison of our simulation results, we can prove that the Subgradient algorithm based on LR can get better results of the file transmitting time than the heuristic algorithm, and with the theorem of Lagrangian Bounding Principle we can know that value of LR method is a lower bound on the optimal value.

Lagrangian relaxation Optical network dynamic routing file transport

Hao Wang Wei Guo Yaohui Jin Weiqiang Sun Weisheng Hu

State Key Laboratory on Fiber-Optic Local Area Networks and Advanced Optical CommunicationSystem,Sha State Key Laboratory on Fiber-Optic Local Area Networks and Advanced Optical Communication System,Sh

国际会议

2008亚太光通信会议(Asia-Pacific Optical Communications 2008)

杭州

英文

2008-10-26(万方平台首次上网日期,不代表论文的发表时间)