During past decades, Ethernet progressively became the most widely used Local Area Network (LAN) technology. Apart from LAN installations, Ethernet also became attractive for other application areas such as industrial control, automotive, and avionics. In traditional LAN design, the objective is to minimize the network deployment cost. However, in embedded networks, additional constraints and ambient conditions add to the complexity of the problem. In this paper, the authors propose a Simulated Annealing (SA) algorithm to optimize the physical topology of an embedded Ethernet network. The various constraints and ambient conditions are modeled by a cost map. For networks with small number of nodes and/or switches, the authors were able to find the optimal solutions using adapted algorithms. These solutions will serve as a lower bound for the solutions obtained via the SA algorithm. However, the adapted algorithms are time consuming and application specific. The paper shows that the SA algorithm can be applied in all cases and finds (near-) optimal solutions.
TopIntroduction
Today, Ethernet is the predominant Local Area Network (LAN) technology and is considered as a de facto standard for network infrastructure. The flexibility and the plug-and-play feature of Ethernet are its key to success. Thanks to the wide availability of its components, its large bandwidth, its reliability, and its backward-compatibility, Ethernet has become an attractive option in many application areas (Sommer et al., 2010).
A prominent example of Ethernet's application area is the industrial domain where Ethernet is gaining ground over traditional fieldbuses (Felser, 2005; Decotignie, 2005). Another area is avionics, where today's Ethernet proved its ability to fulfill real-time requirements needed in such an environment (ARINC 664, 2003). Last but not least, the automotive industry is investigating Ethernet as a suitable in-car network technology (Rahmani, Hillebrand, Hintermaier, Bogenberger, & Steinbach, 2007; Rahmani, Steffen, Tappayuthpijarn, Steinbach, & Giordano, 2008; Rahmani, Tappayuthpijarn, Krebs, Steinbach, & Bogenberger, 2009).
A motivation to use Ethernet in embedded networks is the use of commercial off-the-shelf components (Sommer et al., 2010). This allows integrators to cut down the development cost as well as the time needed to build new components. Furthermore, the large number of Ethernet vendors and the wide range of products promote the competition to provide the best equipment at the lowest price.
In contrast to traditional LANs, an embedded network has to meet additional requirements. For example, in an aircraft or a car, the installation space and the maximum weight tolerated are limited. Furthermore, the ambient conditions impose constraints on the network deployment. For instance, at some places, we need a better cable shielding due to electromagnetic interference or an extra heat-resisting cable due to the environment temperature. At other places, it might be extremely expensive or even impossible to deploy a cable. Moreover, at some places we need additional cables for the power supply of the switches while at other places such as at the positions of the nodes (devices), power supplies are already available. These constraints add to the design complexity of an embedded network.
Ethernet evolved from a bus topology to a so-called micro-segmented network with full duplex links between nodes and switches. On the one hand, deploying a single switch and connecting all the nodes directly to it has the lowest switch cost. However, such a star topology leads to wire bundles, which increase the wiring cost. On the other hand, deploying multiple switches, which increases the switching cost, alleviates the wiring layout, and consequently reduces the wiring cost proportional to the total wire length. Hence, the resulting problem is a multi-objective optimization problem where the optimal solution is a trade-off between the cost penalty due to the additional number of switches and the cost benefit due to the reduction of the total wiring length.
In this paper, we propose a Simulated Annealing (SA) algorithm to optimize the physical topology by minimizing the total link cost of an embedded Ethernet network. We take into account the aforementioned constraints and ambient conditions by modeling them with a cost map. Assuming a constant cost map (fixed cost over all the environment space), we are able to find the optimal solution by means of a Mixed-Integer Linear Program (MILP). For special cases, a Minimum Spanning Tree (MST) algorithm and an exact algorithm for the Steiner Tree (ST) problem can be used. For these cases, we show that the proposed SA algorithm provides optimal solutions in short running time. For general cost map models, the complexity of the problem increases drastically and the ST algorithm is unable to give a solution within reasonable time on today's computers. If we restrict the switches to be placed at the same positions as the nodes, the MILP and the MST algorithms are still able to find optimal solutions, while the proposed SA algorithm is the only general algorithm that keeps its pace with the increasing complexity of the problem.