Program for IP Forwarding Table Lookup

There exists a routing table in the Unix operating system consisting of several tuples that contain the I.P. (Internet Protocol) address of the network, the subnet mask, the IP address of the gateway, and the name of the interface.

This information is required for forwarding packets to the exterior of the network for connecting to the internet. In this article, we shall have a look at how a computer system takes a sequence of decisions when packets need to be forwarded.

Introduction

There exist the following two different methods of delivering IP datagrams:

Routing

Involves finding and setting up routing tables.

Forwarding

Involves passing a packet from an input interface to an output interface.

The process of forwarding must be executed as quickly as possible. On routers, forwarding is done often with hardware support. On personal computer systems, it is performed in the kernel of the machine’s operating system.

Example of IP Forwarding Lookup Table

Let us have a look at a sample IP forwarding lookup table for a clearer understanding. Assume there exists a packet having source IP address “20.129.0.1”. Its routing table may look something like the following:

We shall refer to this system as well as the table above in the article later.

Working of IP Forwarding Lookup Table

When a packet is sent to the kernel of the operating system in order to find the interface and gateway, the first thing that is done is a bitwise AND operation individually with each subnet mask entry in the table for finding the longest prefix match. After obtaining the desired bitwise AND operation result, it’s then compared with the IP addresses of the network.

The result now produced is the IP address corresponding to the gateway, as well as the name of the interface via which the packet may now go out. “00010100.10000001.00000000.00000001” is the binary representation of “20.129.0.1”. A bitwise AND operation is performed upon this value with the subnet mask of each entry in our table.

The subnet mask from entry 2 (20.128.0.0, 255.128.0.0, 12.1.1.1, eth1) yields the longest matching prefix for our packet. Therefore, our packet goes out from the interface eth1 and selects the gateway 12.1.1.1 for forwarding.

Implementation of IP Forwarding Lookup Table

Following is a C program that implements an IP forwarding lookup table

#include "arpa/inet.h"
#include "netinet/in.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

const int Y = 160, X = 16;

// Implement linked-list data structure for storing IP addresses.
struct node {
    char* data;
    struct node* next;
} * head[15];

// getData retreives data from a file and stores them into arrays
void getData(FILE* filePtr, char buffer[X][Y], char networkid[X][Y], char mask[X][Y], char gateWay[X][Y], char port[X][Y]){
    char line[200];
    int c, j, i = 0, k = 0, m = 0;
    // Parse the data from a file line by line sequentially. Store these lines of read data in arrays separately.
    while (fgets(line, sizeof(line), filePtr)){
        j = 0;
        for (int l = 0; l < strlen(line); l++){
            buffer[i][j++] = line[l];
        }
        ++i;
    }
    // We shall extract network id, subnet mask, gateWay and port, from each line stored in buffer, and store them into arrays individually.
    for (i = 0; i < 15; i++){
        k = 0;
        for(j = 0; buffer[i][j] != ','; j++){
            networkid[i][k++] = buffer[i][j];
        }
        m = j + 2, k = 0;
        for (j = m; buffer[i][j] != ','; j++){
            mask[i][k++] = buffer[i][j];
        }
        m = j + 2, k = 0;
        for (j = m; buffer[i][j] != ','; j++){
            gateWay[i][k++] = buffer[i][j];
        }
        m = j + 2, k = 0;
        for (j = m; buffer[i][j] != '\0'; j++){
            port[i][k++] = buffer[i][j];
        }
    }
}
// insert creates a routing table by using the arrays created by getData function using our linked list data structure
void insert(char networkid[X][Y], char mask[X][Y], char gateWay[X][Y], char port[X][Y], char buffer[X][Y]){
    struct node* newNode;
    char *tmp4, *tmp3, *tmp2, *tmp1;
    // Now let us initialise the linked list with NULL
    for (int i = 0; i < X; ++i) {
        head[i] = NULL;
    }
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < 4; j++) {
            // If head[i] is found to be null, we shall then initialize it first, and then store the network id in it.
            if (head[i] == NULL) {
                newNode = (struct node*)malloc(sizeof(struct node));
                newNode->data = networkid[i];
                newNode->next = NULL;
                head[i] = newNode;
            }
            // If head[i] is not null, but the value of j is set to 1, we shall then create a new node as the next pointer to newNode. This new node will contain the subnet.
            else if (j == 1) {
                newNode->next = (struct node*)malloc(sizeof(struct node));
                newNode = newNode->next;
                newNode->data = mask[i];
                newNode->next = NULL;
            }
            // If head[i] isn't null, but the value of j is set to 2, we shall then create a new node as the next pointer to the newNode. It will contain the gateway.
            else if (j == 2) {
                newNode->next = (struct node*)malloc(sizeof(struct node));
                newNode = newNode->next;
                newNode->data = gateWay[i];
            }
            // If head[i] is not null, but the value of j is set to 3, then we shall create a new node as the next pointer to the newNode. This newl;y created node will contain the port.
            else if (j == 3) {
                newNode->next = (struct node*)malloc(sizeof(struct node));
                newNode = newNode->next;
                newNode->data = port[i];
            }
        }
    }
    // Now let us sort the array head on the basis of longest prefix of subnet mask
    for (int i = 0; i < X; i++) {
        for (int j = i; j < X; j++) {
            // We must compute the longest prefix of subnet by using the system call "inet_addr()" which returns the decimal value corresponding to an IP address.
            if (inet_addr(head[i]->next->data) < inet_addr(head[j]->next->data)){
                struct node* tmp = head[i];
                head[i] = head[j];
                head[j] = tmp;
            }
        }
    }
}
// search function searches for the IP of the gateWay and port number in the routing table through which packet is sent to the next node/destination
void search(FILE* filePtr1, FILE* filePtr2){
    unsigned int val;
    struct in_addr addr;
    char str[100];
    fprintf(filePtr2, "%c", ' ');
    // Parse the file 'input.txt' one line at a time, and perform bitwise AND operation between the subnet mask and the input(destination) IP coming from file.
    while(fgets(str, sizeof(str), filePtr1)){
        for(int i = 0; i < X; i++){
            // Now we shall perform the bitwise AND operation on the result - the Decimal value of the IP address.
            addr.s_addr = val = inet_addr(str) & inet_addr(head[i]->next->data);
            int counter = 0;
            char *str2 = head[i]->data, *str1 = inet_ntoa(addr);
            // Now we shall make a comparison between the network id string and the result obtained from the biotwise AND operation. If the 2 are the same, then we must increment the counter by.
            for (int j = 0; str1[j] != '\0'; ++j){
                counter+=(str1[j] == str2[j]);
            }
            // If the value of the counter is found to be the same as the length of network id, we shall then find the port number as well as the gateWay IP of that respective network ID, and save it into the file 'output.txt'.
            if(counter == strlen(str1)){
                for(struct node* tmp = head[i]->next->next; tmp != NULL; tmp=tmp->next) {
                    fprintf(filePtr2, "%s ", tmp->data);
                }
                break;
            }
        }
    }
}

