The Arc-forwarding Index And Wavelength Assignment Problem Of All Optical Networks

Optical network is emerging as key technology in communication networksand is expected to dominate many applications, such as video conference com-munications, scientific visualization, real-time medical imaging, high-speed super-computing and distributed computing. An optical network is defined as a sym-metric directed(i.e., there is an arc from a vertex u to v if and only if there isan arc from v to u) connected graph and a routing consists of a class of pathsconnecting every pair of vertices in the request. Given a routing R, the vertex(orarc)-forwarding index is the maximum number of paths passing through any ver-tex(or arc)in R. The minimum vertex(or arc)-forwarding index over all possibleroutings of a graph G is called the vertex(or arc)-forwarding index of G and de-noted byξ(G)(orπ(G)). The routing problem is to design a routing to route therequest such that the routing minimizes the arc-forwarding index. A wavelengthassignment of a routing R is to assign a color to each path in R such that twopaths sharing an arc have distinct colors and the minimum number of colors overall assignments is denoted byχ(R). Letχ(G) = min {χ(R) : R is a routing of G}.The wavelength assignment problem is to construct a routing and a wavelengthassignment which meets the indexχ(G). In this paper, we only consider theall-to-all networks. It is well-known that the problem of determiningχ(R) isNP-complete. However, it is solvable for some special graphs such as trees, ringsetc.First, we give some bounds for the arc-forwarding index in terms of the vertex-forwarding index, maximum degree, minimum degree, diameter, connectivity andthe sum of distances between two vertices. We also work out the arc-forwardingindex of the folded hypercube. Furthermore, when n is even, the indexχ(G) forthe folded hypercube is determined.