Scheduling with different time intervals

• US 6,760,328 B1
• Filed: 10/14/1999
• Issued: 07/06/2004
• Est. Priority Date: 10/14/1999
• Status: Expired due to Fees

• Current Assignee: Synchrodyne Networks Incorporated
• Original Assignee: Synchrodyne Networks Incorporated
• Inventors: Ofek, Yoram
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): SHAH, CHIRAG G
• Application Number:
  US09/418,279
• Time in Patent Office: 1,727 Days
• Field of Search: 370/389, 370/503, 370/517, 370/252, 370/253, 370/465, 370/519, 370/353, 370/356, 370/357, 370/369, 370/375, 370/376, 370/347, 370/400, 370/401, 370/395.4, 370/468
• US Class Current: 370/389
• CPC Class Codes: H04J 2203/0089 Multiplexing, e.g. coding, scrambling, SONET
• CPC Class Codes: H04L 12/40058 Isochronous transmission
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 2012/5624 Path aspects, e.g. path bundling
• CPC Class Codes: H04L 2012/5674 Synchronisation, timing recovery or alignment
• CPC Class Codes: H04L 2012/6472 Internet
• CPC Class Codes: H04L 2012/6481 Speech, voice
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/206 Real Time traffic
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The invention describes a method for transmitting data packets over a packet switching network with widely varying link speeds. The switches of the network maintain a common time reference (CTR). Each switch along a route from a source to a destination forwards data packets in periodic time frames (TFs) of a plurality of durations that are predefined using the CTR. The time frame duration can be longer than the time duration required for transmitting a data packet, in which case the exact position of a packet in the time interval is not predetermined. In accordance with the present invention, different time frame intervals: TF1, TF2, and so on are used for forwarding over links with different capacities. Employing different time frame intervals is useful in heterogeneous networks with widely varying link speeds, since the number of bytes that can be transmitted during one time frame of one of, for example, 500/125/62.5/12.5 microseconds changes according to the link capacity and various other system parameters and considerations, such as, maximum data packet size. When the transmission of a data packet cannot be completed before the beginning of the next time frame, a time-driven preemption priority can be used in order to ensure the timely transmission of real-time data packet before “best effort” data packets. When the transmission of a data packet cannot be completed in its current time frame the transmission of this data packet can continue in the following time frames.

Claims

1. A system for scheduling and managing data transfer of data packets from at least one source to at least one destination over a network with a plurality of switches, wherein the transfer of the data packets is provided during respective ones of a plurality of predefined time intervals, wherein each of the predefined time intervals is comprised of a plurality of predefined time frames, wherein the time frames have at least one predefined duration, said system comprising:

a common time reference signal coupled to all selected ones of said switches, wherein the common time reference is partitioned into time frames of at least one predefined duration;

wherein the selected ones of said switches have a plurality of uniquely addressable input ports and output ports, for receiving and transmitting the data packets;

wherein each of the respective data packets starts to be received during a first one of the time frames which has a first predefined duration by a first input port of a first switch from the selected ones of said switches, and starts to be transmitted during a second one of the time frames which has a second predefined duration by a first output port of the first switch;

wherein each of the respective data packets starts to be received during a third one of the time frames which has a third predefined duration, by a second input port of a second switch from the selected ones of said switches, and starts to be transmitted during a fourth one of the time frames which has a fourth predefined duration, by a second output port of the second switch;

wherein the first switch and the second switch are interconnected via a sequence of communication links in a path;

a first scheduling controller in the first switch for mapping from a first predefined time frame with the first predefined duration, within which the respective data packet is transferred into the respective switch, to a second predefined time frame with the second predefined duration, within which the respective data packet is transmitted out of the respective switch, wherein the scheduling controller is responsive to the common time reference signal;

a second scheduling controller in the second switch for mapping from a third predefined time fame with the third predefined duration, within which the respective data packet is transferred into the respective switch, to a fourth predefined time frame with the fourth predefined duration, within which the respective data packet is transmitted out of the respective switch, wherein the second scheduling controller is responsive to the common time reference signal; and

wherein there is at least one predefined time interval between at least one of the following;

the first predefined time frame and the third predefined time frame, the first predefined time frame and the fourth predefined time frame, the second predefined time frame and the third predefined time frame, the second predefined time frame and the fourth redefined time frame.

2. The system as in claim 1, wherein the common time reference signal is in accordance with the Coordinated Universal Time (UJTC) standard.

