/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

/*

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License version 2 as

 * published by the Free Software Foundation;

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 */

#include "bs-uplink-scheduler-mbqos.h"

#include "bs-net-device.h"

#include "ns3/simulator.h"

#include "cid.h"

#include "burst-profile-manager.h"

#include "ss-manager.h"

#include "ns3/log.h"

#include "ns3/uinteger.h"

#include "service-flow.h"

#include "service-flow-record.h"

#include "bs-link-manager.h"

#include "bandwidth-manager.h"

#include "connection-manager.h"

NS_LOG_COMPONENT_DEFINE ("UplinkSchedulerMBQoS");

namespace ns3 {

NS_OBJECT_ENSURE_REGISTERED (UplinkSchedulerMBQoS);

UplinkSchedulerMBQoS::UplinkSchedulerMBQoS ()

{

}

UplinkSchedulerMBQoS::UplinkSchedulerMBQoS (Time time)

  : m_windowInterval (time)

{

}

UplinkSchedulerMBQoS::~UplinkSchedulerMBQoS (void)

{

  SetBs (0);

  m_uplinkAllocations.clear ();

}

TypeId

UplinkSchedulerMBQoS::GetTypeId (void)

{

  static TypeId tid = TypeId ("ns3::UplinkSchedulerMBQoS")

    .SetParent<UplinkScheduler> ()

    .AddAttribute ("WindowInterval",

                   "The time to wait to reset window",

                   TimeValue (Seconds (1.0)),

                   MakeTimeAccessor (&UplinkSchedulerMBQoS::m_windowInterval),

                   MakeTimeChecker ());

  return tid;

}

void

UplinkSchedulerMBQoS::InitOnce ()

{

  UplinkSchedWindowTimer ();

}

std::list<OfdmUlMapIe>

UplinkSchedulerMBQoS::GetUplinkAllocations (void) const

{

  return m_uplinkAllocations;

}

void

UplinkSchedulerMBQoS::GetChannelDescriptorsToUpdate (bool &updateDcd,

                                                     bool &updateUcd,

                                                     bool &sendDcd,

                                                     bool &sendUcd)

{

  /* DCD and UCD shall actually be updated when channel or burst profile definitions

   change. burst profiles are updated based on number of SSs, network conditions and etc.

   for now temporarily assuming DCD/UCD shall be updated everytime */

  uint32_t randNr = rand ();

  if (randNr % 5 == 0 || GetBs ()->GetNrDcdSent () == 0)

    {

      sendDcd = true;

    }

  randNr = rand ();

  if (randNr % 5 == 0 || GetBs ()->GetNrUcdSent () == 0)

    {

      sendUcd = true;

    }

  // -------------------------------------

  // additional, just to send more frequently

  if (!sendDcd)

    {

      randNr = rand ();

      if (randNr % 4 == 0)

        {

          sendDcd = true;

        }

    }

  if (!sendUcd)

    {

      randNr = rand ();

      if (randNr % 4 == 0)

        {

          sendUcd = true;

        }

    }

  // -------------------------------------

  Time timeSinceLastDcd = Simulator::Now () - GetDcdTimeStamp ();

  Time timeSinceLastUcd = Simulator::Now () - GetUcdTimeStamp ();

  if (timeSinceLastDcd > GetBs ()->GetDcdInterval ())

    {

      sendDcd = true;

      SetDcdTimeStamp (Simulator::Now ());

    }

  if (timeSinceLastUcd > GetBs ()->GetUcdInterval ())

    {

      sendUcd = true;

      SetUcdTimeStamp (Simulator::Now ());

    }

}

uint32_t

UplinkSchedulerMBQoS::CalculateAllocationStartTime (void)

{

  return GetBs ()->GetNrDlSymbols () * GetBs ()->GetPhy ()->GetPsPerSymbol () + GetBs ()->GetTtg ();

}

void

UplinkSchedulerMBQoS::AddUplinkAllocation (OfdmUlMapIe &ulMapIe,

                                           const uint32_t &allocationSize,

                                           uint32_t &symbolsToAllocation,

                                           uint32_t &availableSymbols)

{

  ulMapIe.SetDuration (allocationSize);

  ulMapIe.SetStartTime (symbolsToAllocation);

  m_uplinkAllocations.push_back (ulMapIe);

  symbolsToAllocation += allocationSize;

  availableSymbols -= allocationSize;

}

void

UplinkSchedulerMBQoS::UplinkSchedWindowTimer (void)

{

  NS_LOG (LOG_DEBUG, "Window Reset at " << (Simulator::Now ()).GetSeconds ());

  uint32_t min_bw = 0;

  if (!GetBs ()->GetSSManager ())

    {

      Simulator::Schedule (m_windowInterval, &UplinkSchedulerMBQoS::UplinkSchedWindowTimer, this);

      return;

    }

  std::vector<SSRecord*> *ssRecords = GetBs ()->GetSSManager ()->GetSSRecords ();

  // For each SS

  for (std::vector<SSRecord*>::iterator iter = ssRecords->begin (); iter != ssRecords->end (); ++iter)

    {

      SSRecord *ssRecord = *iter;

      std::vector<ServiceFlow*> serviceFlows = ssRecord->GetServiceFlows (ServiceFlow::SF_TYPE_ALL);

      // For each flow

      for (std::vector<ServiceFlow*>::iterator iter2 = serviceFlows.begin (); iter2 != serviceFlows.end (); ++iter2)

        {

          ServiceFlow *serviceFlow = *iter2;

          if ((serviceFlow->GetSchedulingType () == ServiceFlow::SF_TYPE_RTPS) || (serviceFlow->GetSchedulingType ()

                                                                                   == ServiceFlow::SF_TYPE_NRTPS))

            {

              min_bw = (int) ceil (serviceFlow->GetMinReservedTrafficRate ());

              // This way we can compensate flows which did not get min_bw in the previous window

              if ((serviceFlow->GetRecord ()->GetBacklogged () > 0)

                  && (serviceFlow->GetRecord ()->GetBwSinceLastExpiry () < min_bw))

                {

                  serviceFlow->GetRecord ()->UpdateBwSinceLastExpiry (-min_bw);

                  // if backlogged < granted_bw then we don't need to provide granted_bw + min_bw in next window, but backlogged + min_bw

                  if (serviceFlow->GetRecord ()->GetBacklogged ()

                      < ((uint32_t) abs (serviceFlow->GetRecord ()->GetBwSinceLastExpiry ())))

                    {

                      serviceFlow->GetRecord ()->SetBwSinceLastExpiry (-serviceFlow->GetRecord ()->GetBacklogged ());

                    }

                }

              else

                {

                  serviceFlow->GetRecord ()->SetBwSinceLastExpiry (0);

                }

            }

        }

    }

  // Periodically reset window

  Simulator::Schedule (m_windowInterval, &UplinkSchedulerMBQoS::UplinkSchedWindowTimer, this);

}

void

UplinkSchedulerMBQoS::Schedule (void)

{

  m_uplinkAllocations.clear ();

  SetIsIrIntrvlAllocated (false);

  SetIsInvIrIntrvlAllocated (false);

  bool allocationForDsa = false;

  uint32_t symbolsToAllocation = 0;

  uint32_t allocationSize = 0; // size in symbols

  uint32_t availableSymbols = GetBs ()->GetNrUlSymbols ();

  uint32_t availableSymbolsAux = GetBs ()->GetNrUlSymbols ();

  AllocateInitialRangingInterval (symbolsToAllocation, availableSymbols);

  std::vector<SSRecord*> *ssRecords = GetBs ()->GetSSManager ()->GetSSRecords ();

  for (std::vector<SSRecord*>::iterator iter = ssRecords->begin (); iter != ssRecords->end (); ++iter)

    {

      SSRecord *ssRecord = *iter;

      if (ssRecord->GetIsBroadcastSS ())

        {

          continue;

        }

      Cid cid = ssRecord->GetBasicCid ();

      OfdmUlMapIe ulMapIe;

      ulMapIe.SetCid (cid);

      if (ssRecord->GetPollForRanging () && ssRecord->GetRangingStatus () == WimaxNetDevice::RANGING_STATUS_CONTINUE)

        {

          // SS's ranging is not yet complete

          // allocating invited initial ranging interval

          ulMapIe.SetUiuc (OfdmUlBurstProfile::UIUC_INITIAL_RANGING);

          allocationSize = GetBs ()->GetRangReqOppSize ();

          SetIsInvIrIntrvlAllocated (true);

          if (availableSymbols >= allocationSize)

            {

              AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);

            }

          else

            {

              break;

            }

        }

      else

        {

          WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();

          // need to update because modulation/FEC to UIUC mapping may vary over time

          ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,

                                                                                 WimaxNetDevice::DIRECTION_UPLINK));

