Input-Queued Switches Using Two Schedulers in Parallel

スポンサーリンク

概要

• 論文の詳細を見る

• It has been shown that virtual output queuing (VOQ) and a sophisticated scheduling algorithm enable an input-queued switch to achieve 100% throughput for independent arrival process. Several of the scheduling algorithms that have been proposed can be classified as either iterative scheduling algorithms or symmetric crossbar arbitration algorithms. i-OCF (oldest-cell-first) and TSA (two step arbiter) are well-known examples of iterative scheduling algorithms and symmetric crossbar arbitration algorithms, respectively. However, there are drawbacks in using these algorithms. i-OCF takes long time to find completely a conflict-free match between input ports and output ports because it requires multiple iterations. If i-OCF cannot find a conflict-free match completely, the switch throughput falls. TSA has the possibility that it finds a conflict-free match faster than i-OCF because it does not need any iterations. However, TSA suffers from the starvation problem. In this paper, we propose a new scheduling algorithm. It uses two schedulers, which we call scheduler 1 and scheduler 2, in parallel. After cells were transmitted, the information that input port i granted the offer from output port j in scheduler 2 is mapped to scheduler 1 if and only if input port i has at least one cell destined for output port j. If the information is moved, input port i and output port j are matched in scheduler 1 at the beginning of the next time slot. Our proposed algorithm uses one scheduler based on TSA and the other scheduler based on i-OCF. Numerical results show that the proposed scheduling algorithm does not require multiple iterations to find a conflict-free match completely and suffer from the starvation problem for both uniform and bursty traffic.

• 社団法人電子情報通信学会の論文
• 2002-02-01

著者

• NABESHIMA Masayoshi

  NTT Network Innovation Laboratories

• Nabeshima Masayoshi

  Ntt Netwok Service Systems Laboratories

関連論文

• Performance of Fair Queuing with In/Out Bit in Core Stateless Networks (Special Issue on New Developments on QoS Technologies for Information Networks)
• MXQ (MaXimal Queuing) : A Network Mechanism for Controlling Misbehaving Flows in Best Effort Networks (Special Issue on High-speed Internet Technology and its Applications)
• Performance of Scalable-Distributed-Arbitration ATM Switch Supporting Multiple QoS Classes (IEICE/IEEE Joint Special Issue on Recent Progress in ATM Technologies)
• Input-Queued Switches Using Two Schedulers in Parallel
• The i-QOCF (Iterative Quasi-Oldest-Cell-First) Scheduling Algorithm for Input-Queued ATM Switches (IEICE/IEEE Joint Special Issue on Recent Progress in ATM Technologies)
• New Scheduling Mechanisms for Achieving Fairness Criteria (MCR Plus Equal Share, Maximum of MCR or Max-Min Share)
• Packet-Based Scheduling for ATM Networks Based on Comparing a Packet-Based Queue and a Virtual Queue
• Performance Evaluation of a Combined Input- and Crosspoint-Queued Switch

スポンサーリンク