Packet switching with common time reference over links with dynamically varying delays

• US 6,038,230 A
• Filed: 07/22/1998
• Issued: 03/14/2000
• Est. Priority Date: 07/22/1998
• Status: Expired due to Term

• Current Assignee: Synchrodyne Networks Incorporated
• Original Assignee: Synchrodyne, Inc.
• Inventors: Ofek, Yoram
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Nguyen, Kim T.
• Application Number:
  US09/120,515
• Time in Patent Office: 601 Days
• Field of Search: 370/252, 370/253, 370/389, 370/465, 370/503, 370/517, 370/519, 370/353, 370/356, 370/357
• US Class Current: 370/389
• CPC Class Codes: H04J 3/0658 Clock or time synchronisation among packet nodes
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The invention describes a method for transmitting and forwarding packets over a packet switching network wherein the delay between two switches increases, decreases, or changes arbitrarily over time. Packets are being forwarded over each link inside the network in predefined periodic time intervals. The switches of the network maintain a common time reference, which is obtained either from an external source (such as GPS--Global Positioning System) or is generated and distributed internally. The time intervals are arranged with simple periodicity and complex periodicity (like seconds and minutes of a clock). When the delay increases at some point of time, a packet may be late for its predefined forwarding time interval. In such case, the packet is delayed until the next time interval of its virtual pipe. When the link delay decreases, packets are buffered until the first time interval of its virtual pipe.

Claims

1. A system for transferring data packets from at least one source to at least one destination, wherein the transfer of the data packets is provided during respective ones of a plurality of time intervals, wherein each of the time intervals is comprised of a plurality of time frames, the system comprising:

a virtual pipe comprising at least two switches interconnected by communication links in a path, the virtual pipe having a defined maximum delay between any two of the switches, each of the switches having a plurality of input ports and a plurality of output ports each with a unique address, wherein the input ports provide for receiving the packets from the source and for recording the time of arrival (TOA) for each said separate packet;

a common time reference signal coupled to each of the switches;

a scheduling controller for determining for each switch a first scheduled time within a first predefined time frame within which a respective one of the packets is scheduled to be transferred out of the respective switch, and a second scheduled time within a second predefined time frame within which the respective data packet is alternately scheduled to be transferred out of the respective switch, and a third predefined scheduled time within a third predefined time frame for alternately scheduling the transfer of the respective packet from the respective output port of the switch;

wherein the first, second, and third predefined time frames are determined responsive to the common time reference;

a delay analysis controller for determining the difference between each of the first, second, and third predefined time frames and the time of arrival for a respective one of the packets, wherein the difference is compared to the maximum defined delay to select the respective predefined time frame having a difference closest to and less than the defined delay;

wherein the scheduling controller is responsive to the delay analysis controller, for scheduling the respective data packet to be associated with the selected respective predefined time frame.

2. The system as in claim 1, wherein the predefined interval is comprised of a fixed number of contiguous time frames comprising a time cycle.

3. The system as in claim 2, wherein the time cycles are contiguous.

4. The system as in claim 2, wherein the time frames associated with a particular one of the switches within the virtual pipe are associated for the same respective switches in all the time cycles.

5. The system as in claim 4, wherein the time frames associated with the particular ones of the switches are associated with one of input into or output from that respective switch.

6. The system as in claim 4, wherein a fixed number of a plurality of contiguous ones of the time cycles comprise a super cycle;

wherein the super cycle is periodic.

7. The system as in claim 1, wherein the common time reference signal coupled to each of the switches comes from a GPS (Global Positioning System).

8. The system as in claim 1, wherein the common time reference signal coupled to each of the switches conforms to the UTC (Coordinated Universal Time) standard.

9. The system as in claim 8, wherein the super cycle duration is equal to one second as measured using the UTC (Coordinated Universal Time) standard.

10. The system as in claim 8, wherein the super cycle duration is equal to a predefined number of seconds as measured using the UTC (Coordinated Universal Time) standard.

11. The system as in claim 8, wherein the super cycle duration is equal to a predefined fraction of a second measured using the UTC (Coordinated Universal Time) standard.

12. The system as in claim 1, wherein the communication links are wireless communication links.

13. The system as in claim 1, wherein the communication links are wireless communication links from a ground station to a satellite.

