Shared medium access scheduling with common time reference

• US 6,754,210 B1
• Filed: 07/28/1999
• Issued: 06/22/2004
• Est. Priority Date: 06/11/1998
• Status: Expired due to Term

• Current Assignee: Synchrodyne Networks Incorporated
• Original Assignee: Synchrodyne Networks Incorporated
• Inventors: Ofek, Yoram
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Pizarro, Ricardo M.
• Application Number:
  US09/362,334
• Time in Patent Office: 1,791 Days
• Field of Search: 370/389, 370/390, 370/391, 370/372, 370/241, 370/252, 370/357, 370/356, 370/351, 370/508, 370/509, 370/516, 370/518, 370/464, 370/463, 370/503, 370/396
• US Class Current: 370/389
• CPC Class Codes: H04J 3/0644 External master-clock
• CPC Class Codes: H04J 3/0697 Synchronisation in a packet node
• 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/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9023 for implementing a jitter-buffer
• 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 data packets over a packet switching and shared media networks. The switches of the network maintain a common time reference (CTR), 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 in simple periodicity and complex periodicity (like seconds and minutes of a clock). The present invention provides for synchronous switches to be accessed by end-stations that are located on a shared media network. The shared media network can be of various types, including but not limited to: IEEE P1394 and Ethernet for desktop computers and room area networks, cable modem head-end (e.g., DOCSIS, IEEE 802.14), wireless base-station (e.g., IEEE 802.11), and Storage Area Network (SAN) (e.g., FC-AL, SSA). The end-station can be of corresponding various types including but not limited to: for IEEE 1394: video cameras, VCR and video disk, for cable modem: set-top box with multiple Ethernet connections to video cameras, VCRs, and for wireless: desktop computers and mobile units, and for SAN; disk drives, tape drives, RAM disks, electronic disks, and other storage devices.

Claims

1. A controller system, for scheduling transfer of data packets between one of a point to point network and a shared medium, and an end station and the shared medium, the system comprising:

a source of common time reference signals;

a first scheduling controller for scheduling of a first time frame for the transfer of the data packets from the shared medium to the point to point network, responsive to UTC (Coordinated Universal Time) timing signals; and

a second scheduling controller for scheduling a time interval for the transfer of the data packets from the end station to the shared medium, responsive to the first scheduling controller;

wherein the time interval occurs immediately before the first time frame.

2. The system as in claim 1, wherein the first and the second scheduling controllers schedule their respective data transfer in alternating sequential time order to effectuate the transfer of a plurality of the data packets over a plurality of the first time frames and a plurality of the time intervals.

3. The system as in claim 1, further comprising an access time manager, wherein the first scheduling controller and the second scheduling controller are part of the access time manager.

4. The system as in claim 1, wherein the time frames are structured into a time cycle comprised of a fixed number of contiguous time frames which are structured into a stream of a plurality of contiguous time cycles.

5. The system as in claim 4, wherein the scheduling of transmission of respective data packets occurs at a defined one of the time frame positions within each of the time cycles.

6. The system as in claim 5, wherein the scheduling of transmission of respective data packets to the point-to-point network occurs at multiple defined ones of the time frame positions within each of the cycles.

7. 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, wherein the scheduling of the transmission of respective data packets to the point-to-point network occurs at a defined one of time frame positions periodically during at least one associated respective one of the time cycles during each of the super cycles.

8. 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, wherein the scheduling of transmission of respective data packets to the point-to-point network occurs at least at one of the defined time frame positions within each of the super cycles.

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

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

11. The system as in claim 10, wherein the super cycle duration is equal to at least one of a predefined number of seconds and a predefined fraction of a second, as measured using the UTC (Coordinated Universal Time) standard.

12. The system as in claim 1, wherein there are a plurality of end-stations;

wherein the second scheduling controller schedules a plurality of time intervals for the transfer of plurality of data packets from the end-stations to the shared medium.

13. The system as in claim 12, wherein the transfer of plurality of data packets from the end-stations to the shared medium is responsive to the first scheduling controller.

14. The system as in claim 1, wherein the second scheduling controller is part of the end-station.

15. The system as in claim 14, the first scheduling controller further comprising TICK sending means for sending TICK signals, the second scheduling controller further comprising TICK receiving means for receiving TICK signals;

wherein the transfer of data packets from the end station to the shared medium is regulated by the second scheduling controller responsive to the TICK signals.

16. The system as in claim 14, wherein the first and the second scheduling controllers receive the same common time reference signals.

