From 9247a4c0998de14ef5993822cac75b4a6327ee1e Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Mon, 19 Apr 2021 18:05:41 +0200 Subject: Router working finally --- Semestr 4/sieci/pracownia2/router/config.h | 6 ++ Semestr 4/sieci/pracownia2/router/dist_vector.c | 99 ++++++++++++++++- Semestr 4/sieci/pracownia2/router/dist_vector.h | 18 +++- Semestr 4/sieci/pracownia2/router/linked_list.c | 5 +- Semestr 4/sieci/pracownia2/router/linked_list.h | 2 +- Semestr 4/sieci/pracownia2/router/network_addr.c | 22 ++-- Semestr 4/sieci/pracownia2/router/network_addr.h | 10 +- Semestr 4/sieci/pracownia2/router/router.c | 74 +++++++------ Semestr 4/sieci/pracownia2/router/utils.c | 132 ++++++++++++++++++----- Semestr 4/sieci/pracownia2/router/utils.h | 13 +++ 10 files changed, 295 insertions(+), 86 deletions(-) (limited to 'Semestr 4/sieci/pracownia2/router') diff --git a/Semestr 4/sieci/pracownia2/router/config.h b/Semestr 4/sieci/pracownia2/router/config.h index 3537c03..ef8bf47 100644 --- a/Semestr 4/sieci/pracownia2/router/config.h +++ b/Semestr 4/sieci/pracownia2/router/config.h @@ -3,6 +3,12 @@ #define SERVER_PORT 54321 #define TURN_LEN_S 5 + +#define INFINITY_DIST 16 +#define REACHABILITY_WAIT_TIME 5 + +#define DV_DATAGRAM_LEN 9 + #define TURN_LEN_MS (1000 * TURN_LEN_S) #define TURN_LEN_US (1000000 * TURN_LEN_S) diff --git a/Semestr 4/sieci/pracownia2/router/dist_vector.c b/Semestr 4/sieci/pracownia2/router/dist_vector.c index 1e09bff..f1c8c67 100644 --- a/Semestr 4/sieci/pracownia2/router/dist_vector.c +++ b/Semestr 4/sieci/pracownia2/router/dist_vector.c @@ -1,8 +1,101 @@ #include "dist_vector.h" +#include bool is_connected_directly(struct vector_item item) { - return (get_network_address(item.network).s_addr == - get_network_address(item.via_ip).s_addr); + return item.is_connected_directly; } -void update_distance_vector(list_t *distance_vector, struct vector_item new_item) {} \ No newline at end of file +bool is_reachable(struct vector_item item) { + return (item.distance < INFINITY_DIST); +} + +void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours) { + for (int i = 0; i < n_cnt; i++) { + struct vector_item new_item; + new_item.network = neighbours[i]; + new_item.distance = INFINITY_DIST; + new_item.is_connected_directly = true; + insert(dv, &new_item, sizeof(new_item)); + } +} + +void update_dv_reachability(list_t *distance_vector) { + reset(distance_vector); + while (distance_vector->it != NULL) { + struct vector_item *current = (struct vector_item *)distance_vector->it->data; + if(++current->reachable > REACHABILITY_WAIT_TIME) { + if (current->distance >= INFINITY_DIST) { + if (!is_connected_directly(*current)) { + erase_it(distance_vector); + } + } else { + current->distance = INFINITY_DIST; + current->reachable = 0; + } + } + iterate(distance_vector); + } +} + +void update_dv_new_item(list_t *distance_vector, struct vector_item new_item) { + bool new_entry = true; + reset(distance_vector); + while (distance_vector->it != NULL) { + struct vector_item *current = (struct vector_item *)distance_vector->it->data; + + /* If the network is already in the distance vector, then we possibly want to change it: + * - if the new item has better distance than the previous one, then we just want to change it no matter what, + * - if the new item has the same via ip, then we want to check two things: + * - if new item has infinity dist, then we want to set infinity (if it wasn't set, then we want to change reachable to 0) + * - if new item has < inf dist, then we want to change reachable to 0 and set our dist accordingly. + * - else we ignore the entry. + */ + if (get_network_address(current->network).s_addr == get_network_address(new_item.network).s_addr) { + if (current->distance > new_item.distance) { + *current = new_item; + current->reachable = 0; + } else if(current->via_ip.s_addr == new_item.via_ip.s_addr) { + if (new_item.distance >= INFINITY_DIST) { + if (current->distance < INFINITY_DIST) { + current->distance = INFINITY_DIST; + current->reachable = 0; + } + } else if (new_item.distance < INFINITY_DIST) { + if (current->distance >= INFINITY_DIST) { + current->distance = new_item.distance; + } + current->reachable = 0; + } + } + new_entry = false; + } + + iterate(distance_vector); + } + + if (new_entry) { + insert(distance_vector, &new_item, sizeof(new_item)); + } +} + +void print_dv(list_t *distance_vector) { + printf("Distance vector:\n"); + reset(distance_vector); + while (distance_vector->it != NULL) { + char addr[20], via_addr[20]; + struct vector_item current = *(struct vector_item *)distance_vector->it->data; + struct in_addr net_addr = get_network_address(current.network); + inet_ntop(AF_INET, &net_addr, addr, sizeof(addr)); + printf("%s/%d ", addr, current.network.netmask); + + if (is_reachable(current)) printf("distance %d ", current.distance); + else printf("unreachable "); + + inet_ntop(AF_INET, ¤t.via_ip, via_addr, sizeof(via_addr)); + if (is_connected_directly(current)) printf("connected directly\n"); + else printf("via %s\n", via_addr); + + iterate(distance_vector); + } + printf("\n"); +} \ No newline at end of file diff --git a/Semestr 4/sieci/pracownia2/router/dist_vector.h b/Semestr 4/sieci/pracownia2/router/dist_vector.h index cd1a995..14159b4 100644 --- a/Semestr 4/sieci/pracownia2/router/dist_vector.h +++ b/Semestr 4/sieci/pracownia2/router/dist_vector.h @@ -3,6 +3,7 @@ #include "linked_list.h" #include "network_addr.h" +#include "config.h" /* Item of the distance vector. * If <> is set to 0, then it means that the network is reachable. @@ -11,14 +12,25 @@ */ struct vector_item { struct network_addr network; - router_addr via_ip; + struct in_addr via_ip; + uint16_t distance; uint8_t reachable; + bool is_connected_directly; }; -/* Returns true if given distance vector item is connected directly, false otherwise */ +/* Initis distance vector with given neighbours array. */ +void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours); + +/* Returns true if given distance vector item is connected directly, false otherwise. */ bool is_connected_directly(struct vector_item item); /* Updates the distance vector. */ -void update_distance_vector(list_t *distance_vector, struct vector_item new_item); +void update_dv_new_item(list_t *distance_vector, struct vector_item new_item); + +/* Updates reachabilities. */ +void update_dv_reachability(list_t *distance_vector); + +/* Print distance vector. */ +void print_dv(list_t *distance_vector); #endif \ No newline at end of file diff --git a/Semestr 4/sieci/pracownia2/router/linked_list.c b/Semestr 4/sieci/pracownia2/router/linked_list.c index f3bccc9..09f6025 100644 --- a/Semestr 4/sieci/pracownia2/router/linked_list.c +++ b/Semestr 4/sieci/pracownia2/router/linked_list.c @@ -8,10 +8,7 @@ node_t *_next(node_t *node) { void _insert(node_t **head, void *data, size_t data_size) { node_t *new_node = (node_t *)malloc(sizeof(node_t)); - new_node->data = malloc(data_size); - for (int i = 0; i < data_size; i++) - *(uint8_t *)(new_node->data + i) = *(uint8_t *)(data + i); - + new_node->data = malloc(data_size); new_node->next = *head; *head = new_node; } diff --git a/Semestr 4/sieci/pracownia2/router/linked_list.h b/Semestr 4/sieci/pracownia2/router/linked_list.h index 28e8ef7..1574b2f 100644 --- a/Semestr 4/sieci/pracownia2/router/linked_list.h +++ b/Semestr 4/sieci/pracownia2/router/linked_list.h @@ -15,7 +15,7 @@ typedef struct list_t { node_t *prev_it; } list_t; -/* Creates an empty list */ +/* Creates an empty list. */ list_t create_list(); /* Insert a new node in the begining of a list. */ diff --git a/Semestr 4/sieci/pracownia2/router/network_addr.c b/Semestr 4/sieci/pracownia2/router/network_addr.c index a65f48c..d1982c2 100644 --- a/Semestr 4/sieci/pracownia2/router/network_addr.c +++ b/Semestr 4/sieci/pracownia2/router/network_addr.c @@ -5,21 +5,31 @@ struct in_addr _get_broadcast_address(struct in_addr addr, uint16_t netmask) { struct in_addr result = addr; + result.s_addr = ntohl(result.s_addr); /* bitshift by more than 31 is UB */ - if (netmask < 32) { - result.s_addr |= ~((1< #include -#define INFINITY_DIST 128 - -/* Network address and sitance */ +/* Network address with netmask. */ struct network_addr { struct in_addr addr; - uint16_t distance; uint8_t netmask; }; @@ -23,10 +20,9 @@ struct in_addr get_broadcast_address(struct network_addr na); struct in_addr get_network_address(struct network_addr na); /* Prints network_addr via stdio. */ -void pretty_print(struct network_addr na); +void pretty_print_network(struct network_addr na); /* Converts string of ip in CIDR notation with a netmask to network_addr. */ -struct network_addr stora(char *str); - +struct network_addr stona(char *str); #endif \ No newline at end of file diff --git a/Semestr 4/sieci/pracownia2/router/router.c b/Semestr 4/sieci/pracownia2/router/router.c index 031ead8..7262ee6 100644 --- a/Semestr 4/sieci/pracownia2/router/router.c +++ b/Semestr 4/sieci/pracownia2/router/router.c @@ -7,74 +7,78 @@ #include #include #include +#include #include "network_addr.h" #include "utils.h" +#include "dist_vector.h" -uint16_t read_configuration(struct network_addr** networks) { +uint16_t read_configuration(struct network_addr** networks, uint16_t **dists) { uint16_t n; scanf("%hd", &n); *networks = malloc(n * sizeof(struct network_addr)); + *dists = malloc(n * sizeof(uint16_t)); for (int i = 0; i < n; i++) { char addr[20]; char _dist[10]; uint16_t dist; scanf(" %s %s %hd", addr, _dist, &dist); - (*networks)[i] = stora(addr); - (*networks)[i].distance = dist; + (*networks)[i] = stona(addr); + (*dists)[i] = dist; } return n; } -void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *netowrks) { - printf("Listening for %dms.\n", timeout); +void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) { + // printf("Listening for %dms.\n", timeout); + char buffer[IP_MAXPACKET + 1]; + struct sockaddr_in sender; + while (poll_socket_modify_timeout(sockfd, &timeout)) { - printf("Poll returned, remaining timeout: %dms.\n", timeout); - recv_and_print(sockfd, networks_number, netowrks); - } - printf("Finished listening\n\n"); -} + size_t buf_len = recv_message(sockfd, buffer, &sender); + struct vector_item new_item = parse_message(buffer, &sender); + // char addr[20]; + // inet_ntop(AF_INET, &sender.sin_addr, addr, sizeof(addr)); + // printf("Via ip: %s\n", addr); -int send_distance_vector(int sockfd, struct in_addr network) { - char* message = "Hello server! My name is S1\n"; - ssize_t message_len = strlen(message); - int result; + if (!is_from_network(sender.sin_addr, new_item.network)) { + for (int i = 0; i < networks_number; i++) { + if (is_from_network(sender.sin_addr, networks[i])) { + new_item.distance += dists[i]; + break; + } + } + new_item.is_connected_directly = false; + } - char addr[20]; - inet_ntop(AF_INET, &network, addr, sizeof(addr)); - printf("Sending datagram to %s\n", addr); - if ((result = send_message(sockfd, message, message_len, network)) != message_len) { - fprintf(stderr, "sendto error: %s\n", strerror(errno)); + update_dv_new_item(dv, new_item); } + update_dv_reachability(dv); + // printf("Finished listening\n\n"); } -void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks) { - printf("Propagating distance vector\n"); - for (int i = 0; i < networks_number; i++) { - struct in_addr broadcast_address = get_broadcast_address(networks[i]); - send_distance_vector(sockfd, broadcast_address); - } - printf("Distance vector propagated.\n\n"); -} +void router_loop(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists) { + list_t dv = create_list(); + init_dv(&dv, networks_number, networks); -void router_loop(int sockfd, int networks_number, struct network_addr *networks) { printf("Starting the router loop...\n"); for (;;) { - listen_for_routers(sockfd, TURN_LEN_MS, networks_number, networks); - propagate_distance_vector(sockfd, networks_number, networks); + print_dv(&dv); + propagate_distance_vector(sockfd, networks_number, networks, dists, &dv); + listen_for_routers(sockfd, TURN_LEN_MS, networks_number, networks, dists, &dv); } } int main() { struct network_addr* networks; - int n = read_configuration(&networks); - for (int i = 0; i < n; i++) { - pretty_print(networks[i]); - } + uint16_t *dists; + int n = read_configuration(&networks, &dists); int sockfd = get_socket(); bind_to_port(sockfd, SERVER_PORT); - router_loop(sockfd, n, networks); + + router_loop(sockfd, n, networks, dists); close(sockfd); free(networks); + free(dists); } \ No newline at end of file diff --git a/Semestr 4/sieci/pracownia2/router/utils.c b/Semestr 4/sieci/pracownia2/router/utils.c index 2872a35..3f9078e 100644 --- a/Semestr 4/sieci/pracownia2/router/utils.c +++ b/Semestr 4/sieci/pracownia2/router/utils.c @@ -5,6 +5,7 @@ #include #include #include +#include int get_socket() { int sockfd = socket(AF_INET, SOCK_DGRAM, 0); @@ -37,7 +38,7 @@ long get_time_interval(struct timespec start, struct timespec finish) { int poll_socket_modify_timeout(int sockfd, int *timeout) { if (*timeout < 0) { - fprintf(stderr, "poll_modify_timeout: timeout is negative.\n"); + fprintf(stderr, "poll_socket_modify_timeout: timeout is negative.\n"); exit(EXIT_FAILURE); } @@ -62,35 +63,9 @@ int poll_socket_modify_timeout(int sockfd, int *timeout) { clock_gettime(CLOCK_REALTIME, &finish); *timeout -= get_time_interval(start, finish); - printf("Timeout: %dms, time waiting: %ldms.\n", *timeout, get_time_interval(start, finish)); return result; } -void recv_and_print(int sockfd, int networks_number, struct network_addr *networks) { - struct sockaddr_in sender; - socklen_t sender_len = sizeof(sender); - uint8_t buffer[IP_MAXPACKET + 1]; - ssize_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, - (struct sockaddr*)&sender, &sender_len); - if (datagram_len < 0) { - fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); - exit(EXIT_FAILURE); - } - for (int i = 0; i < networks_number; i++) { - if (networks[i].addr.s_addr == sender.sin_addr.s_addr) { - return; - } - } - - char sender_ip_str[20]; - inet_ntop(AF_INET, &(sender.sin_addr), sender_ip_str, sizeof(sender_ip_str)); - printf("Received UDP packet from IP address: %s, port %d\n", - sender_ip_str, ntohs(sender.sin_port)); - - buffer[datagram_len] = 0; - printf("%ld-byte message: +%s+\n", datagram_len, buffer); -} - size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr network) { struct sockaddr_in network_address; bzero (&network_address, sizeof(network_address)); @@ -100,3 +75,106 @@ size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr net return sendto(sockfd, buffer, buffer_len, 0, (struct sockaddr*) &network_address, sizeof(network_address)); } + +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender) { + socklen_t sender_len = sizeof(*sender); + for (int i = 0; i < DV_DATAGRAM_LEN; i++) buffer[i] = 0; + size_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0, + (struct sockaddr*)sender, &sender_len); + if (datagram_len < 0) { + fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); + exit(EXIT_FAILURE); + } + // printf("Received a message: "); + // for (int i = 0 ; i < 9; i++) { + // printf("%u ", (uint8_t)buffer[i]); + // } + // printf("\n"); + return datagram_len; +} + +struct vector_item parse_message(char *buffer, struct sockaddr_in *sender) { + // printf("Parsing a message: "); + // for (int i = 0 ; i < 9; i++) { + // printf("%u ", (uint8_t)buffer[i]); + // } + // printf("\n"); + struct vector_item res; + uint32_t ip_addr = *(uint32_t *)buffer; + // ip_addr = ip_addr; + uint32_t dist = *(uint32_t *)(buffer + 5); + dist = ntohl(dist); + + res.network.addr.s_addr = ip_addr; + res.network.netmask = buffer[4]; + res.is_connected_directly = true; + res.via_ip = sender->sin_addr; + res.distance = (dist < INFINITY_DIST ? dist : INFINITY_DIST); + res.reachable = 0; + + char addr[20]; + inet_ntop(AF_INET, &res.network.addr, addr, sizeof(addr)); + char via[20]; + inet_ntop(AF_INET, &sender->sin_addr, via, sizeof(via)); + + // printf("Po ludzku: %s/%d, distance %d, via %s\n", addr, res.network.netmask, res.distance, via); + + return res; +} + +void _get_message(struct vector_item item, char *message) { + *(uint32_t *)message = item.network.addr.s_addr; + message[4] = item.network.netmask; + uint32_t distance = htonl(item.distance >= INFINITY_DIST ? INT_MAX : item.distance); + for (int i = 0; i < 4; i++) { + *(message + 5 + i) = *((char *)(&distance) + i); + } +} + +int _send_item(int sockfd, struct network_addr network, struct vector_item item) { + char message[DV_DATAGRAM_LEN + 1]; + _get_message(item, message); + message[DV_DATAGRAM_LEN] = 0; + ssize_t message_len = DV_DATAGRAM_LEN; + + struct in_addr na = get_broadcast_address(network); + + char addr[20]; + inet_ntop(AF_INET, &na, addr, sizeof(addr)); + // printf("Sending datagram to %s: ", addr); + // for (int i = 0 ; i < DV_DATAGRAM_LEN; i++) { + // printf("%u ", (uint8_t)message[i]); + // } + // printf("\nmessage_len: %ld\n", message_len); + int result; + if ((result = send_message(sockfd, message, message_len, na)) != message_len) { + // fprintf(stderr, "sendto error: %s\n", strerror(errno)); + } + return result; +} + +void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) { + for (int i = 0; i < networks_number; i++) { + reset(dv); + while (dv->it != NULL) { + struct vector_item data = *(struct vector_item *)dv->it->data; + if (!(get_network_address(data.network).s_addr == get_network_address(networks[i]).s_addr)) { + _send_item(sockfd, networks[i], data); + } + iterate(dv); + } + + struct vector_item self_item; + self_item.distance = dists[i]; + self_item.network = networks[i]; + // printf("Sending self message: %d\n", dists[i]); + _send_item(sockfd, networks[i], self_item); + } +} + +bool is_from_network(struct in_addr ip_addr, struct network_addr network) { + struct network_addr temp; + temp.addr= ip_addr; + temp.netmask = network.netmask; + return (get_network_address(temp).s_addr == get_network_address(network).s_addr); +} \ No newline at end of file diff --git a/Semestr 4/sieci/pracownia2/router/utils.h b/Semestr 4/sieci/pracownia2/router/utils.h index 63ad6fb..3642779 100644 --- a/Semestr 4/sieci/pracownia2/router/utils.h +++ b/Semestr 4/sieci/pracownia2/router/utils.h @@ -7,6 +7,7 @@ #include #include #include "network_addr.h" +#include "dist_vector.h" #define NS_TO_MS(X) ((long)(X) / (long)1000000) #define S_TO_MS(X) ((long)(X) * (long)1000) @@ -32,5 +33,17 @@ void recv_and_print(int sockfd, int networks_number, struct network_addr *networ */ size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr addr); +/* Receive message and write it to buffer. */ +size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender); + +/* Parse datagram into a vector item. */ +struct vector_item parse_message(char *buffer, struct sockaddr_in *sender); + +/* Propagates dv to all connected networks. */ +void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv); + +/* Checks if given address is in network range. */ +bool is_from_network(struct in_addr ip_addr, struct network_addr network); + #endif \ No newline at end of file -- cgit v1.2.3