A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
bs-uplink-scheduler-mbqos.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * This program is free software; you can redistribute it and/or modify
4  * it under the terms of the GNU General Public License version 2 as
5  * published by the Free Software Foundation;
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software
14  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15  *
16  */
17 
19 #include "bs-net-device.h"
20 #include "ns3/simulator.h"
21 #include "cid.h"
22 #include "burst-profile-manager.h"
23 #include "ss-manager.h"
24 #include "ns3/log.h"
25 #include "ns3/uinteger.h"
26 #include "service-flow.h"
27 #include "service-flow-record.h"
28 #include "bs-link-manager.h"
29 #include "bandwidth-manager.h"
30 #include "connection-manager.h"
31 
32 NS_LOG_COMPONENT_DEFINE ("UplinkSchedulerMBQoS");
33 
34 namespace ns3 {
35 
36 NS_OBJECT_ENSURE_REGISTERED (UplinkSchedulerMBQoS);
37 
39 {
40 }
41 
43  : m_windowInterval (time)
44 {
45 
46 }
47 
49 {
50  SetBs (0);
51  m_uplinkAllocations.clear ();
52 }
53 
54 TypeId
56 {
57  static TypeId tid = TypeId ("ns3::UplinkSchedulerMBQoS")
58 
60 
61  .AddAttribute ("WindowInterval",
62  "The time to wait to reset window",
63  TimeValue (Seconds (1.0)),
64  MakeTimeAccessor (&UplinkSchedulerMBQoS::m_windowInterval),
65  MakeTimeChecker ());
66  return tid;
67 }
68 
69 void
71 {
73 }
74 
75 std::list<OfdmUlMapIe>
77 {
78  return m_uplinkAllocations;
79 }
80 
81 void
83  bool &updateUcd,
84  bool &sendDcd,
85  bool &sendUcd)
86 {
87  /* DCD and UCD shall actually be updated when channel or burst profile definitions
88  change. burst profiles are updated based on number of SSs, network conditions and etc.
89  for now temporarily assuming DCD/UCD shall be updated everytime */
90 
91  uint32_t randNr = rand ();
92  if (randNr % 5 == 0 || GetBs ()->GetNrDcdSent () == 0)
93  {
94  sendDcd = true;
95  }
96 
97  randNr = rand ();
98  if (randNr % 5 == 0 || GetBs ()->GetNrUcdSent () == 0)
99  {
100  sendUcd = true;
101  }
102 
103  // -------------------------------------
104  // additional, just to send more frequently
105  if (!sendDcd)
106  {
107  randNr = rand ();
108  if (randNr % 4 == 0)
109  {
110  sendDcd = true;
111  }
112  }
113 
114  if (!sendUcd)
115  {
116  randNr = rand ();
117  if (randNr % 4 == 0)
118  {
119  sendUcd = true;
120  }
121  }
122  // -------------------------------------
123 
124  Time timeSinceLastDcd = Simulator::Now () - GetDcdTimeStamp ();
125  Time timeSinceLastUcd = Simulator::Now () - GetUcdTimeStamp ();
126 
127  if (timeSinceLastDcd > GetBs ()->GetDcdInterval ())
128  {
129  sendDcd = true;
131  }
132 
133  if (timeSinceLastUcd > GetBs ()->GetUcdInterval ())
134  {
135  sendUcd = true;
137  }
138 }
139 
140 uint32_t
142 {
143  return GetBs ()->GetNrDlSymbols () * GetBs ()->GetPhy ()->GetPsPerSymbol () + GetBs ()->GetTtg ();
144 }
145 
146 void
148  const uint32_t &allocationSize,
149  uint32_t &symbolsToAllocation,
150  uint32_t &availableSymbols)
151 {
152  ulMapIe.SetDuration (allocationSize);
153  ulMapIe.SetStartTime (symbolsToAllocation);
154  m_uplinkAllocations.push_back (ulMapIe);
155  symbolsToAllocation += allocationSize;
156  availableSymbols -= allocationSize;
157 }
158 
159 void
161 {
162 
163  NS_LOG (LOG_DEBUG, "Window Reset at " << (Simulator::Now ()).GetSeconds ());
164 
165  uint32_t min_bw = 0;
166 
167  if (!GetBs ()->GetSSManager ())
168  {
170  return;
171  }
172 
173  std::vector<SSRecord*> *ssRecords = GetBs ()->GetSSManager ()->GetSSRecords ();
174 
175  // For each SS
176  for (std::vector<SSRecord*>::iterator iter = ssRecords->begin (); iter != ssRecords->end (); ++iter)
177  {
178  SSRecord *ssRecord = *iter;
179  std::vector<ServiceFlow*> serviceFlows = ssRecord->GetServiceFlows (ServiceFlow::SF_TYPE_ALL);
180 
181  // For each flow
182  for (std::vector<ServiceFlow*>::iterator iter2 = serviceFlows.begin (); iter2 != serviceFlows.end (); ++iter2)
183  {
184  ServiceFlow *serviceFlow = *iter2;
185  if ((serviceFlow->GetSchedulingType () == ServiceFlow::SF_TYPE_RTPS) || (serviceFlow->GetSchedulingType ()
187  {
188  min_bw = (int) ceil (serviceFlow->GetMinReservedTrafficRate ());
189 
190  // This way we can compensate flows which did not get min_bw in the previous window
191  if ((serviceFlow->GetRecord ()->GetBacklogged () > 0)
192  && (serviceFlow->GetRecord ()->GetBwSinceLastExpiry () < min_bw))
193  {
194  serviceFlow->GetRecord ()->UpdateBwSinceLastExpiry (-min_bw);
195 
196  // if backlogged < granted_bw then we don't need to provide granted_bw + min_bw in next window, but backlogged + min_bw
197  if (serviceFlow->GetRecord ()->GetBacklogged ()
198  < (serviceFlow->GetRecord ()->GetBwSinceLastExpiry ()))
199  {
200  serviceFlow->GetRecord ()->SetBwSinceLastExpiry (-serviceFlow->GetRecord ()->GetBacklogged ());
201  }
202  }
203  else
204  {
205  serviceFlow->GetRecord ()->SetBwSinceLastExpiry (0);
206  }
207  }
208  }
209  }
210 
211  // Periodically reset window
213 }
214 
215 void
217 {
218  m_uplinkAllocations.clear ();
219  SetIsIrIntrvlAllocated (false);
221  bool allocationForDsa = false;
222 
223  uint32_t symbolsToAllocation = 0;
224  uint32_t allocationSize = 0; // size in symbols
225  uint32_t availableSymbols = GetBs ()->GetNrUlSymbols ();
226  uint32_t availableSymbolsAux = GetBs ()->GetNrUlSymbols ();
227 
228  AllocateInitialRangingInterval (symbolsToAllocation, availableSymbols);
229 
230  std::vector<SSRecord*> *ssRecords = GetBs ()->GetSSManager ()->GetSSRecords ();
231  for (std::vector<SSRecord*>::iterator iter = ssRecords->begin (); iter != ssRecords->end (); ++iter)
232  {
233  SSRecord *ssRecord = *iter;
234 
235  if (ssRecord->GetIsBroadcastSS ())
236  {
237  continue;
238  }
239  Cid cid = ssRecord->GetBasicCid ();
240  OfdmUlMapIe ulMapIe;
241  ulMapIe.SetCid (cid);
242 
244  {
245  // SS's ranging is not yet complete
246  // allocating invited initial ranging interval
248  allocationSize = GetBs ()->GetRangReqOppSize ();
250 
251  if (availableSymbols >= allocationSize)
252  {
253  AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);
254  }
255  else
256  {
257  break;
258  }
259  }
260  else
261  {
262  WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();
263 
264  // need to update because modulation/FEC to UIUC mapping may vary over time
265  ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,
267 
268  // establish service flows for SS
270  && !ssRecord->GetAreServiceFlowsAllocated ())
271  {
272 
273  // allocating grant (with arbitrary size) to allow SS to send DSA messages DSA-REQ and DSA-ACK
274  // only one DSA allocation per frame
275  if (!allocationForDsa)
276  {
277  allocationSize = GetBs ()->GetPhy ()->GetNrSymbols (sizeof(DsaReq), modulationType);
278 
279  if (availableSymbols >= allocationSize)
280  {
281  AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);
282  allocationForDsa = true;
283  }
284  else
285  {
286  break;
287  }
288  }
289  }
290  else
291  {
292  // all service flows associated to SS are established now
293 
294  /* Implementation of uplink scheduler
295  * [1] Freitag, J.; da Fonseca, N.L.S., "Uplink Scheduling with Quality of Service in IEEE 802.16 Networks,"
296  * Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE , vol., no., pp.2503-2508, 26-30 Nov. 2007
297  * URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4411386&isnumber=4410910 */
298 
299  // Step 1
300  if (availableSymbols)
301  {
302  /*allocating grants for data transmission for UGS flows (Data Grant Burst Type IEs, 6.3.7.4.3.3)
303  (grant has been referred by different names e.g. transmission opportunity, slot, uplink allocation, etc)*/
304  if (ssRecord->GetHasServiceFlowUgs ())
305  {
306  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering be unicast polling");
307  // Recover period interval information for UGS flow
308  Time frame_duration = GetBs ()->GetPhy ()->GetFrameDuration ();
309  Time
310  timestamp =
311  (*(ssRecord->GetServiceFlows (ServiceFlow::SF_TYPE_UGS).begin ()))->GetRecord ()->GetLastGrantTime ()
312  + MilliSeconds ((*(ssRecord->GetServiceFlows (ServiceFlow::SF_TYPE_UGS).begin ()))->GetUnsolicitedGrantInterval ());
313 
314  int64_t frame = (timestamp - Simulator::Now ()) / frame_duration;
315 
316  if (frame <= 1)
317  {
318  // UGS Grants
319  // It is not necessary to enqueue UGS grants once it is periodically served
320  ServiceUnsolicitedGrants (ssRecord,
322  ulMapIe,
323  modulationType,
324  symbolsToAllocation,
325  availableSymbols);
326  }
327  }
328 
329  // enqueue allocate unicast polls for rtPS flows if bandwidth is available
330  if (ssRecord->GetHasServiceFlowRtps ())
331  {
332  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering rtps unicast polling");
334  EnqueueJob (UlJob::HIGH, jobRTPSPoll);
335  }
336 
337  if (ssRecord->GetHasServiceFlowNrtps ())
338  {
339  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering nrtps unicast polling");
340  // allocate unicast polls for nrtPS flows if bandwidth is available
342  EnqueueJob (UlJob::HIGH, jobNRTPSPoll);
343  }
344 
345  if (ssRecord->GetHasServiceFlowBe ())
346  {
347  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering be unicast polling");
348  // finally allocate unicast polls for BE flows if bandwidth is available
350  EnqueueJob (UlJob::HIGH, jobBEPoll);
351  }
352  }
353  }
354  }
355  }
356  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " high queue has " << m_uplinkJobs_high.size ()<< " jobs - after sched");
357 
358  availableSymbolsAux = availableSymbols;
359  uint32_t symbolsUsed = 0;
360 
361  symbolsUsed += CountSymbolsQueue (m_uplinkJobs_high);
362  availableSymbolsAux -= symbolsUsed;
363 
364  // Step 2 - Check Deadline - Migrate requests with deadline expiring
365  CheckDeadline (availableSymbolsAux);
366 
367  // Step 3 - Check Minimum Bandwidth
368  CheckMinimumBandwidth (availableSymbolsAux);
369 
370  // Scheduling high priority queue
371  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " high queue has " << m_uplinkJobs_high.size ()<< " jobs");
372  while ((availableSymbols) && (!m_uplinkJobs_high.empty ()))
373  {
374 
375  Ptr<UlJob> job = m_uplinkJobs_high.front ();
376  OfdmUlMapIe ulMapIe;
377  SSRecord * ssRecord = job->GetSsRecord ();
378  enum ServiceFlow::SchedulingType schedulingType = job->GetSchedulingType ();
379 
380  Cid cid = ssRecord->GetBasicCid ();
381  ulMapIe.SetCid (cid);
382  WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();
383  // need to update because modulation/FEC to UIUC mapping may vary over time
384  ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,
386 
387  ReqType reqType = job->GetType ();
388 
389  if (reqType == UNICAST_POLLING)
390  {
391  ServiceUnsolicitedGrants (ssRecord,
392  schedulingType,
393  ulMapIe,
394  modulationType,
395  symbolsToAllocation,
396  availableSymbols);
397  }
398  else if (reqType == DATA)
399  {
400  ServiceFlow *serviceFlow = job->GetServiceFlow ();
401  uint32_t allocSizeBytes = job->GetSize ();
402  ServiceBandwidthRequestsBytes (serviceFlow,
403  schedulingType,
404  ulMapIe,
405  modulationType,
406  symbolsToAllocation,
407  availableSymbols,
408  allocSizeBytes);
409  }
410  m_uplinkJobs_high.pop_front ();
411  }
412 
413  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " interqueue has " << m_uplinkJobs_inter.size ()<< " jobs");
414  /* Scheduling intermediate priority queue */
415  while ((availableSymbols) && (!m_uplinkJobs_inter.empty ()))
416  {
417  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " Scheduling interqueue");
418  Ptr<UlJob> job = m_uplinkJobs_inter.front ();
419  OfdmUlMapIe ulMapIe;
420  SSRecord * ssRecord = job->GetSsRecord ();
421  enum ServiceFlow::SchedulingType schedulingType = job->GetSchedulingType ();
422 
423  Cid cid = ssRecord->GetBasicCid ();
424  ulMapIe.SetCid (cid);
425  WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();
426  // need to update because modulation/FEC to UIUC mapping may vary over time
427  ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,
429 
430  ReqType reqType = job->GetType ();
431 
432  if (reqType == DATA)
433  {
434  ServiceBandwidthRequests (ssRecord,
435  schedulingType,
436  ulMapIe,
437  modulationType,
438  symbolsToAllocation,
439  availableSymbols);
440  }
441  else
442  {
443  NS_FATAL_ERROR ("Intermediate priority queue only should enqueue data packets.");
444  }
445  m_uplinkJobs_inter.pop_front ();
446  }
447 
448  /* Scheduling low priority queue */
449  while ((availableSymbols) && (!m_uplinkJobs_low.empty ()))
450  {
451 
452  Ptr<UlJob> job = m_uplinkJobs_low.front ();
453  OfdmUlMapIe ulMapIe;
454  SSRecord * ssRecord = job->GetSsRecord ();
455  enum ServiceFlow::SchedulingType schedulingType = job->GetSchedulingType ();
456 
457  Cid cid = ssRecord->GetBasicCid ();
458  ulMapIe.SetCid (cid);
459  WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();
460  // need to update because modulation/FEC to UIUC mapping may vary over time
461  ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,
463 
464  ReqType reqType = job->GetType ();
465 
466  if (reqType == DATA)
467  {
468  ServiceBandwidthRequests (ssRecord,
469  schedulingType,
470  ulMapIe,
471  modulationType,
472  symbolsToAllocation,
473  availableSymbols);
474  }
475  else
476  {
477  NS_FATAL_ERROR ("Low priority queue only should enqueue data packets.");
478  }
479  m_uplinkJobs_low.pop_front ();
480  }
481 
482  OfdmUlMapIe ulMapIeEnd;
483  ulMapIeEnd.SetCid (*(new Cid (0)));
484  ulMapIeEnd.SetStartTime (symbolsToAllocation);
486  ulMapIeEnd.SetDuration (0);
487  m_uplinkAllocations.push_back (ulMapIeEnd);
488 
489  // setting DL/UL subframe allocation for the next frame
490  GetBs ()->GetBandwidthManager ()->SetSubframeRatio ();
491 }
492 
494  enum ServiceFlow::SchedulingType schedulingType, OfdmUlMapIe &ulMapIe,
495  const WimaxPhy::ModulationType modulationType,
496  uint32_t &symbolsToAllocation, uint32_t &availableSymbols, uint32_t allocationSizeBytes)
497 {
498  uint32_t allocSizeBytes = allocationSizeBytes;
499  uint32_t allocSizeSymbols = 0;
500 
501  ServiceFlowRecord *record = serviceFlow->GetRecord ();
502 
503  uint32_t requiredBandwidth = record->GetRequestedBandwidth ();
504 
505  if (requiredBandwidth > 0)
506  {
507  allocSizeSymbols = GetBs ()->GetPhy ()->GetNrSymbols (allocSizeBytes, modulationType);
508 
509  if (availableSymbols < allocSizeSymbols)
510  {
511  allocSizeSymbols = availableSymbols;
512  }
513 
514  if (availableSymbols >= allocSizeSymbols)
515  {
516  NS_LOG_DEBUG (
517  "At " << Simulator::Now ().GetSeconds ()<<" BS uplink scheduler, "
518  << serviceFlow->GetSchedulingTypeStr ()
519  << " allocation, size: " << allocSizeSymbols << " symbols"
520  << ", CID: "
521  << serviceFlow->GetConnection ()->GetCid ()
522  << ", SFID: " << serviceFlow->GetSfid ()
523  << ", bw requested: " << record->GetRequestedBandwidth ()
524  << ", bw granted: " << allocSizeBytes
525  << std::endl);
526 
527  record->UpdateGrantedBandwidthTemp (allocSizeBytes);
528  record->UpdateGrantedBandwidth (allocSizeBytes);
529  record->UpdateRequestedBandwidth (-allocSizeBytes);
530 
531  record->UpdateBwSinceLastExpiry (allocSizeBytes);
532 
533 
534  AddUplinkAllocation (ulMapIe, allocSizeSymbols, symbolsToAllocation,
535  availableSymbols);
536  } else
537  {
538  return false;
539  }
540  }
541  return true;
542 }
543 
544 uint32_t
546 {
547  uint32_t symbols = 0;
548  for (std::list<Ptr<UlJob> >::iterator iter = jobs.begin (); iter != jobs.end (); ++iter)
549  {
550  Ptr<UlJob> job = *iter;
551 
552  // count symbols
553  symbols += CountSymbolsJobs (job);
554  }
555  return symbols;
556 }
557 
560 {
561  Ptr<UlJob> job = CreateObject <UlJob> ();
562  job->SetSsRecord (ssRecord);
563  job->SetSchedulingType (schedType);
564  job->SetServiceFlow (*(ssRecord->GetServiceFlows (schedType).begin ()));
565  job->SetType (reqType);
566  return job;
567 }
568 
569 uint32_t
571 {
572  SSRecord *ssRecord = job->GetSsRecord ();
573  ServiceFlow *serviceFlow = job->GetServiceFlow ();
574  uint32_t allocationSize = 0;
575 
576  if (job->GetType () == UNICAST_POLLING)
577  {
578  // if polling
579  Time currentTime = Simulator::Now ();
580  allocationSize = 0;
581  if ((currentTime - serviceFlow->GetRecord ()->GetGrantTimeStamp ()).GetMilliSeconds ()
582  >= serviceFlow->GetUnsolicitedPollingInterval ())
583  {
584  allocationSize = GetBs ()->GetBwReqOppSize ();
585  }
586  }
587  else
588  {
589  // if data
590  uint16_t sduSize = serviceFlow->GetSduSize ();
591  ServiceFlowRecord *record = serviceFlow->GetRecord ();
592  uint32_t requiredBandwidth = record->GetRequestedBandwidth () - record->GetGrantedBandwidth ();
593  if (requiredBandwidth > 0)
594  {
595  WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();
596  if (sduSize > 0)
597  {
598  // if SDU size is mentioned, allocate grant of that size
599  allocationSize = GetBs ()->GetPhy ()->GetNrSymbols (sduSize, modulationType);
600  }
601  else
602  {
603  allocationSize = GetBs ()->GetPhy ()->GetNrSymbols (requiredBandwidth, modulationType);
604  }
605  }
606  }
607  return allocationSize;
608 }
609 
610 void
612 {
613  switch (priority)
614  {
615  case UlJob::HIGH:
616  m_uplinkJobs_high.push_back (job);
617  break;
618  case UlJob::INTERMEDIATE:
619  m_uplinkJobs_inter.push_back (job);
620  break;
621  case UlJob::LOW:
622  m_uplinkJobs_low.push_back (job);
623  }
624 }
625 
628 {
629  Ptr<UlJob> job_front;
630  switch (priority)
631  {
632  case UlJob::HIGH:
633  job_front = m_uplinkJobs_high.front ();
634  m_uplinkJobs_high.pop_front ();
635  break;
636  case UlJob::INTERMEDIATE:
637  job_front = m_uplinkJobs_inter.front ();
638  m_uplinkJobs_inter.pop_front ();
639  break;
640  case UlJob::LOW:
641  job_front = m_uplinkJobs_low.front ();
642  m_uplinkJobs_low.pop_front ();
643  }
644  return job_front;
645 }
646 
647 void
648 UplinkSchedulerMBQoS::CheckDeadline (uint32_t &availableSymbols)
649 {
650  // for each request in the imermediate queue
651  if (m_uplinkJobs_inter.size () > 0)
652  {
653  std::list<Ptr<UlJob> >::iterator iter = m_uplinkJobs_inter.begin ();
654 
655  while (iter != m_uplinkJobs_inter.end () && availableSymbols)
656  {
657  Ptr<UlJob> job = *iter;
658 
659  // guarantee delay bound for rtps connections
660  if (job->GetSchedulingType () == ServiceFlow::SF_TYPE_RTPS)
661  {
662  Time deadline = job->GetDeadline ();
663  Time frame_duration = GetBs ()->GetPhy ()->GetFrameDuration ();
664 
665  int64_t frame = (deadline - Simulator::Now ()) / frame_duration;
666 
667  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " reserved traffic rate: "
668  << job->GetServiceFlow ()->GetMinReservedTrafficRate ()
669  <<" deadline: "<<job->GetDeadline ().GetSeconds () << " frame start: "<<GetBs ()->m_frameStartTime.GetSeconds ()
670  <<" frame duration: "<< frame_duration );
671 
672  // should be schedule in this frame to max latency
673  if (frame >= 3)
674  {
675 
676  if (availableSymbols)
677  {
678  uint32_t availableBytes = GetBs ()->GetPhy ()->GetNrBytes (availableSymbols,job->GetSsRecord ()->GetModulationType ());
679  uint32_t allocationSize = job->GetSize ();
680  if (allocationSize > availableBytes)
681  {
682  allocationSize = availableBytes;
683  }
684 
685 
686  if (allocationSize == 0)
687  {
688  continue;
689  }
690 
691  uint32_t symbolsToAllocate = GetBs ()->GetPhy ()->GetNrSymbols (allocationSize, job->GetSsRecord ()->GetModulationType ());
692  if (symbolsToAllocate > availableSymbols)
693  {
694  symbolsToAllocate = availableSymbols;
695  allocationSize = GetBs ()->GetPhy ()->GetNrBytes (symbolsToAllocate,job->GetSsRecord ()->GetModulationType ());
696  }
697 
698  job->SetSize (job->GetSize () - allocationSize);
699 
700  Ptr<UlJob> newJob = CreateObject<UlJob> ();
701  // Record data in job
702  newJob->SetSsRecord (job->GetSsRecord ());
703  newJob->SetServiceFlow (job->GetServiceFlow ());
704  newJob->SetSize (allocationSize);
705  newJob->SetDeadline (job->GetDeadline ());
706  newJob->SetReleaseTime (job->GetReleaseTime ());
707  newJob->SetSchedulingType (job->GetSchedulingType ());
708  newJob->SetPeriod (job->GetPeriod ());
709  newJob->SetType (job->GetType ());
710 
711  EnqueueJob (UlJob::HIGH, newJob);
712 
713  // migrate request
714  iter++;
715  if ((job->GetSize () - allocationSize) == 0)
716  {
717  m_uplinkJobs_inter.remove (job);
718  }
719 
720  }
721  }
722  else
723  {
724  iter++;
725  }
726  }
727  else
728  {
729  iter++;
730  }
731  }
732  }
733 }
734 
735 void
737 {
738  std::list<Ptr<PriorityUlJob> > priorityUlJobs;
739 
740  // For each connection of type rtPS or nrtPS
741  std::vector<SSRecord*> *ssRecords = GetBs ()->GetSSManager ()->GetSSRecords ();
742  for (std::vector<SSRecord*>::iterator iter = ssRecords->begin (); iter != ssRecords->end (); ++iter)
743  {
744  SSRecord *ssRecord = *iter;
745  std::vector<ServiceFlow*> serviceFlows = ssRecord->GetServiceFlows (ServiceFlow::SF_TYPE_ALL);
746  for (std::vector<ServiceFlow*>::iterator iter2 = serviceFlows.begin (); iter2 != serviceFlows.end (); ++iter2)
747  {
748  ServiceFlow *serviceFlow = *iter2;
749  if (serviceFlow->GetSchedulingType () == ServiceFlow::SF_TYPE_RTPS || serviceFlow->GetSchedulingType ()
751  {
752  serviceFlow->GetRecord ()->SetBackloggedTemp (serviceFlow->GetRecord ()->GetBacklogged ());
753  serviceFlow->GetRecord ()->SetGrantedBandwidthTemp (serviceFlow->GetRecord ()->GetBwSinceLastExpiry ());
754  }
755  }
756  }
757 
758  // for each request in the imermediate queue
759  for (std::list<Ptr<UlJob> >::const_iterator iter = m_uplinkJobs_inter.begin (); iter != m_uplinkJobs_inter.end (); ++iter)
760  {
761  Ptr<UlJob> job = *iter;
762  // SSRecord ssRecord = job->GetSsRecord();
763  ServiceFlow *serviceFlow = job->GetServiceFlow ();
764  if ((job->GetSchedulingType () == ServiceFlow::SF_TYPE_RTPS || job->GetSchedulingType ()
765  == ServiceFlow::SF_TYPE_NRTPS) && (serviceFlow->GetRecord ()->GetBacklogged () > 0))
766  {
767  uint32_t minReservedTrafficRate = serviceFlow->GetMinReservedTrafficRate ();
768  uint32_t grantedBandwidth = serviceFlow->GetRecord ()->GetBwSinceLastExpiry ();
769 
770  Ptr<PriorityUlJob> priorityUlJob = CreateObject<PriorityUlJob> ();
771  priorityUlJob->SetUlJob (job);
772  // pri_array
773  if (minReservedTrafficRate <= grantedBandwidth)
774  {
775  priorityUlJob->SetPriority (-10000);
776  }
777  else
778  {
779  uint32_t allocationSize = serviceFlow->GetRecord ()->GetRequestedBandwidth ()
780  - serviceFlow->GetRecord ()->GetGrantedBandwidth ();
781  uint32_t sduSize = serviceFlow->GetSduSize ();
782 
783  if (allocationSize > 0)
784  {
785  if (sduSize > 0)
786  {
787  // if SDU size is mentioned, grant of that size
788  allocationSize = sduSize;
789  }
790  }
791  int priority = serviceFlow->GetRecord ()->GetBackloggedTemp ()
792  - (serviceFlow->GetRecord ()->GetGrantedBandwidthTemp () - minReservedTrafficRate);
793  priorityUlJob->SetPriority (priority);
794  serviceFlow->GetRecord ()->SetGrantedBandwidthTemp (serviceFlow->GetRecord ()->GetGrantedBandwidthTemp ()
795  + allocationSize);
796  serviceFlow->GetRecord ()->SetBackloggedTemp (serviceFlow->GetRecord ()->GetBackloggedTemp ()
797  - allocationSize);
798  }
799 
800  priorityUlJobs.push_back (priorityUlJob);
801  }
802  }
803 
804  priorityUlJobs.sort (SortProcessPtr ());
805 
806  for (std::list<Ptr<PriorityUlJob> >::const_iterator iter = priorityUlJobs.begin (); iter != priorityUlJobs.end (); ++iter)
807  {
808  Ptr<PriorityUlJob> priorityUlJob = *iter;
809  Ptr<UlJob> job_priority = priorityUlJob->GetUlJob ();
810  Ptr<UlJob> job = job_priority;
811  if (availableSymbols)
812  {
813  availableSymbols -= CountSymbolsJobs (job);
814  // migrate request
815  m_uplinkJobs_inter.remove (job);
816  EnqueueJob (UlJob::HIGH, job);
817  }
818  }
819 }
820 
821 void
823  enum ServiceFlow::SchedulingType schedulingType,
824  OfdmUlMapIe &ulMapIe,
825  const WimaxPhy::ModulationType modulationType,
826  uint32_t &symbolsToAllocation,
827  uint32_t &availableSymbols)
828 {
829  uint32_t allocationSize = 0; // size in symbols
830  uint8_t uiuc = ulMapIe.GetUiuc (); // SS's burst profile
831  std::vector<ServiceFlow*> serviceFlows = ssRecord->GetServiceFlows (schedulingType);
832 
833  for (std::vector<ServiceFlow*>::iterator iter = serviceFlows.begin (); iter != serviceFlows.end (); ++iter)
834  {
835  ServiceFlow *serviceFlow = *iter;
836 
837  /* in case of rtPS, nrtPS and BE, allocating unicast polls for bandwidth requests (Request IEs, 6.3.7.4.3.1).
838  in case of UGS, allocating grants for data transmission (Data Grant Burst Type IEs, 6.3.7.4.3.3) (grant has
839  been referred in this code by different names e.g. transmission opportunity, slot, allocation, etc) */
840 
841  allocationSize = GetBs ()->GetBandwidthManager ()->CalculateAllocationSize (ssRecord, serviceFlow);
842 
843  if (availableSymbols < allocationSize)
844  {
845  break;
846  }
847 
848  if (allocationSize > 0)
849  {
850  ulMapIe.SetStartTime (symbolsToAllocation);
851  if (serviceFlow->GetSchedulingType () != ServiceFlow::SF_TYPE_UGS)
852  {
853  // special burst profile with most robust modulation type is used for unicast polls (Request IEs)
855  }
856  }
857  else
858  {
859  continue;
860  }
861 
862  if (serviceFlow->GetSchedulingType () == ServiceFlow::SF_TYPE_UGS)
863  {
864  NS_LOG_DEBUG ("BS uplink scheduler, UGS allocation, size: " << allocationSize << " symbols");
865  }
866  else
867  {
868  NS_LOG_DEBUG ("BS uplink scheduler, " << serviceFlow->GetSchedulingTypeStr () << " unicast poll, size: "
869  << allocationSize << " symbols" << ", modulation: BPSK 1/2");
870  }
871 
872  NS_LOG_DEBUG (", CID: " << serviceFlow->GetConnection ()->GetCid () << ", SFID: " << serviceFlow->GetSfid ());
873 
874  serviceFlow->GetRecord ()->SetLastGrantTime (Simulator::Now ());
875  AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);
876  ulMapIe.SetUiuc (uiuc);
877  }
878 }
879 
880 void
882  enum ServiceFlow::SchedulingType schedulingType,
883  OfdmUlMapIe &ulMapIe,
884  const WimaxPhy::ModulationType modulationType,
885  uint32_t &symbolsToAllocation,
886  uint32_t &availableSymbols)
887 {
888  std::vector<ServiceFlow*> serviceFlows = ssRecord->GetServiceFlows (schedulingType);
889 
890  for (std::vector<ServiceFlow*>::iterator iter = serviceFlows.begin (); iter != serviceFlows.end (); ++iter)
891  {
892  if (!ServiceBandwidthRequests (*iter,
893  schedulingType,
894  ulMapIe,
895  modulationType,
896  symbolsToAllocation,
897  availableSymbols))
898  {
899  break;
900  }
901  }
902 }
903 
904 bool
906  enum ServiceFlow::SchedulingType schedulingType,
907  OfdmUlMapIe &ulMapIe,
908  const WimaxPhy::ModulationType modulationType,
909  uint32_t &symbolsToAllocation,
910  uint32_t &availableSymbols)
911 {
912  uint32_t allocSizeBytes = 0;
913  uint32_t allocSizeSymbols = 0;
914  uint16_t sduSize = 0;
915 
916  ServiceFlowRecord *record = serviceFlow->GetRecord ();
917  sduSize = serviceFlow->GetSduSize ();
918 
919  uint32_t requiredBandwidth = record->GetRequestedBandwidth () - record->GetGrantedBandwidth ();
920  if (requiredBandwidth > 0)
921  {
922  if (sduSize > 0)
923  {
924  // if SDU size is mentioned, allocate grant of that size
925  allocSizeBytes = sduSize;
926  allocSizeSymbols = GetBs ()->GetPhy ()->GetNrSymbols (sduSize, modulationType);
927 
928  }
929  else
930  {
931  allocSizeBytes = requiredBandwidth;
932  allocSizeSymbols = GetBs ()->GetPhy ()->GetNrSymbols (requiredBandwidth, modulationType);
933  }
934 
935  if (availableSymbols >= allocSizeSymbols)
936  {
937  NS_LOG_DEBUG ("BS uplink scheduler, " << serviceFlow->GetSchedulingTypeStr () << " allocation, size: "
938  << allocSizeSymbols << " symbols" << ", CID: " << serviceFlow->GetConnection ()->GetCid () << ", SFID: "
939  << serviceFlow->GetSfid () << ", bw requested: " << record->GetRequestedBandwidth () << ", bw granted: "
940  << record->GetGrantedBandwidth ());
941 
942  record->UpdateGrantedBandwidth (allocSizeBytes);
943 
944  record->SetBwSinceLastExpiry (allocSizeBytes);
945 
946  if (serviceFlow->GetRecord ()->GetBacklogged () < allocSizeBytes)
947  {
948  serviceFlow->GetRecord ()->SetBacklogged (0);
949  }
950  else
951  {
952  serviceFlow->GetRecord ()->IncreaseBacklogged (-allocSizeBytes);
953  }
954  serviceFlow->GetRecord ()->SetLastGrantTime (Simulator::Now ());
955 
956  AddUplinkAllocation (ulMapIe, allocSizeSymbols, symbolsToAllocation, availableSymbols);
957  }
958  else
959  {
960  return false;
961  }
962  }
963  return true;
964 }
965 
966 void
967 UplinkSchedulerMBQoS::AllocateInitialRangingInterval (uint32_t &symbolsToAllocation, uint32_t &availableSymbols)
968 {
969  Time ssUlStartTime = Seconds (CalculateAllocationStartTime () * GetBs ()->GetPsDuration ().GetSeconds ());
970  SetNrIrOppsAllocated (GetBs ()->GetLinkManager ()->CalculateRangingOppsToAllocate ());
971  uint32_t allocationSize = GetNrIrOppsAllocated () * GetBs ()->GetRangReqOppSize ();
972  Time timeSinceLastIrInterval = Simulator::Now () - GetTimeStampIrInterval ();
973 
974  // adding one frame because may be the time has not elapsed now but will elapse before the next frame is sent
975  if (timeSinceLastIrInterval + GetBs ()->GetPhy ()->GetFrameDuration () > GetBs ()->GetInitialRangingInterval ()
976  && availableSymbols >= allocationSize)
977  {
978  SetIsIrIntrvlAllocated (true);
979  OfdmUlMapIe ulMapIeIr;
980  ulMapIeIr.SetCid ((GetBs ()->GetBroadcastConnection ())->GetCid ());
981  ulMapIeIr.SetStartTime (symbolsToAllocation);
983 
984  NS_LOG_DEBUG ("BS uplink scheduler, initial ranging allocation, size: " << allocationSize << " symbols"
985  << ", modulation: BPSK 1/2" );
986 
987  // marking start and end of each TO, only for debugging
988  for (uint8_t i = 0; i < GetNrIrOppsAllocated (); i++)
989  {
990  GetBs ()->MarkRangingOppStart (ssUlStartTime + Seconds (symbolsToAllocation
991  * GetBs ()->GetSymbolDuration ().GetSeconds ()) + Seconds (i * GetBs ()->GetRangReqOppSize ()
992  * GetBs ()->GetSymbolDuration ().GetSeconds ()));
993  }
994 
995  AddUplinkAllocation (ulMapIeIr, allocationSize, symbolsToAllocation, availableSymbols);
997  }
998 }
999 
1000 void
1002 {
1003  uint8_t delayNrFrames = 1;
1004  uint32_t bitsPerSecond = serviceFlow->GetMinReservedTrafficRate ();
1005  WimaxPhy::ModulationType modulation;
1006  uint32_t bytesPerFrame =
1007  (uint32_t ((double)(bitsPerSecond) * GetBs ()->GetPhy ()->GetFrameDuration ().GetSeconds ())) / 8;
1008  uint32_t frameDurationMSec = GetBs ()->GetPhy ()->GetFrameDuration ().GetMilliSeconds ();
1009 
1010  switch (serviceFlow->GetSchedulingType ())
1011  {
1013  {
1014  if (serviceFlow->GetIsMulticast () == true)
1015  {
1016  modulation = serviceFlow->GetModulation ();
1017  }
1018  else
1019  {
1020  modulation = ssRecord->GetModulationType ();
1021  }
1022  uint32_t grantSize = GetBs ()->GetPhy ()->GetNrSymbols (bytesPerFrame, modulation);
1023  serviceFlow->GetRecord ()->SetGrantSize (grantSize);
1024 
1025  uint32_t toleratedJitter = serviceFlow->GetToleratedJitter ();
1026 
1027  if (toleratedJitter > frameDurationMSec)
1028  {
1029  delayNrFrames = (uint8_t)(toleratedJitter / frameDurationMSec);
1030  }
1031 
1032  uint16_t interval = delayNrFrames * frameDurationMSec;
1033  serviceFlow->SetUnsolicitedGrantInterval (interval);
1034  }
1035  break;
1037  {
1038  serviceFlow->SetUnsolicitedPollingInterval (20);
1039  }
1040  break;
1042  {
1043  // no real-time guarantees are given to NRTPS, serviced based on available bandwidth
1044  uint16_t interval = 1000;
1045  serviceFlow->SetUnsolicitedPollingInterval (interval);
1046  }
1047  break;
1049  {
1050  // no real-time guarantees are given to BE, serviced based on available bandwidth
1051  }
1052  break;
1053  default:
1054  NS_FATAL_ERROR ("Invalid scheduling type");
1055  }
1056 }
1057 
1059 {
1060  uint32_t size = 0;
1061  std::list<Ptr <PriorityUlJob> > priorityUlJobs;
1062 
1063  // for each request in the imermediate queue
1064  for (std::list<Ptr<UlJob> >::const_iterator iter = m_uplinkJobs_inter.begin (); iter
1065  != m_uplinkJobs_inter.end (); ++iter)
1066  {
1067  Ptr<UlJob> job = *iter;
1068 
1069  ServiceFlow *serviceFlowJob = job->GetServiceFlow ();
1070 
1071  if (serviceFlowJob == serviceFlow)
1072  {
1073  size += job->GetSize ();
1074  }
1075  }
1076  return size;
1077 }
1078 
1079 void
1081 {
1082  // Enqueue requests for uplink scheduler.
1083  Ptr<UlJob> job = CreateObject <UlJob> ();
1084  Ptr<WimaxConnection> connection = GetBs ()->GetConnectionManager ()->GetConnection (bwRequestHdr.GetCid ());
1085  SSRecord *ssRecord = GetBs ()->GetSSManager ()->GetSSRecord (connection->GetCid ());
1086  ServiceFlow *serviceFlow = connection->GetServiceFlow ();
1087 
1088  uint32_t size = bwRequestHdr.GetBr ();
1089  uint32_t pendingSize = GetPendingSize (serviceFlow);
1090 
1091  if (size > pendingSize)
1092  {
1093  size -= pendingSize;
1094  }
1095  else
1096  {
1097  size = 0;
1098  }
1099 
1100  if (size == 0)
1101  {
1102  return;
1103  }
1104 
1105 
1106  Time deadline = DetermineDeadline (serviceFlow);
1107  Time currentTime = Simulator::Now ();
1108  Time period = deadline; // So that deadline is properly updated..
1109 
1110  NS_LOG_DEBUG ("At "<<Simulator::Now ().GetSeconds ()<<" at BS uplink scheduler, processing bandwidth request from." <<
1111  ssRecord->GetMacAddress () << " and sf " << serviceFlow->GetSchedulingType () <<" with deadline in " << deadline.GetSeconds () << " and size " << size << " aggreg size " << bwRequestHdr.GetBr ());
1112 
1113  // Record data in job
1114  job->SetSsRecord (ssRecord);
1115  job->SetServiceFlow (serviceFlow);
1116  job->SetSize (size);
1117  job->SetDeadline (deadline);
1118  job->SetReleaseTime (currentTime);
1119  job->SetSchedulingType (serviceFlow->GetSchedulingType ());
1120  job->SetPeriod (period);
1121  job->SetType (DATA);
1122 
1123  // Enqueue job in Uplink Scheduler
1124  switch (serviceFlow->GetSchedulingType ())
1125  {
1128  break;
1131  break;
1133  EnqueueJob (UlJob::LOW, job);
1134  break;
1135  default:
1136  EnqueueJob (UlJob::LOW, job);
1137  break;
1138  }
1139 }
1140 
1141 /*
1142  * Calculate Deadline of requests according to QoS parameter
1143  * */
1144 Time
1146 {
1147  uint32_t latency = serviceFlow->GetMaximumLatency ();
1148  Time lastGrantTime = serviceFlow->GetRecord ()->GetLastGrantTime ();
1149  Time deadline = MilliSeconds (latency) + lastGrantTime;
1150  return deadline;
1151 }
1152 
1153 void
1155 {
1156  // virtual function on UplinkScheduler
1157  // this is not necessary on this implementation
1158 }
1159 
1160 } // namespace ns3
void SetBackloggedTemp(uint32_t backloggedTemp)
Mac48Address GetMacAddress(void) const
Definition: ss-record.cc:116
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:79
enum WimaxPhy::ModulationType GetModulation(void) const
smart pointer class similar to boost::intrusive_ptr
Definition: ptr.h:60
enum ServiceFlow::SchedulingType GetSchedulingType(void) const
void SetCid(Cid cid)
bool GetHasServiceFlowBe(void) const
Definition: ss-record.cc:294
ReqType
Definition: ul-job.h:36
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register the class in the ns-3 factory.
Definition: object-base.h:38
Cid GetBasicCid(void) const
Definition: ss-record.cc:92
void UpdateBwSinceLastExpiry(uint32_t bwSinceLastExpiry)
uint32_t GetRequestedBandwidth(void)
this class implements a structure to manage some parameters and statistics related to a service flow ...
bool GetAreServiceFlowsAllocated(void) const
Definition: ss-record.cc:206
void UpdateRequestedBandwidth(uint32_t requestedBandwidth)
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:170
uint32_t GetSfid(void) const
WimaxNetDevice::RangingStatus GetRangingStatus(void) const
Definition: ss-record.cc:176
#define NS_FATAL_ERROR(msg)
fatal error handling
Definition: fatal-error.h:95
static EventId Schedule(Time const &time, MEM mem_ptr, OBJ obj)
Schedule an event to expire at the relative time "time" is reached.
Definition: simulator.h:825
rare ad-hoc debug messages
Definition: log.h:80
Ptr< WimaxConnection > GetConnection(void) const
char * GetSchedulingTypeStr(void) const
uint32_t GetMinReservedTrafficRate(void) const
void UpdateGrantedBandwidthTemp(uint32_t grantedBandwidthTemp)
double GetSeconds(void) const
Definition: nstime.h:272
Time GetGrantTimeStamp(void) const
hold objects of type ns3::Time
Definition: nstime.h:1008
uint32_t GetBwSinceLastExpiry(void)
void SetUnsolicitedPollingInterval(uint16_t)
void SetDuration(uint16_t duration)
bool GetHasServiceFlowRtps(void) const
Definition: ss-record.cc:268
#define NS_LOG(level, msg)
This macro allows you to log an arbitrary message at a specific log level.
void SetGrantSize(uint32_t grantSize)
Set the grant size (only for UGS service flows)
void SetUnsolicitedGrantInterval(uint16_t)
std::vector< ServiceFlow * > GetServiceFlows(enum ServiceFlow::SchedulingType schedulingType) const
Definition: ss-record.cc:229
#define list
uint32_t GetMaximumLatency(void) const
uint8_t GetUiuc(void) const
uint32_t GetBackloggedTemp(void) const
bool GetHasServiceFlowUgs(void) const
Definition: ss-record.cc:255
this class implements the bandwidth-request mac Header as described by IEEE Standard for Local and me...
uint32_t GetBacklogged(void) const
Definition: cid.h:35
uint8_t GetSduSize(void) const
uint32_t GetGrantedBandwidthTemp(void)
This class implements service flows as described by the IEEE-802.16 standard.
Definition: service-flow.h:39
void SetGrantedBandwidthTemp(uint32_t grantedBandwidthTemp)
void SetStartTime(uint16_t startTime)
bool GetHasServiceFlowNrtps(void) const
Definition: ss-record.cc:281
static Time Now(void)
Return the "current simulation time".
Definition: simulator.cc:180
ServiceFlowRecord * GetRecord(void) const
Time GetLastGrantTime(void) const
bool GetPollForRanging(void) const
Definition: ss-record.cc:194
bool GetIsBroadcastSS(void)
Definition: ss-record.cc:249
uint32_t GetToleratedJitter(void) const
uint32_t GetBr(void) const
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:213
bool GetIsMulticast(void) const
JobPriority
Definition: ul-job.h:48
void SetBwSinceLastExpiry(uint32_t bwSinceLastExpiry)
void SetLastGrantTime(Time grantTime)
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:441
This class is used by the base station to store some information related to subscriber station in the...
Definition: ss-record.h:43
void UpdateGrantedBandwidth(uint32_t grantedBandwidth)
void SetBacklogged(uint32_t backlogged)
uint32_t GetGrantedBandwidth(void)
Doxygen introspection did not find any typical Config paths.
Definition: mac-messages.h:262
void IncreaseBacklogged(uint32_t backlogged)
a unique identifier for an interface.
Definition: type-id.h:49
void SetUiuc(uint8_t uiuc)
TypeId SetParent(TypeId tid)
Definition: type-id.cc:610
WimaxPhy::ModulationType GetModulationType(void) const
Definition: ss-record.cc:164
uint16_t GetUnsolicitedPollingInterval(void) const