US 7,801,177 B2Granted

Method for equitable bandwidth allocation for content distribution networks

AssigneeTelcordia Technologies, Inc.

InventorHanan Luss

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method is presented for determining bandwidth allocations in a content distribution network that comprises multiple trees, where the root of each tree has a server that broadcasts multiple programs throughout the tree. Each network link has limited capacity and may be used by one or more of these trees. The allocation problem is formulated as an equitable resource allocation problem with a lexicographic maximin objective function that attempts to provide equitable service performance for all requested programs at the various nodes. The constraints include link capacity constraints and tree-like ordering constraints imposed on each of the programs. The algorithm provides an equitable solution in polynomial time for wide classes of performance functions. At each iteration, the algorithm solves single-link maximin optimization problems while relaxing the ordering constraints, selects a bottleneck link and fixes various variables at their optimal value.

Claims12

Dependent claims

A method for determining bandwidth allocations among a plurality of programs on each link of a content distribution network comprised of multiple trees, comprising the steps of:

broadcasting a plurality of programs from the root node of each of the trees along a path comprising a plurality of links connecting nodes through the corresponding tree to at least one destination node;
and
allocating bandwidth for each program of said plurality of programs carried on a link having an available bandwidth capacity such that the sum of the allocated bandwidths of all of the programs carried on the link does not exceed the available bandwidth capacity of the link;
where the allocated bandwidth for each program carried on a link cannot be below a specified lower bound and the allocated bandwidth for each program can be decreased but not increased from one link to the next link along a path from the corresponding root node of the tree that broadcasts the program to at least one destination node;
and
assigning a performance function to each program requested at a node where the performance function is the same at all nodes that request the same program and is strictly increasing with the incoming bandwidth for the program at the node;
and
computing equitable bandwidth allocations among all programs carried on each of the links, where the equitable bandwidth allocations result in the performance function values for each program requested at a node and the lexicographic largest vector of performance function values where the performance function values are sorted in non-decreasing order.

5 more elements

A program storage device, readable by machine, tangibly embodying a program of instructions executable by the machine to cause the machine to perform a method for determining equitable bandwidth allocations among a plurality of programs on each link of a content distribution network comprised of multiple trees, comprising the steps of:

broadcasting a plurality of programs from the root node of each of the trees along a path comprising a plurality of links connecting nodes through the corresponding tree to at least one destination node;
and
allocating bandwidth for each program of said plurality of programs carried on a link having an available bandwidth capacity such that the sum of the allocated bandwidths of all of the programs carried on the link does not exceed the available bandwidth capacity of the link;
where the allocated bandwidth for each program carried on a link cannot be below a specified lower bound and the allocated bandwidth for each program can be decreased but not increased from one link to the next link along a path from the corresponding root node of the tree that broadcasts the program to at least one destination node;
and
assigning a performance function to each program requested at a node where the performance function is the same at all nodes that request the same program and is strictly increasing with the incoming bandwidth for said program at said node;
and
computing equitable bandwidth allocations among all programs carried on each of the links, where the equitable bandwidth allocations result in the performance function values for each program requested at a node and the lexicographic largest vector of performance function values where the performance function values are sorted in non-decreasing order.

5 more elements

Dependencies are inferred from the claim text.