From d19fe739422afc739e2ec8429df13d7b6d69e215 Mon Sep 17 00:00:00 2001 From: Nicolas Goaziou Date: Sat, 11 Jun 2016 21:00:20 +0200 Subject: Implement network discovery algorithm * haircontrol/discovery.py (Discovery.compute_neighbourhood): New function. --- haircontrol/discovery.py | 125 +++++++++++++++++++++++++++++++++++++---------- 1 file changed, 99 insertions(+), 26 deletions(-) (limited to 'haircontrol/discovery.py') diff --git a/haircontrol/discovery.py b/haircontrol/discovery.py index 3180ace..70bdc6a 100644 --- a/haircontrol/discovery.py +++ b/haircontrol/discovery.py @@ -192,30 +192,103 @@ class Discovery: i.disconnect() def compute_neighbourhood(self): - print("**********compute_neighbourhood************") - # net.equipments[].ifaces[].mac_seen[i] - - # Fake algorithm - random_e = '172.16.0.254' - for (mgmt_ip,e) in self.net.equipments.items(): - for (ifname,i) in e.ifaces.items(): - last = None - for mac_seen in i.mac_seen: - last = mac_seen - if last and last in self.net.mac2ip: - random_e = self.net.mac2ip[last] - i.direct_neighbours.append(random_e) - -# for (mgmt_ip,e) in self.net.equipments.items(): -# print("%s (%s)"%(mgmt_ip,e.name)) -# for (ifname,i) in e.ifaces.items(): -# print("\t%s"%i.name) -# for mac_seen in i.mac_seen: -# print("\t\tseen %s"%mac_seen) -# for remote_mgmtip in i.direct_neighbours: -# e = self.net.equipments[remote_mgmtip] -# print("\t\tdirect_neighbour %s (%s)"%(remote_mgmtip, e.name)) - - - print("**********compute_neighbourhood************") + ### Configuration + + # GATEWAY_IP and GATEWAY_IFACE_NAME define information about + # the gateway, i.e., the center of the network. + # + # IGNORE_IP lists all IP that should not appear in the network + # representation. + gateway_ip = '172.16.0.254' + gateway_iface_name = 'eth1' + ignore_ip = ['172.16.0.253'] + + ### State variables + + # FIXME: mac2ip() method is incomplete so it sometimes fail + # finding the IP from the MAC of some interface. Meanwhile, we + # build our own database. + mac_to_ip = {} + for (ip, equipment) in self.net.equipments.items(): + for interface in equipment.ifaces.values(): + mac_to_ip[interface.mac] = ip + equipments = { ip: eq for ip, eq in self.net.equipments.items() + if (ip not in ignore_ip) and (ip != gateway_ip) } + outer_net = [] # IP belonging to external levels. + with_uplink = [] # IP already attached to an interface. + + ### Helper functions + + def is_outer_interface (interface): + # Return True when INTERFACE is looking towards leaves of + # the network. + return all(mac not in mac_to_ip or # Ignore unknown eq + mac_to_ip[mac] in outer_net + for mac in interface.mac_seen) + + def is_at_next_level (equipment): + # Return True when EQUIPMENT is adjacent to outer network. + # This happens when it doesn't belong to outer network and + # when all but one of its interfaces can only see MAC from + # outer network. Return False otherwise. Assume EQUIPMENT + # is not the gateway. + if equipment.mgmtip in outer_net: return False + exit_interface_flag = False + for interface in equipment.ifaces.values(): + if is_outer_interface(interface): continue + if exit_interface_flag: return False + exit_interface_flag = True + return True + + def set_uplink (ip, interface): + # Set IP as a direct neighbour of INTERFACE. Also signal + # that equipment relative to IP has a known uplink. + interface.direct_neighbours.append(ip) + with_uplink.append(ip) + + def link_to_outer_net (equipment): + # Link EQUIPMENT with outer network. Orphans in the + # outer network seen by an interface are linked to it. + for interface in equipment.ifaces.values(): + if is_outer_interface(interface): + for mac in interface.mac_seen: + if mac not in mac_to_ip: continue + ip = mac_to_ip[mac] + if ip not in with_uplink: + set_uplink(ip, interface) + + ### Main + + # Walk the the network from the outside, i.e., leaves, to the + # inside, i.e., the gateway, peeling the onion one layer at + # a time. + # + # We know that an equipment is the current level when all but + # one of its interfaces only see MAC from inferior levels (the + # interface left being attached to uplink). This assumes that + # all direct children of an equipment, at the very least, are + # seen by the equipment. Unknown equipment, i.e., a MAC that + # cannot be associated to an equipment in the network, is + # ignored altogether. + # + # Once an equipment is known to be at the current level, we + # attach it to the external network by linking every orphan + # there to the equipment interface seeing it, if any. + # + # At the end of the process, we do the same for the gateway. + # This requires a special step since there is no guarantee + # that gateway sees all of its direct neighbours. However, all + # orphans left in outer network are necessarily directly + # attached to it. + while equipments: + current_level = [] + for (ip, equipment) in equipments.items(): + if is_at_next_level(equipment): + link_to_outer_net(equipment) + current_level.append(equipment.mgmtip) + outer_net.extend(current_level) + for ip in current_level: del equipments[ip] + exit_iface = self.net.equipments[gateway_ip].ifaces[gateway_iface_name] + for ip in outer_net: + if ip not in with_uplink: set_uplink(ip, exit_iface) -- cgit v1.1