1 /** \file mad_rlc.c \brief Receiver-driven layered congestion control<br>
2 * <br>Portions of code derived from MCL library by Vincent Roca et al.
3 * (http://www.inrialpes.fr/planete/people/roca/mcl/)<br><br>
4 * Copyright (c) 1999-2004 INRIA - Universite Paris 6 - All rights reserved<br>
5 * main authors: Julien Laboure - julien.laboure@inrialpes.fr and
6 * Vincent Roca - vincent.roca@inrialpes.fr
7 *
8 * $Author: peltotal $ $Date: 2007/02/28 08:58:00 $ $Revision: 1.24 $
9 *
10 * MAD-ALCLIB: Implementation of ALC/LCT protocols, Compact No-Code FEC,
11 * Simple XOR FEC, Reed-Solomon FEC, and RLC Congestion Control protocol.
12 * Copyright (c) 2003-2007 TUT - Tampere University of Technology
13 * main authors/contacts: jani.peltotalo@tut.fi and sami.peltotalo@tut.fi
14 *
15 * This program is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation; either version 2 of the License, or
18 * (at your option) any later version.
19 *
20 * This program is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
24 *
25 * You should have received a copy of the GNU General Public License
26 * along with this program; if not, write to the Free Software
27 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28 *
29 * In addition, as a special exception, TUT - Tampere University of Technology
30 * gives permission to link the code of this program with the OpenSSL library (or
31 * with modified versions of OpenSSL that use the same license as OpenSSL), and
32 * distribute linked combinations including the two. You must obey the GNU
33 * General Public License in all respects for all of the code used other than
34 * OpenSSL. If you modify this file, you may extend this exception to your version
35 * of the file, but you are not obligated to do so. If you do not wish to do so,
36 * delete this exception statement from your version.
37 */
38
39 #include <stdlib.h>
40 #include <stdio.h>
41 #include <string.h>
42
43 #ifdef _MSC_VER
44 #include <winsock2.h>
45 #include <ws2tcpip.h>
46 #else
47 #include <sys/socket.h>
48 #include <netinet/in.h>
49 #include <arpa/inet.h>
50 #endif
51
52 #include "mad_rlc.h"
53 #include "alc_channel.h"
54
55 /**
56 * This is a private function which process RLC SP.
57 *
58 * @param s pointer to the session
59 *
60 * @return 0 when no new layer is added, 1 when new layeris added, -1 otherwise
61 *
62 */
63
mad_rlc_process_rx_sp(alc_session_t * s)64 int mad_rlc_process_rx_sp(alc_session_t *s) {
65
66 static char addrs[MAX_CHANNELS_IN_SESSION][INET6_ADDRSTRLEN]; /* multicast addresses */
67 static char ports[MAX_CHANNELS_IN_SESSION][MAX_PORT_LENGTH]; /* local port numbers */
68
69 struct sockaddr_in ipv4;
70 struct sockaddr_in6 ipv6;
71
72 #ifdef _MSC_VER
73 int addr_size;
74 #endif
75
76 int retcode;
77
78 int retval = 0;
79
80 if(s->rlc->rx_nblost_since_sp <= s->rlc->loss_accepted
81 && s->rlc->rx_nblate_since_sp <= s->rlc->late_accepted) {
82
83 if(s->addr_family == PF_INET) {
84 if(s->addr_type == 1) {
85 ipv4.sin_addr.s_addr = htonl(ntohl(inet_addr(s->ch_list[s->nb_channel - 1]->addr)));
86 }
87 else {
88 ipv4.sin_addr.s_addr = htonl(ntohl(inet_addr(s->ch_list[s->nb_channel - 1]->addr)) + 1);
89 }
90
91 memset(addrs[s->nb_channel], 0, INET6_ADDRSTRLEN);
92 sprintf(addrs[s->nb_channel], "%s", inet_ntoa(ipv4.sin_addr));
93
94 memset(ports[s->nb_channel], 0, MAX_PORT_LENGTH);
95 sprintf(ports[s->nb_channel], "%i", (atoi(s->ch_list[s->nb_channel - 1]->port) + 1));
96 }
97 else if(s->addr_family == PF_INET6) {
98
99 #ifdef _MSC_VER
100 addr_size = sizeof(struct sockaddr_in6);
101 WSAStringToAddress((char*)s->ch_list[s->nb_channel - 1]->addr, AF_INET6, NULL, (struct sockaddr*)&ipv6, &addr_size);
102 #else
103 inet_pton(AF_INET6, s->ch_list[s->nb_channel - 1]->addr, &ipv6.sin6_addr);
104 #endif
105
106 if(s->addr_type == 0) {
107 if(increase_ipv6_address(&ipv6.sin6_addr) == -1) {
108 printf("Increasing IPv6 address %s is not possible\n", s->ch_list[s->nb_channel - 1]->addr);
109 return -1;
110 }
111 }
112
113 memset(addrs[s->nb_channel], 0, INET6_ADDRSTRLEN);
114
115 #ifdef _MSC_VER
116 addr_size = sizeof(addrs[s->nb_channel]);
117 WSAAddressToString((struct sockaddr*)&ipv6, sizeof(struct sockaddr_in6),
118 NULL, addrs[s->nb_channel], &addr_size);
119 #else
120 inet_ntop(AF_INET6, &ipv6.sin6_addr, addrs[s->nb_channel], sizeof(addrs[s->nb_channel]));
121 #endif
122
123 memset(ports[s->nb_channel], 0, MAX_PORT_LENGTH);
124 sprintf(ports[s->nb_channel], "%i", (atoi(s->ch_list[s->nb_channel - 1]->port) + 1));
125 }
126
127 retcode = add_alc_channel(s->s_id, ports[s->nb_channel], addrs[s->nb_channel],
128 s->ch_list[s->nb_channel - 1]->intface,
129 s->ch_list[s->nb_channel - 1]->intface_name);
130
131 if(!(retcode < 0)) {
132 s->rlc->rx_nblost_since_sp = 0;
133 s->rlc->rx_nblate_since_sp = 0;
134 retval = 1;
135 }
136 }
137
138 return retval;
139 }
140
141 /**
142 * This is a private function which free lists.
143 *
144 * @param s pointer to the session
145 *
146 */
147
mad_rlc_free_lists(alc_session_t * s)148 void mad_rlc_free_lists(alc_session_t *s) {
149 int i;
150 late_list_t *current_late;
151 lost_list_t *current_lost;
152
153 for(i = 0; i < MAX_CHANNELS_IN_SESSION; i++) {
154 current_late = s->rlc->rx_missing[i].next;
155 while(current_late != NULL) {
156 s->rlc->rx_missing[i].next = current_late->next;
157 free(current_late);
158 current_late = s->rlc->rx_missing[i].next;
159 }
160 s->rlc->rx_missing[i].next = NULL; /* redundant, isn't it? */
161 }
162
163 current_lost = s->rlc->rx_lost.next;
164 while(current_lost != NULL) {
165 s->rlc->rx_lost.next = current_lost->next;
166 free(current_lost);
167 current_lost = s->rlc->rx_lost.next;
168 }
169 s->rlc->rx_lost.next = NULL; /* redundant, isn't it? */
170 s->rlc->rx_nblost = 0;
171 s->rlc->rx_nblate = 0;
172 s->rlc->rx_nblost_since_sp = 0;
173 s->rlc->rx_nblate_since_sp = 0;
174 }
175
176 /**
177 * This is a private function which adds late packet to the session's late list.
178 *
179 * @param s pointer to the session,
180 * @param layer layer number
181 * @param nseq packet's sequence number
182 *
183 * @return 0 in success, -1 otherwise
184 *
185 */
186
mad_rlc_add_late(alc_session_t * s,int layer,int nseq)187 int mad_rlc_add_late(alc_session_t *s, int layer, int nseq) {
188 late_list_t *new_missing;
189 double currenttime;
190
191 if(layer > s->nb_channel) {
192 return -1;
193 }
194
195 if(!( new_missing = (late_list_t *)malloc(sizeof(late_list_t))) ) {
196 printf("Could not alloc memory for late_list_t structure!\n");
197 return -1;
198 }
199
200 currenttime = sec();
201
202 new_missing->seq_num = nseq;
203 new_missing->losttime = currenttime + (double)((double)s->rlc->pkt_timeout / (double)1000);
204 new_missing->next = s->rlc->rx_missing[layer].next;
205
206 s->rlc->rx_missing[layer].next = new_missing;
207 s->rlc->rx_nblate++;
208 s->rlc->rx_nblate_since_sp++;
209
210 /* update stats: assume a late pkt is lost (corrected later if req.) */
211 s->lost_packets++;
212
213 return 0;
214 }
215
216 /**
217 * This is a private function which removes late packet from session's late list.
218 *
219 * @param s pointer to the session
220 * @param layer layer number
221 * @param nseq packet's sequence number
222 *
223 * @return 0 in success, -1 otherwise
224 *
225 */
226
mad_rlc_remove_late(alc_session_t * s,int layer,int nseq)227 int mad_rlc_remove_late(alc_session_t *s, int layer, int nseq) {
228 late_list_t *prev;
229 late_list_t *current;
230
231 if(layer > s->nb_channel) {
232 return -1;
233 }
234
235 prev = &(s->rlc->rx_missing[layer]);
236 current = prev->next;
237
238 while(current != NULL && current->seq_num != nseq ) {
239 prev = current;
240 current = current->next;
241 }
242
243 if(current == NULL) {
244 return -1;
245 }
246 else {
247 prev->next = current->next;
248 free(current);
249 s->rlc->rx_nblate--;
250 s->rlc->rx_nblate_since_sp--;
251 }
252
253 /* correct stats... */
254 s->lost_packets++;
255
256 return 0;
257 }
258
259
260 /**
261 * This is a private function which adds lost packet to session's lost list.
262 *
263 * @param s pointer to the session
264 *
265 * @return -1000 when layer should be dropped, 0 when layer should not be dropped, -1 otherwise
266 *
267 */
268
mad_rlc_add_lost(alc_session_t * s)269 int mad_rlc_add_lost(alc_session_t *s) {
270
271 lost_list_t *new_lost;
272 double currenttime;
273
274 currenttime = sec();
275
276 s->rlc->rx_nblost++;
277 s->rlc->rx_nblost_since_sp++;
278
279 if(s->rlc->rx_nblost >= s->rlc->loss_limit) {
280 /* too many losses... drop a layer! */
281
282 s->rlc->drop_highest_layer = TRUE;
283
284 /* initial state for future potential use of this layer*/
285 s->rlc->rx_first_pkt[s->ch_list[s->nb_channel - 1]->ch_id] = 1;
286
287 /* Clean up late and lost lists... */
288 mad_rlc_free_lists(s);
289
290 /* entering the deaf period... */
291 s->rlc->rx_deaf_wait = currenttime + (double)s->rlc->deaf_period / (double)1000;
292
293 return -1000;
294 }
295
296 if(!(new_lost = (lost_list_t *)malloc(sizeof(lost_list_t)))) {
297 printf("Could not alloc memory for lost_list_t structure!\n");
298 return -1;
299 }
300
301 new_lost->pkt_remaining = s->rlc->loss_timeout;
302 new_lost->next = s->rlc->rx_lost.next;
303 s->rlc->rx_lost.next = new_lost;
304
305 return 0;
306 }
307
308 /**
309 * This is a private function which updates session's late list.
310 *
311 * @param s pointer to the session
312 *
313 * @return 0 in success, -1 otherwise
314 *
315 */
316
mad_rlc_update_late_list(alc_session_t * s)317 int mad_rlc_update_late_list(alc_session_t *s) {
318 int layer;
319 late_list_t *prev;
320 late_list_t *current;
321 double currenttime;
322
323 for(layer = 0; layer < s->nb_channel; layer++) {
324 currenttime = sec();
325
326 prev = &(s->rlc->rx_missing[layer]);
327 current = prev->next;
328
329 while(current != NULL) {
330 if(current->losttime <= currenttime) {
331 /* this one is lost! */
332 prev->next = current->next;
333 free(current);
334 s->rlc->rx_nblate--;
335 s->rlc->rx_nblate_since_sp--;
336
337 if(mad_rlc_add_lost(s) == -1000) {
338 return -1; /* roca 0 */
339 }
340 }
341 else {
342 prev = current;
343 current = prev->next;
344 }
345 }
346 }
347
348 return 0;
349 }
350
351 /**
352 * This is a private function which updates session's lost list.
353 *
354 * @param s pointer to the session
355 *
356 * @return 0
357 *
358 */
359
mad_rlc_update_loss_list(alc_session_t * s)360 int mad_rlc_update_loss_list(alc_session_t *s) {
361 lost_list_t *prev;
362 lost_list_t *current;
363
364 prev = &(s->rlc->rx_lost);
365 current = prev->next;
366
367 while(current != NULL) {
368 if(--(current->pkt_remaining) == 0) { /* this loss is too old : removing */
369 prev->next = current->next;
370 free(current);
371 s->rlc->rx_nblost--;
372 }
373 else {
374 prev = current;
375 }
376
377 current = prev->next;
378 }
379
380 return 0;
381 }
382
383 /**
384 * This is a private function which checks packet's RLC sequence number.
385 *
386 * @param s pointer to the session
387 * @param layer layer number
388 * @param seqid packet's sequence number
389 *
390 * @return 0
391 *
392 */
393
mad_rlc_check_sequence(alc_session_t * s,int layer,int seqid)394 int mad_rlc_check_sequence(alc_session_t *s, int layer, int seqid) {
395 unsigned short Delta1;
396 unsigned short Delta2;
397
398 int i;
399 int late_limit;
400
401 if(s->rlc->rx_wait_for[layer] == seqid) {
402 /* This is the packet we're waiting for, let's go on! */
403 s->rlc->rx_wait_for[layer]++;
404 return 0;
405 }
406
407 /* This is not the one we're waiting for... */
408 if(s->rlc->rx_wait_for[layer] < seqid) {
409
410 Delta1 = seqid - s->rlc->rx_wait_for[layer];
411 Delta2 = 65535 - Delta1;
412
413 if(Delta1 < Delta2) {
414
415 late_limit = RLC_MAX_LATES;
416
417 for(i = s->rlc->rx_wait_for[layer]; i < seqid; i++) {
418 mad_rlc_add_late(s, layer, i);
419 late_limit--;
420 if(late_limit <= 0 ) {
421 printf("RLC Warning*** Max number of LATE packets reached\n");
422 fflush(stdout);
423 break;
424 }
425 }
426 /* EOFIX */
427 s->rlc->rx_wait_for[layer] = seqid + 1;
428 }
429 else {
430 /* Late arrival packet (uint16 overflow) */
431 /* eg. we're waiting seq 4 and we get seq 65532 */
432 mad_rlc_remove_late(s, layer, seqid);
433 }
434 }
435 else { /* rx_wait_for > rlc_seqid */
436
437 Delta1 = s->rlc->rx_wait_for[layer] - seqid;
438 Delta2 = 65535 - Delta1;
439 if (Delta1 < Delta2) { /* Late arrival packet */
440 /* ie: we're waiting seq 501 and we get seq 498 */
441 mad_rlc_remove_late(s, layer, seqid);
442 }
443 else {
444 /* Some packet(s) are missing (uint16 overflow) */
445 /* ie: waiting seq 65531 and get seq 3 */
446 /* FIX 14/12/01 */
447 late_limit = RLC_MAX_LATES;
448 for(i = s->rlc->rx_wait_for[layer]; i != (seqid-1); i++) {
449 mad_rlc_add_late(s, layer, i);
450 late_limit--;
451 if(late_limit <= 0 ) {
452 printf("RLC Warning*** Max number of LATE packets reached\n");
453 fflush(stdout);
454 break;
455 }
456 }
457 /* EOFIX */
458 s->rlc->rx_wait_for[layer] = seqid + 1;
459 }
460 }
461
462 return 0;
463 }
464
init_mad_rlc(alc_session_t * s)465 int init_mad_rlc(alc_session_t *s) {
466 int i;
467
468 if(!(s->rlc = (mad_rlc_t*)calloc(1, sizeof(mad_rlc_t)))) {
469 printf("Could not alloc memory for mad rlc congestion control!\n");
470 return -1;
471 }
472
473 if(s->mode == SENDER) {
474 s->rlc->sp_cycle = RLC_SP_CYCLE;
475 }
476 else if(s->mode == RECEIVER) {
477 s->rlc->drop_highest_layer = FALSE;
478 s->rlc->pkt_timeout = RLC_PKT_TIMEOUT;
479 s->rlc->deaf_period = RLC_DEAF_PERIOD;
480 s->rlc->loss_accepted = RLC_LOSS_ACCEPTED;
481 s->rlc->late_accepted = RLC_LATE_ACCEPTED;
482 s->rlc->loss_limit = RLC_LOSS_LIMIT;
483 s->rlc->loss_timeout = RLC_LOSS_TIMEOUT;
484 s->rlc->rx_deaf_wait = 0;
485
486 for(i = 0 ; i < MAX_CHANNELS_IN_SESSION; i++) {
487 s->rlc->rx_first_pkt[i] = 1;
488 s->rlc->rx_first_sp[i] = 0;
489 }
490 }
491
492 return 0;
493 }
494
close_mad_rlc(alc_session_t * s)495 void close_mad_rlc(alc_session_t *s) {
496 if(s->mode == RECEIVER) {
497 mad_rlc_free_lists(s);
498 }
499
500 free(s->rlc);
501 }
502
mad_rlc_next_sp(alc_session_t * s,int layer)503 double mad_rlc_next_sp(alc_session_t *s, int layer) {
504
505 double spacing;
506 double currenttime;
507
508 currenttime = sec();
509
510 spacing = (double)((double)s->rlc->sp_cycle / (double)1000) * (double)(min((1 << layer), 128 + layer));
511
512 return (currenttime + (double)spacing);
513 }
514
mad_rlc_reset_tx_sp(alc_session_t * s)515 void mad_rlc_reset_tx_sp(alc_session_t *s) {
516
517 int i;
518
519 for(i = 0 ; i < MAX_CHANNELS_IN_SESSION; i++) {
520 s->rlc->tx_next_sp[i] = mad_rlc_next_sp(s, i);
521 }
522 }
523
mad_rlc_fill_header(alc_session_t * s,rlc_hdr_t * rlc_hdr,int layer)524 int mad_rlc_fill_header(alc_session_t *s, rlc_hdr_t *rlc_hdr, int layer) {
525
526 unsigned short hdr_seqid;
527 double currenttime;
528
529 currenttime = sec();
530
531 if(layer > MAX_CHANNELS_IN_SESSION || layer > s->nb_channel) {
532 printf("BAD layer!\n");
533 fflush(stdout);
534 return -1;
535 }
536
537 hdr_seqid = s->rlc->tx_layers_seq[layer];
538 s->rlc->tx_layers_seq[layer]++;
539
540 rlc_hdr->reserved = 0x55; /* unused: rlc_reserved = 1010101 */
541 rlc_hdr->layer = layer;
542 rlc_hdr->seqid = htons(hdr_seqid);
543
544 if(s->rlc->tx_next_sp[layer] <= currenttime) {
545
546 if((layer + 1) == s->nb_channel) {
547 rlc_hdr->sp = 0;
548 }
549 else {
550 /* OK this is a new SP for this layer */
551 rlc_hdr->sp = 1;
552
553 /* calculate when next SP will occur */
554 s->rlc->tx_next_sp[layer] = mad_rlc_next_sp(s, layer);
555
556 if(layer + 1 < MAX_CHANNELS_IN_SESSION &&
557 s->ch_list[layer + 1]->start_sending == FALSE) {
558
559 s->ch_list[layer + 1]->start_sending = TRUE;
560 s->nb_sending_channel++;
561 }
562 }
563 }
564 else { /* not a SP... */
565 rlc_hdr->sp = 0;
566 }
567
568 return 0;
569 }
570
mad_rlc_analyze_cci(alc_session_t * s,rlc_hdr_t * rlc_hdr)571 int mad_rlc_analyze_cci(alc_session_t *s, rlc_hdr_t *rlc_hdr) {
572
573 unsigned char hdr_layer;
574 unsigned short hdr_seqid;
575 unsigned char hdr_sp;
576 double currenttime;
577
578 hdr_seqid = ntohs(rlc_hdr->seqid);
579 hdr_layer = rlc_hdr->layer;
580 hdr_sp = rlc_hdr->sp;
581
582 if(rlc_hdr->reserved != 0x55) {
583 return -1;
584 }
585 if(rlc_hdr->layer >= s->nb_channel) {
586 return -1;
587 }
588
589 mad_rlc_update_loss_list(s);
590 mad_rlc_update_late_list(s);
591
592 currenttime = sec();
593
594 if(s->rlc->rx_deaf_wait != 0) {
595
596 if(s->rlc->rx_deaf_wait > currenttime) {
597
598 s->rlc->rx_wait_for[rlc_hdr->layer] = hdr_seqid + 1;
599 return 0;
600 }
601 }
602
603 if(s->rlc->rx_first_pkt[hdr_layer]) {
604 /* First packet on this layer... */
605 s->rlc->rx_wait_for[hdr_layer] = hdr_seqid + 1;
606 s->rlc->rx_first_pkt[hdr_layer] = 0;
607 /* continue as this pkt may contain an SP */
608 } else {
609 /* check if some pkts have been lost or not */
610 mad_rlc_check_sequence(s, hdr_layer, hdr_seqid);
611 }
612
613 if(hdr_sp) {
614 if(hdr_layer == s->nb_channel - 1) {
615 /* This is a Synchronisation Point */
616 if(s->rlc->rx_first_sp[hdr_layer] == 1) {
617 /* skip 1st SP, especially after deaf-period */
618 s->rlc->rx_first_sp[hdr_layer] = 0;
619 } else {
620 mad_rlc_process_rx_sp(s);
621 }
622 }
623 }
624
625 return 0;
626 }
627