頁籤選單縮合
| 題 名 | An Optimal MILP Formulation for the Delay-and Delay Variation-Bounded Multicast Tree Problem |
|---|---|
| 作 者 | Sheu, Pi-Rong; Tsai, Hung-Yuan; Chen, Shao-Chi; | 書刊名 | 網際網路技術學刊 |
| 卷 期 | 8:3 2007.07[民96.07] |
| 頁 次 | 頁321-327 |
| 分類號 | 448.6 |
| 關鍵詞 | Multicast communication; Delay variation; End-to-end delay; Optimal formulation; Linear programming; |
| 語 文 | 英文(English) |
| 英文摘要 | Multicast communications mean providing transmission of common messages from one source to all destinations. The multicast end-to-end delay problem explores an upper bound on the end-to-end delay from a source to each destination. It implies messages must be sent to their destinations within a strict time limit lest they be declared invalid. On the other hand, the multicast delay variation problem studies how to avoid the situation where a message fails to arrive at each destination at the same time. This paper addresses the problem of minimizing multicast delay variation under multicast end-to-end delay constraint. This problem has been proven to be NP-complete. Many heuristic algorithms have been designed for it. However, these heuristic algorithms can only generate suboptimal solutions. In this paper, we propose a mixed-integer linear programming (MILP) formulation to yield optimal solutions for this difficult problem. Computer simulations testify that compared with a known high-performance heuristic algorithm, our MILP formulation can yield solutions with smaller multicast delay variations under different multicast end-to-end delay constraints. |
本系統中英文摘要資訊取自各篇刊載內容。