Socket Programming

I Project Description

Many network related applications require fast identification of the shortest path between a pair of nodes to optimize routing performance. Given a weighted graph 𝐺(𝑉, 𝐸) consisting of a set of vertices 𝑉 and a set of edges 𝐸, we aim at finding the path in 𝐺 connecting the source vertex 𝑣1 and the destination vertex 𝑣𝑛, such that the total edge weight along the path is minimized.
This project implements a distributed system to compute shortest path based on client’s query. Suppose the system stores maps of a city, and the client would like to obtain the shortest path and the corresponding transmission delay between two points in the city. The figure below summarizes the system architecture. The distributed system consists of three computation nodes: a main server (AWS), connected to two backend servers (Server A and Server B). On the backend server A, there is a file named map.txt storing the map information of the city. The AWS server interfaces with the client to receive his query and to return the computed answer. The backend servers, A and B, perform the actual shortest path and transmission delay computation based on the message forwarded by AWS server.

Detailed computation and communication steps performed by the system is listed below:

[Communication] Client -> AWS: client sends the map ID, the source node in the map and the transmission file size (unit: bit) to AWS via TCP.
[Communication] AWS -> ServerA: AWS forwards the map ID and source node to serverA via UDP.
[Computation] ServerA reads map information from map.txt, uses Dijkstra to find the shortest path from input source to all the other nodes and print them out in a pre-defined format.
[Communication] ServerA -> AWS: ServerA sends the outputs of Dijkstra to AWS.
[Communication] AWS -> ServerB: AWS sends to ServerB the file size as well as the outputs of ServerA.
[Computation] ServerB calculates the transmission delay, propagation delay and end to end delay for each path.
[Communication] ServerB -> AWS: ServerB sends the calculated delay values to AWS.
[Communication] AWS -> client: AWS sends to client the shortest path and delay results, and client prints the final results.

The map information of the city is stored in a file named map.txt, stored in ServerA. The map.txt file contains information of multiple maps (i.e. graphs), where each map can be considered as a community of the city. Within each map, the edge and vertex information are further specified, where an edge represents a communication link.
The format of map.txt is defined as follows:

<Map ID 1>
<Propagation speed>
<Transmission speed>
<Vertex index for one end of the edge> <Vertex index for the other end> <Distance between the two vertices>
... (Specification for other edges)
<Map ID 2>
...

Examples:

Github

II Implement Steps

Client->AWS via TCP Connection
Running ./client <Map ID> <Source Vertex Index> <File Size> to see if the connection is successful.
AWS->Server A/ ServerB via UDP
After connection, display Server A/ Server B is up and running using UDP on port <Port Number>

Calculate shortest path in server A
Using Dijkstra Algorithm

vector<double> Dijkstra(int src){
    vector<double> shortestPath(point_count, DBL_MAX);
    shortestPath[src] = 0;
    unordered_set<int> visited;
    priority_queue<pValue, vector<pValue>, greater<pValue>> pq;
    pq.emplace(0, src);
    while(!pq.empty()){
        int p = pq.top().second;
        pq.pop();
        if(visited.count(p)) continue;
        visited.insert(p);

        for(int i=0; i<point_count; i++){
            if(adjMatrix[p][i] != 0){
                if(shortestPath[i] > shortestPath[p] + adjMatrix[p][i]){
                    shortestPath[i] = shortestPath[p] + adjMatrix[p][i];
                    pq.emplace(shortestPath[i], i);
                }
            }
        }
    }
    return shortestPath;
}