Enhancement of network operation and performance

• US 6,069,894 A
• Filed: 04/21/1997
• Issued: 05/30/2000
• Est. Priority Date: 06/12/1995
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Farago, Andras, Henk, Tamas, Blaabjerg, Soren, Holender, deceased, Wlodek, Stavenow, Bengt
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/765,106
• Time in Patent Office: 1,135 Days
• Field of Search: 370/232, 370/248, 370/252, 370/253, 370/338, 370/347, 370/388, 370/397, 370/400, 370/409, 370/465, 370/468, 370/399, 370/396
• US Class Current: 370/397
• CPC Class Codes: H04L 2012/5623 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04L 2012/5626 Network management, e.g. Intelligent nets
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A set of logical networks is established on top of a physical network Next, a predefined objective function, closely related to the operation and performance of the physical network, which physical network is viewed as the set of logical networks, is optimized with respect to at least one set of decision variables. Finally, the decision variables in accordance with the optimization are used to control the operation of the overall network system. Physical transmission resources are partitioned among logical networks. Traffic loads are distributed among routes interconnecting the nodes of node pairs.

Claims

1. In a physical network comprising physical transmission and switching resources, and carrying different traffic types, a method for partitioning said physical transmission resources among logical networks, comprising the steps of:

establishing said logical networks on top of said physical network such that said logical networks are at least based on said physical network and said traffic types, said logical networks comprising nodes and logical links that extend between said nodes,

optimizing, given an objective function, the operation of said physical network, viewed as the set of said logical networks, according to said given objective function, said optimizing step being performed with respect to decision variables comprising capacity values of said logical links, and said objective function comprising variables which depend upon the traffic type, wherein said step of optimizing the operation of the physical network comprises the steps of;

selecting initial values for the capacity values of said logical links associated with said logical networks,

iteratively calculating, given said objective function, new logical link capacities associated with said logical networks, and

terminating said iteration process when at least one convergence condition is met, and wherein said step of allocating is performed according to the finally calculated logical link capacities, and

allocating said physical transmission resources among said logical links of said logical networks according to the capacity values of said logical links after said optimization,

wherein the operation of said physical network is optimized according to said given objective function and with consideration to the traffic types.

2. The method of claim 1, wherein the optimizing step is subject to physical constraints defining a feasibility region.

3. The method of claim 2, wherein the step of iteratively determining logical link capacities comprises the steps of calculating a gradient of the objective function with respect to the decision variables and using the gradient to obtain new logical link capacities in the iterative determination.

4. The method of claim 3, wherein the step of using the gradient of the objective function to obtain new logical link capacities further comprises the steps of performing a one-dimensional line search to find an optimal step size in a direction of a projection of the gradient of the objective function to the feasibility region, and taking a step in the direction according to a found step size.

5. The method of claim 1, wherein logical link capacity values obtained from a convex optimization method are selected as the initial values for the logical link capacities.

6. In a physical network comprising physical transmission and switching resources, and carrying different traffic types, a method for partitioning said physical transmission resources among logical networks, comprising the steps of:

establishing said logical networks on top of said physical network such that said logical networks are at least based on said physical network and said traffic types, said logical networks comprising nodes and logical links that extend between said nodes,

optimizing, given an objective function, the operation of said physical network, viewed as the set of said logical networks, according to said given objective function, said optimizing step being performed with respect to decision variables comprising capacity values of said logical links, and said objective function comprising variables which depend upon the traffic type, and

allocating said physical transmission resources among said logical links of said logical networks according to the capacity values of said logical links after said optimization,

wherein the operation of said physical network is optimized according to said given objective function and with consideration to the traffic types and wherein said logical links are used by routes and said decision variables further comprise route offered traffic values, each of said routes being defined as a subset of logical links which interconnect the nodes of a node pair within a given logical network, and wherein said method further comprises the step of distributing, for each individual node pair in each one of said logical networks, offered traffic load among the routes which can realize communication between the nodes of the individual node pair, in accordance with the route offered traffic values after said optimization.

