Your report is worth 14 marks. Your report will be evaluated as follows:
 Description of the data structure used to create the internal representation of the network
topology: 2 marks

The data structure utilised in order to internally represent the given network topology was a bidirectional weighted graph. This was achieved through an adjacency list in the Graph interface. Each node in the graph corresponded to a supposed ‘router’ in the network, keeping hold of each of the nodes/routers which it was connected/linked to in a List of Edges - which corresponded to each connection between two routers.

This Graph interface allowed for the creation of a graph, as well as the calculation of the path through the graph for each virtual request through Dijkstra’s algorithm.

The Edge class stored all necessary information about each link on the network. This included the given capacity of each link, as well as the propagation delay.

Furthermore, each Edge class stored the start and end times for which these links were occupied. The choice of data structure for storing this data was TreeMap, in order to retain order of the keys of the startTimes and endTimes.

 Tabulated comparison of the performance metrics of the 3 routing protocols for the
provided topology and workload files: 2 marks





 Explanation of the performance results observed: 2 marks

In a circuit request, all packets are serviced as part of the one request, whereas in a packet switching network, each packet is individually serviced. This is apparent in the difference in “number of virtual requests” metric between both network schemes.

As a result, the percentage of successfully routed packets for every instance of the Packet Scheme is greater than those for Circuit Scheme. This is because in a Circuit Network, for each packet being serviced as part of the one request, the same path is utilised. In contrast, in a Packet Switching Network, each packet has the freedom to select/be routed down a path which is available - increasing the likelihood of that packet being successfully routed to it’s destination.

In terms of the three different types of routing protocols, the differences are apparent in three of the metrics - the average hops , the propagation delay, and the amount of successfully routed packets.

In the SHP routing protocol, since the cost of each link is uniform (set to 1), the shortest path is always computed. This however results in the percentage of blocked requests being greater, as the path calculation does not take the availability of links into account. In addition, it also does not take the propagation delay of links into account, which means that they are moderately high for most of the algorithm. However, since the shortest path is being computed at all times, this mitigates the propagation delay to a certain extent, making it the second highest.

In the SDP routing protocol, the cost of each link is calculated based on the propagation delay. By minimising the delay, the average propagation delay of the circuit request is the least amount amongst all routing protocols. Furthermore, the percentage of blocked packets is lower than SHP since the calculation of paths with minimal propagation delay frees up links faster - making the network more readily available. However, the number of hops is maximal amongst all routing protocols, since the length of the paths are not being taken into account, but rather the time it takes for these paths to be traversed.

In the LLP routing protocol, the cost of each link is calculated based on the current capacity of the links in the path. This optimises performance for the successful packet metric, as less packets are dropped due to the nature of the path calculated as being the least loaded. This however means that similar to SDP, the average hops per circuit request is similarly not minimised due to no consideration of the length of the path. This is however mitigated through the nature of this cost calculation since less links/hops lead to a higher chance of network availability. However the lack of any consideration of any propagation delay means that the average propagation delay of the circuit is the maximum of any of the routing protocols.

 Plots for performance evaluation of the virtual packet network: 4 marks



 Explanation of the plots: 4 marks