%\documentclass[12pt,openany]{report}   %\begin{document} \section{MAC Implementation Details}Implementation details of the Mac Layer\footnotemark[3] are described here.We describe the basic channel, the TDMA slot structure, modeling ofpacket transmission and reception, along with the slot handling and callhandling mechanism used. We also describe how we have dealt withexceptions like collisions and errors on the channel.\footnotetext[3] { Implemented by Richa Jain at Indian Institute ofTechnology, Bombay. June 2001}The relevant code can be found in {\it ns}/mac-gprs.\{cc,h\} \subsection{Channels}The physical air interface provided by {\it ns} is used. The number offrequency channels to be created for the Uplink and Downlink can be set bythe user through {\em max\_num\_freq} in the OTcl script. We differentiatebetween the uplink and downlink channels by creating separate timers toclock the TDMA on each.  A hard-coded skew of 3 time-slots is maintainedbetween the uplink and downlink TDMA frames. On each frequency (uplink aswell as downlink), slot 0 is reserved for signalling and broadcasts. Theuser can decide the number of slots to reserve for GPRS traffic on eachfrequency through {\em gprs\_slots\_per\_frame} in the OTcl script. Theremaining slots are left for GSM mobiles. The frequency channel a packetis to be transmitted on is stamped onto a new field called {\em chan\_} inthe common header of the packet.The logical channels are mapped such that:PBCH - slot0 on uplink/downlink frequency 0.PRACH - slot0 on uplink frequency 0. PAGCH - slot0 on downlink frequency 0. PDTCH - all other slots/frequencies. \subsection{TDMA Slot Structure}Every TDMA frame has 8 slots (defined as SLOTS\_PER\_FRAME). Slot durationis set as 577 microseconds. We transmit 50 bytes ie one (simulated) RLCPDU, in each slot. This models the transmission of one GPRS Radio Block(RB) (of size ~200 bytes) over four slots in consecutive frames. Forpackets smaller than the size of an RLC PDU (ex {\em rlc\_acks} or {\emll\_acks}), the packet transmission time is taken as {\em packet\_size/transmission\_rate}.We use {\em Up\_Slot\_Gprs\_Timer} and {\em Down\_Slot\_Gprs\_Timer} tosignal the start and end of each slot on the uplink and downlinkrespectively, and the processing is handled by the {\em upslotHandler()}and {\em downslotHandler()} respectively.The {\em upslotHandler()} checks whether any MS has a packet to transmitin the current upslot. If it does, the packet is passed onto {\emtx\_onto\_PHY()} that starts the `transmission' of the packet. Similarlythe {\em downslotHandler()} checks at the BS.\subsubsection{Timing Advance}The upslot/downslot TDMA frames at the MS and the BS should besynchronized. But the finite propagation delay between the MS and BScauses a mismatch. Therefore, the clock at the MS would have to beadvanced by the finite propagation delay time, in order to maintainsynchronism. Implementing this would introduce undue complexity. Instead,we work a way around this problem by setting thepropagation delay to zero (in {\it ~ns}/wirelessphy.cc).\subsection{Packet Transmission and Reception}We model packet transmission over the air-interface by a timer that keepstrack of how long the radio transmission should take and signals when thetransmission is over.  The packet transmit timer ({\em TxPktGprsTimer}) isstarted at the begining of the appropriate slot by {\em tx\_onto\_PHY()}.On expiry of the transmit timer, the {\em sendHandler()} is called, whichfrees the packet, switches off the radio, and unlocks the IFQ.If a MS or the BS senses a packet destined for it at the air-interface, itcalls {\em rx\_from\_PHY()}. This starts a receive timer ({\emRxPktGprsTimer}) to model the actual radio reception and also checks forcollisions. On expiry of the receive timer, the {\em recvHandler()} iscalled, which checks whether the packet is in error or can be received,and sends it on to be processed by {\em fwd\_DATA\_to\_LL()} and forwardedto the RLC.Since we take propagation delay to be zero, the transmit and receivetimers effectively start (and end) together.\subsection{Call Set-up and Handling}The following messages are used for call set-up and handling.\subsubsection{Resource Request}The first packet received by the MAC of an MS (from the IFQ) triggers a{\em resource\_request} message to the BS. We buffer the packet and thelock the IFQ to prevent it from sending down further packets. Await\_timer is started to keep track of the time an MS waits for a {\emresource\_reply}. The {\em resource\_request} message is transmitted onslot 0 on uplink frequency 0.\subsubsection{Resource Reply}The BS allots a channel (slot-frequency) to an MS either on the receipt ofa {\em resource\_request} from the MS or on the receipt of a packet fromits own IFQ for the MS (slot allocation is described in the next section).Information about the slot-frequency channel is written onto the MACheader of the {\em resource\_reply} packet and it is transmitted on slot 0of downlink frequency 0, to the appropriate MS.On receipt of a {\em resource\_reply}, an MS checks the slot-frequencychannel alloted to it and stores it in {\em tx\_chan[]} and {\emrx\_chan[]} for future reference. It then kills the wait timer; schedulesthe old buffered packet to be transmited on the appropriate slot-frequencyand unblocks the IFQ. Other waiting packets can now be passed down fromthe IFQ to the MAC and transmitted.In case the BS has a second {\em resource\_reply} message to betransmitted in slot 0 of the upcoming frame (this situation can arise whenthe BS receives a {\em resource\_request} (from an MS) and a packet destinedto a new MS (from its IFQ) in the same TDMA frame), thesecond reply is stored in a temporary buffer and transmitted on thenext free downlink slot0.\subsubsection{Resource Release}Since Internet traffic is mostly bursty, we have implemented a slotrelease mechanism for GPRS MS.  If the IFQ of the MS is empty and nopacket is transmitted or received for four TDMA frames while the MS isholding a channel, we initiate a {\em resource\_release}.  The MS clearsits {\em tx\_chan[]} and {\em rx\_chan[]} entries and sends a {\emresource\_release}. On receipt of a {\em resource\_release}, the BS purgesits {\em vlr\_.up\_table} and {\em vlr\_.down\_table} entries. Only an MScan initiate a {\em resource\_release}.If the MS later wants to restart transmission, we send another {\emresource\_request}. This request is treated on par with any other freshrequests by the BS. In the case of traffic from the BS to MS, the BS willallot fresh resources to the MS and send a {\em resource\_reply} informingthe MS.\subsection{Slot Handling}\subsubsection{Allocation}At the BS we maintain a table recording which Upslot/Downslot has beenalloted to which MS (in {\em vlr\_}, specifically {\em vlr\_.upslot[][]}and {\em vlr\_downslot[][]}). When the BS receives a {\emresource\_request} from an MS or a packet from its own IFQ (to be sent toan MS), it allocates the {\em first free slot} available to that MS. Thisis done in {\em slot\_allot()}. If the MS is a GPRS MS, a slot isallocated from the pool of GPRS slots, else from the pool of GSM slots. Bydefault, an MS is GPRS and four slots on each frequency are reserved forGPRS (this leaves only three slots on each frequency for GSM). Allocationis symmetric on the uplink and the downlink frequencies. Only single slotoperation is supported ie each MS can be alloted only one slot.\subsubsection{Release}Slot release is possible only with GPRS mobile nodes. We maintain arelease timer ({\em SlotReleaseTimer}) at the MS. On receiving a packet(in either direction) the MS checks the IFQ. If the IFQ is empty, the {\emSlotReleaseTimer} is started. It is reset if the MS gets another packet(in either direction) within four TDMA frames. Otherwise, on expiry of thetimer, the {\em releaseHandler()} is called.Currently, the value of four TDMA frames for the release timer is takenbased on simulations performed. It was found optimal in preventingspurious time-outs and avoiding waiting too long. However, the optimalvalue may differ according to traffic generation pattern and needs to befurther explored.\subsection{Dealing with Collisions}Since this is a reservation based slotted Aloha system, the only placecollisions can occur is during contention on the Packet Random AccessCHannel (ie slot 0 on uplink frequency 0) when more than one MS send a{\em resource\_request} at the same time. We use {\em chan0\_0} tomaintain the state information about the PRACH. In case of collision, thecolliding {\em resource\_request} packets are dropped by {\emrx\_from\_phy()} at the BS. The MS wait one TDMA frame for a reply. Sinceno reply is received, the MS set the {\em Backoff Timer} for a randominterval (generated using {\em Random::integer(k)}). On expiry this callsthe {\em backoffHandler()}, which then schedules another {\emresource\_request}.\subsection{Error model}The error model provided by {\it ns} can introduce errors into packetscreated by Agents like TCP or UDP. It cannot introduce errors at the lowerlayers. In order to test our acknowledgement mechanism, we introduce anerror model that produces random errors in (simulated) RLC PDUs ie forslot level transmissions.This error model (in {\em bs\_recv()})  marks a randomly chosen RLCfragment (either going up or down) as erroneous. This causes the packet tobe dropped at its destination. At each drop, we use {\emRandom::integer(error\_rate\_)} to decide the next drop.The user may choose to include this error model through {\em rlc\_error\_}in the OTcl script. The {\em error\_rate\_} can also be set by the userfrom the OTcl script.\subsection{Handling ARPs}At the start of a simulation, the first packet to be received at the Macof an MS is an ARP request. Though this is a broadcast message, it is nottransmitted directly, but resources are requested and the ARP request issent out only on the alloted slot-frequency channel. This is to preventother MS from receiving an ARP request from an MS. The BS however, goesahead and broadcasts the ARP request on the broadcast channel ie slot 0 ondownlink frequency 0.Also, in {\it ns}, a node sends an ARP request each time a packet isreceived at the LL, even though an ARP request has already been sent andit is waiting for a reply. To prevent our MAC from transmitting suchduplicate ARP requests and wasting precious radio-resources, we simplydrop duplicate ARPs in {\it ms\_recv()}\subsection{MacGprs class in C++}The elements of the code - the storage structures, the methods and thetimers used - are as follows\subsubsection{Storage Structures}In this section, we summarize the important storage structures used.\noindent\begin{itemize}\item At the MS\end{itemize}{\tt  Packet *pktTx[i]}: pointer to the packet  to be sent in Upslot i {\tt  Packet *pktRx[i]}: pointer to the packet received in Downslot i 										{\tt  int tx\_chan[i]}: which channel should the MS transmit on in Upslot i {\tt  int rx\_chan[i]}: which channel should the MS listen to in Downslot i \ \\Note: {\tt  tx\_chan[0]} = 0 for Random Access \indent {\tt  rx\_chan[0]}=0  for  Broadcasts and other messages from BS This structure also allows for multi-slot allocation to be included later.  \noindent\begin{itemize}\item At the BS\end{itemize}  {\tt  Packet *txQ[i][j]}: pointer to the packet to be sent in Downslot j, frequency i  {\tt  Packet *rxQ[i][j]}: pointer to the packet received in Upslot j, frequency i {\tt  int vlr\_.hier\_addr\_[i]}: hierarchical address of MS with  MAC index i {\tt  int vlr\_.up\_table[i][j]}: MAC index of MS alloted Upslot j on frequency i {\tt  int vlr\_.down\_table[i][j]}: MAC index of MS alloted Downslot j on frequency i \ \\{\bf Note:}These structures have to be unique for each BS. Since {\it ns} doesnot currently have a separate BS node at the C++ level ({\it ns}configures a node as BS only at the OTcl level), these structures hadto be made static. This limits our simulator to supporting just oneBS and consequently, just one cell.\subsubsection{Methods}The methods created for the class Mac/GPRS are\begin{itemize}{\tt\item recv(Packet *p, Handler *h) : the entry point for the MAC\item ms\_recv(Packet *p, Handler *h) : packet processing at the MS \item bs\_recv(Packet *p, Handler *h) :  processing a packet  at the BS\item slot\_allot(int ms\_, int \&freq, int \&slot) : allot a slot to ms\_,return\\ values through \&freq, \&slot\item send\_res\_reply (int dst, int freq, int slot) : creating a resource\_reply packet, to be sent on slot/freq  \item send\_res\_request () : creating a resource\_reply packet\item send\_let\_go() : creating a resource\_release packet\item downslotHandler(Event *e) : actions at the end of every down slot\item upslotHandler(Event *e) : actions at the end of every up slot\item sendHandler(Event *e) : actions after packet has been transmitted\item recvHandler(Event *e) :  actions after packet has been completelyreceived.\item releaseHandler(void) : on the expiry of the slot release timer\item backoffHandler(void) : on the expiry of the back off timer  \item waitHandler(void) : on the expiry of the wait timer  \item radioSwitch(int i) : switching the radio on/off to conserve energy.\item rx\_from\_phy(Packet* p) : remove MAC headers, check for collisions\item rx\_from\_ll(Packet* p) : add MAC header\item fwd\_DATA\_to\_LL(Packet *p) : handle data according to type and passto \\ upper layer. \item tx\_onto\_PHY(Packet *p ) : transmit onto air interface}\end{itemize}\subsubsection{Timers}The following is a list of timers  used by the system\begin{itemize}\item Up-Slot Timer : clocks slots on the Uplink frequencies.\item Down-Slot Timer : clocks slots on the Downlink frequencies.    \item Packet Transmit Timer : times the transmission of a packet.\item Packet Receive Timer : keeps track while a packet is beingreceived.\item Wait Timer : the amount of time to wait for a {\em resource\_reply}.\item Backoff Timer : to back off for a random interval beforeretransmitting a {\em resource\_request}.\end{itemize}The psuedocode for the implementation is listed in Appendix II. Wedescribe the simulations performed using our extensions for GPRS in {\itns} in the next chapter. %\end{document}