3. The system as in claim 1, wherein the time frames of the third predefined duration are of different duration than the time frames of the fourth predefined duration.

4. The system as in claim 1, wherein the time frames of the first predefined duration are of different duration than the time frames of the second predefined duration.

5. The system as in claim 1,

wherein a predefined number of contiguous time frames comprise a time cycle;

wherein there are a plurality of time cycles that are contiguous; and

wherein the first scheduling controller and second scheduling controller select respective predefined time frames within each of the respective time cycles to transmit the respective data packet.

6. The system as in claim 1,

wherein a first number of contiguous time frames of the first predefined duration comprise a time cycle of a fifth predefined duration;

wherein the time cycles of the fifth predefined duration are contiguous;

wherein a second number of contiguous time frames of the second predefined duration comprise a time cycle of a sixth predefined duration;

wherein the time cycles of the sixth predefined duration are contiguous; and

wherein the first scheduling controller selects a predefined time frame within each of the cycles to transmit the respective data packet.

7. The system as in claim 6, wherein the time cycle of the fifth predefined duration is equal to the time cycle of the sixth predefined duration.

8. The system as in claim 6, wherein the time cycle of the fifth predefined duration is larger than the time cycle of the sixth predefined duration.

9. The system as in claim 6, wherein the time cycle of the fifth predefined duration is smaller than the time cycle of the sixth predefined duration.

10. The system as in claim 1,

wherein a first number of contiguous time frames of the first predefined duration comprise a time cycle of a fifth predefined duration;

wherein the time cycles of the fifth predefined duration are contiguous;

wherein a second number of contiguous tine frames of the second predefined duration comprise a time cycle of a sixth predefined duration;

wherein the time cycles of the sixth predefined duration are contiguous;

wherein a third number of time cycles of the fifth predefined duration comprise a first super cycle;

wherein the first super cycles are contiguous;

wherein a fourth number of time cycles of the sixth predefined duration comprise a second super cycle;

wherein the second super cycles are contiguous; and

wherein each of the first and second scheduling controllers selects a predefined time frame within each of the super cycles to transmit the respective data packets.

11. The system as in claim 10, wherein the first super cycle and the second super cycle have equal durations.

12. The system as in claim 10, wherein the first super cycle and the second super cycle start at a same time with respect to the common time reference.

13. The system as in claim 10, wherein the first super cycle and the second super cycle have different durations.

14. The system as in claim 1, wherein a predefined number of contiguous time frames comprise a time cycle;

wherein there are a plurality of time cycles that are contiguous;

wherein a fixed number of a plurality of contiguous ones of the time cycles comprise a super cycle;

wherein the super cycle is periodic; and

wherein each of the first and second scheduling controllers selects a predefined time frame within each of the super cycles to transmit the respective data packets.

15. The system as in claim 1, wherein the common time reference signal is coupled from a Global Positioning System (GPS);

wherein the coupling from GPS is at least one of the following;

directly to selected ones of said switches, directly to selected ones of said input ports, directly to selected ones of said out ports, indirectly to selected ones of said switches, indirectly to selected ones of said input ports, indirectly to selected ones of said out ports, indirectly to selected ones of said switches via adjacent switches, indirectly to selected ones of said input ports via adjacent switches, indirectly to selected ones of said out ports via adjacent switches, indirectly to selected ones of said switches via adjacent network interfaces, indirectly to selected ones of said input ports via adjacent network interfaces, indirectly to selected ones of said out ports via adjacent network interfaces.

16. The system as in claim 1, wherein the position of a beginning of said data packet within each time frame is at least one of the following:

in an arbitrary position, in a predefined position.

17. The system as in claim 15, wherein the super cycle duration is equal to at least one of the following:

one second as measured using the Coordinated Universal Time (UTC) standard, a fraction of a second as measured using the Coordinated Universal Time (UTC) standard, a predefined number of seconds as measured using the Coordinated Universal Time (UTC) standard.

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

a plurality of virtual pipes;

wherein each of the virtual pipes has at least two of the switches interconnected via a sequence of communication links in a path;

wherein for each switch within one of the virtual pipes there is a fifth predefined time frame within which a respective beginning of data packet is transferred into the respective switch, and a sixth predefined time frame within which the respective beginning of data packet is forwarded out of the respective switch.

19. The system as in claim 18, wherein the transmission over each of said communication links is provided during a time frame with a duration selected from a plurality of predefined time frame durations.

