Communication network multiplexer grooming optimization

Patent metadata

Field	Value
Publication number	US-10764138-B2
Application number	US-201916543262-A
Country	US
Kind code	B2
Filing date	Aug 16, 2019
Priority date	May 13, 2015
Publication date	Sep 1, 2020
Grant date	Sep 1, 2020

Abstract

Aspects of optimized grooming of multiplexers of a communication network are presented. In an example method, an optimization value associated with each of a plurality of multiplexer configurations may be determined, wherein each of the plurality of multiplexer configurations includes a proposed assignment of each of a plurality of data channels to one of a plurality of inputs of a plurality of multiplexers. A multiplexer configuration having a highest-ranked optimization value of the plurality of multiplexer configurations may be identified and subsequently used to configure the multiplexers. Other potential aspects of the present disclosure are described in greater detail below.

First claim

The invention claimed is:

1. A method for optimization of communication network multiplexers, the method comprising:
identifying, using at least one hardware processor of a machine, each service delivery point of a plurality of service delivery points as a cluster, wherein each service delivery point comprises a plurality of multiplexers;
iteratively combining, using the at least one hardware processor of the machine, two closest clusters according to geographical distance between clusters until all clusters are combined to create a hierarchical clustering of the plurality of service delivery points;
identifying, using the at least one hardware processor of the machine, multiple subgroups of service delivery points based on the hierarchical clustering of the plurality of service delivery points; and
for each subgroup of service delivery points:
determining, using the at least one hardware processor of the machine, an optimization value associated with each of a plurality of multiplexer configurations associated with the subgroup of service delivery points; and
identifying, using the at least one hardware processor of the machine and from the plurality of multiplexer configurations associated with the subgroup, a multiplexer configuration having a highest-ranked optimization value of the plurality of multiplexer configurations, wherein
the multiplexers are configured to multiplex the plurality of data channels using time-division multiplexing (TDM).

2. The method of claim 1 , wherein each of the plurality of multiplexer configurations comprises a proposed assignment of each of a plurality of data channels to one of a plurality of inputs of the plurality of multiplexers, further comprising configuring the plurality of multiplexers based on the proposed assignment corresponding to the identified multiplexer configuration.

3. The method of claim 2 , wherein the determining of the optimization value associated with each of the plurality of multiplexer configurations comprises instituting at least one constraint on the proposed assignment of each of the plurality of data channels to a corresponding one of the plurality of inputs.

4. The method of claim 2 , wherein:
a most recently identified multiplexer configuration comprises the identified multiplexer configuration; and
the method further comprises, for each time period of a series of time periods:
revising the most recently identified multiplexer configuration based on at least one simulated change in the plurality of data channels during the time period;
determining a next optimization value associated with each of a next plurality of multiplexer configurations based on the revised multiplexer configuration;
identifying, from the next plurality of multiplexer configurations, a next multiplexer configuration having a highest-ranked next optimization value of the next plurality of multiplexer configurations as the most recently identified multiplexer configuration; and
advancing to a next time period in the series of time periods.

5. The method of claim 1 , wherein the determining of the optimization value associated with each of the plurality of multiplexer configurations is performed using an integer programming algorithm.

6. The method of claim 1 , wherein:
the optimization value associated with each of the plurality of multiplexer configurations comprises a monetary cost associated with each of the plurality of multiplexer configurations; and
the highest-ranked optimization value of the plurality of multiplexer configurations comprises a lowest monetary cost associated with the plurality of multiplexer configurations.

7. A system for optimization of communication network multiplexers, the system comprising:
at least one hardware processor; and
memory comprising instructions that, when executed by the at least one hardware processor, cause the system to:
identify each service delivery point of a plurality of service delivery points as a cluster, wherein each service delivery point comprises a plurality of multiplexers;
iteratively combine two closest clusters according to geographical distance between clusters until all clusters are combined to create a hierarchical clustering of the plurality of service delivery points;
identify multiple subgroups of service delivery points based on the hierarchical clustering of the plurality of service delivery points; and
for each subgroup of service delivery points:
determine an optimization value associated with each of a plurality of multiplexer configurations associated with the subgroup of service delivery points; and
identify, from the plurality of multiplexer configurations associated with the subgroup, a multiplexer configuration having a highest-ranked optimization value of the plurality of multiplexer configurations, wherein
the multiplexers are configured to multiplex the plurality of data channels using time-division multiplexing (TDM).

8. The system of claim 7 , wherein each of the plurality of multiplexer configurations comprises a proposed assignment of each of a plurality of data channels to one of a plurality of inputs of the plurality of multiplexers, further comprising configuring the plurality of multiplexers based on the proposed assignment corresponding to the identified multiplexer configuration.

9. The system of claim 7 , wherein the instructions cause the system to determine the optimization value associated with each of the plurality of multiplexer configurations using an integer programming algorithm.

10. The system of claim 9 , wherein the instructions cause the system to determine the optimization value associated with each of the plurality of multiplexer configurations by instituting at least one constraint on the proposed assignment of each of the plurality of data channels to a corresponding one of the plurality of inputs.

11. The system of claim 10 , wherein the at least one constraint on the proposed assignment of each of the plurality of data channels to a corresponding one of the plurality of inputs comprises:
each of the plurality of data channels is assigned to exactly one of the plurality of multiplexers;
each of the plurality of multiplexers is assigned less than or equal to a predetermined number of the plurality of data channels; and
a multiplexer to be disconnected is assigned none of the plurality of data channels.

12. The system of claim 10 , wherein the at least one constraint on the proposed assignment of each of the plurality of data channels to a corresponding one of the plurality of inputs comprises:
and

∑
j

⁢

x

i
,
j

=
1

,

∀

i
∈

{

1
,
2
,

…
⁢

⁢
I

}

Assignees

• Level 3 Communications Llc

Inventors

• Chen Binchao
• Gray William

Classifications

• H04L41/0826 Primary

  for reduction of network costs (H04L41/0833 takes precedence) · CPC title

• H04L41/145

  involving simulating, designing, planning or modelling of a network · CPC title