Switching device for controlling data packet flow

• US 20050047405A1
• Filed: 08/20/2004
• Published: 03/03/2005
• Est. Priority Date: 08/25/2003
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Denzel, Wolfgang E., Iliadis, Ilias
• Application Number:
  US10/923,238
• Publication Number:
  US 20050047405A1
• Time in Patent Office: Days
• US Class Current: 370/388
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections

Abstract

Methods for controlling a data packet flow through a switch having first, second and third stage switch modules. Each switch module has a number of data inputs, a number of data outputs, and a data packet buffer. The data outputs of the first stage switch modules are connected to data inputs of the second stage switch modules, and data outputs of the second stage switch modules are connected to the data inputs of the third stage switch modules. A data packet received at one of the first stage switch modules is forwarded to a specific data output of one of the third stage switch modules. A method for controlling a data packet flow comprises: A storing credit information associated to each of the second stage switch modules indicating a number of free data packet buffer locations in the respective second stage switch module; selecting one of the second stage switch modules in dependence on the credit information; forwarding the received data packet from the first stage switch module to the selected second stage switch module; forwarding the received data packet from the selected second stage switch module to the respective third stage switch module, from which the received data packet is to be sent; after sending the data packet from the respective third stage switch module, delivering a credit information about the freed data packet buffer location from the third stage switch module to the second stage switch module, wherein the respective second stage switch module is chosen by a credit return strategy.

Claims

1. A method for controlling a data packet flow through a switching device comprising a first number of first stage switch modules, a second number of second stage switch modules and a third number of third stage switch modules, each of the switch modules, having a number of data inputs a number of data outputs and a data packet buffer the data outputs of the first stage switch modules being connected to the data inputs of the second stage switch modules and the data outputs of the second stage switch modules to the data inputs of the third stage switch modules;

wherein a data packet received at a data input of one of the first stage switch modules is forwarded to a specific data output of one of the third stage switch modules;

the method comprising the steps of;

storing credit information associated to each of the second stage switch modules indicating a number of free data packet buffer locations in the respective second stage switch module;

selecting one of the second stage switch modules in dependence on the credit information;

forwarding the received data packet from the first stage switch module to the selected second stage switch module;

forwarding the received data packet from the selected second stage switch module to the respective third stage switch module, from which the received data packet is to be sent;

after sending the data packet from the respective third stage switch module, delivering a credit information about the freed data packet buffer location from the third stage switch module to the second stage switch module, wherein the respective second stage switch module is selected according to a credit return strategy.

2. A method according to claim 1, wherein according to the credit return strategy the respective second stage switch module is selected as the one having the most free data packet buffer locations.

3. A method according to claim 2, wherein the respective second stage switch module having the same number of free data packet buffer locations is selected randomly or according to a round-robin scheme.

4. A method according to claim 1, wherein according to the credit return strategy the credit is returned by increasing the number of free third-stage data packet buffer locations in the respective second stage switch module, wherein the respective second stage switch module is chosen by one of a round-robin scheme, by random, and by the second stage switch module having the lowest number of free data packet buffer locations.

5. A method according to claim 1, wherein the delivering of one credit information about the freed data packet buffer location from the third stage switch module to the second stage switch module includes the steps of:

transmitting the credit information from the third stage switch module to the first stage switch module;

adding the credit information to a next data packet to be transmitted to the chosen second stage switch module; and

transmitting the next data packet including the credit information to the chosen second stage switch module.

6. A method according to claim 1, further comprising the steps of:

forwarding the data packets according to a priority scheduling mechanism, wherein transmission of high-priority data packets are preferred to transmission of lower-priority data packets;

overriding the priority scheduling mechanism if the transmission of lower-priority data packets is blocked for a predetermined time or if an override information is generated indicating that one or more of the lower-priority data packet are preferably transmitted, wherein the override information is generated depending on missing low priority data packets in a sequence of data packets in the data buffer of the third stage switch module.

12. A method according to claim 3,

wherein according to the credit return strategy the credit is returned by increasing the number of free third-stage data packet buffer locations in the respective second stage switch module, and

