Sliding window protocol

go_back_n.c

#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);
}

Awesome!