Last active
August 5, 2016 15:57
-
-
Save asutoshpalai/a0c16d0636ada394f25e4eabeaeb0d4e to your computer and use it in GitHub Desktop.
Sliding window protocol
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdlib.h> | |
#include <stdint.h> | |
#include <unistd.h> | |
#include <signal.h> | |
#include <time.h> | |
#include <fcntl.h> | |
#include <string.h> | |
#include <stdio.h> | |
#define PACKET_DROP_PROBABILITY 4 // Inverse of the probability | |
#define PACKET_DATA_LENGTH 10 | |
#define MAX_PACKET_DELAY (50 * 1000 * 1000) // in nanoseconds | |
#define SENDING_WINDOW_SIZE 10 | |
#define SENDER_TIMEOUT 100 // in milliseconds | |
#define SENDER_WAIT_SLEEP (10 * 1000 * 1000) // in nanoseconds | |
enum packet_type { DATA_PACKET, ACK_PACKET }; | |
typedef struct packet { | |
enum packet_type type; | |
uint32_t seq_no; | |
int data_length; | |
char data[PACKET_DATA_LENGTH]; | |
} packet; | |
void sleep_helper(int nsecs); | |
void random_delay(); | |
long time_in_ms(); | |
void send_packet(int fd, packet pack); | |
int recv_packet(int fd, packet *pack); | |
packet build_packet(enum packet_type type, int seq_no, char *data, int size); | |
void sender(char *data, int data_size, int sending_pipe[2], int recv_pipe[2]); | |
void receiver(char *data, int data_size, int sending_pipe[2], int recv_pipe[2]); | |
int main() { | |
int sender_pipe[2], receiver_pipe[2]; | |
if(pipe(sender_pipe) == -1) { | |
fprintf(stderr, "Failed to create pipe for sender\n"); | |
exit(1); | |
} | |
if(pipe(receiver_pipe) == -1) { | |
fprintf(stderr, "Failed to create pipe for receiver\n"); | |
exit(1); | |
} | |
char *buffer = NULL; | |
int read; | |
size_t len; | |
printf("Enter the data to transmit\n"); | |
getline(&buffer, &len, stdin); | |
len = strlen(buffer); | |
pid_t child_id = fork(); | |
if(child_id == -1) { | |
fprintf(stderr, "Failed to fork\n"); | |
exit(1); | |
} | |
if(child_id) { | |
char *r_buffer = malloc(sizeof(char) * (len + 1)); | |
receiver(r_buffer, len + 1, receiver_pipe, sender_pipe); | |
kill(child_id, SIGKILL); // Kill the sender since we have received all the data | |
printf("Receiver received: %s\n", r_buffer); | |
free(r_buffer); | |
} | |
else { | |
sender(buffer, len + 1, sender_pipe, receiver_pipe); | |
} | |
free(buffer); | |
} | |
int min(int a, int b) { return a > b ? b : a; } | |
void sender(char *data, int data_size, int sending_pipe[2], int recv_pipe[2]) { | |
close(sending_pipe[0]); | |
close(recv_pipe[1]); | |
fcntl(recv_pipe[0], F_SETFL, O_NONBLOCK); // Make the recv_pipe non-blocking | |
printf("Sender: sending data of length %d\n", data_size); | |
packet pack_buffer[SENDING_WINDOW_SIZE]; | |
unsigned int window_start = 0, window_end = SENDING_WINDOW_SIZE - 1, | |
next_seq = 0, pack_buffer_start = 0, sent = 0; | |
while(sent != data_size || window_start != next_seq) { | |
// If the window is more than half empty, send more data | |
// Assuming next_seq has not wrapped around | |
printf("Sender: in main loop, sent %d, window_start %d, window_end %d, next_seq %d\n", sent, window_start, window_end, next_seq); | |
if(next_seq - window_start < SENDING_WINDOW_SIZE / 2) { | |
printf("Sender: Buffer is half empty, attempting to send data\n", data_size); | |
while(next_seq - window_start < SENDING_WINDOW_SIZE && sent < data_size) { | |
int size = min(data_size - sent, PACKET_DATA_LENGTH); | |
packet pack = build_packet(DATA_PACKET, next_seq, data + sent, size); | |
int buff_index = (pack_buffer_start + (next_seq - window_start)) % SENDING_WINDOW_SIZE; | |
pack_buffer[buff_index] = pack; | |
sent += size; | |
next_seq = next_seq + 1; | |
printf("Sender: sending packet with seq no %d\n", pack.seq_no); | |
send_packet(sending_pipe[1], pack); | |
} | |
} | |
long long c_time = time_in_ms(); | |
// Timeout part | |
while(time_in_ms() - c_time < SENDER_TIMEOUT && window_start < next_seq) { | |
packet pack; | |
int read = recv_packet(recv_pipe[0], &pack); | |
if(read == -1) { | |
printf("Sender: received no ack packet, sleeping...\n"); | |
sleep_helper(SENDER_WAIT_SLEEP); | |
continue; | |
} | |
printf("Sender: received packet with seq no %d\n", pack.seq_no); | |
if(pack.type == ACK_PACKET && pack.seq_no > window_start | |
&& pack.seq_no <= next_seq) { | |
printf("Sender: received ack is in the range...\n"); | |
// We received a ACK packet from receiver within our window | |
// ACK seq no is 1 more than the last successfully received packet | |
int no_of_successful_packs = pack.seq_no - window_start; | |
window_start += no_of_successful_packs; | |
window_end += no_of_successful_packs; | |
pack_buffer_start = (pack_buffer_start + no_of_successful_packs) % SENDING_WINDOW_SIZE; | |
} | |
else { | |
printf("Sender: rejected packet...\n"); | |
} | |
} | |
// Resend all the packets in the buffer | |
int i; | |
for(i = window_start; i < next_seq; i++) { | |
int buff_index = (pack_buffer_start + (i - window_start)) % SENDING_WINDOW_SIZE; | |
send_packet(sending_pipe[1], pack_buffer[buff_index]); | |
} | |
} | |
} | |
void receiver(char *data, int data_size, int sending_pipe[2], int recv_pipe[2]) { | |
close(sending_pipe[0]); | |
close(recv_pipe[1]); | |
printf("Receiver: Have to receive data of length %d\n", data_size); | |
unsigned int next_seq = 0, read = 0; | |
while(read < data_size) { | |
packet pack; | |
recv_packet(recv_pipe[0], &pack); | |
if(pack.type == DATA_PACKET && pack.seq_no == next_seq) { | |
printf("Receiver: received packet with seq_no %d\n", pack.seq_no); | |
int i; | |
for(i = 0; i < pack.data_length; i++) { | |
data[read + i] = pack.data[i]; | |
} | |
read += pack.data_length; | |
next_seq++; | |
send_packet(sending_pipe[1], build_packet(ACK_PACKET, next_seq, NULL, 0)); | |
} | |
else { | |
printf("Receiver: rejecting packet with seq_no %d\n", pack.seq_no); | |
} | |
} | |
} | |
void send_packet(int fd, packet pack) { | |
if(rand() % PACKET_DROP_PROBABILITY == 0) return; // Random packet drop | |
random_delay(); | |
write(fd, &pack, sizeof(packet)); | |
} | |
int recv_packet(int fd, packet *pack) { | |
random_delay(); | |
return read(fd, pack, sizeof(packet)); | |
} | |
packet build_packet(enum packet_type type, int seq_no, char *data, int size) { | |
packet pack; | |
pack.type = type; | |
pack.seq_no = seq_no; | |
pack.data_length = size; | |
int i; | |
for(i = 0; i < size && i < PACKET_DATA_LENGTH; i++) { | |
pack.data[i] = data[i]; | |
} | |
return pack; | |
} | |
void sleep_helper(int nsecs) { | |
struct timespec *tsp = malloc(sizeof(struct timespec)); | |
tsp->tv_nsec = nsecs; | |
tsp->tv_sec = 0; | |
nanosleep(tsp, NULL); | |
free(tsp); | |
} | |
void random_delay() { | |
sleep_helper(rand() % MAX_PACKET_DELAY); | |
} | |
long time_in_ms() { | |
struct timespec spec; | |
clock_gettime(CLOCK_MONOTONIC, &spec); | |
return (spec.tv_sec * 1000) + (spec.tv_nsec / 1000000); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Awesome!