Available Bandwidth Based Dijkstra’s Algorithm

 

[Description]

   Some readers asked me how to write a dijkstra’s algorithm to find a path that has the biggest capacity to transmit the packets. Therefore, I will show some examples to show how I do it. But I leave some work for the algorithm. The algorithm is not stable. The controller will change to different paths.

 

[Topology]

 

 

Assumptions: The bandwidth for each link is 1Mbps. H1 will transmit pacts to H2. H3 will transmit packets to H4.

In this topology, there are different paths that can be chosen for packet transmission, e.g. s1-s2-s3-s4 or s1-s5-s6-s4.

 

[Mininet Script: test_bw.py]

#!/usr/bin/python

 

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, Intf

 

def topology():

    "Create a network."

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

    print "*** Creating nodes"

    h1 = net.addHost( 'h1')

    h2 = net.addHost( 'h2')

    h3 = net.addHost( 'h3')

    h4 = net.addHost( 'h4')  

    s1 = net.addSwitch('s1')

    s2 = net.addSwitch('s2')

    s3 = net.addSwitch('s3' )

    s4 = net.addSwitch('s4' )

    s5 = net.addSwitch('s5' )

    s6 = net.addSwitch('s6' )

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

 

    print "*** Creating links"

    linkopts0=dict(bw=1, delay='1ms', loss=0)

    net.addLink(s1, h1, **linkopts0)

    net.addLink(s1, s2, **linkopts0)

    net.addLink(s2, s3, **linkopts0)

    net.addLink(s3, s4, **linkopts0)

    net.addLink(s4, h2, **linkopts0)

    net.addLink(s1, s5, **linkopts0)

    net.addLink(s5, s6, **linkopts0)

    net.addLink(s6, s4, **linkopts0)

    net.addLink(s2, s6, **linkopts0)

    net.addLink(s1, h3, **linkopts0)    

    net.addLink(s4, h4, **linkopts0)

 

    print "*** Starting network"

    net.build()

    c7.start()

    s1.start( [c7] )

    s2.start( [c7] )

    s3.start( [c7] )

    s4.start( [c7] )

    s5.start( [c7] )

    s6.start( [c7] )

 

    print "*** Running CLI"

    CLI( net )

 

    print "*** Stopping network"

    net.stop()

 

if __name__ == '__main__':

    setLogLevel( 'info' )

    topology()

 

[Pyretic Controller version 1: dijkstra_bw1.py] (This version shows how to measure the bandwidth usage for each link)

from pyretic.lib.corelib import*

from pyretic.lib.std import *

from multiprocessing import Lock

from pyretic.lib.query import *

from collections import defaultdict

 

from datetime import datetime

import time

 

byte=defaultdict(lambda:defaultdict(lambda:None))

clock=defaultdict(lambda:defaultdict(lambda:None))

thr=defaultdict(lambda:defaultdict(lambda:None))

 

#switches

switches = []

 

#myhost[srcmac]->(switch, port)

myhost={}

 

#adjacency map [sw1][sw2]->port from sw1 to sw2

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

 

def byte_count_printer(n):

  #print n.items()

  if len(n)!=0:

    print "Now:", time.time()

    for i, j in n.items():

      #print "switch ", str(i).split(" ")[2][0], "port ", str(i).split(" ")[4][0], "j=", j

      for p in switches:

        for q in switches:

          if  str(i).split(" ")[2][0]== str(q) and str(adjacency[q][p])==str(i).split(" ")[4][0]:       

               if byte[p][q]>0:

                 thr[p][q] = (j - byte[p][q]) * 8.0 / (time.time()-clock[p][q])    

                 #the bandwidth usage for the link from switch p to switch q

                 print str(p),"->",str(q), ":", thr[p][q], "bps"

               byte[p][q]=j

               clock[p][q]=time.time()

      print " ----------------------------------------------------"

 

def measure_link():

  #every 3 seconds, we measure the incoming bytes for each port of the switch

  q = count_bytes(3, ['switch', 'inport'])

  q.register_callback(byte_count_printer)

  return q   

 

