Network monitoring method using phantom nodes

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;
• 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 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);
• 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.

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;
• and
• VI)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);
• and
• VI)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.