<commit_before>#!/usr/bin/python
# -*- coding: utf-8 -*-

'''
A POX module implementation of the CastFlow clean slate multicast proposal, with modifications to support
management of group state using an IGMP manager module.

Implementation adapted from NOX-Classic CastFlow implementation provided by caioviel.

Depends on openflow.igmp_manager

WARNING: This module is not complete, and should currently only be tested on loop free topologies

Created on July 16, 2013
@author: alexcraig
'''

from collections import defaultdict
from sets import Set
from heapq import heapify, heappop, heappush

# POX dependencies
from pox.openflow.discovery import Discovery
from pox.core import core
from pox.lib.revent import *
from pox.lib.util import dpid_to_str
import pox.lib.packet as pkt
from pox.lib.packet.igmp import *   # Required for various IGMP variable constants
from pox.lib.packet.ethernet import *
import pox.openflow.libopenflow_01 as of
from pox.lib.addresses import IPAddr, EthAddr
from pox.lib.recoco import Timer
import time

log = core.getLogger()

class MulticastPath:
    def __init__(self, src_ip, src_router_dpid, ingress_port, dst_mcast_address, groupflow_manager):
        self.src_ip = src_ip
        self.ingress_port = ingress_port
        self.src_router_dpid = src_router_dpid
        self.dst_mcast_address = dst_mcast_address
        self.mst = None
        self.weighted_topo_graph = []
        self.node_list = []                 # List of all managed router dpids
        self.installed_node_list = []       # List of all router dpids with rules currently installed
        self.receivers = []                 # Tuples of (router_dpid, port)
        self.groupflow_manager = groupflow_manager
        self.calc_mst()

        
    def calc_mst(self):
        self._calc_link_weights()
        nodes = self.node_list
        edges = self.weighted_topo_graph
        
        conn = defaultdict( list )
        for n1,n2,c in edges:
            conn[ n1 ].append( (c, n1, n2) )
            conn[ n2 ].append( (c, n2, n1) )
        mst = []
        used = set([self.src_router_dpid])
        usable_edges = conn[self.src_router_dpid][:]
        heapify( usable_edges )

        while usable_edges:

            cost, n1, n2 = heappop( usable_edges )
            if n2 not in used:
                used.add( n2 )
                mst.append( ( n1, n2, cost) )
                for e in conn[ n2 ]:
                    if e[ 2 ] not in used:
                        heappush( usable_edges, e )
        self.mst = mst
        
        log.debug('Calculated MST for source at router_dpid: ' + dpid_to_str(self.src_router_dpid))
        for edge in self.mst:
            log.debug(dpid_to_str(edge[0]) + ' -> ' + dpid_to_str(edge[1]))
    
    def _update_node_weight(self, node, curr_topo_graph, weighted_topo_graph, weight, prev_node = None):
        for edge in curr_topo_graph:
            if edge[0] == node:
                if edge[1] == prev_node:
                    # Don't bother trying to calculate a weight for the return link
                    continue;
                    
                updated_existing = False
                found_lower_weight = False
                for weighted_edge in weighted_topo_graph:
                    if weighted_edge[0] == node and weighted_edge[1] == edge[1] and weighted_edge[2] <= weight:
                        found_lower_weight = True
                        break
                    elif weighted_edge[0] == node and weighted_edge[1] == edge[1] and weighted_edge[2] > weight:
                        weighted_edge[2] = weight
                        updated_existing = True
                        break
                        
                if not updated_existing and not found_lower_weight:
                    weighted_topo_graph.append([edge[0], edge[1], weight])
                
                if not found_lower_weight:
                    weighted_topo_graph = self._update_node_weight(edge[1], curr_topo_graph, weighted_topo_graph, weight + 1, edge[0])
        
        return weighted_topo_graph
    
    def _calc_link_weights(self):
        curr_topo_graph = self.groupflow_manager.topology_graph
        self.node_list = list(self.groupflow_manager.node_set)
        self.weighted_topo_graph = self._update_node_weight(self.src_router_dpid, curr_topo_graph, [], 0)
        
        # log.debug('Calculated link weights for source at router_dpid: ' + dpid_to_str(self.src_router_dpid))
        # for edge in self.weighted_topo_graph:
        #     log.debug(dpid_to_str(edge[0]) + ' -> ' + dpid_to_str(edge[1]) + ' W: ' + str(edge[2]))
    
    def install_openflow_rules(self):
        reception_state = self.groupflow_manager.get_reception_state(self.dst_mcast_address, self.src_ip)
        outgoing_rules = defaultdict(lambda : None)
        
        # Calculate the paths for the specific receivers that are currently active from the previously
        # calculated mst
        edges_to_install = []
        calculated_path_router_dpids = []
        for receiver in reception_state:
            if receiver[0] in calculated_path_router_dpids:
                continue
            log.info('Building path for receiver on router: ' + dpid_to_str(receiver[0]))
            got_complete_path = False
            cur_node = receiver[0]
            while got_complete_path == False:
                edge_to_add = None
                min_weight = None
                for edge in self.mst:
                    if edge[1] == cur_node:
                        if min_weight is None:
                            edge_to_add = edge
                            min_weight = edge[2]
                        elif edge[2] < min_weight:
                            edge_to_add = edge
                            min_weight = edge[2]
                edges_to_install.append(edge_to_add)
                log.info('Added edge: ' + dpid_to_str(edge_to_add[0]) + ' -> ' + dpid_to_str(edge_to_add[1]))
                cur_node = edge_to_add[0]
                if cur_node == self.src_router_dpid:
                    got_complete_path = True
                    calculated_path_router_dpids.append(receiver[0])
                    
        # Get rid of duplicates in the edge list (must be a more efficient way to do this, find it eventually)
        edges_to_install = list(Set(edges_to_install))
        log.info('Installing edges:')
        log.info(edges_to_install)
                
        
        for edge in edges_to_install:
            if edge[0] in outgoing_rules:
                # Add the output action to an existing rule if it has already been generated
                output_port = self.groupflow_manager.adjacency[edge[0]][edge[1]]
                outgoing_rules[edge[0]].actions.append(of.ofp_action_output(port = output_port))
                log.info('ER: Configured router ' + dpid_to_str(edge[0]) + ' to forward group ' + \
                    str(self.dst_mcast_address) + ' to next router ' + \
                    dpid_to_str(edge[1]) + ' over port: ' + str(output_port))
            else:
                # Otherwise, generate a new flow mod
                msg = of.ofp_flow_mod()
                msg.match.dl_type = 0x800   # IPV4
                msg.match.nw_dst = self.dst_mcast_address
                msg.match.nw_src = self.src_ip
                output_port = self.groupflow_manager.adjacency[edge[0]][edge[1]]
                msg.actions.append(of.ofp_action_output(port = output_port))
                outgoing_rules[edge[0]] = msg
                log.info('NR: Configured router ' + dpid_to_str(edge[0]) + ' to forward group ' + \<commit_msg>Improved info printing for multicast edge installation.<commit_after>#!/usr/bin/python
# -*- coding: utf-8 -*-

'''
A POX module implementation of the CastFlow clean slate multicast proposal, with modifications to support
management of group state using an IGMP manager module.

Implementation adapted from NOX-Classic CastFlow implementation provided by caioviel.

Depends on openflow.igmp_manager

WARNING: This module is not complete, and should currently only be tested on loop free topologies

Created on July 16, 2013
@author: alexcraig
'''

from collections import defaultdict
from sets import Set
from heapq import heapify, heappop, heappush

# POX dependencies
from pox.openflow.discovery import Discovery
from pox.core import core
from pox.lib.revent import *
from pox.lib.util import dpid_to_str
import pox.lib.packet as pkt
from pox.lib.packet.igmp import *   # Required for various IGMP variable constants
from pox.lib.packet.ethernet import *
import pox.openflow.libopenflow_01 as of
from pox.lib.addresses import IPAddr, EthAddr
from pox.lib.recoco import Timer
import time

log = core.getLogger()

class MulticastPath:
    def __init__(self, src_ip, src_router_dpid, ingress_port, dst_mcast_address, groupflow_manager):
        self.src_ip = src_ip
        self.ingress_port = ingress_port
        self.src_router_dpid = src_router_dpid
        self.dst_mcast_address = dst_mcast_address
        self.mst = None
        self.weighted_topo_graph = []
        self.node_list = []                 # List of all managed router dpids
        self.installed_node_list = []       # List of all router dpids with rules currently installed
        self.receivers = []                 # Tuples of (router_dpid, port)
        self.groupflow_manager = groupflow_manager
        self.calc_mst()

        
    def calc_mst(self):
        self._calc_link_weights()
        nodes = self.node_list
        edges = self.weighted_topo_graph
        
        conn = defaultdict( list )
        for n1,n2,c in edges:
            conn[ n1 ].append( (c, n1, n2) )
            conn[ n2 ].append( (c, n2, n1) )
        mst = []
        used = set([self.src_router_dpid])
        usable_edges = conn[self.src_router_dpid][:]
        heapify( usable_edges )

        while usable_edges:

            cost, n1, n2 = heappop( usable_edges )
            if n2 not in used:
                used.add( n2 )
                mst.append( ( n1, n2, cost) )
                for e in conn[ n2 ]:
                    if e[ 2 ] not in used:
                        heappush( usable_edges, e )
        self.mst = mst
        
        log.debug('Calculated MST for source at router_dpid: ' + dpid_to_str(self.src_router_dpid))
        for edge in self.mst:
            log.debug(dpid_to_str(edge[0]) + ' -> ' + dpid_to_str(edge[1]))
    
    def _update_node_weight(self, node, curr_topo_graph, weighted_topo_graph, weight, prev_node = None):
        for edge in curr_topo_graph:
            if edge[0] == node:
                if edge[1] == prev_node:
                    # Don't bother trying to calculate a weight for the return link
                    continue;
                    
                updated_existing = False
                found_lower_weight = False
                for weighted_edge in weighted_topo_graph:
                    if weighted_edge[0] == node and weighted_edge[1] == edge[1] and weighted_edge[2] <= weight:
                        found_lower_weight = True
                        break
                    elif weighted_edge[0] == node and weighted_edge[1] == edge[1] and weighted_edge[2] > weight:
                        weighted_edge[2] = weight
                        updated_existing = True
                        break
                        
                if not updated_existing and not found_lower_weight:
                    weighted_topo_graph.append([edge[0], edge[1], weight])
                
                if not found_lower_weight:
                    weighted_topo_graph = self._update_node_weight(edge[1], curr_topo_graph, weighted_topo_graph, weight + 1, edge[0])
        
        return weighted_topo_graph
    
    def _calc_link_weights(self):
        curr_topo_graph = self.groupflow_manager.topology_graph
        self.node_list = list(self.groupflow_manager.node_set)
        self.weighted_topo_graph = self._update_node_weight(self.src_router_dpid, curr_topo_graph, [], 0)
        
        # log.debug('Calculated link weights for source at router_dpid: ' + dpid_to_str(self.src_router_dpid))
        # for edge in self.weighted_topo_graph:
        #     log.debug(dpid_to_str(edge[0]) + ' -> ' + dpid_to_str(edge[1]) + ' W: ' + str(edge[2]))
    
    def install_openflow_rules(self):
        reception_state = self.groupflow_manager.get_reception_state(self.dst_mcast_address, self.src_ip)
        outgoing_rules = defaultdict(lambda : None)
        
        # Calculate the paths for the specific receivers that are currently active from the previously
        # calculated mst
        edges_to_install = []
        calculated_path_router_dpids = []
        for receiver in reception_state:
            if receiver[0] in calculated_path_router_dpids:
                continue
            log.info('Building path for receiver on router: ' + dpid_to_str(receiver[0]))
            got_complete_path = False
            cur_node = receiver[0]
            while got_complete_path == False:
                edge_to_add = None
                min_weight = None
                for edge in self.mst:
                    if edge[1] == cur_node:
                        if min_weight is None:
                            edge_to_add = edge
                            min_weight = edge[2]
                        elif edge[2] < min_weight:
                            edge_to_add = edge
                            min_weight = edge[2]
                edges_to_install.append(edge_to_add)
                log.info('Added edge: ' + dpid_to_str(edge_to_add[0]) + ' -> ' + dpid_to_str(edge_to_add[1]))
                cur_node = edge_to_add[0]
                if cur_node == self.src_router_dpid:
                    got_complete_path = True
                    calculated_path_router_dpids.append(receiver[0])
                    
        # Get rid of duplicates in the edge list (must be a more efficient way to do this, find it eventually)
        edges_to_install = list(Set(edges_to_install))
        if not edges_to_install is None:
            log.info('Installing edges:')
            for edge in edges_to_install:
                log.info(dpid_to_str(edge[0]) + '->' + dpid_to_str(edge[1]) + ' (Weight: ' + str(edge[2]) + ')')
        
        for edge in edges_to_install:
            if edge[0] in outgoing_rules:
                # Add the output action to an existing rule if it has already been generated
                output_port = self.groupflow_manager.adjacency[edge[0]][edge[1]]
                outgoing_rules[edge[0]].actions.append(of.ofp_action_output(port = output_port))
                log.info('ER: Configured router ' + dpid_to_str(edge[0]) + ' to forward group ' + \
                    str(self.dst_mcast_address) + ' to next router ' + \
                    dpid_to_str(edge[1]) + ' over port: ' + str(output_port))
            else:
                # Otherwise, generate a new flow mod
                msg = of.ofp_flow_mod()
                msg.match.dl_type = 0x800   # IPV4
                msg.match.nw_dst = self.dst_mcast_address
                msg.match.nw_src = self.src_ip
                output_port = self.groupflow_manager.adjacency[edge[0]][edge[1]]
                msg.actions.append(of.ofp_action_output(port = output_port))
                outgoing_rules[edge[0]] = msg
                log.info('NR: Configured router ' + dpid_to_str(edge[0]) + ' to forward group ' + \
{'fraction_non_alphanumeric': 0.08118390508124838, 'fraction_numerical': 0.009607944286819705, 'mean_word_length': 1.9512844909609894, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1999150', 'n_tokens_mistral': 4714, 'n_tokens_neox': 4493, 'n_words': 1108}