def minimum_distance(distance, Q):

  min = float('Inf')

  node = 0

  for v in Q:

    if distance[v] < min:

      min = distance[v]

      node = v

  return node

 

def get_path (src,dst,first_port,final_port):

  #Dijkstra's algorithm

  print "src=",src," dst=",dst, " first_port=", first_port, " final_port=", final_port

  distance = {}

  previous = {}

 

  for dpid in switches:

    distance[dpid] = float('Inf')

    previous[dpid] = None

 

  distance[src]=0

  Q=set(switches)

  

  while len(Q)>0:

    u = minimum_distance(distance, Q)

    Q.remove(u)

  

    for p in switches:

      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()

  if src==dst:

    path=[src]

  else:

    path=r

 

  # Now add the ports

  r = []

  in_port = first_port

  for s1,s2 in zip(path[:-1],path[1:]):

    out_port = adjacency[s1][s2]

    r.append((s1,in_port,out_port))

    in_port = adjacency[s2][s1]

  r.append((dst,in_port,final_port))

  return r

 

class find_route(DynamicPolicy):

  def __init__(self):

    super(find_route,self).__init__()

    self.flood = flood()

    self.set_initial_state()

 

  def set_initial_state(self):

    self.query = packets(1,['srcmac','dstmac', 'srcip', 'dstip'])

    self.query.register_callback(self.myroute)

    self.forward = self.flood

    self.update_policy()

 

  def set_network(self,network):

    self.set_initial_state()

 

  def update_policy(self):

    self.policy = self.forward + self.query

 

  def myroute(self,pkt):

    #print pkt['srcmac'], pkt['dstmac'], pkt['srcip'], pkt['dstip']

    if (pkt['srcmac'] not in myhost.keys()) or (pkt['dstmac'] not in myhost.keys()):

      return

 

    p1 = get_path(myhost[pkt['srcmac']][0], myhost[pkt['dstmac']][0],myhost[pkt['srcmac']][1], myhost[pkt['dstmac']][1])

    print p1

  

    r1 = parallel([(match(switch=a,srcip=pkt['srcip'],dstip=pkt['dstip']) >> fwd(c)) for a,b,c in p1])

    #print r1

  

    self.forward = if_(match(dstip=pkt['dstip'],srcip=pkt['srcip']),r1,self.forward)

    self.update_policy()

 

 

def find_host():

   q = packets(1,['srcmac','switch'])

   q.register_callback(mymac_learner)

   return q

 

def mymac_learner(pkt):

   print pkt['srcmac'], pkt['dstmac'], pkt['switch'], pkt['inport']

   #if match(ethtype=ARP_TYPE):

   # print "arp packet"

 

   if pkt['srcmac'] not in myhost.keys():

      myhost[pkt['srcmac']]=( pkt['switch'], pkt['inport'])

 

   #for a in myhost.keys():

   #  print a, myhost[a][0], myhost[a][1]

 

 

class find_switch(DynamicPolicy):

    def __init__(self):

        self.last_topology = None

        self.lock = Lock()

        super(find_switch,self).__init__()

 

    def set_network(self, network):

        with self.lock:

            for x in network.switch_list():

              switches.append(x)

            for (s1,s2,data) in network.topology.edges(data=True):

              adjacency[s1][s2]=data[s1]

              adjacency[s2][s1]=data[s2]

            self.last_topology = network.topology

         

 

def arp_and_ip():

  return if_(match(ethtype=ARP_TYPE), flood(), find_route())

       

def main():

  return ( find_switch() + find_host() + arp_and_ip() +  measure_link())

 

 

[demo]

 

In the following figure, we can see that when h1 ping h2. The packet path will be s1-s2-s3-s4 when the h1 sends out imcp requests. In [(1,1,2), (2,1,2),(3,1,2),(4,1,2)],

(1,1,2) means that the switch DPID is 1, input port is 1, and output port is 2. So [(1,1,2), (2,1,2),(3,1,2),(4,1,2)] means that the packets will go to s1 from input port 1 to output port2, then go to s2 from input port 1 to output 2, go to s3 from input port 1 to output port 2, and finally go to s4 from input port 1 to output port 2.

 

