python - 使用具有权重的路径列表检测网络上有问题的节点

Question

我正在尝试检测网络中有问题/速度较慢的节点，为此，我有一个节点之间的路径列表，以及将消息发送到目的地所花费的错误或重传次数。例如:

[
    {'path':['a', 'c', 'e', 'z'], 'errors': 0},
    ...
    {'path':['a', 'b', 'd', 'z'], 'errors': 4},
    {'path':['a', 'c', 'd', 'z'], 'errors': 4},
    ...
    {'path':['a', 'b', 'e', 'z'], 'errors': 0}
]

理论上，我有节点之间所有可能的路径和它们各自的延迟。因此，使用这些数据，我想检测“有问题的节点”。在前面的示例中，有几条路径，但所有通过 d 节点的路径都会有更多延迟，因此必须将此节点(以及其他类似的节点)查明为有问题。

有没有已知的算法可以解决这个问题？

我天真的方法是为每条路径使用错误计数器，并将这些计数器添加到路径上的每个节点，然后在处理完所有路径/节点后，将错误计数器除以该节点的邻居数。但这并没有给我一个好的结果，显示不同的节点有问题。

代码示例:

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


def get_problematic_nodes(path_list):
    node_connections = {}
    node_counter_dict = {}
    for e in path_list:
        value = 0
        if e['retransmits'] > 1:
            value = 1

        path_len = len(e['path'])
        for i in xrange(path_len):
            node = e['path'][i]
            if node not in node_counter_dict:
                node_counter_dict[node] = value
            else:
                node_counter_dict[node] += value

            if node not in node_connections:
                node_connections[node] = set()

            # previous node
            if i - 1 >= 0:
                node_connections[node].add(e['path'][i - 1])

            # next node
            if i + 1 <= path_len - 1:
                node_connections[node].add(e['path'][i + 1])

    nodes_score = {}

    print "Link size for every node:"
    for k, v in node_connections.items():
        link_number = len(v)
        print "Node: {} links:{}".format(k, link_number)
        nodes_score[k] = node_counter_dict[k]/link_number

    print "\nHeuristic score for every node:"
    for k,v in nodes_score.items():
        print "Node: {} score:{}".format(k, v)

    max_score_node_key = max(node_counter_dict.iterkeys(), key=(lambda key: node_counter_dict[key]/len(node_connections[key]) ))
    print "\nMax scored node: {}".format(max_score_node_key)

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
test_problem_nodes = ['spine3']

# generate the paths. Paths that touches problematic nodes have more retransmits
test_path_list = []
hosts = ['host1', 'host2', 'host3', 'host4']
for h1 in hosts:
    for h2 in hosts:
        if h1 == h2:
            continue

        all_paths = nx.all_simple_paths(G, h1, h2)
        for path in all_paths:
            retransmits = 0
            if len(set(path).intersection(set(test_problem_nodes))) > 0:
                retransmits = 10

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

# nx.draw(G, with_labels=True)
# plt.draw()
# plt.show()

get_problematic_nodes(test_path_list)

Answer 1

我想你想通过观察到的路径数来标准化你的错误计数。将 get_problematic_nodes 更改为

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] / denominator[node] for node in numerator.keys()}

    print "\nHeuristic score for every node:"
    for k,v in node_score.items():
        print "Node: {} score:{}".format(k, v)

    max_score = None
    for k,v in node_score.items():
        if v > max_score:
            max_score_node_key = k
            max_score = v
    print "\nMax scored node: {}".format(max_score_node_key)

产量:

Heuristic score for every node:
Node: vmx9 score:8
Node: vmx8 score:8
Node: host1 score:7
Node: vmx7 score:7
Node: spine1 score:7
Node: leaf4 score:8
Node: spine3 score:10
Node: spine2 score:7
Node: leaf1 score:7
Node: spine4 score:7
Node: leaf3 score:8
Node: leaf2 score:7
Node: host3 score:8
Node: host4 score:8
Node: host2 score:7

Max scored node: spine3