Multi-Path Dijkstra Algorithm & ECMP (Equal Cost Multi-Path Routing)

[Description]

Based on this post, I implement the multi-path Dijkstra algorithm in pyretic controller. With this algorithm. Sender can transmit packets through different paths to the destination. The basic idea is that when original Dijkstra algorithm is used and (distance [u] + distance_between(u,v) ) < distance [v], we will set the distance[v] to distance [u] + distance_between(u,v) and the previous node of v is u. The modified version is to remember all the previous nodes of u when (distance [u] + distance_between(u,v) ) = distance [v]. Take the following figure as an example, in original Dijkstra algorithm, the previous node of r3 will be r2 or r4. Only one node will be remembered. But for the modified version, r2 and r4 will be both remembered. After calculation, if r2 is chosen for the previous node of r3, the path from h1 to h2 will be h1-r1-r2-r3-h2. If r4 is chosen, the path will be h1-r1-r4-r3-h2. So there will exists two paths with the same cost.

[pyretic controller: myroute_dijkstra_ecmp.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))

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

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

alt = distance[u] + w

if alt < distance[p]:

distance[p] = alt

if len(previous[p])!=0:

del previous[p][:]

previous[p].append(u)

elif alt == distance[p]:

previous[p].append(u)

r=[]

p=dst

r.append(p)

q=random.choice(previous[p])

while q is not None:

if q == src:

r.append(q)

break

p=q

r.append(p)

q=random.choice(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', 'protocol', 'ethtype', 'srcport', 'dstport'])

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'], pkt['protocol'], pkt['srcport'], pkt['dstport']

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"

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

print p1

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

#print p2

#print "srcport=", pkt['srcport']

#print "protocol=", pkt['protocol'], "ethtype=",pkt['ethtype']

if pkt['protocol']==1:

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)

else:

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

self.forward = if_(match(ethtype=pkt['ethtype'],dstip=pkt['dstip'],srcip=pkt['srcip'], protocol=pkt['protocol'], srcport=pkt['srcport'],dstport=pkt['dstport']),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())

[mininet script:test_ecmp1.py]

#!/usr/bin/python

from mininet.net import Mininet

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

print "*** Creating nodes"

h1 = net.addHost( 'h1')

h2 = net.addHost( 'h2')

SwitchList = []

# set n to different numbers, you can set that each path to contain n switches

n = 3

for x in range(1, n*2-2+1):

PREFIX="s"

SwitchList.append(net.addSwitch(PREFIX+str(x)))

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

print "*** Creating links"

linkBW = {'bw':10}

linkBW2 = {'bw':100}

net.addLink(h1, SwitchList[0], cls=TCLink, **linkBW2)

net.addLink(h2, SwitchList[n-1], cls=TCLink, **linkBW2)

for i in range(n*2-2):

if i==(n-1):

net.addLink(SwitchList[0], SwitchList[i+1], cls=TCLink, **linkBW)

elif i!=(n-1) and i!=(n*2-2-1):

net.addLink(SwitchList[i], SwitchList[i+1], cls=TCLink, **linkBW)

else:

net.addLink(SwitchList[i], SwitchList[n-1], cls=TCLink, **linkBW)

print "*** Starting network"

net.build()

c0.start()

for sw in SwitchList:

sw.start([c0])

#using the static arp, the hosts don't need to run arp protocol. Speed up the emulation.

#h1.cmd('arp -s '+ h2.IP()+' '+h2.MAC())

#h1.cmdPrint('arp -n')

#h2.cmd('arp -s '+h1.IP()+' '+h1.MAC())

#h2.cmdPrint('arp -n')

#print "*** Running CLI"

CLI( net )

print "*** Stopping network"

net.stop()

if __name__ == '__main__':

setLogLevel( 'info' )

topology()

[Execution]

Before running the script, we need to use iperf2. You can download iperf2 from here.

User xterm h1 h2 to open two terminals. (p.s. –P means number of parallel client threads to run)

From the following figure, we can see that there are two flows from h1 to h2. These two flows take different paths. The total throughput is around 19.1 Mbps.

If these two flows go the same paths, no more than 10Mbps can be obtained. Therefore, the performance is greatly improved.

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

Department of Computer Science and Information Engineering,

National Quemoy University, Kinmen, Taiwan.