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
Generated on Thu Apr 19 14:14:59 2007 for IT++ by Doxygen 1.5.1