We also can see that the bandwidth usage for each link. For example, 1-2: 1192.34752835 bps means the link between s1 and s2 has consumed 1192 bps.

 

[Pyretic Controller version 2: dijkstra_bw2.py] (This version shows how to use dijkstra’s algorithm to find the path with the biggest capacity)

from pyretic.lib.corelib import*

from pyretic.lib.std import *

from multiprocessing import Lock

from pyretic.lib.query import *

from collections import defaultdict

 

from datetime import datetime

import time

 

byte=defaultdict(lambda:defaultdict(lambda:None))

clock=defaultdict(lambda:defaultdict(lambda:None))

thr=defaultdict(lambda:defaultdict(lambda:None))

 

#switches

switches = []

 

#myhost[srcmac]->(switch, port)

myhost={}

 

#adjacency map [sw1][sw2]->port from sw1 to sw2

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

 

def byte_count_printer(n):

  #print n.items()

  if len(n)!=0:

    #print "Now:", time.time()

    for i, j in n.items():

      #print "switch ", str(i).split(" ")[2][0], "port ", str(i).split(" ")[4][0], "j=", j

      for p in switches:

        for q in switches:

          if  str(i).split(" ")[2][0]== str(q) and str(adjacency[q][p])==str(i).split(" ")[4][0]:       

               if byte[p][q]>0:

                 thr[p][q] = (j - byte[p][q]) * 8.0 / (time.time()-clock[p][q])    

                 #the bandwidth usage for the link from switch p to switch q

                 #print str(p),"->",str(q), ":", thr[p][q], "bps"

               byte[p][q]=j

               clock[p][q]=time.time()

      #print " ----------------------------------------------------"

 

def measure_link():

  q = count_bytes(3, ['switch', 'inport'])

  q.register_callback(byte_count_printer)

  return q  

 

def minimum_distance(distance, Q):

  min = float('Inf')

  node = 0

  for v in Q:

    if distance[v] < min:

      min = distance[v]

      node = v

  return node

 

# The weight for each link depends on its bandwidth usage. In this example, we assume the bandwidth for every link is 1Mbps

# The higher bandwidth is consumed the higher the weight for the link is. So if we want to find a path that has the biggest capacity, we can use the algorithm to find the path with the minimum cost (the link with the least bandwidth consumed) from sender to receiver

def get_path2 (src,dst,first_port,final_port):

  #Dijkstra's algorithm

  print "2 src=",src," dst=",dst, " first_port=", first_port, " final_port=", final_port

  distance = {}

  previous = {}

 

  for dpid in switches:

    distance[dpid] = float('Inf')

    previous[dpid] = None

 

  distance[src]=0

  Q=set(switches)

  

  while len(Q)>0:

    u = minimum_distance(distance, Q)

    Q.remove(u)

  

    for p in switches:

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

        #print time.time(), u, "->", p, ":", thr[u][p]

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

          w = thr[u][p]

        else:

          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()

  if src==dst:

    path=[src]

  else:

    path=r

 

  # Now add the ports

  r = []

  in_port = first_port

  for s1,s2 in zip(path[:-1],path[1:]):

    out_port = adjacency[s1][s2]

    r.append((s1,in_port,out_port))

    in_port = adjacency[s2][s1]

  r.append((dst,in_port,final_port))

  return r

 

#the weight for each link is 1

def get_path (src,dst,first_port,final_port):

  #Dijkstra's algorithm

  print "1 src=",src," dst=",dst, " first_port=", first_port, " final_port=", final_port

  distance = {}

  previous = {}

 

  for dpid in switches:

    distance[dpid] = float('Inf')

    previous[dpid] = None

 

  distance[src]=0

  Q=set(switches)

  

  while len(Q)>0:

    u = minimum_distance(distance, Q)

    Q.remove(u)

  

    for p in switches:

      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()

  if src==dst:

    path=[src]

  else:

    path=r

 

  # Now add the ports

  r = []

  in_port = first_port

  for s1,s2 in zip(path[:-1],path[1:]):

    out_port = adjacency[s1][s2]

    r.append((s1,in_port,out_port))

    in_port = adjacency[s2][s1]

  r.append((dst,in_port,final_port))

  return r

 

