May 21, 2022

greedy algorithms for computer network topology | by Mohammad Masum, PhD | February 2022

Application of Prims and Kruskals algorithms to network topology

Photo by Arlington Research on Unsplash

network topology is an important procedure of a network where the devices (nodes) are interconnected in the network using network lines such as Ethernet. Topology also describes the process of data transfer between network connections. Thus, the importance of computer network topology is increasing drastically in most of the regular activities of the organization due to the increasing use of electronic devices such as computers. With the increasing importance, the network should be configured in such a way that the network topology requires minimum development cost. In this article, we implement two greedy algorithms to solve a computer network topology using the minimum spanning tree problem. The results of the two algorithms show consistency. A comparative analysis of time complexity is explained.

In this project we consider the problem of designing a small network of computers in an office [1]. The goal is to generate the network in such a way that all the computers in the office are connected to each other by building Ethernet lines. Ethernet is a local area network (LAN) technology that can be used as a protocol to connect multiple systems over the LAN network connection. Besides LAN, it is also used in metropolitan area network (MAN), wide area network (WAN), etc. Each possible link (the connection between two computers in the office) and the associated construction cost is shown in the following figure [1]:

Network of potential offices

Construction costs are mainly decided based on the distance of the links and some restrictions due to physical boundaries. We take advantage of a minimum spanning tree of the network to study the minimum cost of connecting all computers.

The goal of this project is to implement a greedy algorithm to find the minimum spanning tree. We will implement standard greedy algorithms such as Kruskal’s minimum spanning tree, Prim’s minimum spanning tree, and finally compare the performance of the algorithms taking time complexity into account.

he greedy algorithm is an algorithm widely used in optimization problems. The following greedy algorithm solves the problem heuristically by making locally optimal choices at each step of the problem. Using the local optimal approach, it studies a global solution for the problem. Greedy algorithms do not guarantee a global solution but generate a locally optimal solution that approximates a global solution with a reasonable amount of time. Greedy algorithms do quite well in some problems, such as Prim’s algorithm and Kruskal’s algorithm to find the minimum spanning tree, Huffman coding to compress the data, or Dijkstra’s algorithm to find the shortest path (distance) from a vertex to all other vertices in a graph. To solve our computer network topology problem, we implemented the algorithms of Prim and Kruskal to study the minimum spanning tree for a weighted network.

rim algorithm is one of the famous greedy algorithms that finds the minimum spanning tree of a graph. A graph is fed into the algorithm and it finds the minimum spanning tree, i.e. finds a subset of the edges of this graph that form a tree including all vertices and has minimum weights among all generated trees. The steps of Prim’s algorithms are followed:

  1. Create a set (mstSet) to keep track of vertices already included in MST
  2. Assign a key value to all vertices of the input graph
  3. Initialize all key values ​​as INFINITE
  4. Set the key value to 0 for the first vertex so that it is selected first
  5. While mstSet does not include all vertices — 5a. Choose a vertex you who is not in mstSet and has a minimum key value. — 5b. Include you at mstSet — 5c. Update the key value of all adjacent vertices of you. To update key values, loop through all adjacent vertices. For each adjacent vertex vif the edge weight UV is less than the previous key value of vupdate key value as weight of UV

Ruskal’s algorithm is another greedy algorithm that finds the minimum spanning tree of a connected undirected graph. He finds an edge of the lowest possible weight that connects any two trees in the forest. It follows the following steps:

  1. Sort all edges in non-descending order of their edges
  2. Choose the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not created, include the edge or delete it.
  3. Repeat step 2 until there are (v-1) edges in the spanning tree

We implement both algorithms on our dataset. An adjacency matrix is ​​formed from the given network and it is used as input for both algorithms. The adjacency matrix is ​​shown in the following figure.

The results of using the two algorithms are listed below in prim’s algorithm in Table 1 and in Kruskal’s algorithm. Figure 2 shows the minimum spanning tree.

Both algorithms produce identical results when the minimum cost for the computer network is 13. Moreover, the minimum spanning tree generated is also the same for both methods.

In this paper, we implement two greedy algorithms to solve a computer network topology using a minimum spanning tree problem. The results of the two algorithms show consistency. We explored that the two greedy algorithms produce identical results.

Reference

[1] https://documentation.sas.com/?docsetId=casmopt&docsetTarget=casmopt_networksolver_examples05.htm&docsetVersion=8.2&locale=en


Source link