Pyretic+Mininet:  Yen's K-Shortest Paths Algorithm

[Topology]

http://csie.nqu.edu.tw/smallko/sdn/pyretic_asp.files/image003.gif

 

[Mininet Script: multiple_path2.py]

#!/usr/bin/python

 

from mininet.net import Mininet

from mininet.node import Controller, RemoteController, OVSKernelSwitch, OVSLegacyKernelSwitch, 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')

    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"

    net.addLink(s1, h1)

    net.addLink(s1, s2)

    net.addLink(s2, s3)

    net.addLink(s3, s4)

    net.addLink(s4, h2)

    net.addLink(s1, s5)

    net.addLink(s5, s6)

    net.addLink(s6, s4)

    net.addLink(s2, s6)

 

    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: yen_ksp.py]

from pyretic.lib.corelib import*

from pyretic.lib.std import *

from multiprocessing import Lock

from pyretic.lib.query import *

from collections import defaultdict

from operator import itemgetter

import random

import copy

 

#switches

switches = []

 

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

myhost={}

 

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

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

 

ip1 = IPAddr('10.0.0.1')

ip2 = IPAddr('10.0.0.2')

 

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 path(previous, node_start, node_end):

  r=[]

  p=node_end

  r.append(p)

  q=previous[p]

  while q is not None:

    if q == node_start:

      r.append(q)

      break

    p=q

    r.append(p)

    q=previous[p]

 

  r.reverse()

  if node_start==node_end:

    path=[node_start]

  else:

    path=r

  return r

 

def dijkstra(graph, node_start, node_end=None):

    distances = {}     

    previous = {}  

   

    for dpid in switches:

      distances[dpid] = float('Inf')

      previous[dpid] = None

 

    distances[node_start]=0

    Q=set(switches)

   

    while len(Q)>0:

      u = minimum_distance(distances, Q)

      Q.remove(u)  

  

      for p in switches:

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

          w = 1

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

            distances[p] = distances[u] + w

            previous[p] = u

 

    if node_end:

        return {'cost': distances[node_end],

                'path': path(previous, node_start, node_end)}

    else:

        return (distances, previous)

 

def yen_ksp(src,dst,first_port,final_port,max_k=2):

  print "YenKSP is called"

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

  adjacency2=defaultdict(lambda:defaultdict(lambda:None))

 

  distances, previous = dijkstra(adjacency,src)

  A = [{'cost': distances[dst],

          'path': path(previous, src, dst)}]

  B = []

  #print "distances=", distances

  #print  "previous=", previous

  #print "A=", A

 

  if not A[0]['path']: return A

 

  for k in range(1, max_k):

    adjacency2=copy.deepcopy(adjacency)

    #print "k=", k, " adjacency2=", adjacency2

    for i in range(0, len(A[-1]['path']) - 1):

      node_spur = A[-1]['path'][i]

      path_root = A[-1]['path'][:i+1]

      #print "node_spur=", node_spur, " path_root=", path_root

 

      for path_k in A:

        curr_path = path_k['path']

        #print "curr_path=", curr_path, " i=", i

        if len(curr_path) > i and path_root == curr_path[:i+1]:

          adjacency2[curr_path[i]][curr_path[i+1]]=None

          #print "link[", curr_path[i],"][", curr_path[i+1], "] is removed"

           

      path_spur = dijkstra(adjacency2, node_spur, dst)

      #print "path_spur=", path_spur

 

      if path_spur['path']:

        path_total = path_root[:-1] + path_spur['path']

        #print "path_total=", path_total

        dist_total = distances[node_spur] + path_spur['cost']

        #print "dist_total=", path_total

        potential_k = {'cost': dist_total, 'path': path_total}

        #print "potential_k=", potential_k

 

        if not (potential_k in B):

          B.append(potential_k)

          #print "B=", B

 

    if len(B):

      B = sorted(B, key=itemgetter('cost'))

      #print "after sorting, B=", B

      A.append(B[0])

      B.pop(0)

      #print "after poping out the first element, B=", B, " A=", A

    else:

      break

 

  tmp=[]

  print "YenKSP->"

  for path_k in A:

     selected_path = path_k['path']

     print selected_path

     tmp.append(selected_path)

 

  ChosenPath=random.choice(tmp)

  print "Chosen Path=", ChosenPath

  #Now add the ports

  r = []

  in_port = first_port

  for s1,s2 in zip(ChosenPath[:-1],ChosenPath[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))

  #print r

  return r

  

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

  print "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

    #print myhost[pkt['srcmac']][0], myhost[pkt['dstmac']][0]

    #if match(ethtype=IP_TYPE):

    #  print "ipv4 packet"

    if pkt['srcip']==ip1 and pkt['dstip']==ip2:

      # select 3 paths

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

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

  

    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'])

  

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]

 

H1 ping H2 (From the right hand of the following figure. We can see that there will be three paths for packets from h1 to h2, i.e. 1-5-6-4, 1-2-6-4, and 1-2-3-4.

The Chosen path is 1-2-6-4.)

 

[Reference]

1.  https://en.wikipedia.org/wiki/Yen%27s_algorithm

2. https://github.com/Pent00/YenKSP

 

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

Department of Computer Science and Information Engineering,

National Quemoy University, Kinmen, Taiwan.