Shared network path contention reduction

• US 7,751,315 B1
• Filed: 07/15/2003
• Issued: 07/06/2010
• Est. Priority Date: 07/15/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Colyer, Wallace C., Thaler, Leslie H., Pai, Sukesh H., Thukral, Vivek
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US10/620,143
• Time in Patent Office: 2,548 Days
• Field of Search: 370/230, 370/395.4, 370/412, 370/468, 725/115, 725/145
• US Class Current: 370/230
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876

Abstract

Shared network path contention can be reduced by limiting the number of contending client devices to which pending requests may be outstanding. Contention may also be reduced by managing available downstream bandwidth based on request size and managing available upstream bandwidth based on estimated response size. Portions of available downstream and/or upstream bandwidth may also be allocated to groups of one or more applications from which requests may be received, and the allocated portions may be configured to vary over time.

Claims

1. A method comprising:

identifying a plurality of upstream network paths associated with a single downstream network path;

establishing a plurality of upstream path request queues, wherein first and second upstream path request queues of the plurality of upstream path request queues are associated with first and second upstream network paths of the plurality of upstream network paths, respectively;

receiving from one or more applications, first and second requests to be transmitted to first and second client devices, respectively;

determining that the first client device is associated with the first upstream network path and that the second client device is associated with the second upstream network path;

storing the first request in the first upstream path request queue and storing the second request in the second upstream path request queue; and

performing a scheduling process, the scheduling process comprising;

verifying that a bandwidth available on the downstream network path is larger than a data size of the first request;

verifying that a bandwidth available on the first upstream network path is larger than a data size of an anticipated response to the first request; and

moving the first request to a first dispatch queue.

2. The method as recited in claim 1 wherein the scheduling process further comprises:

verifying that the bandwidth available on the downstream network path is larger than a combined data size of the first request and the second request;

verifying that a bandwidth available on the second upstream network path is larger than a data size of an anticipated response to the second request; and

moving the second request to a second dispatch queue.

3. The method as recited in claim 2 further comprising:

transmitting the first and second requests from the first and second dispatch queues over the downstream network path.

4. A system comprising:

one or more application request channels for receiving requests to be transmitted to client devices via a downstream network path, individual ones of the application request channels having an associated downstream path bandwidth allocation;

a plurality of upstream request queues for grouping the requests based on upstream network paths over which responses to the requests may be received; and

a bandwidth management system configured to schedule the requests from the plurality of upstream request queues for transmission to the client devices based, at least in part, on a request size and the downstream path bandwidth allocation associated with the application request channel through which the request was received.

5. The system as recited in claim 4 wherein individual ones of the application request channels have an associated upstream path bandwidth allocation and wherein the bandwidth management system is further configured to schedule the requests from the plurality of upstream request queues based on an estimated response size and the upstream path bandwidth allocation associated with the application request channel through which the request was received.

6. The system as recited in claim 4, implemented as a component of a cable television system headend.

7. A system comprising:

one or more application request channels for receiving requests to be transmitted to client devices via a downstream network path, individual ones of the application request channels having an associated upstream path bandwidth allocation;

a plurality of upstream request queues for grouping the requests based on upstream network paths over which responses to the requests may be received; and

a bandwidth management system configured to schedule the requests from the plurality of upstream request queues for transmission to the client devices based, at least in part, on an anticipated request response size and the upstream path bandwidth allocation associated with the application request channel through which the request was received.

8. The system as recited in claim 7 wherein individual ones of the application request channels have an associated downstream path bandwidth allocation and wherein the bandwidth management system is further configured to schedule the requests from the plurality of upstream request queues based on a request size and the downstream path bandwidth allocation associated with the application request channel through which the request was received.

9. The system as recited in claim 7, implemented as a component of a cable television system headend.

10. One or more computer-readable storage media comprising computer-executable instructions that, when executed, direct a computing system to perform a method comprising:

receiving a request through an application request channel;

identifying a client device to which the request is to be transmitted;

identifying an upstream network path associated with the client device;

queuing the request for transmission over a downstream network path based on the upstream network path that was identified;

identifying an upstream bandwidth allocation associated with the application request channel; and

scheduling the request for transmission based on a comparison between a portion of an available bandwidth associated with the upstream network path and a size of an anticipated response to the request, wherein the portion of the available bandwidth is determined based on the upstream bandwidth allocation associated with the application request channel.

11. The one or more computer-readable storage media as recited in claim 10, wherein the method further comprises estimating the size of the anticipated response to the request.

12. One or more computer-readable storage media comprising computer-executable instructions that, when executed, direct a computing system to perform a method comprising:

receiving a request through an application request channel;

identifying a client device to which the request is to be transmitted;

identifying an upstream network path associated with the client device;

identifying a downstream network path associated with the client device;

queuing the request for transmission over the downstream network path; and

identifying a downstream bandwidth allocation associated with the application request channel;

scheduling the request for transmission based on a comparison between a portion of an available bandwidth associated with the downstream network path and a size of the request, wherein the portion of the available bandwidth associated with the downstream network path is determined based on the downstream bandwidth allocation associated with the application request channel.