System and methods for controlling virtual paths within a network based on entropy rate function

• US 6,304,639 B1
• Filed: 11/24/1998
• Issued: 10/16/2001
• Est. Priority Date: 07/14/1995
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Holender, Wlodek, Malomsoky, Szabolcs
• Primary Examiner(s): TIEU, BINH KIEN
• Application Number:
  US09/198,681
• Time in Patent Office: 1,057 Days
• Field of Search: 379/11, 379/13, 379/14, 379/112, 379/113, 379/115, 379/133, 379/137, 379/201, 379/207, 379/219, 379/220, 379/230, 379/188, 379/189, 379/221, 379/222, 379/223, 379/224 , 379/242, 379/244, 370/241, 370/242, 370/244, 370/245, 370/250, 370/251, 370/252
• US Class Current: 379/112.04
• CPC Class Codes: H04Q 2213/13526 resource management
• CPC Class Codes: H04Q 2213/13531 virtual networks - inc. PVN
• CPC Class Codes: H04Q 2213/13562 blocking
• CPC Class Codes: H04Q 3/0062 Provisions for network management

Abstract

A general dimensioning method and system for allocating limited transmission resources to various virtual paths defined on top of a physical network. A two-level hierarchical structure is defined with a layer of one or more virtual paths on top of a layer of physical network elements. Traffic demand is specified for each virtual path and the Entropy Rate Function is used as a blocking measure. The loads on the various links are balanced by equalizing blocking probabilities and the optimal allocation of network physical resources is determined.

Claims

1. A method for dimensioning virtual paths defined within a telecommunications network carrying general traffic over a plurality of interconnected links whose transmission capacities are limited, said method comprising the steps of:

modeling the load on each virtual path of said telecommunications network using a computer configured to implement an entropy rate function; and

using said entropy rate function as a blocking measure to operatively cause said computer to dynamically control load balancing of said general traffic over said interconnected links.

2. The method of claim 1, wherein said step of using said entropy rate function further includes determining actual traffic measurements of at least a portion of said general traffic over certain ones of said interconnected links.

3. The method of claim 1 wherein said step of using said entropy rate function further includes determining idealized characteristics for said general traffic based on at least one probabilistic function selected from a group comprising a homogenous Poissonian distribution, a multi-class Poissonian distribution, a Normal distribution, and a Binomial distribution.

4. A method for dimensioning virtual paths on a constrained telecommunications network having a plurality of physical links interconnecting a plurality of nodes, said method comprising the steps of:

using a computer to map at least a portion of said plurality of physical links into at least two virtual paths, each of said virtual paths providing an individually switchable connection between a different pair of nodes in the telecommunications network;

specifying offered traffic for each of said virtual paths;

identifying a transmission capacity constraint for at least a portion of said physical links within said telecommunications network that are available for inclusion in said virtual paths;

using said computer to model offered traffic on at least a selected portion of said physical links available for inclusion in said virtual paths based at least in part on an entropy blocking measure function; and

selectively allocating capacities to each of said virtual paths, subject to said transmission capacity constraints, based on said entropy blocking measure function such that the blocking probabilities for at least said at least two virtual paths are substantially uniform.

5. A method for dimensioning a constrained telecommunications network having a plurality of physical links interconnecting a plurality of nodes, said method comprising:

mapping a plurality of physical links into one or more virtual paths, each of said virtual paths providing an individually switchable connection between a pair of nodes of the telecommunications network;

grouping a selected plurality of said virtual paths into a dimensioning set;

allocating initial transmission capacity to each virtual path at an initial blocking value;

selecting at least one subsequent blocking value that is lower than a corresponding initial blocking value by;

calculating blocking on each of said virtual paths traversing a single physical link;

allocating the available transmission capacity amongst virtual paths traversing a single physical link in response to variations in the blocking amongst different virtual paths until a physical link is identified as having no unallocated capacity;

removing all virtual paths traversing said identified physical link from said dimensioning set;

reducing the transmission capacity allocated to each of the physical links by an amount previously allocated to said removed virtual paths; and

iteratively repeating said calculating, allocating, removing and reducing steps until no virtual paths are left in the dimensioning set.

