Achieving Realtime Capabilities in Ethernet Networks by Edge-Coloring of Communication Conflict-Multigraphs

F. Dopatka and R. Wismüller (Germany)


Industrial automation, graph coloring, greedy, and QoS


This paper presents a top-down Quality-of-Service (QoS) approach to design realtime Ethernet networks for automation systems based upon tree topologies. Therefore, the parallelism of switched unicast communication is utilized by generating an off-line schedule, which considers each port of a switch as an exclusive networking resource. We point out that the schedule can be generated independently for each switch. Starting from a given network infrastructure and QoS requests, we present a method consisting of attribution to identify routes, specification of conflicts inside the switches, and building of a conflict-multigraph for each switch. The schedule is realized using greedy edge coloring of the graph together with optional edge pre sorting and re-coloring after execution of the greedy algorithm. The method is shown for a class of special cases with unitary packet-sizes and transmission of every request in each cycle-period. Finally, some first results of this method are presented.

Important Links:

Go Back