IT++ Logo Newcom Logo

selective_repeat.cpp

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

Generated on Thu Apr 19 14:43:45 2007 for IT++ by Doxygen 1.5.1