×

Network monitoring method using phantom nodes

  • US 9,960,956 B1
  • Filed: 09/14/2015
  • Issued: 05/01/2018
  • Est. Priority Date: 10/15/2014
  • Status: Active Grant
First Claim
Patent Images

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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×