[ninux-research] [ninux-roma] Analisi fra correlazione di etx e RTT

Alessandro Gnagni alessandro at gnagni.it
Wed Jun 11 19:06:49 CEST 2014


Ok, essenzialmente io ho tutti dati divisi in 3 categorie:
- i ping sono uno per ogni test raggruppati nelle cartelle per
destinazione annidate in quelle per sorgente
- ho i traceroute ma per ora non li ho ancora utilizzati
- ho i file topologia di olsrd presi dal jsoninfo.

Ognuno di questi test viene eseguito e poi salvato ogni minuto, quindi
ho i file tutti "ammucchiati" nelle singole cartelle.

ecco lo script che lancio per ogni sorgente:

#!/bin/bash

# ./exec_scripts.sh ip_s

mkdir -p ../path_sum/$1/
mkdir -p ../ping/$1/
mkdir -p ../timestamp/$1/

for i in $(ls -d */ | grep -v -i "olsr" | rev | cut -c 2- | rev); do
 ../ping_sum_minimum_rtt.sh "$i/ping"  > ../ping/$1/"$1-$i.ping"

 ../path_cost.sh olsr $1 $i > ../path_sum/$1/"$1-$i.path_sum"

 ../timestamp_extract.sh ../path/$1 > ../timestamp/$1/"$1-$i.timestamp"
done


gli script che eseguo sono 3 per generare i dati per plottare:
ping_sum_minimum_rtt.sh

- uno mi genera i valori dei ping:
#!/bin/sh

