Node placement algorithms for shuffle-like packet-switched networks with wavelength-division multiplexing

The shuffle-like network (SL-Net) is known as a logical topology for WDM-based multihop packet-switched networks. We propose two heuristic node placement algorithms for the SL-Net to decrease the average end-to-end packet transmission delay for a given traffic matrix. The principal idea is to prevent too many traffic flows from overlapping on any link. To attain this objective, one algorithm selects nodes one by one in decreasing order of the sums of their sending and receiving traffic requirements, and places them so that the maximum traffic in the links is minimal. The other selects nodes in the same way, and places then so that the average distance among the nodes which have already been placed is as large as possible. Numerical results for four typical traffic matrices show that either of the proposed algorithms has better performance than the conventional algorithms for each matrix.