Method of telecommunications demand-route multiplexing (DEROM)

• US 5,959,975 A
• Filed: 05/23/1997
• Issued: 09/28/1999
• Est. Priority Date: 05/23/1997
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: WorldCom, Inc. (Verizon Communications Inc.)
• Inventors: Sofman, Lev B., Nathan, Sridhar S.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/862,290
• Time in Patent Office: 858 Days
• Field of Search: 370/216, 370/225, 370/228, 370/229, 370/230, 370/231, 370/235, 370/236, 370/237, 370/238, 370/252, 370/254, 370/255, 370/351, 370/400, 370/539, 370/541, 340/825.01, 340/825.03, 340/826, 340/827, 395/181, 395/182.01, 395/182.02, 395/200.64, 395/200.65, 395/200.68, 395/200.69, 395/200.7, 395/200.71, 395/200.72, 395/500
• US Class Current: 370/238
• CPC Class Codes: H04J 2203/0053 Routing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of optimizing a telecommunications network in terms of transmission and equipment cost by multiplexing lower bandwidth level telecommunications demand-routes to form higher bandwidth level bundles, by determining, for each demand-route, whether the demand-route includes a patching subroute. For each patching subroute, the method finds a best bundle of demand-routes that includes the patching subroute. The best bundle is the one that has the highest cost gradient between the sum of the costs associated with the demand-routes included in the best bundle and the total cost associated with the best bundle. The method then multiplexes the demand-routes according to the best bundles.

Claims

1. A method of multiplexing lower bandwidth level telecommunications demand-routes to form higher bandwidth level bundles, there being a multiplex level ratio defined between said lower bandwidth level and said higher bandwidth level, each of said demand-routes having a cost associated therewith, which comprises the computer implemented steps of:

for each demand-route, determining whether said demand-route includes a patching subroute;

for each patching subroute, finding a best bundle of demand-routes that includes said patching subroute, said best bundle having a highest cost gradient between the sum of the costs associated with the demand-routes included in said best bundle and the total cost associated with said best bundle; and

,

multiplexing said demand-routes according to said best bundles.

2. The method as claimed in claim 1, wherein said step of finding a best bundle of demand-routes includes the computer implemented steps of:

(a) setting a best cost gradient equal to a selected value;

(b) selecting a bundle of demand-routes that include said patching subroute;

(c) calculating a cost gradient for said selected bundle;

(d) whenever a calculated cost gradient is greater than the set best cost gradient, setting the best cost gradient equal to the calculated cost gradient and identifying the selected bundle as the best bundle; and

,

(e) repeating steps (b) through (d) until all combinations of demand-routes that include said patching subroute have been selected.

3. The method as claimed in claim 2, wherein said selected value is zero.

4. The method as claimed in claim 1, including the computer implemented step of:

excluding from bundling any demand-route that includes a number of lower bandwidth demands equal to an integer of an express parameter.

5. The method as claimed in claim 4, wherein said express parameter is an integer multiple of said multiplex level ratio.

6. The method as claimed in claim 1, including the computer implemented step of:

excluding from bundling any demand-route that includes a number of lower bandwidth demands equal to or greater than an integer multiple of an express parameter plus a predetermined threshold value.

7. The method as claimed in claim 1, including the computer implemented steps of:

for each demand-route, determining whether said demand-route includes a number of lower bandwidth demands less than an integer multiple of an express parameter plus a predetermined threshold value;

partitioning a demand-route determined to include a number of lower bandwidth demands less than an integer multiple of said express parameter plus a predetermined threshold value into a first demand subroute having a number of lower bandwidth demands equal to said integer multiple of said express parameter and a second demand subroute having the remaining lower bandwidth demands; and

,

excluding said first demand subroute from bundling.

8. The method as claimed in claim 1, including the computer implemented steps of:

defining a patching subroute set;

defining a temporary array; and

,

defining a final array.

9. The method as claimed in claim 8, including the computer implemented step of:

including each patching subroute in said patching subroute set.

10. The method as claimed in claim 8, including the computer implemented step of:

including each demand-route determined not to include a patching subroute in said final array.

11. The method as claimed in claim 8, including the computer implemented step of:

including in said final array each demand-route that includes a number of lower bandwidth demands equal to an integer multiple of an express parameter.

12. The method as claimed in claim 8, including the computer implemented step of:

including in said final array each demand-route that includes a number of lower bandwidth demands equal to or greater than an integer multiple of an express parameter plus a predetermined threshold value.

13. The method as claimed in claim 8, including the computer implemented steps of:

for each demand-route determined to include a patching subroute, determining whether said demand-route includes a number of lower bandwidth demands less than an integer multiple of an express parameter plus a predetermined threshold value;

