Reduce the time of find a route

[Description]

  When a sender wants to send packets to a receiver, it will use the ARP protocol to get the MAC address of the receiver through ARP request packet. The ARP request packet uses broadcast to find the destined receiver. When the network size is large, it takes time. If want to reduce the time to send out the first IP packet, we can directly write the mapping of IP address and MAC address at the ARP table in the sender. Then the sender does not send out the ARP request packet. It will speed up our evaluation.

 

[Problem]

  We will create a 4 level tree structure and use dijkstra's algorithm to find a shortest path from h1 to h16. Then we will see how long it takes that ping works correctly.

 

When the icmp_seq=12, the ping works correctly. When the network becomes more complex, it will take more time.

 

Method: Directly write the mapping into the arp table

 

In the following, I will use a simple topology to show the idea.

 

[Topology]

h1---s1---s2---h2

 

[Mininet script: simple_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', mac='00:00:00:00:00:01', ip='10.0.0.1/24' )

    h2 = net.addHost( 'h2', mac='00:00:00:00:00:02', ip='10.0.0.2/24' )

    s1 = net.addSwitch('s1')

    s2 = net.addSwitch('s2')

    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(s2, h2, cls=TCLink, **linkBW)

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

   

    print "*** Starting network"

    net.build()

    c7.start()

    s1.start( [c7] )

    s2.start( [c7] )

    h1.cmd('arp -s 10.0.0.2 00:00:00:00:00:02')

    h2.cmd('arp -s 10.0.0.1 00:00:00:00:00:01')

    print "*** Running CLI"

    CLI( net )

 

    print "*** Stopping network"

    net.stop()

 

if __name__ == '__main__':

    setLogLevel( 'info' )

    topology()

 

[Pyretic: myroute_dijkstra2.py]

In order to make the new controller module works correctly, prepare one file to store the related information.

(file name: host_mac.txt) The first column is the host's MAC address, then the switch number this host connects to, and finally the port number in this connected switch

The first line means that host with MAC address (00:00:00:00:00:01) connects to switch 1 in the port 1.

The second line means that host with MAC address (00:00:00:00:00:02) connects to switch 2 in the port 1.

00:00:00:00:00:01 1 1

00:00:00:00:00:02 2 1

 

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] = 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 "In myroute()->",pkt['srcmac'], pkt['dstmac'], pkt['srcip'], pkt['dstip']

    if ( str(pkt['srcmac']) not in myhost.keys() ) or (str(pkt['dstmac']) not in myhost.keys()):

      return

 

    #if match(ethtype=IP_TYPE):

    #  print "ipv4 packet"

 

    p1 = get_path(myhost[str(pkt['srcmac'])][0], myhost[str(pkt['dstmac'])][0],myhost[str(pkt['srcmac'])][1], myhost[str(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()

 

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

  global myhost

  fin = open("/home/ubuntu/pyretic/pyretic/tutorial/host_mac.txt", "r")

  for line in fin:

    a=line.split()

    myhost[str(a[0])]=(int(a[1]), int(a[2]))

  fin.close()

  #print "myhost=", myhost

  #We don't need ARP packet, so we drop the ARP packets.

  return if_(match(ethtype=ARP_TYPE), drop, find_route())

   

def main():

  return ( find_switch() + arp_and_ip())

 

 

[Execution]

 

 

Dr. Chih-Heng Ke

Department of Computer Science and Information Engineering, National Quemoy University, Kinmen, Taiwan

Email: smallko@gmail.com