Method and apparatus for detecting impending overflow and/or underrun of elasticity buffer

• US 4,945,548 A
• Filed: 10/14/1988
• Issued: 07/31/1990
• Est. Priority Date: 04/28/1988
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Iannarone, John R., Thompson, Bruce W.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Huseman, Marianne
• Application Number:
  US07/257,907
• Time in Patent Office: 655 Days
• Field of Search: 375/3, 375/4, 375/118, 358/149, 358/19, 360/51, 360/54, 370/102, 370/105, 370/105.3, 370/108, 370/103, 369/60
• US Class Current: 375/214
• CPC Class Codes: G06F 2205/102 Avoiding metastability, i.e. preventing hazards, e.g. by using Gray code counters
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags
• CPC Class Codes: H04L 2007/045 Fill bit or bits, idle words

Abstract

A parallel asynchronous elasticity buffer. Selection of the address of a storage element for writing or reading of data is provided by asynchronous input and output pointers implemented using circular gray code counters. The buffer is initialized once during transmission of each frame of data so that the pointers do not select the same storage element for writing and reading at the same time. Write overflow or read underrun of a storage element is detected before any data corruption can occur by comparing the input and output pointers. An error condition is detected if the input and output pointers overlap for a threshold period, which can be shorter than the period required for writing or reading of a multibit data unit to or from the buffer. The overlap time period is determined by comparing the pointers at one or more sampling times corresponding to selected phases of a clock signal.

Claims

1. A parallel asynchronous elasticity buffer in a repeater node for transferring data in a data communication system, the data communication system including a plurality of nodes coupled in a network for transferring frames of data from a source node to a destination node through the repeater node, wherein the repeater node receives a plurality of bits of data in a frame from an upstream node and transmits the plurality of bits of data in the frame to a downstream node, and wherein each node in the network transmits data in synchronism with an independent clock, the elasticity buffer comprising:

receiving means for providing in parallel format, in response to a transmit multibit clock signal that is in synchronism with an independent clock of the upstream node, a multibit data unit received from the upstream node;

storage means including a fixed number of multibit storage elements, coupled to the receiving means, for storing the multibit data unit in parallel format in one of the storage elements, wherein each storage element has a unique address;

transmitting means, coupled to the storage means, for outputting in parallel format, in response to a local multibit clock signal that is in synchronism with the independent clock of the repeater node, one of the multibit data units stored in the storage means;

write pointer means, coupled to the storage means, for selecting as a write address the address of a storage element to store the next multibit data unit provided by the receiving means;

read pointer means, coupled to the storage means, for selecting as a read address the address of a storage element to provide the next multibit data unit output by the transmitting means, wherein each multibit data unit is output in first-in, first-out order;

initialization means for initializing the elasticity buffer to prevent simultaneous selection of the same address as a read address and a write address, wherein in response to initialization, a write address is selected as a read address after a predetermined delay; and

detection means for detecting whether an error condition corresponding to a write overflow or read underrun of a storage element is impending by determining whether the same address is selected as the write address and as the read address during an overlap time period having a duration equal to a threshold time period.

2. An elasticity buffer in accordance with claim 1, wherein the threshold time period is unequal in duration to an integer multiple of the period of the local multibit clock signal.

3. An elasticity buffer in accordance with claim 2, wherein the write pointer means comprises a counter.

4. An elasticity buffer in accordance with claim 3, wherein the read pointer means comprises a counter.

5. An elasticity buffer in accordance with claim 4, wherein the write and read pointer means comprise gray code counters.

6. An elasticity buffer in accordance with claim 2, wherein the read pointer means comprises a counter.

7. An elasticity buffer in accordance with claim 2, wherein:

the elasticity buffer further comprises means for providing a sampling clock signal; and

the detection means comprises comparator means for comparing, in response to the sampling clock signal, the write address and the read address.

8. An elasticity buffer in accordance with claim 7, wherein the sampling clock signal is in synchronism with the local multibit clock signal.

9. An elasticity buffer in accordance with claim 8, wherein the sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal.

10. An elasticity buffer in accordance with claim 8, wherein the sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

11. An elasticity buffer in accordance with claim 7, wherein the sampling clock signal providing means provides a first sampling clock signal to detect whether a write overflow is impending and provides a second sampling clock signal out of phase with the first sampling clock signal to detect whether a read underrun is impending.

12. An elasticity buffer in accordance with claim 11, wherein the second sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal, and the first sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

13. An elasticity buffer in accordance with claim 2, wherein:

