Grooming traffic to minimize load (Q658091)

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.