20. The system as in claim 18, wherein the mapping by the first scheduling controller provides consistent fixed time intervals between the input to and output from at least a selected one of the plurality of virtual pipes.

21. The system as in claim 18, wherein each link of each of the virtual pipes has a selected one of a plurality of the predefined time frame durations.

22. The system as in claim 18,

wherein a predefined number of contiguous time frames of the fifth predefined duration comprise a time cycle of a seventh predefined duration;

wherein the time cycles of the seventh predefined duration are contiguous;

wherein a predefined number of contiguous time frames of the sixth predefined duration comprise a time cycle of a eighth predefined duration;

wherein the time cycles of the eighth predefined duration are contiguous;

wherein a predefined number of contiguous time frames of a ninth predefined duration comprise a time cycle of a tenth predefined duration;

wherein the time cycles of the tenth predefined duration are contiguous; and

wherein the transmission over at least a selected one of the plurality of virtual pipes utilizes at least one of a time cycle of the seventh predefined duration, a time cycle of the eighth predefined duration, and a time cycle of the tenth predefined duration.

23. The system as in claim 22,

wherein there are a plurality of different time frame durations;

and

wherein there are a plurality of different time cycle durations.

24. The system as in claim 4, wherein the first scheduling controller maps the respective data packet received during the tint predefined time frame for output during a selected one of the second predefined time frames in which the respective data packet is scheduled to be forwarded out of the respective switch.

25. The system as in claim 1, wherein the scheduling controller maps the data packet to one of a plurality of predefined ones of the second predefined time frames in which the respective data packet is scheduled to be forwarded out of the respective switch.

26. The system as in claim 4, wherein the scheduling controller maps the data packet, from one of a plurality of the first predefined time frames within which a respective data packet is transferred into the respective switch, to the second predefined time frame in which the respective data packet is scheduled to be transmitted out of the respective switch.

27. The system as in claim 4, wherein the scheduling controller maps the data packet, from one of a plurality of the first predefined time frames within which a respective data packet is transferred into the respective switch, to one of a plurality of the second predefined time frames within which the respective data packet is scheduled to be transmitted out of the respective switch.

28. The system as in claim 1, wherein the respective one of the first and second scheduling controllers maps the respective data packet to be forwarded out of the respective switch, during a plurality of predefined ones of the second predefined time frames.

29. The system as in claim 1, wherein the data packet is received during a sequence of a plurality of first predefined time frames.

30. The system as in claim 29, wherein the scheduling controller maps the data packet according to the first time frame in said sequence of the plurality of first predefined time frames.

31. A switching system for scheduling and managing data transfer, during at least one of a plurality of consecutive time frames having boundaries, of a plurality of data packets of at least a first priority and a second priority, from at least one source to at least one destination, the system comprising:

a plurality of switches with plurality of uniquely addressable input ports and output ports, for receiving and transmitting the data packets;

means for scheduling the data packets for transmission out of the output port;

a select buffer and time-driven preemption controller for selecting a second priority data packet for active transmission out of the output port when there is no first priority data packet scheduled for a given respective one of the time frames;

detection means for detecting boundaries between two consecutive time frames, and for detecting an overlap of an active transmission of the second priority data packet into a second time frame relative to a scheduled transfer of at least one first priority data packet during said second time frame, to provide a time-driven preemption signal;

preemption logic, responsive to the time-driven preemption signal, for interrupting the overlapping active transmission from the respective output port of the respective second priority data packet, and for marking the respective second priority data packet as to where the transfer was interrupted, and for initiating active transmission of at least one scheduled first priority data packet, and for providing a completion signal upon completion of the scheduled transfer of at least one scheduled first priority data packet; and

resumption logic, responsive to the completion signal, for resuming the active transmission of the respective second priority data packet from the marking where the transfer was interrupted.

32. The system as in claim 31, wherein the first priority data packets are further characterized as at least one of Constant Bit Rite (CBR) and Variable Bit Rate (VBR) data packets.

33. The system as in claim 31,

wherein the first priority data packets are further comprised of a high first priority and a low first priority;

wherein the system is further comprised of a first priority select buffer and time-driven preemption controller for first selecting the high first priority data packet for active transmission, if available, and if not available, for then selecting the low first priority data packet for active transmission; and

wherein the select buffer and time-driven preemption controller selects the second priority data packet when there is no high first priority data packet and no low first priority data packet scheduled for the given respective one of the time frames.

