A Discrete-Event Network Simulator
API
bs-uplink-scheduler-simple.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2007,2008 INRIA
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Jahanzeb Farooq <jahanzeb.farooq@sophia.inria.fr>
19  */
20 
22 #include "bs-net-device.h"
23 #include "ns3/simulator.h"
24 #include "cid.h"
25 #include "burst-profile-manager.h"
26 #include "ss-manager.h"
27 #include "ns3/log.h"
28 #include "ns3/uinteger.h"
29 #include "ss-record.h"
30 #include "service-flow.h"
31 #include "service-flow-record.h"
32 #include "bs-link-manager.h"
33 #include "bandwidth-manager.h"
34 
35 namespace ns3 {
36 
37 NS_LOG_COMPONENT_DEFINE ("UplinkSchedulerSimple");
38 
39 NS_OBJECT_ENSURE_REGISTERED (UplinkSchedulerSimple);
40 
42 {
43  SetBs (0);
46  SetIsIrIntrvlAllocated (false);
50 }
51 
53 {
54  SetBs (bs);
57  SetIsIrIntrvlAllocated (false);
61 }
62 
64 {
65  SetBs (0);
66  m_uplinkAllocations.clear ();
67 }
68 
69 void
71 {
72 
73 }
74 
75 TypeId
77 {
78  static TypeId tid = TypeId ("ns3::UplinkSchedulerSimple")
80  .SetGroupName("Wimax")
81  .AddConstructor<UplinkSchedulerSimple> ()
82  ;
83  return tid;
84 }
85 
86 std::list<OfdmUlMapIe>
88 {
89  return m_uplinkAllocations;
90 }
91 
92 void
94  bool &updateUcd,
95  bool &sendDcd,
96  bool &sendUcd)
97 {
98  /*DCD and UCD shall actually be updated when channel or burst profile definitions
99  change. burst profiles are updated based on number of SSs, network conditions and etc.
100  for now temporarily assuming DCD/UCD shall be updated every time */
101 
102  uint32_t randNr = rand ();
103  if (randNr % 5 == 0 || GetBs ()->GetNrDcdSent () == 0)
104  {
105  sendDcd = true;
106  }
107 
108  randNr = rand ();
109  if (randNr % 5 == 0 || GetBs ()->GetNrUcdSent () == 0)
110  {
111  sendUcd = true;
112  }
113 
114  // -------------------------------------
115  // additional, just to send more frequently
116  if (!sendDcd)
117  {
118  randNr = rand ();
119  if (randNr % 4 == 0)
120  {
121  sendDcd = true;
122  }
123  }
124 
125  if (!sendUcd)
126  {
127  randNr = rand ();
128  if (randNr % 4 == 0)
129  {
130  sendUcd = true;
131  }
132  }
133  // -------------------------------------
134 
135  Time timeSinceLastDcd = Simulator::Now () - GetDcdTimeStamp ();
136  Time timeSinceLastUcd = Simulator::Now () - GetUcdTimeStamp ();
137 
138  if (timeSinceLastDcd > GetBs ()->GetDcdInterval ())
139  {
140  sendDcd = true;
142  }
143 
144  if (timeSinceLastUcd > GetBs ()->GetUcdInterval ())
145  {
146  sendUcd = true;
148  }
149 }
150 
151 uint32_t
153 {
154  return GetBs ()->GetNrDlSymbols () * GetBs ()->GetPhy ()->GetPsPerSymbol () + GetBs ()->GetTtg ();
155 }
156 
157 void
159  const uint32_t &allocationSize,
160  uint32_t &symbolsToAllocation,
161  uint32_t &availableSymbols)
162 {
163  ulMapIe.SetDuration (allocationSize);
164  ulMapIe.SetStartTime (symbolsToAllocation);
165  m_uplinkAllocations.push_back (ulMapIe);
166  symbolsToAllocation += allocationSize;
167  availableSymbols -= allocationSize;
168 }
169 
170 void
172 {
173  m_uplinkAllocations.clear ();
174  SetIsIrIntrvlAllocated (false);
176  bool allocationForDsa = false;
177 
178  uint32_t symbolsToAllocation = 0;
179  uint32_t allocationSize = 0; // size in symbols
180  uint32_t availableSymbols = GetBs ()->GetNrUlSymbols ();
181 
182  AllocateInitialRangingInterval (symbolsToAllocation, availableSymbols);
183 
184  std::vector<SSRecord*> *ssRecords = GetBs ()->GetSSManager ()->GetSSRecords ();
185  for (std::vector<SSRecord*>::iterator iter = ssRecords->begin (); iter != ssRecords->end (); ++iter)
186  {
187  SSRecord *ssRecord = *iter;
188 
189  if (ssRecord->GetIsBroadcastSS ())
190  {
191  continue;
192  }
193  Cid cid = ssRecord->GetBasicCid ();
194  OfdmUlMapIe ulMapIe;
195  ulMapIe.SetCid (cid);
196 
198  {
199 
200  // SS's ranging is not yet complete
201  // allocating invited initial ranging interval
203  allocationSize = GetBs ()->GetRangReqOppSize ();
205 
206  if (availableSymbols >= allocationSize)
207  {
208  AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);
209  }
210  else
211  {
212 
213  break;
214  }
215  }
216  else
217  {
218  WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();
219 
220  // need to update because modulation/FEC to UIUC mapping may vary over time
221  ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,
223 
224  // establish service flows for SS
226  && !ssRecord->GetAreServiceFlowsAllocated ())
227  {
228 
229  // allocating grant (with arbitrary size) to allow SS to send DSA messages DSA-REQ and DSA-ACK
230  // only one DSA allocation per frame
231  if (!allocationForDsa)
232  {
233  allocationSize = GetBs ()->GetPhy ()->GetNrSymbols (sizeof(DsaReq), modulationType);
234 
235  if (availableSymbols >= allocationSize)
236  {
237  AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);
238  allocationForDsa = true;
239  }
240  else
241  {
242  break;
243  }
244  }
245  }
246  else
247  {
248  // all service flows associated to SS are established now
249 
250  /*allocating grants for data transmission for UGS flows (Data Grant Burst Type IEs, 6.3.7.4.3.3)
251  (grant has been referred by different names e.g. transmission opportunity, slot, uplink allocation, etc)*/
252  ServiceUnsolicitedGrants (ssRecord,
254  ulMapIe,
255  modulationType,
256  symbolsToAllocation,
257  availableSymbols);
258 
259  // allocate unicast polls for rtPS flows if bandwidth is available
260  if (availableSymbols)
261  {
262  ServiceUnsolicitedGrants (ssRecord,
264  ulMapIe,
265  modulationType,
266  symbolsToAllocation,
267  availableSymbols);
268  }
269  // allocate unicast polls for nrtPS flows if bandwidth is available
270  if (availableSymbols)
271  {
272  ServiceUnsolicitedGrants (ssRecord,
274  ulMapIe,
275  modulationType,
276  symbolsToAllocation,
277  availableSymbols);
278  }
279  // finally allocate unicast polls for BE flows if bandwidth is available
280  if (availableSymbols)
281  {
282  ServiceUnsolicitedGrants (ssRecord,
284  ulMapIe,
285  modulationType,
286  symbolsToAllocation,
287  availableSymbols);
288  }
289 
290  // now allocating grants for non-UGS flows (i.e., in response of bandwidth requests)
291 
292  if (availableSymbols)
293  {
294  ServiceBandwidthRequests (ssRecord,
296  ulMapIe,
297  modulationType,
298  symbolsToAllocation,
299  availableSymbols);
300  }
301  // allocate unicast polls for nrtPS flows if bandwidth is available
302  if (availableSymbols)
303  {
304  ServiceBandwidthRequests (ssRecord,
306  ulMapIe,
307  modulationType,
308  symbolsToAllocation,
309  availableSymbols);
310  }
311  // finally allocate unicast polls for BE flows if bandwidth is available
312  if (availableSymbols)
313  {
314  ServiceBandwidthRequests (ssRecord,
316  ulMapIe,
317  modulationType,
318  symbolsToAllocation,
319  availableSymbols);
320  }
321  }
322  }
323  }
324  OfdmUlMapIe ulMapIeEnd;
325 
326  ulMapIeEnd.SetCid (Cid::InitialRanging ());
327  ulMapIeEnd.SetStartTime (symbolsToAllocation);
329  ulMapIeEnd.SetDuration (0);
330  m_uplinkAllocations.push_back (ulMapIeEnd);
331 
332  // setting DL/UL subframe allocation for the next frame
333  GetBs ()->GetBandwidthManager ()->SetSubframeRatio ();
334 }
335 
336 void
338  enum ServiceFlow::SchedulingType schedulingType,
339  OfdmUlMapIe &ulMapIe,
340  const WimaxPhy::ModulationType modulationType,
341  uint32_t &symbolsToAllocation,
342  uint32_t &availableSymbols)
343 {
344  uint32_t allocationSize = 0; // size in symbols
345  uint8_t uiuc = ulMapIe.GetUiuc (); // SS's burst profile
346  std::vector<ServiceFlow*> serviceFlows = ssRecord->GetServiceFlows (schedulingType);
347 
348  for (std::vector<ServiceFlow*>::iterator iter = serviceFlows.begin (); iter != serviceFlows.end (); ++iter)
349  {
350  ServiceFlow *serviceFlow = *iter;
351 
352  /* in case of rtPS, nrtPS and BE, allocating unicast polls for bandwidth requests (Request IEs, 6.3.7.4.3.1).
353  in case of UGS, allocating grants for data transmission (Data Grant Burst Type IEs, 6.3.7.4.3.3) (grant has
354  been referred in this code by different names e.g. transmission opportunity, slot, allocation, etc) */
355 
356  allocationSize = GetBs ()->GetBandwidthManager ()->CalculateAllocationSize (ssRecord, serviceFlow);
357  // verifying that minimum reserved traffic rate of nrtPS flow is maintained
358  if (serviceFlow->GetSchedulingType () == ServiceFlow::SF_TYPE_NRTPS)
359  {
360  Time currentTime = Simulator::Now ();
361  ServiceFlowRecord *record = serviceFlow->GetRecord ();
362  if (currentTime - record->GetGrantTimeStamp () > Seconds (1))
363  {
364  uint32_t bps = (record->GetBwSinceLastExpiry () * 8);
365  if (bps < serviceFlow->GetMinReservedTrafficRate ())
366  {
367  ServiceBandwidthRequests (serviceFlow,
368  schedulingType,
369  ulMapIe,
370  modulationType,
371  symbolsToAllocation,
372  availableSymbols);
373  record->SetBwSinceLastExpiry (0);
374  record->SetGrantTimeStamp (currentTime);
375  }
376  }
377  }
378 
379  if (availableSymbols < allocationSize)
380  {
381  break;
382  }
383 
384  if (allocationSize > 0)
385  {
386  ulMapIe.SetStartTime (symbolsToAllocation);
387  if (serviceFlow->GetSchedulingType () != ServiceFlow::SF_TYPE_UGS)
388  {
389  // special burst profile with most robust modulation type is used for unicast polls (Request IEs)
391  }
392  }
393  else
394  {
395  continue;
396  }
397 
398  NS_LOG_DEBUG (", CID: " << serviceFlow->GetConnection ()->GetCid () << ", SFID: " << serviceFlow->GetSfid ());
399 
400  AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);
401  ulMapIe.SetUiuc (uiuc);
402  }
403 }
404 
405 void
407  enum ServiceFlow::SchedulingType schedulingType,
408  OfdmUlMapIe &ulMapIe,
409  const WimaxPhy::ModulationType modulationType,
410  uint32_t &symbolsToAllocation,
411  uint32_t &availableSymbols)
412 {
413  std::vector<ServiceFlow*> serviceFlows = ssRecord->GetServiceFlows (schedulingType);
414 
415  for (std::vector<ServiceFlow*>::iterator iter = serviceFlows.begin (); iter != serviceFlows.end (); ++iter)
416  {
417  if (!ServiceBandwidthRequests (*iter,
418  schedulingType,
419  ulMapIe,
420  modulationType,
421  symbolsToAllocation,
422  availableSymbols))
423  {
424  break;
425  }
426  }
427 }
428 
429 bool
431  enum ServiceFlow::SchedulingType schedulingType,
432  OfdmUlMapIe &ulMapIe,
433  const WimaxPhy::ModulationType modulationType,
434  uint32_t &symbolsToAllocation,
435  uint32_t &availableSymbols)
436 {
437  uint32_t allocSizeBytes = 0;
438  uint32_t allocSizeSymbols = 0;
439  uint16_t sduSize = 0;
440 
441  ServiceFlowRecord *record = serviceFlow->GetRecord ();
442  sduSize = serviceFlow->GetSduSize ();
443 
444  uint32_t requiredBandwidth = record->GetRequestedBandwidth () - record->GetGrantedBandwidth ();
445  if (requiredBandwidth > 0)
446  {
447  if (sduSize > 0)
448  {
449  // if SDU size is mentioned, allocate grant of that size
450  allocSizeBytes = sduSize;
451  allocSizeSymbols = GetBs ()->GetPhy ()->GetNrSymbols (sduSize, modulationType);
452  }
453  else
454  {
455  allocSizeBytes = requiredBandwidth;
456  allocSizeSymbols = GetBs ()->GetPhy ()->GetNrSymbols (requiredBandwidth, modulationType);
457  }
458 
459  if (availableSymbols >= allocSizeSymbols)
460  {
461  record->UpdateGrantedBandwidth (allocSizeBytes);
462 
463  if (schedulingType == ServiceFlow::SF_TYPE_NRTPS)
464  {
465  record->SetBwSinceLastExpiry (allocSizeBytes);
466  }
467 
468  AddUplinkAllocation (ulMapIe, allocSizeSymbols, symbolsToAllocation, availableSymbols);
469  }
470  else
471  {
472  return false;
473  }
474  }
475  return true;
476 }
477 
478 void
479 UplinkSchedulerSimple::AllocateInitialRangingInterval (uint32_t &symbolsToAllocation, uint32_t &availableSymbols)
480 {
481  Time ssUlStartTime = Seconds (CalculateAllocationStartTime () * GetBs ()->GetPsDuration ().GetSeconds ());
482  SetNrIrOppsAllocated (GetBs ()->GetLinkManager ()->CalculateRangingOppsToAllocate ());
483  uint32_t allocationSize = GetNrIrOppsAllocated () * GetBs ()->GetRangReqOppSize ();
484  Time timeSinceLastIrInterval = Simulator::Now () - GetTimeStampIrInterval ();
485 
486  // adding one frame because may be the time has not elapsed now but will elapse before the next frame is sent
487  if (timeSinceLastIrInterval + GetBs ()->GetPhy ()->GetFrameDuration () > GetBs ()->GetInitialRangingInterval ()
488  && availableSymbols >= allocationSize)
489  {
490  SetIsIrIntrvlAllocated (true);
491  OfdmUlMapIe ulMapIeIr;
492  ulMapIeIr.SetCid ((GetBs ()->GetBroadcastConnection ())->GetCid ());
493  ulMapIeIr.SetStartTime (symbolsToAllocation);
495 
496  NS_LOG_DEBUG ("BS uplink scheduler, initial ranging allocation, size: " << allocationSize << " symbols"
497  << ", modulation: BPSK 1/2");
498 
499  // marking start and end of each TO, only for debugging
500  for (uint8_t i = 0; i < GetNrIrOppsAllocated (); i++)
501  {
502  GetBs ()->MarkRangingOppStart (ssUlStartTime + Seconds (symbolsToAllocation
503  * GetBs ()->GetSymbolDuration ().GetSeconds ()) + Seconds (i * GetBs ()->GetRangReqOppSize ()
504  * GetBs ()->GetSymbolDuration ().GetSeconds ()));
505  }
506 
507  AddUplinkAllocation (ulMapIeIr, allocationSize, symbolsToAllocation, availableSymbols);
509  }
510 }
511 
512 void
514 {
515  uint8_t delayNrFrames = 1;
516  uint32_t bitsPerSecond = serviceFlow->GetMinReservedTrafficRate ();
517  WimaxPhy::ModulationType modulation;
518  uint32_t bytesPerFrame =
519  (uint32_t ((double)(bitsPerSecond) * GetBs ()->GetPhy ()->GetFrameDuration ().GetSeconds ())) / 8;
520  uint32_t frameDurationMSec = GetBs ()->GetPhy ()->GetFrameDuration ().GetMilliSeconds ();
521 
522  switch (serviceFlow->GetSchedulingType ())
523  {
525  {
526  if (serviceFlow->GetIsMulticast () == true)
527  {
528  modulation = serviceFlow->GetModulation ();
529  }
530  else
531  {
532  modulation = ssRecord->GetModulationType ();
533  }
534  uint32_t grantSize = GetBs ()->GetPhy ()->GetNrSymbols (bytesPerFrame, modulation);
535  serviceFlow->GetRecord ()->SetGrantSize (grantSize);
536 
537  uint32_t toleratedJitter = serviceFlow->GetToleratedJitter ();
538 
539  if (toleratedJitter > frameDurationMSec)
540  {
541  delayNrFrames = (uint8_t)(toleratedJitter / frameDurationMSec);
542  }
543 
544  uint16_t interval = delayNrFrames * frameDurationMSec;
545  serviceFlow->SetUnsolicitedGrantInterval (interval);
546  }
547  break;
549  {
550  if (serviceFlow->GetSduSize () > bytesPerFrame)
551  {
552  delayNrFrames = (uint8_t)(serviceFlow->GetSduSize () / bytesPerFrame);
553  }
554 
555  uint16_t interval = delayNrFrames * frameDurationMSec;
556  serviceFlow->SetUnsolicitedPollingInterval (interval);
557  }
558  break;
560  {
561  // no real-time guarantees are given to NRTPS, serviced based on available bandwidth
562  }
563  break;
565  {
566  // no real-time guarantees are given to BE, serviced based on available bandwidth
567  }
568  break;
569  default:
570  NS_FATAL_ERROR ("Invalid scheduling type");
571  }
572 }
573 
574 void
576 {
577  // virtual function on UplinkScheduler
578  // this is not necessary on this implementation
579 }
580 
581 void
583 {
584  // m_grantedBandwidth must be reset to zero
585  uint32_t grantedBandwidth = 0;
586  sfr->SetGrantedBandwidth (grantedBandwidth);
587 }
588 
589 } // namespace ns3
This class implements the bandwidth-request mac Header as described by IEEE Standard for Local and me...
Cid class.
Definition: cid.h:38
static Cid InitialRanging(void)
Definition: cid.cc:82
This class implements the DSA-REQ message described by "IEEE Standard for Local and metropolitan area...
Definition: mac-messages.h:374
This class implements the UL-MAP_IE message as described by "IEEE Standard for Local and metropolitan...
uint8_t GetUiuc(void) const
Get UIUC.
void SetStartTime(uint16_t startTime)
Set start time.
void SetDuration(uint16_t duration)
Set duration.
void SetCid(const Cid &cid)
Set CID.
void SetUiuc(uint8_t uiuc)
Set UIUC.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:74
This class is used by the base station to store some information related to subscriber station in the...
Definition: ss-record.h:44
bool GetPollForRanging(void) const
Get poll for ranging.
Definition: ss-record.cc:194
WimaxNetDevice::RangingStatus GetRangingStatus(void) const
Get ranging status.
Definition: ss-record.cc:176
WimaxPhy::ModulationType GetModulationType(void) const
Get modulation type.
Definition: ss-record.cc:164
std::vector< ServiceFlow * > GetServiceFlows(enum ServiceFlow::SchedulingType schedulingType) const
Get service flows.
Definition: ss-record.cc:229
bool GetAreServiceFlowsAllocated(void) const
Check if service flows are allocated.
Definition: ss-record.cc:206
bool GetIsBroadcastSS(void)
Get is broadcast SS.
Definition: ss-record.cc:249
Cid GetBasicCid(void) const
Get basic CID.
Definition: ss-record.cc:92
This class implements service flows as described by the IEEE-802.16 standard.
Definition: service-flow.h:40
enum WimaxPhy::ModulationType GetModulation(void) const
Get modulation.
uint32_t GetMinReservedTrafficRate(void) const
Get minimum reserved traffic rate.
uint8_t GetSduSize(void) const
Get SDU size.
enum ServiceFlow::SchedulingType GetSchedulingType(void) const
Get scheduling type.
SchedulingType
section 11.13.11 Service flow scheduling type, page 701
Definition: service-flow.h:59
ServiceFlowRecord * GetRecord(void) const
Get service flow record.
Ptr< WimaxConnection > GetConnection(void) const
Can return a null connection is this service flow has not been associated yet to a connection.
void SetUnsolicitedGrantInterval(uint16_t unsolicitedGrantInterval)
Set unsolicied grant interval.
bool GetIsMulticast(void) const
Get is multicast.
void SetUnsolicitedPollingInterval(uint16_t unsolicitedPollingInterval)
Set unsolicited polling interval.
uint32_t GetToleratedJitter(void) const
Get tolerated jitter.
uint32_t GetSfid(void) const
Get SFID.
this class implements a structure to manage some parameters and statistics related to a service flow
Time GetGrantTimeStamp(void) const
uint32_t GetRequestedBandwidth(void)
uint32_t GetBwSinceLastExpiry(void)
void SetGrantSize(uint32_t grantSize)
Set the grant size (only for UGS service flows)
void SetBwSinceLastExpiry(uint32_t bwSinceLastExpiry)
set BW since last expiry
void UpdateGrantedBandwidth(uint32_t grantedBandwidth)
update the granted bandwidth
uint32_t GetGrantedBandwidth(void)
void SetGrantTimeStamp(Time grantTimeStamp)
Set the grant time stamp.
void SetGrantedBandwidth(uint32_t grantedBandwidth)
set the granted bandwidth
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:195
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
ModulationType
ModulationType enumeration.
Definition: wimax-phy.h:52
#define NS_FATAL_ERROR(msg)
Report a fatal error with a message and terminate.
Definition: fatal-error.h:165
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1244
Every class exported by the ns3 library is enclosed in the ns3 namespace.