[[Include(wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/TOC)]]

[[TracNav(802.11/TOC)]]

= Extending TokenMAC =

Recall in the [wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/characterization characterization section of this tutorial] that we noted a significant weakness in the design of TokenMAC -- when there is no contention between multiple flows, the token reservation periods for idle nodes are wasted. The design really only starts to show any gains when devices are backlogged and have a lot of traffic to send. This isn't a realistic assumption for typical traffic profiles.

In this section, we propose a simple extension to TokenMAC to address this problem. By default, a TokenMAC AP issues a reservation to each device on the network in a round-robing sequence for a fixed {{{DEFAULT_RESERVATION_DURATION_USEC}}} microseconds. Our extension will make this parameter adaptive. Rather than be fixed value, an AP will give longer reservation periods to devices that are actively using the time allocated to them. Conversely, idle or near-idle devices will be given a smaller duration of the medium until they demonstrate a need for more. We can implement this behavior entirely in CPU_HIGH and leave the low-level frame exchange behavior alone. Specifically, will augment the AP so that it audits how well each reservation period is utilized. If this audit deems that the device used a sufficient amount of the allocation given to it, a multiplication factor will increase the duration of the allocation the device's next turn.

== Specific Changes ==

=== MAC High Framework ===

Changes should be made to {{{wlan_mac_high.c}}} and {{{wlan_mac_high.h}}} in the project SDK workspace zip.

----
CPU_LOW is already configured to send the {{{IPC_MBOX_TOKEN_NEW_RESERVATION}}} IPC message back up to CPU_HIGH as a confirmation when a new reservation period starts. It will also send the {{{IPC_MBOX_TOKEN_END_RESERVATION}}} IPC message up to CPU_HIGH when the reservation period is over (which is how CPU_HIGH currently knows when to rotate to the next device for its reservation period). These messages demarcate the intervals that the AP should audit performance. The first change we will make to the MAC High Framework is to add two new callbacks that will be called upon the reception of these IPC messages. Add the following top-level global function pointers to the MAC High Framework:

{{{
#!c

volatile function_ptr_t      token_stats_start_callback;
volatile function_ptr_t      token_stats_end_callback;
}}}

In {{{wlan_mac_high_init()}}}, make sure to set these callbacks to the default nullCallback with the following two lines of code:

{{{
#!c

	token_stats_start_callback = (function_ptr_t)nullCallback;
	token_stats_end_callback = (function_ptr_t)nullCallback;
}}}

Finally, add the following setters for these callbacks so we can assign them in the AP code:

{{{
#!c

void wlan_mac_high_set_token_stats_start_callback(function_ptr_t callback){
	token_stats_start_callback = callback;
}

void wlan_mac_high_set_token_stats_end_callback(function_ptr_t callback){
	token_stats_end_callback = callback;
}
}}}

Next, we need to call the new callbacks upon the receipt of the two relevant IPC messages. We already have the case of {{{IPC_MBOX_TOKEN_END_RESERVATION}}} from our previous implementation of TokenMAC. This function called the {{{token_new_reservation_callback()}}} function pointer to let the AP know that it should issue a new token reservation period. We want to keep this behavior, but now we should additionally call the new {{{token_stats_end_callback}}} callback. We should also add the {{{IPC_MBOX_TOKEN_NEW_RESERVATION}}} case to the switch statement can call the {{{token_stats_start_callback()}}} function pointer. Furthermore, we should pass the address of the whichever device owns this reservation period as well as the duration of the reservation period as arguments to the call.

{{{
#!c

		case IPC_MBOX_TOKEN_END_RESERVATION:
			token_stats_end_callback();
			token_new_reservation_callback();
		break;
		case IPC_MBOX_TOKEN_NEW_RESERVATION:
			token_stats_start_callback( ((ipc_token_new_reservation*)msg->payload_ptr)->addr,
										((ipc_token_new_reservation*)msg->payload_ptr)->res_duration );
		break;
}}}

