Hi allI need to implement the larac algorithm (Lagrange Relaxation based
Aggregated Cost) in ryu controller but i have some problem can any one help me
to find the error ??you can see the attachment
thank you in advance
Wisam Maala
from datetime import datetime
from ryu.lib.revent.revent import EventMixin, Event
import ryu.lib.util as util
from ryu.core import core
import pox.openflow.libopenflow_01 as of
from collections import defaultdict
import ryu.lib.packet as pkt
from collections import namedtuple
log = core.getLogger()
switches = {}
switch_ports = {}
adj = defaultdict(lambda:defaultdict(lambda:None))
mac_learning = {}
class ofp_match_withHash(of.ofp_match):
##Our additions to enable indexing by match specifications
@classmethod
def from_ofp_match_Superclass(cls, other):
match = cls()
match.wildcards = other.wildcards
match.in_port = other.in_port
match.dl_src = other.dl_src
match.dl_dst = other.dl_dst
match.dl_vlan = other.dl_vlan
match.dl_vlan_pcp = other.dl_vlan_pcp
match.dl_type = other.dl_type
match.nw_tos = other.nw_tos
match.nw_proto = other.nw_proto
match.nw_src = other.nw_src
match.nw_dst = other.nw_dst
match.tp_src = other.tp_src
match.tp_dst = other.tp_dst
return match
def __hash__(self):
return hash((self.wildcards, self.in_port, self.dl_src, self.dl_dst, self.dl_vlan, self.dl_vlan_pcp, self.dl_type, self.nw_tos, self.nw_proto, self.nw_src, self.nw_dst, self.tp_src, self.tp_dst))
class Path(object):
def __init__(self, src, dst, prev, first_port):
self.src = src
self.dst = dst
self.prev = prev
self.first_port = first_port
def __repr__(self):
ret = util.dpid_to_str(self.dst)
u = self.prev[self.dst]
while(u != None):
ret = util.dpid_to_str(u) + "->" + ret
u = self.prev[u]
return ret
def _tuple_me(self):
list = [self.dst,]
u = self.prev[self.dst]
while u != None:
list.append(u)
u = self.prev[u]
#log.debug("List path: %s", list)
#log.debug("Tuple path: %s", tuple(list))
return tuple(list)
def __hash__(self):
return hash(self._tuple_me())
def __eq__(self, other):
return self._tuple_me() == other._tuple_me()
def _get_path(src, dst):
#Input format
a = [["00:00:00:00:00:01", "00:00:00:00:00:02", "00:00:00:00:00:03", "00:00:00:00:00:04", "00:00:00:00:00:05", "00:00:00:00:00:11", "00:00:00:00:00:22", "00:00:00:00:00:33", "00:00:00:00:00:44"]
,[None, (10,4,2,2), (2,1,3,1), None, (4,3,4,1), (1,1,0,1), None, None, None]
,[(10,4,2,2), None, None, (2,1,3,2), (4,3,4,2), None, (1,1,1,0), None, None]
,[(2,1,1,3), None, None, (6,4,2,1), None,None, None, None,None]
,[None, (2,1,2,3), (6,4,1,2), None, None, None, None, (1,1,3,0), None]
,[(4,3,1,4), (4,3,2,4), None, None, None,None,None,None, (1,1,3,0)]
,[(1,1,1,0), None,None,None,None,None,None,None,None]
,[None,(1,1,1,0), None,None,None,None,None,None,None]
,[None,None,None,(1,1,3,0),None,None,None,None,None]
,[None,None,None,None,(1,1,3,0),None,None,None,None]]
# src = 6
# dst = 7
graph = []
graph2 = []
portDictionary = {}
delayMatrix = [[0]*9 for i in range(9)]
costMatrix = [[0]*9 for i in range(9)]
# src = 6
# dst = 7
def makeGraph(costMatrix):
graph = []
for source, sourceList in enumerate(costMatrix, start=0):
for destination, cost in enumerate(sourceList, start=0):
if cost == 0:
continue
else:
graph.append((source+1, destination+1, cost))
return graph
def calculateCostDelay(previous, costMatrix, delayMatrix, source, dest):
totalDelay = 0
totalCost = 0
currentNode = dest
previousNode = previous[currentNode]
path = []
while currentNode is not None:
if currentNode == source:
path.insert(0,currentNode)
break
path.insert(0,currentNode)
totalDelay = totalDelay + delayMatrix[previousNode-1][currentNode-1]
totalCost = totalCost + costMatrix[previousNode-1][currentNode-1]
currentNode = previousNode
previousNode = previous[currentNode]
return totalCost, totalDelay, path
for source , element in enumerate(a):
for destination , node in enumerate(element):
if source is 0:
portDictionary[destination+1] = [node]
else:
if node is None:
continue
else:
graph.append((source, destination+1 , node[0]))
graph2.append((source, destination+1, node[1]))
delayMatrix[source-1][destination] = node[1]
costMatrix[source-1][destination] = node[0]
oldList = portDictionary[source]
oldList.append((portDictionary[destination+1][0] , node[2], node[3]))
portDictionary[source] = oldList
# print graph
# print graph2
# print costMatrix
# print delayMatrix
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')
class Graph():
def __init__(self, edges):
self.edges = edges2 = [Edge(*edge) for edge in edges]
self.vertices = set(sum(([e.start, e.end] for e in edges2), []))
return
def dijkstra(self, source, dest):
assert source in self.vertices
dist = {vertex: inf for vertex in self.vertices}
previous = {vertex: None for vertex in self.vertices}
dist[source] = 0
q = self.vertices.copy()
neighbours = {vertex: set() for vertex in self.vertices}
for start, end, cost in self.edges:
neighbours[start].add((end, cost))
while q:
u = min(q, key=lambda vertex: dist[vertex])
q.remove(u)
if dist[u] == inf or u == dest:
break
for v, cost in neighbours[u]:
alt = dist[u] + cost
if alt < dist[v]: # Relax (u,v,a)
dist[v] = alt
previous[v] = u
s = []
first_port = None
v = dest
u = previous[v]
while u is not None:
if u == source:
first_port = adj[u][v]
v = u
u = previous[v]
print previous
print source
print dest
return previous, first_port
print graph
graph = Graph(graph)
graph_list = graph
# graph2 = Graph(graph2)
costPrevious, cost_first_port = graph.dijkstra(src, dst)
costPath = []
totalDelayCost = 0
totalCostCost = 0
currentNode = dst
previousNode = costPrevious[currentNode]
while currentNode is not None:
if currentNode == src:
costPath.insert(0,currentNode)
break
costPath.insert(0,currentNode)
totalDelayCost = totalDelayCost + delayMatrix[previousNode-1][currentNode-1]
# print currentNode
# print previousNode
totalCostCost = totalCostCost + costMatrix[previousNode-1][currentNode-1]
currentNode = previousNode
previousNode = costPrevious[currentNode]
# print str(costPath) + " path"
# print str(totalDelayCost) + " delay in path"
# print str(totalCostCost) + " cost of path"
if totalDelayCost <= 100: #change this delay accordingly
#return path
print str(costPath) + " path"
print str(totalDelayCost) + " delay in path"
print str(totalCostCost) + " cost of path"
return Path(src,dst,costPrevious, cost_first_port)
else:
graph2 = Graph(graph2)
graph_list2 = graph2
delayPrevious, delay_first_port = graph2.dijkstra(src,dst)
delayPath = []
totalDelayDelay = 0
totalCostDelay = 0
currentNode = dst
previousNode = delayPrevious[currentNode]
while currentNode is not None:
if currentNode == src:
delayPath.insert(0,currentNode)
break
delayPath.insert(0,currentNode)
totalDelayDelay = totalDelayDelay + delayMatrix[previousNode-1][currentNode-1]
totalCostDelay = totalCostDelay + costMatrix[previousNode-1][currentNode-1]
currentNode = previousNode
previousNode = delayPrevious[currentNode]
# print str(delayPath) + " path"
# print str(totalDelayDelay) + " delay in path"
# print str(totalCostDelay) + " cost of path"
if totalDelayDelay > 6: #change this delay accordingly
print "No feasible solution"
return None
else:
changeCostMatrix = costMatrix
changeDelayMatrix = delayMatrix
changeCostCost = totalCostCost
changeCostDelay = totalCostDelay
changeDelayCost = totalDelayCost
changeDelayDelay = totalDelayDelay
changeCostPath = costPath
changeDelayPath = delayPath
changeCostPrevious = costPrevious
changeDelayPrevious = delayPrevious
while True:
change = (changeCostCost - changeCostDelay) / (changeDelayDelay - changeDelayCost)
for i in range(len(costMatrix)):
for j in range(len(costMatrix)):
changeCostMatrix[i][j] = costMatrix[i][j] + change * delayMatrix[i][j]
newGraph = Graph(makeGraph(changeCostMatrix))
newPrevious, new_first_port = newGraph.dijkstra(src,dst)
changeCost, changeDelay, changePath = calculateCostDelay(newPrevious, changeCostMatrix, delayMatrix, src,dst)
newCostCost, newDelayCost, newCostPath = calculateCostDelay(costPrevious, changeCostMatrix, delayMatrix, src,dst)
if changeCost == newCostCost:
print changePath
print changeCost
print changeDelay
return Path(src, dst, newPrevious, new_first_port)
elif changeDelay <= 6:
changeDelayPrevious = newPrevious
changeCostDelay, changeDelayDelay, changeDelayPath = calculateCostDelay(changeDelayPrevious, costMatrix, delayMatrix, src,dst)
else:
changeCostPrevious = newPrevious
changeCostCost, changeDelayCost, changeCostPath = calculateCostDelay(changeCostPrevious, costMatrix, delayMatrix, src,dst)
return None
def _install_path(prev_path, match):
dst_sw = prev_path.dst
cur_sw = prev_path.dst
dst_pck = match.dl_dst
msg = of.ofp_flow_mod()
msg.match = match
msg.idle_timeout = 10
msg.flags = of.OFPFF_SEND_FLOW_REM
msg.actions.append(of.ofp_action_output(port = mac_learning[dst_pck].port))
log.debug("Installing forward from switch %s to output port %s", util.dpid_to_str(cur_sw), mac_learning[dst_pck].port)
switches[dst_sw].connection.send(msg)
next_sw = cur_sw
cur_sw = prev_path.prev[next_sw]
while cur_sw is not None: #for switch in path.keys():
msg = of.ofp_flow_mod()
msg.match = match
msg.idle_timeout = 10
msg.flags = of.OFPFF_SEND_FLOW_REM
log.debug("Installing forward from switch %s to switch %s output port %s", util.dpid_to_str(cur_sw), util.dpid_to_str(next_sw), adj[cur_sw][next_sw])
msg.actions.append(of.ofp_action_output(port = adj[cur_sw][next_sw]))
switches[cur_sw].connection.send(msg)
next_sw = cur_sw
cur_sw = prev_path.prev[next_sw]
def _print_rev_path(dst_pck, src, dst, prev_path):
str = "Reverse path from %s to %s over: [%s->dst over port %s]" % (util.dpid_to_str(src), util.dpid_to_str(dst), util.dpid_to_str(dst), mac_learning[dst_pck].port)
next_sw = dst
cur_sw = prev_path[next_sw]
while cur_sw != None: #for switch in path.keys():
str += "[%s->%s over port %s]" % (util.dpid_to_str(cur_sw), util.dpid_to_str(next_sw), adj[cur_sw][next_sw])
next_sw = cur_sw
cur_sw = prev_path[next_sw]
log.debug(str)
class NewFlow(Event):
def __init__(self, prev_path, match, adj):
Event.__init__(self)
self.match = match
self.prev_path = prev_path
self.adj = adj
class Switch(EventMixin):
_eventMixin_events = set([
NewFlow,
])
def __init__(self, connection):
self.connection = connection
connection.addListeners(self)
for p in self.connection.ports.itervalues(): #Enable flooding on all ports until they are classified as links
self.enable_flooding(p.port_no)
def __repr__(self):
return util.dpid_to_str(self.connection.dpid)
def disable_flooding(self, port):
msg = of.ofp_port_mod(port_no = port,
hw_addr = self.connection.ports[port].hw_addr,
config = of.OFPPC_NO_FLOOD,
mask = of.OFPPC_NO_FLOOD)
self.connection.send(msg)
def enable_flooding(self, port):
msg = of.ofp_port_mod(port_no = port,
hw_addr = self.connection.ports[port].hw_addr,
config = 0, # opposite of of.OFPPC_NO_FLOOD,
mask = of.OFPPC_NO_FLOOD)
self.connection.send(msg)
def _handle_PacketIn(self, event):
def forward(port):
"""Tell the switch to forward the packet"""
msg = of.ofp_packet_out()
msg.actions.append(of.ofp_action_output(port = port))
if event.ofp.buffer_id is not None:
msg.buffer_id = event.ofp.buffer_id
else:
msg.data = event.ofp.data
msg.in_port = event.port
self.connection.send(msg)
def flood():
"""Tell all switches to flood the packet, remember that we disable inter-switch flooding at startup"""
#forward(of.OFPP_FLOOD)
for (dpid,switch) in switches.iteritems():
msg = of.ofp_packet_out()
if switch == self:
if event.ofp.buffer_id is not None:
msg.buffer_id = event.ofp.buffer_id
else:
msg.data = event.ofp.data
msg.in_port = event.port
else:
msg.data = event.ofp.data
ports = [p for p in switch.connection.ports if (dpid,p) not in switch_ports]
if len(ports) > 0:
for p in ports:
msg.actions.append(of.ofp_action_output(port = p))
switches[dpid].connection.send(msg)
def drop():
"""Tell the switch to drop the packet"""
if event.ofp.buffer_id is not None: #nothing to drop because the packet is not in the Switch buffer
msg = of.ofp_packet_out()
msg.buffer_id = event.ofp.buffer_id
event.ofp.buffer_id = None # Mark as dead, copied from James McCauley, not sure what it does but it does not work otherwise
msg.in_port = event.port
self.connection.send(msg)
#log.debug("Received PacketIn")
packet = event.parsed
SwitchPort = namedtuple('SwitchPoint', 'dpid port')
if (event.dpid,event.port) not in switch_ports: # only relearn locations if they arrived from non-interswitch links
mac_learning[packet.src] = SwitchPort(event.dpid, event.port) #relearn the location of the mac-address
if packet.effective_ethertype == packet.LLDP_TYPE:
drop()
log.debug("Switch %s dropped LLDP packet", self)
elif packet.dst.is_multicast:
flood()
#log.debug("Switch %s flooded multicast 0x%0.4X type packet", self, packet.effective_ethertype)
elif packet.dst not in mac_learning:
flood() #Let's first learn the location of the recipient before generating and installing any rules for this. We might flood this but that leads to further complications if half way the flood through the network the path has been learned.
log.debug("Switch %s flooded unicast 0x%0.4X type packet, due to unlearned MAC address", self, packet.effective_ethertype)
elif packet.effective_ethertype == packet.ARP_TYPE:
#These packets are sent so not-often that they don't deserve a flow
#Instead of flooding them, we drop it at the current switch and have it resend by the switch to which the recipient is connected.
#flood()
drop()
dst = mac_learning[packet.dst]
#print dst.dpid, dst.port
msg = of.ofp_packet_out()
msg.data = event.ofp.data
msg.actions.append(of.ofp_action_output(port = dst.port))
switches[dst.dpid].connection.send(msg)
log.debug("Switch %s processed unicast ARP (0x0806) packet, send to recipient by switch %s", self, util.dpid_to_str(dst.dpid))
else:
log.debug("Switch %s received PacketIn of type 0x%0.4X, received from %s.%s", self, packet.effective_ethertype, util.dpid_to_str(event.dpid), event.port)
dst = mac_learning[packet.dst]
prev_path = _get_path(self.connection.dpid, dst.dpid)
if prev_path is None:
flood()
return
log.debug("Path from %s to %s over path %s", packet.src, packet.dst, prev_path)
match = ofp_match_withHash.from_packet(packet)
_install_path(prev_path, match)
#forward the packet directly from the last switch, there is no need to have the packet run through the complete network.
drop()
dst = mac_learning[packet.dst]
msg = of.ofp_packet_out()
msg.data = event.ofp.data
msg.actions.append(of.ofp_action_output(port = dst.port))
switches[dst.dpid].connection.send(msg)
self.raiseEvent(NewFlow(prev_path, match, adj))
log.debug("Switch %s processed unicast 0x%0.4x type packet, send to recipient by switch %s", self, packet.effective_ethertype, util.dpid_to_str(dst.dpid))
def _handle_ConnectionDown(self, event):
log.debug("Switch %s going down", util.dpid_to_str(self.connection.dpid))
del switches[self.connection.dpid]
#pprint(switches)
class NewSwitch(Event):
def __init__(self, switch):
Event.__init__(self)
self.switch = switch
class Forwarding(EventMixin):
_core_name = "myforwarding"
_eventMixin_events = set([NewSwitch,])
def __init__ (self):
log.debug("Forwarding is initialized")
def startup():
core.openflow.addListeners(self)
core.openflow_discovery.addListeners(self)
log.debug("Forwarding started")
core.call_when_ready(startup, 'openflow', 'openflow_discovery')
def _handle_LinkEvent(self, event):
link = event.link
if event.added:
log.debug("Received LinkEvent, Link Added from %s to %s over port %d", util.dpid_to_str(link.dpid1), util.dpid_to_str(link.dpid2), link.port1)
adj[link.dpid1][link.dpid2] = link.port1
switch_ports[link.dpid1,link.port1] = link
else:
log.debug("Received LinkEvent, Link Removed from %s to %s over port %d", util.dpid_to_str(link.dpid1), util.dpid_to_str(link.dpid2), link.port1)
def _handle_ConnectionUp(self, event):
log.debug("New switch connection: %s", event.connection)
sw = Switch(event.connection)
switches[event.dpid] = sw;
self.raiseEvent(NewSwitch(sw))
def launch (postfix=datetime.now().strftime("%Y%m%d%H%M%S")):
from log.level import launch
launch(DEBUG=True)
from samples.pretty_log import launch
launch()
#from openflow.keepalive import launch
#launch(interval=15) # 15 seconds
from openflow.discovery import launch
launch()
core.registerNew(Forwarding)
------------------------------------------------------------------------------
_______________________________________________
Ryu-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/ryu-devel