wherein the respective second stage switch module is chosen by one of a round-robin scheme, by random, and by the second stage switch module having the lowest number of free data packet buffer locations.

13. A method according to claim 4, wherein the delivering of one credit information about the freed data packet buffer location from the third stage switch module (3) to the second stage switch module includes the steps of:

transmitting the credit information from the third stage switch module to the first stage switch module;

adding the credit information to a next data packet to be transmitted to the chosen second stage switch module; and

transmitting the next data packet including the credit information to the chosen second stage switch module.

7. A first stage switch module of a three or more stage switching device comprising:

a number of data inputs;

a number of data outputs to be connected to second stage switch modules;

a data packet buffer to receive and to store externally received data packets;

a credit memory to store a first credit information for each of the second stage switch modules, wherein the credit memory has an input to receive an information about a freed data packet buffer location in one of the second stage switch modules;

a packet scheduling means to select the data output, on which a received data packet is to be sent, depending on the stored credit information of each of the second stage switch modules connected to the data outputs;

a credit insertion means to insert one or more credits in a data packet to be sent to a chosen second stage switch module associated with a respective data output to return the one or more credits according to a second credit information to the chosen second stage switch module wherein the second stage switch module is chosen by the packet scheduling means according to an appropriate credit return strategy.

9. A switching module comprising:

a first stage switch module according to claim 7,

and a third stage switch module, the third stage switch module comprising

a number of data inputs to be connected to second stage switch modules;

a number of data outputs;

a data packet buffer to receive and to store data packets from the second stage switch modules;

a credit extraction means to extract first credit information sent by the second stage switch modules and to provide the respective credit information used for a path selecting function which is operable to select a path for a data packet between a first stage switch module and a second stage switch module;

a packet scheduling means to send data packets to the respective data output in a given order and according to their destination and to return a credit information to one of the second stage switch modules,

wherein the first stage switch module and the third stage switch module are commonly integrated in one device, wherein at least one data line is provided to transmit credit information from the third-stage switch module to the first-stage switch module.

10. A switching device for controlling a data packet flow comprising

a first number of first stage switch modules according to claim 7;

a second number of second stage switch modules; and

a third number of third stage switch modules, each third stage switch module comprising;

a number of data inputs to be connected to second stage switch modules;

a number of data outputs;

a data packet buffer to receive and to store data packets from the second stage switch modules;

a credit extraction means to extract first credit information sent by the second stage switch modules and to provide the respective credit information used for a path selecting function which is operable to select a path for a data packet between a first stage switch module and a second stage switch module;

a packet scheduling means to send data packets to the respective data output in a given order and according to their destination and to return a credit information to one of the second stage switch modules;

each of the first, second, and third switch modules having a number of data inputs, a number of data outputs, and a data packet buffer, wherein the data outputs of the first stage switch modules are at least partially connected to the data inputs of the second stage switch modules, wherein the data outputs of the second stage switch modules are at least partially connected to the data inputs of the third stage switch modules,

wherein a data packet received at a data input of one of the first stage switch modules is forwarded to a specific data output of one of the third stage switch modules,

wherein the respective first credit information used for a path selecting function is provided to the credit memory of the first stage switch module to be stored,

wherein the respective second credit information is provided to the credit insertion means to insert in a data packet credit information of one or more credits to be sent to a chosen second stage switch module associated with a respective data output to return the one or more credits to the chosen second stage switch module according to the appropriate credit return strategy.

11. A switching device according to claim 10, wherein the second number of second-stage switch modules is bigger than the first number of first-stage switch modules.

8. A third stage switch module comprising:

a number of data inputs to be connected to second stage switch modules;

a number of data outputs;

a data packet buffer to receive and to store data packets from the second stage switch modules;

a credit extraction means to extract first credit information sent by the second stage switch modules and to provide the respective credit information used for a path selecting function which is operable to select a path for a data packet between a first stage switch module and a second stage switch module;

a packet scheduling means to send data packets to the respective data output in a given order and according to their destination and to return a credit information to one of the second stage switch modules.