Recoders with Erasure Channels

This example considers a transmitter sending coded packets with RLNC from a generation size g and field size q to a decoder. Packets are set through N relays in a broadcast erasure channel. Each link from the encoder to the relays has the same erasure rate \epsilon_{E-R}. In the second hop, all the links from the relays to the decoder have a common erasure rate \epsilon_{R-D}. By default, we consider: g = 5, q = 2^{8}, N = 2, \epsilon_{E-R} = 0.4 and \epsilon_{R-D} = 0.2. Topology is shown as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//                +-----------------------------------------------+
//                |             Encoder (Node 0)                  |
//                |                                               |
//                | Net Device 1   Net Device 2  ..  Net Device N |
//                | IP: 10.1.1.1   IP: 10.1.2.1  ..  IP: 10.1.N.1 |
//                |                                               |
//                |     +---+         +---+             +---+     |
//                |     |   |         |   |             |   |     |
//                +-----+-+-+---------+-+-+-------------+-+-+-----+
//                        |             |                 |
//     eE-R  +------------+        eE-R |           eE-R  +-------+
//           |                          |                         |
//+--------+-v-+-------+     +--------+-v-+-------+    +--------+-v-+-------+
//|        |   |       |     |        |   |       |    |        |   |       |
//|        +-+-+       |     |        +-+-+       |    |        +-+-+       |
//|    Net Device 1    |     |    Net Device 1    | .. |    Net Device 1    |
//|    IP: 10.1.1.2    |     |    IP: 10.1.2.2    | .. |    IP: 10.1.N.N    |
//|                    |     |                    |    |                    |
//| Recoder 1 (Node 1) |     | Recoder 2 (Node 2) | .. | Recoder N (Node N) |
//|                    |     |                    |    |                    |
//|    Net Device 2    |     |    Net Device 2    | .. |    Net Device 2    |
//|    IP: 10.2.1.1    |     |    IP: 10.2.1.3    | .. |    IP: 10.2.1.2N+1 |
//|                    |     |                    |    |                    |
//|        +---+       |     |        +---+       |    |        +---+       |
//|        |   |       |     |        |   |       |    |        |   |       |
//+--------+-+-+-------+     +--------+-+-+-------+    +--------+-+-+-------+
//           |                          |                         |
//           +-----------+  eR-D        |  eR-D           +-------+  eR-D
//                       |              |                 |
//               +-----+-v-+----------+-v-+-------------+-v-+----+
//               |     |   |          |   |             |   |    |
//               |     +---+          +---+             +---+    |
//               |                                               |
//               |             Decoder (Node N+1)                |
//               |                                               |
//               | Net Device 1   Net Device 2  ..  Net Device N |
//               | IP: 10.2.1.2   IP: 10.2.1.4  ..  IP: 10.2.1.2N|
//               +-----------------------------------------------+

//                           N: Number of recoders
//                           eE-R: errorRateEncoderRecoders
//                           eR-D: errorRateRecodersDecoder

What to Simulate

  • Behavior: The sender keeps transmitting the generation until the all the relays have g linearly independent (l.i.) coded packets. The relays keep sending packets until the decoder has received this data. As with previous examples, packets might or might not be loss at the given erasure rates in the respective links. Additionally, we have 2 transmission policies depending if recoding is enabled or not. If recoding is enabled (default), received packets in each recoder are recoded to create new coded packets which are sent to the decoder. If recoding is disabled, any previously received packet is forwarded to the decoder. The packet to be forwarded is selected at random. To avoid collisions from the relays, all the relays access the medium to transmit with probability p. If two or more relays access the medium at the same time, then event simulator schedules them to transmit in a non-colliding order.
  • Inputs: Main parameters will be generation size, field size, number of relays, packet losses in each hop, a boolean flag for the recoding policy and a transmit probability to access the shared medium.
  • Outputs: Two counters to indicate how much transmissions did the process required and some prints to indicate when decoding is completed. The number of transmissions should change as we vary the input parameters.
  • Scenarios: We will variate the generation and field size to verify theoretical expected values regarding the amount of transmissions to decode.

Program Description

In your ~/ns-3-dev/examples/kodo folder, you will see the kodo-recoders.cc file which contains the source code of this simulation. Its structure is similar to previous simulations, so again we will focus on the main differences.

Header Includes

1
#include "kodo-recoders.h"

The Recoders class in kodo-recoders.h is used to model the expected behavior of the nodes in our simulation.

Simulation Class

The Recoders class can be roughly defined in the following way:

class Recoders
{
public:

