This software is Copyright (c) 2005-6 the University of Washington. It can be used and distributed under the following terms: - the software is provided as is, with no warranties or liabilities - research and non-commercial use is permitted - contact the authors for commercial use - the original attribution should exist on any derivative work - the derivative works should be distributed under similar terms The primary authors are: Ratul Mahajan Maya Rodrig John Zahorjan ===================== Table of Contents: NOTE USING THE SCRIPTS EXAMPLE FILES ===================== NOTE: these scripts are provided as is. they may cause irreversible damage to your psyche; use them at your own risk. they were written hastily and not with a view to sharing with others. as a result, they are ugly, sloppy, and have many idiosyncracies. we have tried to flag these in this README file but you are bound to run into issues. if problems arise, first please carefully look at the source and try to understand what is going on. contact us if things are still unclear. we are very interested in hearing about your experience with them. bugfixes and suggestions for improvement are also appreciated. ==================== USING THE SCRIPTS the included scripts use perl, the DBI module of perl and mysql (other databases supported by DBI should also work). install them first. you should be at least a little familiar with sql. only the default behavior of most of the scripts is explained below. their behavior can be modified using command line arguments. look at the scripts for the various options. using the -h flag or incorrect usage will print out a usage message for most scripts. A. inserting traces into the database ------------------------------------- 1. create the database where you want to store the tables. you can do this with mysqladmin as: % mysqladmin create where is the name of the database. 2. set up your environment to use the database: export WDB_USER=; # the username to use for accessing the DB export WDB_PASSWD=; # the password export WDB_HOST=; # the host where mysql is installed export WDB_DB= # the database name to avoid setting up this environment each time, insert these into your shell's .rc file (e.g., .bashrc), or modify localutils.pl which contains the defaults to use when the above environment variables are not defined. 3. run createIndexTablesTable.pl to create some helper index tables in the database. 4. populate the database with the monitor traces. the format of these tables is: mysql> show columns from raw_east_i0_c3; +------------------+----------------------+------+-----+---------+-------+ | Field | Type | Null | Key | Default | Extra | +------------------+----------------------+------+-----+---------+-------+ | id | int(11) | NO | PRI | | | | aFrameTime | decimal(18,7) | YES | | NULL | | | aTimeDelta | int(10) unsigned | YES | | NULL | | | bChannel | tinyint(3) unsigned | YES | | NULL | | | bHostTime | int(10) unsigned | YES | | NULL | | | bMACTime | int(10) unsigned | YES | | NULL | | | bRate | float | YES | | NULL | | | bRssi | smallint(6) | YES | | NULL | | | bSize | smallint(5) unsigned | YES | | NULL | | | cA1_Dest | smallint(5) unsigned | YES | | NULL | | | cA2_Src | smallint(5) unsigned | YES | | NULL | | | cA3 | smallint(5) unsigned | YES | | NULL | | | cA4 | smallint(5) unsigned | YES | | NULL | | | cDSFrom | tinyint(3) unsigned | YES | | NULL | | | cDSTo | tinyint(3) unsigned | YES | | NULL | | | cDur | smallint(5) unsigned | YES | | NULL | | | cFragno | tinyint(3) unsigned | YES | | NULL | | | cMoredata | tinyint(3) unsigned | YES | | NULL | | | cMorefrag | tinyint(3) unsigned | YES | | NULL | | | cOrdered | tinyint(3) unsigned | YES | | NULL | | | cProtver | tinyint(3) unsigned | YES | | NULL | | | cPwrmgt | tinyint(3) unsigned | YES | | NULL | | | cRetry | tinyint(3) unsigned | YES | | NULL | | | cSeqno | smallint(5) unsigned | YES | | NULL | | | cSubtype | tinyint(3) unsigned | YES | | NULL | | | cType | tinyint(3) unsigned | YES | | NULL | | | cWEP | tinyint(3) unsigned | YES | | NULL | | | dBeaconTimestamp | bigint(20) unsigned | YES | | NULL | | | zErr | tinyint(3) unsigned | YES | | NULL | | | zErrDriver | tinyint(3) unsigned | YES | | NULL | | | zErrPhy | tinyint(3) unsigned | YES | | NULL | | +------------------+----------------------+------+-----+---------+-------+ 31 rows in set (0.03 sec) the meanings of the most fields should be apparent (ignore the first letter of the fieldnames) except for maybe the following: - zErr* fields correspond to frames that were not correctly decoded - aFrameTime is the absolute time of the frame in seconds. this is persistent but may not be very precise. - aTimeDelta and bHostTime: ignore these fields - bMACTime is the hardware timestamp of the frame in microseconds. it is 32 bit wide and hence rolls over in rougly 1.2 hours. not all fields are meaningful for all captured frames. to save disk space (and to speed processing), the MAC address fields are stored as indices into a corresponding MACIndex table. the name of the mac index table should be _MACIndex. its format is: mysql> show columns from raw_east_i0_c3_MACIndex; +-------+------------------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------+------------------+------+-----+---------+----------------+ | id | int(10) unsigned | NO | PRI | NULL | auto_increment | | value | char(18) | YES | | NULL | | +-------+------------------+------+-----+---------+----------------+ 2 rows in set (0.00 sec) we have included a script called createRawDataDatabase.pl that creates such tables from tcpdump, prism header logs such as those collected by us at sigcomm04. this script is run as: % createRawDataDatabase.pl -d where: is the directory containing the traces the script assumes that the trace filenames are of the format: //*-ath.tcpdump*; if your filenames are different format, modify the following line in the script: my @fileList = split(' ', `ls $rootDir/$logger/*-ath$interface.tcpdump*`); the script uses tethereal to read the traces; you need to point it at the location of tethereal by modifying the following line in the script: my $TETHEREAL = "$ENV{HOME}/usr/local/bin/tethereal"; to insert traces of a different format into the database, you need to change the processPackets subroutine in createRawDataDatabase.pl. B. merging (halfWit) -------------------- merging happens in multiple, waterfall rounds. two tables are merged in round. the first table can be a result of merging in the previous rounds; the second table is a raw table. a round consists of two steps: a. createBeaconIndex.pl creates a temporary table that contains all the beacons that are common to the two tables. be sure to ignore beacons from APs that do not have monotonically increasing beacon timestamps. b. createMergedTable.pl uses the beacons table to merge the two tables. an example of the usage of these two scripts is shown in merge-commands.sh. that shell script shows how to merge the following five tables: raw_chi_i0_c1 raw_sah_i0_c1 raw_son_i0_c1 raw_kal_i0_c1 raw_moj_i0_c1 createBeaconIndex.pl takes as input the names of the two tables being merged and the desired name for the beacons table, which should be of the form beacons_*. createMergedTable.pl takes as input the name of the beacons table. from beacons_*, it produces the merged table called merged_*. for us, merging the traces of kal(ahari) was a little bit more problematic because that monitor was being shut down at nights. merge-commands.sh also shows how such monitors can be merged. the merged tables contain more columns than the raw tables. the number of additional columns depends on how many raw tables have been merged so far. the extra columns in a merge of three raw tables will have the following additional columns: | zzFromTable | tinyint(3) unsigned | YES | | NULL | | | zzid_0 | int(11) | YES | | NULL | | | zzbRssi_0 | smallint(6) | YES | | NULL | | | zzTDiff_0 | tinyint(3) unsigned | YES | | NULL | | | zzid_1 | int(11) | YES | | NULL | | | zzbRssi_1 | smallint(6) | YES | | NULL | | | zzTDiff_1 | tinyint(3) unsigned | YES | | NULL | | | zzid_2 | int(11) | YES | | NULL | | | zzbRssi_2 | smallint(6) | YES | | NULL | | | zzTDiff_2 | tinyint(3) unsigned | YES | | NULL | | +------------------+----------------------+------+-----+---------+----------------+ - zzFromTable: the input table from which this frame came from (any one if it was present in multiple tables). - zzid_: the corresponding id of this frame in the k-th raw table. it is null if this frame was not present in k-th raw table. - zzbRssi_: similar to the above. - zzTDiff_: the time difference in translated terms between the timestamp in the k-th raw table and the timestamp assigned to the merged frame. (this can be used to gauge the quality of time synchronization.) C. inference (nitWit) -------------------- lostPackets.pl implements the functionality of nitWit. it can be run simply as: % ./lostPackets.pl where can either be a raw or a merged table. this scripts mainly produces three tables -- processed, extras, and synthpkts. apart from some columns that it shares with the raw and merged tables, the processed table contains the following columns: | _zBSSID | smallint(5) unsigned | YES | | NULL | | | _zDir | tinyint(3) unsigned | YES | | NULL | | | _zWasrcvd | tinyint(3) unsigned | YES | | NULL | | +------------+----------------------+------+-----+---------+-------+ - _zBSSID is the inferred BSSID of the packet. not all 802.11 packets contain the BSSID field in their headers. inserting this here simplifies per packet processing. similarly, the cA2_Src is filled out properly with the inferred source of the packet if its absent (e.g., for ACKs). - _zDir represents the direction of the packet. the meanings of the values are contained in the dirIndex table created by createIndexTablesTable.pl. mysql> select * from dirIndex; +----+--------+ | id | value | +----+--------+ | 0 | up | | 1 | down | | 2 | ad hoc | | 3 | ap-ap | +----+--------+ 4 rows in set (0.02 sec) - _zWasrcvd represents whether the frame was received by its destination. the extras table contains some auxillary information for the frames. it is separate from the processed table to reduce the processing time of the scripts that operate on the processed table, which is restricted to commonly used fields. the synthpkts table contains the inferred packets. for an input table called raw_
or merged_
, by default, the three tables will be called processed_
, processed_
_extras, processed_
_SynthPkts. lostPackets.pl takes a bunch of options. (for details, see the script or use the -h flag.) a couple of important ones are: -e regexpFile : the file containing the regular expression -w wtfile : the file containing symbol weights the script also uses the perl Parse::RecDescent package. it is included for convenience. D. contenders (dimWit) --------------------- computeContention2.pl estimates the number of contenders at the instant when each packet was sent. run is simply as: % computeContention2.pl it take a processed table (see above) as input. to simplify the computation of aggregate statistics as function of #contenders, it summarizes its results in two main tables. given processed_
, the two tables will be called contention_
_Time and contention_
_Packet. - the _Time table summarizes how a client spends its time -- whether it was idle, deferring, busy, etc. -- at each contention level. - the _Packet table summarizes the details of clients' packets -- their rate, direction, reception status, etc. -- at each contention level. look at the columns of the two tables (and the source) to get a better sense of what's in them. ====================== EXAMPLE we have provided a toy database as an example to help you get started. the toy db contains 3 raw tables from our simulator experiments. the script wit_toydb.sh contains commands to run halfwit, nitwit, and dimwit over them. 1. assuming that you have already installed mysql, set the environment to use it: % export WDB_HOST= % export WDB_USER= % export WDB_PASSWD= (the script below will automatically set the WDB_DB variable) 2. simply run the provided shell script which should do the following % ./wit_toydb.sh this will generate a bunch of output and warnings. if everything is working fine, your output should look like that in wit_toydb.log. (you could pipe the output of wit_toydb.sh to a file and compare it with the provided wit_toydb.log.) 3. by now, you should have a few logs in your working directory and more tables in your database. to look at the tables: % mysql -h -u -p wit_toydb this should bring up the mysql shell, at which point, do: mysql> show tables; the output of this command should display: +------------------------------------------+ | Tables_in_wit_toydb | +------------------------------------------+ | _zParseSymbolIndex | | beacons_mon1_mon2_i0_c0 | | beacons_mon1_mon2_i0_c0_TblIndex | | beacons_mon1_mon2_mon3_i0_c0 | | beacons_mon1_mon2_mon3_i0_c0_TblIndex | | contention_mon1_mon2_mon3_i0_c0_Client | | contention_mon1_mon2_mon3_i0_c0_Interval | | contention_mon1_mon2_mon3_i0_c0_Packet | | contention_mon1_mon2_mon3_i0_c0_Time | | dirIndex | | indexIndex | | merged_mon1_mon2_i0_c0 | | merged_mon1_mon2_i0_c0_MACIndex | | merged_mon1_mon2_i0_c0_MTblIndex | | merged_mon1_mon2_mon3_i0_c0 | | merged_mon1_mon2_mon3_i0_c0_MACIndex | | merged_mon1_mon2_mon3_i0_c0_MTblIndex | | processed_mon1_mon2_mon3_i0_c0 | | processed_mon1_mon2_mon3_i0_c0_MACIndex | | processed_mon1_mon2_mon3_i0_c0_PTblIndex | | processed_mon1_mon2_mon3_i0_c0_SymWts | | processed_mon1_mon2_mon3_i0_c0_SynthPkts | | processed_mon1_mon2_mon3_i0_c0_extras | | raw_mon1_i0_c0 | | raw_mon1_i0_c0_MACIndex | | raw_mon2_i0_c0 | | raw_mon2_i0_c0_MACIndex | | raw_mon3_i0_c0 | | raw_mon3_i0_c0_MACIndex | | subtypeIndex | | typeIndex | +------------------------------------------+ 31 rows in set (0.00 sec) ========================== FILES README a common helper file: localutils.pl creates the index tables: createIndexTablesTable.pl creates the raw trace tables: createRawDataDatabase.pl files related to merging: merge-commands.sh createBeaconIndex.pl createMergedTable.pl createBumpsTable.pl computeMergeBoundaries.pl files related to inference: lostPackets.pl lostPacketsFSA.sub lostPacketsCommon.pm regexpProduction.dat # example regex file wtFile.dat # example weight file Parse/RecDescent.pm # Parse::RecDescent package Parse/RecDescent.pod files related to contender estimation: computeContention2.pl file related to wit_toydb: wit_toydb.sh wit_toydb.gz wit_toydb.log regexpSim.dat # a simpler regular expression file for the toydb traces