US6473424B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Port aggregation load balancing
Assignee: Cisco Technology Inc
•
Filing: 1998-12-02
•
Granted: 2002-10-29
•
Expires: 2018-12-02
Abstract
Abstract Provided are methods, apparatuses and systems for balancing the load of data transmissions through a port aggregation. The methods and apparatuses of the present invention allocate port assignments based on load, that is, the amount of data being forwarded through each port in the group. The load balancing of the present invention is preferably dynamic, that is, packets from a given stream may be forwarded on different ports depending upon each port's current utilization. When a new port is selected to transmit a particular packet stream, it is done so that the packets cannot be forwarded out of order. This is preferably accomplished by ensuring passage of a period of time sufficient to allow all packets of a given stream to be forwarded by a port before a different port is allocated to transmit packets of the same stream. The invention may be used in a variety of different network environments and speeds, including 10Base-T, 100Base-T, and Gigabit Ethernet, and other network environments.
Inventors
- 👤 Gregory L. DeJager
- 👤 James R. Rivers
- 👤 David H. Yen
- 👤 Stewart Findlater
- 👤 Scott A. Emery
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 08:47
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/13; H04L47/11; H04L47/12; H04L47/125; H04L49/00; H04L49/90; H04L49/9084; H04L49/9089; H04L49/9094
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
172 words
A method of distributing traffic over a network port group, comprising: receiving a packet of data to be forwarded; determining a stream ID for said packet by hashing and masking; determining whether a bit for the stream ID is set in a current time mark register; where the bit is not set, setting the bit in the current time mark register, and determining whether a bit for the stream ID is set in an alternate time mark register; where neither the bit in the current nor the alternate time mark registers are set, allocating the packet to a least utilized queue, assigning the packet a queue mark bit, and storing an identifier for the queue in a stream state table location corresponding to the stream ID; where the bit for the stream ID is set in the current time mark register, consulting the stream state table for an identifier of a transmit queue to which the packet is assigned, and assigning the packet a queue mark bit; and forwarding the queued packet.
Claim 2
Independent Claim
172 words
A method of distributing traffic over a network port group, comprising: receiving a packet of data to be forwarded; determining a stream ID for said packet by hashing and masking; determining whether a bit for the stream ID is set in a current time mark register; where the bit is not set, setting the bit in the current time mark register, and determining whether a bit for the stream ID is set in an alternate time mark register; where neither the bit in the current nor the alternate time mark registers are set, allocating the packet to a least utilized queue, assigning the packet a queue mark bit, and storing an identifier for the queue in a stream state table location corresponding to the stream ID; where the bit for the stream ID is set in the current time mark register, consulting the stream state table for an identifier of a transmit queue to which the packet is assigned, and assigning the packet a queue mark bit; and forwarding the queued packet.
Claim 3
Dependent Claim
69 words
The method of claim 1 , further comprising: maintaining proper identification of the least utilized queue whenever a packet is pushed onto a queue, comprising, comparing the identifier of the queue with a least utilized queue identifier, and where the identifiers are the same, determining if any other queues in the port group have no entries, and selecting a queue with no entries to be the least utilized queue.
Claim 4
Dependent Claim
78 words
The method of claim 2 , further comprising: maintaining proper identification of the least utilized queue whenever a packet is popped from a queue, each of said queues having a number of entries, comprising, comparing the number of entries in the queue with the number of entries in the least utilized queue, and where the number of entries on the queue is less than that on the least utilized queue, designating the queue as the least utilized queue.
Claim 5
Dependent Claim
104 words
The method of claim 3 , further comprising a method of updating the time mark registers, comprising: determining whether a load balance time interval has passed; where the load balance time interval has passed, determining for each queue of the port group, whether a queue mark indicate bit assigned to packets exiting the queue is equal to a queue mark bit being assigned to packets entering the queue; where the queue mark indicate bit is the same as the queue mark bit, clearing all alternate time mark register bits, and toggling all queue mark bits; and, switching the current and alternate time mark registers.
Claim 6
Dependent Claim
20 words
The method of claim 4 , wherein said load balance time interval is less than about 1 millisecond in duration.
Claim 7
Dependent Claim
58 words
The method of claim 4 , further comprising a method of handling empty queues, comprising: immediately prior to or after switching the current and alternate time mark registers, checking to see if any queues for ports of the group are empty; for any empty queues, setting the queue's queue mark indicate bit equal to its queue mark bit.
Claim 8
Dependent Claim
151 words
A network switch, comprising: a port group; a system for distributing network traffic among ports of the port group, comprising, a mechanism for determining a stream ID for a packet and assigning the packet having the stream ID to a queue of a port of the port group, and a mechanism for adjusting a queue assignment of a subsequent packet having the stream ID to a queue of a different port of the port group based on load in the queues of the ports of the group, wherein the adjusting mechanism comprises: a least utilized queue register for maintaining proper identification of a least utilized queue, and a pair of queue mark registers for determining whether a queue for a port of the port group is current, and a clock for timing a load balance time interval, wherein said load balance time interval is less than about 1 millisecond in duration.
Claim 9
Dependent Claim
151 words
A network switch, comprising: a port group; a system for distributing network traffic among ports of the port group, comprising, a mechanism for determining a stream ID for a packet and assigning the packet having the stream ID to a queue of a port of the port group, and a mechanism for adjusting a queue assignment of a subsequent packet having the stream ID to a queue of a different port of the port group based on load in the queues of the ports of the group, wherein the adjusting mechanism comprises: a least utilized queue register for maintaining proper identification of a least utilized queue, and a pair of queue mark registers for determining whether a queue for a port of the port group is current, and a clock for timing a load balance time interval, wherein said load balance time interval is less than about 1 millisecond in duration.
Claim 10
Dependent Claim
90 words
The switch of claim 7 , wherein the mechanism for determining a stream ID and assigning the packet having the stream ID to a queue for a port of the port group comprises: a hashing and masking mechanism for determining a stream ID for the packet; a pair of time mark registers for determining whether another packet having the stream ID has been distributed to a queue for a port of the group during a time interval; and a stream state table for storing stream IDs with corresponding queue assignments.
Claim 11
Dependent Claim
138 words
A computer program product comprising a computer-usable medium having computer-readable program code embodied thereon relating to updating current and alternate time mark registers for a dynamic load balancing of traffic on a port group, the computer program product comprising computer-readable program code for effecting the following steps within a computing system: determining whether a load balance time interval has passed; where the load balance time interval has passed, determining for each queue of the port group, whether a queue mark indicate bit assigned to packets exiting the queue is equal to a queue mark bit being assigned to packets entering the queue; where the queue mark indicate bit is the same as the queue mark bit, clearing all alternate time mark register bits, and toggling all queue mark bits; and, switching the current and alternate time mark registers.
Claim 12
Dependent Claim
138 words
A computer program product comprising a computer-usable medium having computer-readable program code embodied thereon relating to updating current and alternate time mark registers for a dynamic load balancing of traffic on a port group, the computer program product comprising computer-readable program code for effecting the following steps within a computing system: determining whether a load balance time interval has passed; where the load balance time interval has passed, determining for each queue of the port group, whether a queue mark indicate bit assigned to packets exiting the queue is equal to a queue mark bit being assigned to packets entering the queue; where the queue mark indicate bit is the same as the queue mark bit, clearing all alternate time mark register bits, and toggling all queue mark bits; and, switching the current and alternate time mark registers.
Claim 13
Dependent Claim
22 words
The computer program product of claim 9 , wherein said load balance time interval is less than about 1 millisecond in duration.
Claim 14
Dependent Claim
52 words
The computer program product of claim 9 , wherein immediately prior to or after switching the current and alternate time mark registers, checking to see if any queues for ports of the group are empty; for any empty queues, setting the queue's queue mark indicate bit equal to its queue mark bit.
References Cited (Backward Citations)
US5506987A
Cited
US5414704A
Cited
US6016388A
Cited
US5872773A
Cited
US6006266A
Cited
US5892903A
Cited
WO1998031107A2
Cited
US6052718A
Cited
US5953335A
Cited
US5989060A
Cited
US5959968A
Cited
US5950205A
Cited
US6345294B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-28 | 2006-04-29 | 2006-10-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-28 | 2010-04-29 | 2010-10-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-28 | 2014-04-29 | 2014-10-29 | $7700.00 | Window Closed / Lapsed |