the elasticity buffer further comprises memory means for storing at least one initialization address; and

at least one of the write pointer means and the read pointer means, in response to a control signal from the initialization means, selects an initialization address stored in the memory means.

14. An elasticity buffer in accordance with claim 13, wherein:

the elasticity buffer further comprises means for detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

the memory means, in response to detection of the first multibit data unit of the frame, stores from the write pointer means as the initialization address for the read pointer means the write address corresponding to the storage element selected to store the first multibit data unit.

15. An elasticity buffer in accordance with claim 1, wherein the threshold time period is shorter in duration than the period of the local multibit clock signal.

16. An elasticity buffer in accordance with claim 15, wherein the write pointer means comprises a counter.

17. An elasticity buffer in accordance with claim 16, wherein the read pointer means comprises a counter.

18. An elasticity buffer in accordance with claim 17, wherein the write and read pointer means comprise gray code counters.

19. An elasticity buffer in accordance with claim 15, wherein:

the elasticity buffer further comprises memory means for storing at least one initialization address; and

at least one of the write pointer means and the read pointer means, in response to a control signal from the initialization means, selects an initialization address stored in the memory means.

20. An elasticity buffer in accordance with claim 19, wherein:

the elasticity buffer further comprises means for detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

the memory means, in response to detection of the first multibit data unit of the frame, stores from the write pointer means as the initialization address for the read pointer means the write address corresponding to the storage element selected to store the first multibit data unit.

21. An elasticity buffer in accordance with claim 15, wherein the network comprises a token ring.

22. An elasticity buffer in accordance with claim 21, wherein the network comprises an FDDI network.

23. An elasticity buffer in accordance with claim 22, wherein the multibit data unit comprises a byte.

24. An elasticity buffer in accordance with claim 22, wherein the multibit data unit comprises a symbol.

25. An elasticity buffer in accordance with claim 15, wherein the read pointer means comprises a counter.

26. An elasticity buffer in accordance with claim 15, wherein:

the elasticity buffer further comprises means for providing a sampling clock signal; and

the detection means comprises comparator means for comparing, in response to the sampling clock signal, the write address and the read address.

27. An elasticity buffer in accordacne with claim 26, wherein the sampling clock signal is in synchronism with the local multibit clock signal.

28. An elasticity buffer in accordance with claim 27, wherein the sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal.

29. An elasticity buffer in accordance with claim 27, wherein the sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

30. An elasticity buffer in accordance with claim 26, wherein the sampling clock signal providing means provides a first sampling clock signal to detect whether a write overflow is impending and provides a second sampling clock signal out of phase with the first sampling clock signal to detect whether a read underrun is impending.

31. An elasticity buffer in accordance with claim 30, wherein the second sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal, and the first sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

32. An elasticity buffer in accordance with claim 30, wherein:

the elasticity buffer further comprises memory means for storing at least one initialization address; and

at least one of the write pointer means and the read pointer means, in response to a control signal from the initialization means, selects an initialization address stored in the memory means.

33. An elasticity buffer in accordance with claim 32, wherein:

the elasticity buffer further comprises means for detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream mode; and

the memory means, in response to detection of the first multibit data unit of the frame, stores from the write pointer means as the initialization address for the read pointer means the write address corresponding to the storage element selected to store the first multibit data unit.

34. An elasticity buffer in accordance with claim 30, wherein the network comprises a token ring.

35. An elasticity buffer in accordance with claim 34, wherein the network comprises an FDDI network.

36. An elasticity buffer in accordance with claim 35, wherein the multibit data unit comprises a byte.

37. An elasticity buffer in accordance with claim 35, wherein the multibit data unit comprises a symbol.

38. An elasticity buffer in accordance with claim 26, wherein:

the elasticity buffer further comprises memory means for storing at least one initialization address; and

at least one of the write pointer means and the read pointer means, in response to a control signal from the initialization means, selects an initialization address stored in the memory means.

39. An elasticity buffer in accordance with claim 38, wherein:

the elasticity buffer further comprises means for detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream mode; and

the memory means, in response to detection of the first multibit data unit of the frame, stores from the write pointer means as the initialization address for the read pointer means the write address corresponding to the storage element selected to store the first multibit data unit.

40. An elasticity buffer in accordance with claim 1, wherein the write pointer means comprises a counter.

41. An elasticity buffer in accordance with claim 40, wherein the read pointer means comprises a counter.

42. An elasticity buffer in accordance with claim 41, wherein the write and read pointer means comprise gray code counters.

43. An elasticity buffer in accordance with claim 42, wherein:

the elasticity buffer further comprises means for providing a sampling clock signal; and

the detection means comprises comparator means for comparing, in response to the sampling clock signal, the write address and the read address.

44. An elasticity buffer in accordance with claim 43, wherein the sampling clock signal is in synchronism with the local multibit clock signal.

45. An elasticity buffer in accordance with claim 43, wherein the sampling clock signal providing means provides a first sampling clock signal to detect whether a write overflow is impending and provides a second sampling clock signal out of phase with the first sampling clock signal to detect whether a read underrun is impending.

46. An elasticity buffer in accordance with claim 41, wherein:

the elasticity buffer further comprises means for providing a sampling clock signal; and

the detection means comprises comparator means for comparing, in response to the sampling clock signal, the write address and the read address.

47. An elasticity buffer in accordance with claim 46, wherein the sampling clock signal is in synchronism with the local multibit clock signal.

48. An elasticity buffer in accordance with claim 46, wherein the sampling clock signal providing means provides a first sampling clock signal to detect whether a write overflow is impending and provides a second sampling clock signal out of phase with the first sampling clock signal to detect whether a read underrun is impending.

49. An elasticity buffer in accordance with claim 1, wherein the read pointer means comprises a counter.

50. An elasticity buffer in accordance with claim 1, wherein:

the elasticity buffer further comprises means for providing a sampling clock signal; and

the detection means comprises comparator means for comparing, in response to the sampling clock signal, the write address and the read address.

51. An elasticity buffer in accordance with claim 50, wherein the sampling clock signal is in synchronism with the local multibit clock signal.

52. An elasticity buffer in accordance with claim 51, wherein the sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal.

53. An elasticity buffer in accordance with claim 51, wherein the sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

54. An elasticity buffer in accordance with claim 50, wherein the sampling clock signal providing means provides a first sampling clock signal to detect whether a write overflow is impending and provides a second sampling clock signal out of phase with the first sampling clock signal to detect whether a read underrun is impending.

55. An elasticity buffer in accordance with claim 54, wherein the second sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal, and the first sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

56. An elasticity buffer in accordance with claim 54, wherein:

the elasticity buffer further comprises memory means for storing at least one initialization address; and

at least one of the write pointer means and the read pointer means, in response to a control signal from the initialization means, selects an initialization address stored in the memory means.

57. An elasticity buffer in accordance with claim 56, wherein:

the elasticity buffer further comprises means for detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

the memory means, in response to detection of the first multibit data unit of the frame, stores from the write pointer means as the initialization address for the read pointer means the write address corresponding to the storage element selected to store the first multibit data unit.

58. An elasticity buffer in accordance with claim 50, wherein:

the elasticity buffer further comprises memory means for storing at least one initialization address; and

at least one of the write pointer means and the read pointer means, in response to a control signal from the initialization means, selects an initialization address stored in the memory means.

59. An elasticity buffer in accordance with claim 58, wherein:

the elasticity buffer further comprises means for detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

the memory means, in response to detection of the first multibit data unit of the frame, stores from the write pointer means as the initialization address for the read pointer means the write address corresponding to the storage element selected to store the first multibit data unit.

60. An elasticity buffer in accordance with claim 1, wherein:

the elasticity buffer further comprises memory means for storing at least one initialization address; and

at least one of the write pointer means and the read pointer means, in response to a control signal from the initialization means, selects an initialization address stored in the memory means.

61. An elasticity buffer in accordance with claim 60, wherein:

the elasticity buffer further comprises means for detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

the memory means, in response to detection of the first multibit data unit of the frame, stores from the write pointer means as the initialization address for the read pointer means the write address corresponding to the storage element selected to store the first multibit data unit.

62. A method for transferring data in a data communication system via a repeater node having a parallel asynchronous elasticity buffer, the elasticity buffer including storage means having a fixed number of multibit storage elements, each storage element having a unique address, and the data communication system including a plurality of nodes coupled in a network for transferring frames of data from a source node to a destination node through the repeater node, wherein the repeater node receives a plurality of bits of data in a frame from an upstream node and transmits the plurality of bits of data in the frame to a downstream node, and wherein each node in the network transmits data in synchronism with an independent clock, the method comprising the following steps performed by the repeater node:

providing in parallel format to the storage means, in response to a transmit multibit clock signal that is in synchronism with an independent clock of the upstream node, a multibit data unit received from the upstream node;

storing the multibit data unit in parallel format in one of the storage elements;