          // establish service flows for SS

          if (ssRecord->GetRangingStatus () == WimaxNetDevice::RANGING_STATUS_SUCCESS

              && !ssRecord->GetAreServiceFlowsAllocated ())

            {

              // allocating grant (with arbitrary size) to allow SS to send DSA messages DSA-REQ and DSA-ACK

              // only one DSA allocation per frame

              if (!allocationForDsa)

                {

                  allocationSize = GetBs ()->GetPhy ()->GetNrSymbols (sizeof(DsaReq), modulationType);

                  if (availableSymbols >= allocationSize)

                    {

                      AddUplinkAllocation (ulMapIe, allocationSize, symbolsToAllocation, availableSymbols);

                      allocationForDsa = true;

                    }

                  else

                    {

                      break;

                    }

                }

            }

          else

            {

              // all service flows associated to SS are established now

              /* Implementation of uplink scheduler

               * [1] Freitag, J.; da Fonseca, N.L.S., "Uplink Scheduling with Quality of Service in IEEE 802.16 Networks,"

               * Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE , vol., no., pp.2503-2508, 26-30 Nov. 2007

               * URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4411386&isnumber=4410910 */

              // Step 1

              if (availableSymbols)

                {

                  /*allocating grants for data transmission for UGS flows (Data Grant Burst Type IEs, 6.3.7.4.3.3)

                   (grant has been referred by different names e.g. transmission opportunity, slot,         uplink allocation, etc)*/

                  if (ssRecord->GetHasServiceFlowUgs ())

                    {

                      NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering be unicast polling");

                      // Recover period interval information for UGS flow

                      Time frame_duration = GetBs ()->GetPhy ()->GetFrameDuration ();

                      Time

                        (*(ssRecord->GetServiceFlows (ServiceFlow::SF_TYPE_UGS).begin ()))->GetRecord ()->GetLastGrantTime ()

                        + MilliSeconds ((*(ssRecord->GetServiceFlows (ServiceFlow::SF_TYPE_UGS).begin ()))->GetUnsolicitedGrantInterval ());

                      Time frame = Time ((timestamp - Simulator::Now ()) / frame_duration);

                      if (frame <= 1)

                        {

                          // UGS Grants

                          // It is not necessary to enqueue UGS grants once it is periodically served

                          ServiceUnsolicitedGrants (ssRecord,

                                                    ServiceFlow::SF_TYPE_UGS,

                                                    ulMapIe,

                                                    modulationType,

                                                    symbolsToAllocation,

                                                    availableSymbols);

                        }

                    }

                  // enqueue allocate unicast polls for rtPS flows if bandwidth is available

                  if (ssRecord->GetHasServiceFlowRtps ())

                    {

                      NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering rtps unicast polling");

                      Ptr<UlJob> jobRTPSPoll = CreateUlJob (ssRecord, ServiceFlow::SF_TYPE_RTPS, UNICAST_POLLING);

                      EnqueueJob (UlJob::HIGH, jobRTPSPoll);

                    }

                  if (ssRecord->GetHasServiceFlowNrtps ())

                    {

                      NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering nrtps unicast polling");

                      // allocate unicast polls for nrtPS flows if bandwidth is available

                      Ptr<UlJob> jobNRTPSPoll = CreateUlJob (ssRecord, ServiceFlow::SF_TYPE_NRTPS, UNICAST_POLLING);

                      EnqueueJob (UlJob::HIGH, jobNRTPSPoll);

                    }

                  if (ssRecord->GetHasServiceFlowBe ())

                    {

                      NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds () << " offering be unicast polling");

                      // finally allocate unicast polls for BE flows if bandwidth is available

                      Ptr<UlJob> jobBEPoll = CreateUlJob (ssRecord, ServiceFlow::SF_TYPE_BE, UNICAST_POLLING);

                      EnqueueJob (UlJob::HIGH, jobBEPoll);

                    }

                }

            }

        }

    }

  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " high queue has " << m_uplinkJobs_high.size ()<< " jobs - after sched");

  availableSymbolsAux = availableSymbols;

  uint32_t symbolsUsed = 0;

  symbolsUsed += CountSymbolsQueue (m_uplinkJobs_high);

  availableSymbolsAux -= symbolsUsed;

  // Step 2 - Check Deadline - Migrate requests with deadline expiring

  CheckDeadline (availableSymbolsAux);

  // Step 3 - Check Minimum Bandwidth

  CheckMinimumBandwidth (availableSymbolsAux);

  // Scheduling high priority queue

  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " high queue has " << m_uplinkJobs_high.size ()<< " jobs");

  while ((availableSymbols) && (!m_uplinkJobs_high.empty ()))

    {

      Ptr<UlJob> job = m_uplinkJobs_high.front ();

      OfdmUlMapIe ulMapIe;

      SSRecord * ssRecord = job->GetSsRecord ();

      enum ServiceFlow::SchedulingType schedulingType = job->GetSchedulingType ();

      Cid cid = ssRecord->GetBasicCid ();

      ulMapIe.SetCid (cid);

      WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();

      // need to update because modulation/FEC to UIUC mapping may vary over time

      ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,

                                                                             WimaxNetDevice::DIRECTION_UPLINK));

      ReqType reqType = job->GetType ();

      if (reqType == UNICAST_POLLING)

        {

          ServiceUnsolicitedGrants (ssRecord,

                                    schedulingType,

                                    ulMapIe,

                                    modulationType,

                                    symbolsToAllocation,

                                    availableSymbols);

        }

      else if (reqType == DATA)

        {

          ServiceFlow *serviceFlow = job->GetServiceFlow ();

          uint32_t allocSizeBytes = job->GetSize ();

          ServiceBandwidthRequestsBytes (serviceFlow,

                                         schedulingType,

                                         ulMapIe,

                                         modulationType,

                                         symbolsToAllocation,

                                         availableSymbols,

                                         allocSizeBytes);

        }

      m_uplinkJobs_high.pop_front ();

    }

  NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " interqueue has " << m_uplinkJobs_inter.size ()<< " jobs");

  /* Scheduling intermediate priority queue */

  while ((availableSymbols) && (!m_uplinkJobs_inter.empty ()))

    {

      NS_LOG_DEBUG ("At " << Simulator::Now ().GetSeconds ()<< " Scheduling interqueue");

      Ptr<UlJob> job = m_uplinkJobs_inter.front ();

      OfdmUlMapIe ulMapIe;

      SSRecord * ssRecord = job->GetSsRecord ();

      enum ServiceFlow::SchedulingType schedulingType = job->GetSchedulingType ();

      Cid cid = ssRecord->GetBasicCid ();

      ulMapIe.SetCid (cid);

      WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();

      // need to update because modulation/FEC to UIUC mapping may vary over time

      ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,

                                                                             WimaxNetDevice::DIRECTION_UPLINK));

      ReqType reqType = job->GetType ();

      if (reqType == DATA)

        {

          ServiceBandwidthRequests (ssRecord,

                                    schedulingType,

                                    ulMapIe,

                                    modulationType,

                                    symbolsToAllocation,

                                    availableSymbols);

        }

      else

        {

          NS_FATAL_ERROR ("Intermediate priority queue only should enqueue data packets.");

        }

      m_uplinkJobs_inter.pop_front ();

    }

  /* Scheduling low priority queue */

  while ((availableSymbols) && (!m_uplinkJobs_low.empty ()))

    {

      Ptr<UlJob> job = m_uplinkJobs_low.front ();

      OfdmUlMapIe ulMapIe;

      SSRecord * ssRecord = job->GetSsRecord ();

      enum ServiceFlow::SchedulingType schedulingType = job->GetSchedulingType ();

      Cid cid = ssRecord->GetBasicCid ();

      ulMapIe.SetCid (cid);

      WimaxPhy::ModulationType modulationType = ssRecord->GetModulationType ();

      // need to update because modulation/FEC to UIUC mapping may vary over time

      ulMapIe.SetUiuc (GetBs ()->GetBurstProfileManager ()->GetBurstProfile (modulationType,

                                                                             WimaxNetDevice::DIRECTION_UPLINK));

      ReqType reqType = job->GetType ();

      if (reqType == DATA)

        {

          ServiceBandwidthRequests (ssRecord,

                                    schedulingType,

                                    ulMapIe,

                                    modulationType,

                                    symbolsToAllocation,

                                    availableSymbols);

        }

      else

        {

          NS_FATAL_ERROR ("Low priority queue only should enqueue data packets.");

        }

      m_uplinkJobs_low.pop_front ();

    }

  OfdmUlMapIe ulMapIeEnd;

  ulMapIeEnd.SetCid (*(new Cid (0)));

  ulMapIeEnd.SetStartTime (symbolsToAllocation);

  ulMapIeEnd.SetUiuc (OfdmUlBurstProfile::UIUC_END_OF_MAP);

  ulMapIeEnd.SetDuration (0);

  m_uplinkAllocations.push_back (ulMapIeEnd);

  // setting DL/UL subframe allocation for the next frame

  GetBs ()->GetBandwidthManager ()->SetSubframeRatio ();

}

