Energy-Saving Routing Algorithm using Steiner Tree

There is much demand for reducing energy consumption with regards to network communications. For this purpose, this paper proposes an energy-saving routing algorithm that uses a Steiner tree created using a branch-based multi-cast Steiner tree algorithm. The proposed algorithm creates a Steiner tree among edge nodes in a network and creates point to point paths between two different edge nodes by following the created Steiner tree. Since only the links and nodes on the Steiner tree are used, the numbers of used links and nodes are dramatically reduced compared with other routing algorithms. The proposed algorithm creates bypass routes between nodes on the Steiner tree to reduce traffic congestion between nodes. Many energy-saving routing algorithms have been proposed recently, but most are nondeterministic polynomial time (NP)-complete or NP-hard; thus, it is difficult to apply them to real-time routing operations. This paper compares the proposed routing algorithm with a polynomial time routing algorithm, which has already been proposed for energy saving, and the conventional open shortest path first (OSPF)-based routing algorithm to clarify the applicability of the proposed algorithm.