US6192028B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus providing programmable thresholds for half-duplex flow control in a network switch
Assignee: GlobalFoundries Inc
•
Filing: 1997-12-18
•
Granted: 2001-02-20
•
Expires: 2017-12-18
Abstract
Abstract A network switch having a shared memory architecture for storing data frames has a set of programmable thresholds that specify when flow control should be initiated on a selected network port. The network switch includes a queue for storing free frame pointers, each specifying available memory locations in an external memory for storing data frames received from a network station. The network switch takes a frame pointer from a free buffer queue for each received data frame, and stores the received data frame in the location in external memory specified by the frame pointer while a decision making engine within the switch determines the appropriate destination ports. Flow control is initiated on a half-duplex network port by transmitting a phantom packet to a transmitting network station if the output buffer of a destination port exceeds a programmed high threshold, or if the output buffer of the destination port exceeds a low programmed threshold and the queue of free frame pointers falls below a low programmable threshold. The switch thus provides flexibility in providing selective collisions with transmitting stations to minimize the possibility of network congestion without wasting network bandwidth with unnecessary collisions.
Inventors
- 👤 Philip Simmons
- 👤 Bahadir Erimli
- 👤 Jinqlih Sang
- 👤 Eric Tsin-Ho Leung
- 👤 Ian Crayford
- 👤 Jayant Kadambi
- 👤 Denise Kerstein
- 👤 Thomas Jefferson Runaldue
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 17:32
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L49/3009; G; G06; G06F; G06F13/00; G06F13/14; G06F13/16; G06F13/1605; G06F13/20; G06F13/24; G11; G11C; G11C11/00; G11C11/21; G11C11/34; G11C11/40; G11C11/41; G11C11/412; H04L12/00; H04L12/28; H04L12/46; H04L12/4641; H04L41/00; H04L41/02; H04L41/0213; H04L47/00; H04L47/50; H04L47/62; H04L47/622; H04L47/6225; H04L49/10; H04L49/103; H04L49/20; H04L49/201; H04L49/25; H04L49/253; H04L49/255; H04L49/3027; H04L49/35; H04L49/351; H04L49/354; H04L49/50; H04L49/55; H04L49/552; H04L49/555; H04L49/90; H04L49/901; H04L49/9047; H04L49/9063; H04L49/9068; H04L49/9073; H04L49/9078; H04L49/9084; H04Q; H04Q3/00; H04Q3/42; H04Q3/54; H04Q3/545; H04Q3/54575; H04Q3/54591; H04L12/02; H04L12/16; H04L12/18; H04L12/1863; H04L12/4645; H04L12/467; H04L49/3054; H04L49/40; H04Q2213/00; H04Q2213/1316; H04Q2213/13162
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
257 words
A method in a network having network stations, the method comprising: setting a first queue threshold level for a first queue configured for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames; receiving a portion of a first data frame from a first of the network stations; selectively transmitting a signal to the first network station during reception of the first data frame based on the first queue threshold level and a number of the free frame pointers stored in the first queue, the signal causing a collision with the first network stations during transmission of said first data frame; setting a second queue threshold level for a port queue configured to store an assigned frame pointer, the assigned frame pointer specifying a storage memory location of a stored data frame to be transmitted to a second of the network stations; identifying the port queue as a destination port for the first data frame based on the portion of the first data frame; wherein the selectivity transmitting step comprises selectively generating the signal based on the number of free frame pointers relative to the first queue threshold level and a number of the assigned frame pointers relative to the second queue threshold level; and setting for the port queue a third queue threshold level having a value greater than the second queue threshold, the selectivity transmitting step further comprising selectivity generating the signal based on the number of assigned frame pointers relative to the third queue threshold level.
Claim 2
Independent Claim
257 words
A method in a network having network stations, the method comprising: setting a first queue threshold level for a first queue configured for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames; receiving a portion of a first data frame from a first of the network stations; selectively transmitting a signal to the first network station during reception of the first data frame based on the first queue threshold level and a number of the free frame pointers stored in the first queue, the signal causing a collision with the first network stations during transmission of said first data frame; setting a second queue threshold level for a port queue configured to store an assigned frame pointer, the assigned frame pointer specifying a storage memory location of a stored data frame to be transmitted to a second of the network stations; identifying the port queue as a destination port for the first data frame based on the portion of the first data frame; wherein the selectivity transmitting step comprises selectively generating the signal based on the number of free frame pointers relative to the first queue threshold level and a number of the assigned frame pointers relative to the second queue threshold level; and setting for the port queue a third queue threshold level having a value greater than the second queue threshold, the selectivity transmitting step further comprising selectivity generating the signal based on the number of assigned frame pointers relative to the third queue threshold level.
Claim 3
Dependent Claim
29 words
The method of claim 1 , wherein the selectively transmitting step comprises transmitting the signal when the number of free frame pointers falls below the first queue threshold level.
Claim 4
Dependent Claim
44 words
The method of claim 1 , wherein the selectively transmitting step further comprises selectively generating the signal if the number of free frame pointers falls below the first queue threshold level and the number of assigned frame pointers exceeds the second queue threshold level.
Claim 5
Dependent Claim
39 words
The method of claim 3 , wherein the selectively transmitting step further comprises generating the signal to cause the collision if the number of assigned frame pointers exceeds the second queue threshold level and the third queue threshold level.
Claim 6
Dependent Claim
68 words
The method of claim 3 , wherein the selectively transmitting step further comprises: determining if the identifying step identifies the port queue within a prescribed time interval; and generating the signal if the identifying step identifies the port queue within the prescribed time interval, the number of free frame pointers falls below the first queue threshold, and the number of assigned frame pointers exceed the second queue threshold.
Claim 7
Dependent Claim
36 words
The method of claim 5 , wherein the determining step comprises determining if the identifying step identifies the port queue within one half a slot time relative to receiving the portion of the first data frame.
Claim 8
Dependent Claim
42 words
The method of claim 1 , wherein the selectively transmitting step comprises outputting as said signal an unrecognizable data frame to the first network station within one half a slot time of the reception of the portion of the first data frame.
Claim 9
Dependent Claim
31 words
The method of claim 7 , wherein the outputting step comprises generating as said unrecognizable data frame a phantom packet having a length less than a minimum required data frame length.
Claim 10
Dependent Claim
21 words
The method of claim 8 , wherein the phantom packet consists of a sequence of bits alternating between 1 and 0.
Claim 11
Dependent Claim
58 words
The method of claim 1 , further comprising: supplying data frames received from a second of the network stations to a third of the network stations during the collision with the first network station; and supplying carrier signals output by at least one of the second and third network stations to the first network station after the collision.
Claim 12
Dependent Claim
76 words
The method of claim 10 , further comprising: counting a number of collisions encountered by the first network station based on attempted transmissions of the first data frame; and selectively transmitting a second signal to one of the first network station, the second network station, and the third network station based on the counted number of collisions encountered by the first network station, the second signal causing a second collision with the one selected network station.
Claim 13
Independent Claim
226 words
A method in a network switch for selectively outputting a data frame from a transmitting station to a destination station, comprising; setting a first queue threshold level for a first queue configured for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames; setting a second queue threshold for a port queue configured for storing assigned frame pointers identifying stored data frames for the destination station; receiving a portion of a first data frame from the transmitting station; selectively halting transmission of the first data frame based on the first and second thresholds relative to a number of the stored free frame pointers and a number of the stored assigned frame pointers, respectively; wherein the selectively halting step comprises outputting an unrecognizable data frame to the transmitting station within a prescribed interval of receiving the portion of the first data frame; setting for the port queue a third queue threshold having a value greater than the second queue threshold, the selectivity halting step further comprising outputting the unrecognizable data frame based on at least one of; the number of stored assigned frame pointers exceeding the second and third queue threshold, and the number of the stored free frame pointers falling below the first queue threshold level and the number of assigned frame pointers exceeding the second queue threshold.
Claim 14
Independent Claim
226 words
A method in a network switch for selectively outputting a data frame from a transmitting station to a destination station, comprising; setting a first queue threshold level for a first queue configured for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames; setting a second queue threshold for a port queue configured for storing assigned frame pointers identifying stored data frames for the destination station; receiving a portion of a first data frame from the transmitting station; selectively halting transmission of the first data frame based on the first and second thresholds relative to a number of the stored free frame pointers and a number of the stored assigned frame pointers, respectively; wherein the selectively halting step comprises outputting an unrecognizable data frame to the transmitting station within a prescribed interval of receiving the portion of the first data frame; setting for the port queue a third queue threshold having a value greater than the second queue threshold, the selectivity halting step further comprising outputting the unrecognizable data frame based on at least one of; the number of stored assigned frame pointers exceeding the second and third queue threshold, and the number of the stored free frame pointers falling below the first queue threshold level and the number of assigned frame pointers exceeding the second queue threshold.
Claim 15
Dependent Claim
59 words
The method of claim 12 , further comprising identifying the port queue as a destination port for the first data frame based on the portion of the first data frame and within a prescribed interval of receiving the portion of the first data frame, the prescribed interval based on a distance between the network switch and the transmitting station.
Claim 16
Independent Claim
248 words
An apparatus for selectively outputting a data frame from a transmitting station to a destination station in a network, comprising: a first port for receiving at least a portion of the data frame from the transmitting station; a first queue for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames, a first programmable threshold register for storing a first threshold value; a second port for outputting data frames identified for transmission to the destination station; a controller for selectively causing the first output port to induce a collision with the transmitting station during reception of the data frame from the transmitting station, based on a number of the free frame pointers stored in the first queue relative to the first threshold value; the second port comprises a second queue for storing assigned frame pointers specifying respective storage memory locations for the identified data frames; the apparatus further comprises a second programmable threshold register storing a second threshold value; the controller causes the first output port to induce the collision based on a number of the stored assigned frame pointers exceeding the second threshold value; and a third programmable threshold register storing a third threshold value greater than the second threshold value, the controller causing the first output port to induce the collision based on the number of stored assigned frame pointers exceeding the third threshold value and the number of free frame pointers falling below the first threshold value.
Claim 17
Independent Claim
248 words
An apparatus for selectively outputting a data frame from a transmitting station to a destination station in a network, comprising: a first port for receiving at least a portion of the data frame from the transmitting station; a first queue for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames, a first programmable threshold register for storing a first threshold value; a second port for outputting data frames identified for transmission to the destination station; a controller for selectively causing the first output port to induce a collision with the transmitting station during reception of the data frame from the transmitting station, based on a number of the free frame pointers stored in the first queue relative to the first threshold value; the second port comprises a second queue for storing assigned frame pointers specifying respective storage memory locations for the identified data frames; the apparatus further comprises a second programmable threshold register storing a second threshold value; the controller causes the first output port to induce the collision based on a number of the stored assigned frame pointers exceeding the second threshold value; and a third programmable threshold register storing a third threshold value greater than the second threshold value, the controller causing the first output port to induce the collision based on the number of stored assigned frame pointers exceeding the third threshold value and the number of free frame pointers falling below the first threshold value.
Claim 18
Dependent Claim
137 words
The apparatus of claim 14 , further comprising a queue manager controlling the storage of the free frame pointers and the assigned frame pointers in the first queue and second queue, respectively, the first and second queue each comprising: a write-side queue receiving the corresponding frame pointer at an input end and selectively outputting the corresponding frame pointer at an output end to a corresponding assigned portion of an external memory; and a read-side queue selectively receiving the corresponding frame pointer stored in the write-side queue from one of the output end of the write-side queue and the corresponding assigned portion of the external memory, the queue manager selectively storing the corresponding frame pointer in the assigned portion of the external memory based on a second number of the corresponding frame pointers stored in the read-side queue.
Claim 19
Dependent Claim
67 words
The apparatus of claim 15 , wherein the number of free frame pointers stored in the first queue is based on the second number of free frame pointers stored in the corresponding read-side queue, a third number of the free frame pointers stored in the corresponding assigned portion of the external memory, and a fourth number of the free frame pointers stored in the corresponding write-side queue.
Claim 20
Dependent Claim
67 words
The apparatus of claim 15 , wherein the number of assigned frame pointers stored in the first queue is based on the second number of assigned frame pointers stored in the corresponding read-side queue, a third number of the assigned frame pointers stored in the corresponding assigned portion of the external memory, and a fourth number of the assigned frame pointers stored in the corresponding write-side queue.
Claim 21
Dependent Claim
45 words
The apparatus of claim 15 , wherein the queue manager fetches one of the stored received data frames from the external memory and supplies the fetched data frame to the second port based one of the assigned frame pointers output from the corresponding read-side queue.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-02-20 | 2004-08-21 | 2005-02-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-02-20 | 2008-08-21 | 2009-02-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-02-20 | 2012-08-21 | 2013-02-20 | $7700.00 | Window Closed / Lapsed |