MACA_P

Project: MACA-P Improvement

Step 0: Observe Original Code
Step 1: Re-locate in ns-2.27
Step 2: Test mac code with TCL script
Step 3: Analyze the 802.11 code of MACA-P mechanism
Step 3.5 Find the fixed route of DSDV
Step 4: Find How to record and compare the simulation results of MACA-P
Step 5: Reproduce the original results
Step 6: Generate New results for Grid Topology
Step 7: Generate New Results for Random Topology
Questions

Step 0: Observe Original Code

Original Changes: Applied as following: relative to the ns directory

mac/	mobile/	common/	tools/	trace/	/	/dsdv
mac-802_11.h mac-802_11.cc mac-timers.h mac-timers.cc mac.cc mac.h wireless-phy.cc arp.h arp.cc	tworayground.cc	scheduler.cc	loss-monitor.cc loss-monitor.h	cmu-trace.h	autoconf.h Makefile	dsdv.cc dsdv.h rtable.cc rtable.h

Among those files, scheduler.cc Makefile, tworayground.cc autoconf.h are unchange at all! So, we don't need them.

Step 1: Re-locate in ns-2.27

Some necessary operations:

1. scheduler.cc
(no change????)
2. Makefile (no change) and autoconf.h
3. mac-802_11.cc
default value of function cannot be re-defined in mac-802_11.cc (already defined in mac-802_11.h) (total 3 occurance in mac-802_11.h)
4. Wireless-phy.cc
conversion from Node to MobileNode in "log-energy()" and "stamp()" ( totally 4 occurance in the file)
5. cmu-trace.cc :
Some new definitions for new version like "DROP_RTR_SALVAGE" has to be added.
6. Tworayground.cc
Have to copy the implementation of "TwoRayGetDist" function from the ns-2.27 to this file to avoid link errors.

Step 2: Test mac code with TCL script

Note: All perl scripts and other text files in /tcl directory have to change to UNIX fromat from DOS format.

udp.pl	A test perl script to run udp traffic on a star topology. it will call "ns run.tcl ....."
run.tcl	The mainl tcl script for a wireless simulaton.
./topo/	topology tcl files such as star.tcl
./traffic/	traffic generation tcl files such as udpstar.tcl
./tmpres/	directory to store the analysis of trace
./tmp/	store trace file ( not in cmu-trace format)
./scripts/	other perl script
grid.pl	A test script to test grid topology
nn.pl	Anoter test script
./results/	?
numnodes	?

Run udp.pl...
It took serveral minutes to finish this 200-sec scenario.
There would be a new line in the tmpres/outer.c640 file as below:

4 1 1536 640 0 0.85828125 0.817734375 0.0715234375

which shows

$nn	$triggerconstant	$packetsize	$control_len	$angle	$mm_thput	$mac802_11_thput	$mm_per_stream_thput
4	1	1536	640	0	0.85	0.81	0.07152

There is no output as trace file because of "tr -/dev/null" option. if needed, specify -tr option when call "run.tcl".

Step 3: Aanlyze the 802.11 code of MACA-P mechanism:

Adaptive Learning:

The learning is performed by a hash table structure. A node has to decide it will go or not to go with a neighbor's schedule.

struct part_list {
        struct part_list *next;
        u_int32_t nodeId;
};

A part_list is just a link table of nodes. Assign_goodness function is to set value based on the RTS request to neighbors, if it fails, a value 0 will be set. If it succeeds, a value 2 is set. Once a 2 is set, it is always regarded as "good". hashtable is just a double precision array. If the value is set to 2, it si always 2. Otherwise, it will forget with a gamma factor and the value will between (0,1). then a coin toss could make the node obey a neighbor's schedule with probability.

Preferential Triggering:

This is triggered in function update_nav_with_rollback.
It is mainly called by check_pktRTS. Thus, if a node has a packet to send and can schedule with a previous announcement from a neighbor. It reduce it is own back off by half through followngi functons:

