Pyretic + Mininet: Finding all shortest paths

[Topology]

[Mininet Script: multiple_path.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"

linkBW = {'bw':1}

net.addLink(s1, h1, cls=TCLink, **linkBW)

net.addLink(s1, s2, cls=TCLink, **linkBW)

net.addLink(s2, s3, cls=TCLink, **linkBW)

net.addLink(s3, s4, cls=TCLink, **linkBW)

net.addLink(s4, h2, cls=TCLink, **linkBW)

net.addLink(s1, s5, cls=TCLink, **linkBW)

net.addLink(s5, s6, cls=TCLink, **linkBW)

net.addLink(s6, s4, cls=TCLink, **linkBW)

net.addLink(s2, s6, cls=TCLink, **linkBW)

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

from pyretic.lib.corelib import*

from pyretic.lib.std import *

from multiprocessing import Lock

from pyretic.lib.query import *

from collections import defaultdict

import random

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

tmp_asp=set()

#list: save all the shortest paths for the path from ip1 to ip2

list_asp=[]

def get_dist(src):

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

return distance

def find_one_shortest_path(new_adjacency, now, dst, path_info):

if now == dst:

#print path_info

tmp_asp.add(tuple(path_info))

return

for p in switches:

if new_adjacency[now][p]!=None:

path_info.append(p)

find_one_shortest_path(new_adjacency, p, dst, path_info)

path_info.pop(-1)

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

print "all_shortest_paths() is called"

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

disS={} #shortest path from src

disT={}

disS = get_dist(src)

disT = get_dist(dst)

#print "disS=", disS

#print "disT=", disT

new_adjacency=defaultdict(lambda:defaultdict(lambda:None))

for p in switches:

for q in switches:

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

if (disS[p] + 1 + disT[q]) == disS[dst]:

new_adjacency[p][q] = adjacency[p][q]

#print new_adjacency

find_one_shortest_path(new_adjacency, src, dst, [])

tuple_asp=tuple(tmp_asp)

#print "tuple_asp=", tuple_asp

for i in range(len(tuple_asp)):

tmp = [src] + list(tuple_asp[i])

print tmp

# Now add the ports

r = []

in_port = first_port

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

list_asp.append(r)

#print "list_asp=", list_asp

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

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:

all_shortest_paths(myhost[pkt['srcmac']][0], myhost[pkt['dstmac']][0],myhost[pkt['srcmac']][1], myhost[pkt['dstmac']][1])

p1=random.choice(list_asp)

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 following figure. We can see that there will be three paths for packets from h1 to h2, i.e. 1-2-3-4, 1-5-6-4, and 1-2-6-4.

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

[Reference]

1. http://www.widecodes.com/0izqkPgPPe/python-dijkstra-k-shortest-paths.html

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

Department of Computer Science and Information Engineering,

National Quemoy University, Kinmen, Taiwan.