IP Library › Granted Patent US 7,224,671
Granted Patent B2
US 7,224,671 · App. 09/930,764 · Granted May 29, 2007

Method and apparatus for load balancing in network processing device

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 7,224,671
App. No.
09/930,764
Granted
May 29, 2007
Kind
B2
Abstract

A data rate controller controls a rate that data is transferred over a backplane in a network processing device. A bandwidth allocator allocates bandwidth to an input port for transmitting data over the backplane to an output port. A bandwidth limiter identifies a maximum allowable bandwidth the input port is allocated on the backplane. A bandwidth tracker identifies an amount of bandwidth currently allocated to the input port for transmitting data over the backplane to the output port. When the current allocated bandwidth is used up, the data rate controller prevents that input port from connecting to output ports through the backplane until more bandwidth is allocated.

Claims (46)

1. A data rate controller for controlling a rate that data is transferred over a backplane in a network processing device, comprising:

a bandwidth allocator configured to allocate bandwidth to an input port for transmitting data over the backplane to an output port, the bandwidth allocator comprising a register that stores a programmable peak time slot rate value, and a counter that assigns an additional amount of bandwidth when the counter decrements the peak time slot rate value down to zero;

a bandwidth limiter configured to identify a maximum allowable bandwidth the input port is allocated on the backplane; and

a bandwidth tracker configured to identify an amount of bandwidth currently allocated to the input port for transmitting data over the backplane to the output port, the input port prevented from connecting to the output port when the current allocated bandwidth is used up.

2. A data rate controller for controlling a rate that data is transferred over a backplane in a network processing device, comprising:

a bandwidth allocator configured to allocate bandwidth to an input port for transmitting data over the backplane to an output port;

a bandwidth limiter configured to identify a maximum allowable bandwidth the input port is allocated on the backplane; and

a bandwidth tracker configured to identify an amount of bandwidth currently allocated to the input port for transmitting data over the backplane to the output port, the input port prevented from requesting a connection to the output port when the current allocated bandwidth is used up, the bandwidth tracker including a counter that decrements the amount of bandwidth currently allocated when the input port is connected through the backplane to an output port and increments the amount of currently allocated bandwidth when the input port is not connected through the backplane to the output port, wherein the bandwidth tracker is disabled from counting up when the maximum allowable bandwidth has been reached.

3. A data rate controller for controlling a rate that data is transferred over a backplane that includes multiple input ports and multiple output ports in a network processing device, comprising:

an arbitration circuit configured to arbitrate between input ports for connections to output ports;

a bandwidth allocator configured to allocate bandwidth to an input port for transmitting data over the backplane to an output port;

a bandwidth limiter configured to identify a maximum allowable bandwidth the input port is allocated on the backplane; and

a bandwidth tracker configured to identify an amount of bandwidth currently allocated to the input port for transmitting data over the backplane to the output port, the input port prevented from connecting to the output port when the current allocated bandwidth is used up, the data rate controller one of multiple data rate controllers in the network processing device, the data rate controllers assigned respectively to each input-output port combination in the network processing device, wherein the bandwidth tracker prevents requests to the arbitration circuit for the input ports having exhausted bandwidth allocation.

4. A data rate controller according to claim 3 wherein each one of the input ports has associated virtual output queues each associated with a different one of the output ports and the virtual output queues each have associated data rate controllers.

5. A data rate controller according to claim 3 , the arbitration circuit selecting the input ports for a next time slot according to both a priority and weight of packets at the input ports.

6. A data rate controller according to claim 5 wherein the arbitration circuit selects the input ports in a round robin order when two or more of the input ports have a same highest priority and a same largest weight.

7. A data rate controller according to claim 5 wherein the arbitration circuit conducts output port arbitrations for all of the virtual output queues dedicated to the same output ports and conducts input port arbitrations between the virtual output queues for the same input port issued grants during the output port arbitrations, the data rate controllers associated with the virtual output queues preventing participation in the output port arbitrations when bandwidth allocation associated with the virtual output queues is exhausted.

