Path Recovery when link is down

 

[Note]

        If you want to use this work, please cite the following paper.

Ali MalikBenjamin AzizChih-Heng KeHan Liu and Mo AddaVirtual Topology Partitioning Towards An Efficient Failure Recovery of Software Defined Networks.  In Proceedings of the 16th International Conference on Machine Learning and Cybernetics (ICMLC), Ningbo, China, July 2017

 

[Network Topology]

   The topology will be created. The source switch node is node 1 and the destination switch node is node 36. If the dijkstra algorithm is adopted for path finding, the path between 1 and 36 will be [1,2,3,13,15,17,34,36]. Two different path recovery methods will be given. The first one is re-find the path at the source node switch (alidijkstra.py). The second one is to red-find the path at the ingress switch node of failed link. For example, when link s13 and s15 is down and a packet researches s13, the second method will find another path from 13 to 15, i.e. total path is [1,2,3,13,12,14,15,17,34,36]. (Note the path 13,12,14,15 is newly found, and while other links along the path remain the same.)(alidijkstra2.py)

 

 

More closer look for the network topology.

 

[Scripts]

[ERnet.py ---- for generating network topology] (Note. We don’t want the arp operations to affect the performance evaluation. So I use the static ARP at the sender and the receiver)

#Created By Ali Malik

 

from mininet.net import Mininet

from mininet.node import Controller, RemoteController, OVSKernelSwitch, UserSwitch

from mininet.cli import CLI

from mininet.log import setLogLevel

from mininet.link import Link, TCLink

 