7. The method of claim 6, wherein the optimizing step is executed with physical network data, a topology of the logical networks, traffic type information, routes in each of the logical networks, and offered traffic to each node pair in each logical network as input information.

8. The method of claim 6, wherein the optimizing step, allocating step, and distributing step are repeated in response to changing traffic conditions so as to adapt partitioning of the physical transmission resources and distributing of the offered traffic load to prevailing traffic.

9. The method of claim 6, wherein the optimizing step further comprises the steps of:

selecting initial values for the decision variables;

iteratively determining, based on the objective function, new values for the decision variables; and

terminating the iterative determination when at least one convergence condition is met; and

the allocating and distributing steps are performed according to the iteratively determined values for the decision variables.

10. The method of claim 9, wherein the optimizing step is subject to physical constraints defining a feasibility region.

11. The method of claim 9, wherein the iteratively determining step comprises the steps of calculating a gradient of the objective function with respect to the decision variables and using the gradient to obtain new values for the decision variables in the iterative determination.

12. The method of claim 11, wherein the step of using the gradient of the objective function further comprises the steps of performing a one-dimensional line search to find an optimal step size in a direction of a projection of the gradient of the objective function to a feasibility region, and taking a step in the direction according to a found step size.

13. In a physical network comprising physical transmission resources and carrying different traffic types, a device for partitioning said physical transmission resources among logical networks, comprising:

means for establishing said logical networks on top of said physical network such that said logical networks are at least based on said physical network and said traffic types, said logical networks comprising nodes and logical links that extend between said nodes,

means for optimizing a given objective function which is representative of the performance of said physical network viewed as the set of said logical networks, said objective function comprising variables which vary with the traffic type, and said optimizing step being performed with respect to decision variables comprising capacity values of said logical links, and

means for allocating said physical transmission resources among said logical links of said logical networks according to the capacity values of said logical links after said optimization, wherein said logical links are used by routes and said decision variables further comprise route offered traffic values, a route being defined as a subset of logical links which interconnect the nodes of a node pair within a given logical network, and said device further comprising means for distributing, for each individual node pair in each one of said logical networks, offered traffic load among the routes which can realize communication between the nodes of the individual node pair, in accordance with the route offered traffic values after said optimization.

14. In a physical network comprising physical transmission and switching resources, a method for distributing offered traffic load among routes interconnecting the nodes of the node pairs, comprising the steps of:

optimizing, given an objective function, the distribution, for each individual node pair, of the offered traffic load to the individual node pair among the routes which can realize communication between the nodes of the individual node pair, according to said given objective function, said optimizing step being performed with respect to route offered traffic values, wherein said step of optimizing the distribution comprises the steps of;

selecting initial route offered traffic values,

iteratively calculating, given said objective function, new route offered traffic values, ands

terminating said iteration process when at least one convergence condition is met, and wherein said step of apportioning is performed according to the finally calculated route offered traffic values, and

apportioning, for each individual node pair, the offered traffic load of the individual node pair among the routes which can realize communication between the nodes of the individual node pair, according to the route offered traffic values after said optimization.

15. The method of claim 14, wherein the iteratively determining step comprises the steps of calculating a gradient of the objective function with respect to the route offered traffic values and using the gradient to obtain the new route offered traffic values in the iterative determination.

16. The method of claim 15, wherein the optimizing step is subject to physical constraints defining a feasibility region.

17. The method of claim 16, wherein the step of using the gradient of the objective function further comprises the steps of performing a one-dimensional line search to find an optimal step size in a direction of a projection of the gradient of the objective function to the feasibility region, and taking a step in the direction according to a found step size.

18. In a physical network comprising physical transmission and switching resources, a device for distributing offered traffic load among routes interconnecting the nodes of node pairs, comprising:

means for determining the optimal distribution, for each individual node pair in each one of a number of logical networks established on top of said physical network, of the traffic load offered to the individual node pair among the routes which can realize communication between the nodes of the individual node pair, according to a given objective function, said determining step being performed with respect to route offered traffic values, wherein said determining means further comprises;

means for selecting initial values for route offered traffic,