  Recoders (const kodocpp::codec codeType, const kodocpp::field field,
    const uint32_t users, const uint32_t generationSize, const uint32_t packetSize,
    const std::vector<ns3::Ptr<ns3::Socket>>& recodersSockets,
    const bool recodingFlag)
    : m_codeType (codeType),
      m_field (field),
      m_users (users),
      m_generationSize (generationSize),
      m_packetSize (packetSize),
      m_recodingFlag (recodingFlag),
      m_recodersSockets (recodersSockets)
  {
    // Constructor
  }

  void SendPacketEncoder (ns3::Ptr<ns3::Socket> socket, ns3::Time pktInterval)
  {
    // Encoder logic
  }

  void ReceivePacketRecoder (ns3::Ptr<ns3::Socket> socket)
  {
    // Recoders logic for reception
  }

  void SendPacketRecoder (ns3::Ptr<ns3::Socket> socket, ns3::Time pktInterval)
  {
    // Recoders logic for transmission
  }

  void ReceivePacketDecoder (ns3::Ptr<ns3::Socket> socket)
  {
    // Decoder logic
  }

private:

  const kodocpp::codec m_codeType;
  const kodocpp::field m_field;
  const uint32_t m_users;
  const uint32_t m_generationSize;
  const uint32_t m_packetSize;
  const bool m_recodingFlag;

  kodocpp::encoder m_encoder;
  std::vector<uint8_t> m_encoderBuffer;
  std::vector<kodocpp::decoder> m_recoders;
  std::vector<std::vector<uint8_t>> m_recoderBuffers;
  kodocpp::decoder m_decoder;
  std::vector<uint8_t> m_decoderBuffers;
  std::vector<ns3::Ptr<ns3::Socket>> m_recodersSockets;

  std::vector<uint8_t> m_payload;
  uint32_t m_encoderTransmissionCount;
  uint32_t m_recodersTransmissionCount;
  uint32_t m_decoderRank;
  std::map<uint32_t, std::map<uint32_t, ns3::Ptr<ns3::Packet>>> m_previousPackets;

  const double m_transmitProbability;
  ns3::Ptr<ns3::UniformRandomVariable> m_uniformRandomVariable;
};

The Recoders design is similar as the one for Broadcast. Still, some differences exist. For this case kodocpp::decoder is the type for the relays since it behaves in the same way.

Also, now we add different functions for what a relay might perform. Hereby, we include SendPacketRecoder and ReceivePacketRecoder to split the functionality of recoding (or forwarding) and receiving with decoding. The recoding functionality is performed again with recoder.write_payload ().

For control variables, for the recoding or forwarding behavior, we included a boolean as a construction argument. Also we keep track of the decoder rank with a counter, in order to notify when a coded packet is received at the decoder. Furthermore, for each of the relays we store its received packets so we can forward one of them at random later.

For the medium probability access p, we use samples from a ns3::Ptr<ns3::UniformRandomVariable> and convert them to samples of a Bernoulli random variable at a given transmission using the Inverse Transmformating Sampling. In this way, we guarantee that a node attemps a medium access with the desired probability. Finally, we include a counter for the total number of transmissions from all the relays for counting total transmissions in general.

Default Parameters and Command-line Parsing

For the default parameters, we show what has been added for this example:

// Main parameters
double errorRateEncoderRecoder = 0.4; // Error rate for encoder-recoder link
double errorRateRecoderDecoder = 0.2; // Error rate for recoder-decoder link
bool recodingFlag = true; // Flag to control recoding
uint32_t recoders = 2; // Number of recoders
std::string field = "binary"; // Finite field used
double transmitProbability = 0.5; // Transmit probability for the relays

// Command parsing
cmd.AddValue ("errorRateEncoderRecoder",
              "Packet erasure rate for the encoder-recoder link",
              errorRateEncoderRecoder);
cmd.AddValue ("errorRateRecoderDecoder",
              "Packet erasure rate for the recoder-decoder link",
              errorRateRecoderDecoder);
cmd.AddValue ("recodingFlag", "Enable packet recoding", recodingFlag);
cmd.AddValue ("recoders", "Amount of recoders", recoders);
cmd.AddValue ("field", "Finite field used", field);
cmd.AddValue ("transmitProbability", "Transmit probability from recoder",
              transmitProbability);

