Network monitoring method using phantom nodes
First Claim
1. A system for determining node congestion in a dynamic network comprising:
- a nodal network, where the nodal network comprises a quantity of n nodes, where every node comprising the quantity of n nodes comprises a forwarding device, and where the every node has a communications link to at least one other node comprising the quantity of n nodes, where the communications link has a maximum bandwidth XMAXIMUM;
a programmable controller in data communication with each node comprising the quantity of n nodes, where the programmable controller is programmed to perform steps comprising;
polling one or more nodes comprising the quantity of n nodes and determining a throughput XMEASURED for each communications link comprising the nodal network;
defining a link weight for the each communications link using the XMAXIMUM for the each communications link and using the XMEASURED for the each communications link;
creating one or more phantom nodes, where each phantom node does not physically exist within the nodal network, and where the one or more phantom nodes comprises a quantity of m phantom nodes, and where each phantom node is a representation of an additional node in the nodal network, by;
devising a phantom link between the each phantom node and one of the nodes comprising the quantity of n nodes, thereby devising one or more phantom links; and
assigning a phantom link weight for each phantom link in the one or more phantom links, thereby assigning one or more phantom link weights and creating the one or more phantom nodes;
developing a plurality of analysis nodes where the plurality of analysis nodes comprises the quantity of n nodes and the quantity of m phantom nodes and designating each separate node and each separate phantom node in the plurality of analysis nodes with a node designation, where the each separate node and the each separate phantom node has a unique node designation;
generating a Graph representing the plurality of analysis nodes, where the Graph comprises a representation for each individual node comprising the quantity of n nodes, each individual phantom node comprising the quantity of m phantom nodes, every link weight for every communications link in the nodal network, and every phantom link weight; and
analyzing the Graph by performing steps comprising;
determining a Laplacian matrix Q describing the Graph and using the node designations;
finding an eigenvector matrix V using the Laplacian matrix Q, where the eigenvector matrix V is an (n+m) by (n+m) matrix comprising elements ν
il, where i is an eigenindex and where l is one of the node designations; and
determining node congestion by, identifying at least two nodal influencers by selecting at least a first eigenindex i(1) and a second eigenindex i(2), where i(1) is less than i(2), and performing steps comprising;
finding a primary influencer of the first eigenindex i(1) by inspecting the eigenvector matrix V and finding for the first eigenindex i(1) a maximum ν
i(1)lmax(1), where the maximum ν
i(1)lmax(1) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigenindex i is equal to the first eigenindex i(1), and designating the node corresponding to the node designation lmax(1) of the maximum ν
i(1)lmax(1) as the primary influencer of the first eigenindex i(1);
ascertaining a primary influencer of the second eigenindex i(2) by inspecting the eigenvector matrix V and finding for the second eigenindex i(2) a maximum ν
i(2)lmax(2), where the maximum ν
i(2)lmax(2) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigen index i is equal to the second eigenindex i(2), and designating the node corresponding to the node designation lmax(2) of the maximum ν
i(2)lmax(2) as the primary influencer of the second eigenindex i(2); and
identifying, if the primary influencer of the first eigenindex i(1) is one of the quantity of n nodes comprising the nodal network and the primary influencer of the second eigenindex i(2) is one of the one or more phantom nodes, the primary influencer of the first eigenindex i(1) as a congested node, thereby determining node congestion in the dynamic network.
2 Assignments
0 Petitions
Accused Products
Abstract
Determining flow rules in a software defined network (SDN) of a plurality of forwarding devices includes determining, by a controller device, a network adjacency matrix of the SDN, wherein the network adjacency matrix represents a topology of the SDN; placing, by the controller device, a phantom node in the network adjacency matrix, wherein the phantom node does not physically exist within the topology of the SDN and the phantom node is attached to a first node with maximum degree in the network adjacency matrix to create a phantom adjacency matrix, wherein the first node corresponds to a first forwarding device in the SDN; and determining, by the controller device, an adverse condition in the SDN using the phantom node, wherein the controller device is separate from the plurality of forwarding devices.
36 Citations
21 Claims
-
1. A system for determining node congestion in a dynamic network comprising:
-
a nodal network, where the nodal network comprises a quantity of n nodes, where every node comprising the quantity of n nodes comprises a forwarding device, and where the every node has a communications link to at least one other node comprising the quantity of n nodes, where the communications link has a maximum bandwidth XMAXIMUM; a programmable controller in data communication with each node comprising the quantity of n nodes, where the programmable controller is programmed to perform steps comprising; polling one or more nodes comprising the quantity of n nodes and determining a throughput XMEASURED for each communications link comprising the nodal network; defining a link weight for the each communications link using the XMAXIMUM for the each communications link and using the XMEASURED for the each communications link; creating one or more phantom nodes, where each phantom node does not physically exist within the nodal network, and where the one or more phantom nodes comprises a quantity of m phantom nodes, and where each phantom node is a representation of an additional node in the nodal network, by; devising a phantom link between the each phantom node and one of the nodes comprising the quantity of n nodes, thereby devising one or more phantom links; and assigning a phantom link weight for each phantom link in the one or more phantom links, thereby assigning one or more phantom link weights and creating the one or more phantom nodes; developing a plurality of analysis nodes where the plurality of analysis nodes comprises the quantity of n nodes and the quantity of m phantom nodes and designating each separate node and each separate phantom node in the plurality of analysis nodes with a node designation, where the each separate node and the each separate phantom node has a unique node designation; generating a Graph representing the plurality of analysis nodes, where the Graph comprises a representation for each individual node comprising the quantity of n nodes, each individual phantom node comprising the quantity of m phantom nodes, every link weight for every communications link in the nodal network, and every phantom link weight; and analyzing the Graph by performing steps comprising; determining a Laplacian matrix Q describing the Graph and using the node designations; finding an eigenvector matrix V using the Laplacian matrix Q, where the eigenvector matrix V is an (n+m) by (n+m) matrix comprising elements ν
il, where i is an eigenindex and where l is one of the node designations; anddetermining node congestion by, identifying at least two nodal influencers by selecting at least a first eigenindex i(1) and a second eigenindex i(2), where i(1) is less than i(2), and performing steps comprising; finding a primary influencer of the first eigenindex i(1) by inspecting the eigenvector matrix V and finding for the first eigenindex i(1) a maximum ν
i(1)lmax(1), where the maximum ν
i(1)lmax(1) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigenindex i is equal to the first eigenindex i(1), and designating the node corresponding to the node designation lmax(1) of the maximum ν
i(1)lmax(1) as the primary influencer of the first eigenindex i(1);ascertaining a primary influencer of the second eigenindex i(2) by inspecting the eigenvector matrix V and finding for the second eigenindex i(2) a maximum ν
i(2)lmax(2), where the maximum ν
i(2)lmax(2) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigen index i is equal to the second eigenindex i(2), and designating the node corresponding to the node designation lmax(2) of the maximum ν
i(2)lmax(2) as the primary influencer of the second eigenindex i(2); andidentifying, if the primary influencer of the first eigenindex i(1) is one of the quantity of n nodes comprising the nodal network and the primary influencer of the second eigenindex i(2) is one of the one or more phantom nodes, the primary influencer of the first eigenindex i(1) as a congested node, thereby determining node congestion in the dynamic network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A non-transitory program storage device readable by a programmable controller and tangibly embodying a program of instructions executable by the programmable controller to perform a method for determining node congestion in a software defined network (SDN) of a plurality of forwarding devices, the program of instructions directing the programmable controller to perform steps comprising:
-
polling one or more nodes comprising a nodal network, where the nodal network comprises a quantity of n nodes, where every node comprising the quantity of n nodes comprises a forwarding device, and where the every node has a communications link to at least one other node comprising the quantity of n nodes, where the communications link has a maximum bandwidth XMAXIMUM, and defining a link weight for each communications link in the nodal network by; determining a throughput XMEASURED for the each communications link comprising the nodal network; and defining a link weight for the each communications link using the XMAXIMUM for the each communications link and using the XMEASURED for the each communications link; creating one or more phantom nodes, where each phantom node does not physically exist within the nodal network, and where the one or more phantom nodes comprises a quantity of m phantom nodes, and where each phantom node is a representation of an additional node in the nodal network, by; devising a phantom link between the each phantom node and one of the nodes comprising the quantity of n nodes, thereby devising one or more phantom links; and assigning a phantom link weight for each phantom link in the one or more phantom links, thereby assigning one or more phantom link weights and creating the one or more phantom nodes; developing a plurality of analysis nodes where the plurality of analysis nodes comprises the quantity of n nodes and the quantity of m phantom nodes and designating each separate node and each separate phantom node in the plurality of analysis nodes with a node designation, where the each separate node and the each separate phantom node has a unique node designation; generating a Graph representing the plurality of analysis nodes, where the Graph comprises a representation for each individual node comprising the quantity of n nodes, each individual phantom node comprising the quantity of m phantom nodes, every link weight for every communications link in the nodal network, and every phantom link weight; and analyzing the Graph by performing steps comprising; determining a Laplacian matrix Q describing the Graph and using the node designations; finding an eigenvector matrix V using the Laplacian matrix Q, where the eigenvector matrix V is an (n+m) by (n+m) matrix comprising elements ν
il, where i is an eigenindex and where l is one of the node designations; anddetermining, node congestion by identifying at least two nodal influencers by selecting at least a first eigenindex i(1) and a second eigenindex i(2), where i(1) is less than i(2), and performing steps comprising; finding a primary influencer of the first eigenindex i(1) by inspecting the eigenvector matrix V and finding for the first eigenindex i(1) a maximum ν
i(1)lmax(1), where the maximum ν
i(1)lmax(1) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigen index i is equal to the first eigenindex i(1), and designating the node corresponding to the node designation lmax(1) of the maximum ν
i(1)lmax(1) as the primary influencer of the firsteigenindex i(1);ascertaining a primary influencer of the second eigenindex i(2) by inspecting the eigenvector matrix V and finding for the second eigenindex i(2) a maximum ν
i(2)lmax(2), where the maximum ν
i(2)lmax(2) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigen index i is equal to the second eigenindex i(2), and designating the node corresponding to the node designation lmax(2) of the maximum ν
i(2)lmax(2) as the primary influencer of the second eigenindex i(2); andidentifying, if the primary influencer of the first eigenindex i(1) is one of the quantity of n nodes comprising the nodal network and the primary influencer of the second eigenindex i(2) is one of the one or more phantom nodes, the primary influencer of the first eigenindex i(1) as a congested node, thereby determining node congestion. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A system for determining flow rules in a communications network comprising:
-
a nodal network comprising a quantity of n nodes, where every node comprising the quantity of n nodes comprises a forwarding device, and where the every node comprising the quantity of n nodes in the nodal network comprises a routing table, and where the every node has a communications link to at least one other node comprising the quantity of n nodes, where the communications link has a maximum bandwidth XMAXIMUM; a programmable controller in data communication with each node comprising the quantity of n nodes, where the programmable controller is programmed to perform steps comprising; I) polling one or more nodes comprising the quantity of n nodes and determining a throughput XMEASURED for each communications link comprising the nodal network; II) defining a link weight for the each communications link using the XMAXIMUM for the each communications link and using the XMEASURED for the each communications link; III) creating one or more phantom nodes, where the one or more phantom nodes comprises a quantity of m phantom nodes, and where each phantom node is a representation of an additional node in the nodal network, by; III)A) devising a phantom link between the each phantom node and one of the nodes comprising the quantity of n nodes, thereby devising one or more phantom links; and III)B) assigning a phantom link weight for each phantom link in the one or more phantom links, thereby assigning one or more phantom link weights and creating the one or more phantom nodes; IV) developing a plurality of analysis nodes where the plurality of analysis nodes comprises the quantity of n nodes and the quantity of m phantom nodes and designating each separate node and each separate phantom node in the plurality of analysis nodes with a node designation, where the each separate node and the each separate phantom node has a unique node designation; V) generating a Graph representing the plurality of analysis nodes, where the Graph comprises a representation for each individual node comprising the quantity of n nodes, each individual phantom node comprising the quantity of m phantom nodes, every link weight for every communications link in the nodal network, and every phantom link weight; and VI) analyzing the Graph by performing steps comprising; VI)A) determining a phantom adjacency matrix A using the Graph and using the node designations; VI)B) determining a degree matrix D using the Graph and using the node designations; and VI)C) determining a Laplacian matrix Q by subtracting the degree matrix D from the phantom adjacency matrix A; VI)D) finding an eigenvector matrix V using the Laplacian matrix Q, where the eigenvector matrix V is an (n+m) by (n+m) matrix comprising elements ν
il, where i is an eigenindex and where l is one of the node designations; andVI)E) determining node congestion by identifying at least two nodal influencers by selecting at least a first eigenindex i(1) and a second eigenindex i(2), where i(1) is less than i(2), and performing steps comprising; VI)E)1) finding a primary influencer of the first eigenindex i(1) by inspecting the eigenvector matrix V and finding for the first eigenindex i(1) a maximum ν
i(1)lmax(1), where the maximum ν
i(1)lmax(1) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigen index i is equal to the first eigenindex i(1), and designating the node corresponding to the node designation lmax(1) of ν
i(1)lmax(1) as the primary influencer of the first eigenindex i(1);VI)E)2) ascertaining a primary influencer of the second eigenindex i(2) by inspecting the eigenvector matrix V and finding for the second eigenindex i(2) a maximum ν
i(2)lmax(2), where the maximum ν
i(2)lmax(2) is an element ν
il of the eigenvector matrix V having a maximum magnitude among all elements ν
il of the eigenvector matrix V when the eigen index i is equal to the second eigenindex i(2), and designating the node corresponding to the node designation lmax(2) of ν
i(2)lmax(2) as the primary influencer of the second eigenindex i(2); andVI)E)3) identifying, if the primary influencer of the first eigenindex i(1) is one of the quantity of n nodes comprising the nodal network and the primary influencer of the second eigenindex i(2) is one of the one or more phantom nodes, the primary influencer of the first eigenindex i(1) as a congested node, thereby determining node congestion; VII) communicating a flow level routing instruction to at least one node comprising the nodal network based on the node congestion. - View Dependent Claims (18, 19, 20, 21)
-
Specification