Grooming traffic to minimize load

DOI10.1016/J.DISC.2011.03.016MaRDI QIDQ658091zbMATH OpenOpenAlexFDO

Authors Charles J. Colbourn, Alan C. H. Ling, Gaetano Quattrocchi, Violet R. Syrotiuk

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.03.016

graph decomposition load minimization optic network traffic grooming

Optimality conditions for problems involving relations other than differential equations (49K21) Mathematical problems of computer architecture (68M07) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Review text

Traffic grooming refers to the process of choosing an assignment of each traffic stream to an optic network such that for every connection on every wavelength, there is sufficient capacity to carry the union of such a collection of traffic streams. Besides the natural objective of minimizing the required wavelengths, one would like to minimize the maximum number of drop cost, namely, the number of add-drop multiplexers used to adjust traffic in this process, and maximize the throughput of these traffic streams when the drop cost reaches the physical limitation associated with a node. This paper follows a graph-theoretical approach to study various optimization issues related to the above grooming process. More specifically, a graph \(G,\) representing an optic network, is decomposed into a collection of edge disjoint spanning subgraphs \({\mathcal G}.\) Then, the wavelength cost of the decomposition, denoted by \(wc({\mathcal G}),\) is the number of such subgraphs in \({\mathcal G},\) the drop cost, \(dc({\mathcal G}),\) is the number of vertices of nonzero degrees in all the subgraphs, the load on a vertex is the number of subgraphs where this vertex has nonzero degree, and the load of the decomposition, \(ld({\mathcal G}),\) is obtained by maximizing vertex load for all vertices in \(G.\) A major indicator of such a decomposition \({\mathcal G}\) is the maximum number of edges in any of its spanning trees, referred to as the grooming ratio, \(gr({\mathcal G}),\) which specifies the maximum number of nodes to be allocated to the same wavelength. Given a network with \(n\) vertices and \(m\) edges, and a grooming ratio \(c,\) the general problem is to select a decomposition \({\mathcal G},\) with \(|V({\mathcal G})|=n, |E({\mathcal G})|\geq m\) and \(gr({\mathcal G})\leq c\) that minimizes \(wc({\mathcal G}), dc({\mathcal G})\) and \(ld({\mathcal G}).\) Although it is easy to minimize \(wc({\mathcal G}),\) it is rather challenging to minimize \(dc({\mathcal G})\) and \(ld({\mathcal G}).\) The main contribution of this technical paper is to have determined, by detailed case analysis, the minimum values of both drop cost and load cost for any decomposition of a network where the grooming ratio equals 2, 3 or 4.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Grooming traffic to minimize load

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658091)