17. The system as in claim 1, wherein the shared medium is at least one of an IEEE P1394 room network, an Ethernet local area network, a Data-Over-Cable Service Interface Specification (DOCSIS) cable modem network, an IEEE 802.14 cable modem network, an IEEE 802.11 wireless network, a Fiber Channel Arbitrated Loop (FC-AL) storage area network, and an Serial Storage Association (SSA) storage area network.

18. The system as in claim 1, wherein the end-station is at least one of a video camera, a video cassette recorder (VCR), a video disk, a set-top box, a set-top box with Ethernet connection to video camera and VCR, a desktop computer, a mobile unit, a disk drive, a tape drive, a semiconductor disk, an electronic disk, a telephone set, a video display, a video game input and output, and a computer work-station.

19. The system as in claim 1, wherein the second scheduling controller is part of at least one of the following:

a cable-modem head-end, a wireless network base station, an IEEE 1394 shared medium, and a host adapter for storage area network.

20. A shared media access time manager (SMATM) System comprising:

a source of a common time reference;

a plurality of endstations;

a shared media network for providing a second time reference divided into time intervals, responsive to the common time reference, which is coupled to at least one end-station of the plurality of end stations;

at least one synchronous virtual pipe comprised of a plurality of linked switches, each switch having at least one input port for synchronous receiving incoming data packets and at least one output port for synchronously transmitting data packets, coupled to the common time reference, and together defining a path, and at least one synchronous virtual pipe having an associated schedule of pre-allocated time frames that are derived from the common time reference; and

an access time manager responsive to the schedule of pre-allocated time frames for allocating specific ones of the time intervals for transfer of an associated one of the data packets between a respective one of the end-stations and the synchronous virtual pipe over the shared media network.

21. The system as in claim 20, wherein the common time reference is equal to the second time reference.

22. The system as in claim 20, wherein the SMATM provides separate scheduling for each of the time intervals.

23. The system as in claim 20, wherein the SMATM schedules the transfer of the respective data packet from the respective end-station to provide for coupling of the respective data packet to the output port immediately prior to the respective pre-allocated time frame associated with the respective data packet.

24. The system as in claim 20, wherein the shared media network is a ring network with concurrent access and spatial bandwidth reuse.

25. The system as in claim 24, wherein a plurality of data packets for a selected plurality of the end-stations are scheduled by the SMATM to transmit data packets during the same time interval, and wherein said plurality of data packets are forwarded in at least one time frame, and to at least one synchronous virtual pipe.

26. The system as in claim 20, wherein the SMATM is at least one of a desk-top computer, a computer work-station, an host adapter, a cable-modem head-end, and a wireless base-station.

27. The system as in claim 20, wherein the SMATM further comprises of means for processing a plurality of format types of data packets.

28. The system as in claim 27, wherein the data packets within shared media network are of a first format type;

wherein the first format type is at least one of an ATM, an IP, a fiber channel for FC-AL, an SSA, a DOCSIS, and an IEEE 802.11.

wherein the data packets within the synchronous virtual pipe are of a second format type,

wherein the second format type is at least one of an ATM, an IP, a fiber channel for FC-AL, an SSA, a DOCSIS, and an IEEE 802.11.

29. The system as in claim 28, wherein the SMATM converts the data packets of the first format type to the data packets of second format type.

30. The system as in claim 28, wherein the SMATM converts the data packets of the second format type to the data packets of the first format type.

31. The system as in claim 28, wherein the SMATM converts a first number of data packets of the first format type to a second number of data packets of the second format type.

32. The system as in claim 31, wherein each respective one of the first number of data packets is scheduled in a corresponding respective one of the time intervals;

wherein each of the time intervals can selectively have associated with it scheduled data packets;

wherein each respective one of the second number of data packets is scheduled in a corresponding respective one of the time frames; and

wherein each time frame can selectively have associated with it scheduled data packets.

33. The system as in claim 20, wherein the SMATM further comprises a first scheduling controller and transmit buffer;

wherein the data packet further comprises a pipe-ID (PID) and a time stamp;

wherein the SMATM provides for attaching a time of arrival (TOA) to incoming data packets from the shared media network;

wherein the first scheduling controller and transmit buffer provides for assigning selected predefined time frames for transfer out of the output port for synchronously transmitting data packets over the synchronous virtual pipe responsive to the time of arrival, PID, time stamp and the common time reference.

34. The system as in claim 20, wherein the SMATM further comprises a second scheduling controller and transmit buffer;

wherein the data packet further comprises a pipe-ID (PID) and a time stamp;

wherein the SMATM provides for attaching a time of arrival (TOA) to incoming data packets from the synchronous virtual pipe; and

wherein the second scheduling controller and transmit buffer provides for assigning selected predefined time intervals for transfer the data packets over the shared media network responsive to the time of arrival, PID, time stamp, and responsive to the second time reference.

