Skip to main content
 首页 » 编程设计

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

2025年01月19日9thcjp

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

[ 
    {'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) 

请您参考如下方法:

我想你想通过观察到的路径数来标准化你的错误计数。将 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