Pyretic + Mininet: Using Dijkstra's Algorithm to find the shortest path

 

[Topology]

 

 

pyretic: myroute_dijkstra.py

from pyretic.lib.corelib import*

from pyretic.lib.std import *

from multiprocessing import Lock

from pyretic.lib.query import *

from collections import defaultdict

 

#switches

switches = []

 

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

myhost={}

 

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

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

 

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] = 9999

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

 

 

[Execution]

Open one terminal to generate a tree topology with level 2.

 

Open another terminal to run pyretic controller

 

h1 ping h4

ICMP requet

 

ICMP reply

 

 

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

Department of Computer Science and Information Engineering,

National Quemoy University, Kinmen, Taiwan.