class find_route(DynamicPolicy):

  def __init__(self):

    super(find_route,self).__init__()

    self.flood = flood()

    self.set_initial_state()

 

  def set_initial_state(self):

    self.query = packets(1,['srcmac','dstmac', 'srcip', 'dstip'])

    self.query.register_callback(self.myroute)

    self.forward = self.flood

    self.update_policy()

 

  def set_network(self,network):

    self.set_initial_state()

 

  def update_policy(self):

    self.policy = self.forward + self.query

 

  def myroute(self,pkt):

    #print pkt['srcmac'], pkt['dstmac'], pkt['srcip'], pkt['dstip']

    if (pkt['srcmac'] not in myhost.keys()) or (pkt['dstmac'] not in myhost.keys()):

      return

  

    #for 10.0.0.3-->10.0.0.4, we will find the path based on available bandwidth

    if (str(pkt['srcip'])=="10.0.0.3" and str(pkt['dstip'])=="10.0.0.4") or (str(pkt['srcip'])=="10.0.0.4" and str(pkt['dstip'])=="10.0.0.3"):

      p1 = get_path2(myhost[pkt['srcmac']][0], myhost[pkt['dstmac']][0],myhost[pkt['srcmac']][1], myhost[pkt['dstmac']][1])

    else:

      p1 = get_path(myhost[pkt['srcmac']][0], myhost[pkt['dstmac']][0],myhost[pkt['srcmac']][1], myhost[pkt['dstmac']][1])

    print p1

  

    r1 = parallel([(match(switch=a,srcip=pkt['srcip'],dstip=pkt['dstip']) >> fwd(c)) for a,b,c in p1])

    #print r1

  

    self.forward = if_(match(dstip=pkt['dstip'],srcip=pkt['srcip']),r1,self.forward)

    self.update_policy()

 

 

def find_host():

   q = packets(1,['srcmac','switch'])

   q.register_callback(mymac_learner)

   return q

 

def mymac_learner(pkt):

   print pkt['srcmac'], pkt['dstmac'], pkt['switch'], pkt['inport']

   #if match(ethtype=ARP_TYPE):

   # print "arp packet"

 

   if pkt['srcmac'] not in myhost.keys():

      myhost[pkt['srcmac']]=( pkt['switch'], pkt['inport'])

 

   #for a in myhost.keys():

   #  print a, myhost[a][0], myhost[a][1]

 

 

class find_switch(DynamicPolicy):

    def __init__(self):

        self.last_topology = None

        self.lock = Lock()

        super(find_switch,self).__init__()

 

    def set_network(self, network):

        with self.lock:

            for x in network.switch_list():

              switches.append(x)

            for (s1,s2,data) in network.topology.edges(data=True):

              adjacency[s1][s2]=data[s1]

              adjacency[s2][s1]=data[s2]

            self.last_topology = network.topology

         

 

def arp_and_ip():

  return if_(match(ethtype=ARP_TYPE), flood(), find_route())

       

def main():

  return ( find_switch() + find_host() + arp_and_ip() +  measure_link())

 

[Demo]

 

First, we use xterm to open a terminal for h1. Then h1 ping h2. After that, h3 ping h4. We can see from the following figure that the communication between h1 and h2 is via s1-s2-s3-s4 and s4-s3-s2-s1.

The communication between h3 and h4 is via s1-s5-s6-s4 and s4-s6-s6-s1. (Different transmission paths.) Note: When the communication path has been decided, this path won’t be changed.

 

[Pyretic Controller version 3: dijkstra_bw3.py] (This version shows how to use dijkstra’s algorithm to find the path with the biggest capacity every T seconds. The path will be changed according to the network condition)

from pyretic.lib.corelib import*

from pyretic.lib.std import *

from multiprocessing import Lock

from pyretic.lib.query import *

from collections import defaultdict

 

from datetime import datetime

import time

import threading

 

byte=defaultdict(lambda:defaultdict(lambda:None))

clock=defaultdict(lambda:defaultdict(lambda:None))