// The CLI program as well as the main driver function code.
int main(int argc, char* argv[]){
    FILE *fin, *fout, *filePtr;
    char port[X][Y] = { { 0 } };
    char gateWay[X][Y] = { { 0 } };
    char mask[X][Y] = { { 0 } };
    char networkid[X][Y] = { { 0 } };
    char buffer[X][Y] = { { 0 } };
    // If the number of command-line arguments is smaller than 3, we shall then show a standard error.
    if (argc < 3){
        fprintf(stderr, "File name:%s\n", argv[0]);
        return 1;
    }
    // If 3 arguments are given then the file output.txt must be opened in write mode, and the files input.txt and routing.txt must be opened in reading mode.
    else{
        fin = fopen(argv[1], "r");
        fout = fopen(argv[2], "w");
        filePtr = fopen(argv[3], "r");
    }
    // If either of the files is inexistent, then we shall give an error.
    if (filePtr == NULL || fin == NULL || fout == NULL){
        printf("Error");
        return 0;
    }

    // We shall now read the data of the 'routing.txt' file one line at a time, and then store them into an 'buffer' named array. Then we shall store the coma separated values from buffer, into their respective array.
    getData(filePtr, buffer, networkid, mask, gateWay, port);
    // Now let us create a routing table using the linked list.
    insert(networkid, mask, gateWay, port, buffer);
    // Now let us take input from the file input.txt, containing only the destination IP address. Then we shall search for the route through which the packet is sent in network. The output then is stored in a file named "output.txt".
    search(fin, fout);
    printf("Forwarding table has been implemented successfully");
    printf("See the output in %s file\n", argv[2]);
    // We must closes all the open files.
    fclose(fin);
    fclose(filePtr);
    fclose(fout);
    return 0;
}

Conclusion

• There exists a routing table In the Unix operating system consisting of several tuples that contain the I.P. (Internet Protocol) address of the network, the subnet mask, the IP address of the gateway, and the name of the interface.
• There exist two different methods of delivering IP datagrams: Routing and Forwarding.
• When a packet is sent to the kernel of the operating system in order to find the interface and gateway, the first thing that is done is a bitwise AND operation individually with each subnet mask entry in the table for finding the longest prefix match.