outputting in parallel format from the storage means, in response to a local multibit clock signal that is in synchronism with the independent clock of the repeater node, one of the multibit data units stored in the storage means;

selecting as a write address the address of a storage element to store the next multibit data unit provided to the storage means;

selecting as a read address the address of a storage element to provide the next multibit data unit output by the storage means, wherein each multibit data unit is output in first-in, first-out order;

initializing the elasticity buffer to prevent simultaneous selection of the same address as a read address and a write address, wherein in response to initialization, a write address is selected as a read address after a predetermined delay; and

detecting whether an error condition corresponding to a write overflow or read underrun of a storage element is impending by determining whether the same address is selected as the write address and as the read address during an overlap time period having a duration equal to a threshold time period.

63. A method in accordance with claim 62, wherein the threshold time period is unequal in duration to an integer multiple of the period of the local multibit clock signal.

64. A method in accordance with claim 62, wherein the threshold time period is shorter in duration than the period of the local multibit clock signal.

65. A method in accordance with claim 64, wherein:

the method further comprises providing a sampling clock signal; and

the detecting step comprises comparing, in response to the sampling clock signal, the write address and the read address.

66. A method in accordance with claim 65, wherein the sampling clock signal is in synchronism with the local multibit clock signal.

67. A method in accordance with claim 66, wherein the sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal.

68. A method in accordance with claim 66, wherein the sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

69. A method in accordance with claim 65, wherein the sampling clock signal providing step comprises providing a first sampling clock signal to detect whether a write overflow is impending and providing a second sampling clock signal out of phase with the first sampling clock signal to detect whether a read underrun is impending.

70. A method in accordance with claim 69, wherein the second sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal, and the first sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

71. A method in accordance with claim 69, wherein the method further comprises:

storing at least one initialization address; and

selecting, as at least one of the write address and the read address, a stored initialization address in response to a control signal.

72. A method in accordance with claim 71, wherein the method further comprises:

detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

storing as the initialization address to be selected as the read address, in response to detection of the first multibit data unit of the frame, the write address corresponding to the storage element selected to store the first multibit data unit.

73. A method in accordance with claim 65, wherein the method further comprises:

storing at least one initialization address; and

selecting, as at least one of the write address and the read address, a stored initialization address in response to a control signal.

74. A method in accordance with claim 73, wherein the method further comprises:

detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

storing as the initialization address to be selected as the read address, in response to detection of the first multibit data unit of the frame, the write address corresponding to the storage element selected to store the first multibit data unit.

75. A method in accordance with claim 64, wherein the method further comprises:

storing at least one initialization address; and

selecting, as at least one of the write address and the read address, a stored initialization address in response to a control signal.

76. A method in accordance with claim 75, wherein the method further comprises:

detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

storing as the initialization address to be selected as the read address, in response to detection of the first multibit data unit of the frame, the write address corresponding to the storage element selected to store the first multibit data unit.

77. A method in accordance with claim 62, wherein the method further comprises:

storing at least one initialization address; and

selecting, as at least one of the write address and the read address, a stored initialization address in response to a control signal.

78. A method in accordance with claim 77, wherein the method further comprises:

detecting receipt by the repeater node of a first multibit data unit of a frame from the upstream node; and

storing as the initialization address to be selected as the read address, in response to detection of the first multibit data unit of the frame, the write address corresponding to the storage element selected to store the first multibit data unit.

79. A method in accordance with claim 62, wherein:

the method further comprises providing a sampling clock signal; and

the detecting step comprises comparing, in response to the sampling clock signal, the write address and the read address.

80. A method in accordance with claim 79, wherein the sampling clock signal is in synchronism with the local multibit clock signal.

81. A method in accordance with claim 80, wherein the sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal.

82. A method in accordance with claim 80, wherein the sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

83. A method in accordance with claim 79, wherein the sampling clock signal providing step comprises providing a first sampling clock signal to detect whether a write overflow is impending and providing a second sampling clock signal out of phase with the first sampling clock signal to detect whether a read underrun is impending.

84. A method in accordance with claim 83, wherein the second sampling clock signal is between 135 degrees and 225 degrees out of phase with the local multibit clock signal, and the first sampling clock signal is between 225 degrees and 315 degrees out of phase with the local multibit clock signal.

85. A method in accordance with claim 62, wherein the network comprises a token ring.

86. A method in accordance with claim 85, wherein the network comprises an FDDI network.

87. A method in accordance with claim 86, wherein the multibit data unit comprises a byte.

88. A method in accordance with claim 86, wherein the multibit data unit comprises a symbol.