Fast switching of data packet with common time reference

• US 6,757,282 B1
• Filed: 03/28/2000
• Issued: 06/29/2004
• Est. Priority Date: 11/09/1999
• Status: Expired due to Fees

• Current Assignee: Synchrodyne Networks Incorporated
• Original Assignee: Synchrodyne Networks Incorporated
• Inventors: Ofek, Yoram
• Primary Examiner(s): Pezzlo, John
• Assistant Examiner(s): Tsegaye, Saba
• Application Number:
  US09/536,809
• Time in Patent Office: 1,554 Days
• Field of Search: 370/230, 370/235, 370/252, 370/253, 370/387, 370/397, 370/395, 370/396, 370/392, 370/399, 370/352, 370/353, 370/356, 370/413, 370/401, 370/503, 370/517
• US Class Current: 370/389
• CPC Class Codes: H04Q 11/0005 Switch and router aspects
• CPC Class Codes: H04Q 2011/0016 using wavelength multiplexing or demultiplexing
• CPC Class Codes: H04Q 2011/0024 using space switching
• CPC Class Codes: H04Q 2011/0039 Electrical control
• CPC Class Codes: H04Q 2011/0045 Synchronisation
• CPC Class Codes: H04Q 2011/005 Arbitration and scheduling

Abstract

An input buffer switch scheduling method operates responsively to a global common time reference. The global time reference is used to enable pre-computed switching schedules from an input port to an output port, thereby, expediting switching and increasing the performance and scalability of the switching system. In the switch architecture disclosed in this invention the switching fabric operates according to predefined switching schedules. The switch decodes the data packet headers in order to determine the destination output port and the switching time responsive to the global common time reference. This decoded switching time is then used by the pre-defined switching schedules in order to switch the data packet from the input port to the output port. The usage of predefined switching schedules provides scalability to the design of high performance input buffer switch design.

Claims

1. A method of scheduling and controlling switching of data packets, each comprising a header portion and a payload portion, from an input source to an output destination, through a switch having a plurality of addressable input ports and a plurality of addressable output ports, the method comprising:

scheduling on a time slot assignment basis, wherein a provided common time reference (CIR) is divided into a plurality of contiguous periodic super-cycles each comprised of at least one contiguous time cycle each comprised of at least one contiguous time frame each comprised of at least one contiguous time slot;

providing a plurality of queues in a first memory wherein each of the plurality of queues is associated with a particular one of the output ports for each one of the plurality of input ports;

wherein each time frame is associated with a respective one of the plurality of queues that are associated with a particular one of the output ports in said first memory;

analyzing the header portion of a respective one of the data packets;

selecting one of the plurality of queues as a selected queue for a particular one of the output ports responsive to the analyzing;

storing the data packets in the selected queue;

partitioning each of the data packets into data units, wherein each of the data units can be communicated from the input port to the output port within the duration of one of the time slots;

storing information, in a second memory, defining coupling for a selected subset of the time slots, in each of the time frames in each of the time cycles, and in each of the super-cycles, of each of the respective data units from a respective one of the queues to a respective one of the output ports; and

scheduling for each of the data units of each of the respective data packets, from the respective input port to the respective output port, responsive to at least one of retrieving a stored value from the second memory defining the time slot in which said data unit will be switched to the output port, and computing the time slot in which said data unit will be switched to the output port.

2. The method as in claim 1, further comprising:

generating an input request message (IRM) responsive to the requirement to compute the time slot in which said data unit will be switched to the output port.

3. The method as in claim 2, further comprising:

generating at least one of an input reject message and an input schedule message responsive to the IRM.

4. The method as in claim 3, further comprising:

updating the information in the second memory defining the coupling of the respective data unit from a respective one of the queues to a respective one of the output ports responsive to the input schedule message.

5. The method as in claim 3, further comprising:

generating a second IRM responsive to the input reject message.

6. The method as in claim 5, further comprising:

generating at least one of a second input reject message and a second input schedule message responsive to the second IRM.

7. The method as in claim 6, further comprising:

updating the information in the second memory defining the coupling of the respective data unit from a respective one of the queues to a respective one of the output ports responsive to the second input schedule message.

8. The method as in claim 1, further comprising:

deriving the CTR from a coordinated universal time (UTC) standard, wherein the super-cycle is one of a single UTC second, a predefined integer number of UTC seconds, and a fraction of one UTC second.

9. The method as in claim 8, further comprising:

obtaining the UTC via a Global Positioning System (GPS).

10. The method as in claim 1, further comprising:

updating the information, in the second memory, regarding the coupling of each of the respective data units from a respective one of the queues to a respective, one of the output ports during a respective one of the time slots, within a respective one of the time frames within a respective one of the time cycles and within a respective one of the super-cycles, responsive to predefined external scheduling information.

11. The method as in claim 1, further comprising:

partitioning a subset of the plurality of queues as associated with one of a CBR (constant bit rate) part, a VBR (variable bit rate) part, and a Fast part;

partitioning a subset of the data packets into a respective plurality of data units that follow a predefined periodic pattern in the Fast part of said queue; and

using the existing information in the second memory to define the coupling of each one of the plurality of data units in the Fast part of said queue from a respective one of the Fast part of the queues to a respective one of the output ports.

12. The method as in claim 11, further comprising:

providing a predefined switching schedule time in the second memory, defining a fixed periodic connection schedule, for all data units to be switched to the output port in the Fast part of the queue.

13. The method as in claim 12, further comprising:

providing a successive plurality of switches;

