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

Generated on Sun Dec 9 17:30:27 2007 for IT++ by Doxygen 1.5.4