for f in $1/*.log; do
EPOCH=$(cat $f | awk --re-interval '/^[0-9]{5,}/ {print $NF}')
pinglog="$pinglog$(cat $f | nawk -F'[ =]' -v e=$EPOCH '/64 bytes/
{s=$6+e; print s " " $10}')"
done

echo "$pinglog"  | awk 'BEGIN {min_timestamp=0; last_timestamp=0;
min_value=99999} {if ($1-last_timestamp > 30) {if (min_value != 99999)
{print min_timestamp, min_value}; min_value=$2; min_timestamp=$1}; if
($2 < min_value) {min_timestamp=$1; min_value=$2}; last_timestamp=$1}'


- uno il costo in etx sfruttando uno script in python:
ping_sum_minimum_rtt.sh

#!/bin/bash
# usage: path_compare.sh path/ source destination > ........

for f in $1/*.log; do
        echo -n "." 1>&2
        pathcost=$(python2.7 ./find_olsr4_path.py $f $2 $3 | awk
'function isnum(x){return(x==x+0)} {if (isnum($1)) {pathcost += $1}} END
{print pathcost}')
        echo "$(basename $f | cut -d "-" -f3 | cut -d "." -f1) $pathcost"
done


- il terzo mi dovrebbe generare dei timestamp quando viene rilevata una
variazione nei traceroute, ci sto ancora lavorando.


Ti ho allegato il file in python, è stato fatto da clauz.

Il 11/06/2014 17:08, Alessandro Gnagni ha scritto:
> Ecco, appena ho un attimo di tempo ti scrivo qualcosa.
> In questo momento sono un attimo impicciato a casa.
> 
> 
> Il 11/06/2014 16:39, Leonardo ha scritto:
>> On 06/11/2014 04:32 PM, Alessandro Gnagni wrote:
>>> Il 11/06/2014 16:30, Leonardo ha scritto:
>>>
>>>> ma figurati. se ti metti ora a fare lo stesso algorithmo in python,
>>>> senza averci mai programmato, tra mezz'ora hai finito. Un'ora tiè..  :-)
>>>>
>>>> poi però il tmepo lo riguadagni in esecuzione...
>>>>
>>>> ciao,
>>>> leonardo.
>>>>
>>>
>>> Non saprei neanche da dove cominciare. Python mi aiuterebbe anche perchè
>>> una parte dello script è in python, quello per il calcolo dell'etx
>>>
>>
>> se mi scrivi un algoritmo a parole ti aiuto... ci spostiamo su
>> ninux-research?
>>
> 

-------------- next part --------------
#!/usr/bin/env python2
# vim:ts=2:expandtab
#
#  Copyright 2013 Claudio Pisa (clauz at ninux dot org)
#
#  This file is part of find_olsr_path
#
#  find_olsr_path is free software: you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation, either version 3 of the License, or
#  (at your option) any later version.
#
#  find_olsr_path is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#
#  You should have received a copy of the GNU General Public License
#  along with find_olsr_path.  If not, see <http://www.gnu.org/licenses/>.
#


import networkx as nx
import urllib2
import sys
import json

verbose = False

def printout(string):
    if verbose:
        print string


class InvalidOlsrJsonException(Exception):
  pass


class oneWayLink():
  "a one-way OLSR link"
  def __init__(self, linkDict=None):
    if linkDict == None:
            return
    if not linkDict.has_key('destinationIP') or not linkDict.has_key('lastHopIP') or not linkDict.has_key('linkQuality') or not linkDict.has_key('neighborLinkQuality') or not linkDict.has_key('tcEdgeCost'):
      raise InvalidOlsrJsonException
    self.__dict__.update(linkDict)

  def __repr__(self):
    return repr(self.__dict__)

  def aliased_link(self, destination, lasthop):
    "return a copy of the link with changed IP addresses"
    a = oneWayLink()
    a.__dict__.update(self.__dict__)
    a.destinationIP = destination
    a.lastHopIP = lasthop
    return a

class Hna():
  "an OLSR HNA entry"
  def __init__(self, linkDict):
    if linkDict == None:
            return
    if not linkDict.has_key('destination') or not linkDict.has_key('genmask') or not linkDict.has_key('gateway'):
      raise InvalidOlsrJsonException
    self.__dict__.update(linkDict)

  def __repr__(self):
    return repr(self.__dict__)

  def __dotted_decimal_2_int(self, ip_address):
    dotteddecimals = ip_address.split('.')
    bip = 0
    for d in dotteddecimals:
        i = int(d)
        bip = bip << 8
        bip += i
    return bip

  def ip_in_net(self, ip_address):
    "return True iff ip_address belongs to this HNA"
    bip = self.__dotted_decimal_2_int(ip_address)
    bnet = self.__dotted_decimal_2_int(self.destination)
    l = self.genmask
    bmask = int("0b" + "1" * l + "0" * (32-l), 2)
    return bip & bmask == bnet


class OlsrTopology():
  "an OLSR topology"
  linklist = []
  addressset = set()
  aliasdict = {}
  hnalist = []

  def __init__(self, urlorfile):
    self.urlorfile = urlorfile
    self.update_topology()
    self.update_mids()
    self.update_hnas()
    self.update_gateways()

  def get_from_jsoninfo(self, urlappend):
    if self.urlorfile.startswith("http:"):
      # download 
      fno = urllib2.urlopen(self.urlorfile + urlappend, timeout=180)
    else:
      fno = open(self.urlorfile)
    json_topology = ("".join(fno.readlines())).strip()
    fno.close()
    
    # workaround for a bug in some versions of the jsoninfo plug-in
    if json_topology[0] != "{":
      json_topology = "{" + json_topology
    
    return json_topology
 
  def update_topology(self):
    json_topology = self.get_from_jsoninfo("/all")
    topolist = json.loads(json_topology)['topology']

    # check for asymmetric links
    tmplinklist = [oneWayLink(ld) for ld in topolist]
    self.linklist = []
    for link in tmplinklist:
      reverselinks = [lnk for lnk in tmplinklist if lnk.destinationIP == link.lastHopIP and lnk.lastHopIP == link.destinationIP]
      assert len(reverselinks) == 1
      self.linklist.append(link)

    # add ourselves to the graph
    mainaddr = json.loads(json_topology)['config']['mainIpAddress']
    directlinklist = json.loads(json_topology)['links']
    for dl in directlinklist:
        # direct link
        owl1 = oneWayLink()
        owl1.lastHopIP = mainaddr
        owl1.destinationIP = dl['remoteIP']
        owl1.linkQuality = dl['linkQuality']
        owl1.neighborLinkQuality = dl['neighborLinkQuality']
        owl1.tcEdgeCost = dl['linkCost']

        # reverse link
        owl2 = oneWayLink()
        owl2.lastHopIP = owl1.destinationIP
        owl2.destinationIP = owl1.lastHopIP
        owl2.linkQuality = owl1.neighborLinkQuality
        owl2.neighborLinkQuality = owl1.linkQuality
        owl2.tcEdgeCost = owl1.tcEdgeCost

        self.linklist.append(owl1)
        self.linklist.append(owl2)

    self.addressset = set([lnk.destinationIP for lnk in self.linklist] + [lnk.lastHopIP for link in self.linklist])

  def update_mids(self):
    json_mids = self.get_from_jsoninfo("/all")
    aliaslist = json.loads(json_mids)['mid']
    for aliasdef in aliaslist:
      self.aliasdict[aliasdef['ipAddress']] = [ alias['ipAddress'] for alias in aliasdef['aliases'] ]

    interfacelist = json.loads(json_mids)['interfaces']
    if len(interfacelist) < 2:
        return
    mainaddr = json.loads(json_mids)['config']['mainIpAddress']
    self.aliasdict[mainaddr] = []
    for interface in interfacelist:
        ipaddr = interface['ipv4Address']
        if mainaddr != ipaddr:
            self.aliasdict[mainaddr].append(ipaddr)

  def update_hnas(self):
    json_hnas = self.get_from_jsoninfo("/all")
    hnalist = json.loads(json_hnas)['hna']
    for hna in hnalist:
      self.hnalist.append(Hna(hna))

    localhnalist = json.loads(json_hnas)['config']['hna']
    for hna in localhnalist:
      self.hnalist.append(Hna(hna))

  def update_gateways(self):
    json_hnas = self.get_from_jsoninfo("/all")
    hnalist = json.loads(json_hnas)['hna']
    localhnalist = json.loads(json_hnas)['config']['hna']

    self.gatewaylist = [hna['gateway'] for hna in hnalist + localhnalist if hna['destination'] == "0.0.0.0"]

  def is_gateway(self, address):
    return address in self.gatewaylist

  def getAliases(self, addr):
    if self.aliasdict.has_key(addr):
      return self.aliasdict[addr]
    else:
      return []

  def getHnaGateway(self, addr):
    """if the IP address belongs to an HNA then return the IP address 
    of the node announcing the HNA. Else return addr."""
    gwresult = addr
    gwmask = 0
    for hna in self.hnalist:
      if hna.genmask > gwmask and hna.ip_in_net(addr):
        gwresult = hna.gateway
        mask = hna.genmask
    return gwresult

  def getMainAddress(self, addr):
    if self.aliasdict.has_key(addr):
      return addr
    for mainaddr, aliases in self.aliasdict.iteritems():
      for alias in aliases:
        if alias == addr:
          return mainaddr
    # assume it is a main address with no aliases (i.e. the only OLSR IP address of the node)
    return addr

  def __loadG(self, u_source, u_destination):
    self.G = nx.DiGraph()
    self.G.add_weighted_edges_from([(link.lastHopIP, link.destinationIP, 1 / (link.linkQuality * link.neighborLinkQuality)) for link in self.linklist])
    #G.add_weighted_edges_from([(link.lastHopIP, link.destinationIP, link.tcEdgeCost) for link in self.linklist])

    source = self.getMainAddress(u_source)
    if source == u_source:
      source = self.getHnaGateway(u_source)
      if source != u_source:
        printout( "Source %s is in an HNA. Using %s for path computation." % (u_source, source))
        self.G.add_weighted_edges_from([(u_source, source, 0)])
        source = u_source

    destination = self.getMainAddress(u_destination)
    if destination == u_destination:
      destination = self.getHnaGateway(u_destination)
      if destination != u_destination:
        printout( "Destination %s is in an HNA. Using %s for path computation." % (u_destination, destination))
        self.G.add_weighted_edges_from([(destination, u_destination, 0)])
        destination = u_destination

    return (source, destination)

  def get_etx(self, u_source, u_destination):
    source, destination = self.__loadG(u_source, u_destination)

    if source in self.G.nodes() and destination in self.G.nodes():
      return nx.dijkstra_path_length(self.G, source, destination)
    elif source in self.G.nodes():
      # find the closest gateway
      closestgw = None
      cost = 0
      for gw in self.gatewaylist:
        splen = nx.shortest_path_length(self.G, source, gw)
        if splen > cost:
          cost = splen
          closestgw = gw
      if closestgw:
        printout( "Warning: using gateway %s" % (closestgw,))
        return nx.dijkstra_path_length(self.G, source, closestgw)
      else:
        return 1.0
    else:
      return 1.0

  def get_shortest_path(self, u_source, u_destination):
    source, destination = self.__loadG(u_source, u_destination)

    if source in self.G.nodes() and destination in self.G.nodes():
      return nx.dijkstra_path(self.G, source, destination)
    elif source in self.G.nodes():
      # find the closest gateway
      closestgw = None
      cost = 0
      for gw in self.gatewaylist:
        splen = nx.shortest_path_length(self.G, source, gw)
        if splen > cost:
          cost = splen
          closestgw = gw
      if closestgw:
        printout( "Warning: using gateway %s" % (closestgw,))
        return nx.dijkstra_path(self.G, source, closestgw)
      else:
        return None
    else:
      return None


if __name__ == "__main__":
        if len(sys.argv) < 4:
                print "Usage: %s <url or file> <source> <destination>"
                sys.exit(1)
        urlorfile = sys.argv[1]
        src = sys.argv[2]
        dst = sys.argv[3]
        t = OlsrTopology(urlorfile)
        path = t.get_shortest_path(src, dst)
        if path == None or len(path) < 1:
                printout( "No path found. Please check the script parameters")
                sys.exit(2)
        previoushop = None
        for hop in path:
          if previoushop != None:
              print "%.3f\t" % t.get_etx(previoushop, hop),
          else:
              print "\t",

          print hop,
          aliases = t.getAliases(hop)
          if len(aliases) < 1:
            print ""
          else:
            print "\t (" + ", ".join(aliases) + ")"

          previoushop = hop




More information about the Research mailing list