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