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
Generated on Sat May 3 16:10:43 2008 for IT++ by Doxygen 1.5.5