Randomised scheduling algorithm for virtual output queuing switch at the presence of non‐uniform traffic. Issue 2 (1st March 2019)

• Record Type: Journal Article
• Authors: Jamali, Majid; Ghiasian, Ali
• Is Part Of: IET networks. Volume 8:Issue 2(2019)
• Page Start: 138
• Page End: 142
• Publication Date: 2019-03-01
• Subjects: queueing theory -- packet switching -- telecommunication traffic -- scheduling -- telecommunication switching -- randomised algorithms; nonuniform traffic -- virtual output queuing switch -- randomised scheduling algorithm -- input traffic -- randomised algorithms -- high‐speed switches -- impractical algorithm -- outstanding attainable throughput -- MWM -- Maximum Weight Matching -- time slot -- virtual queues -- input port -- separate FIFO -- output port -- VOQ scheme -- Line blocking issue; Computer network architectures -- Periodicals; Computer network protocols -- Periodicals; Information networks -- Periodicals; Telecommunication systems -- Periodicals; 004.605
• DOI: 10.1049/iet-net.2018.5115
• Languages: English
• ISSNs: 2047-4954

Abstract

Abstract : Virtual Output Queuing (VOQ) is a well‐known queuing discipline in data switch architecture that eliminates Head of Line (HOL) blocking issue. In VOQ scheme, for each output port, a separate FIFO is maintained by each input port. Consequently, a scheduling algorithm is required to determine the order of service to virtual queues at each time slot. Maximum Weight Matching (MWM) is a well‐known scheduling algorithm that achieves the entire throughput region. Despite of outstanding attainable throughput, high complexity of MWM makes it an impractical algorithm for implementation in high‐speed switches. To overcome this challenge, a number of randomised algorithms have been proposed in the literature. They commonly perform poorly when input traffic does not uniformly select output ports. Here, the authors propose two randomised algorithms that outperform the well‐known formerly proposed solutions. They exploit a method to keep a parametric number of heavy edges from the last time matching and mix it by randomly generated matching to produce a new schedule. Simulation results confirm the superior performance of the proposed algorithms.