Scheduling method and scheduler for switching

Patent metadata

Field	Value
Publication number	US-10511537-B2
Application number	US-201715607931-A
Country	US
Kind code	B2
Filing date	May 30, 2017
Priority date	Mar 10, 2017
Publication date	Dec 17, 2019
Grant date	Dec 17, 2019

Abstract

A scheduling method for switching including receiving an allocation request for a time slot from input nodes to which the time slot is not allocated, receiving property information of at least one of virtual output queues (VOQs) in which data received by the input nodes is stored, determining a transmission priority of the VOQs for transmission of the data stored in the VOQs based on the received property information of the VOQs, determining input nodes to which the time slot is to be allocated using outputter arbiters for output nodes corresponding to the VOQs, allocating the time slot to the determined input nodes, and updating elements used to allocate the time slot with respect to input nodes for which the allocating of the time slot is completed and output nodes for which the allocating of the time slot is completed.

First claim

What is claimed is:

1. A scheduling method of a scheduler for switching, the method comprising:
receiving, at the scheduler, an allocation request for a time slot from input nodes to which the time slot is not allocated from input nodes connected to a switch;
receiving property information of at least one of virtual output queues (VOQs) in which data received by the input nodes is stored;
determining a transmission priority of the VOQs for transmission of the data stored in the VOQs based on the received property information of the VOQs;
determining input nodes to which the time slot is to be allocated using at least two corresponding outputter arbiters, the outputter arbiters being round robin arbiters, each having a different transmission priority level for output nodes corresponding to the VOQs;
allocating the time slot to the determined input nodes; and
updating elements used to allocate the time slot with respect to input nodes for which the allocating of the time slot is completed and output nodes for which the allocating of the time slot is completed.

2. The method of claim 1 , further comprising: determining VOQs from which the stored data is to be transmitted using at least two corresponding inputter arbiters, the inputter arbiters being round robin arbiters, each having a different transmission priority level corresponding to the determined transmission priority among inputter arbiters for the input nodes to which the time slot is not allocated.

3. The method of claim 2 , wherein the determining of the VOQs from which the stored data is to be transmitted comprises:
identifying whether the determined transmission priority of the VOQs is a highest transmission priority; and
performing round robin scheduling starting from pointer values indicated by the inputter arbiters corresponding to the determined transmission priority in response to the determined transmission priority being the highest transmission priority.

4. The method of claim 3 , wherein the performing of the round robin scheduling comprises performing the round robin scheduling starting from the pointer values indicated by the inputter arbiters corresponding to the determined transmission priority when the VOQs having a transmission priority higher than the determined transmission priority are absent, in response to the determined transmission priority not being the highest transmission priority.

5. The method of claim 1 , further comprising: determining output nodes to receive the allocation request for the time slot based on a preset condition.

6. The method of claim 1 , wherein the property information includes lengths of the VOQs and delays of the VOQs.

7. The method of claim 1 , wherein the determining of the transmission priority comprises:
determining the transmission priority of the VOQs based on a transmission priority table indicating the transmission priority of the VOQs based on lengths of the VOQs and delays of the VOQs.

8. The method of claim 1 , wherein the determining of the input nodes to which the time slot is allocated comprises:
identifying whether the determined transmission priority of the VOQs of the determined input nodes is a highest transmission priority; and
performing round robin scheduling starting from pointer values indicated by outputter arbiters corresponding to the determined transmission priority in response to the determined transmission priority being the highest transmission priority.

9. The method of claim 8 , wherein the performing of the round robin scheduling comprises performing the round robin scheduling starting from the pointer values indicated by the outputter arbiters corresponding to the determined transmission priority when the input nodes having a transmission priority higher than the determined transmission priority are absent, in response to the determined transmission priority being lower than the highest transmission priority.

10. The method of claim 1 , wherein the updating of the elements comprises:
displaying grant indicators indicating allocating of the time slot is completed to the output nodes for which the allocating of the time slot is completed;
storing pointer values of the outputter arbiters corresponding to the determined transmission priority of the VOQs;
displaying the grant indicators to the VOQs corresponding to the output nodes to which the grant indicators are displayed among the VOQs for the input nodes to which the time slot is allocated;
displaying output node indicators for identifying the output nodes that allocate the time slot to the input nodes to which the time slot is allocated; and
increasing the pointer values of the inputter arbiters corresponding to the determined transmission priority.

11. The method of claim 10 , further comprising: resetting the VOQs corresponding to the output nodes to which the grant indicators are displayed among the VOQs of the input nodes to which the time slot is not allocated.

12. The method of claim 1 , further comprising: initializing the elements used to allocate the time slot in response to allocating of the time slot to all input nodes being completed.

13. A scheduling method of a scheduler for switching, the method comprising:
receiving, at the scheduler, an allocation request for a time slot from input nodes to which the time slot is not allocated from input nodes connected to a switch;
verifying whether the time slot to be allocated to the input nodes is a time slot for guaranteed bit rate (GBR) data based on a GBR table indicating information on the GBR data and the time slot for the GBR data;
verifying whether virtual output queues (VOQs) storing the GBR data among at least one VOQ storing data received by the input nodes are present in response to the time slot being for the GBR data;
priorly allocating the time slot to the input nodes in response to the VOQs storing the GBR data being present; and
in response to the time slot to be allocated to the input nodes not being for the GBR data, the scheduler allocates the time slot based on a transmission priority of the VOQs.

14. An apparatus for switching including a scheduler, wherein the scheduler is configured to receive an allocation request for a time slot from input nodes to which the time slot is not allocated,
receive property information of at least one of virtual output queues (VOQs) in which data received by the input nodes to which the time slot is not allocated is stored,
determine a transmission priority of the VOQs for transmission of the data stored in the VOQs based on the received property information of the VOQs,
determine input nodes to which the time slot is to be allocated using at least two corresponding outputter arbiters, the outputter arbiters being round robin arbiters, each having a different transmission priority level corresponding to the transmission priority of the determined VOQs among outputter arbiters for output nodes corresponding to the VOQs,
allocate the time slot to the determined input nodes, and
update elements used to allocate the time slot with respect to input nodes for which allocating of the time slot is completed and output nodes for which allocating of the time slot is completed.

15. The apparatus of claim 14 , wherein the scheduler is configured to determine VOQs from which the stored data is to be transmitted using at least two corresponding inputter arbiters corresponding to the determined transmission priority among inputter arbiters for the input nodes to which the time slot is not allocated.

16. The apparatus of claim 15 , wherein the scheduler is configured to determine the VO

Assignees

• Electronics & Telecommunications Res Inst

Inventors

• Han Kyeong-Eun
• Song Jongtae
• Kim Daeub
• Park Chansung
• Kim Sun Me
• Youn Ji Wook

Classifications

• H04L12/00

  Data switching networks (interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00) · CPC title

• G06F9/4837

  time dependent · CPC title

• H04L49/252

  Store and forward routing · CPC title

• H04L49/254

  Centralised controller, i.e. arbitration or scheduling · CPC title

• G06F9/48

  Program initiating; Program switching, e.g. by interrupt · CPC title