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