def topology():

        net = Mininet( controller=RemoteController, link=TCLink, switch=OVSKernelSwitch )

 

        # Add hosts and switches

        h1= net.addHost( 'h1', mac=

"00:00:00:00:00:01" )

        h2 = net.addHost( 'h2', mac=

"00:00:00:00:00:02" )

        S1 = net.addSwitch( 's1')

        S2 = net.addSwitch( 's2') 

        S3 = net.addSwitch( 's3') 

        S4 = net.addSwitch( 's4')

        S5 = net.addSwitch( 's5') 

        S6 = net.addSwitch( 's6') 

        S7 = net.addSwitch( 's7') 

        S8 = net.addSwitch( 's8') 

        S9 = net.addSwitch( 's9') 

        S10 = net.addSwitch( 's10')  

        S11 = net.addSwitch( 's11') 

        S12 = net.addSwitch( 's12') 

        S13 = net.addSwitch( 's13') 

        S14 = net.addSwitch( 's14') 

        S15 = net.addSwitch( 's15') 

        S16 = net.addSwitch( 's16') 

        S17 = net.addSwitch( 's17') 

        S18 = net.addSwitch( 's18') 

        S19 = net.addSwitch( 's19') 

        S20 = net.addSwitch( 's20') 

        S21 = net.addSwitch( 's21') 

        S22 = net.addSwitch( 's22') 

        S23 = net.addSwitch( 's23') 

        S24 = net.addSwitch( 's24') 

        S25 = net.addSwitch( 's25') 

        S26 = net.addSwitch( 's26') 

        S27 = net.addSwitch( 's27') 

        S28 = net.addSwitch( 's28') 

        S29 = net.addSwitch( 's29') 

        S30 = net.addSwitch( 's30') 

        S31 = net.addSwitch( 's31') 

        S32 = net.addSwitch( 's32') 

        S33 = net.addSwitch( 's33') 

        S34 = net.addSwitch( 's34') 

        S35 = net.addSwitch( 's35') 

        S36 = net.addSwitch( 's36')

        S37 = net.addSwitch( 's37') 

        c0 = net.addController( 'c0', controller=RemoteController, ip='127.0.0.1', port=6633 )

 

        # Add links

        #10

        net.addLink(h1, S1)  #s1 is the source switch

        net.addLink(h2, S36)  #s36 is the destination switch

 

        net.addLink( S1 , S2 )

        net.addLink( S1 , S5 )        

        net.addLink( S1 , S4 )

        net.addLink( S3 , S5 )

        net.addLink( S3 , S13 )

        net.addLink( S3 , S20 )

        net.addLink( S12 , S14 )

        net.addLink( S10 , S12 )

        net.addLink( S10 , S8 )

        net.addLink( S10 , S11 )

 

        #20

        net.addLink( S7 , S9 )

        net.addLink( S2 , S3 )

        net.addLink( S4 , S3 )

        net.addLink( S5 , S7 )

        net.addLink( S5 , S6 )

        net.addLink( S6 , S8 )

        net.addLink( S6 , S13 )

        net.addLink( S13 , S15 )

        net.addLink( S13 , S16 )

        net.addLink( S13 , S12 )

 

         #30

        net.addLink( S15 , S14 )

        net.addLink( S7 , S10 )

        net.addLink( S20 , S19 )

        net.addLink( S20 , S21 )

        net.addLink( S16 , S19 )

        net.addLink( S16 , S17 )

        net.addLink( S19 , S18 )

        net.addLink( S21 , S18 )

        net.addLink( S18 , S17 )

        net.addLink( S17 , S34 )

 

        #40

        net.addLink( S17 , S15 )

        net.addLink( S37 , S11 )

        net.addLink( S37 , S14 )

        net.addLink( S37 , S34 )

        net.addLink( S11 , S9 )

        net.addLink( S11 , S29 )

        net.addLink( S9 , S25 )

        net.addLink( S9 , S26 )

        net.addLink( S9 , S28 )

        net.addLink( S28 , S29 )

 

        #50

        net.addLink( S28 , S30 )

        net.addLink( S29 , S31 )

        net.addLink( S31 , S32 )

        net.addLink( S31 , S34 )

        net.addLink( S31 , S35 )

        net.addLink( S34 , S36 )

        net.addLink( S36 , S35 )

        net.addLink( S35 , S33 )

        net.addLink( S33 , S32 )

        net.addLink( S32 , S30 )

 

         #57

        net.addLink( S30 , S27 )

        net.addLink( S27 , S26 )

        net.addLink( S26 , S23 )

        net.addLink( S23 , S22 )

        net.addLink( S23 , S24 )

        net.addLink( S22 , S25 )

        net.addLink( S25 , S24 )

 

        net.build()

        c0.start()

        S1.start(  [c0] )

        S2.start(  [c0] )

        S3.start(  [c0] )

        S4.start(  [c0] )

        S5.start(  [c0] )

        S6.start(  [c0] )

        S7.start(  [c0] )

        S8.start(  [c0] )

        S9.start(  [c0] )

        S10.start(  [c0] )

        S11.start(  [c0] )

        S12.start(  [c0] )

        S13.start(  [c0] )

        S14.start(  [c0] )

        S15.start(  [c0] )

        S16.start(  [c0] )

        S17.start(  [c0] )

        S18.start(  [c0] )

        S19.start(  [c0] )

        S20.start(  [c0] )  

        S21.start(  [c0] )

        S22.start(  [c0] )

        S23.start(  [c0] )

        S24.start(  [c0] )

        S25.start(  [c0] )

        S26.start(  [c0] )

        S27.start(  [c0] )

        S28.start(  [c0] )

        S29.start(  [c0] )

        S30.start(  [c0] )  

        S31.start(  [c0] )

        S32.start(  [c0] )

        S33.start(  [c0] )

        S34.start(  [c0] )

        S35.start(  [c0] )

        S36.start(  [c0] )

        S37.start(  [c0] )

        h1.cmd("arp -s 10.0.0.2 00:00:00:00:00:02")

        h2.cmd("arp -s 10.0.0.1 00:00:00:00:00:01") 

        h1.cmd("tcpdump -i h1-eth0 -nn -X 'icmp' -w send &")

        h2.cmd("tcpdump -i h2-eth0 -nn -X 'icmp' -w receive &")

 

        print "*** Running CLI"

        CLI( net )

 

        print "*** Stopping network"

        net.stop()

       