thr=defaultdict(lambda:defaultdict(lambda:None))

 

#switches

switches = []

 

#myhost[srcmac]->(switch, port)

myhost={}

 

#adjacency map [sw1][sw2]->port from sw1 to sw2

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

 

def byte_count_printer(n):

  #print n.items()

  if len(n)!=0:

    #print "Now:", time.time()

    for i, j in n.items():

      #print "switch ", str(i).split(" ")[2][0], "port ", str(i).split(" ")[4][0], "j=", j

      for p in switches:

        for q in switches:

          if  str(i).split(" ")[2][0]== str(q) and str(adjacency[q][p])==str(i).split(" ")[4][0]:       

               if byte[p][q]>0:

                 thr[p][q] = (j - byte[p][q]) * 8.0 / (time.time()-clock[p][q])    

                 #the bandwidth usage for the link from switch p to switch q

                 #print str(p),"->",str(q), ":", thr[p][q], "bps"

               byte[p][q]=j

               clock[p][q]=time.time()

      #print " ----------------------------------------------------"

 

def measure_link():

  q = count_bytes(1, ['switch', 'inport'])

  q.register_callback(byte_count_printer)

  return q  

 

def minimum_distance(distance, Q):

  min = float('Inf')

  node = 0

  for v in Q:

    if distance[v] < min:

      min = distance[v]

      node = v

  return node

 

# The weight for each link depends on its bandwidth usage. In this example, we assume the bandwidth for every link is 1Mbps

# The higher bandwidth is used, the higher the weight for the link is. So if we want to find a path that has the greatest bandwidth, we can use the algorithm to find the path with the minimun cost from sender to receiver

def get_path2 (src,dst,first_port,final_port):

  #Dijkstra's algorithm

  print "2 src=",src," dst=",dst, " first_port=", first_port, " final_port=", final_port

  distance = {}

  previous = {}

 

  for dpid in switches:

    distance[dpid] = float('Inf')

    previous[dpid] = None

 

  distance[src]=0

  Q=set(switches)

  

  while len(Q)>0:

    u = minimum_distance(distance, Q)

    Q.remove(u)

  

    for p in switches:

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

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

          w = thr[u][p]

        else:

          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()

  if src==dst:

    path=[src]

  else:

    path=r

 

  # Now add the ports

  r = []

  in_port = first_port

  for s1,s2 in zip(path[:-1],path[1:]):

    out_port = adjacency[s1][s2]

    r.append((s1,in_port,out_port))

    in_port = adjacency[s2][s1]

  r.append((dst,in_port,final_port))

  return r

 

#the weight for each link is 1

def get_path (src,dst,first_port,final_port):

  #Dijkstra's algorithm

  print "1 src=",src," dst=",dst, " first_port=", first_port, " final_port=", final_port

  distance = {}

  previous = {}

 

  for dpid in switches:

    distance[dpid] = float('Inf')

    previous[dpid] = None

 

  distance[src]=0

  Q=set(switches)

  

  while len(Q)>0:

    u = minimum_distance(distance, Q)

    Q.remove(u)

  

    for p in switches:

      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()

  if src==dst:

    path=[src]

  else:

    path=r

 

  # Now add the ports

  r = []

  in_port = first_port

  for s1,s2 in zip(path[:-1],path[1:]):

    out_port = adjacency[s1][s2]

    r.append((s1,in_port,out_port))

    in_port = adjacency[s2][s1]

  r.append((dst,in_port,final_port))

  return r

 