means for iteratively calculating, given said objective function, new values for the route offered traffic by calculating the gradient of said given objective function with respect to the route offered traffic values and using said gradient to obtain said new values for the route offered traffic in said iteration process, and

means for terminating said iteration process when at least one convergence condition is met, and wherein said apportioning means executes the apportioning in accordance with the finally calculated values for the route offered traffic, and

means for apportioning, for each individual node pair in each one of said logical networks, the traffic load offered to the individual node pair among the routes which can realize communication between the nodes of the individual node pair, according to the route offered traffic values after said determination of the optimal distribution.

19. In a physical network comprising physical transmission and switching resources, a device for distributing offered traffic load among routes interconnecting the nodes of node pairs, comprising:

means for determining the optimal distribution, for each individual node pair in each one of a number of logical networks established on top of said physical network, of the traffic load offered to the individual node pair among the routes which can realize communication between the nodes of the individual node pair, according to a given objective function, said determining step being performed with respect to route offered traffic values, and

means for apportioning, for each individual node pair in each one of said logical networks, the traffic load offered to the individual node pair among the routes which can realize communication between the nodes of the individual node pair, according to the route offered traffic values after said determination of the optimal distribution, wherein said apportioning means comprises random number generator means.

20. In a physical network, a method for partitioning physical link capacities among logical links, the method comprising the steps of:

establishing logical nodes and the logical links on top of the physical network, the logical links extending between the logical nodes;

selecting initial capacity values for the logical links;

iteratively determining, based on an objective function, new logical link capacity values, wherein the iterative determination is subject to physical constraints defining a feasibility region;

terminating the iterative determination when convergence with a known level of accuracy is obtained; and

allocating the physical link capacities among the logical links according to the iteratively determined logical link capacity values;

wherein the iteratively determining step comprises the steps of calculating a gradient of the objective function with respect to the logical link capacities and using the gradient to obtain the new logical link capacity values in the iterative determination.

21. The method of claim 20, wherein the step of using the gradient of the objective function to obtain new logical link capacity values further comprises the steps of performing a one-dimensional line search to find an optimal step size in a direction of a projection of the gradient of the objective function to the feasibility region, and taking a step in the direction according to a found step size.

22. The method of claim 20, wherein the iterative determination is executed with physical network data, the topology of the logical links, routes and offered traffic to each route or to each node pair as input information, and each of said routes corresponds to a subset of logical links that interconnect the nodes of a node pair.

23. The method of claim 20, wherein the established logical links carry different traffic types, and the objective function comprises parameters that depend on the traffic types.

24. The method of claim 23, wherein the traffic types are distinguished with respect to bandwidth requirement.

25. The method of claim 20, wherein optimization is subject to physical link capacity constraints, and a logical link is guaranteed a minimum capacity provided overall physical link capacity constraints are satisfied.

26. In a physical network comprising physical switching resources and physical transmission resources, and carrying different traffic types, a method for partitioning the physical transmission resources among logical networks, comprising the steps of:

establishing the logical networks on top of the physical network, each logical network comprising a plurality of nodes and a plurality of logical links extending between the nodes,

optimizing a given objective function, which is closely related to the operation of the physical network viewed as a set of the logical networks, with respect to decision variables comprising capacity values of the logical links, the objective function comprising variables that depend upon the traffic types, and

allocating the physical transmission resources among the logical links of the logical networks according to the capacity values of said logical links after the optimization,

whereby the operation of said physical network is optimized according to the given objective function and with consideration to the traffic types.

27. The method of claim 26, wherein said traffic types are distinguished with respect to a bandwidth requirement.

28. The method of claim 26, wherein the optimizing step and the allocating step are repeated in response to changing traffic conditions so as to adapt the partitioning of the physical transmission resources to prevailing traffic.

29. The method of claim 26, wherein the establishing step comprises the step of controlling a port assignment of the physical switching resources.

30. The method of claim 26, wherein the optimizing step comprises the steps of:

selecting initial values for the capacity values of the logical links,

iteratively calculating, given said objective function, new capacity values of logical links, and

