이번 시간에는 저번에 공부했던 (m,k)firm deadline의 추가 공부에 IRSML 구현을 위해 ns3 코드 구현을 하였다.
* 본 글은 A Dynamic Priority Assignment Technique for Streams with (m,k)-Firm Deadlines를 읽고 작성한 글임.
(https://ieeexplore.ieee.org/document/477249)
Real Time System(Application)은 주어진 Task를 정해진 Deadline 내에 처리해야하는 구조를 의미한다.
여기서 Task는 Job들의 Set이다. 예를들어 Customer 1이 원하는 Task는 여러번의 Job에 걸쳐 처리해야하는 일인 것일 때,
해당 Task가 전부 처리되는 시점이 End Time이고 이 시점이 Deadline을 넘기면 안된다는 것이다.
여기서 생각해볼 점은 "Deadline"이다.
모든 Task들을 전부 Deadline을 철저히 지키며 System이 작동하면 당연히 정말 좋을 것이다.
그러나 잘생각해보면 Task의 개별 Job에 주어지는 시간은 해당 Task가 Resource를 독점하고 있다는 뜻이며, 그만큼 다른 Task들은 처리되지 못하고 있다는 뜻이다.
대부분의 환경에서 Resource는 무한하지 않으며, 설령 그렇게 Resource를 많이 마련해둘 수 있다고 해도 꽤나 고비용의 일이 될 것이다.
그러한 비용을 지불하면서 Task를 전부 Deadline에 맞춰야할까?
어떤 Task는 철저히 Deadline을 지켜야겠지만, 어떤 Task는 어느정도의 Deadline miss는 충분히 감내할 수 있다고 여길지도 모른다.
예를 들면, 구급차의 병원 도착 Deadline은 1분 1초가 철저히 지켜져야겠지만, 가족여행을 가는 가족들의 도착 시간은 1초가 아니라 5분 정도 혹은 그 이상도 충분히 감내할만한 딜레이일 것이다.
따라서 대부분의 상황에서 우리는 경찰차나 구급차들에게 교통 신호를 양보해준다.
이걸 이해하기 쉽게 고쳐 생각해보자. 구급차나 경찰차는 Hard deadline을 지니는 중요한 Task이며, 일반 차량들은 Soft deadline을 지니는 Task고, 일정시간마다 주어지는 교통 신호는 Resource인 것이다.
따라서 Deadline의 개념에는 Hard, Soft가 있으며 이들을 어떤 알고리즘을 통해 스케쥴링할 지가 Real Time System의 주요 고민이다. (Early Deadline First가 대부분의 상황에서 좋다고 배웠다.)
그러나 해당 논문에서는 Hard, Soft가 아닌 새로운 Deadline의 개념, 즉 "(m,k) deadline"을 제안하고 있다.
이 Deadline은 Hard와 Soft의 사이에 존재한다.
여기까지 이해를 하고 논문을 읽으면 좀 잘 읽힐 것이다.
1. INTRODUCTION
(m,k)-Firm은 Soft Deadline의 Frame Loss Rate에 주목한다.
우리가 영상이나 음악 등 "연속적"인 데이터를 소비한다고 치자.
기본적으로 이러한 연속적인 데이터는 당연히 데이터의 순서가 중요해진다.
디스코드 등 실시간성이 중요한 데이터들은 UDP로 전송이 되며 이들의 순서를 맞춰 재생시키는 것은 Application Layer의 몫이다.
따라서 이러한 실시간 연속 데이터들은 도착하는데로 "버퍼"에 축적된다.
이 버퍼 안에서는 도착한 데이터들이 순서대로 정렬되어 대기하며, 사용자에게 버퍼의 앞쪽부터 데이터를 계속 재생시켜주는 원리다.
여기서 1 데이터를 재생중인데, [2,3,4]가 loss되고 5,6,7이 있다고 가정해보자. 그럼 2,3,4가 버퍼에 도착할 때까지 재생을 멈출 수 밖에 없다.(버퍼링)
반대로 [5,6,7]이 loss되고 2,3,4가 있는 경우는 재생을 당장은 멈출 필요가 없다. 2,3,4를 재생하는 동안 5,6,7이 도착하면 되는 문제이기 때문이다.
그러나 (2,3,4) [5,6,7] 이나 [2,3,4] (5,6,7)이나 전부 똑같은 Packet Loss Rate를 가진다.
이러한 현상 때문에 Video stream이 10% loss rate 까지는 Tolerate 가능하다는 표현은 문제가 존재하게 된다.
(이러한 lost frame들이 얼마나 "잘" 위치하냐에 따라 달라짐.)
이를 해결하고자 고안된 개념이 "(m,k)-Firm Deadline" 개념이다.
(m,k)-Firm deadline을 지니는 Stream은 k개의 연속적인 customer 중 m개 이상의 customer가 deadline miss가 날 시 "Dynamic Failure"를 겪었다고 한다.
따라서 Stream이 Dynamic failure를 경험하는 지표가 서비스 품질이 허용 가능한 수준 아래로 얼마나 자주 떨어지는 가를 측정하는 지표가 된다.
본 논문에서는 이 Dynamic Failure를 줄이기 위해 Priority를 세밀하게 customer들에게 할당하는 접근을 한다.
( Distance-Based Priority(DBP) 방식은 각 Customer의 Stream에서 Deadline miss history를 기반으로 Priority를 할당하는 방식이다. )
Server는 이 Priority를 Deadline 등 다양한 Parameter와 함께 사용하여 Customer들을 스케쥴한다.
이러한 모델에서 Customer들은 2가지 갈래로 분류된다.(Mandatory, Optional)
Mandatory customer들은 항상 서비스된다. Optional의 경우는 best-effort로 서비스된다.
이러한 관점에서, (m.k)-Firm Stream은 k개의 연속적인 customer 중 m개의 Mandatory customer가 존재하는 방향으로 볼 수 있다.
이 접근 방식은 Dynamic Failure의 발생 확률은 상당히 낮추지만, Mandatory customer의 resource 점유로 인해 Deadline miss의 전반적인 확률은 늘어나는 결과를 초래할 것이다.
2. SYSTEM MODEL AND PROBLEM FORMULATION
위에 정의한 내용대로 생각해보면 (4,6)-firm deadline은 6개의 연속 Customer 중 3개 이상 연속되는 Miss Customer가 없어야한다는 뜻이다. 또한 (6-4)/6 => 33.33% 의 loss rate를 허용 가능하다는 뜻도 포함한다.
마찬가지로 (4,5)-firm deadline은 2개 이상 연속되는 Miss가 없어야하며 (5-4)/5 = 20 % loss rate를 허용한다는 뜻이다.
(8,10)-firm deadline은 허용 가능한 loss rate는 (4,5)-firm과 동일하지만 2개까지는 연속되는 Miss를 허용하므로 조금 더 느슨한 정의가 된다.
R1,R2,...,Rn까지 n개의 Real time Stream들을 가정하고 각자 Rj Stream은 (mj,kj)-firm deadline을 가진다고 가정해보자.
이러한 구조에서 Dynamic Failure를 감소시키기 위한 직관적인 approach는 Customer가 deadline miss가 나는 경우를 줄이는 것이다.
(애초에 단일 customer가 Deadline miss가 덜 나게 되면, k개중 m개의 Customer가 데드라인을 만족할 확률도 올라간다.)
Service Queue를 FIFO Queue라고 가정하고 이곳에 Streams(Customer)의 job들이 들어간다고 해보자.
여기서 어떤 Customer를 골라서 Service queue에 집어넣을지는 사용하는 Policy에 따라 달라진다.
위에 서술한 대로, 보통 EDF approach가 optimal한 결과를 낸다고 알려져있다.
(Deadline이 가까운 순서대로 service)
따라서 본 논문에서도 EDF가 사용된다고 가정한다.
그러나 이외에도 Service Policy에 대해 추가적인 정의가 필요한 점이 하나 있다.
일부 application에서는 System이 대기 중인 Customer가 Deadline miss된 Customer인지 아닌지를 판단할 수 있고, 어떤 application은 판단하지 못할 수도 있다.
판단이 가능할 경우 해당 Customer들을 drop 해버리면 되지만, 반대의 경우는 deadline missed Customer도 똑같이 처리해주어야한다.
본 논문에서 제시한 평가는 이러한 2 가지 가능성 모두를 고려한다.
3.DISTANCE-BASED PRIORITY ASSIGNMENT TECHNIQUE
각 Stream에 대해 System은 deadline을 만족한지, miss한지 여부를 기록해둔다.
각 Stream의 Customer를 도착 순서대로 1,2,3...과 같이 가정하자. Customer들은 Service를 받거나, 받지 못하고 삭제될 수 있다. Service 받은 Customer는 Deadline을 맞출 수도, 맞추지 못할 수도 있다.
(애초에 Service를 받지 못하고 삭제된 Customer는 Deadline missed Customer로 가정하자.)
S(i,j)를 Rj Stream으로 부터의 i번째 Customer의 Status라고 정의하자.
해당 상태는 Miss거나 meet일 것이다. 그러면 Rj stream의 state는 각 Customer들의 State 기록 나열로 목록화할 수 있다.
{ (S(i-kj,j), S(i-kj+1,j)...,S(i-1, j), S(i,j)) => Rj state history }
그러므로 Stream Rj의 State는 kj에 따라 2^kj 개의 상태가 가능하다.
만약 Rj가 mj 보다 적게 deadline meet을 한 상태라면 Dynamic Failure 발생으로 간주할 수 있으며, Rj가 Failing state에 있음을 의미한다.
어떻게 Stream을 Failing state가 되지 않게 할까?
단순하다. Failing state에 가까운 Stream일수록 그 Stream의 next Customer에게 더 높은 Priority를 주어 처리를 먼저 해주는 것이다.
논문의 방식에서는 Stream이 현재 상태에서 Failing State로 될 때까지 남은 연속적인 miss의 최소 횟수와 동일한 Priority가 설정된다. 우선 순위가 작으면 먼저 Service 된다.
(ex: 1개만 더 연속으로 miss나면 Failing -> Priority 1)
다음의 상태 전이 다이어그램을 보자. 이 Stream은 (2,3)-Firm Deadline이다. M은 meet, m은 miss이다.
(2,3)은 2개 이상 연속된 miss를 허용하지 않으며, 33.33% 까지의 loss rate 까지만 허용하겠다는 뜻이다.
따라서 빗금쳐진 (Mmm, mMm, mmM, mmm)은 miss state이다.
이 State Diagram 상에서 빗금에 가까워지면 가까워질 수록 Priority가 올라가게 되는 것이다.
빗금 상태에 Stream이 존재하게 된다면 Priority 0, MMm 이나 MmM, MMm에 존재하게 되면 Priority 1
mMM, MMM일 시 Priority 2가 할당될 것이다.
이러한 과정을 통해 Failing State에 있는 Stream의 빠른 복귀, Failing State로의 진입의 방지를 보장할 수 있다.
물론 동시에 Failing State에 가깝지 않은 Stream들에게는 loss를 유발할 수 있다. => Dynamic Failure 감소
(그러나 상술했듯이 (2,3,4) [5,6,7]의 형태로 loss가 난 Stream의 경우 충분히 기다릴만 하다.)
DBP 방식은 System 상에서 Stream들이 서로 다른 Deadline Requirement를 지닐 때 장점이 있다.
예를 들어 (3,5)-Firm (9,10)-Firm Stream 이 있다고 해보자.
(3,5) stream은 매 5개의 연속적인 Customer들 마다 2개까지의 연속 miss를 감당 가능할 것이다.
(40% loss rate)
(9,10)-Firm은 매 10개의 연속적인 Customer들마다 오직 1개의 miss만 감당 가능하다.
(10% loss rate)
이러한 구조에서 일반적인 Priority 채계는 개별적인 Timing requirement는 고려하지 않을 것이며 따라서 두 Stream에 대해 동일한 loss rate를 발생시킬 것이다.
DBP 방식에서는 (9,10) -Firm Dealine은 항상 실패 상태에서 2개 전에 존재하므로 일반적으로 (3,5) 보다 더 높은 Priority에 위치할 것이다.
그러나 그냥 더 엄격한 조건을 가진다고 더 높은 Priority를 주는 것은 아니다.
만약 (3,5)-Firm deadline Stream이 (9,10)-Firm의 높은 Priority에 의해 miss가 여러 개 발생하게 되면, 순간적으로 (9,10) Stream보다 더 높은 Priority에 존재하게 될 수도 있다.(Dynamic 한 Priority)
이제 이 것을 현실적으로 hardware에 어떻게 구현시킬지를 보자.
Rj Stream의 history는 kj-bit shift register에 저장할 수 있다.
0,1을 miss,meet이라고 치자. 매번 다음 Customer가 Service 될 때 해당 Customer의 State에 따라 0 or 1이 shift된다.
lj(n,s)를 오른쪽으로부터 Stream Rj의 state s에서 n번째 meet 기록(1)이라고 하자.
만약 s에서 1의 갯수가 n보다 작을 시 lj(n,s) = kj+1 이다.
( ex : (1,3)-Firm stream R1 => l1(1,MmM) = 1, l1(2,MmM) = 3, n>2일 시 l1(n,MmM)=k1+1=3+1=4 )
여기서 priority = kj-lj(mj,s)+1 로 정의된다.
만약 이전에 customer가 deadline을 놓쳤다면, 다음 customer는 한 단계 높은 Priority를 받을 것이다.
이전 Customer가 Deadline을 맞췄다면 Customer의 Priority는 Stream의 state에 따라 유지 or 감소될 수 있다.
- ns3
저번에 작성한 코드에서 문제를 조금 수정하고 NetAnim으로 xml 파일을 트레이싱 해보았다.
2024.01.30
#include <sstream>
#include <random>
#include <string>
#include "ns3/core-module.h"
#include "ns3/network-module.h"
#include "ns3/applications-module.h"
#include "ns3/mobility-module.h"
#include "ns3/config-store-module.h"
#include "ns3/netanim-module.h"
#include "ns3/internet-module.h"
#include "ns3/yans-wifi-helper.h"
#include "ns3/flow-monitor-module.h"
#include "ns3/aodv-helper.h"
#define SIMULATION_NUM 1020
#define SIMULATION_AREA 1000
#define SIMULATION_TIME 2400
#define APnum 17
#define TransmitPower 12
#define ReceiverSensitivity -76
#define TransmissionRange 250
#define BERthreshold 0.000001
#define MinSNR 25
#define dataRate 54
using namespace ns3;
NS_LOG_COMPONENT_DEFINE("IRSMLResult");
int numberOfMHs[7] = {30,35,40,45,50,55,60};
int APx[] = {250,500,750,200,400,600,800,250,500,750,200,400,600,800,250,500,750};
int APy[] = {166,166,166,333,333,333,333,500,500,500,665,665,665,665,832,832,832};
Ptr<PacketSink> psink1;
Ptr<PacketSink> psink2;
uint64_t lastTotalRx1=0;
uint64_t lastTotalRx2=0;
int
main(int argc, char* argv[]){
std::random_device rd;
//for(int i=0; i<SIMULATION_NUM; i++){
SeedManager::SetSeed(10);
SeedManager::SetRun(1);
//node 수 select
uint32_t nWifi;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dis(0,6);
nWifi = numberOfMHs[dis(gen)];
//AP
NodeContainer sinkNodes;
sinkNodes.Create(APnum);
NodeContainer adhocNodes;
adhocNodes.Create(nWifi);
NodeContainer allNodes;
allNodes.Add(sinkNodes);
allNodes.Add(adhocNodes);
NetDeviceContainer allDevicesMH;
NetDeviceContainer allDevicesAP;
//RTS&CTS setting
Config::SetDefault("ns3::WifiRemoteStationManager::RtsCtsThreshold",StringValue("0"));
//Set AP mobility model
MobilityHelper mobility;
Ptr<ListPositionAllocator> positionAlloc = CreateObject<ListPositionAllocator> ();
for(int i=0; i<APnum; i++){
positionAlloc->Add(Vector(APx[i],APy[i],0));
}
mobility.SetPositionAllocator(positionAlloc);
mobility.SetMobilityModel("ns3::ConstantPositionMobilityModel");
mobility.Install(sinkNodes);
//Set MH mobility Model
ObjectFactory points;
points.SetTypeId("ns3::RandomRectanglePositionAllocator");
points.Set("X",StringValue("ns3::UniformRandomVariable[Min=0.0|Max=1000.0]"));
points.Set("Y",StringValue("ns3::UniformRandomVariable[Min=0.0|Max=1000.0]"));
Ptr<PositionAllocator> waypos = points.Create() -> GetObject<PositionAllocator>();
mobility.SetMobilityModel("ns3::RandomWaypointMobilityModel",
"Speed",StringValue("ns3::UniformRandomVariable[Min=0.0|Max=20.0]"),
"Pause",StringValue("ns3::UniformRandomVariable[Min=0.0|Max=2.0]"),
"PositionAllocator",PointerValue(waypos));
mobility.Install(adhocNodes);
//Set Wifi
WifiHelper wifi;
wifi.SetStandard(WIFI_STANDARD_80211ac);
YansWifiPhyHelper wifiPhy;
YansWifiChannelHelper wifiChannel;
wifiChannel.SetPropagationDelay("ns3::ConstantSpeedPropagationDelayModel");
wifiChannel.AddPropagationLoss("ns3::RangePropagationLossModel","MaxRange",DoubleValue(TransmissionRange));
wifiPhy.SetErrorRateModel("ns3::YansErrorRateModel");
wifiPhy.SetChannel(wifiChannel.Create());
WifiMacHelper wifiMac;
wifi.SetRemoteStationManager("ns3::ConstantRateWifiManager","DataMode",StringValue("OfdmRate54Mbps"),"ControlMode",StringValue("VhtMcs0"));
wifiMac.SetType("ns3::AdhocWifiMac");
allDevicesMH = wifi.Install(wifiPhy,wifiMac,adhocNodes);
allDevicesAP = wifi.Install(wifiPhy,wifiMac,sinkNodes);
NetDeviceContainer allDevices = NetDeviceContainer(allDevicesAP, allDevicesMH);
//IPv4 setting
InternetStackHelper internet;
AodvHelper aodv;
internet.SetRoutingHelper(aodv);
internet.Install(allNodes);
Ipv4AddressHelper address;
address.SetBase("10.1.1.0","255.255.255.0");
Ipv4InterfaceContainer allInterfaces;
allInterfaces = address.Assign(allDevices);
uint16_t port1 = 9;
//sink app install to AP
PacketSinkHelper sink1 ("ns3::UdpSocketFactory",InetSocketAddress(Ipv4Address::GetAny(), port1));
ApplicationContainer apps_sink1 = sink1.Install(sinkNodes);
psink1 = StaticCast<PacketSink> (apps_sink1.Get(16));
psink2 = StaticCast<PacketSink> (apps_sink1.Get(9));
apps_sink1.Start(Seconds(0.0));
apps_sink1.Stop(Seconds(SIMULATION_TIME));
for(uint32_t i = 0; i<APnum; i++){
OnOffHelper client("ns3::UdpSocketFactory", InetSocketAddress(allInterfaces.GetAddress(i), port1));
client.SetAttribute("OnTime", StringValue("ns3::ConstantRandomVariable[Constant=1]"));
client.SetAttribute("OffTime", StringValue("ns3::ConstantRandomVariable[Constant=1]"));
client.SetAttribute("DataRate", DataRateValue(DataRate(dataRate)));
ApplicationContainer clientApp = client.Install(adhocNodes);
clientApp.Start(Seconds(2.0));
clientApp.Stop(Seconds(SIMULATION_TIME - 2));
}
Ptr<FlowMonitor> flowmon;
FlowMonitorHelper flowmonHelper;
flowmon = flowmonHelper.InstallAll();
AnimationInterface anim("IRSML_demo.xml");
anim.SetMobilityPollInterval(Seconds(2.0));
anim.SetMaxPktsPerTraceFile(99999999);
for(int i=0; i<APnum; i++){
anim.UpdateNodeSize(i,6,6);
anim.SetConstantPosition(sinkNodes.Get(i),APx[i],APy[i],0);
anim.UpdateNodeColor(i,255,255,102);
anim.UpdateNodeDescription(i,"AP"+std::to_string(i));
}
for(uint32_t i=APnum; i<allDevices.GetN();i++){
anim.UpdateNodeDescription(i,"MH"+std::to_string(i));
}
anim.EnablePacketMetadata(true);
anim.EnableIpv4RouteTracking("IRSML_routetable.xml",Seconds(1),Seconds(SIMULATION_TIME-1),Seconds(SIMULATION_TIME/2));
anim.EnableIpv4L3ProtocolCounters(Seconds(0),Seconds(SIMULATION_TIME-1));
anim.EnableQueueCounters(Seconds(0),Seconds(SIMULATION_TIME-1));
wifiPhy.SetPcapDataLinkType(WifiPhyHelper::DLT_IEEE802_11_RADIO);
wifiPhy.EnablePcap("IRSML",allDevicesAP.Get(0));
wifiPhy.EnablePcap("IRSML-Mobile",allDevicesMH.Get(0));
Simulator::Stop(Seconds(SIMULATION_TIME));
Simulator::Run();
flowmon->SerializeToXmlFile("IRSML_flowmetrics.xml",true,true);
double average1 = ((psink1->GetTotalRx()*8)/(1e6*SIMULATION_TIME));
double average2 = ((psink2->GetTotalRx()*8))/(1e6*SIMULATION_TIME);
lastTotalRx1=psink1->GetTotalRx();
lastTotalRx2=psink2->GetTotalRx();
Simulator::Destroy();
std::cout<<"\n 17 Access Point Average throughput: "<<average1<<" Mbit/s"<<std::endl;
std::cout<<"\n 17 Access Point LastTotalRx: "<<lastTotalRx1<<" Mbit"<<std::endl;
std::cout<<"\n 4 Access Point Average throughput: "<<average2<<" Mbit/s"<<std::endl;
std::cout<<"\n 4 Access Point LastTotalRx: "<<lastTotalRx2<<" Mbit"<<std::endl;
//}
}우선 문제는 저번 코드에서는 allDevices에 allMH, allAP 순으로 저장을 하였으나, MH의 onoff application의 연결 대상 IP로
allDevices의 첫번째 디바이스부터 Apnum(17)만큼을 지정해주어 MH들이 MH(0~16)에 연결하려고 하여 오류가 났었다.
따라서 allDevices의 저장 순서를 바꾸어주었고, NetAnim으로 결과를 트레이싱 하기위해 해당 부분 코드도 작성해두었다.
또한 우선적으로 실행한 데이터가 있어야 ML을 돌릴 데이터를 뽑을 수 있으므로 첫 알고리즘은 Distance Vector(AODV)로 지정하였다.
그리고 실행을 해보았다.
정상적으로 각 AP를 거쳐간 데이터, 평균 throughput이 나온다.
그러나, 제대로 정상 작동을 하는지 알기 위해 NetAnim에 결과 xml 파일을 연결했으나 xml 파일이 너무 커 자꾸 힙 메모리 문제가 생겼다.
결과 xml file은 1.42 GB 였다.
또한 현재 코드 역시 문제점이 많다.
우선 Throughput이 아무리 봐도 너무 적고, 제대로 데이터가 오가는 과정이 NetAnim에 찍히지 않는다는 것이다.
다음 시간에는 코드의 문제점을 찾고 고쳐야겠다.
'모각코(개인 활동 계획)' 카테고리의 다른 글
| 모각코 여섯 번째 모임 개인 계획, 활동 과정 및 결과 (0) | 2024.02.07 |
|---|---|
| 모각코 다섯 번째 모임 개인 계획, 활동 과정 및 결과 (0) | 2024.02.02 |
| 모각코 세 번째 모임 개인 계획, 활동과정 및 결과 (0) | 2024.01.19 |
| 모각코 두 번째 모임 개인 계획, 활동과정 및 결과 (0) | 2024.01.13 |
| 모각코 첫 번째 모임 개인 계획, 활동과정 및 결과 (0) | 2024.01.06 |