## A Near-Optimal Solution Approach for the Multi-hop Traffic Grooming Problem |

Journal of Optical Communications and Networking, Vol. 3, Issue 11, pp. 891-901 (2011)

http://dx.doi.org/10.1364/JOCN.3.000891

Enhanced HTML Acrobat PDF (379 KB)

### Abstract

In this paper we consider a capacity sizing and routing problem in synchronous digital hierarchy/wavelength division multiplexing networks with nodes having switching capabilities. This problem is well known in the literature as the multi-hop traffic grooming problem and is generally formulated as an integer linear program, which is especially hard to solve when the demand channels are unsplittable and nonuniform. To overcome this difficulty we develop a branching strategy, using a lower bound that is close to the optimal solution. We also devise a reformulation which accelerates branch-and-bound-based solvers. The computational results clearly show that our method is effective in reducing execution time as well as memory consumption, in comparison to traditional methods based on branch-and-bound.

© 2011 OSA

**OCIS Codes**

(060.4254) Fiber optics and optical communications : Networks, combinatorial network design

(060.4256) Fiber optics and optical communications : Networks, network optimization

**ToC Category:**

Research Papers

**History**

Original Manuscript: December 8, 2010

Revised Manuscript: August 16, 2011

Manuscript Accepted: September 30, 2011

Published: October 31, 2011

**Citation**

Ali Balma, Nejib Ben Hadj-Alouane, and Atidel B. Hadj-Alouane, "A Near-Optimal Solution Approach for the Multi-hop Traffic Grooming Problem," J. Opt. Commun. Netw. **3**, 891-901 (2011)

http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-3-11-891

Sort: Year | Journal | Reset

### References

- B. Mukherjee, K. Zhu, and H. Zhu, Traffic Grooming in Optical WDM Mesh Networks, Springer, 2006.
- A. L. Chiu and E. H. Modiano, "Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks," J. Lightwave Technol. 18, (1), 2‒10 (2000). [CrossRef]
- T. Y. Chow and P. J. Lin, "The ring grooming problem," Networks 44, (3), 194‒202 (2004). [CrossRef]
- R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, (1), 110‒121 (2002). [CrossRef]
- E. Modiano and P. J. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 9, (2), 124‒129 (2001). [CrossRef]
- X. Zhang and C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, (5), 608‒617 (2000). [CrossRef]
- F. Alvelos and J. M. Valerio de Carvalho, "Comparing branch-and-price algorithms for the unsplittable multicommodity flow problem," Proc. INOC’03, 2003, pp. 7‒12.
- H. Holler and S. Vob, "A heuristic approach for combined equipment-planning and routing in multilayer SDH/WDM networks," Eur. J. Oper. Res. 171, 787‒796 (2006). [CrossRef]
- H. Liu and F. A. Tobagi, "Traffic grooming in WDM SONET UPSR rings with multiple line speeds," Proc. IEEE INFOCOM’05, 2005, pp. 718‒729.
- J. Q. Hu, "Traffic grooming in WDM ring networks: a linear programming solution," J. Opt. Netw. 1, (11), 397‒408 (2002).
- J. Q. Hu and B. Leida, "Traffic grooming, routing and wavelength assignment in optical WDM mesh networks," Proc. IEEE INFOCOM’04, 2004, pp. 495‒501.
- R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.
- V. Gabrel, A. Knippel, and M. Minoux, "Exact solutions of multicommodity network optimization problems with general step cost function," Oper. Res. Lett. 25, 13‒23 (1999). [CrossRef]
- S. Ketabi and F. Salzborn, "Network optimization with piecewise linear convex costs," Proc. INOC’03, 2003, pp. 326‒330.
- S. Ketabi, "The overflow model for network optimization problems with piecewise linear costs," Proc. INOC’03, 2003, pp. 323‒325.
- M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP models based on flow aggregation," IEEE/ACM Trans. Netw. 15, (3), 709‒720 (2007). [CrossRef]
- M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP based on source formulation," Proc. IEEE INFOCOM, 2004, pp. 1813‒1821.
- D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).
- W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009). [CrossRef]
- S. Thiagarajan and A. K. Somani, "A capacity correlation model for WDM networks with constrained grooming capabilities," Proc. IEEE ICC, 2001, pp. 1592‒1596.
- A. E. Ozdaglar and D. P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Trans. Netw. 11, (2), 259‒272 (2003). [CrossRef]
- M. Pioro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004.
- J. F. Tsai, M. H. Lin, and Y. C. Hu, "Finding multiple solutions to general integer linear programs," Eur. J. Oper. Res. 184, 802‒809 (2008). [CrossRef]
- R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical lopologies: a linear formulation for wavelength-routed optical networks with no wavelength changers," IEEE/ACM Trans. Netw. 9, (2), 186‒198 (2001). [CrossRef]

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

OSA is a member of CrossRef.