computing an associated successive plurality of switching schedules for fixed periodic connection over the successive plurality of switches responsive to the CTR.

14. The method as in claim 11, further comprising:

determining what amount of memory space in the Fast part of the queue is unused by the predefined periodic pattern of data packets;

using said unused memory space in the Fast part of the queue for communication of “

best effort”

data packets.

15. The method as in claim 14, further comprising:

determining what amount of memory space in the Fast part of the queue is unused memory space by the predefined periodic pattern of data packets;

using said unused memory space in the Fast part of the queue for communication of variable bit rate (VBR) data packets.

16. A system for scheduling and controlling switching of data packets, each comprising a header portion and a payload portion, from an input source to an output destination, through a switch having a plurality of addressable input ports and a plurality of addressable output ports, the system comprising:

means for scheduling the transfer of the data packets on a time slot assignment basis, wherein a provided common time reference (CTR) is divided into a plurality of contiguous periodic super-cycles each comprised of at least one contiguous time cycle each comprised of at least one contiguous time frame each comprised of at least one contiguous time slot;

a first memory comprising a plurality of queues wherein for each of the plurality of queues there is associated a particular one of the output ports for each one of the plurality of input ports;

wherein each of the queues in said first memory is associated with a respective one of the plurality of time frames;

means for analyzing the header portion of a respective one of the data packets;

means for selecting one of the plurality of queues as a selected queue for a particular one of the output ports responsive to the means for analyzing;

means for storing the data packets in the selected queue;

means for partitioning each of the data packets into data units, wherein each of the data units can be communicated from the input port to the output port within the duration of one of the time slots;

means for storing in the second memory information defining coupling for a subset of the time slots, in each of the time frames in each of the time cycles and in each of the super-cycles, of the respective data unit from a respective one of the queues to a respective one of the output ports; and

additional means for scheduling, for each of the data units, of the respective data packet, from the respective input port to the respective output port, responsive to one of the following;

retrieving a stored value from the second memory defining the time slot in which said data unit will be switched to the output port, and computing the time slot in which said data unit will be switched to the output port.

17. The system as in claim 16, further comprising:

means for generating an input request message (IRM) responsive to the requirement to compute the time slot in which said data unit will be switched to the output port.

18. The system as in claim 17, further comprising:

means for generating at least one of an input reject message and an input schedule message responsive to the IRM.

19. The system as in claim 18, further comprising:

means for updating the information in the second memory defining the coupling of the respective data unit from a respective one of the queues to a respective one of the output ports responsive to the input schedule message.

20. The system as in claim 18, further comprising:

means for generating a second IRM responsive to the input reject message.

21. The system as in claim 19, further comprising:

means for generating at least one of a second input reject message and a second input schedule message responsive to the second input request message (IRM).

22. The system as in claim 21, further comprising:

means updating the information in the second memory defining the coupling of the respective data unit from a respective one of the queues to a respective one of the output ports responsive to the second input schedule message.

23. The system as in claim 16, further comprising:

means for deriving the CTR from a coordinated universal time (UTC) standard, wherein the super-cycle is one of a single UTC second, a predefined integer number of UTC seconds, and a faction of one UTC second.

24. The system as in claim 23, further comprising:

means for obtaining the UTC via a Global Positioning System (GPS).

25. The system as in claim 16, further comprising:

means for updating the information, in the second memory, regarding the coupling of the respective data unit from a respective one of the queues to a respective one of the output ports during a respective one of the time slots, within a respective one of the time frames within a respective one of the time cycles and within a respective one of the supercycles, responsive to predefined external scheduling information.

26. The system as in claim 16, further comprising:

means for partitioning a subset of the plurality of queues into a CBR (constant bit rate) part, a VBR (variable bit rate) part, and a Fast part;

means for partitioning a subset of the data packets into a respective plurality of data units that follow a predefined periodic pattern in the Fast part of said queue; and

means for defining the coupling of each one of the plurality of data units in the Fast part of said queue from a respective one of the Fast part of the queues to a respective one of the output ports, responsive to the information in the second memory.

27. The system as in claim 26, wherein for all data units to be switched to the output port in the Fast part of the queue, there is a predefined switching schedule time stored in the second memory, defining a fixed periodic connection schedule.

28. The system as in claim 27, further comprising:

a successive plurality of switches;

wherein a respective associated successive plurality of switching schedules is computed for fixed periodic connection over the successive plurality of switches responsive to the CTR.

29. The system as in claim 26, further comprising:

means for determining an amount of memory space in the Fast part of the queue that is unused memory space not utilized by the predefined periodic pattern of data packets;

means for using said unused memory space in the Fast part of the queue for communication of “

best effort”

data packets.

30. The system as in claim 29, further comprising:

means for determining an amount of memory space in the Fast part of the queue that is unused memory space not utilized by the predefined periodic pattern of data packets;

means for using said unused memory space in the Fast part of the queue for communication of variable bit rate (VBR) data packets.

31. The system as in claim 16, further comprising:

means for determining a respective data packet location within a flow of data packets, responsive to the header portion of the data packet;

wherein the data packet location is one of a first data packet location in the flow, and a middle data packet location in the flow.

32. The system as in claim 31, further comprising:

means for generating an input request message (IRM), when the data packet is in the first data packet location in the flow, for computing a switching schedule responsive to the first data packet location in the flow.

33. The system as in claim 31, further comprising:

means for using a previously computed schedule for an input request message (IRM) that was computed responsive to the first data packet location in the flow, when the data packet is in the middle data packet location in the flow.