class find_route(DynamicPolicy):

  def __init__(self):

    super(find_route,self).__init__()

    self.flood = flood()

    self.set_initial_state()

 

  def handle_function(self, *args, **keywords):

    print time.time(), " handle_function is called"

    #for arg in args: print arg

    #for kw in keywords.keys(): print kw, ':', keywords[kw]

    p1=get_path2(keywords['a'], keywords['b'], keywords['c'], keywords['d'])    

    print "new path=", p1

    new_r = parallel([(match(switch=a,dstip=keywords['e'],srcip=keywords['f']) >> fwd(c))  for a,b,c in p1])

    self.forward = if_(match(dstip=keywords['e'],srcip=keywords['f']), new_r, self.forward)

    self.update_policy()

    self.thread = threading.Timer(3.0, self.handle_function, ["test"], {"a":keywords['a'], "b":keywords['b'], "c":keywords['c'], "d":keywords['d'], "e":keywords['e'], "f":keywords['f']})

    self.thread.start()

 

  def set_initial_state(self):

    self.query = packets(1,['srcmac','dstmac', 'srcip', 'dstip'])

    self.query.register_callback(self.myroute)

    self.forward = self.flood

    self.update_policy()

 

  def set_network(self,network):

    self.set_initial_state()

 

  def update_policy(self):

    self.policy = self.forward + self.query

 

  def myroute(self,pkt):

    #print pkt['srcmac'], pkt['dstmac'], pkt['srcip'], pkt['dstip']

    if (pkt['srcmac'] not in myhost.keys()) or (pkt['dstmac'] not in myhost.keys()):

      return

  

    if (str(pkt['srcip'])=="10.0.0.3" and str(pkt['dstip'])=="10.0.0.4") or (str(pkt['srcip'])=="10.0.0.4" and str(pkt['dstip'])=="10.0.0.3"):

      p1 = get_path2(myhost[pkt['srcmac']][0], myhost[pkt['dstmac']][0],myhost[pkt['srcmac']][1], myhost[pkt['dstmac']][1])

      self.thread = threading.Timer(3.0, self.handle_function, ["test"], {"a": myhost[pkt['srcmac']][0], "b": myhost[pkt['dstmac']][0], "c": myhost[pkt['srcmac']][1], "d": myhost[pkt['dstmac']][1], "e": pkt['dstip'], "f":pkt['srcip']})

      self.thread.start()

    else:     

      p1 = get_path(myhost[pkt['srcmac']][0], myhost[pkt['dstmac']][0],myhost[pkt['srcmac']][1], myhost[pkt['dstmac']][1])

    print p1

  

    r1 = parallel([(match(switch=a,srcip=pkt['srcip'],dstip=pkt['dstip']) >> fwd(c)) for a,b,c in p1])

    #print r1

  

    self.forward = if_(match(dstip=pkt['dstip'],srcip=pkt['srcip']),r1,self.forward)

    self.update_policy()

 

 

def find_host():

   q = packets(1,['srcmac','switch'])

   q.register_callback(mymac_learner)

   return q

 

def mymac_learner(pkt):

   print pkt['srcmac'], pkt['dstmac'], pkt['switch'], pkt['inport']

   #if match(ethtype=ARP_TYPE):

   # print "arp packet"

 

   if pkt['srcmac'] not in myhost.keys():

      myhost[pkt['srcmac']]=( pkt['switch'], pkt['inport'])

 

   #for a in myhost.keys():

   #  print a, myhost[a][0], myhost[a][1]

 

 

class find_switch(DynamicPolicy):

    def __init__(self):

        self.last_topology = None

        self.lock = Lock()

        super(find_switch,self).__init__()

 

    def set_network(self, network):

        with self.lock:

            for x in network.switch_list():

              switches.append(x)

            for (s1,s2,data) in network.topology.edges(data=True):

              adjacency[s1][s2]=data[s1]

              adjacency[s2][s1]=data[s2]

            self.last_topology = network.topology

         

 

def arp_and_ip():

  return if_(match(ethtype=ARP_TYPE), flood(), find_route())

       

def main():

  return ( find_switch() + find_host() + arp_and_ip() +  measure_link())

 

[Demo]

 

From the following figure, we can see that the communication between h3 and h4 will be via s1-s2-s3-s4 or s1-s5-s6-s4. This version is not stable. Because when the communication between h3 and s4 is via s1-s2-s3-s4. The controller will find that the s1-s5-s6-s4 has bigger capacity than s1-s2-s3-s4. So the controller will change the path to s1-s5-s6-s4. Likely, the path will be changed back to s1-s2-s3-s4 again. So how to design a stable version of algorithm will be your work. Think how to do it.

 

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

Department of Computer Science and Information Engineering,

National Quemoy University, Kinmen, Taiwan.