void
BackoffTimer::faster(double constant) {
        assert(paused_);// this is only called on immediately hearing an RTS. so backoff counter should have been paused right now.

Second Capture Anytime:
The codes in recv() fucntion is modified to enable "second capture" behavior that no matter what packet comes first, the strong signal get captured. This is done by set a large value 1e+5 in the comparison of mhRecv.age().
If we reset it to 4 us, then it is go back to normal behavior.

else if (p->txinfo_.RxPr / pktRx_->txinfo_.RxPr > pktRx_->txinfo_.CPThresh && mhRecv_.age() < 1e+5) { ......

The other suspicious lines related to 2nd capture is in IS_Idle_for_CTS:

	//XXX : if we want second capture, only then should the following
	//two lines be uncommented --sorav(7/7/02)
	if (recvnav_ > Scheduler::instance().clock())
		return 0;

Step 3.5 Find the fixed route of DSDV

The tpology use genstar.pl script to generate 4 nodes graph and use shortestpath.pl to calculate shortest path and store it in "routes" file.
The file is in such a format that the "from to next_hop_addr hops" are 4 columns.
It is possible to manually configure such a table for DSDV's usage.
The modification of DSDV is also a little tricky. The fixed path routing table is not read at the initialization of the routing agent, but when a mac transmission failuer (link_lost) occurres. Also, the "makeroutingtable" functuon is placed in the helper_Callback procedure. And the helper is the periodic route maintanance procedure in DSDV and scheduled like:

 // kick off periodic advertisments
  periodic_callback_ = new Event ();
  Scheduler::instance ().schedule (helper_,
                                   periodic_callback_,
                                   jitter (DSDV_STARTUP_JITTER, be_random_));

Step 4: How to trace and analyze results:

Becasue the sink are defined as Agent/LossMonitor. Thus, it could show how many packets are lost.
Further, loss monitor's behavior are also modified to correct calculations for late packets.
However, as we use fixed path, what's the reason for a dis-order packet sequence?
In loss-monitor.cc npkts_ is recvd number and nlost_ is the loss numbe.
And when we source a traffic.tcl such as udpstar.tcl in run.tcl. There is a line in this traffic TCL file like

$ns_ at $opt(stopmonitor) "printnpkts_ $null_($i)"

This is to print a numberof loss in one sink in the opt(trace) specifirf in run.tcl. After this, some perl scipts in udp.pl will calculate some results basen on this trace file stored like /tmp/trace-c640.mymac. The calculation is done by this way:

        $mm_thput = 8*$packetsize*$mm_totalpkts/(($stopmonitor-$startmonitor)*1024*1024);
        $mac802_11_thput = 8*$packetsize*$mac802_11_totalpkts/(($stopmonitor-$startmonitor)*1024*1024);
open (RESULTS,">>tmpres/outer.c640");
        print RESULTS "$nn $triggerconstant $packetsize $control_len $angle $mm_thput $mac802_11_thput $mm_per_stream_thput\n";
        close RESULTS;

From above, UDP throughput is measured as Mbps recorded in the /tmpres/outer.c640 file.

Step 5: Reproduce Previous Results:

100 Sec. 640Byte Control Gap. 1536B cbr packet load Senders are located in Outer Ring

with second capture enabled in MACA-P

Number of nodes	802.11 Throughput Avg.	Original	MACA-P Througphut	Original results
2	0.8248828125	0.8221875	0.590625	0.5905078125
4	0.817734375	0.817734375	0.8574609375	0.85828125
6	0.81046875	0.8119921875	0.959296875	0.961640625
8	0.8199609375	0.8184375	1.6330078125	1.6339453125
10	0.813984375	0.8141015625	1.8010546875	1.806796875
12	0.8082421875	0.8096484375	0.7515234375	0.7365234375
14	0.8002734375	0.80484375	0.7812890625	0.783515625
16	0.808125	0.8115234375	1.0201171875	1.0098046875
18	0.8034375	0.8058984375		1.031015625

Results for normal capture ( 2nd captuer less than 4us) behavior:
Here, I vary the parameter 4us from 0 to 4ms

Number of nodes	MACA-P Througphut (0us)	4us	40us	400us	4ms	Original results
2	0.590625	0.590625	0.590625	0.590625	0.590625	0.5905078125
4	0.4884375	0.4883203125	0.5501953125	0.8574609375 0	0.8574609375	0.8591015625
6	0.5724609375	0.5883984375	0.6167578125	0.959296875	0.959296875	0.7723828125
8	0.8279296875	0.8980078125	0.9945703125	1.621171875	1.621171875	0.9202734375
10	0.8712890625	1.021640625	1.08984375	1.80328125	1.80328125	0.8203125
12	0.6200390625	0.64546875	0.65332031	0.718125	0.7391015625	0.470859375
14	0.6219140625	0.66375	0.688359375	0.7529296875	0.7866796875	0.4810546875
16	0.622734375	0.708515625	0.720703125	0.983203125	1.01390625	0.526640625
18	0.5975390625	0.6891796875	0.7140234375	1.02234375	1.00921875	0.481171875

Here, we simulation with "adaptive learning" disabled. As there are no original results.
We only have this table:

Number of nodes	MACA-P Througphut (4us)
2	0.590625
4	0.4883203125
6	0.5883984375
8	0.8963671875
10	1.026328125
12	0.465
14	0.5051953125
16	0.4946484375
18	0.5288671875

This reuslt does not match the figure 8b in Broadnets paper.

Step 6: Generate New reuslts for Grid Topology

Aggregate throughput of 2 diagonal flows: ( upleft --> downright & downleft --> upright) ------------ Contrl gap: 640B, captuer : 4us

Grid Size	MACA-P Througphut	Original 802.11 results
2 x 2	0.359765625	0.41484375
3 x 3	0.1470703125	0.1986328125
4 x 4	0.1248046875	0.16640625 0
5 x 5	0.097265625	0.1634765625
6 x 6	0.1083984375	0.15
7 x 7	0.092578125	0.1482421875

Step 7: Generate New Reults for Random Topology

Simulation Parameters:

topology:	670m x 670m
nodes	50
cbr cconnections	10 ( start randomly from 10-150 sec)
simulaiton time	400 seconds

First, we have to generate fixed routes for DSDV for simulation purpose. To use
shortestpath.pl scipt we have to has an "ADJ" file.
So, we modify the "scen-670...." file which is generated by setdest tool of ns. Remove all mobility parts, and keep the position of each node in a seperate "random.tcl" script in "topo" directory. And copy all "god dist" part into a seperate file named "new_adj".
We use a perl scipt to handle this new_adj" to let it become a normal adj file we want. Then it could be feed into the "shortestpath.pl" to generate routes.
This need an awk script:

awk '$5 ~ /^1$/ { print ($3,$4,$5) >> "new_adj"}' scen_god

Simulation Results:

	Results of each flow ( packets delivered)
Flow	Original 802.11	MACA-P
1-35-2 1-3 2-35-3 8-35-9 8-10 9-10 9-11 10-11 11-16-12 11--1-13	npkts_ = 1027 npkts_ = 3407 npkts_ = 1279 npkts_ = 332 npkts_ = 1864 npkts_ = 2507 npkts_ = 3490 npkts_ = 3549 npkts_ = 840 npkts_ = 820	npkts_ = 1857 npkts_ = 3503 npkts_ = 1800 npkts_ = 312 npkts_ = 1433 npkts_ = 2171 npkts_ = 3151 npkts_ = 3554 npkts_ = 648 npkts_ = 700
	19115 packets	19129 packets

Step 8: 15-node mesh Network' simulation

Packet size 512B. topo: 800mx800m.

	Flow 1(14-3-2)	Flow 2(0-1-4-7-10)	Flow 3(13-8)	Flow 4(12-9-5)	Total (Mbps)
80	772	673	356	251	0.08015625
90	773	648	344	253	0.078828125
100kbps	757	631	317	265	0.076953125
110	812	641	299	237	0.0776953125
120	770	677	345	223	0.0787109375
130	807	643	332	247	0.0792578125

Adjust the Second capture effect as any capture, alos use the 128B as the control gap:

	Flow 1(14-3-2)	Flow 2(0-1-4-7-10)	Flow 3(13-8)	Flow 4(12-9-5)	Total (Mbps)
80	npkts_ = 2014	1923	1910	817	0.2603125
90	npkts_ = 2253	1845	1939	749	0.265078125
100kbps	npkts_ = 2467	1782	1751	793	0.2653515625
110	npkts_ = 2732	1704	1818	730	0.2728125
120	npkts_ = 2970	1645	1807	644	0.276015625
130	npkts_ = 3152	1618	1770	609	0.2792578125

Seems the last flow 12-9-5 has a problem with MACA-P protocol, many DATA packets (12-9) collided with other packets around node 9 and RTS from node 12 get no response.

Simulate with 4 by 4 grid vertical flows:
Packet size 1024B, Anytime second capture

	Control len= 640	Control-len = 128
Each column	npkts_ = 1629 npkts_ = 1014 npkts_ = 931 npkts_ = 1621	npkts_ = 2025 npkts_ = 677 npkts_ = 670 npkts_ = 2031
Total (Mbps )	0.405859375	0.422109375

4us second capture results:

	Control len= 640	Control-len = 128
Each column	npkts_ = 1318 npkts_ = 666 npkts_ = 644 npkts_ = 1244	npkts_ = 2027 npkts_ = 338 npkts_ = 304 npkts_ = 2078
Total (Mbps )	0.3025	0.370859375

Questions:

I see no new files are created comparing to ns-2 source tree. So, why we need to modify the makefile? Same question to the autoconf.h?
Why we need to modify scheduler.cc? I didn't see any comments in it.
What's the modifications in tworayground.cc?
what is "ns8" in udp.pl line 39 ? cannot find ns8 to execute? and there is no error message about this??
Why "column" ( Line 14 in udp.pl) is set to 12?
How to compare the perfromance with old 802.11? How to get old 802.11 test result? Need to modify dsdv directory? Is there any change to tcl script and perl scripts?
in Run.tcl Line 27 " set opt(packetSize) 1536;". So the packet size is not passed from arguments. Why in Line 26 of udp.pl still has a parameter option like, "-packetSize $packetsize".
in udp.pl Line 10. the topology is set to "udpstar.tcl", but it is not in current directory. Also, for traffic file "star.tcl"....
Need I copy all tcl files in ns2.27/tcl/ directory. All we just maintain a seperate directory for all our own tcl scripts?
Line 26 of udp.pl, why the code is " ./ns ....." Does this mean ns has to be in the same directory as that of this perl script?
The route stored in "routes" file of /scripts directotry seems not used by any other script?
About assign_goodness (function), as it is value is either 0 or 2 ( inital value is 1). Why we need a hashtable, can we just assign values to each neighboring node? Why we need a hash function?

Zhibin Wu, 08/16/2004