8. A method for controlling a rate that data is transferred over a switch fabric, comprising:

allocating bandwidth to input ports for transferring data to output ports over the switch fabric;

providing multiple input port buffers for each input port, each input port buffer associated with a different output port;

sending requests from the input ports for connecting to the output ports during a next time slot, wherein sending requests from a given input port comprises sending connection requests, from multiple ones of the input port buffers provided for the given input port, for connecting to the output ports through the switch fabric;

conducting arbitrations for the connection requests to determine which input ports are connected to which output ports;

increasing bandwidth allocation for the input ports that are not connected to the output ports for the next time slot;

decreasing bandwidth allocation for the input ports that are connected to the output ports for the next time slot; and p 1 preventing the input ports from sending requests for the input ports when the bandwidth allocated to the input ports has been exhausted, wherein preventing the input ports from sending requests comprises disabling the input port buffers from sending connection requests when their allocated bandwidth has been used up.

9. A method according to claim 8 including identifying maximum bandwidth allocations for the input ports and disabling bandwidth allocation to the input ports that reach these maximum allowable bandwidth allocations.

10. A method according to claim 8 including providing a programmable amount of bandwidth allocation for the input ports.

11. A method for controlling a rate that data is transferred over a switch fabric, comprising:

selecting a bandwidth allocation to time slot period ratio;

allocating bandwidth to input ports for transferring data to output ports over the switch fabric;

assigning a bandwidth allocation value to the input ports according to the selected ratio;

sending requests from the input ports for connecting to the output ports during a next time slot;

increasing bandwidth allocation for the input ports that are not connected to the output ports for the next time slot;

decreasing bandwidth allocation for the input ports that are connected to the output ports for the next time slot; and

preventing the input ports from sending requests for the output ports when the bandwidth allocated to the input ports has been exhausted.

12. A method according to claim 8 including:

identifying bandwidth allocated to the output ports for transferring data to a network; and

preventing the output ports that have used up this allocated bandwidth from granting connections to the input ports.

13. A network processing device, comprising:

multiple input ports for receiving incoming packets;

multiple output ports for outputting packets;

a switch fabric coupled to the different input ports and the different output ports;

multiple virtual output queues associated with each one of the input ports, each one of the virtual output queues dedicated to a different one of the output ports;

a scheduler that configures the switch fabric for connecting the input ports to the output ports; and

a set of data rate controllers associated with each one of the virtual output queues for controlling a data rate that the input ports can transfer data to the output ports over the switch fabric, wherein the data rate controllers prevent input ports that have exceeded a data rate limit from sending connection requests to the scheduler.

14. A network processing device according to claim 13 wherein packets are transferred over the switch fabric during time slots and the data rate controllers control data rate per time slot ratios between the input ports and output ports.

15. A network processing device according to claim 14 including a second set of data rate controllers that control a rate that data is received by the output ports from multiple input ports.