----

Next, we need to make a small addition to an existing struct definition that tracks details about each associated device to an AP. The reasons behind this addition will be clear once we make our changes to the AP code. In the meantime, find the definition of {{{station_info}}} in {{{wlan_mac_high.h}}}. Simply add the following element somewhere after the {{{MY_STATION_INFO_COMMON_FIELDS}}}:

{{{
#!c
u8	token_res_mult_factor;
}}}

Next, let us add a few new definitions that will act as parameters for our new TokenMAC extensions. The easiest place to add these is to the top of {{{wlan_mac_high.h}}}. This will ensure that both the MAC High Framework as well as the AP has visibility of these definitions.

{{{
#!c

#define TOKEN_RES_MULT_FACTOR_MIN 1
#define TOKEN_RES_MULT_FACTOR_MAX 50

#define DEFAULT_RESERVATION_DURATION_USEC 2000

//Ignoring all overhead, a 6 Mbps PHY rate
//could theoretically deliver (6e6*2000e-6) = 12 kBytes
//in 2ms. Let's define our "success" threshold at (an arbitrary) 1/6 of that: 2000 bytes.
//Delivering more than this threshold in 2ms will grant access to the larger
//token reservation period
#define TOKEN_RES_BYTES_EFFICIENCY_THRESH 2000
}}}

Note that we moved the {{{DEFAULT_RESERVATION_DURATION_USEC}}} definition to the above code snippet. We will remove it from the AP code in the next section.

Finally, we should set this new {{{token_res_mult_factor}}} field to {{{TOKEN_RES_MULT_FACTOR_MIN}}} whenever a {{{station_info}}} is created. To do this, add the following line to {{{wlan_mac_high_add_association()}}} just prior to the {{{entry->data = (void*)station;}}} line.
{{{
#!c

station->token_res_mult_factor = TOKEN_RES_MULT_FACTOR_MIN;
}}}

----

=== Access Point (AP) ===

Changes should be made to {{{wlan_mac_ap.c}}} in the project SDK workspace zip.

----

First, we need to add a few global variables to the top of the AP code. Add the following code snippet:

{{{
#!c

u8		token_addr[6];
u64		token_ap_num_tx_bytes;
u8		token_ap_res_mult_factor;

u64		token_sta_num_rx_bytes_start;
}}}

We will use these variables in the coming sections. Furthermore, add the following line somewhere in the AP's main() function to give it a sane default:

{{{
#!c

token_ap_res_mult_factor = TOKEN_RES_MULT_FACTOR_MIN;
}}}

---- 