if __name__ == '__main__':

    setLogLevel( 'info' )

    topology()

 

 

[GraphCliques.py—for plotting the network topology]

#Created By Ali Malik

 

from pox.core import core

import pox.openflow.libopenflow_01 as of

from pox.lib.revent import *

from pox.lib.recoco import Timer

from collections import defaultdict

from pox.openflow.discovery import Discovery

from pox.lib.util import dpid_to_str

import time

from matplotlib import pylab

from pylab import *

import igraph

from igraph import *

import numpy as np

import networkx as nx, igraph as ig

from random import randint

from collections import defaultdict

from itertools import tee, izip

 

#---------------------------------

 

class GraphCliques(EventMixin):

    G = nx.Graph()

 

    def __init__(self):

 

        def startup():

            core.openflow.addListeners(self, priority = 0)

            core.openflow_discovery.addListeners(self)

        core.call_when_ready(startup, ('openflow','openflow_discovery'))

        print "init completed"

 

    def _handle_LinkEvent(self, event):

 

        l = event.link

        sw1 = l.dpid1

        sw2 = l.dpid2

        pt1 = l.port1

        pt2 = l.port2

        self.G.add_node( sw1 )

        self.G.add_node( sw2 )

 

        if event.added:

            self.G.add_edge(sw1,sw2)

 

 

        if event.removed:

            try:

                self.G.remove_edge(sw1,sw2)

 

            except:

                print "remove edge error"

        try:

            #print nx.shortest_path(self.G,2,33)

 

             N= nx.number_of_nodes(self.G)

             print "Number of nodes", N            

             E= nx.number_of_edges(self.G)

             print "Number of Edges", E

 

             if (N == 37) and (E == 57):

 

                 print "Graph is ready now :-) "

                 print "Graph nodes are: ",self.G.nodes()

                 #nx.draw(self.G, with_labels=True)

                 #plt.show()

 

        except:

            print "no such complete Graph yet..."

    #---------------------------------------------------------

 

    #---------------------------------------------------------

    

    def pt(self, g, membership=None):

        if membership is not None:

                gcopy = g.copy()

                edges = []

                edges_colors = []

                for edge in g.es():

                    if membership[edge.tuple[0]] != membership[edge.tuple[1]]:

                        edges.append(edge)

                        edges_colors.append("gray")

                    else:

                        edges_colors.append("black")

                gcopy.delete_edges(edges)

                layout = gcopy.layout("kk")

                g.es["color"] = edges_colors

        else:

                layout = g.layout("kk")

                g.es["color"] = "gray"

                visual_style = {}

                visual_style["vertex_label_dist"] = 0

                visual_style["vertex_shape"] = "circle"

                visual_style["edge_color"] = g.es["color"]

                # visual_style["bbox"] = (4000, 2500)

                visual_style["vertex_size"] = 30

                visual_style["layout"] = layout

                visual_style["bbox"] = (1024, 768)

                visual_style["margin"] = 40

                

                for vertex in g.vs():

                 vertex["label"] = vertex.index

                if membership is not None:

                 colors = []

                 for i in range(0, max(membership)+1):

                    colors.append('%06X' % randint(0, 0xFFFFFF))

                 for vertex in g.vs():

                    vertex["color"] = str('#') + colors[membership[vertex.index]]

 

                 visual_style["vertex_color"] = g.vs["color"]

 

                igraph.plot(g, **visual_style)

                

 

    def graph(self):

 

        """

        Draws the Graph/Network switches ...

        """

        #---------------------------------------------------------

        N = self.G.nodes()

        d = defaultdict(list)

        E = self.G.number_of_edges()

        print "The number of Nodes in this Network:", N

        print "The number of Edges in this Network:", E

 

        fig = plt.figure()

        fig.canvas.set_window_title("The ERnet Topology View")

        nx.draw_networkx(self.G)

        plt.show()

        

        g = ig.Graph(len(self.G), zip(*zip(*nx.to_edgelist(self.G))[:2]))

        self.pt(g)

        cl = g.community_fastgreedy()

        #print cl

        membership = cl.as_clustering().membership

        print membership

        self.pt(g, membership)

        #print g.get_all_shortest_paths (2, 33)

        membership.pop(0)

        for q, a in zip(N, membership):

            print 'The Node {0} --> Belongs to cluster {1}.'.format(q, a)

 

        #The following procedure is to get the exact nodes of each cluster

        for i in range (max(membership)):

            i+=1

            for j in range (len(N)):

                if membership[j]==i:

                    d[i].append(N[j])

        print d.items()

        #Test the subgraphs correctness, which is the clusters

        fig = plt.figure()

        fig.canvas.set_window_title("Sub-Graph/Clique 1 of ERnet")

        G3 = self.G.subgraph(d[1])  #each index in dictionary "d" is considered as a one cluster/subgraph of G

        nx.draw_networkx(G3)

        plt.show()

 

        #---------------------------------------------------------

 