terminating said iteration process when at least one convergence condition is met; and

wherein the allocating step is performed according to the finally calculated capacity values of the logical links.

31. The method of claim 30, wherein the optimizing step is subject to physical constraints defining a feasibility region.

32. The method of claim 31, wherein the step of iteratively calculating capacity values of the logical links comprises the steps of calculating a gradient of the given objective function with respect to the decision variables and using the gradient to obtain new capacity values of the logical links in the iterative calculation.

33. The method of claim 32, wherein the step of using the gradient of the given objective function to obtain new capacity values comprises the steps of performing a one-dimensional line search to find an optimal step size in a direction of a projection of the gradient of the objective function to the feasibility region, and taking a step in the direction according to a found step size.

34. The method of claim 32, wherein the step of calculating the gradient is based on a per se known reduced load and link independence assumption.

35. The method of claim 32, wherein the step of calculating the gradient includes the step of solving fixed point equations with respect to the current capacity values of the logical links.

36. The method of claim 30, wherein logical link capacity values obtained from a convex optimization method (COM) are selected as the initial values for the capacity values of the logical links.

37. The method of claim 26, wherein the allocating step comprises the step of using logical buffers at output ports of the physical switching resources.

38. The method of claim 26, wherein the physical network is an infrastructure network modeling the ATM cross connect stratum in a B-ISDN overlaid network.

39. The method of claim 26, wherein the optimizing step is executed with physical network data, the topology of the logical networks, traffic type information, the routes in each of the logical networks and the offered traffic to each route or to each node pair in each logical network as given input information, a route being defined as a subset of logical links which interconnect the nodes of a node pair within a given logical network.

40. The method of claim 26, wherein the objective function represents one of network resource utilization and total carried traffic summed up over all the logical networks.

41. In a physical network comprising physical transmission resources and carrying different traffic types, a device for partitioning the physical transmission resources among logical networks, comprising:

means for establishing the logical networks on top of the physical network, each logical network comprising a plurality of nodes and a plurality of logical links extending between the nodes;

means for optimizing a given objective function, which is representative of a performance of the physical network viewed as a set of the logical networks, with respect to decision variables comprising capacity values of said logical links, the objective function comprising variables that vary with traffic type, and

means for allocating the physical transmission resources among the logical links of the logical networks according to the capacity values of the logical links after optimization.

42. In a physical network comprising physical transmission resources, and carrying different traffic types that are distinguished with respect to bandwidth requirement, a method for partitioning the physical transmission resources among logical networks, comprising the steps of:

establishing the logical networks on top of the physical network, each logical network comprising a plurality of nodes and a plurality of logical links extending between the nodes, traffic types having a bandwidth requirement within a first interval being integrated in a first of the logical networks and traffic types having a bandwidth requirement within a second different interval being integrated in another of the logical networks;

optimizing a given objective function, which is closely related to the operation of the physical network viewed as a set of the logical networks, with respect to decision variables comprising capacity values of the logical links, the objective function having bandwidth requirement variables that vary with traffic type; and

allocating the physical transmission resources among the logical links of the logical networks according to the capacity values of said logical links after the optimization.

43. In a physical network, a method for partitioning physical link capacities among logical links, said method comprising the steps of:

establishing logical nodes and the logical links on top of the physical network, the logical links extending between the logical nodes;

selecting initial capacity values for the logical links,

iteratively calculating, based on a given objective function, new logical link capacity values, wherein the iterative calculation is subject to physical constraints defining a feasibility region and involves establishing and solving of a set of fixed point equations;

terminating the iterative calculation when convergence is achieved with a predetermined level of accuracy; and

allocating the physical link capacities among the logical links according to the finally calculated logical link capacity values.

44. The method of claim 43, wherein the logical link capacity values are regarded as fixed in each iteration step, and the objective function, in each iteration step, is approximated as a linear function valid in a neighborhood of the fixed logical link capacity values.

45. The method of claim 43, wherein the fixed point equations are solved by successive substitutions to thereby compute blocking probabilities for the logical links.