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
Generated on Sat Aug 25 23:40:56 2007 for IT++ by Doxygen 1.5.2