Network Algorithms

For the graph below, apply the Dijkstra and Distance Vector algorithms. Use the digits of your ID number which is 01024977 , to give you the weight of the different arcs. Example, for someone with the number 12345678, W1 will be 1, W2 will be 2 and so on. A zero should count as 10 and any alpha character (e.g. "D") should count as 5. Note that 2 arcs are already weighted for you. For both algorithms you should give: a) An explanation of how each algorithm works; b) A routing table for node C for each algorithm; for Dijkstra, show entries for each iteration of the algorithm. c) The conditions necessary for each algorithm to complete; d) For Dijkstra, the number of iterations needed for the algorithm to complete. Those who want to get an A*: explain how many iterations each algorithm will make if a network graph has n nodes and m arcs. 1. The Role of the Transport Layer · Why does the Transport Layer have to provide a Reliable Transport Service (RTS) when the Data Link Layer already does so? · What guarantees regarding reliability does the Transport Layer provide to the Application Layer? Which applications require these guarantees? 2. The Functioning of RTS · If we are using a channel where data corruptions can occur to packets, what mechanisms do we need to handle these and how do they operate? · What happens if our ACKs and NAKs are corrupted? Explain the mechanisms to cope with this. · What if we now introduce the possibility of packet loss? What new mechanisms are required and how do they operate? · What problem does the need to await acknowledgements introduce into our connection? Name the mechanism for dealing with this and describe briefly how the two principle variants of it work. 3. Making RTS More Efficient Given a MSS of 500 bytes and a RTT of 45 milliseconds, how long would it take to transmit a file 106 bytes long over a 1Gbps connection using a stop-and-wait (alternating-bit) protocol? Now, suppose we use a pipelined protocol with a window size of 30. How long does it take now? What is the efficiency of the new connection, expressed as a percentage. : The Data Link Layer 4. Explain the Algorithm of Error Tolerance that is required to realise reliable frame delivery over a network. Describe each step of the algorithm and detail the options used to realise each of these steps. ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Complete ownership and distribution copyrights to all work purchased. For the graph below, apply the Dijkstra and Distance Vector algorithms. Use the digits of your ID number which is 01024977 , to give you the weight of the different arcs. Example, for someone with the number 12345678, W1 will be 1, W2 will be 2 and so on. A zero should count as 10 and any alpha character (e.g. "D") should count as 5. Note that 2 arcs are already weighted for you. For both algorithms you should give: a) An explanation of how each algorithm works; b) A routing table for node C for each algorithm; for Dijkstra, show entries for each iteration of the algorithm. c) The conditions necessary for each algorithm to complete; d) For Dijkstra, the number of iterations needed for the algorithm to complete. Those who want to get an A*: explain how many iterations each algorithm will make if a network graph has n nodes and m arcs. 1. The Role of the Transport Layer · Why does the Transport Layer have to provide a Reliable Transport Service (RTS) when the Data Link Layer already does so? · What guarantees regarding reliability does the Transport Layer provide to the Application Layer? Which applications require these guarantees? 2. The Functioning of RTS · If we are using a channel where data corruptions can occur to packets, what mechanisms do we need to handle these and how do they operate? · What happens if our ACKs and NAKs are corrupted? Explain the mechanisms to cope with this. · What if we now introduce the possibility of packet loss? What new mechanisms are required and how do they operate? · What problem does the need to await acknowledgements introduce into our connection? Name the mechanism for dealing with this and describe briefly how the two principle variants of it work. 3. Making RTS More Efficient Given a MSS of 500 bytes and a RTT of 45 milliseconds, how long would it take to transmit a file 106 bytes long over a 1Gbps connection using a stop-and-wait (alternating-bit) protocol? Now, suppose we use a pipelined protocol with a window size of 30. How long does it take now? What is the efficiency of the new connection, expressed as a percentage. : The Data Link Layer 4. Explain the Algorithm of Error Tolerance that is required to realise reliable frame delivery over a network. Describe each step of the algorithm and detail the options used to realise each of these steps. 5. How do the Transport Layer and Data Link Layer differ in the way they use redundancy as a means to increase the reliability of transmission? 6. Which MAC protocol does Ethernet use? Give a brief description of how this protocol works. 10 Marks Marking scheme for problem 5 1.1. Classification of Redundancy Types - 1; 1.2. Steps of algorithms to realised error tolerance - 1; 1.3. Comments for each step - 2; 2.1. Redundancy types applied for AET at the Transport Layer - 1; 2.2. Redundancy types applied for AET at the Data Link Layer - 1; 2.3. Analysis of pros and cons for each solution - 1; 3.1. MAC algorithms - classification - 1; 3.2. Ethernet MAC algorithm, its features - 1; 3.3. Critics of the algorithm applied - 1; ## Platform MS WORD