Algorithmic Aspects of Telecommunications Networks Implementation of a Basic Network Design Model Project 1 Nazim Uddin Ahmed [email protected] 1 Introduction: This project is an implementation of the basic network design model that is presented in the lecture note entitled “An Application to Network Design”. The goal of this project is to find the capacity of each link in a given network where the demand (bij) from one node to another node is given. Another goal of the project is to find the total cost and density of the network using the given unit cost values of the potential links (aij). Finally the project output will show how total cost and density of the network depends on k. We need to create software that will fulfill the project requirement. The software will receive the number of nodes (N) as user input. For each node pair, it will then generate unit cost value and demand matrix for different values of k (from 3 to 15). For each value of k, the program will generate different total cost and density of the network. Finally the program will show graphically how the total cost and density of the network depends of different values of k. k’s value places a significance role in this program. For every node i, there will be k low cost links going out of the node, the others will have large cost. The program will use the shortest path algorithm to avoid the high cost links, so it effectively means that by using different value of k, we can limit the number of links that go out of the node which will eventually limit the network density.Chapter 2 Software Design and Algorithm: 2.1 Simulation Tool: MATLAB is used in this software as programming language/simulation tool. This simulation tool is used for its built in capabilities of calculating shortest path and graph drawing. As MATLAB is well known for its reliability and it can easily plot graphs for any weight matrix, we can use it to fulfill our purpose efficiently. 2.2 Simulation Design: The program used the work flow process mentioned in figure 2.1. 2.3 Program Input: This program will receive number of nodes (N) as user input, traffic demand values (bij) between pairs of nodes and unit cost values for the potential links (aij). In order to simulate the program, we will generate aij and bij for different values of k where k is a parameter that will change in the experiment. The program will run with k = 3, 4, 5… 15. For each run new generated aij and bij will be used. In each run, bij can take independent random integers from the range [0, 1, 2, 3, 4]. For generating aij values, k different random indices (j1, j2… jk) will be generated and set aij1 = aij2 = aij3 = … = aijk = 1 and set aij = 400 whenever j ≠ j1 ≠… jk.Figure 2.1: Work Flow Process2.4 Algorithm: In this simulation, first we generate the graph using the unit cost (aij) as weight matrix and N as number of nodes. In order to generate directed graph, start node matrix, end node matrix and link cost is being calculated. Then call sparse function which will give a directed graph. Now from each node i to any other node j, call graphshortestpath function which will return the shortest path from node i to node j. For each link (k, l) in the shortest path, update the capacity for link (k, l). New capacity of the link will be old capacity of that link plus demand from node i to j. new capacity[k ,l] = old capacity[k, l] + b[i, j] Using each link capacity and cost, calculate the total cost of the network: new TotalCost = old TotalCost + capacity[i, j]*a[i, j] In order to calculate the density of the network, first calculate number of edges where capacity[i, j] is not zero: new numOfNonZeroCapacityEdges = old numOfNonZeroCapacityEdges + 1 density = numOfNonZeroCapacityEdges / N*(N-1) Now compare the total cost where costs are calculated in two different ways: costFromLink = costFromLink + a[i, j]*capacity[i, j]; costFromPath = costFromPath + weightDist[i, j]*b[i, j]; Both the total cost should be same. Finally the program plots total cost and density graphs for different values of k.Figure 2.2: Data Flow ProcessChapter 3 Results and Observations: 3.1 Capacity: The software will generate different capacity of the links for different values of k. In order to explain the situation and show it nicely in graph, I used small value of N (=10) and k (=3) so that all the link capacity and node is clearly visible. Figure 3.1: Capacity graph for N = 10 and K = 3It is possible to show this graph for large value of N. As N is a user input, user can easily draw the graph for any value of N. Figure 3.2: Capacity graph for N = 40 and K = 3Showing the actual unit cost, demand and corresponding capacity of the links is also a nice visual representation of the graph. For nice presentation, I choose small value of N and k. But it is possible to draw the graph using this software for any value of N and k. Figure 3.3: Unit cost graph for N = 5 and K = 2Figure 3.4: Demand graph for N = 5 and K = 2 Figure 3.5: Capacity graph for N = 5 and K = 23.2 K vs Total Cost: In the program, for each value of k = 3, 4, 5 …, 15, we got the total cost of the network for each new generated random aij and bij parameters. For every node i there are k low cost links going out of the node. For small value of k, there will be less low cost links going out of the node. So, if we try to find the shortest path from node i to all other nodes, then those low cost links will be used more and capacity of those links will be increased. In order to get the total cost of the network, we used these link capacity and link unit costs. Link unit cost is fixed. So the total cost is actually depends on link capacity. If capacity increases, total cost will increase. For large value of k, there will be lower cost outgoing links for each node i. So, each link will be used less for carrying traffic. That will impact the capacity of the links. So, capacity of the links will be less compare to small value of k and eventually total cost of the network will be less. Figure 3.6: Change of total cost for different values of KIn the figure 3.6, we also can see this thing. While k is 3, total cost of the network is almost 19,000. When k is increasing, total cost is decreasing and for k = 15, total cost decreases to almost 5000. So, we can justify our explanation for this experiment. In the figure, we see
View Full Document
Unlocking...