Skip to main content

Go-Back-N ARQ

Here's a simple Go-Back-N ARQ implementation using C socket programming to simulate communication between a client (sender) and a server (receiver).

Overview:

  • Go-Back-N ARQ allows the sender to send multiple packets (window size) without waiting for individual ACKs.
  • If a packet is lost or an ACK is not received, all packets starting from the lost packet are retransmitted.
  • The server randomly simulates ACK loss or successful reception.

Program Structure:

  • Server: Simulates ACK reception with a chance of ACK loss, acknowledging packets up to the first lost packet.
  • Client: Sends packets in a sliding window fashion, retransmitting the entire window if an ACK is lost.
Server - Receiver

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <time.h>

#define PORT 8080
#define BUFFER_SIZE 1024
#define LOSS_PROBABILITY 30  // 30% chance of ACK loss

int main() {
    int server_fd, new_socket;
    struct sockaddr_in address;
    int addrlen = sizeof(address);
    char buffer[BUFFER_SIZE] = {0};
    int ack;

    srand(time(0));  // Random seed for ACK simulation

    // Create socket
    if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) == 0) {
        perror("Socket creation failed");
        exit(EXIT_FAILURE);
    }

    address.sin_family = AF_INET;
    address.sin_addr.s_addr = INADDR_ANY;
    address.sin_port = htons(PORT);

    // Bind socket
    if (bind(server_fd, (struct sockaddr *)&address, sizeof(address)) < 0) {
        perror("Bind failed");
        exit(EXIT_FAILURE);
    }

    // Listen for client
    if (listen(server_fd, 3) < 0) {
        perror("Listen failed");
        exit(EXIT_FAILURE);
    }

    printf("Server: Waiting for connection...\n");

    if ((new_socket = accept(server_fd, (struct sockaddr *)&address, (socklen_t*)&addrlen)) < 0) {
        perror("Accept failed");
        exit(EXIT_FAILURE);
    }

    printf("Server: Connection established.\n");

    while (1) {
        memset(buffer, 0, BUFFER_SIZE);
        int valread = read(new_socket, buffer, BUFFER_SIZE);
        if (valread == 0) break;

        ack = atoi(buffer);
        printf("Server: Received packet %d\n", ack);

        // Simulate ACK loss
        if (rand() % 100 < LOSS_PROBABILITY) {
            printf("Server: ACK for packet %d lost!\n\n", ack);
        } else {
            sleep(1);  // Simulate processing delay
            printf("Server: ACK sent for packet %d\n\n", ack);
            memset(buffer,0,BUFFER_SIZE);
            sprintf(buffer, "%d", ack);  // Send ACK
            send(new_socket, buffer, strlen(buffer)+1, 0);
        }
    }

    close(new_socket);
    close(server_fd);
    return 0;
}

Client - Sender

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/time.h>

#define PORT 8080
#define BUFFER_SIZE 1024
#define TIMEOUT 3  // Timeout in seconds
#define WINDOW_SIZE 4  // Sliding window size
#define TOTAL_PACKETS 10  // Number of packets to send