def launch():

    core.registerNew(GraphCliques)

 

 

 

[alidijkstra.py --- method 1 for path recovery]

from pox.core import core

import pox.openflow.libopenflow_01 as of

from pox.lib.revent import *

from pox.lib.recoco import Timer

from collections import defaultdict

from pox.openflow.discovery import Discovery

from pox.lib.util import dpid_to_str

import time

import copy

 

log = core.getLogger()

mac_map = {}

switches = {}

myswitches=[]

adjacency = defaultdict(lambda:defaultdict(lambda:None))

current_p=[]

 

def minimum_distance(distance, Q):

  #print "distance=", distance

  #print "Q=", Q

  min = float('Inf')

  node = 0

  for v in Q:

    if distance[v] < min:

      min = distance[v]

      node = v

  #print "min=", min, " node=", node

  return node

 

def _get_raw_path (src,dst):

  #Dijkstra algorithm

  print "src=",src," dst=", dst

  #print "myswitches=", myswitches

  distance = {}

  previous = {}      

  sws = myswitches

 

  for dpid in sws:

    distance[dpid] = float('Inf')

    previous[dpid] = None

 

  distance[src]=0

  Q=set(sws)

 

  while len(Q)>0:

    u = minimum_distance(distance, Q)

    #print "u=", u

    Q.remove(u)

  

    for p in sws:

      if adjacency[u][p]!=None:

        w = 1

        if distance[u] + w < distance[p]:

          distance[p] = distance[u] + w

          previous[p] = u

  r=[]

  p=dst

  r.append(p)

  q=previous[p]

  while q is not None:

    if q == src:

      r.append(q)

      break

    p=q

    r.append(p)

    q=previous[p]

 

  r.reverse() 

  return r

 