14. As the system in claim 1, wherein the communication links are wireless communication links between two satellites orbiting the earth.

15. The system as in claim 1, wherein the position of said data packet within said time frame is arbitrary.

16. A system for transferring data packets from at least one source to at least one destination, wherein the transfer of the data packet is provided during respective ones of a plurality of time intervals, wherein each of the time intervals is comprised of a plurality of time frames, said system comprising:

a virtual pipe comprising at least two switches interconnect by links in a path;

wherein each of the switches has a plurality of input ports and a plurality of output ports each with a unique address;

a delay analysis and scheduling controller at each of the output ports of said switch; and

a common time reference signal coupled to each of the switches;

wherein for each switch there is a predefined time frame within which a respective packet is transferred into the respective switch, and a separate predefined time frame within which the respective packet is transferred out of the respective switch;

wherein each switch has an associated predefined set of time frames wherein during one time frame of the predefined set of time frames, the switch outputs a data packet from said virtual pipe;

wherein when each of the packets arrives, it is assigned a time of arrival (TOA) responsive to an instant value of the common time reference, where the packet is scheduled to be output during a not fully occupied subsequently available time frame of the respective predefined set of time frames; and

wherein the subsequently available time frame is determined responsive to determining that the time elapsed since the time of arrival is greater than a predefined threshold.

17. The system as in claim 16, wherein the subsequently available time frame is determined by the delay analysis and scheduling controller as the first time frame available from the set of time frames associated with said virtual pipe.

18. The system as in claim 16, wherein there are at least two virtual pipes comprising a first virtual pipe and a second virtual pipe;

wherein packet communication is scheduled independently for the first and second virtual pipes;

wherein when one of the switches operationally fails in the first virtual pipe, the communication of the respective packets is rescheduled and resynchronized from within the first virtual pipe to within the second virtual pipe;

wherein the data packets transferred over the second virtual pipe are resynchronized at the switch where the two virtual pipes converge at a converging node, such that after said converging point, scheduling of the data packets transferred over the second virtual pipe is the same as scheduling of the data packets transferred over the first virtual pipe.

34. The system as in claim 16, wherein the PID is at least one of an Internet protocol (IP) address, Internet protocol port number, Internet protocol group multicast address, an asynchronous transfer mode (ATM), a virtual circuit identified (VCI), a virtual path identifier (VPI), used in combination as VCI/VPI, and a combined IP address and IP port number.

35. The system as in claim 34, wherein one PID is associated with a plurality of said IP and ATM addresses, and IP port numbers.

19. A system for switching data packets comprising a data packet header, having a PID field, from at least one source of incoming data packets to at least one destination, 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, said system comprising:

a plurality of switches with plurality of uniquely addressable input and output ports;

a common time reference signal coupled to each of the switches;

wherein the common time reference is partitioned into time frames;

wherein a predefined number of contiguous time frames are grouped into a time cycle;

wherein a predefined number of contiguous time cycles are grouped into a super cycle;

a routing controller at the input port for determining which of the plurality of output ports said data packet will be forwarded to, and for attaching a time of arrival (TOA) to incoming data packets;

a delay analysis and scheduling controller for assigning a first feasible time frame, from a selected plurality of predefined time frames associated with a predefined one of the switches, for transfer data packets out from each of the respective switches, responsive to the time of arrival and the unique address of the input port associated with the incoming data packet, and to the PID field in the data packet header.

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

apparatus for providing availability of transmission capacity for each of the time frames, wherein the delay analysis and scheduling controller is responsive to the availability of transmission capacity in said time frame.

21. The system as in claim 20, wherein each of the data packets is comprised of a plurality of bytes of data, and the apparatus for providing availability counts the number of bytes in the data packets already scheduled for transmission during a respective one of the time frames to determine the availability.

22. The system as in claim 19, wherein the position of said data packet in said predefined time frame is arbitrary.

23. The system as in claim 19, wherein the time of arrival reflects the UTC time and is represented as a time frame number within a time cycle and as time cycle number within a super cycle.

24. A system for scheduling the transfer of data packets comprising a data packet header having a PID field, on a switch comprised of a plurality of uniquely addressable input ports and a plurality of uniquely addressable output ports, 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 data packets coupled into the switch are incoming data packets, said system comprising:

a common time reference signal coupled to each of the switches;