int main() {
    int sock = 0;
    struct sockaddr_in serv_addr;
    char buffer[BUFFER_SIZE] = {0};
    struct timeval tv;

    if ((sock = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
        perror("Socket creation failed");
        exit(EXIT_FAILURE);
    }

    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(PORT);

    if (inet_pton(AF_INET, "127.0.0.1", &serv_addr.sin_addr) <= 0) {
        perror("Invalid address/ Address not supported");
        exit(EXIT_FAILURE);
    }

    if (connect(sock, (struct sockaddr *)&serv_addr, sizeof(serv_addr)) < 0) {
        perror("Connection failed");
        exit(EXIT_FAILURE);
    }

    printf("Client: Connected to server.\n");

    tv.tv_sec = TIMEOUT;
    tv.tv_usec = 0;
    setsockopt(sock, SOL_SOCKET, SO_RCVTIMEO, (const char*)&tv, sizeof(tv));

    int base = 1;
    int next_to_send = 1;
    int ack, packets_acked = 0;

    while (packets_acked < TOTAL_PACKETS) {
        // Send all packets in the window
        while (next_to_send < base + WINDOW_SIZE && next_to_send <= TOTAL_PACKETS) {
            memset(buffer,0,BUFFER_SIZE);
            printf("Client: Sending packet %d\n", next_to_send);
            sprintf(buffer, "%d", next_to_send);
            send(sock, buffer, strlen(buffer)+1, 0);
            next_to_send++;
      }

        // Wait for ACK
        memset(buffer, 0, BUFFER_SIZE);
        int valread = read(sock, buffer, BUFFER_SIZE);

        if (valread > 0) {
            ack = atoi(buffer);
            printf("Client: ACK received for packet %d\n", ack);
            
            // Slide the window if ACK corresponds to the base
            if (ack == base) {
                base = ack + 1;
                packets_acked = ack;
            }
        } else {
            printf("Client: Timeout! Retransmitting from packet %d...\n", base);
            next_to_send = base;  // Reset next_to_send to base for retransmission
        }
    }

    printf("Client: All packets sent successfully.\n");
    close(sock);
    return 0;
}

How to Run the Program:

  1. Compile the Server and Client

    gcc server.c -o server
    gcc client.c -o client
  1. Run the Server

    ./server
  1. Run the Client (in a new terminal)
    ./client

How It Works:

  • Client sends packets in batches (window size of 4).
  • If an ACK is not received within the timeout period, the client retransmits starting from the first unacknowledged packet.
  • Server randomly decides to send ACKs or simulate ACK loss.
  • This process continues until all packets are successfully acknowledged.

Testing Process:

  1. Run the server first.
  2. Run the client in a separate terminal.
  3. Observe the gradual packet transmission and retransmissions based on ACK loss.

Key Points:

  • Sliding window approach for efficiency.
  • Efficient retransmission by avoiding the need to retransmit all packets, only those starting from the missing ACK.
  • Simulates real-world network issues like packet loss and retransmission.

Code Explanations - Receiver Server

1. Headers and Macros:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <time.h>
  • Purpose: These headers provide necessary functions for socket programming and general operations.
    • stdio.h – Standard I/O functions (printf, perror).
    • stdlib.h – For general utilities (exit, atoi, rand).
    • string.h – For string handling (memset, strlen).
    • unistd.h – For system calls (read, write, close).
    • arpa/inet.h – Socket-related functions (inet_addr, sockaddr_in).
    • time.h – For randomization (time, srand).

#define PORT 8080
#define BUFFER_SIZE 1024
#define LOSS_PROBABILITY 30
  • PORT – The server listens on port 8080.
  • BUFFER_SIZE – Defines the size of the buffer used for sending/receiving data (1 KB).
  • LOSS_PROBABILITY – Simulates a 30% chance that the ACK will be "lost" (simulated by not sending an acknowledgment).

2. Variable Declarations:


int server_fd, new_socket;
struct sockaddr_in address;
int addrlen = sizeof(address);
char buffer[BUFFER_SIZE] = {0};
int ack;
  • server_fd – File descriptor for the server socket.
  • new_socket – File descriptor for the client connection (after accept()).
  • address – Stores server address information (IPv4, port, IP).
  • addrlen – Length of the address structure.
  • buffer – Temporary buffer for sending and receiving data.
  • ack – Packet number for which an acknowledgment (ACK) is sent.

3. Random Seed Initialization:


srand(time(0));
  • Purpose: Initializes the random number generator for simulating packet loss.
  • srand(time(0)) – Seeds randomness based on the current time to ensure that every execution results in different ACK loss patterns.

4. Socket Creation:


if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) == 0) {
    perror("Socket creation failed");
    exit(EXIT_FAILURE);
}
  • socket(AF_INET, SOCK_STREAM, 0) – Creates a TCP socket (SOCK_STREAM indicates a stream-based connection).
  • Error Handling: If socket creation fails, an error is printed (perror), and the program exits.

