Patent ID: 8320274
Filing Date: 2012-11-27
Classification: H04L

Abstract:
1. A distributed method for determining equitable bandwidth allocations in a content distribution tree network of nodes and interconnecting links comprising the steps of: performing computations at each of the nodes independently while only minimal information is exchanged among the nodes where the root of the tree has a server that broadcasts multiple programs throughout the tree; and defining the equitable bandwidth allocation problem by Problem EBAM comprising the lexicographic maximin optimization problem so that are satisfied, and where x (i,j)p =Bandwidth allocated on link (i, j) for program p where x (i,j)p is continuous, and x (i,j)p ≧B p where B p is a lower bound for bandwidth required by program p x=Vector of decision variables x NP=a set of all program-node pairs c(i,j)=a capacity limit of available bandwidth of link (i,j) A=set of interconnecting directed links D SUC(j)=the set of immediate successor nodes of node j LP=a set of all program-link pairs F jp (x (i,j)p) =Performance function associated with program p requested at node j, where x (i,j)p is the bandwidth allocated to program p on link (i, j) and, hence, into node j and the distributed method for determining equitable bandwidth allocations among plurality of programs on each link of the network is specified by the Distributed Method for EBAM comprising the steps of: a. computing sets of programs that will be carried on each link of the network wherein set computations are done recursively starting at the leaf nodes of the tree network and moving upwards along the tree nodes; b. computing temporary equitable bandwidth allocation at each node for each outgoing link from that node among plurality of programs carried on the outgoing link, independently from computations executed at other nodes, where the allocation among plurality of programs at link (i, j) is computed by solving a single link association problem Problem SLBAM-(i, j) comprising so that c. determining bottleneck link in the tree network through recursive computations, starting computations from the leaf nodes and moving upwards along the tree nodes; d. determining final equitable bandwidth allocations to programs carried on the bottleneck link; e. determining final equitable bandwidth allocations to programs on links that are included in the subtree whose root node is the head node of the bottleneck link; f. determining final equitable bandwidth allocations to programs on links that are included on the path connecting the root node of the tree network to the tail node of the bottleneck link; and g. proceeding with a new iteration with distributed computations, starting at step b with computing new temporary equitable bandwidth allocations for some links, wherein the method terminates once final equitable allocation decisions for all programs on all links are made.