34. The system as in claim 33,

wherein the preemption logic is responsive to the preemption signal, for interrupting the overlap active transmission from the output port of the low first priority data packet, and for marking the low first priority data packet as to where the transfer was interrupted, and for initiating active transmission of at least one scheduled high first priority data packet, and for providing a completion signal upon completion of the scheduled transfer of the high first priority data packets;

and

wherein the resumption logic, responsive to the completion signal, for resuming the active transmission of the low first priority data packet from the marking where the transfer was interrupted.

35. The system as in claim 31, wherein the time frame boundaries are determined responsive to a common time reference (CTR).

36. The system as in claim 35, wherein the common time reference signal is coupled from a Global Positioning System (GPS).

37. A system for scheduling data packets on a plurality of switches, said system comprising:

each switch with a plurality of input ports each having a unique address;

each switch with a plurality of output ports each having a unique address;

a common time reference signal coupled to each of the input ports and output ports, wherein the common time reference at each of the input ports and output ports is partitioned into time cycles;

wherein each time cycle at each of the input ports is partitioned into time frames, wherein each time frame duration at each of the input ports has one of a plurality of predefined durations;

wherein each time cycle at each of the output ports is partitioned into time frames, wherein each time frame duration at each of the output ports has one of a plurality of predefined durations;

a first switching fabric for simultaneously scheduling coupling of incoming data packets between selected ones of the input ports and the output ports responsive to the common time reference, wherein each of the selected input ports has an associated first time frame duration, and wherein each of the selected output ports has an associated second time frame duration;

a second switching fabric for simultaneously scheduling coupling of incoming data packets between selected ones of the input ports and the output ports responsive to the common time reference, wherein each of the selected input ports has an associated third time frame duration, and wherein each of the selected output ports has an associated fourth time frame duration;

wherein responsive to the common time reference there is a predefined time interval between the beginning of at least on of the following;

the first time frame duration and third time frame duration, the first time frame duration and fourth time frame duration, the second time frame duration and third time frame duration, the second time frame duration and fourth time frame duration.

38. The systems as in claim 37, wherein one or more data packets can be communicated within each of the time frames.

39. The systems as in claim 37,

wherein a predefined number of contiguous first input time frames (i1) of duration d1 at a first input port are grouped into a first input time cycle (ic1), wherein i1 is at least 1;

wherein a predefined number of contiguous second input time frames (i2) of duration d2 at a second input port are grouped into a second input time cycle (ic2), wherein i2 is at least 1;

wherein a predefined number of contiguous third input time frames (i3) of duration d3 at a third input port are grouped into a third input time cycle (ic3), wherein i3 is at least 1;

wherein a predefined number of contiguous first output time frames (o1) of duration t1 at a first output port are grouped into a first output time cycle (oc1), wherein o1 is at least 1;

wherein a predefined number of contiguous second output time frames (o2) of duration t2 at a second output port are grouped into a second output time cycle (oc2), wherein o2 is at least 1;

wherein a predefined number of contiguous third output time frames (o3) of duration t3 at a third output port are grouped into a third output time cycle (oc3), wherein o3 is at least 1;

wherein the scheduling of data packets on the input ports and output ports of the switch have plurality of predefined mappings from selected ones of the input time frames with selected ones of the input time cycles to selected ones of the output time frames within selected ones of the output time cycles.

40. The systemn as in clam 39, further comprising:

a routing controller with a routing table for selecting at least one output port that said respective data packets will be forwarded to;

wherein the routing controller attaches a time of arrival (ToA) to incoming data packets at the input port using the predefined time frame duration and the time cycle associated wit the respective input port;

wherein the time of arrival (ToA) relates to the common time reference and is represented as a time frame number within a time cycle; and

wherein the ToA has a unique representation on each of at least the first input port, the second input port, and the third input port.

41. The system as in claim 40, wherein after the incoming data packet is transferred to one of the output ports, the ToA unique representation is utilized to transform to a unique output port representation on each of at least the first output port, the second output port, and the third output port.

42. The system as in claim 41, further comprising:

a memory partitioned into plurality of buffers; and

a scheduling controller for selecting one of the plurality of buffers;

wherein the unique output port representation is used by the scheduling controller to select one of the plurality of buffers.

43. The system as in claim 42,

wherein each of the buffers is uniquely associated with one of the time frames;

and

wherein selected ones of the buffers determine the selected one of the time frames for the time the data packet to be forwarded from the output port.