partitioning a demand-route determined to include a number of lower bandwidth demands less than an integer multiple of said express parameter plus a predetermined threshold value into a first demand subroute having a number of lower bandwidth demands equal to said integer multiple of said express parameter and a second demand subroute having the remaining lower bandwidth demands;

including said first demand subroute in said final array; and

,

including said second demand subroute in said temporary array.

14. The method as claimed in claim 8, including the computer implemented step of:

including in said temporary array each demand-route determined to include a patching subroute and that includes a number of lower bandwidth demands less than a predetermined threshold value.

15. The method as claimed in claim 14, wherein said step of finding a best bundle of demand-routes that includes a patching subroute includes the computer implemented steps of:

(a) selecting a patching subroute from said patching subroute set;

(b) setting a best cost gradient equal to a selected value;

(c) selecting from said temporary array a bundle of demand-routes that include said patching subroute;

(d) calculating a cost gradient for said selected bundle;

(e) whenever a calculated cost gradient is greater than the set best cost gradient, setting the best cost gradient equal to the calculated cost gradient and identifying the selected bundle as the best bundle;

(f) repeating steps (c) through (e) until all combinations of demand-routes that include said patching subroute have been selected;

(g) partitioning the best bundle into a partition that includes said patching subroute and remaining parts of the demand-routes comprising said best bundle;

(h) moving said partitioned patching subroute to said final array;

(i) including said remaining parts in said temporary array;

(j) deleting the demand-routes comprising said best bundle from said temporary array; and

,

(k) repeating steps (a) through (j) until all patching subroutes in said patching subroute set have been selected.

16. The method as claimed in claim 15, wherein said selected value is zero.

17. The method as claimed in claim 15, including the computer implemented step of:

after step (k), moving the contents of the temporary array to the final array.

18. A method of multiplexing lower bandwidth level telecommunications demand-routes to form higher bandwidth level bundles, there being a multiplex level ratio defined between said lower bandwidth level and said higher bandwidth level, each of said demand-routes having a cost associated therewith, which comprises the computer implemented steps of:

defining a patching subroute set;

defining a temporary array;

defining a final array;

for each demand-route, determining whether said demand-route includes a patching subroute;

including in said patching subroute set each patching subroute;

including in said final array each demand-route determined not to include a patching subroute;

including in said temporary array each demand-route determined to include a patching subroute and that includes a number of lower bandwidth demands less than a predetermined threshold value;

including in said final array each demand-route that includes a number of lower bandwidth demands equal to an integer multiple of an express parameter;

including in said final array each demand-route that includes a number of lower bandwidth demands equal to or greater than an integer multiple of said express parameter plus a predetermined threshold value;

for each patching subroute in said patching subroute set, finding a best bundle of demand-routes in said temporary array that includes said patching subroute, said best bundle having a highest cost gradient between the sum of the costs associated with the demand-routes included in said best bundle and the total cost associated with said best bundle; and

,

multiplexing said demand-routes according to said best bundles.

19. The method as claimed in claim 18, including the computer implemented steps of:

for each demand-route determined to include a patching subroute, determining whether said demand-route includes a number of lower bandwidth demands less than an integer multiple of said express parameter plus a predetermined threshold value;

partitioning a demand-route determined to include a number of lower bandwidth demands less than an integer multiple of said express parameter plus a predetermined threshold value into a first demand subroute having a number of lower bandwidth demands equal to said integer multiple of said express parameter and a second demand subroute having the remaining lower bandwidth demands;

including said first demand subroute in said final array; and

,

including said second demand subroute in said temporary array.

20. The method as claimed in claim 18, wherein said step of finding a best bundle of demand-routes that includes a patching subroute includes the computer implemented steps of:

(a) selecting a patching subroute from said patching subroute set;

(b) setting a best cost gradient equal to a selected value;

(c) selecting from said temporary array a bundle of demand-routes that include said patching subroute;

(d) calculating a cost gradient for said selected bundle;

(e) whenever a calculated cost gradient is greater than the set best cost gradient, setting the best cost gradient equal to the calculated cost gradient and identifying the selected bundle as the best bundle;

(f) repeating steps (c) through (e) until all combinations of demand-routes that include said patching subroute have been selected;

(g) partitioning the best bundle into a partition that includes said patching subroute and remaining parts of the demand-routes comprising said best bundle;

(h) moving said partitioned patching subroute to said final array;

(i) including said remaining parts in said temporary array;

(j) deleting the demand-routes comprising said best bundle from said temporary array; and

,

(k) repeating steps (a) through (j) until all patching subroutes in said patching subroute set have been selected.

21. The method as claimed in claim 20, wherein said selected value is zero.

22. The method as claimed in claim 20, including the computer implemented step of:

after step (k), moving the contents of the temporary array to the final array.

23. The method as claimed in claim 18, wherein said express parameter is an integer multiple of said multiplex level ratio.