Assignments (15)
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (053546/0001) Recorded Jun 23, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC IP HOLDING COMPANY LLC
Reel/Frame 071642/0001 →
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (045455/0001) Recorded May 20, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO ASAP SOFTWARE EXPRESS, INC.); DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC CORPORATION (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MAGINATICS LLC); EMC IP HOLDING COMPANY LLC (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MOZY, INC.); SCALEIO LLC
Reel/Frame 061753/0001 →
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (040136/0001) Recorded Apr 26, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO ASAP SOFTWARE EXPRESS, INC.); DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC CORPORATION (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MAGINATICS LLC); EMC IP HOLDING COMPANY LLC (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MOZY, INC.); SCALEIO LLC
Reel/Frame 061324/0001 →
RELEASE OF SECURITY INTEREST Recorded Nov 3, 2021
From: CREDIT SUISSE AG, CAYMAN ISLANDS BRANCH
To: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL, L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; WYSE TECHNOLOGY L.L.C.
Reel/Frame 058216/0001 →
MERGER Recorded Mar 4, 2021
From: FORCE10 NETWORKS, INC.
To: DELL MARKETING CORPORATION
Reel/Frame 056104/0988 →
SECURITY AGREEMENT Recorded Apr 22, 2020
From: CREDANT TECHNOLOGIES INC.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; FORCE10 NETWORKS, INC.; WYSE TECHNOLOGY L.L.C.; EMC IP HOLDING COMPANY LLC
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A.
Reel/Frame 053546/0001 →
SECURITY AGREEMENT Recorded Mar 21, 2019
From: CREDANT TECHNOLOGIES, INC.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; FORCE10 NETWORKS, INC.; WYSE TECHNOLOGY L.L.C.; EMC IP HOLDING COMPANY LLC
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A.
Reel/Frame 049452/0223 →
SECURITY AGREEMENT Recorded Sep 21, 2016
From: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; SPANNING CLOUD APPS LLC; WYSE TECHNOLOGY L.L.C.
To: CREDIT SUISSE AG, CAYMAN ISLANDS BRANCH, AS COLLATERAL AGENT
Reel/Frame 040134/0001 →
SECURITY AGREEMENT Recorded Sep 21, 2016
From: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; SPANNING CLOUD APPS LLC; WYSE TECHNOLOGY L.L.C.
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
Reel/Frame 040136/0001 →
RELEASE OF SECURITY INTEREST Recorded Sep 14, 2016
From: BANK OF AMERICA, N.A., AS COLLATERAL AGENT
To: DELL SOFTWARE INC.; FORCE10 NETWORKS, INC.; DELL MARKETING L.P.; ASAP SOFTWARE EXPRESS, INC.; APPASSURE SOFTWARE, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL PRODUCTS L.P.; DELL USA L.P.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
Reel/Frame 040040/0001 →
RELEASE OF SECURITY INTEREST Recorded Sep 14, 2016
From: BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS COLLATERAL AGENT
To: DELL MARKETING L.P.; ASAP SOFTWARE EXPRESS, INC.; APPASSURE SOFTWARE, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL PRODUCTS L.P.; DELL USA L.P.; DELL SOFTWARE INC.; FORCE10 NETWORKS, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
Reel/Frame 040065/0618 →
RELEASE OF SECURITY INTEREST Recorded Sep 13, 2016
From: BANK OF AMERICA, N.A., AS ADMINISTRATIVE AGENT
To: DELL MARKETING L.P.; ASAP SOFTWARE EXPRESS, INC.; APPASSURE SOFTWARE, INC.; COMPELLANT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL PRODUCTS L.P.; DELL USA L.P.; DELL SOFTWARE INC.; FORCE10 NETWORKS, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
Reel/Frame 040065/0216 →
PATENT SECURITY AGREEMENT (NOTES) Recorded Jan 2, 2014
From: APPASSURE SOFTWARE, INC.; ASAP SOFTWARE EXPRESS, INC.; BOOMI, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL USA L.P.; FORCE10 NETWORKS, INC.; GALE TECHNOLOGIES, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
To: BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS FIRST LIEN COLLATERAL AGENT
Reel/Frame 031897/0348 →
PATENT SECURITY AGREEMENT (ABL) Recorded Jan 2, 2014
From: DELL INC.; APPASSURE SOFTWARE, INC.; ASAP SOFTWARE EXPRESS, INC.; BOOMI, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL USA L.P.; FORCE10 NETWORKS, INC.; GALE TECHNOLOGIES, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
To: BANK OF AMERICA, N.A., AS ADMINISTRATIVE AGENT
Reel/Frame 031898/0001 →
PATENT SECURITY AGREEMENT (TERM LOAN) Recorded Jan 2, 2014
From: DELL INC.; APPASSURE SOFTWARE, INC.; ASAP SOFTWARE EXPRESS, INC.; BOOMI, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL USA L.P.; FORCE10 NETWORKS, INC.; GALE TECHNOLOGIES, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
To: BANK OF AMERICA, N.A., AS COLLATERAL AGENT
Reel/Frame 031899/0261 →