Next we will let {{{set_new_reservation}}} set the reservation duration as a function of a per-station multiplication factor. In the existing function find the {{{ipc_payload.res_duration = DEFAULT_RESERVATION_DURATION_USEC;}}} line within the {{{if(curr_station_info_entry == NULL){}}} clause. Replaces this line with

{{{
#!c

ipc_payload.res_duration = DEFAULT_RESERVATION_DURATION_USEC * token_ap_res_mult_factor;
}}}

Here, {{{token_ap_res_mult_factor}}} is the top-level variable we just added. If we make no other changes, then this value will be fixed at {{{TOKEN_RES_MULT_FACTOR_MIN}}}. Next, find the same {{{ipc_payload.res_duration = DEFAULT_RESERVATION_DURATION_USEC;}}} line in the {{{else}}} clause and replace it with

{{{
#!c

ipc_payload.res_duration = DEFAULT_RESERVATION_DURATION_USEC * curr_station_info->token_res_mult_factor;
}}}

{{{token_res_mult_factor}}} is the element we added to the {{{station_info}}} struct definition and set to {{{TOKEN_RES_MULT_FACTOR_MIN}}} whenever a station_info gets created.

----
Next, we need to actually make the {{{token_res_mult_factor}}} of {{{station_info}}} as well as the {{{token_ap_res_mult_factor}}} factors adapt with perceived usage of the token reservation periods. To do this, we will keep track of how many bytes were received in each token reservation from each STA as well as how many bytes were sent by the AP during its token reservation. First, we will deal with the AP case. Find the {{{mpdu_transmit_done()}}} function and add the following line at the top of the function:

{{{
#!c

token_ap_num_tx_bytes += (tx_mpdu->length);
}}}

This line ensures that every time we get confirmation from CPU_LOW that we have transmitted a frame, we increment {{{token_ap_num_tx_bytes}}} with the number of bytes in that frame. For each STA, we are already tracking the cumulative number of received bytes in each station's statistics struct. Next, we need to create a function that will be called whenever we receive the {{{IPC_MBOX_TOKEN_NEW_RESERVATION}}} message from CPU_LOW. Add the following function to the AP code:

{{{
#!c

void token_stats_start( u8* addr, u16 res_duration ){
	dl_entry*	      station_info_entry           = NULL;
	station_info*     station                      = NULL;

	memcpy(token_addr, addr, 6);

	if(wlan_addr_eq(token_addr, my_bss_info->bssid)){
		//This is the start of the AP's reservation
		token_ap_num_tx_bytes = 0;
	} else {
		//This is the start of the a STA's reservation
		station_info_entry = wlan_mac_high_find_station_info_ADDR(&my_bss_info->associated_stations, token_addr);

		if(station_info_entry != NULL){
			station = (station_info*)(station_info_entry->data);
			token_sta_num_rx_bytes_start = station->stats->data.rx_num_bytes;
		}
	}
}
}}}


If the address provided as the argument to this function matches the AP's address (stored in {{{my_bss_info->bssid}}}), then we will reset {{{token_ap_num_tx_bytes}}}. Once this reservation period is over, {{{token_ap_num_tx_bytes}}} will only represent the total number of bytes sent during the reservation period. If the address does not match the AP, we will find the {{{station_info}}} struct that matches the address from the doubly-linked list of associated stations. From that struct, we will record the current value of the cumulative number of received bytes and store it in the {{{token_sta_num_rx_bytes_start}}} global variable. When the reservation period is over, we will calculate the difference between this value and the new cumulative number of received bytes from the same struct.

Finally, we need to attach this new function to the callback we created in the MAC High Framework. In the {{{main()}}} function of the AP, add the following line:

{{{
#!c

wlan_mac_high_set_token_stats_start_callback((function_ptr_t)token_stats_start);
}}}

----

Finally, the last change we need to make to the AP is to write a function that actually performs the performance audit at the end of every reservation period. Add the following function to the AP:

{{{
#!c

void token_stats_end(){
	u64 efficiency_metric;
	u32 token_sta_num_rx_bytes_end;
	dl_entry*	      station_info_entry           = NULL;
	station_info*     station                      = NULL;

	if(wlan_addr_eq(token_addr, my_bss_info->bssid)){
		//This is the start of the AP's reservation
		efficiency_metric = token_ap_num_tx_bytes * token_ap_res_mult_factor;

		if(efficiency_metric > TOKEN_RES_BYTES_EFFICIENCY_THRESH){
			//Set the mult factor to max
			token_ap_res_mult_factor = TOKEN_RES_MULT_FACTOR_MAX;
		} else {
			//Set the mult factor to min
			token_ap_res_mult_factor = TOKEN_RES_MULT_FACTOR_MIN;
		}

	} else {
		//This is the start of the a STA's reservation
		station_info_entry = wlan_mac_high_find_station_info_ADDR(&my_bss_info->associated_stations, token_addr);

		if(station_info_entry != NULL){
			station = (station_info*)(station_info_entry->data);
			token_sta_num_rx_bytes_end = station->stats->data.rx_num_bytes;

			efficiency_metric = (token_sta_num_rx_bytes_end - token_sta_num_rx_bytes_start) * station->token_res_mult_factor;

			if(efficiency_metric > TOKEN_RES_BYTES_EFFICIENCY_THRESH){
				//Set the mult factor to max
				station->token_res_mult_factor = TOKEN_RES_MULT_FACTOR_MAX;
			} else {
				//Set the mult factor to min
				station->token_res_mult_factor = TOKEN_RES_MULT_FACTOR_MIN;
			}

		}
	}
}
}}}

In the above function, we normalize the number of transmitted or received bytes by the device's associated {{{res_mult_factor}}}. We compare this normalize "efficiency metric" against the {{{TOKEN_RES_BYTES_EFFICIENCY_THRESH}}} value we defined earlier. If we exceed this value, we'll set the multiplication factor for the next reservation period to be {{{TOKEN_RES_MULT_FACTOR_MAX}}}. Otherwise, we will set it to be {{{TOKEN_RES_MULT_FACTOR_MIN}}}.

----

== Characterizing Extended TokenMAC ==

So, how does this extended TokenMAC perform? We repeat the experiment from [wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/characterization the characterization section].

||  [[Image(wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/figs:token_xput.png, width=600)]]  ||  [[Image(wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/figs:token_extended_xput.png, width=600)]]  ||
||  '''TokenMAC'''  ||  '''Extended TokenMAC'''  ||

The above figure shows a considerable improvement in the regimes where only one traffic flow is enabled, achieving over 15 Mbps where our standard TokenMAC implementation achieved only 8 Mbps. To explain why, we use the same packet log visualization as the previous section in the tutorial to view the A, B, C regions annotated in the above results.

===  Transition A: Beginning of Time  ===

||  [[Image(wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/figs:token_extended_A.png, width=1200)]]  ||
||  '''Extended TokenMAC: Transition A Timeline'''  ||

At the beginning of the experiment, neither that AP nor the STA is transmitting anything. As such, our adaptive protocol has deemed neither device worthy of having the {{{TOKEN_RES_MULT_FACTOR_MAX}}} multiplication factor on its reservation period. When the AP starts transmitting, you can see a relatively small window of transmissions on the far left of the above figure. At the end of this period, the AP performs its performance audit and decides to set the multiplication factor to {{{TOKEN_RES_MULT_FACTOR_MAX}}} on the next reservation period. From that point forward, we can see that the relative duty cycle of the AP's reservation period to the idle period reserved for the STA is very large. Because our protocol gives less time to the STA, we are able to achieve a significant boost in overall throughput since we are not wasting nearly as much time as the basic TokenMAC implementation.

===  Transition B: Start of a Contending Traffic Flow  ===

||  [[Image(wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/figs:token_extended_B.png, width=1200)]]  ||
||  '''Extended TokenMAC: Transition B Timeline'''  ||

When the STA begins transmitting, we see a small burst of transmissions during one of its reservation periods. At the end of this period, the AP recognizes that the STA is now utilizing the time given to it and decides to increase its multiplication factor to {{{TOKEN_RES_MULT_FACTOR_MAX}}} for the next reservation. From that point forward, we can see that both the STA and the AP continue to achieve the maximum multiplication factor and continue to split the medium evenly.

===  Transition C: Removal of a Contending Traffic Flow  ===

||  [[Image(wiki:802.11/wlan_exp/app_notes/tutorial_token_mac/figs:token_extended_C.png, width=1200)]]  ||
||  '''Extended TokenMAC: Transition C Timeline'''  ||

When the STA stops transmitting, we see that the final part of its reservation period goes idle. There was still enough receptions during this time for the AP to justify continuing to give the STA a {{{TOKEN_RES_MULT_FACTOR_MAX}}} multiplication factor for the next reservation. When this reservation period goes unused, the AP drops the STA's multiplication factor back to {{{TOKEN_RES_MULT_FACTOR_MIN}}}, thereby increasing the relative duty cycle of the AP's own transmissions.