IP Library › Granted Patent US 8,248,930
Granted Patent B2
US 8,248,930 · App. 12/387,196 · Granted Aug 21, 2012

Method and apparatus for a network queuing engine and congestion management gateway

Assignee: Google Inc.
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 8,248,930
App. No.
12/387,196
Granted
Aug 21, 2012
Kind
B2
Abstract

A method, apparatus, and queuing engine implement congestion management. The method may include receiving, via a first interface of the apparatus, data traffic for forwarding to a node of a network. The method may also include receiving, at a second interface of the apparatus, a notification that indicates that congestion is affecting communication with the node, and responsive to the notification, accumulating the data traffic into the queue for a given time period. The method may further include dequeuing the data traffic from the queue after the given time period; and sending the portion of the data traffic to the node via the second interface.

Claims (40)

1. A method comprising: receiving, via a first interface, a packet flow of data packets from a first network for forwarding to a node of a second network, the second network employing a protocol for managing congestion and the first network not employing any protocol for managing congestion; receiving, at a second interface, a notification from the second network that indicates that congestion is affecting communication with the node of the second network, wherein the protocol for managing congestion employed by the second network defines a given bitrate for sending at least one first packet in the packet flow to the node of the second network; responsive to the notification, calculating a first time and a second time to satisfy the given bitrate, enqueuing the packet flow into a process-controlled queue at the first time; dequeuing the at least the one first packet in the packet flow from the queue at the second time; and sending the at least one first packet of the packet flow to the node of the second network via the second interface.

2. The method of claim 1 , wherein the notification from the second network includes the given bitrate defined by the protocol for managing congestion employed by the second network.

3. the method of claim 1 , wherein enqueuing the packet flow into the queue at the first time comprises: pausing a flow of the at least one first packet in the packet flow to the second interface, and wherein dequeuing the at least one first packet in the packet flow from the queue at the second time comprises: resuming the flow of the at least one first packet in the packet flow to the second interface.

4. The method of claim 1 , wherein the notification comprises a message formed in accordance with the protocol for managing congestion.

5. An apparatus comprising: a first interface for receiving a packet flow of data packets from a first network for forwarding to a node of a second network, the second network employing a protocol for managing congestion and the first network not employing any protocol for managing congestion; a second interface for receiving a notification from the second network that indicates that congestion is affecting communication with the node, wherein the protocol for managing congestion employed by the second network defines a given bitrate for sending at least one first packet in the packet flow to the node of the second network; a memory; and a processor that is configured to execute executable instructions to: calculate a first time and a second time to satisfy the given bitrate; enqueue the packet flow into a queue at the first time; dequeue the at least one first packet in the packet flow from the queue at the second time; and send the at least one first packet in the packet flow to the node of the second network via the second interface.

6. The apparatus of claim 5 ,

wherein the notification from the second network includes the given bitrate defined by the protocol for managing congestion employed by the second network.

7. The apparatus of claim 5 , wherein the executable instructions further comprise one or more executable instructions to: pause a flow of the packet flow to the second interface, and dequeue the at least one first packet in the packet flow to resume the flow of the packet flow to the second interface.

8. The apparatus of claim 5 , wherein the notification comprises a message formed in accordance with the protocol for managing congestion.

9. A method comprising:

receiving, at a first interface that communicatively couples with a first network, a first notification that indicates that congestion is affecting communication with a first node of the first network, the first network employing a protocol for managing congestion;

receiving, at the first interface, a second notification that indicates that congestion is affecting communication with a second node of the first network,

wherein the protocol for managing congestion employed by first network defines a first bitrate for sending at least one first packet in a first packet flow to the first node, and the protocol for managing congestion employed by the first network defines a second bitrate for sending at least one second packet in a second packet flow to the second node;

receiving, at a second interface that communicatively couples with a second network, the first packet flow including the at least one first packet from the second network for delivery to the first node, the second network not employing any protocol for managing congestion;

receiving, at the second interface, the second packet flow including the at least one second packet from the second network for delivery to the second node;

calculating a first time and a third time to satisfy the first bitrate;

calculating a second time and a forth time to satisfy the second bitrate;

enqueuing, by a processor, the first packet flow at the first time;

enqueuing, by the processor, the second packet flow at the second time;

dequeueing, by the processor, the at least one first packet of the first packet flow at the third time;

dequeueing, by the processor, the at least one second packet of the second packet flow at the fourth time;

sending the at least one first packet to the first node via the first interface; and

sending the at least one second packet to the second node via the first interface.

10. The method of claim 9 , wherein the first notification includes the first bitrate for sending the at least one first packet to the first node, and wherein the second notification includes the second bitrate for sending the at least one second packet to the second node.

11. An apparatus comprising:

a first interface that is configured to (i) communicatively couple with a first network, (ii) receive a first notification that indicates that congestion is affecting communication with a first node of the first network, and (iii) receive a second notification that indicates that congestion is affecting communication with a second node of the first network, the first networking employing a protocol for managing congestion, wherein the protocol for managing congestion employed by the first network defines a first bitrate for sending at least one first packet in a first flow of data packets to the first node, and, the protocol for managing congestion employed by the first network defines a second bitrate for sending at least one second packet in a second flow of data packets to the second node;

a second interface that is configured to (i) communicatively couple with a second network, (ii) receive the first packet flow including the at least one first packet from the second network for delivery to the first node, and (iii) receive the second packet flow including the at least one second packet from the second network for delivery to the second node, the second network not employing any protocol for managing congestion;

memory; and

a processor that is configured to execute executable instructions to:

calculate a first time period to satisfy the first bitrate;

calculate a second time period to satisfy the second bitrate;

enqueue the first packet flow in the queue for the first time period;

enqueue the second packet flow in the queue for the second time period;

dequeue the at least one first packet of the first packet flow from the queue after the first time period;

dequeue the at least one second packet of the second packet flow from the queue after the second time period;

send the at least one first packet to the first node via the first interface; and

send the at least one second packet to the second node via the first interface.

12. The apparatus of claim 11 , wherein the first notification comprises a first message formed in accordance with the protocol for managing congestion, and wherein the second notification comprises a second message formed in accordance with the protocol for managing congestion.

13. The apparatus of claim 11 , wherein the first notification includes the first bitrate for sending the at least one first packet to the first node, and wherein the second notification includes the second bitrate for sending the at least one second packet to the second node.

14. The apparatus of claim 11 , wherein the first notification comprises a first indication to pause delivery of the at least one first packet, and wherein the second notification comprises a second indication to pause delivery of the at least one second packet.

Assignments (3)
CHANGE OF NAME Recorded Oct 2, 2017
From: GOOGLE INC.
To: GOOGLE LLC
Reel/Frame 044101/0405 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 10, 2012
From: FELDERMAN, ROBERT EDMAN
To: GOOGLE INC.
Reel/Frame 028571/0703 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 22, 2009
From: FELDERMAN, BOB; BANNON, ROY M.; HOCHSCHILD, PETER; ROECK, GUENTER; LIU, HAIN-CHING HUMPHREY
To: GOOGLE INC.
Reel/Frame 022726/0917 →
Continuity (2)
Provisional Application 61048913 · Apr 29, 2008
Related Publication 20090268612A1 · Oct 29, 2009