Routing algorithms for time sensitive networks

Abstract

IEEE 802.1Qbv standard is an enhancement introduced by Time Sensitive Network Task Group to provide real time communication in a converged Ethernet network capable of transmitting both time critical traffic and best effort traffic. The standard includes a gating mechanism which controls the access to the transmission medium at the egress port of a switch, allowing transmission of frames from the specified queue. The gating events are time triggered and are programmed using a transmission schedule. A transmission schedule is a cyclic schedule that can be generated using various independent scheduling methods. However, the first step to each method involves routing the traffic across the network, followed by computation of gate schedules along the route. Due to lack of a standard, assessment of the quality of a schedule is difficult. Therefore independent metrics are used to measure the quality of schedule generated by different scheduling methods. However, the aim of each scheduling method is to transmit maximum amount of data traffic in a single cycle of a schedule. This thesis proposes that routing impact the quality of a transmission schedule irrespective of the scheduling method used. To begin evaluations showing the impact of routing algorithms on the data load distribution across the network are present. Followed by evaluations of the impact of data load distribution on the quality of a transmission schedule. Consequently establishing a direct relation between routing of the data traffic and the quality of a schedule. In response a generic routing algorithm aimed at optimizing the data load distribution is presented. The algorithm is based on heuristic algorithm Tabu Search to make it scalable in nature, allowing its use across different scenarios. We evaluate the algorithms with respect to data load distribution, impact on the quality of a schedule and scalability.