5. Server Address Configuration:


address.sin_family = AF_INET;
address.sin_addr.s_addr = INADDR_ANY;
address.sin_port = htons(PORT);
  • sin_family – Specifies the address family (AF_INET for IPv4).
  • sin_addr.s_addr – Binds the server to listen on all available network interfaces (INADDR_ANY).
  • sin_port – Converts the port number to network byte order (htons(PORT)). This ensures compatibility across systems with different byte ordering.

6. Binding the Socket to the Address:


if (bind(server_fd, (struct sockaddr *)&address, sizeof(address)) < 0) {
    perror("Bind failed");
    exit(EXIT_FAILURE);
}
  • bind – Binds the server socket to the specified IP and port.
  • Error Handling: If the bind fails (e.g., if the port is already in use), the server exits.

7. Listening for Incoming Connections:


if (listen(server_fd, 3) < 0) {
    perror("Listen failed");
    exit(EXIT_FAILURE);
}
  • listen – Puts the server in a listening state for incoming connections.
  • 3 – Maximum number of pending connections in the queue.
  • Error Handling: If listen fails, the server exits.

8. Accepting Client Connections:


printf("Server: Waiting for connection...\n");

if ((new_socket = accept(server_fd, (struct sockaddr *)&address, (socklen_t*)&addrlen)) < 0) {
    perror("Accept failed");
    exit(EXIT_FAILURE);
}
  • accept – Waits for a client to connect. It blocks execution until a connection request arrives.
  • new_socket – A new socket for handling the specific client connection (different from the server socket).
  • Error Handling: If accept fails, the server exits.

9. Connection Established:


printf("Server: Connection established.\n");
  • Indicates that the client successfully connected.

10. Receiving and Sending ACKs:


while (1) {
    memset(buffer, 0, BUFFER_SIZE);
    int valread = read(new_socket, buffer, BUFFER_SIZE);
    if (valread == 0) break;
  • while (1) – Infinite loop to keep receiving packets until the client disconnects.
  • memset – Clears the buffer before each packet reception to avoid residual data.
  • read – Reads data from the client into the buffer.
  • valread == 0 – If no data is received (client disconnects), the loop breaks.

11. Processing Received Packets:


ack = atoi(buffer);
printf("Server: Received packet %d\n", ack);
  • atoi – Converts the received packet number (in string format) to an integer.

12. Simulating ACK Loss:


if (rand() % 100 < LOSS_PROBABILITY) {
    printf("Server: ACK for packet %d lost!\n\n", ack);
}
  • rand() % 100 < 30 – Simulates ACK loss by generating a random number between 0 and 99. If the value falls below 30 (30% chance), the ACK is "lost".
  • No ACK Sent: The server prints the loss message but does not send an acknowledgment.

13. Sending ACKs (if not lost):


else {
    sleep(1);
    printf("Server: ACK sent for packet %d\n\n", ack);
    memset(buffer, 0, BUFFER_SIZE);
    sprintf(buffer, "%d", ack);
    send(new_socket, buffer, strlen(buffer) + 1, 0);
}
  • sleep(1) – Simulates network delay by pausing for 1 second before sending an ACK.
  • sprintf – Converts the integer ack to a string format for transmission.
  • send – Sends the ACK back to the client.

14. Closing Sockets:


close(new_socket);
close(server_fd);
return 0;
  • close – Closes both the client (new_socket) and server (server_fd) sockets to release resources.

Summary:

  • The server accepts a connection from the client and continuously listens for incoming packets.
  • For each packet received, it simulates ACK loss with a 30% probability.
  • If ACK is not "lost," the server sends it back to the client after a small delay.
  • This simulates the behavior of a Go-Back-N ARQ protocol where packets may need retransmission if ACKs are not received.


Code Explanations Sender - Client

1. Headers and Macros:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/time.h>
  • Standard C Headers:
    • stdio.h – For input/output functions (printf, sprintf).
    • stdlib.h – For general functions like exit(), atoi().
    • string.h – For string manipulation (strlen, memset).
    • unistd.h – For system calls (read, write, close).
    • arpa/inet.h – For socket functions (inet_pton, sockaddr_in).
    • sys/time.h – For handling timeouts with setsockopt().

#define PORT 8080
#define BUFFER_SIZE 1024
#define TIMEOUT 3  // Timeout in seconds
#define WINDOW_SIZE 4  // Sliding window size
#define TOTAL_PACKETS 10  // Number of packets to send
  • Macros:
    • PORT – Defines the port number used for communication.
    • BUFFER_SIZE – Sets the buffer size for sending and receiving data.
    • TIMEOUT – Specifies how long the client will wait for an ACK before retransmitting.
    • WINDOW_SIZE – Number of packets that can be sent before waiting for ACKs.
    • TOTAL_PACKETS – Total number of packets to send.

2. Socket Creation and Connection:


int sock = 0;
struct sockaddr_in serv_addr;
char buffer[BUFFER_SIZE] = {0};
struct timeval tv;
  • Socket Variables:
    • sock – The socket descriptor.
    • serv_addr – Stores server address information.
    • buffer – Temporary buffer for sending and receiving data.
    • tv – Timeout structure for setting the socket read timeout.

if ((sock = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
    perror("Socket creation failed");
    exit(EXIT_FAILURE);
}
  • Create Socket:
    • socket(AF_INET, SOCK_STREAM, 0) – Creates a TCP socket.
    • AF_INET – IPv4 address family.
    • SOCK_STREAM – Stream socket (TCP).
    • perror – Prints error if socket creation fails.

3. Server Address Setup:


serv_addr.sin_family = AF_INET;
serv_addr.sin_port = htons(PORT);

if (inet_pton(AF_INET, "127.0.0.1", &serv_addr.sin_addr) <= 0) {
    perror("Invalid address/ Address not supported");
    exit(EXIT_FAILURE);
}
  • Configure Server Address:
    • sin_family – Set to AF_INET (IPv4).
    • sin_port – Converts the port to network byte order using htons().
    • inet_pton – Converts IP address (localhost 127.0.0.1) from text to binary.

4. Connect to Server:


if (connect(sock, (struct sockaddr *)&serv_addr, sizeof(serv_addr)) < 0) {
    perror("Connection failed");
    exit(EXIT_FAILURE);
}
printf("Client: Connected to server.\n");
  • Establish Connection:
    • connect() – Connects to the server using the specified address.
    • If the connection fails, an error message is displayed.

5. Set Timeout:


tv.tv_sec = TIMEOUT;
tv.tv_usec = 0;
setsockopt(sock, SOL_SOCKET, SO_RCVTIMEO, (const char*)&tv, sizeof(tv));
  • Timeout Setup:
    • setsockopt – Configures the socket to timeout if no data is received within 3 seconds (TIMEOUT).

6. Sliding Window Variables:


int base = 1;
int next_to_send = 1;
int ack, packets_acked = 0;
  • Sliding Window Variables:
    • base – The first unacknowledged packet.
    • next_to_send – Tracks the next packet to be sent.
    • ack – Stores received ACKs.
    • packets_acked – Total packets acknowledged so far.

7. Sending Packets (Sliding Window):


while (packets_acked < TOTAL_PACKETS) {
    // Send packets in the window
    while (next_to_send < base + WINDOW_SIZE && next_to_send <= TOTAL_PACKETS) {
        printf("Client: Sending packet %d\n", next_to_send);
        sprintf(buffer, "%d", next_to_send);
        send(sock, buffer, strlen(buffer)+1, 0);
        next_to_send++;
    }
  • Send Packets Within Window:
    • while (next_to_send < base + WINDOW_SIZE) – Send packets until the window is full.
    • sprintf(buffer, "%d", next_to_send) – Prepare packet number as a string.
    • send() – Send the packet to the server.
    • Increment next_to_send after each packet.

8. Wait for ACKs:


    while (1) {
        memset(buffer, 0, BUFFER_SIZE);
        int valread = read(sock, buffer, BUFFER_SIZE);
        
        if (valread > 0) {
            ack = atoi(buffer);
            printf("Client: ACK received for packet %d\n", ack);
            
            if (ack >= base) {
                base = ack + 1;
                packets_acked = ack;
            }
        } else {
            printf("Client: Timeout! Retransmitting from packet %d...\n", base);
            next_to_send = base;
            break;
        }
    }
}
  • ACK Handling (Loop Until Timeout):
    • read() – Wait for the server to send an ACK.
    • atoi(buffer) – Convert received string to integer (ACK number).
    • If ACK is received, slide the window by adjusting base and increment packets_acked.
    • Timeout Handling:
      • If no ACK is received within 3 seconds, the client retransmits packets starting from the base.

9. Completion:


printf("Client: All packets sent successfully.\n");
close(sock);
return 0;
  • Completion Message:
    • Once all packets are acknowledged, the client displays a success message and closes the socket.

How It Works:

  1. Window-Based Transmission:

    • Packets are sent in chunks (size of the window).
    • The client waits for ACKs for the sent packets.

  2. Timeouts and Retransmission:

    • If an ACK is not received within 3 seconds, the client retransmits starting from the first unacknowledged packet (base).

  3. Efficiency:

    • Multiple packets can be sent before waiting for ACKs (Go-Back-N mechanism).
    • The window slides forward when consecutive ACKs are received.

Key Concepts:

  • Sliding Window: Allows multiple packets to be in-flight at once.
  • Timeout & Retransmission: Ensures lost packets are resent.
  • Go-Back-N ARQ: If a packet is lost, all packets from that point are retransmitted.



Comments

Post a Comment

Popular posts from this blog

Server/Client Communication-python

The basic mechanisms of client-server setup are: A client app send a request to a server app.  The server app returns a reply.  Some of the basic data communications between client and server are: File transfer - sends name and gets a file.  Web page - sends url and gets a page.  Echo - sends a message and gets it back.  Client server communication uses socket.              To connect to another machine, we need a socket connection. What's a connection?  A relationship between two machines, where two pieces of software know about each other. Those two pieces of software know how to communicate with each other. In other words, they know how to send bits to each other. A socket connection means the two machines have information about each other, including network location (IP address) and TCP port. (If we can use anology, IP address is the phone number and the TCP port is the extension).  A so...
19 comments
Read more

Banker's Algorithm

Banker's algorithm is a deadlock avoidance algorithm. It is named so because this algorithm is used in banking systems to determine whether a loan can be granted or not. Consider there are n account holders in a bank and the sum of the money in all of their accounts is S. Everytime a loan has to be granted by the bank, it subtracts the loan amount from the total money the bank has. Then it checks if that difference is greater than S. It is done because, only then, the bank would have enough money even if all the n account holders draw all their money at once. Banker's algorithm works in a similar way in computers. Whenever a new process is created, it must exactly specify the maximum instances of each resource type that it needs. Let us assume that there are n processes and m resource types. Some data structures are used to implement the banker's algorithm. They are: Available: It is an array of length m . It represents the number of available resourc...
7 comments
Read more

Inter Process Communication-Message Queue

Interprocess communication (IPC) is a set of programming interfaces that allow a programmer to coordinate activities among different program processes that can run concurrently in an operating system. This allows a program to handle many user requests at the same time. Since even a single user request may result in multiple processes running in the operating system on the user's behalf, the processes need to communicate with each other. The IPC interfaces make this possible. Each IPC method has its own advantages and limitations so it is not unusual for a single program to use all of the IPC methods . Message Based Communication Messages are a very general form of communication. Messages can be used to send and receive formatted data streams between arbitrary processes. Messages may have types. This helps in message interpretation. The type may specify appropriate permissions for processes. Usually at the receiver end, messages are put in a queue. Messages may also be fo...
13 comments
Read more