6. A computer implemented system for dimensioning virtual paths defined on a telecommunications network carrying general traffic, said network having a plurality of interconnected links whose transmission capacities are limited, said system comprising:

means for choosing an appropriate entropy rate function to model the load on each virtual path of said telecommunications network;

means for selecting a solution algorithm using the entropy rate function as a blocking measure that is operative to solve a load balancing problem for said general traffic; and

means for controlling load distribution via a computer using said load balancing algorithm incorporating said entropy rate function to produce a load distribution on said virtual paths that is substantially uniform.

7. The virtual path dimensioning system of claim 6, wherein said entropy rate function is determined by traffic measurements.

8. The system of claim 6 wherein said entropy rate function further determines idealized characteristics for said general traffic based on at least one probabilistic function selected from a group comprising a homogenous Poissonian distribution, a multi-class Poissonian distribution, a Normal distribution, and a Binomial distribution.

9. A system for dimensioning virtual paths on a constrained telecommunications network having a plurality of physical links interconnecting a plurality of nodes, said system comprising:

means for mapping said plurality of physical links into one or more virtual paths, each of said virtual paths providing an individually switchable connection between a pair of nodes in the telecommunications network;

means for specifying offered traffic for each of said virtual paths;

means for specifying a transmission capacity constraint for each physical link of the telecommunications network, including each physical link in each of said virtual paths;

means for modeling offered traffic over each of said physical links, using an entropy blocking measure; and

at least one computer configured to allocate capacities to each of said plurality of virtual paths based on said modeling and subject to said link transmission capacity constraints, such that the blocking probabilities on the at least a portion of said different virtual paths are significantly uniform.

10. A computer implemented method for establishing virtual paths within a network configured to carry general traffic, said network having a plurality of interconnected links whose transmission capacities are inherently limited, said method comprising:

choosing an appropriate entropy rate function to model the load on each virtual path of said telecommunications network, said entropy rate function being determined by idealizing the characteristics of offered traffic on a telecommunications network, and wherein the idealized entropy blocking measure used to model the offered traffic is said Entropy Rate Function, I_X(C), said Entropy Rate Function being calculable as the approximation of the negative logarithm of the probability that an arbitrarily distributed random variable, X, is greater than or equal to a preselected value, C, and said Entropy Rate Function additionally being a convex function obtaining its minimum value of zero at a mean of the distribution;

selecting a solution algorithm using said entropy rate function as a blocking measure that is operative to solve a load balancing problem for said general traffic; and

performing computations on a computing system using said load balancing algorithm incorporating said entropy rate function to produce a load distribution on said virtual paths that is substantially uniform for at least a selected portion of said virtual paths.

11. A computer implemented method of dimensioning virtual paths defined on a telecommunications network carrying general traffic, said network having a plurality of interconnected links whose transmission capacities are inherently limited, said dimensioning method comprising the steps of:

choosing an appropriate entropy rate function to model the load on each virtual path of said telecommunications network;

selecting a solution algorithm using said entropy rate function as a blocking measure that is operative to solve a load balancing problem for said general traffic, wherein said solution algorithm uses said entropy rate function as a blocking measure and is further configured to act as a push down algorithm that assembles the virtual paths to be dimensioned into a dimensioning set, calculates the blocking on each virtual path at every network link traversed by said virtual path using said entropy rate function, identifies the virtual path having the highest blocking on each network link, and allocates additional capacity to the identified virtual path without violating the network resource constraints until it no longer has the highest blocking; and

performing computations on a computing system using said load balancing algorithm incorporating said entropy rate function to produce a load distribution on said virtual paths that is substantially uniform.

12. A computer implemented method of dimensioning virtual paths defined on a telecommunications network carrying general traffic, said network having a plurality of interconnected links whose transmission capacities are inherently limited, said method comprising:

choosing an entropy rate function to model a load associated with each of a plurality of virtual paths within said telecommunications network;

using said entropy rate function as a blocking measure that is operative to solve a load balancing problem for said general traffic, wherein said algorithm using the entropy rate function as a blocking measure is further configured to perform the following iterative steps;

grouping all virtual paths into a dimensioning set;

specifying the transmission capacity of each physical link;

choosing a relatively large initial blocking value for each virtual path;

