Granted Patent B2

US 12,640,984 · App. 18/680,820 · Granted May 26, 2026

Inventors: Ziv Shem-Tov (Ramat Hasharon, IL); Efraim Gelman (Ramat Gan, IL); Inbal Hecht (Petah Tikva, IL); Shirel Ezra (Ganei Tal, IL)

Assignee: ECI Telecom Ltd.

H04L41/082H04L41/12

Abstract

Claims (76)

1 . A method for configuring a communications network, comprising:

obtaining a network graph representing the communications network, the network graph including vertices corresponding to nodes in the communications network and edges corresponding to communications links in the communications network;

obtaining a demand on the network graph, the demand specifying a source vertex of the vertices and a terminal vertex of the vertices;

determining a valid path from the source vertex to the terminal vertex, the determination comprising:

identifying a path length for which some valid path exists between the source vertex and the terminal vertex using a structure lacking zero divisors and a connectivity set for the network graph, wherein communicatively connected consecutive pairs of communication links in the communications network are each associated with an element of the connectivity set; and

determining a valid path of the identified path length on the network graph using the connectivity set; and

configuring one or more components of the communications network to implement a route that satisfies the demand using the valid path.

2 . The method of claim 1 , wherein:

the structure includes an additive identity element and additional elements.

3 . The method of claim 1 , wherein:

the structure comprises a modulus field constructed by an irreducible polynomial over the set of all polynomials over a binary field.

4 . The method of claim 3 , wherein:

an order of the irreducible polynomial is selected, at least in part, to satisfy a false negative probability criterion.

5 . The method of claim 1 , wherein:

the path length is identified using dynamic programming.

6 . The method of claim 1 , wherein:

identifying the path length for which the valid path exists comprises:

determining an element of the structure, the element corresponding to a set of paths of the path length between the source vertex and the terminal vertex.

7 . The method of claim 6 , wherein:

based on the element being an additive identity element of the structure, identifying the path length for which the valid path exists further comprises:

updating an association of elements of the structure with elements of the connectivity set; and

determining an updated element of the structure, the updated element corresponding to the set of paths of the path length between the source vertex and the terminal vertex.

8 . The method of claim 1 , wherein:

determining the valid path of the identified path length comprises:

selecting an edge in the network graph that connects to an endpoint vertex of an initial path, the initial path starting at the source vertex and ending at the endpoint vertex;

determining a second path length for which a second valid path exists between the source vertex and the terminal vertex, the second valid path including the initial path and the selected edge;

comparing the identified path length to the second path length; and

adding the selected edge to the initial path based on the comparison.

9 . The method of claim 1 , wherein:

determining the valid path of the identified path length comprises:

identifying a set of candidate edges connected to an endpoint vertex of an initial path on the network graph, the initial path starting at the source vertex and ending at the endpoint vertex;

iteratively searching the set of candidate edges for a valid candidate edge; and

concatenating the initial path and the valid candidate edge.

10 . The method of claim 9 , wherein:

an iteration of the iterative search comprises:

determining a second path length for which a second valid path exists between the source vertex and the terminal vertex, the second valid path including the initial path concatenated with one of an enabled subset of the candidate edges;

updating the enabled subset of the candidate edges when the enabled subset of the candidate edges includes multiple edges or the path length differs from the second path length; and

selecting, when the enabled subset of the candidate edges includes a single edge and the identified path length equals the second path length, the single edge as the valid candidate edge.

11 . A non-transitory, computer-readable medium containing instructions that, when executed by at least one processor of a system, cause the system to perform operations for configuring a communications network, the operations comprising:

obtaining a network graph representing the communications network, the network graph including vertices corresponding to nodes in the communications network and edges corresponding to communications links in the communications network;

obtaining a demand on the network graph, the demand specifying a source vertex of the vertices and a terminal vertex of the vertices;

determining a valid path from the source vertex to the terminal vertex, the determination comprising:

identifying a path length for which some valid path exists between the source vertex and the terminal vertex using a structure lacking zero divisors and a connectivity set for the network graph, wherein communicatively connected consecutive pairs of communication links in the communications network are each associated with an element of the connectivity set; and

determining a valid path of the identified path length on the network graph using the connectivity set; and

configuring one or more components of the communications network to implement a route that satisfies the demand using the valid path.

12 . The non-transitory, computer-readable medium of claim 11 , wherein:

the structure includes an additive identity element and additional elements.

13 . The non-transitory, computer-readable medium of claim 11 , wherein:

the structure comprises a modulus field constructed by an irreducible polynomial over the set of all polynomials over a binary field.

14 . The non-transitory, computer-readable medium of claim 13 , wherein:

an order of the irreducible polynomial is selected, at least in part, to satisfy a false negative probability criterion.

15 . The non-transitory, computer-readable medium of claim 11 , wherein:

the path length is identified using dynamic programming.

16 . The non-transitory, computer-readable medium of claim 11 , wherein:

identifying the path length for which the valid path exists comprises:

determining an element of the structure, the element corresponding to a set of paths of the path length between the source vertex and the terminal vertex.

17 . The non-transitory, computer-readable medium of claim 16 , wherein:

based on the element being an additive identity element of the structure, identifying the path length for which the valid path exists further comprises:

updating an association of elements of the structure with elements of the connectivity set; and

determining an updated element of the structure, the updated element corresponding to the set of paths of the path length between the source vertex and the terminal vertex.

18 . The non-transitory, computer-readable medium of claim 16 , wherein:

determining the valid path of the identified path length comprises:

selecting an edge in the network graph that connects to an endpoint vertex of an initial path, the initial path starting at the source vertex and ending at the endpoint vertex;

determining a second path length for which a second valid path exists between the source vertex and the terminal vertex, the second valid path including the initial path and the selected edge;

comparing the identified path length to the second path length; and

adding the selected edge to the initial path based on the comparison.

19 . The non-transitory, computer-readable medium of claim 11 , wherein:

determining the valid path of the identified path length comprises:

identifying a set of candidate edges connected to an endpoint vertex of an initial path on the network graph, the initial path starting at the source vertex and ending at the endpoint vertex;

iteratively searching the set of candidate edges for a valid candidate edge; and

concatenating the initial path and the valid candidate edge.

20 . The non-transitory, computer-readable medium of claim 19 , wherein:

an iteration of the iterative search comprises:

determining a second path length for which a second valid path exists between the source vertex and the terminal vertex, the second valid path including the initial path concatenated with one of an enabled subset of the candidate edges;

updating the enabled subset of the candidate edges when the enabled subset of the candidate edges includes multiple edges or the path length differs from the second path length; and

selecting, when the enabled subset of the candidate edges includes a single edge and the identified path length equals the second path length, the single edge as the valid candidate edge.

Assignments (2)

Continuity (3)

References Cited (11)