class Switch (EventMixin):

  def __init__ (self):

    self.connection = None

    self.ports = None

    self.dpid = None

    self._listeners = None

    self._connected_at = None

    mac_map[str("00:00:00:00:00:01")]=(1,1)

    mac_map[str("00:00:00:00:00:02")]=(36,1)

 

  def __repr__ (self):

    return dpid_to_str(self.dpid)

 

  def _install (self, in_port, out_port, match, buf = None):

    msg = of.ofp_flow_mod()

    msg.match = match

    msg.match.in_port = in_port

    msg.idle_timeout = 0

    msg.hard_timeout = 0

    msg.actions.append(of.ofp_action_output(port = out_port))

    msg.buffer_id = buf

    self.connection.send(msg)

 

  def _handle_PacketIn (self, event):

    global current_p

    print "_hanle_PacketIn() is called at", self.dpid

    packet = event.parsed

    print "packet.src=", str(packet.src), " packet.dst=", packet.dst

    if str(packet.src) !="00:00:00:00:00:01" and str(packet.src) !="00:00:00:00:00:02":

      return  

    #print "switches=", switches

    #print "adjacency=", adjacency

    path = _get_raw_path (mac_map[str(packet.src)][0], mac_map[str(packet.dst)][0])

    #if len(current_p)!=0 and current_p != path:

    #  del current_p[:]

    current_p=copy.deepcopy(path) 

    print "path=", path, "current_p=", current_p

    if mac_map[str(packet.dst)][0]!=self.dpid:

      next=path[path.index(self.dpid)+1]

      #print "next=", next

      output_port = adjacency[self.dpid][next]

      #print "output_port=", adjacency[self.dpid][next]

      match = of.ofp_match.from_packet(packet)

      self._install(event.port, output_port, match)

    else:

      output_port=mac_map[str(packet.dst)][1]

    msg = of.ofp_packet_out()

    msg.actions.append(of.ofp_action_output(port = output_port))

    msg.buffer_id = event.ofp.buffer_id

    msg.in_port = event.port

    self.connection.send(msg)

 

  def disconnect (self):

    if self.connection is not None:

      log.debug("Disconnect %s" % (self.connection,))

      self.connection.removeListeners(self._listeners)

      self.connection = None

      self._listeners = None

 

  def connect (self, connection):

    #print "type(conection.dpid)=", type(connection.dpid)

    if self.dpid is None:

      self.dpid = connection.dpid

    assert self.dpid == connection.dpid

    if self.ports is None:

      self.ports = connection.features.ports

    self.disconnect()

    log.debug("Connect %s" % (connection,))

    self.connection = connection

    self._listeners = self.listenTo(connection)

    self._connected_at = time.time()

 

  def _handle_ConnectionDown (self, event):

    self.disconnect()

 

class l2_multi (EventMixin):

  def __init__ (self):

    # Listen to dependencies

    def startup ():

      core.openflow.addListeners(self, priority=0)

      core.openflow_discovery.addListeners(self)

    core.call_when_ready(startup, ('openflow','openflow_discovery'))

 

  def _handle_ConnectionUp (self, event):

      sw = switches.get(event.dpid)

      if sw is None:

        # New switch

        sw = Switch()

        switches[event.dpid] = sw

        sw.connect(event.connection)

        myswitches.append(event.dpid)

      else:

        sw.connect(event.connection)

 

  def _handle_LinkEvent(self, event):

        global current_p

        l = event.link

        sw1 = l.dpid1

        sw2 = l.dpid2

        pt1 = l.port1

        pt2 = l.port2

 

        no_edges=0

        for p in myswitches:

          for q in myswitches:

             if adjacency[p][q]!=None:

               no_edges+=1

        print "number of edges=", (no_edges*0.5)        

        print "current_p=", current_p

  

        if len(myswitches)==37 and (no_edges*0.5) ==56:

           if event.removed:

              print sw1, "----", sw2, " is removed"

           clear = of.ofp_flow_mod(command=of.OFPFC_DELETE)

           for dpid in current_p:

             if switches[dpid].connection is None: continue

             switches[dpid].connection.send(clear)

 

        if event.added:

            #print "link is added"

            if adjacency[sw1][sw2] is None:

              adjacency[sw1][sw2] = l.port1

              adjacency[sw2][sw1] = l.port2  

 

        if event.removed:

            #print "link is removed"

            try:

                if sw2 in adjacency[sw1]: del adjacency[sw1][sw2]

                if sw1 in adjacency[sw2]: del adjacency[sw2][sw1]

 

            except:

                print "remove edge error"

       

def launch ():

  core.registerNew(l2_multi)

 

[alidijkstra2.py --- method 2 for path recovery]

from pox.core import core

import pox.openflow.libopenflow_01 as of

from pox.lib.revent import *

from pox.lib.recoco import Timer

from collections import defaultdict

from pox.openflow.discovery import Discovery

from pox.lib.util import dpid_to_str

import time

import copy

 

log = core.getLogger()

mac_map = {}

switches = {}

myswitches=[]

adjacency = defaultdict(lambda:defaultdict(lambda:None))

