IT++ Logo

selective_repeat.cpp

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

Generated on Wed Jan 20 23:03:06 2010 for IT++ by Doxygen 1.6.2