Check for 'bad' or 'slow' nodes on paths using a metric for every path. Python + networkx.

test_bad_nodes_network.py

import networkx as nx
import matplotlib.pyplot as plt
import random
import numpy as np


def outliers_modified_z_score(ys):
    threshold = 1.5

    median_y = np.median(ys)
    median_absolute_deviation_y = np.median([np.abs(y - median_y) for y in ys])

    modified_z_scores = [0.6745 * (y - median_y) / median_absolute_deviation_y for y in ys]

    print "Using threshold:", threshold
    print "Z scores:", modified_z_scores

    return np.flatnonzero(np.array(modified_z_scores) > threshold)


def get_paths_with_retransmits(G, hosts_from, hosts_to, problematic_nodes, get_simple=False):
    
    generated_path_list = []

    for h1 in hosts_from:
        for h2 in hosts_to:
            if h1 == h2:
                continue

            if get_simple:
                all_paths = nx.all_simple_paths(G, h1, h2)
            else:
                all_paths = nx.all_shortest_paths(G, h1, h2)

            for path in all_paths:
                retransmits = random.randint(0, 2)
                if len(set(path).intersection(set(problematic_nodes))) > 0:
                    retransmits = random.randint(2, 6)

                generated_path_list.append({
                    'src': h1,
                    'dst': h2,
                    'path': path,
                    'retransmits': retransmits
                    })

    return generated_path_list


def get_problematic_nodes(event_list):
    numerator = dict()
    denominator = dict()
    for event in event_list:
        for node in event['path']:
            try:
                numerator[node] += event['retransmits']
                denominator[node] += 1
            except KeyError:
                numerator[node] = event['retransmits']
                denominator[node] = 1

    node_score = {node : numerator[node] / float(denominator[node]) for node in numerator.keys()}

    # natively sort tuples by first element
    d_view = [(v,k) for k,v in node_score.iteritems() ]
    d_view.sort(reverse=True) 

    min_v = min(node_score.values())
    max_v = max(node_score.values())

    print "Heuristic score for every node:"
    for v, k in d_view:
        print "Node:{}\tscore:{:.3f}\tnormalized:{:.3f}".format(k, v, (v - min_v)/float(max_v - min_v))
    print ""

    outliers = outliers_modified_z_score([v[0] for v in d_view])
    if len(outliers) > 0:
        print "\n**Critical outlier nodes:**"
        for i in outliers:
            print "Node:{}".format(d_view[i][1])
    else:
        print "No critical outliers were found"


def main():
    # Recreating graph in:
    # https://raw.githubusercontent.com/cwoodfield/hackathon71/master/hackathon_lab_diagram_asns.png
    edge_list = [
        ('host1', 'leaf1'),
        ('host2', 'leaf2'),
        ('leaf1', 'spine1'),
        ('leaf1', 'spine2'),
        ('leaf2', 'spine1'),
        ('leaf2', 'spine2'),
        ('spine1', 'vmx8'),
        ('spine1', 'vmx9'),
        ('spine2', 'vmx8'),
        ('spine2', 'vmx9'),
        ('vmx8', 'vmx7'),
        ('vmx9', 'vmx7'),
        ('spine3', 'vmx8'),
        ('spine3', 'vmx9'),
        ('spine4', 'vmx8'),
        ('spine4', 'vmx9'),
        ('leaf3', 'spine3'),
        ('leaf3', 'spine4'),
        ('leaf4', 'spine3'),
        ('leaf4', 'spine4'),
        ('host3', 'leaf3'),
        ('host4', 'leaf4'),
    ]

    # prepare graph
    G = nx.Graph()

    for e in edge_list:
        G.add_edge(*e)

    # define problematic nodes
    simulated_bad_nodes = ['vmx7']

    # hosts belonging to edge_list to generate the paths
    # those nodes will be used as 'src' and 'dst' to the paths
    hosts = ['host1', 'host2', 'host3', 'host4']

    # generate the paths. Paths that touches problematic nodes have more retransmits
    test_path_list = get_paths_with_retransmits(G, hosts, hosts, simulated_bad_nodes, get_simple=True)

    # print the nodes by problematic importance
    get_problematic_nodes(test_path_list)

if __name__ == "__main__":
    main()