Path Discovery Mechanism/Analysis

From OLPC

< Path Discovery Mechanism
Revision as of 02:07, 2 September 2009 by FGrose (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Contents

This page is dedicated to the PDM-analysis tool, a small python script that takes a pcap file as input and outputs statistics on the Path Discovery Mechanism.

The PDM-analysis tool

Requirements

  • The PDM-analysis tool requires the stats.py module (which requires the pstat.py module).
  • You also need wireshark on the box (the script uses tshark to decode the file). If you want to decode mesh frames you will need the mesh patch. No other dependencies.

Download

Download the current version here

Usage

Just make the script executable and fire it:

./PDM-Analysis.py -f <pcap_file> [--no-fcs]

Options:

 -h, --help            show this help message and exit
 -f PCAPFILE, --pcap-file=PCAPFILE
                       Capture dump
 -t TEXTFILE, --text-file=TEXTFILE
                       Capture already converted/filtered
 --no-fcs              don't check if frames have bad crc


  • The input file (PCAPFILE) is a tcpdump capture file (captured by tcpdump, wireshark or any other compatible tool)
    • Radiotap header must be present (for the script needs the tx datarate)
    • If your capture does not provide Frame CheckSum (this is the case of the captures from XOs) you must provide the flag --no-fcs
    • By default only frames with good FCS will be computed
  • The script generates a temporary file in the local directory named <caprute file>.tmp2
    • This file can be used instead of the original pcap file (using the -t option). This is meant to save processing time if you just want to generate the same report later.
    • The .tmp3 file can be safely removed

The Report

The PDM-Analysis tool will generate a report like the following: Note: In this case 10 nodes were forced into a topology with paths varying from one to four links in length and all the nodes stated pinging a multicast address, so to trigger the Path Discovery Mechanism.

------------------------------------------------------------------------
ROUTE DISCOVERY REPORT (for ../route_exp/captures/10s-mcastping-1.pcap)
------------------------------------------------------------------------
Captured route discovery frames: 14152 [RREQs 12936 (91.41%) RREPs 1141 (8.06%) RERRs 75 (0.53%)]
Route discovery clusters: 852
Average # of frames captured per cluster: 16.52 (stdev = 11.57) [RREQs 15.18, RREPs 1.34, RERRs 0.09]
Replied requisitions (with any rrep captured): 509 (59.00%)
Completed requisitions (with final rrep captured): 158 (18.00%)

RREQs:
By Hop Count: 1: 2165 (16.74%) 2: 4449 (34.39%) 3: 3354 (25.93%) 4: 2280 (17.63%) 5: 688 (5.32%) 
By Datarate: 54: 2374 (18.35%) 36: 2470 (19.09%) 11: 3991 (30.85%) 1: 4101 (31.70%) Unknown: 0 (0.00%) 

RREPs:
By Hop Count: 1: 93 (8.15%) 2: 362 (31.73%) 3: 478 (41.89%) 4: 180 (15.78%) 5: 28 (2.45%) 
Estimated % of multihop paths: 34.26%

First RREP elapsed time (ms): 62.27 (stdev = 35.94) MIN: 14.87 MAX: 183.31
Route acquisition time (ms): 80.74 (stdev = 50.73) MIN 14.87 MAX 263.99
Route discovery lifespan (ms): 94.71 (stdev = 57.99) MAX 263.99
RREQ distribution for 1 hop(s) (ms): mean = 11.02 (stdev = 24.53) MIN: 0.00 MAX: 189.35
RREQ distribution for 2 hop(s) (ms): mean = 34.07 (stdev = 38.90) MIN: 1.69 MAX: 232.48
RREQ distribution for 3 hop(s) (ms): mean = 52.19 (stdev = 40.12) MIN: 4.94 MAX: 227.01
RREQ distribution for 4 hop(s) (ms): mean = 64.19 (stdev = 39.30) MIN: 10.75 MAX: 194.59
RREQ distribution for 5 hop(s) (ms): mean = 82.54 (stdev = 42.35) MIN: 18.09 MAX: 189.81

PDM Airtime (ms): 5778.6543
PDM Activity Interval (s): 68.53
PDM Airtime %: 8.43

Participants: 10

00:17:c4:05:2c:ae: FWD 1518             ORIGIN 65 => 1309               TARGET 65 => 1199
00:17:c4:05:23:3a: FWD 1475             ORIGIN 61 => 1217               TARGET 83 => 1325
00:17:c4:0c:e8:eb: FWD 1307             ORIGIN 145 => 2205              TARGET 82 => 1463
00:17:c4:02:2f:59: FWD 1325             ORIGIN 127 => 1823              TARGET 91 => 1711
00:17:c4:05:27:98: FWD 1691             ORIGIN 149 => 1968              TARGET 78 => 1351
00:17:c4:05:23:02: FWD 1080             ORIGIN 43 => 874                TARGET 109 => 1615
00:17:c4:03:57:1b: FWD 1357             ORIGIN 60 => 1006               TARGET 81 => 1361
00:17:c4:05:2a:79: FWD 1525             ORIGIN 68 => 1217               TARGET 98 => 1701
00:17:c4:03:56:e0: FWD 1477             ORIGIN 67 => 1264               TARGET 83 => 1121
00:17:c4:05:27:a3: FWD 1397             ORIGIN 67 => 1194               TARGET 82 => 1230

How to read the Report

HEADER:

The header informs the name of the file used to generate the report

------------------------------------------------------------------------
ROUTE DISCOVERY REPORT (for ../route_exp/captures/10s-mcastping-1.pcap)
------------------------------------------------------------------------

GENERAL INFORMATION SECTION:

The total number of PDM frames captured [by type]:

Captured route discovery frames: 14152 [RREQs 12936 (91.41%) RREPs 1141 (8.06%) RERRs 75 (0.53%)]

The number of times the PDM was started and the average composition of a cluster:

Route discovery clusters: 852
Average # of frames captured per cluster: 16.52 (stdev = 11.57) [RREQs 15.18, RREPs 1.34, RERRs 0.09]

For how many of the clusters at least one RREP was captured, and for how many a final rrep (i.e. one with the transmission address of the originator of the cluster):

Replied requisitions (with any rrep captured): 509 (59.00%)
Completed requisitions (with final rrep captured): 158 (18.00%)

Note: The above, of course, does not mean that only 18% of the path discovery attempts were complete, but it can be used to compare the results between two different experiments (an increase in this number is an indicator of higher efficacy)

ROUTE REQUESTS SECTION:

RREQs:

A RREQ cluster will be propagated through the mesh cloud in many hops (in this case, an interesting topology was forced with Blinding Table):

By Hop Count: 1: 2165 (16.74%) 2: 4449 (34.39%) 3: 3354 (25.93%) 4: 2280 (17.63%) 5: 688 (5.32%)
By Datarate: 54: 2374 (18.35%) 36: 2470 (19.09%) 11: 3991 (30.85%) 1: 4101 (31.70%) Unknown: 0 (0.00%) 

Note: The position of the monitoring station should be take into account. If placed far away from the observed traffic lower rates will dominate.

ROUTE RESPONSES SECTION:

RREPs:

This will give you a good insight on the typical path length (in this case, an interesting topology was forced with Blinding Table):

By Hop Count: 1: 93 (8.15%) 2: 362 (31.73%) 3: 478 (41.89%) 4: 180 (15.78%) 5: 28 (2.45%) 
Estimated % of multihop paths: 34.26%

TIME LINE SECTION:

Time necessary for the first RREP to each cluster to be transmitted.

First RREP elapsed time (ms): 62.27 (stdev = 35.94) MIN: 14.87 MAX: 183.31

Time necessary for the last RREP to each cluster to be transmitted.

Route acquisition time (ms): 80.74 (stdev = 50.73) MIN 14.87 MAX 263.99

PDM traffic keeps being transmitted even after the path was discovered (because it floods the mesh)

Route discovery lifespan (ms): 94.71 (stdev = 57.99) MAX 263.99

The RREQs by hop count in a time line.

RREQ distribution for 1 hop(s) (ms): mean = 11.02 (stdev = 24.53) MIN: 0.00 MAX: 189.35
RREQ distribution for 2 hop(s) (ms): mean = 34.07 (stdev = 38.90) MIN: 1.69 MAX: 232.48
RREQ distribution for 3 hop(s) (ms): mean = 52.19 (stdev = 40.12) MIN: 4.94 MAX: 227.01
RREQ distribution for 4 hop(s) (ms): mean = 64.19 (stdev = 39.30) MIN: 10.75 MAX: 194.59
RREQ distribution for 5 hop(s) (ms): mean = 82.54 (stdev = 42.35) MIN: 18.09 MAX: 189.81

PDM AIRTIME STATISTICS:

Total airtime consumed by all PDM frame in the input file

PDM Airtime (ms): 5778.6543

Interval between the first and the last PDM frame in the input file

PDM Activity Interval (s): 68.53

The percentage of the airtime consumed by the PDM traffic (in the interval it was detected)

PDM Airtime %: 8.43

PARTICIPANTS SECTION:

Participants: 10

The number of PDM frames forwarded (FWD) by each node.
The number of PREQ clusters originated by each node (ORIGIN) and how many frames were triggered by the original RREQs.
The number of PREQ clusters destined (targeted at) the node and how many frames were triggered by the original RREQs.

00:17:c4:05:2c:ae: FWD 1518             ORIGIN 65 => 1309               TARGET 65 => 1199
00:17:c4:05:23:3a: FWD 1475             ORIGIN 61 => 1217               TARGET 83 => 1325
00:17:c4:0c:e8:eb: FWD 1307             ORIGIN 145 => 2205              TARGET 82 => 1463
00:17:c4:02:2f:59: FWD 1325             ORIGIN 127 => 1823              TARGET 91 => 1711
00:17:c4:05:27:98: FWD 1691             ORIGIN 149 => 1968              TARGET 78 => 1351
00:17:c4:05:23:02: FWD 1080             ORIGIN 43 => 874                TARGET 109 => 1615
00:17:c4:03:57:1b: FWD 1357             ORIGIN 60 => 1006               TARGET 81 => 1361
00:17:c4:05:2a:79: FWD 1525             ORIGIN 68 => 1217               TARGET 98 => 1701
00:17:c4:03:56:e0: FWD 1477             ORIGIN 67 => 1264               TARGET 83 => 1121
00:17:c4:05:27:a3: FWD 1397             ORIGIN 67 => 1194               TARGET 82 => 1230

Note: This report was generated over a forced topology (with blinding table)

Personal tools
  • Log in
  • Login with OpenID
About OLPC
About the laptop
About the tablet
Projects
OLPC wiki
Toolbox
In other languages