ori_adjacency = defaultdict(lambda:defaultdict(lambda:None))

current_p=[]

#grp1=[1,2,3,4,5]

#grp2=[6,7,8,9,10,11,12,13,14,37]

#grp3=[15,16,17,18,19,20,21]

#grp4=[22,23,24,25,26,27]

#grp5=[28,29,30,31,32,33,34,35,36]

link_fail=[]

 

def minimum_distance(distance, Q):

  #print "distance=", distance

  #print "Q=", Q

  min = float('Inf')

  node = 0

  for v in Q:

    if distance[v] < min:

      min = distance[v]

      node = v

  #print "min=", min, " node=", node

  return node

 

def _get_raw_path (src,dst,adj):

  #Dijkstra algorithm

  #print "src=",src," dst=", dst

  #print "myswitches=", myswitches

  distance = {}

  previous = {}      

  sws = myswitches

 

  for dpid in sws:

    distance[dpid] = float('Inf')

    previous[dpid] = None

 

  distance[src]=0

  Q=set(sws)

 

  while len(Q)>0:

    u = minimum_distance(distance, Q)

    #print "u=", u

    Q.remove(u)

  

    for p in sws:

      if adj[u][p]!=None:

        w = 1

        if distance[u] + w < distance[p]:

          distance[p] = distance[u] + w

          previous[p] = u

  r=[]

  p=dst

  r.append(p)

  q=previous[p]

  while q is not None:

    if q == src:

      r.append(q)

      break

    p=q

    r.append(p)

    q=previous[p]

 

  r.reverse() 

  return r

 