bool UplinkSchedulerMBQoS::ServiceBandwidthRequestsBytes (ServiceFlow *serviceFlow,

                                                          enum ServiceFlow::SchedulingType schedulingType, OfdmUlMapIe &ulMapIe,

                                                          const WimaxPhy::ModulationType modulationType,

                                                          uint32_t &symbolsToAllocation, uint32_t &availableSymbols, uint32_t allocationSizeBytes)

{

  uint32_t allocSizeBytes = allocationSizeBytes;

  uint32_t allocSizeSymbols = 0;

  ServiceFlowRecord *record = serviceFlow->GetRecord ();

  uint32_t requiredBandwidth = record->GetRequestedBandwidth ();

  if (requiredBandwidth > 0)

    {

      allocSizeSymbols = GetBs ()->GetPhy ()->GetNrSymbols (allocSizeBytes, modulationType);

      if (availableSymbols < allocSizeSymbols)

        {

          allocSizeSymbols = availableSymbols;

        }

      if (availableSymbols >= allocSizeSymbols)

        {

          NS_LOG_DEBUG (

            "At " << Simulator::Now ().GetSeconds ()<<" BS uplink scheduler, "

                  << serviceFlow->GetSchedulingTypeStr ()

                  << " allocation, size: " << allocSizeSymbols << " symbols"

                  << ", CID: "