IT++ Logo
selective_repeat.cpp
Go to the documentation of this file.
00001 
00029 #include <itpp/protocol/selective_repeat.h>
00030 #include <cstdlib>
00031 
00033 
00034 namespace itpp
00035 {
00036 
00037 bool in_sequence(const int a, const int b, const int L)
00038 {
00039   it_assert(a >= 0 && a < L, "in_sequence(): ");
00040   it_assert(b >= 0 && b < L, "in_sequence(): ");
00041   return ((b - a + L) % L) < L / 2;
00042 }
00043 
00044 Selective_Repeat_ARQ_Sender::Selective_Repeat_ARQ_Sender()
00045 {
00046   parameters_ok = false;
00047   packet_input.set_name("Selective_Repeat_ARQ_Sender packet_input Slot");
00048   packet_input.forward(this, &Selective_Repeat_ARQ_Sender::handle_packet_input);
00049   ack_input.set_name("Selective_Repeat_ARQ_Sender ack_input Slot");
00050   ack_input.forward(this, &Selective_Repeat_ARQ_Sender::handle_ack_input);
00051   query_nof_ready_packets.set_name("Selective_Repeat_ARQ_Sender query_nof_ready_packets Slot");
00052   query_nof_ready_packets.forward(this, &Selective_Repeat_ARQ_Sender::handle_query_nof_ready_packets);
00053   packet_output_request.set_name("Selective_Repeat_ARQ_Sender packet_output_request Slot");
00054   packet_output_request.forward(this, &Selective_Repeat_ARQ_Sender::handle_packet_output_request);
00055 
00056 }
00057 
00058 Selective_Repeat_ARQ_Sender::Selective_Repeat_ARQ_Sender(const int Seq_no_size, const int Buffer_size_factor, const int Link_packet_size, const Ttype Time_out)
00059 {
00060   set_parameters(Seq_no_size, Buffer_size_factor, Link_packet_size, Time_out);
00061   packet_input.set_name("Selective_Repeat_ARQ_Sender packet_input Slot");
00062   packet_input.forward(this, &Selective_Repeat_ARQ_Sender::handle_packet_input);
00063   ack_input.set_name("Selective_Repeat_ARQ_Sender ack_input Slot");
00064   ack_input.forward(this, &Selective_Repeat_ARQ_Sender::handle_ack_input);
00065   query_nof_ready_packets.set_name("Selective_Repeat_ARQ_Sender query_nof_ready_packets Slot");
00066   query_nof_ready_packets.forward(this, &Selective_Repeat_ARQ_Sender::handle_query_nof_ready_packets);
00067   packet_output_request.set_name("Selective_Repeat_ARQ_Sender packet_output_request Slot");
00068   packet_output_request.forward(this, &Selective_Repeat_ARQ_Sender::handle_packet_output_request);
00069 }
00070 
00071 Selective_Repeat_ARQ_Sender::~Selective_Repeat_ARQ_Sender()
00072 {
00073   std::cout << "no_retransmit = " << no_retransmit << std::endl;
00074 }
00075 
00076 void Selective_Repeat_ARQ_Sender::set_parameters(const int Seq_no_size,
00077     const int Buffer_size_factor,
00078     const int Link_packet_size,
00079     const Ttype Time_out)
00080 {
00081   it_assert((0 < Seq_no_size) && (Seq_no_size <= 30),
00082             "Selective_Repeat_ARQ_Sender::set_parameters(): ");
00083   it_assert((0 < Buffer_size_factor) && (Buffer_size_factor <= 10),
00084             "Selective_Repeat_ARQ_Sender::set_parameters(): ");
00085   it_assert(Link_packet_size > 0, "Selective_Repeat_ARQ_Sender::set_parameters(): ");
00086   it_assert(Time_out > 0, "Selective_Repeat_ARQ_Sender::set_parameters(): ");
00087   seq_no_size = Seq_no_size;
00088   link_packet_size = Link_packet_size;
00089   seq_no_max = 1 << Seq_no_size;
00090   input_buffer_size = seq_no_max * Buffer_size_factor;
00091   input_buffer.set_size(input_buffer_size);
00092   for (int l = 0; l < input_buffer_size; input_buffer(l++) = NULL);
00093   input_free_space = input_buffer_size;
00094   input_next = 0;
00095   tx_next = 0;
00096   tx_last = 0;
00097   time_out = Time_out;
00098   timer.set_size(seq_no_max);
00099   for (int l = 0; l < seq_no_max; timer(l++).forward(this, &Selective_Repeat_ARQ_Sender::retransmit));
00100   outstanding = 0;
00101   seq_no = 0;
00102   output_indexes.set_size(seq_no_max);
00103   output_indexes.ones();
00104   output_indexes *= -1;
00105   retransmission_indexes.set_size(seq_no_max);
00106   retransmission_indexes.ones();
00107   retransmission_indexes *= -1;
00108   rd_pos = 0;
00109   rt_pos = 0;
00110   scheduled_total = 0;
00111   scheduled_retransmissions = 0;
00112   no_retransmit = 0;
00113   parameters_ok = true;
00114   ip_pkt_queue.set_max_byte_size(1500*32);
00115   id = 0;
00116 }
00117 
00118 void Selective_Repeat_ARQ_Sender::handle_ack_input(Array<Packet*> packet_array)
00119 {
00120   Packet *packet = packet_array(0);
00121   ACK *A = (ACK *) packet;
00122 
00123   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::handle_ack_input(): ");
00124   it_assert(A, "Selective_Repeat_ARQ_Sender::handle_ack_input(): ");
00125   it_assert(A->seq_no >= 0 && A->seq_no < seq_no_max, "Selective_Repeat_ARQ_Sender::handle_ack_input(): ");
00126   if (outstanding) {
00127     if (in_sequence(tx_last % seq_no_max, A->seq_no, seq_no_max))
00128       remove(A->seq_no);
00129     while (!input_buffer(tx_last) && outstanding) {
00130       outstanding--;
00131       input_free_space++;
00132       tx_last = (tx_last + 1) % input_buffer_size;
00133     }
00134   }
00135   delete A;
00136   fill_output();
00137 }
00138 
00139 void Selective_Repeat_ARQ_Sender::handle_packet_input(Packet *packet)
00140 {
00141   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::handle_packet_input(): ");
00142   it_assert(packet, "Selective_Repeat_ARQ_Sender::handle_packet_input(): ");
00143   ip_pkt_queue.push(packet);
00144 
00145 }
00146 
00147 // The number of blocks in the ip_pkt_queue that can be scheduled to be
00148 // transmitted (in the tx buffer)
00149 int Selective_Repeat_ARQ_Sender::feasable_blocks()
00150 {
00151   div_t q = div(ip_pkt_queue.byte_size(), link_packet_size);
00152   int blocks_in_ip_queue = (q.rem) ? q.quot + 1 : q.quot;
00153   return std::min(free_sequence_numbers(),
00154                   buffered_non_outstanding() +
00155                   std::min(blocks_in_ip_queue, input_free_space));
00156 }
00157 
00158 
00159 void Selective_Repeat_ARQ_Sender::handle_query_nof_ready_packets(void*)
00160 {
00161   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::handle_query_nof_ready_packets(): ");
00162   nof_ready_packets(scheduled_total + feasable_blocks());
00163 }
00164 
00165 void Selective_Repeat_ARQ_Sender::handle_packet_output_request(const int nbr_blocks_requested)
00166 {
00167   int nbr_blocks_to_tx;
00168   int feasable_blks = feasable_blocks();
00169   if (nbr_blocks_requested <= scheduled_total + feasable_blks) {
00170     nbr_blocks_to_tx = nbr_blocks_requested;
00171   }
00172   else {
00173     it_warning("Number of requested blocks is more than what is possible to transmitt");
00174     nbr_blocks_to_tx = scheduled_total + feasable_blks;
00175   }
00176 
00177   //int nbr_ip_pkts_in_q = ip_pkt_queue.size();
00178   while (nbr_blocks_to_tx > scheduled_total) {
00179     it_assert(!ip_pkt_queue.empty(), "Selective_Repeat_ARQ_Sender::handle_packet_output_request(): ");
00180     Packet *packet = ip_pkt_queue.front();
00181     ip_pkt_queue.pop();
00182     push_packet_on_tx_buffer(packet);
00183   }
00184 
00185   Array<Packet*> tmp;
00186   get_link_packets(nbr_blocks_requested, tmp);
00187   packet_output(tmp);
00188 }
00189 
00190 void Selective_Repeat_ARQ_Sender::push_packet_on_tx_buffer(Packet *packet)
00191 {
00192   L3_Packet_Info *pkt_info = new L3_Packet_Info(packet);
00193   int packet_byte_size = pkt_info->pkt_pointer->bit_size() / 8;
00194   int nbr_blocks = packet_byte_size / link_packet_size;
00195   if (nbr_blocks*link_packet_size != packet_byte_size)
00196     nbr_blocks++;
00197   if (input_free_space >= nbr_blocks) {
00198     pkt_info->timestamp = Event_Queue::now();
00199     for (int n = nbr_blocks - 1; n >= 0; n--) {
00200       input_buffer(input_next) = new Link_Packet(-1, n, pkt_info);
00201       input_free_space--;
00202       input_next = (input_next + 1) % input_buffer_size;
00203     }
00204   }
00205   else {
00206     buffer_overflow(0);
00207     it_error("Selective_Repeat_ARQ_Sender::push_packet_on_tx_buffer(): "
00208              "Stopped due to buffer overflow");
00209   }
00210   fill_output();
00211 
00212 }
00213 
00214 void Selective_Repeat_ARQ_Sender::fill_output()
00215 {
00216   int packets_2_output = std::min(free_sequence_numbers(), buffered_non_outstanding());
00217   while (packets_2_output) {
00218     input_buffer(tx_next)->seq_no = seq_no;
00219     outstanding++;
00220     schedule_output(tx_next, seq_no, false);
00221     seq_no = (seq_no + 1) % seq_no_max;
00222     tx_next = (tx_next + 1) % input_buffer_size;
00223     packets_2_output--;
00224   }
00225 }
00226 
00227 void Selective_Repeat_ARQ_Sender::schedule_output(const int Buffer_index, const int Sequence_number, const bool Retransmission)
00228 {
00229   it_assert(input_buffer(Buffer_index) != NULL, "Selective_Repeat_ARQ_Sender::schedule_output(): ");
00230   if (output_indexes(Sequence_number) == -1)
00231     scheduled_total++;
00232   output_indexes(Sequence_number) = Buffer_index;
00233   if (Retransmission) {
00234     if (retransmission_indexes(Sequence_number) != 1) // This is a new retransmission.
00235       scheduled_retransmissions++;
00236     retransmission_indexes(Sequence_number) = 1; // Mark packet (index) for retransmission.
00237   }
00238   else // Mark packet (index) for first time transmission.
00239     retransmission_indexes(Sequence_number) = 0;
00240 }
00241 
00242 void Selective_Repeat_ARQ_Sender::get_link_packets(const int K, Array<Packet*> &pa)
00243 {
00244   int packets_2_retransmit = std::min(K, scheduled_retransmissions);
00245   int new_packets_2_transmit = std::min(K, scheduled_total) - packets_2_retransmit;
00246   scheduled_retransmissions -= packets_2_retransmit;
00247   scheduled_total -= packets_2_retransmit + new_packets_2_transmit;
00248   pa.set_size(packets_2_retransmit + new_packets_2_transmit);
00249   int l = 0;
00250   while (packets_2_retransmit) { // Retransmissions have priority over ...
00251     if (retransmission_indexes(rt_pos) == 1) {
00252       timer(rt_pos).set(rt_pos, time_out);
00253       pa(l++) = (Packet *) new Link_Packet(*input_buffer(output_indexes(rt_pos)));
00254       output_indexes(rt_pos) = -1;
00255       retransmission_indexes(rt_pos) = -1;
00256       packets_2_retransmit--;
00257     }
00258     rt_pos = (rt_pos + 1) % seq_no_max;
00259   }
00260   while (new_packets_2_transmit) { // new packets.
00261     if (output_indexes(rd_pos) != -1) {
00262       timer(rd_pos).set(rd_pos, time_out);
00263       pa(l++) = (Packet *) new Link_Packet(*input_buffer(output_indexes(rd_pos)));
00264       output_indexes(rd_pos) = -1;
00265       new_packets_2_transmit--;
00266     }
00267     rd_pos = (rd_pos + 1) % seq_no_max;
00268   }
00269 }
00270 
00271 void Selective_Repeat_ARQ_Sender::remove(const int Sequence_number)
00272 {
00273   if (output_indexes(Sequence_number) != -1) {
00274     output_indexes(Sequence_number) = -1;
00275     scheduled_total--;
00276     if (retransmission_indexes(Sequence_number) == 1)
00277       scheduled_retransmissions--;
00278     retransmission_indexes(Sequence_number) = -1;
00279   }
00280   const int i = sequence_number_2_buffer_index(Sequence_number);
00281   if (input_buffer(i)) {
00282     timer(Sequence_number).cancel(); // Cancel the retransmission timer.
00283     it_assert(input_buffer(i)->seq_no == Sequence_number, "Selective_Repeat_ARQ_Sender::remove(): ");
00284     delete input_buffer(i);
00285     input_buffer(i) = NULL;
00286   }
00287 }
00288 
00289 void Selective_Repeat_ARQ_Sender::retransmit(const int Sequence_number)
00290 {
00291   no_retransmit++;
00292   const int buffer_index = sequence_number_2_buffer_index(Sequence_number);
00293   schedule_output(buffer_index, Sequence_number, true);
00294 }
00295 
00296 int Selective_Repeat_ARQ_Sender::buffered_non_outstanding()
00297 {
00298   return input_buffer_size - input_free_space - outstanding;
00299 }
00300 
00301 int Selective_Repeat_ARQ_Sender::free_sequence_numbers()
00302 {
00303   return seq_no_max / 2 - outstanding;
00304 }
00305 
00306 int Selective_Repeat_ARQ_Sender::sequence_number_2_buffer_index(const int Sequence_number)
00307 {
00308   it_assert(input_buffer(tx_last), "Selective_Repeat_ARQ_Sender::sequence_number_2_buffer_index(): ");
00309   it_assert(input_buffer(tx_last)->seq_no != -1, "Selective_Repeat_ARQ_Sender::sequence_number_2_buffer_index(): ");
00310   return (tx_last + (Sequence_number - input_buffer(tx_last)->seq_no + seq_no_max) % seq_no_max) % input_buffer_size;
00311 }
00312 
00313 int Selective_Repeat_ARQ_Sender::link_packets_buffered()
00314 {
00315   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::link_packets_buffered(): ");
00316   return input_buffer_size - input_free_space;
00317 }
00318 
00319 int Selective_Repeat_ARQ_Sender::nof_ready_link_packets()
00320 {
00321   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::nof_ready_link_packets(): ");
00322   return scheduled_total + feasable_blocks();
00323 }
00324 
00325 int Selective_Repeat_ARQ_Sender::link_packets_queued_waiting_for_transmission()
00326 {
00327   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::link_packets_queued_waiting_for_transmission(): ");
00328   div_t q = div(ip_pkt_queue.byte_size(), link_packet_size);
00329   int blocks_in_ip_queue = (q.rem) ? q.quot + 1 : q.quot;
00330   return buffered_non_outstanding() + scheduled_total + blocks_in_ip_queue;
00331 }
00332 
00333 // int Selective_Repeat_ARQ_Sender::time_stamp_HOL_packet(){
00334 //   assert(parameters_ok);
00335 //   return buffered_non_outstanding()+feasable_blocks();
00336 // }
00337 
00338 int Selective_Repeat_ARQ_Sender::buffer_size()
00339 {
00340   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::buffer_size(): ");
00341   return input_buffer_size;
00342 }
00343 
00344 Ttype Selective_Repeat_ARQ_Sender::link_packets_max_queuing_time()
00345 {
00346   it_assert(parameters_ok, "Selective_Repeat_ARQ_Sender::link_packets_max_queuing_time(): ");
00347   it_assert(input_buffer(tx_last), "Selective_Repeat_ARQ_Sender::link_packets_max_queuing_time(): ");
00348   return Event_Queue::now() - input_buffer(tx_last)->l3_pkt_info_p->timestamp;
00349 }
00350 
00352 Selective_Repeat_ARQ_Receiver::Selective_Repeat_ARQ_Receiver()
00353 {
00354   parameters_ok = false;
00355   packet_input.forward(this, &Selective_Repeat_ARQ_Receiver::handle_packet_input);
00356   packet_input.set_name("Selective_Repeat_ARQ_Receiver packet_input Slot");
00357 }
00358 
00359 Selective_Repeat_ARQ_Receiver::Selective_Repeat_ARQ_Receiver(const int Seq_no_size)
00360 {
00361   set_parameters(Seq_no_size);
00362   packet_input.forward(this, &Selective_Repeat_ARQ_Receiver::handle_packet_input);
00363   packet_input.set_name("Selective_Repeat_ARQ_Receiver packet_input Slot");
00364 }
00365 
00366 Selective_Repeat_ARQ_Receiver::~Selective_Repeat_ARQ_Receiver() {}
00367 
00368 void Selective_Repeat_ARQ_Receiver::set_parameters(const int Seq_no_size)
00369 {
00370   seq_no_size = Seq_no_size;
00371   seq_no_max = 1 << seq_no_size;
00372   rx_buffer.set_size(seq_no_max);
00373   for (int l = 0; l < seq_no_max; rx_buffer(l++) = NULL);
00374   Rnext = 0;
00375   id = 0;
00376   parameters_ok = true;
00377 }
00378 
00379 void Selective_Repeat_ARQ_Receiver::handle_packet_input(Array<Packet*> packet_array)
00380 {
00381   it_assert(parameters_ok, "Selective_Repeat_ARQ_Receiver::handle_packet_input(): ");
00382 
00383   int nbr_pkts = packet_array.length();
00384   Link_Packet *packet;
00385   for (int i = 0;i < nbr_pkts;i++) {
00386     packet = (Link_Packet *) packet_array(i);
00387     it_assert(packet, "Selective_Repeat_ARQ_Receiver::handle_packet_input(): ");
00388     it_assert(packet->seq_no >= 0 && packet->seq_no < seq_no_max, "Selective_Repeat_ARQ_Receiver::handle_packet_input(): ");
00389     Array<Packet*> ack_pkt;
00390     ack_pkt.set_size(1);
00391     ack_pkt(0) = (Packet *) new ACK(packet->seq_no, id++);
00392     ack_output(ack_pkt); // Acknowledge the receipt of this packet.
00393     if (in_sequence(Rnext, packet->seq_no, seq_no_max) && !rx_buffer(packet->seq_no)) // Is this a new packet in-sequence packet?
00394       rx_buffer(packet->seq_no) = packet; // This is a new in-sequence packet.
00395     else // This either is a duplicate packet or an out-of-sequence packet.
00396       delete packet;
00397     while (rx_buffer(Rnext)) { // Is there an unbroken sequence of packets that we can output?
00398 
00399       if (rx_buffer(Rnext)->link_packet_id == 0) {
00400         packet_output(rx_buffer(Rnext)->l3_pkt_info_p->pkt_pointer);
00401         delete rx_buffer(Rnext)->l3_pkt_info_p;
00402       }
00403       delete rx_buffer(Rnext);
00404       rx_buffer(Rnext) = NULL;
00405       Rnext = (Rnext + 1) % seq_no_max;
00406     }
00407   }
00408 }
00409 
00410 
00411 } //namespace itpp
00412 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
SourceForge Logo

Generated on Wed Jul 27 2011 16:27:05 for IT++ by Doxygen 1.7.4