class Switch (EventMixin):

  def __init__ (self):

    self.connection = None

    self.ports = None

    self.dpid = None

    self._listeners = None

    self._connected_at = None

    mac_map[str("00:00:00:00:00:01")]=(1,1)

    mac_map[str("00:00:00:00:00:02")]=(36,1)

 

  def __repr__ (self):

    return dpid_to_str(self.dpid)

 

  def _install2 (self, in_port, out_port, match, dpid):

    msg = of.ofp_flow_mod()

    msg.match = match

    msg.match.in_port = in_port

    msg.idle_timeout = 0

    msg.hard_timeout = 0

    msg.actions.append(of.ofp_action_output(port = out_port))

    switches[dpid].connection.send(msg)

 

  def _install (self, in_port, out_port, match, buf = None):

    msg = of.ofp_flow_mod()

    msg.match = match

    msg.match.in_port = in_port

    msg.idle_timeout = 0

    msg.hard_timeout = 0

    msg.actions.append(of.ofp_action_output(port = out_port))

    msg.buffer_id = buf

    self.connection.send(msg)

 

  def _handle_PacketIn (self, event):

    global current_p, link_fail

    #print "_hanle_PacketIn() is called at", self.dpid

    packet = event.parsed

 

    #print "packet.src=", str(packet.src), " packet.dst=", packet.dst, " packet.type=", hex(packet.type)

    if str(packet.src) !="00:00:00:00:00:01" and str(packet.src) !="00:00:00:00:00:02":

      return  

    #print "switches=", switches

    #print "adjacency=", adjacency

    path = _get_raw_path (mac_map[str(packet.src)][0], mac_map[str(packet.dst)][0],adjacency)

    current_p=copy.deepcopy(path)  

    #print "path=", path, "current_p=", current_p, "link_fail=", link_fail

    if len(link_fail)!=0 and self.dpid in link_fail:

      #print "link_fail=", link_fail

      if self.dpid == link_fail[0]:

        p1=_get_raw_path(link_fail[0], link_fail[1],adjacency)

        p2=_get_raw_path (mac_map[str(packet.src)][0], mac_map[str(packet.dst)][0],ori_adjacency)

        print "p1=", p1, "p2=", p2

      else:

        p1=_get_raw_path(link_fail[1], link_fail[0],adjacency)

        p2=_get_raw_path (mac_map[str(packet.src)][0], mac_map[str(packet.dst)][0],ori_adjacency)

        print "p1=", p1, "p2=", p2

 

      indx=p2.index(p1[0])

      p1.remove(p1[0])

      #p1.remove(p1[len(p1)-1])

      j=1

      for i in p1:

          if j==len(p1):

            break

          p2.insert(indx+j,i)

          j+=1

      #print "final p2=", p2, " final p1=", p1

      path=p2

      j=1

      for i in p1:

        next=path[path.index(self.dpid)+j+1]

        #print "next=", next

        output_port = adjacency[i][next]

        input_port = adjacency[path[path.index(self.dpid)+j]][path[path.index(self.dpid)+j-1]]

        #print "path[path.index(self.dpid)+j]=",path[path.index(self.dpid)+j]

        #print "path[path.index(self.dpid)+j-1]=",path[path.index(self.dpid)+j-1]

        #print "output_port=", output_port

        #print "input_port=", input_port

        match = of.ofp_match.from_packet(packet)

        self._install2(input_port, output_port, match, i)

        j+=1

          

    if mac_map[str(packet.dst)][0]!=self.dpid:

      next=path[path.index(self.dpid)+1]

      #print "next=", next

      output_port = adjacency[self.dpid][next]

      #print "output_port=", adjacency[self.dpid][next]

      match = of.ofp_match.from_packet(packet)

      self._install(event.port, output_port, match)

    else:

      output_port=mac_map[str(packet.dst)][1]

    msg = of.ofp_packet_out()

    msg.actions.append(of.ofp_action_output(port = output_port))

    msg.buffer_id = event.ofp.buffer_id

    msg.in_port = event.port

    self.connection.send(msg)

 

  def disconnect (self):

    if self.connection is not None:

      log.debug("Disconnect %s" % (self.connection,))

      self.connection.removeListeners(self._listeners)

      self.connection = None

      self._listeners = None

 

  def connect (self, connection):

    #print "type(conection.dpid)=", type(connection.dpid)

    if self.dpid is None:

      self.dpid = connection.dpid

    assert self.dpid == connection.dpid

    if self.ports is None:

      self.ports = connection.features.ports

    self.disconnect()

    log.debug("Connect %s" % (connection,))

    self.connection = connection

    self._listeners = self.listenTo(connection)

    self._connected_at = time.time()

 

  def _handle_ConnectionDown (self, event):

    self.disconnect()

 

class l2_multi (EventMixin):

  def __init__ (self):

    # Listen to dependencies

    def startup ():

      core.openflow.addListeners(self, priority=0)

      core.openflow_discovery.addListeners(self)

    core.call_when_ready(startup, ('openflow','openflow_discovery'))

 

  def _handle_ConnectionUp (self, event):

      sw = switches.get(event.dpid)

      if sw is None:

        # New switch

        sw = Switch()

        switches[event.dpid] = sw

        sw.connect(event.connection)

        myswitches.append(event.dpid)

      else:

        sw.connect(event.connection)

 

  def _handle_LinkEvent(self, event):

        global current_p, link_fail

        l = event.link

        sw1 = l.dpid1

        sw2 = l.dpid2

        pt1 = l.port1

        pt2 = l.port2

 

        no_edges=0

        for p in myswitches:

          for q in myswitches:

             if adjacency[p][q]!=None:

               no_edges+=1

        print "number of edges=", (no_edges*0.5)        

        print "current_p=", current_p

  

        if len(myswitches)==37 and (no_edges*0.5) ==56:      

           if event.removed:

              print sw1, "----", sw2, " is removed"

              clear = of.ofp_flow_mod(command=of.OFPFC_DELETE)

              link_fail=[sw1,sw2]   

              for dpid in link_fail:

                if switches[dpid].connection is None: continue

                switches[dpid].connection.send(clear)

 

        if event.added:

            #print "link is added"

            if adjacency[sw1][sw2] is None:

              adjacency[sw1][sw2] = l.port1

              adjacency[sw2][sw1] = l.port2  

            if ori_adjacency[sw1][sw2] is None:

              ori_adjacency[sw1][sw2] = l.port1

              ori_adjacency[sw2][sw1] = l.port2  

 

        if event.removed:

            #print "link is removed"

            try:

                if sw2 in adjacency[sw1]: del adjacency[sw1][sw2]

                if sw1 in adjacency[sw2]: del adjacency[sw2][sw1]

 

            except:

                print "remove edge error"

       