selecting an error bound to evaluate the convergence of a critical link identifying algorithm;

determining the blocking value for each virtual path using an entropy blocking measure;

iteratively identifying the virtual path having the largest blocking value as long as the physical link has available capacity;

reducing the blocking of the virtual path having the largest blocking value by reallocating transmission capacities amongst said virtual paths as long as no physical link reaches full utilization and the blocking reductions of the maximally-obstructed virtual path is greater than a preselected error bound;

identifying physical links lacking allocable capacity as critical links;

eliminating all virtual paths spanning critical links from the dimensioning set; and

selectively re-adjusting the transmission capacities of the remaining physical links to reflect the capacities allocated to virtual paths most recently eliminated from the dimensioning set; and

performing computations on a computing system using said load balancing algorithm incorporating said entropy rate function to produce a load distribution on said virtual paths that is substantially uniform.

13. A computer implemented system for dimensioning virtual paths defined on a telecommunications network carrying general traffic, said network having a plurality of interconnected links whose transmission capacities are limited, said system comprising:

means for choosing an appropriate entropy rate function to model the load on each virtual path of said telecommunications network;

means for selecting a solution algorithm using the entropy rate function, and wherein said entropy rate function is determined by idealizing the characteristics of offered traffic on a telecommunications network wherein the idealized entropy blocking measure used to model the offered traffic is the Entropy Rate Function, I_X(C), said Entropy Rate Function being calculable as the approximation of the negative logarithm of the probability that an arbitrarily distributed random variable, X, is greater than or equal to a preselected value, C, and said Entropy Rate Function additionally being a convex function obtaining its minimum value of zero at the mean of the distribution; and

means for performing computations on a computing system using said load balancing algorithm incorporating said entropy rate function to produce a load distribution on said virtual paths that is substantially uniform.

14. A computer system for dimensioning virtual paths defined on a telecommunications network carrying general traffic, said network having a plurality of interconnected links whose transmission capacities are limited, said computer system comprising:

at least one processor configured to operatively respond to computer implemented instructions associated with an entropy rate function, a solution algorithm, and a load balancing algorithm, wherein;

said entropy rate function is configured to model the load on each virtual path of said telecommunications network;

said solution algorithm is configured to use the entropy rate function as a blocking measure in solving a load balancing problem for said general traffic by assembling the virtual paths to be dimensioned into a dimensioning set, calculating a blocking on each virtual path at every network link traversed by said virtual path using said entropy rate function, identifying the virtual path having a largest blocking on each network link, and selectively allocating additional capacity to the identified virtual path having the largest blocking to reduce the blocking associated with the identified virtual path; and

said load balancing algorithm is configured to incorporate said entropy rate function to produce a load distribution on each of said virtual paths that is substantially uniform.

15. A system for use in dimensioning virtual paths defined within a telecommunications network for carrying general traffic, said network having a plurality of interconnected links whose transmission capacities are limited, said system comprising:

means for choosing an appropriate entropy rate function to model the load on each virtual path of said telecommunications network;

means for selecting a solution algorithm that uses said entropy rate function as a blocking measure in solving load balancing problems associated with said general traffic, said solution algorithm iteratively implementing a push down function using;

means for grouping all virtual paths into a dimensioning set;

means for specifying the transmission capacity of each physical link;

means for choosing a relatively large initial blocking value for each virtual path;

means for selecting an error bound to evaluate the convergence of a critical link identifying algorithm;

means for determining the blocking value for each virtual path using an entropy blocking measure;

means for iteratively identifying the virtual path having the largest blocking value as long as the physical link has available capacity;

means for reducing the blocking of the virtual path having the largest blocking value by reallocating transmission capacities amongst said virtual paths as long as no physical link reaches full utilization and the blocking reductions of the maximally-obstructed virtual path is greater than a preselected error bound;

means for identifying physical links lacking allocable capacity as critical links;

means for eliminating all virtual paths spanning critical links from the dimensioning set; and

means for iteratively readjusting the transmission capacities of the remaining physical links to reflect the capacities allocated to virtual paths most recently eliminated from the dimensioning set; and

means for controlling a load distribution on each of said virtual paths based on said entropy rate function and said solution algorithm such that the resulting load distributions are substantially uniform.