35. The system as in claim 20, wherein the common time reference and the second time reference are the same.

36. A communications management system comprising:

a common time reference, wherein the common time reference is partitioned into a plurality of contiguous time frames;

a synchronous virtual pipe comprised of a plurality of linked switches, each switch having at least one input port and at least one output port, coupled to the common time reference, and together defining a path;

a source for transmitting periodic data bursts;

a destination for receiving periodic data bursts;

a first shared media network, coupled to the source for transmitting periodic data bursts and to the synchronous virtual pipe; and

a second shared media network, coupled to the synchronous virtual pipe and to the destination for receiving periodic data bursts.

37. The system as in claim 36, wherein the first shared media network is coupled to the input of the synchronous virtual pipe;

and

wherein the second shared media network is coupled to the output of the synchronous virtual pipe.

38. The system as in claim 36,

wherein there are a plurality of synchronous virtual pipes;

wherein the first shared media network is coupled to the input of the a first synchronous virtual pipe and is coupled to the output of the a second synchronous virtual pipe; and

wherein the second shared media network is coupled to the input of the a third synchronous virtual pipe and is coupled to the output of the a fourth synchronous virtual pipe.

39. The system as in claim 36, wherein the periodic data bursts represent captured video frames by a video camera.

40. The system as in claim 36, wherein the destination for receiving periodic data bursts provides for a display of video frames responsive to the respective periodic data bursts.

41. The system as in claim 40, wherein there are a plurality of destinations for receiving the periodic data bursts, each providing for a respective display of video frames to a respective display.

42. The system as in claim 40, wherein the display is at least one of a television (TV) set, a high definition TV (HDTV) set, a computer monitor, a flat panel display, a movie theater, a video display in a conference room, and a hand-held wireless video display.

43. The system as in claim 36, further comprising a scheduling controller for defining one or more predefined time frames, and for scheduling the a synchronous transfer of the periodic data bursts commencing during respective scheduled ones of the time frames occurring closest in time to an occurrence of the respective periodic data bursts from the source.

44. The system as in claim 43, wherein the synchronous transfer is from the source to the destination.

45. The system as in claim 43, wherein the source is coupled to at least one of a first IEEE 1394 shared media network, a first cable-modem system, and a second IEEE 1394 shared media network that is coupled to a second cable-modem system;

wherein the display is coupled to the destination via at least one of a third IEEE 1394 shared media network, a third cable-modem system, and a fourth IEEE 1394 shared media network that is coupled to a fourth cable-modem system.

46. The system as in claim 44, wherein the synchronous transfer is from a plurality of sources to a plurality of destinations.

47. The system as in claim 36, wherein the periodic data bursts have complex periodicity.

48. The system as in claim 47, 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, and wherein l is at least 1;

wherein the source of periodic data bursts are scheduled for transmission in reoccurring predefined time frames in selected ones of said time cycles and super cycles.

49. The system as in claim 48, wherein the periodic data bursts are scheduled for transmission in reoccurring predefined time frame positions within selected ones of the time cycles within each of the super cycles.

50. A communications scheduling system comprising:

a common time reference, wherein the common time reference is partitioned into contiguous time frames;

a source for transmitting periodic data bursts;

a destination for receiving periodic data bursts;

a first shared media network, coupled to the source for transmitting periodic data bursts; and

a second shared media network, coupled to the destination for receiving periodic data bursts;

a scheduling controller for providing scheduling of the selective coupling of the first and second shared media networks to provide for transferring the respective periodic data bursts from the source to the destination during a respective scheduled time frame position;

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, and wherein l is at least 1;

wherein the periodic data bursts are scheduled for transmission in reoccurring predefined time frame positions within selected ones of the time cycles within each of the super cycles.

51. The system as in claim 50, wherein the destination is coupled to a video display via at least one of an IEEE 1394 shared media network, a cable-modem shared media network, an IEEE 802.3 (Ethernet) shared media network, a second IEEE 802.3. (Ethernet) shared media network that is connected to a second cable-modem shared media network, and a second IEEE 1394 shared media network that is connected to a third cable-modem shared media network.

52. The system as in claim 50, wherein the source for transmitting periodic data bursts is a video source, wherein the video source provides an output of Motion Picture Expert'"'"'s Group (MPEG) video I frames, selectively followed by an integer number of MPEG video P frames and MPEG video B frames;

wherein following a single MPEG video I frame there is between zero and a plurality of MPEG video P frames, and following that there is between zero and a plurality of zero or more MPEG video B frames.

