11. WiMAX Module for ns-2 Simulator
The Network Simulator 2 (ns-2) is a popular and powerful simulation tool for the simulation of packet-switched networks, which provides substantial support for simulation of TCP, routing, and MAC protocols over wired and wireless networks, such as wireless LANs, mobile ad hoc networks (MANETs), and satellite communications, etc, and is widely used in both academia and industry. Although many protocol modules have been implemented in the ns-2, the IEEE 802.16 broadband wireless access networks (BWANs) or WiMAX module has not been contributed yet.
I have used, for my simulations, a simulator with the following structure.
11.1 Packets
WimaxBurstWiMAX mesh burst of MAC PDUs. A burst of PDUs is either a list of MAC PDUs, or a container for one MSH-DSCH message, according to the burst type.
If you want to copy a burst, then use the copy() function. On the other hand, the destructor can be used safely to delete a burst. In any case, the ns2 packets, nor the MSH-DSCH message, are not copied. If you really want to deallocate the ns2 packets, which are encapsulated into each SDU, you have to do it manually. The rationale behind this is that we want only one copy of each ns2 packet to travel from the source node to the destination, to save both memory (a packet) and time (copying a packet). However, care must be taken to destroy these objects. We assume that only the final recipient of the communication destroys ns2 packets, which should be safe enough with unicast communications.
Payload of the burst, depending on the burst type. Fields:
• List pdus_: list of PDUs if type is wimax::DATA.
• WimaxMshDsch* mshDsch_: pointer to the MSH-DSCH message if type is wimax::MSHDSCH. • double txtime_: transmission time of this burst in seconds, including preambles.
• bool error_: true if the whole burst is corrupt. • wimax::BurstProfile profile_: burst profile. • wimax::BurstType type_: PDU burst type. • unsigned int size_: size, in bytes.
• WimaxNodeId src_: source Node ID. WimaxSdu
Wimax Service Data Unit (SDU) is an ns2 packet plus traversed hops. Note that a WimaxSdu does not own its payload. Thus, the copy constructor and assignment operator only copy the pointer to the payload, which has to be freed only once.
Fields:
• Packet* payload_: IP datagram from ns2.
• WimaxNodeId hops_[]: array of the traversed hops. • unsigned int nhops_: number of hops traversed.
• double timestamp_: timestamp for statistics collection. WimaxMacHeader
Generic MAC header. Fields:
• bool crc_: CRC indicator. 1 bit.
• unsigned int length_: PDU length. 11 bits.
• bool fragmentation_: fragmentation subheader present. 1 bit. • bool gmsh_: grant management subheader present. 1 bit. • WimaxMeshCid meshCid_: mesh CID. 16 bits.
• WimaxCid cid_: PMP CID. 16 bits. This simulator is valid also for PMP.
• bool mesh_: true if the mesh subheader is present. This flag does not exist in a real network, where the device knows which kind of network (Mesh or PMP) it is being operated.
WimaxMeshCid
It contains destination neighbor Node ID, instead of the Link ID which has been negotiated during the initial network configuration (via MSH-NCFG messages). During normal operation, then, each node uses the mesh subheader plus Link ID information to derive the destination Node ID.
Since, the simulator do not simulate network configuration, there is no point in using the Link ID, which only incurs additional simulation overhead due to the lookup of:
(LinkID, src-NodeID) Æ dst-NodeID
Management broadcast messages IRL are identified through a 0xFF Link ID. We simply ignore this, and assume that all management CIDs are broadcast. This is safe, since the only management message that is simulated is MSH-DSCH, which is broadcast.
Fields:
• WimaxNodeId dst_: destination.
• unsigned char type_: PDU type, management or IP. 2 bits (1 is reserved). • unsigned char reliability_: 1 bit. ARQ enabled:
0x0: no.
0x2: up to four retransmissions allowed. • unsigned char priority_: priority/class. 3 bits. • unsigned char drop_: drop precedence. 2 bits. WimaxPdu
Wimax MAC Protocol Data Unit (PDU). It is an SDU plus MAC header plus fragmentation subheader. Instead, the mesh subheader is included directly. Of course, SDUs are not actually fragmented as IRL.
Fields:
• WimaxSdu* sdu_: SDU (or fragment thereof) encapsulated. • WimaxMacHeader hdr_: generic MAC header.
• WimaxBwReqHeader brHdr_: bandwidth request header.
• WimaxGmsh gmsh_: grant management subheader, if present (as specified in the MAC header). • WimaxNodeId nodeId_: in mesh subheader is the transmitter Node ID. 16 bits.
• bool error_: true if the content of this PDU is corrupt. • unsigned char type_: indicates the type of header. WimaxMshDsch
MSH-DSCH control message. The simulator assumes coordinated message scheduling. The maximum size is not enforced while adding new IEs. Thus, all the functions to add IEs return the size of the available space. Since IEs cannot be removed (unless you do it “manually” using the returned list, which you should do), the amount of available space should be checked before adding IEs using the appropriate functions. The same discussion on the Link ID of WimaxCid holds also for all the information elements defined here.
Fields:
• std::list<ReqIE> req_: list of requests. ReqIE: request data structure (3 bytes).
WimaxNodeId nodeId_: destination Node ID (IRL, Link ID). 8 bits. unsigned char level_: demand level. 8 bits.
Persistence persistence_: demand persistence. 3 bits. • std::list<AvlIE> avl_: list of availabilities.
Availability data structure (4 bytes).
unsigned int frame_: start frame number. IRL are 8 bits. Here is used the full frame number. unsigned char start_: minislot start. 8 bits.
unsigned char range_: minislot range. 7 bits. Direction direction_: direction. 2 bits. Persistence persistence_: persistence. 3 bits. unsigned char channel_: channel number. 4 bits. • std::list<GntIE> gnt_: list of grants.
Grant data structure (5 bytes).
WimaxNodeId nodeId_: destination Node ID (IRL, Link ID). 8 bits.
unsigned int frame_: start frame number. IRL are 8 bits. Here is used the full frame number. unsigned char start_: minislot start. 8 bits.
unsigned char range_: minislot range. 8 bits.
bool fromRequester_: direction. 1 bit. True if it is from requester to granter. Otherwise, false.
Persistence persistence_: persistence. 3 bits. unsigned char channel_: channel number. 4 bits. • std::list<NghIE> ngh_: list of neighbors.
Neighbor coordination IE (3 bytes).
WimaxNodeId nodeId_: Node ID. 8 bits. This field does not exist for information on itself. unsigned char nextXmtMx_: NextXmtMx. 3 bits.
unsigned char xmtHoldoffExponent_: XmtHoldoffExponent. 5 bits. unsigned int nextXmtTime_: Next transmit time. This does not exist IRL. • PathRT pathRT_: path packet for EBRP.
WimaxNodeId sender_: sender Node ID. 8 bits. WimaxNodeId receiver_: receiver Node ID. 8 bits. WimaxNodeId nextHop_: packet next hop. 8 bits. unsigned int nNodes_: number of nodes crossed. 8 bits.
unsigned int flowID_: flow identifier. 8 bits.
double packetdim_: packet dimension in bytes. 32 bits. double packetperiod_: packet period in seconds. 32 bits. double timerloc_: system parameter for TS. 16 bits.
double timerinst_: system parameter for TE. 16 bits.
double timerflow_: system parameter for TF. 16 bits.
double timerdummy_: system parameter for TD. 16 bits.
double time_: timestamp.
unsigned int timeid_: time identifier, used for statistical collection. • RsvRT rsvRT_: reservation packet for EBRP.
WimaxNodeId sender_: sender Node ID. 8 bits. WimaxNodeId receiver_: receiver Node ID. 8 bits. WimaxNodeId nextHop_: packet next hop. 8 bits. unsigned int nNodes_: number of nodes crossed. 8 bits.
std::vector<WimaxNodeId> crossNodes_: vector of crossed nodes. unsigned int flowID_: flow identifier. 8 bits.
double packetdim_: packet dimension in bytes. 32 bits. double packetperiod_: packet period in seconds. 32 bits.
unsigned int frame_: start frame number. IRL are 8 bits. Here we use the full frame number. std::vector <unsigned char> minislotid_: vector of minislot. 1 minislot = 8 bits.
unsigned char channel_: channel number. 4 bits. double timerloc_: system parameter for TS. 16 bits.
double timerinst_: system parameter for TE. 16 bits.
double timerflow_: system parameter for TF. 16 bits.
double timerdummy_: system parameter for TD. 16 bits.
double time_: timestamp.
unsigned int timeid_: time identifier, used for statistical collection. • CnfRT cnfRT_: confirmation packet for EBRP.
WimaxNodeId sender_: sender Node ID. 8 bits. WimaxNodeId receiver_: receiver Node ID. 8 bits. WimaxNodeId nextHop_: packet next hop. 8 bits. unsigned int flowID_: flow identifier. 8 bits.
• WimaxMacHeader hdr_: MAC header (always present). MSH-DSCH messages are never fragmented.
• WimaxNodeId src_: in mesh subheader is the transmitter Node ID. 16 bits. • unsigned int nseq_: sequence counter. 6 bits.
• unsigned int nreq_: number of requests. 4 bits. • unsigned int navl_: number of availabilities. 4 bits. • unsigned int ngnt_: number of grants. 6 bits.
• unsigned int nngh_: number of advertised neighbors, not including itself. 8 bits. • RT label_: distinguish the type of real time control packet.
• NghIE myself_: information on myself, about the distributed election mechanism.
• static AllocationType allocationType_: allocation type. Changed via allocationType(). Default is BASIC.
11.2 Physical
Layer
WimshPhyMib
Physical layer management information base. Field:
• double symDuration_: OFDM symbol duration in seconds. Set via Tcl command. • double frameDuration_: frame duration in seconds. Set via Tcl command.
• unsigned int symPerFrame_: number of OFDM symbols per frame. • unsigned int controlSlots_: number of control slots per frame. • unsigned int slotPerFrame_: number of minislots per frame. • unsigned int symPerSlot_: number of OFDM symbols per minislot. WimshPhy
Physical layer. Field:
• std::list <BurstDesc> rxBursts_: list of descriptors of received bursts to detect interference. Descriptor for each received burst, to detect interference.
WimaxNodeId src_: source node. WimaxNodeId dst_: destination node. double start_: Transmission start time. double finish_: Transmission finish time.
WimshChannel* channel_: pointer to the channel over which this burst was received. WimaxBurst* burst_: burst dispatched (neighbor only, otherwise null).
• WimaxMultiTimer<WimshPhy, WimaxBurst*> rxFinishTimes_: multi-timer for transmission finish times.
• WimshChannel* channel_: pointer to the channel to which the PHY is connected (either tx/rx). • WimshPhyMib* phyMib_: pointer to the PHY MIB.
• WimshMac* mac_: pointer to the MAC layer.
• WimshTopologySimple* topology_: pointer to the topology.
• double epsilon_: small amount of time that is used to check for transmission collision. This value should definitely be smaller than the duration of an OFDM symbol.
Functions:
• void setMode ( wimax::ChannelStatus s, WimshChannel* channel = 0 )
Switch the channel/mode used by this PHY. If no channel is specified, then only the mode is changed. If there is a channel switch or a tx/rx switch, then are dropped any burst which has not been dispatched yet.
• void sendBurst ( WimaxBurst* burst )
Send a burst to the current channel. Compute the burst duration, including physical preamble, if needed, and send the latter to the channel.
• void recvBurst (WimaxBurst* burst)
Receive a burst from the channel. Drop any corrupted PDU and then pass the PDUs to the MAC layer.
Handle the timer_ event. Get the burst with the earliest finish time. If this is from a neighbor of ours, then check whether there are ongoing communications which interfere with this one. If so, then set the error flag into the burst. In any case, pass the burst to the MAC layer. If this is not from a neighbor of ours, then just ignore the burst. The burst is also ignoring if there was a channel or tx/rx switch of the PHY during this burst's transmission.
WimshChannel
Physical channel. Each burst is delayed of the propagation time before being dispatched to all the PHYs that are currently listening to this channel. Note that the channel does not enforce that a PHY keeps listening to this channel for the whole burst duration.
Fields:
• std::map <WimshPhy*, wimax::ChannelStatus> phymap_: map of PHYs connected to this channel (transmission, receiver, or not connected).
• WimshTopologySimple* topology_: pointer to the topology.
• WimaxMultiTimer <WimshChannel, WimaxBurst*> timer_: timer to delay bursts of a propagation time.
• double propagation_: fixed propagation delay, in seconds. Initialized via Tcl command. • double errorData_: uniform error rate for DATA bursts.
• double errorCtrl_: uniform error rate for CONTROL bursts.
• RNG* rngErrorData_: random number generator for DATA errors. • RNG* rngErrorCtrl_: random number generator for CONTROL errors. • unsigned int uid_: channel identifier, used for statistics collection. Functions:
• void setMode ( WimshPhy* phy, wimax::ChannelStatus s ) Set the specified mode for a given PHY.
• wimax::ChannelStatus getMode ( WimshPhy* phy ) Get the specified mode for a given PHY.
• void recvBurst ( WimaxBurst* burst )
Receive a PDU burst from a PHY. Start the propagation timer. • void handle ( WimaxBurst* burst )
11.3 MAC
Layer
WimshMacMibWiMAX MAC management information base. Field:
• WimaxTimer <WimshMacMib> timer_: timer to count frames. • WimshPhyMib* phyMib_: pointer to the PHY MIB.
• unsigned int frame_: frame counter. There should be no wrap-around. 1 ms Æ 49 days.
• std::map <int, bool> flow2crc_: map from ns2 packet Flow ID to CRC indicator. This allows the user to specify via Tcl the presence of CRC at the 802.16 MAC layer on a flow by flow basis. The CRC is disabled by default.
• std::map<int, unsigned char> flow2prio_: map from ns2 packet Flow ID to 802.16 MAC priority. This allows the user to specify via Tcl the 802.16 MAC priorities of PDUs on a flow by flow basis. The priority if zero by default.
• std::map <int, unsigned char> flow2drop_: map from ns2 packet Flow ID to 802.16 MAC precedence. This allows the user to specify via Tcl the 802.16 MAC precedence of PDUs on a flow by flow basis. The precedence is zero by default.
• std::list< Link > linkList_: link list. Link structure:
WimaxNodeId src_: source node. WimaxNodeId dst_: destination node.
wimax::BurstProfile profile_: current burst profile.
WimshMac
WiMAX MAC layer. Field:
• WimshPhyMib* phyMib_: PHY MIB. Initialized via Tcl command. • WimshMacMib* macMib_: MAC MIB. Initialized via Tcl command. • LL* ll_: link layer. Initialized via Tcl command.
• WimshTopology* topology_: network topology. Initialized via Tcl command. • WimshScheduler* scheduler_: packet scheduler. Initialized via Tcl command.
• WimshSchedulerRT* schedulerRT_: packet scheduler for EBRP. Initialized via Tcl command. • std::map <WimaxNodeId, unsigned int> neigh2ndx_: map each neighbor to a local numerical
identifier for other structures. Initialized via the initialization() function from the topology. The “index” stored by this data structure can be seen as the Link ID in a real 802.16 system, which is chosen randomly (between 0 and 255) during the link establishment negotiation phase, which is not simulated.
• std::vector <WimaxNodeId> ndx2neigh_: map each neighbor local numerical identifier to the Node ID.
• std::vector <unsigned int> alpha_: array of alpha values, one for each neighbor. This data structure is initialized via the “profile” Tcl command. The entry i of this array stores the number of coded bytes that are conveyed by each OFDM symbol to transmit data from this node to the neighbor mapper to the index i via neigh2ndx_. The simulator assumes that the burst profile is bi-directional.
• std::vector <wimax::BurstProfile> profile_: array of burst profiles, one for each neighbor. This data structure is initialized via the “profile” Tcl command. The entry i of this array stores the burst profile used to transmit data from this node to the neighbor mapper to the index i via
neigh2ndx_.
• std::vector <WimshFragmentationBuffer*> fragbuf_: array of fragmentation buffers, one for each neighbor. This data structure is created by the initialize() function.
• std::vector <WimshFragmentationBuffer*> fragbufprio_: array of fragmentation buffers, one for each neighbor. This data structure is created by the initialize() function.
• std::vector<WimaxReassemblyBuffer*> reasbuf_: array of reassembly buffers, one for each neighbor. This data structure is created by the initialize() function.
• std::vector <WimaxReassemblyBuffer*> reasbufprio_: array of reassembly buffers for real time flow, one for each neighbor. This data structure is created by the initialize() function.
• std::vector <double> hNeigh_: array of estimated interval times between two consecutive opportunities.
• std::vector <double> hNeighLast_: last time that the neighbors sent an opportunity. • std::vector <WimaxNodeId> neighbors_: vector of neighbors.
• std::vector <unsigned int> groupElements_: list of number of element for group. • double hSelf_: my estimated interval time between two consecutive opportunities. • double hLast_: last time that this node sent an opportunity.
• double hEstCurr_: weight of the current sample for estimating H values. • double hEstPast_: weight of the past estimated value for estimating H values.
• std::vector <WimshPhy*> phy_: array of PHY. If more than 1, then the node is multiradio. Initialized via Tcl. During control frames, only one PHY can be used, even though there is more than one. We assume that phy_[0] is always used for that purpose.
• std::vector <WimshChannel*> channel_: array of the available channels. Initialized via Tcl. The list of available channels is the same for all the 802.16 nodes in the same network. Channels are identified IRL using a numerical identifier from 0 to 15 (4 bits), which are used in bandwidth availabilities/grants. We do not map the channel pointers to the numerical identifiers, since we assume that all nodes have the same list of channels. Thus, the channel identifier is simply the array entry index. If there are multiple channels, then the control channel is iterated at the start of each frame.
• WimshBwManager* bwmanager_: bandwidth request manager. • WimshManagerRT* managerRT_: EBRP manager.
• WimshForwarding* forwarding_: forwarding module.
• WimshCoordinator* coordinator_: distributed election coordination module. • WimaxNodeId nodeId_: Node ID. It is equal to the ns2 Node ID.
• Matrix < unsigned int > groupOpt_: matrix of groups makes by optimum algorithm. • Matrix < unsigned int > groupEur_: matrix of groups makes by heuristic algorithm. • unsigned int nneighs_: number of neighbors of this node.
Enumerator:
• enum {BE, RT}: priority, best effort or real time. Functions:
• void recvPacket ( Packet* pkt )
Receive an IP datagram from upper layer (LL). • void recvSdu ( WimaxSdu* sdu )
Receive a MAC SDU. SDUs are either IP datagrams received from LL (function recvPacket) encapsulated by the MAC, or SDUs received from the reassembly buffers.
Receive a MAC SDU EBRP. SDUs are either IP datagrams received from LL (function
recvPacket) encapsulated by the MAC, or SDUs received from the reassembly buffers.
• void recvMshDsch ( WimaxMshDsch* dsch, double txtime ) Receive an MSH-DSCH.
• void recvBurst ( WimaxBurst* burst )
Receive a burst, either control or data, from PHY. • void opportunity ( WimaxMshDsch* dsch )
Receive a partial MSH-DSCH from the coordinator. The coordinator has just allocated a new MSH-DSCH, containing the information about the distributed election algorithms of neighbors. We now pass this MSH-DSCH message to the bandwidth manager, which fills the information elements about bandwidth request/grants, and then send it to the PHY layer.
• void setControlChannel ( wimax::ChannelStatus s )
Set the control PHY/channel to the specified mode. The standard specifies that all nodes in the network use the same channel to transmit control messages, so that all nodes in the neighborhood can hear them. However it does not specify which of the available channel is used to this purpose. Every node uses channel number 0, and transmits using the only available physical interface (at the moment, the implementation of this MAC layer does not support multiple radios).
• void receive ( unsigned int channel )
Receive data from a given channel. Single-radio only.
• void transmit ( unsigned int range, WimaxNodeId dst, unsigned int channel ) Transmit data over a given channel. Single-radio only.
• void transmitRT ( unsigned int range, WimaxNodeId dst, unsigned int channel ) Transmit real time data over a given channel. Single-radio only.
• unsigned int startframe ( std::vector <unsigned char> slot )
Return the frame from which to depart for allocate, this function is used by EBRP. • void initialize ()
Initialize MAC data structures, provided that all objects are defined.
WimshCoordinator
Abstract class for a distributed election coordinator. Note that slots are number from 0 to
(MSH-CTRL-LEN - 1).
Fields:
• WimshMac* mac_: pointer to the MAC object.
• WimaxTimer <WimshCoordinator> timer_: expire each new transmission opportunity. • unsigned int nextSlot_: next opportunity slot.
• unsigned int nextFrame_: next opportunity frame number. Functions:
• virtual void recvMshDsch ( WimaxMshDsch* dsch, double txtime = 0 ) Get an MSH-DSCH message from the MAC. The message is not freed. • virtual void handle ()
Timer handler.
This handler is called in any of the following events: Frame start time.
End of the control subframe.
End of the transmission opportunity. • virtual void election ()
Election procedure called by handle().
• virtual void fillSelf ( WimaxMshDsch* dsch ) Fill the IE about myself.
• virtual void fillNeighbors ( WimaxMshDsch* dsch ) Fill the IEs about my neighbors.
WimshCoordinatorStandard
802.16 standard coordinator. Implements the 802.16 standard election mechanism modified to avoid collision of requests. Two modifications are implemented.
• In XMTAWARE mode, the standard 802.16 MAC protocol is modified to make SSs transmit the
NextXmtTime information.
• In XMTUNAWARE mode, the election mechanism is performed in the worst case: The EarliestSubsequentXmtTime = holdOffTime + xmtTimeWindow lower bound. Two-hop neighbors are always considered competing nodes.
Fields:
• enum { XMTAWARE = 0, XMTUNAWARE } type_: coordination type.
Fixed mode: each opportunity is scheduled at the i-th opportunity (where i = slot_) of frame
f = frame_ * k, with k = 0, 1, ...
Moving mode: there is a period of period_ control slots, not necessarily aligned with the frame boundaries. The first opportunity is set to the value of slot_. The subsequent opportunities are k + slot_ modulo period_.
• WimshPhyMib* phyMib_: PHY MIB.
• unsigned int nextXmtTime_: next transmit time. • unsigned short nextXmtMx_: next transmit mx. • unsigned short holdHoffExp_: holdoff exponent.
• int maxAdvertisedNeighbors_: maximum number of advertised neighbors. A negative value means that the maximum number is limited by the control slot size only.
• std::list <NeighInfo> neighborsList_: list of neighbors; this list is used during the mesh election procedure. Neighbors must be sorted in increasing nextXmtTime_. The < operator in the struct
NeighInfo has been redefined for that purpose.
NeighInfo fields:
unsigned nextXmtTime_: next transmit time. unsigned short nextXmtMx_: next transmit mx. unsigned short holdHoffExp_: holdoff exponent.
unsigned int earlSubXmtTime_: earliest subsequent xmt time. WimaxNodeId nodeID_: Node ID.
unsigned short nhop_: first hop or second hop neighbour.
bool competing_: tell if the node is competing for the current slot. unsigned int timeStamp_: time stamp update.
• std::map <WimaxNodeId, NeighInfo*> neighborsMap_: map to neighbor list. This map is used to optimize the scan of the neighbor list.
• bool maxClique_: true if this node belongs to the maximum clique in the conflict graph. Functions:
Ignore MSH-DSCH message from the MAC. • void election ()
Election procedure called by handle (). • void fillSelf ( WimaxMshDsch* dsch )
Fill the IE about myself with scheduling information. • void fillNeighbors ( WimaxMshDsch* dsch )
Fill the IEs about my neighbors with scheduling information. • void start ()
Start the timer the first time. • void competition ()
Competition procedure. Run the standard mesh election procedure as specified in IEEE 802.16-2004 standard, Section 6.3.7.5.5.6 pp. 159-160; nextXmtTime_ is filled with the slot number relative to the node's nextXmtTime.
• void competingNodes ( unsigned int TempXmtTime ) Find competing node given a certain XmtTime.
• bool meshElection ( unsigned int TempXmtTime, short unsigned int nodeID )
Execute the mesh election procedure. This function is identical to that in the standard p. 160.
WimshForwarding
Abstract class for the forwarding module in 802.16. Fields:
• WimshMac* mac_: pointer to the MAC layer.
• WimshTopology* topology_: pointer to the topology. Functions:
• virtual WimaxNodeId nextHop ( WimaxSdu* sdu ) Get the next-hop of an SDU.
• virtual void recvMshDsch ( WimaxMshDsch* dsch ) Receive the control message.
• virtual void profile ()
The burst profile of a link has changed.
WimshForwardingSpf
Implement the shortest-path-first algorithm. Functions:
• WimaxNodeId nextHop ( WimaxSdu* sdu )
Get the next-hop of an SDU, based on the shortest-path policy. • void recvMshDsch ( WimaxMshDsch* dsch )
Do nothing. • void profile ()
WimshFwdOppNodeMib
WiMAX Node management information base for opportunistic forwarding. Fields:
• std::map <WimaxNodeId, LinkInfo> links_: links map where destination node is the key. It contains all the necessary information for characterizing a link.
Link information fields:
WimaxNodeId dst_: destination node.
double linkRate_: link rate. The link rate is computed given the number of bytes per slot divided by the slot time.
double reqAmount_: actual amount of request issued by the source node in number of slot. double gntAmount_: actual amount of grants issued by the source node in number of slot. wimax::BurstProfile burstProfile_: current burst profile.
• double nodeLoad_: node estimated load. Node load is estimated by adding a new sample to the average each sampling interval. A sample is computed by summing up all the request and grants normalized to the link rate.
• WimaxNodeId nodeID_: Node ID. Functions:
• void addRequestORGrant ( WimaxNodeId dst, unsigned int amount, bool what ) Add a new request OR grant amount:
0: request. 1: grant.
• void addSample ( const float chi, const float beta )
Add a new sample to the node load average. The new sample is computed and then added to the average.
WimshForwardingOpp Fields:
• std::list <WimshFwdOppNodeMib> neighborList_: neighbor node info map. This list holds all the necessary information to keep track of neighbors nodes' estimated state.
• std::map <WimaxNodeId, std::vector <wimax::NextHopInfo> > destinationMap_: this Map contains for each destination all the possible next-hop and the number of hop to the destination. • float chi_: constant to weight, the contribute of grants to the link cost.
• float beta_: constant to weight, the contribute of a new sample to the node load.
• unsigned int maxNumHops_: maximum number of hop threshold. This is used to avoid very long path. If 0 the amount is infinite.
• WimaxMultiTimer <WimshForwardingOpp, bool> timer_: timer for updating burst profiles (0) and sampling (1).
• unsigned int samplingPeriod_: sampling node load period in number of frames. • unsigned int profileUpdatePeriod_: profile update period in number of frames. Functions:
• WimaxNodeId nextHop ( WimaxSdu* sdu ) Get the next-hop of an SDU.
• void recvMshDsch ( WimaxMshDsch* dsch ) Receive the control messages.
• void handle ( bool what )
Handle the events of timer expiration Timer expiration events are: Sampling node load: what is equal to 1.
Update burst profiles: what is equal to 0. • void start ()
11.4 Topology
WimshTopology
Abstract topology class for WiMAX networks.
WimshTopologySimple
Simple topology for WiMAX networks, where nodes do not have an explicit spatial location (i.e. coordinates). Topology is based on logical links between nodes, and it is represented as a connectivity matrix, where the vertices are nodes and the edges are links, and a conflict matrix, where vertices are links and edges are conflicts. Additionally, an all-pairs-shortest-path matrix is computed, so that the MAC/routing layers can query the topology to know the shortest path to a destination.
Fields:
• Matrix <unsigned int> connectivity_: connectivity graph. Element (i, j) is either zero (i.e. no direct communication is possible between nodes i and j) or it contains the link identifier used in the conflict matrix.
• std::vector <Link> links_: link vector. Hold all links in the topology. The vector index is assumed to be the name of the vector.
Link structure:
WimaxNodeId src_: source Node ID. WimaxNodeId dst_: destination Node ID.
• Matrix <bool> conflict_: conflict graph. Two links (a, b) and (x, y) interfere if and only if a is equal to x or a is equal to y or b is equal to x or b is equal to y or there exists at least 1 link between the two pairs.
• Matrix <unsigned int> groupOpt_: matrix of groups computes through optimum algorithm. • Matrix <unsigned int> groupEur_: matrix of groups computes through heuristic algorithm. • unsigned int grouptype_: type of groups.
• const char* namefileEur_: heuristic groups file name. Initialized via Tcl command. The first simulation computes groups and writes these in namefileEur_ file; next simulation read groups in this file.
• const char* namefileOpt_: optimum groups file name. Initialized via Tcl command. The first simulation computes groups and writes these in namefileOpt_ file; next simulation read groups in this file.
• const char* numEur_: name of file that contains number of heuristic groups and the number of their elements.
• const char* numOpt_: name of file that contains number of optimum groups and the number of their elements.
Functions:
• unsigned int numHops ( WimaxNodeId x, WimaxNodeId y ) Return number of hops between x and y.
• void getGroupOpt ( Matrix <unsigned int>& gO ) Return the groups compute with optimum algorithm. • void getGroupEur ( Matrix <unsigned int >& gE )
• unsigned int groupType () Return groups type.
• void computeGroupsOpt ()
Compute the groups with algorithm for colouring a graph. This algorithm use conflict_ matrix. • void computeGroupsEur ()
Compute the groups with heuristic algorithm. The groups contain links that don't interfere if transmit together.
11.5 Scheduler
Figure 11.1 – Scheduler.
WimshScheduler
Abstract class for an 802.16 packet scheduler.
Each MAC has one WimshScheduler object, which receives and stores MAC PDUs from the MAC itself. We assume that the MAC already filled the following MAC header fields:
• Length.
• Src/dst Node ID. • CRC.
• Priority. • Precedence.
The fragmentation subheader will be added if needed by the WimshFragmentationBuffer object. This scheduler is used for best effort flows.
Filed:
• WimshMac* mac_: pointer to the MAC layer.
• unsigned int bufSize_: cumulative occupancy in bytes of the FIFO queues. Must be updated by the functions of derived classes. For instance, it may be used to drop packets.
• unsigned int maxBufSize_: maximum buffer size in bytes. Set by the MAC via Tcl command. Functions:
• virtual void addPdu (WimaxPdu* pdu) Adds a MAC PDU to this object.
• virtual void schedule (WimshFragmentationBuffer& frag, WimaxNodeId dst) Schedule a new data burst to a neighbor.
WimshSchedulerFifo
FIFO packet scheduler. MAC PDUs are stored in several FIFO queues, on a per destination Node ID basis.
Fields:
• std::vector <std::queue <WimaxPdu*> > buffer_: vector of FIFO queues of MAC PDUs. • std::vector <unsigned int> size_: occupancy in bytes of each FIFO queue.
Functions:
Adds a MAC PDU to this object.
• void schedule ( WimshFragmentationBuffer& frag, WimaxNodeId dst ) Schedule a new data burst to a neighbor.
WimshSchedulerFairRR
Fair Round Robin packet scheduler. Fields:
• std::vector <LinkDesc> link_: array of link descriptors, one for each neighbor. Initialized by the MAC.
Link descriptor contains the packet queues, one for each end-to-end destination and related data structures.
Fields:
unsigned int size_: buffer occupancy of this link, in bytes.
CircularList <FlowDesc> rr_: round robin list of flow descriptors, i.e. packet queues. Flow descriptor contains the packet queue and related information used for identify a traffic flow (source and destination Node ID's) and for scheduling (deficit counter). The quantum is computed as the roundDuration_ weighted on the number of traffic flows in the round-robin list of this link.
Fields:
→ WimaxNodeId src_: source Node ID. → WimaxNodeId dst_: destination Node ID. → unsigned int deficit_: deficit counter, in bytes. → unsigned int size_: buffer occupancy, in bytes.
std::queue <WimaxPdu*> queue_: packet queue to go to the destination dst_. • unsigned int roundDuration_: round-robin duration, in bytes. Set via Tcl.
• bool unfinishedRound_: true if there is a pending DRR round. If a flow cannot make up its deficit because there is no more spare room into the burst of PDUs under service, not due to the packet size being larger than its deficit, then the DRR service of this flow is not complete. In this case, unfinishedRound_ is true, and the current flow is pointer by the current round-robin pointer in the active list.
• BufferSharingMode bufferSharingMode_: buffer sharing mode. Default is SHARED. Functions:
• void addPdu ( WimaxPdu* pdu ) Adds a MAC PDU to this object.
• void schedule ( WimshFragmentationBuffer& frag, WimaxNodeId dst ) Schedule a new data burst to a neighbor.
• void drop ( WimaxPdu* pdu )
Drop a PDU (by deallocating PDU/SDU/IP).
WimshSchedulerRT
Real time packet scheduler. This is the scheduler used by EBRP. Fields:
• WimshMac* mac_: pointer to the MAC layer.
• unsigned int maxBufSize_: maximum buffer size in bytes. Set by the MAC via Tcl command. • std::vector <LinkDesc> link_: array of link descriptors, one for each neighbor. Initialized by the
MAC.
Link descriptor contains the packet queues, one for each end-to-end destination and related data structures.
unsigned int size_: buffer occupancy of this link, in bytes.
CircularList <unsigned int> rr_: round robin list of active flows. Each element is the Flow ID for a flow with packets.
std::map <unsigned int, struct FlowDesc> flowdescriptor_: flows map where Flow ID is the key. This map is used for packet scheduling, contains the packet queue and related information used for identify a traffic flow.
Flow descriptor fields:
WimaxNodeId sender_: sender Node ID. WimaxNodeId receiver_: receiver Node ID. unsigned int flowID_: Flow ID.
unsigned int deficit_: deficit counter, in bytes. double dim_: packet dimension.
double per_: packet periodicity.
unsigned int weight_: weight about a flow, in bytes. unsigned int size_: buffer occupancy, in bytes.
std::queue <WimaxPdu*> queue_: packet queue about a Flow ID.
• bool unfinishedRound_: true if there is a pending DRR round. If a flow cannot make up its deficit because there is no more spare room into the burst of PDUs under service, not due to the packet size being larger than its deficit, then the DRR service of this flow is not complete. In this case, unfinishedRound_ is true, and the current flow is pointer.
Functions:
• void addflow ( RTDesc desc )
Add flow descriptor in link_ and call computeweight (). • void removeflow ( unsigned int flowId, WimaxNodeId ndx )
1. Remove flow descriptor in link_. 2. Call computeweight ()
3. Remove rr element with the same Flow ID. • void addPdu (WimaxPdu* pdu)
Adds a MAC PDU to this object.
• void schedule ( WimshFragmentationBuffer& frag, WimaxNodeId dst ) Schedule PDUs directed to the specified neighbor on a DRR fashion. • unsigned int neighbor ( unsigned ndx )
Return the size, in bytes, of the queue to a neighbor (by neighbor node index). • void drop ( WimaxPdu* pdu )
Drop a PDU (by deallocating PDU/SDU/IP). • void computeweight ( unsigned int ndx )
11.6 Bandwidth
Manager
Figure 11.2 – WimshBwManager.
WimshBwManager
Abstract class for a bandwidth manager in 802.16. Single-radio only. Fields:
• WimshMac* mac_: pointer to the MAC layer.
• WimaxTimer <WimshBwManager> timer_: timer to schedule bandwidth manager events.
• std::vector <std::bitset <MAX_SLOTS> > grants_: array of bit maps representing granted minislots within frames. When the minislot is not granted for transmission, the node moves to receive mode. The channel used for both reception and transmission is specified in the channel_ array.
Note that there is the following (bad) trick. The elements in the channel_ array are initialized to “zero” and those in the grants_ array to “receive”. Therefore, whenever a node does not send a confirmation (i.e. it does not use that slot for transmission) and does not receive a confirmation addressed to itself (i.e. it does not receive from a neighbor in that slot) then the slot is automatically used for reception from the “zero” channel, which is the control channel. This allows for uncoordinated scheduling to be implemented without any modification, but only works provided that the control channel used by the MAC is always “zero”. The F-th entry of this data structure is reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame at the end of each frame.
• std::vector <std::vector <WimaxNodeId> > dst_: array of vectors representing the grants' destinations.
• std::vector <std::vector <unsigned int> > channel_: array of vectors representing the channel identifiers.
• std::vector <std::vector <unsigned int> > prio_: array of vectors representing the flow priority. • unsigned int lastSlot_: next slot to be served.
Functions:
• virtual void recvMshDsch ( WimaxMshDsch* dsch )
Get an MSH-DSCH message from a neighbor, which is not deallocated. • virtual void schedule ( WimaxMshDsch* dsch )
Schedule bandwidth into the following MSH-DSCH message. Some fields have been already filled by the coordinator.
• virtual void backlog ( WimaxNodeId src, WimaxNodeId dst, WimaxNodeId nexthop, unsigned
int bytes )
Indicate some additional backlog of an end-to-end flow.
• virtual void backlog ( WimaxNodeId nexthop, unsigned int bytes ) Indicate some additional backlog of an end-to-end flow.
Indicate some additional on a link towards a neighbor.
• virtual void received ( WimaxNodeId src, WimaxNodeId dst, WimaxNodeId source, unsigned int
bytes )
Indicate some data was received.
• void flowrtReleaseAllocation ( std::vector <bool> busy, std::vector <WimaxNodeId> dst ) Release and allocation of minislots for real time flows. This function is used by EBRP.
WimshWeightManager
Object which computes/stores he weight of end-to-end flows. We define an end-to-end flow as a stream of IP datagrams from a source to a destination. For instance, FTP flows (even though uni-directional in ns2) consist of two flows each. On the other hand, many application sending data to the same destination node (i.e. final destination, not to the same next-hop neighbor of the source node) are treated as a single flow.
Fields:
• DescList in_: list of flow descriptors for incoming flows. • DescList out_: list of flow descriptors for outgoing flows.
Where:
typedef std::list <FlowDesc> DescList
This is a flow descriptor used for any outgoing flows, for which we always know both source and destination and an incoming flow, provided that are received some packets.
FlowDesc fields:
WimaxNodeId src_: source Node ID (i.e. the flow source).
WimaxNodeId dst_: destination Node ID (i.e. the flow destination).
NdxList ndx_: list of neighbors to which we send (from which we receive). With single-path routing the list holds at most one element. Also, incomplete elements only have one element.
unsigned int ndxSize_: size of the list of neighbors.
bool incomplete_: true if the information is not complete. When a bandwidth request is received, then the node does not know the destination/source of the packets that will be conveyed. However, if we assigned a weight to nodes that have already sent packets, then we would end up never assigning bandwidth to new flows (i.e. deadlock at startup). However, we mark this descriptor as “incomplete”, so that we will remove it as soon as the first packet from the sending node is received.
double lastRcvd_: last time a packet has been received, used to invalidate flows. This field is not meaningful for incomplete flow descriptors.
• unsigned int nFlowDesc_: sum of the number of elements in the flow descriptors' lists. • std::vector <double> weightIn_: array of weights about input links.
• std::vector <double> weightOut_: array of weights about output links. • WimshMac* mac_: pointer to the MAC layer.
• WimaxTimer <WimshWeightManager> timer_: timer to clean up stale weights.
• double interval_: stale weights cleaning interval. Set via the interval() function. If this function is not called, or if it sets the interval to zero, then stale weights are never removed. If the timer has not been started, then subsequent calls to the interval() to change the interval value will have no effect. Furthermore, if the timer is stopped (i.e. by setting a value smaller than or equal to zero, then it cannot be restarted).
• bool normalizeProfile_: true if weights are normalized based on the burst profiles.
Functions:
• void flow ( WimaxNodeId src, WimaxNodeId dst, unsigned int ndx, wimax::LinkDirection dir ) Set a, perhaps new, flow as active. Adding a flow descriptor also removes the corresponding incomplete flow descriptor into the list, if any. If a new element is added to the list of descriptors, then weights are recomputed.
• void flow ( unsigned int ndx, wimax::LinkDirection dir )
Set a, perhaps new, incomplete flow as active. If an element, either complete or incomplete, associated to the same link already exists into the list, then the incomplete flow is not added. If a new element is added to the list of descriptors, then weights are recomputed.
WimshBwManagerRoundRobin
Round robin bandwidth manager for 802.16. Single channel only. We assume that bandwidth is never granted in the past. However, we assume that bandwidth can be confirmed in the past.
Fields:
• std::vector <unsigned int> req_in_: cumulative size, in minislots, of the bandwidth requests received. This data structure is used when granting bandwidth to neighbors.
• std::vector <unsigned int> gnt_in_: cumulative size, in minislots, of the bandwidth grants sent. This data structure is used when granting bandwidth to neighbors.
• std::vector <unsigned int> cnf_in_: cumulative size, in minislots, of the bandwidth confirmations received. This data structure is used when granting bandwidth to neighbors.
• std::vector <unsigned int> req_out_: cumulative size, in minislots, of the bandwidth requests sent. This data structure, at the moment, is write-only.
• std::vector <unsigned int> gnt_out_: cumulative size, in minislots, of the bandwidth grants received. This data structure, at the moment, is write-only.
• std::vector <unsigned int> cnf_out_: cumulative size, in minislots, of the bandwidth confirmations sent. This data structure, at the moment, is write-only.
• std::vector <bool> rcvCnf_: true if are received a confirmation from a node before are sent it a grant.
• std::vector <std::vector <std::bitset <MAX_SLOTS> > > neigh_tx_unavl_: neighbors' unavailability to transmit. This is a vector of a two-dimension bitmap. Each entry of the vector is relevant to a neighbor i. Each row of the two-dimension bitmap is relevant to a frame f. Each column of the two-dimension bitmap is relevant to a minislot m. The bit is set (i.e. true) if this node's neighbor with index i cannot transmit in the m-th minislot of frame f. This data structure is used when granting bandwidth to neighbors. The F-th entry for each neighbor of this data structure is reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame, at the end of each frame.
• std::vector <std::bitset <MAX_SLOTS> > self_rx_unavl_: two-dimension bitmap representing the nodes unavailability to receive. The bit self_rx_unavl_[F][S] is set (i.e. true) if this node cannot receive in the minislot S of frame F. This data structure is used when granting bandwidth to neighbors. The F-th entry of this data structure is reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame at the end of each frame.
• std::vector <std::bitset <MAX_SLOTS> > self_tx_unavl_: two-dimension bitmap representing the nodes unavailability to transmit. The bit self_tx_unavl_[F][S] is set (i.e. true) if this node cannot transmit in the minislot S of frame F. This data structure is used when confirming bandwidth. The F-th entry of this data structure is reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame at the end of each frame.
• std::vector <std::bitset <MAX_SLOTS> > unconfirmedSlots_: unconfirmed slots unavailable for reception. This is updated when a granted addressed to this node is received. It is used to confirm only minislots that have not been reserved by other nodes. The F-th entry of this data structure is reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame at the end of each frame.
• std::list <WimaxMshDsch::GntIE> unconfirmed_: list of unconfirmed grants directed to this node.
• std::list <WimaxMshDsch::AvlIE> availabilities_: list of pending availabilities to send out. • std::vector <unsigned int> backlog_: new backlog indicated by the scheduler.
• bool avlAdvertise_: true if availabilities have to be advertised. • bool regrantEnabled_: true if unconfirmed bandwidth is regranted.
• unsigned int lastRequest_: this is the last neighbor for which bandwidth was requested. • unsigned int lastGrant_: this is the last neighbor to which bandwidth has been granted.
• unsigned int regrantHorizon_: number of frames after the grant horizon used eligible for regranting. Changed via Tcl. Default value equal to 1.
• bool someFairness_: true if we want to be a bit fair while granting bandwidth. Functions:
• void recvMshDsch ( WimaxMshDsch* dsch )
Get an MSH-DSCH message from a neighbor, which is not deallocated. • void schedule ( WimaxMshDsch* dsch )
Schedule bandwidth into the following MSH-DSCH message. Some fields have been already filled by the coordinator.
• void backlog ( WimaxNodeId src, WimaxNodeId dst, WimaxNodeId nexthop, unsigned int bytes) Update the backlog_ data structures of the next hop.
• void backlog ( WimaxNodeId nexthop, unsigned int bytes ) Update the backlog_ data structures of the next hop. • void rcvGrants ( WimaxMshDsch* dsch )
Decode grants/confirmations from an incoming MSH-DSCH message. There are the following cases:
For each grant addressed to this node, a confirmation is added to the pending list of confirmations (managed by confirm ()), the granted minislots are marked as unconfirmed unavailable (in the unconfirmedSlots_ bitmap) and the amount of bandwidth granted by a neighbor is updated.
For each grant not addressed to this node, an unavailability is added to the pending list of availabilities (managed by availabilities ()).
For each confirmation addressed to this node, update the cnf_in_ data structure.
For each confirmation addressed to a node which is not in this node's first-hop neighborhood, mark the confirmed minislots as unavailable for reception from this node. • void rcvAvailabilities ( WimaxMshDsch* dsch )
Decode availabilities from an incoming MSH-DSCH message. We update the status of
neigh_tx_unavail_ based on the received availabilities.
• void rcvRequests ( WimaxMshDsch* dsch )
Decode requests from an incoming MSH-DSCH message. For each request addressed to this node, add the number of minislots requested to the req_in_ data structure.
• void confirm ( WimaxMshDsch* dsch ) Confirm pending grants.
For each confirmation in the unconfirmed list:
Try to send as many confirmations as possible, provided that the slots that have been granted are still available for transmission by this node (via the self_tx_unaval_ bitmap).
Update the status of the cnf_out_ data structure
Set the minislots reserved for transmission at this node, which will be used by the handle() function to trigger the packet scheduler at the MAC layer. Both self_tx_unavl_ and
self_tx_unavl_ are updated.
Note that the cnf_out_ data structure is updated with the number of minislots actually confirmed which will be used for transmission.
• void availabilities ( WimaxMshDsch* dsch ) Advertise pending availabilities.
• void request ( WimaxMshDsch* dsch ) Request bandwidth.
• void grant ( WimaxMshDsch* dsch )
Grant bandwidth. Let H be the average number of frames between two consecutive transmission opportunities of this node, and H' the same measure for the node to which we are currently granting bandwidth. The time window over which we grant bandwidth is NOW + [H',H + 2H']. The granted minislots are marked as unavailable for reception. The amount of granted minislots is updated.
• unsigned int fillReqIE ( WimaxMshDsch::ReqIE& ie )
Fill the <level, persistence> fields of the ReqIE. Return the number of minislots requested. • void realPersistence ( unsigned int start, WimaxMshDsch::Persistence pers, unsigned int&
realStart, unsigned int& range )
Return the real number of frames for which the persistence is relevant. Since the frame number never wraps around, but the frame index into the data structures does, if a stale message is received, we have to update only the frames that are actually relevant. In other words, the simulator does not want to update frames in the past, because it would overwrite information that will be used in the future (in a circular manner).
• WimaxMshDsch::GntIE grantFit ( unsigned int ndx, unsigned int maxSlots, unsigned int
minFrame, unsigned int maxFrame )
Find a first-fit to grant bandwidth to a neighbor. The first fit is searched starting from the first minislot of the first frame. Persistence is always 1-frame. If it is not possible to schedule bandwidth to ndx in the specified time window, then a grant with an empty minislot range is returned.
• void confFit ( std::vector <std::bitset <MAX_SLOTS> >& map, unsigned int fstart, unsigned
int frange, unsigned int mstart, unsigned int mrange, WimaxMshDsch::GntIE& gnt, bool value )
Find a first-fit to confirm bandwidth.
WimshBwManagerFairRR
Fair round robin bandwidth manager for 802.16. Single-radio only. Fields:
• std::vector <NeighDesc> neigh_: array of neighbor descriptors for bandwidth requesting/granting.
NeighDesc fields:
unsigned int req_in_: cumulative size, in bytes, of the bandwidth requests received. This data structure is used when granting bandwidth to neighbors.
unsigned int gnt_in_: cumulative size, in bytes, of the bandwidth grants sent. This data structure is used when granting bandwidth to neighbors.
unsigned int cnf_in_: cumulative size, in bytes, of the bandwidth confirmations received. This data structure is used when granting bandwidth to neighbors.
unsigned int gnt_out_: cumulative size, in bytes, of the bandwidth grants received. unsigned int cnf_out_: cumulative size, in bytes, of the bandwidth confirmations sent. bool rcvCnf_: true if is received a confirmation from a node before it sent it a grant.
unsigned int backlog_: backlog for which no request has been issued, in bytes. This value is continuously incremented by the scheduler. On the other hand, it is decremented when this node sends a bandwidth request.
unsigned int def_in_: deficit counter of the input link, in bytes. During bandwidth request, it increments the deficit counter of any encountered input link, up to a maximum value, so that this input link will lag some bandwidth granting.
unsigned int def_out_: deficit counter of the output link, in bytes. During bandwidth granting, it increments the deficit counter of any encountered output link, up to a maximum value, so that this output link will lag some bandwidth request.
• CircularList <wimax::LinkId> activeList_: active-list of neighbor descriptors for bandwidth granting/requesting.
• CircularList <unsigned int> regntActiveList_: active-list of neighbors’ descriptors for bandwidth regranting.
• std::vector <std::vector <Bitmap> > neigh_tx_unavl_: neighbors' unavailability to transmit. This is a four-dimension bitmap. The first dimension is the neighbor index. The second dimension is the channel index. The third dimension is the frame index (modulo HORIZON). The four dimensions is the slot index within a frame. The last two dimensions are embedded into the Bitmap type, which is a vector of bitsets. This data structure is used when granting bandwidth to neighbors. All the slots of the F-th frame of each neighbor for all channels are reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame, at the end of each frame.
• std::vector <Bitmap> self_rx_unavl_: combination of <channel, frame, slot> where this node cannot receive. Updated when a confirmation from a node which is not in this node's neighborhood is received. Used when granting bandwidth to neighbors. All the slots of the F-th frame for all channels are reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame, at the end of each frame.
• std::vector <Bitmap> self_tx_unavl_: combination of <channel, frame, slot> where this node cannot transmit. Updated when a grant which is not addressed to this node is received. Used when confirming bandwidth to neighbors. All the slots of the F-th frame for all channels are reset by handle (), where F is the frame number (modulo HORIZON) of the current data frame, at the end of each frame.
• Bitmap busy_: two-dimension bitmap representing this node unavailability. The bit busy_[F][S] is set (i.e. true) if this node cannot receive/transmit in the minislot S of frame F. This data structure is used when granting/confirming bandwidth. The F-th entry of this data structure is reset by handle (), where F is the frame number (modulo HORIZON) of the current data frame at the end of each frame.
• Bitmap unconfirmedSlots_: two-dimension bitmap representing the slots unconfirmed by this node. Updated when a granted addressed to this node is received. Used to confirm only minislots that have not been reserved by other nodes. As soon as slot is confirmed, it is marked as busy (i.e. the corresponding bit in busy_ is set to true) so that the same slot can never be confirmed twice. The F-th entry of this data structure is reset by handle(), where F is the frame number (modulo HORIZON) of the current data frame at the end of each frame.
• std::list <WimaxMshDsch::GntIE> unconfirmed_: list of unconfirmed grants directed to this node.
• std::list <WimaxMshDsch::AvlIE> availabilities_: list of pending availabilities to send out. • bool avlAdvertise_: true if availabilities have to be advertised. Configured via Tcl.
• unsigned int regrantHorizon_: number of frames after the grant horizon used eligible for regranting. Changed via Tcl. Default value equal to 1.
• bool regrantEnabled_: true if unconfirmed bandwidth is regranted. Configured via Tcl. • bool fairRegrant_: true if we want to be fair while regranting bandwidth.
• bool fairGrant_: true if we want to be fair while granting bandwidth. • bool fairRequest_: true if we want to be fair while requesting bandwidth.
• unsigned int maxDeficit_: maximum deficit, in bytes. Set via Tcl command. Zero means no maximum.
• unsigned int maxBacklog_: maximum backlog, in bytes. Set via Tcl command. Zero means no maximum.
• bool deficitOverflow_: true if the last bandwidth/request grant terminated due to maxDeficit_. • WimshWeightManager wm_: weight manager.
• unsigned int roundDuration_: sum of the quanta, in bytes. Each quantum for bandwidth requesting/granting is computed as this value times the weight of the input/output link. This value is set via a Tcl command.
• RNG grantFitRng: random number generator to pick up channel/frame/slot when granting. • bool grantFitRandomChannel_: true if the starting channel is picked up randomly when
granting.
• unsigned int ddTimeout_: deadlock detection timeout, in units of MSH-DSCH opportunities. Zero means disabled.
• unsigned int ddTimer_: number of consecutive rounds in which deficitOverflow_ is true.
• unsigned int minGrant_: minimum grant size, in OFDM symbols, preamble not included. Default is 1.
Functions:
• void recvMshDsch ( WimaxMshDsch* dsch )
Get an MSH-DSCH message from a neighbor, which is not deallocated. • void schedule ( WimaxMshDsch* dsch )
Schedule bandwidth into the following MSH-DSCH message. Some fields have been already filled by the coordinator.
• void backlog ( WimaxNodeId src, WimaxNodeId dst, WimaxNodeId nexthop, unsigned int bytes) We have some new data to send out on an end-to-end flow.
• void backlog ( WimaxNodeId nexthop, unsigned int bytes ) We have some new data to send out on a link.
• void received ( WimaxNodeId src, WimaxNodeId dst, WimaxNodeId source, unsigned int bytes ) We received some new data addressed to this node.
• void rcvGrants (WimaxMshDsch* dsch)
Decode grants/confirmations from an incoming MSH-DSCH message. There are the following cases:
For each grant addressed to this node, a confirmation is added to the pending list of confirmations (managed by confirm ()), the granted minislots are marked as unconfirmed unavailable (in the unconfirmedSlots_ bitmap) and the amount of bandwidth granted by a neighbor is updated.
For each grant not addressed to this node, an unavailability is added to the pending list of availabilities (managed by availabilities ())
For each confirmation addressed to this node, update the cnf_in_ data structure.
For each confirmation addressed to a node which is not in this node's first-hop neighborhood, mark the confirmed minislots as unavailable for reception from this node. • void rcvAvailabilities ( WimaxMshDsch* dsch )
Decode availabilities from an incoming MSH-DSCH message. We update the status of
neigh_tx_unavail_ based on the received availabilities.
Decode requests from an incoming MSH-DSCH message. For each request addressed to this node, add the number of minislots requested to the req_in_ data structure.
• void confirm ( WimaxMshDsch* dsch ) Confirm pending grants.
For each confirmation in the unconfirmed list, we:
Try to send as many confirmations as possible, provided that the slots that have been granted are still available for transmission by this node (via the self_tx_unaval_ bitmap).
Update the status of the cnf_out_ data structure.
Set the minislots reserved for transmission at this node, which will be used by the handle () function to trigger the packet scheduler at the MAC layer. Both self_tx_unavl_ and
self_tx_unavl_ are updated. Note that the cnf_out_ data structure is updated with the number
of minislots actually confirmed which will be used for transmission. • void availabilities ( WimaxMshDsch* dsch )
Advertise pending availabilities.
• void requestGrant ( WimaxMshDsch* dsch )
Request/grant bandwidth. Let H be the average number of frames between two consecutive transmission opportunities of this node, and H' the same measure for the node to which we are currently granting bandwidth. The time window over which we grant bandwidth is NOW +
[H',H + 2H']. The granted minislots are marked as unavailable for reception. The amount of
granted minislots is updated.
• void regrant ( WimaxMshDsch* dsch )
Regrant as much as possible unconfirmed bandwidth. Bandwidth is regranted on a round-robin fashion. If it is not possible to regrant bandwidth to a neighbor, then the behaviour depends on the someFairness_ flag. If true, regranting stops immediately, and next regranting will begin from the current neighbor. On the other hand, if it is false, the neighbor is skipped and regranting continues over the remaining neighbors until either none of them can be served or there is not any more spare room in the MSH-DSCH message. In any case, the gnt_in_ counter for this neighbor is not updated. In other words, the latter counts the bytes that have been granted the first time only.
• void realPersistence ( unsigned int start, WimaxMshDsch::Persistence pers, unsigned int&
realStart, unsigned int& range )
Return the real number of frames for which the persistence is relevant. Since the frame number never wraps around, but the frame index into the data structures does, if a stale message is received, we have to update only the frames that are actually relevant. In other words, we do not want to update frames in the past, because we would overwrite information that will be used in the future, in a circular manner.
• WimaxMshDsch::GntIE grantFit ( unsigned int ndx, unsigned int bytes, unsigned int minFrame,
unsigned int maxFrame, grantFitDesc& status )
First-fit to grant bandwidth to a neighbor. The first fit is searched starting from the first minislot of the first frame in the first available channel. Persistence is always 1-frame. A slot in a frame on a channel is eligible to be granted to the requester if the corresponding entry in the following data structures is false: busy_, neigh_tx_unavl_, unconfirmed_. If it is not possible to schedule bandwidth to ndx in the specified time window, then a grant with an empty minislot range is returned.
grantFitDesc is a descriptor of the internal status used by grantFit (). grantFitDesc fields:
bool first: true if this is the first time that it is called during granting. unsigned int chSum: last channel to be considered.
unsigned int ch: current channel.
• void confFit ( unsigned int fstart, unsigned int frange, unsigned int mstart, unsigned int
First-fit to confirm bandwidth (similar to grantFit). A slot in a frame on a channel is eligible to be confirmed if the corresponding entry of busy_ is false.
WimshManagerRT
Class for a real time bandwidth manager in 802.16. Single-radio only. In this class I use the following structure.
• State
It contains flow parameters. Fields:
WimaxNodeId sender_: sender Node ID. WimaxNodeId receiver_: receiver Node ID. unsigned int flowID_: Flow ID.
double packetdim_: packet dimension in bytes. double packetperiod_: packet period in seconds.
unsigned int frame_: start frame number. IRL equal to 8 bits. Here we use the full frame number.
std::vector <unsigned char> minislot_: contains minislot allocated for this flow. unsigned char channel_: channel number.
double timerloc_: system parameter for compute TS.
double timerinst_: system parameter for compute TE.
double timerflow_: system parameter for compute TF.
double timerdummy_: system parameter for compute TD.
bool dir_: flow direction. → 0: upstream
→ 1: downstream. • TimerDesc
Timer descriptor for TS andTF.
Fields:
enum { LOCAL, FLOW } type_: recognize TS andTF.
WimaxNodeId sender_: sender Node ID. WimaxNodeId receiver_: receiver Node ID. unsigned int flowID_: Flow ID.
• TimerDummy
Timer descriptor for TD.
Fields:
WimaxNodeId sender_: sender Node ID. WimaxNodeId receiver_: receiver Node ID. unsigned int flowID_: Flow ID.
• TimerInstall
Timer descriptor for TE.
Fields:
WimaxNodeId sender_: sender Node ID. WimaxNodeId receiver_: receiver Node ID. unsigned int flowID_: Flow ID.