def launch ():

  core.registerNew(l2_multi)

 

[Execution]

Open two terminals. In the first terminal. (the command is ./pox.py  openflow.discovery  GraphCliques  alidijkstra  py)

 

In the second terminal.

 

After executing “sudo python ERnet.py”, you can see similar messages. (37 nodes and 57 links)

 

In the first terminal, type “Enter” key and type the command “core.GraphCliques.graph()”. Then you can see the network topology.

 

When h1 ping h2, the first algorithm will find the path [1,2,3,13,15,17,34,36]. The packet that enters each switch along the path will trigger packet_in event and a rule will be setup for that switch.

 

When the link s13 and s15 is down.

 

h1 re-ping h2. The method one will re-find another path [1,2,13,16,17,34,36].

 

Type exit and then prepare to do post-processing.

 

[process_e2e_delay.sh --- measure the end to end delay]

#!/bin/bash

 

# Make sure only root can run our script

if [ "$(id -u)" != "0" ]; then

   echo "This script must be run as root" 1>&2

   exit 1

fi

 

tcpdump -r $1 | awk '{print $1}' > temp1

tcpdump -r $2 | awk '{print $1}' > temp2

 

declare -a Stime

index=0

#record 1: icmp request send time

#record 2: icmp response received time

#record 3: icmp request send time after link fails

#record 4: icmp response received time after link fails

while read -r line || [[ -n "$line" ]]; do

    #echo "Text read from file: $line"

    Stime[$index]="$line"

    index=`expr $index + 1`

done < temp1

 

declare -a Rtime

index=0

while read -r line || [[ -n "$line" ]]; do

    #echo "Text read from file: $line"

    Rtime[$index]="$line"

    index=`expr $index + 1`

done < temp2

 

for ((index=0; index<${#Stime[@]}; index++)); do

   echo "Stime[$index]: ${Stime[$index]}"

done

 

for ((index=0; index<${#Rtime[@]}; index++)); do

   echo "Rtime[$index]: ${Rtime[$index]}"

done

 

After evaluation, you can rule a simple script to do the analysis. send is the tcpdump result at h1 and receive is the tcpdump result at h2.

Stime[0] is the send time of the first icmp request and Rtime[0] is the receiving time of the first icmp request.

Stime[1] is the receiving time of the first icmp response and Rtime[1] is the sending time of the first icmp response.

Stime[2] is the send time of the second icmp request and Rtime[2] is the receiving time of the first second request. (after a link is down)

Stime[3] is the receiving time of the first icmp response and Rtime[2] is the sending time of the first icmp response.

End to End delay of the first icmp request is (12.567-12.366 = 0.201) seconds.

End to End delay of the first icmp response is (12.811-12.567=0.244) seconds.

End to End delay of the second icmp request is (02.704-02.486=0.218) seconds

End to End delay of the second icmp response is(02.914-02.705=0.209) seconds

 

 

(method 2)

The following steps are similar with method 1.

 

End to End delay of the first icmp request is (02.075-01.899 = 0.176) seconds.

End to End delay of the first icmp response is (02.209-02.075=0.134) seconds.

End to End delay of the second icmp request is (38.517-38.478=0.039) seconds

End to End delay of the second icmp response is(38.579-38.517=0.062) seconds

 

From the above experimental results, we can see that the method 2 is better than method 1.

 

Dr. Chih-Heng Ke (smallko@gmail.com)

Department of Computer Science and Information Engineering,

National Quemoy University, Kinmen, Taiwan.