53. The system as in claim 52, wherein the transmission of the MPEG video I frames is scheduled for reoccurring in a first predefined selected ones of the time frames within a first predefined selected ones of the time cycles within each of the super cycles;

wherein the transmission of the MPEG video B frames is scheduled for reoccurring in a second predefined selected ones of the time frames within a second predefined selected ones of the time cycles within each of the super cycles; and

wherein the transmission of the MPEG video P frames is scheduled for reoccurring in a third predefined selected ones of the time frames within a third predefined selected ones of the time cycles within each of the super cycles.

54. The system as in claim 50, wherein the common time reference signal is provided in accordance with the UTC (Coordinated Universal Time) standard.

55. The system as in claim 50, wherein the super cycle duration is equal to at least one of a predefined number of seconds and a predefined fraction of a second, as measured using the UTC (Coordinated Universal Time) standard.

56. The system as in claim 53, wherein the first, second, and third predefined selected ones of the time frames are the same.

57. The system as in claim 53, wherein the first, second, and third predefined selected ones of the time frames are consecutive.

58. A method for scheduling transfer of data packets between one of a point to point network and a shared medium, and alternatively between an end station and the shared medium, the method comprising:

providing for signaling of a common time reference;

scheduling a first time frame for the transfer of the data packets from the shared medium to the point to point network, responsive to UTC (Coordinated Universal Time) timing signals; and

scheduling a time interval for the transfer of the data packets from the end station to the shared medium, responsive to the scheduling of the first time fame,

wherein the time interval occurs immediately before the first time frame.

59. The method as in claim 58, further comprising:

alternating in sequential time order between the scheduling of the first time frame and the scheduling of a second time frame, to effectuate the transfer of a plurality of the data packets over a plurality of the first time frames and a plurality of the time intervals.

60. The method as in claim 58, further comprising:

providing for access time management, controlling the scheduling of the first time frame and the scheduling of the second time fame.

61. The method as in claim 58, further comprising:

structuring the time frames into a time cycle comprised of a fixed number of contiguous time frames which are structured into a stream of a plurality of contiguous time cycles.

62. The method as in claim 61, further comprising:

scheduling transmission of respective data packets to occur at a defined one of the time frame positions within each of the time cycles.

63. The method as in claim 62, further comprising:

scheduling transmission of respective data packets to the point-to-point network to occur at multiple defined ones of the time frame positions within each of the cycles.

64. The method as in claim 61, further comprising:

configuring a fixed number of a plurality of contiguous ones of the time cycles into a super cycle,

defining a plurality of super cycles as periodic, and

scheduling transmission of respective ones of the data packets to the point-to-point network to each occur at a defined one of time frame positions periodically during at least one associated respective one of the time cycles during each of the super cycles.

65. The system as in claim 61, further comprising:

configuring a fixed number of a plurality of contiguous ones of the time cycles into a super cycle,

defining a plurality of super cycles as periodic, and

scheduling transmission of respective ones of the data packets to the point-to-point network to each occur at least at one of the defined time frame positions within each of the super cycles.

66. The method as in claim 58, further comprising:

coupling a common time reference signal, responsive to the providing for signaling of a common time reference, to a GPS (Global Positioning System).

67. The method as in claim 58, further comprising:

providing a common time reference signal, responsive to the providing for signaling of a common time reference, in accordance with the UTC (Coordinated Universal Time) standard.

68. The method as in claim 58, providing the scheduling of the time interval within the end-station.

69. The method as in claim 68, further comprising:

sending TICK signals as a part of the scheduling of the first time frame;

receiving TICK signals, as a part of the scheduling of the time interval, and

transferring data packets from the end station to the shared medium responsive to the TICK signals.

70. The method as in claim 58, wherein the shared medium is further comprised of at least one of an IEEE P1394 room network, an Ethernet local area network, a Data-Over-Cable Service Interface Specification (DOCSIS) cable modem network, an IEEE 802.14 cable modem network, an IEEE 802.11 wireless network, a Fiber Channel Arbitrated Loop (FC-AL) storage area network, and an Serial Storage Association (SSA) storage area network.

71. The method as in claim 58, wherein the end-station is further comprised of at least one of a video camera, a video cassette recorder (VCR), a video disk, a set-top box, a set-top box with Ethernet connection to video camera and VCR, a desktop computer, a mobile unit, a disk drive, a tape drive, a semiconductor disk, an electronic disk, a telephone set, a video display, a video game input and output, and a computer work-station.

72. The method as in claim 58, wherein the scheduling of the time interval is comprised of:

utilizing part of at least one of a cable-modem headed, a wireless network base station, an IEEE 1394 shared medium, and a host adapter for storage area network.