Topology and Net Helpers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
  // We group the nodes in different sets because
  // we want many net devices per node. For the broadcast
  // topology we create a subnet and for the recoders to
  // the decoders, we create a secondary one. This in order to
  // properly set the net devices and socket connections later


  // First we set the basic helper for a single link.
  PointToPointHelper ptp;

  // Encoder to recoders
  PointToPointStarHelper toRecoders (recoders, ptp);
  NodeContainer decoder;
  decoder.Create (1);

  // Recoders to decoder
  NetDeviceContainer recodersDecoderDev;

  for (uint32_t n = 0; n < recoders; n++)
   {
      recodersDecoderDev.Add (ptp.Install (
        NodeContainer (toRecoders.GetSpokeNode (n), decoder.Get (0))) );
   }

  // Internet stack for the broadcast topology and decoder
  InternetStackHelper internet;
  toRecoders.InstallStack (internet);
  internet.Install (decoder);

  // Here, we first create a total of N net devices in the encoder
  // (N = recoders amount) and a net device per recoder
  // Second, we mirror this procedure in the second hop.
  // Each net device in the recoder is in a different subnet.

  toRecoders.AssignIpv4Addresses (Ipv4AddressHelper ("10.1.1.0",
    "255.255.255.0"));

  // The IP set of the recoders to the decoder is calculated
  // in order to not collide with the one from the encoder
  // to the recoders.
  Ipv4AddressHelper fromRecoders ("10.2.1.0", "255.255.255.0");
  fromRecoders.Assign (recodersDecoderDev);

In order to be able to construct various net devices in the relays from the helpers, we separate the relays in 2 subnets: a one-to-many subnet which covers the encoder and the relays, and a many-to-one subnet which covers the relays and the decoder. For the one-to-many (broadcast) subnet, we use the PointToPointStarHelper and for the many-to-one we create the net devices with the Install member function of the PointToPointHelper and store it in a container for easy IP address assignment. Then, we assign the IP addresses as shown in the previous topology figure. For the one-to-many, we use the "10.1.X.X" subnet and for the many-to-one, the "10.2.1.X" subnet.

Simulation Event Handler

1
2
3
4
5
6
7
  // Recoders
  for (auto recoderSocket : recodersSockets)
    {
      Simulator::ScheduleWithContext (recoderSocket->GetNode ()->GetId (),
        Seconds (1.5), &Recoders::SendPacketRecoder,
        &multihop, recoderSocket, interPacketInterval);
    }

Now we aggregate the generation of coded packets from the relays to the scheduling process. We send packets from each recoder independently from previously having received a packet. However, the recoder will only send coded packets from the coded packets that it has l.i. packets and it sucessfully access the medium. If some relays send their coded packet at, the same time, the event scheduling organizes them properly.

Simulation Runs

Default Run

To run the default simulation, just type:

python waf --run kodo-recoders

You will see an output similar to this:

+-----------------------------------+
|Sending a coded packet from ENCODER|
+-----------------------------------+
Received a packet at RECODER 2
+-------------------------------------+
|Sending a coded packet from RECODER 2|
+-------------------------------------+
Received an innovative packet at DECODER!
Decoder rank: 1

+-----------------------------------+
|Sending a coded packet from ENCODER|
+-----------------------------------+
Received a packet at RECODER 1
+-------------------------------------+
|Sending a coded packet from RECODER 1|
+-------------------------------------+
+-------------------------------------+
|Sending a coded packet from RECODER 2|
+-------------------------------------+
Received an innovative packet at DECODER!
Decoder rank: 2

+-----------------------------------+
|Sending a coded packet from ENCODER|
+-----------------------------------+
Received a packet at RECODER 1
+-------------------------------------+
|Sending a coded packet from RECODER 1|
+-------------------------------------+
+-------------------------------------+
|Sending a coded packet from RECODER 2|
+-------------------------------------+
Received an innovative packet at DECODER!
Decoder rank: 3

*** Decoding completed! ***
Encoder transmissions: 3
Recoders transmissions: 5
Total transmissions: 8

From the simulation output, it can be seen that in the first transmission only recoder 2 got the coded packet from the source and it conveyed properly to the decoder. Here recoder 1 does not make any transmissions since it does not have any possible information to convey. For the second and third transmission, recoder 1 got the packet and conveyed properly to the decoder. Observe that for the second and third transmissions, recoder 2 did not get any coded packets but it still tries to send them. However, it will only be possible to send only one degree of freedom given that its set of packets only allow this. Whenever it receives more combinations, it will be possible for it to send more. You can modify the number of relays and erasure rates in the hops to check the effects in the number of transmissions. Also, you may verify the pcap traces as well. We invite you to modify the parameters as you might prefer to verify your intuitions and known results.