Back to results
US 11,108,684 B1Granted
Satisfying a set of services over given network resources
AssigneeECI Telecom Ltd.
InventorsShirel Ezra, Efraim Gelman, Inbal Hecht
Life of this patent
Estimating the term…
Abstract
Techniques for satisfying a plurality of service demands in a data communication network are disclosed. Aspects include identifying a first plurality of edges, each of which connects two of a plurality of nodes in the data communication network, wherein each of the first plurality of edges is associated with one of a plurality of unprotected service demands; generating a spanning tree comprising a second plurality of edges selected from the first plurality of edges, wherein the spanning tree connects all of the plurality of nodes that are connected by the first plurality of edges; and creating a set of service links based on the generated spanning tree.
Claims27
A method of satisfying demands in a data communication network utilizing a set of service links, the method comprising:
- identifying a plurality of service link paths,
- wherein each of the plurality of service link paths corresponds to one of a first plurality of service demands,
- wherein each of the first plurality of service demands is associated with a weight;
- wherein each of the set of service links is associated with a plurality of weights, each of the plurality of weights is associated with a service demand;
- and a P value is assigned to each of the first plurality of service demands;
- determining a protection level for one or more of the first plurality of service demands;
- assigning one of the first plurality of service demands with one or more of the plurality of service link paths based on the determined protection level;
- selecting a second plurality of service demands from the first plurality of service demands based on the weight associated with each of the first plurality of service demands, the plurality of weights associated with each of the set of service links, and the P value assigned to each of the first plurality of service demands,
- wherein a sum for each of a plurality of weights associated with the second plurality of service demands is less than or equal to a predetermined value associated with each of the service links, and
- wherein a sum of P values associated with demands of the second plurality of service demands is maximized;
- and
- satisfying the second plurality of service demands using at least one of the set of service links.
9 more elements
A method of rerouting service demands in a data communication network upon one or more failures, the method comprising:
- identifying one or more failed service links;
- identifying a second plurality of service demands among a first plurality of service demands, each of the second plurality of service demands associated with the one or more failed service links;
- identifying a third plurality of service demands among the second plurality of service demands, wherein for each of the third plurality of service demands, a pre-planned route that does not use the failed service links is unavailable;
- determining one or more of the third plurality of service demands are satisfied using available service links;
- identifying one or more candidate routes for each of the one or more of the third plurality of service demands, where a candidate route comprises non-failed service links, each of the third plurality of service demands is associated with a weight, each of the available service links is associated with a plurality of weights, each of the plurality of weights is associated with a service demand, and a P value is assigned to each of the third plurality of service demands;
- determining a protection level for one or more of the third plurality of service demands;
- assigning one of the third plurality of service demands with one or more of the available service links based on the determined protection level;
- selecting a set of service demands from the third plurality of service demands based on the weight associated with each of the third plurality of service demands, the plurality of weights associated with each of the available service links, and the P value assigned to each of the third plurality of service demands, wherein a sum of P values associated with the set of service demands is maximized,
- wherein the selected set of service demands is associated with one or more of the available service links, each service link of the one or more of the available service links is associated with one or more service demands of the selected set of service demands, and for each service link of the one or more of the available service links, a total volume of the associated one or more service demands does not exceed a free space of the corresponding service link;
- and
- rerouting the selected set of service demands based on the identified candidate routes.
8 more elements
A system for satisfying demands in a data communication network utilizing a set of service links, the system comprising:
- at least one processor;
- and
- at least one memory containing instructions that, when executed by the at least one processor, cause the system to perform operations comprising:
- identifying a plurality of service link paths,
- wherein each of the plurality of service link paths corresponds to one of a first plurality of service demands,
- wherein each of the first plurality of service demands is associated with a weight, wherein each of the set of service links is associated with a plurality of weights, each of the plurality of weights is associated with a service demand, and wherein a P value is assigned to each of the first plurality of service demands;
- determining a protection level for one or more of the first plurality of service demands;
- assigning one of the first plurality of service demands with one or more of the plurality of service link paths based on the determined protection level;
- selecting a second plurality of service demands from the first plurality of service demands based on the weight associated with each of the first plurality of service demands, the plurality of weights associated with each of the set of service links, and the P value assigned to each of the first plurality of service demands,
- wherein a sum for each of a plurality of weights associated with the second plurality of service demands is less than or equal to a predetermined value associated with each of the plurality of service demands, and
- wherein a sum of P values associated with demands of the second plurality of service demands is maximized;
- and
- satisfying the second plurality of service demands using at least one of the set of service links.
10 more elements
A system for rerouting service demands in a data communication network upon one or more failures, comprising:
- at least one processor;
- and
- at least one memory containing instructions that, when executed by the at least one processor, cause the system to perform operations comprising:
- identifying one or more failed service links;
- identifying a second plurality of service demands among a first plurality of service demands, each of the second plurality of service demands associated with the one or more failed service links;
- identifying a third plurality of service demands among the second plurality of service demands, wherein for each of the third plurality of service demands, a pre-planned route that does not use the failed service links is unavailable;
- determining one or more of the third plurality of service demands are satisfied using available service links;
- identifying one or more candidate routes for each of the one or more of the third plurality of service demands, where a candidate route comprises non-failed service links, each of the third plurality of service demands is associated with a weight, each of the available service links is associated with a plurality of weights, each of the plurality of weights is associated with a service demand, and a P value is assigned to each of the third plurality of service demands;
- determining a protection level for one or more of the third plurality of service demands;
- assigning one of the third plurality of service demands with one or more of the available service links based on the determined protection level;
- selecting a set of service demands from the third plurality of service demands based on the weight associated with each of the third plurality of service demands, the plurality of weights associated with each of the available service links, and the P value assigned to each of the third plurality of service demands, wherein a sum of P values associated with the set of service demands is maximized,
- wherein the selected set of service demands is associated with one or more of the available service links, each service link of the one or more of the available service links is associated with one or more service demands of the selected set of service demands, and for each service link of the one or more of the available service links, a total volume of the associated one or more service demands does not exceed a free space of the corresponding service link;
- and
- rerouting the selected set of service demands based on the identified candidate routes.
11 more elements
Dependencies are inferred from the claim text.