wherein the common time reference is partitioned into time frames;

wherein a predefined number of contiguous k time frames are grouped into a time cycle;

wherein k is at least 1;

wherein a predefined number of contiguous l time cycles are grouped into a super cycle;

wherein l is at least 1;

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

wherein the routing controller attaches a time of arrival (TOA) to the incoming data packets;

wherein the time of arrival is derived from the common time reference and is represented as a time frame number within a time cycle and as a time cycle number within a super cycle;

a switching fabric for coupling the incoming data packets between selected ones of the input ports and the output ports;

apparatus for determining availability of transmission capacity for each of the time frames;

a delay analysis and scheduling controller for assigning a first feasible time frame, from a selected plurality of predefined time frames, for transfer of the respective data packet out from each of the respective switches responsive to the time of arrival, the unique address of the respective input port, and the PID field in the data packet header for the respective data packet, and the availability of transmission capacity in said time frame;

a random access memory partitioned into plurality of buffers for storing the respective data packets in associated ones of the buffers associated with the respective time frames; and

a select buffer controller for selecting one of the plurality of buffers for output.

25. The system as in claim 24, wherein the data packet scheduling controller is responsive to the reception of a respective one of the data packets from the switching fabric for assigning a first feasible time frame from a predefined plurality of selected predefined time frames for transferring said respective data packet out from the said switch responsive to the time of arrival attached to the data packet by the routing controller, the unique address of the respective input port, and the PID in the respective data packet header.

26. The system as in claim 25, wherein the first feasible time frame is selected as the first time frame with available transmission capacity for forwarding said data packet.

27. The system as in claim 24, wherein the random access memory is partitioned into k+1 buffers;

wherein first k buffers are for storing data packets to be forwarded from said switch during one of the k time frames in each of said time cycle, as were measured by the common time reference;

wherein the k+1 buffer is for storing "best effort" data packets.

28. The system as in claim 24, wherein in each of the k time frames of the time cycle, the select buffer controller provides for forwarding of the data packets from the corresponding one of the k buffers;

wherein when said first k buffer is empty, said select buffer controller forwards said "best effort" data packets out of said switch.

29. The system as in claim 24, wherein the random access memory is partitioned into (l times k)+1 buffers;

wherein a first (l times k) buffers provide for storing data packets to be forwarded from said switch during one of the (l times k) time frames in each of said super cycle;

wherein a (l times k)+1 buffer is for storing "best effort" data packets.

30. The system as in claim 29, wherein in each of the (l times k) time frames of the super cycle the select buffer controller forwarded data packets from the corresponding one of the (l times k) buffers;

wherein when said (l times k) buffers are empty, said select buffer controller forwards said "best effort" data packets out of said switch.

31. A system for switching data packets, each comprising a data packet header having a PID field and a time stamp, from at least one source to at least one destination, 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, said system comprising:

a plurality of switches with plurality of uniquely addressable input and output ports;

a common time reference signal coupled to each of the switches;

wherein the common time reference partitioned into time frames;

wherein a predefined number of contiguous time frames are grouped into a time cycle;

wherein a predefined number of contiguous time cycles are grouped into a super cycle;

a routing controller for determining uniquely which one of the output ports is scheduled to receive the respective data packet from a respective one of the input ports responsive to the PID field in the data packet header;

apparatus for determining the availability of transmission capacity for each of the respective time frames;

a delay analysis and scheduling controller for assigning a first feasible time frame, from a plurality of predefined time frames, for scheduling transfer of the respective data packet out from the respective switch responsive to the respective time stamp, the unique address of the input port, the PID field in the data packet header, and the availability of transmission capacity in said respective time frame;

a random access memory partitioned into plurality of buffers, each of the buffers associated with a unique one of the time frames; and

a select buffer controller for selecting one of the buffers for output.

32. The system as in claim 31, wherein the first feasible time frame for transferring the data packet out from the respective switch is determined by adding a predefined number of time frames to the time stamp value in the data packet header.

33. The system as in claim 32, wherein the scheduling controller is further comprised of a forwarding table, and wherein the number of predefined time frames added to the time stamp value, in order to determine the first feasible time frame for transferring of said data packet out from said switch, is determined by looking this number up in the forwarding table using the PID in the data packet header as an index to said table.