IT++ Logo Newcom Logo

selective_repeat.cpp

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

Generated on Fri Jun 8 00:37:34 2007 for IT++ by Doxygen 1.5.2