Friday 20 December 2019 13.00 - 14.30 (90 minutes) DEGREES of MSci, MEng, BEng, BSc, MA and MA (Social Sciences) NETWORKS AND OPERATING SYSTEMS ESSENTIALS 2 Answer all 2 questions This examination paper is worth a total of 60 marks. The use of calculators is not permitted in this examination. INSTRUCTIONS TO INVIGILATORS: Please collect all exam question papers and exam answer scripts and retain for school to collect. Candidates must not remove exam question papers. 1. Networked Systems (a) Describe what is meant by a best-effort service and explain why the Internet offers such a service. [4] Solution: (Bookwork) By best-effort service we mean a network service that provides no guarantees regarding delivery of the messages that it handles. More specifically, message may be dropped, reordered, duplicated, delayed, or corrupted, and the network service will not attempt to retransmit/reorder affected messages. [3 marks] By removing the requirement for the network (Internet) to provide such guarantees, it can be made to operate more efficiently (smaller header hence less space overhead, less processing hence faster routing/forwarding, etc.). [1 mark] (b) The Open Systems Interconnection (OSI) reference model provides a standard layered system model. Name the seven layers used in the OSI reference model, in order from lowest (closest to hardware) to highest (closest to the user), and explain what this layering means for the implementers of each layer. [6] Solution: (Bookwork) The layers of the OSI reference model are: Physical, Data link, Network, Transport, Session, Presentation, Application [4 marks: 0.5 mark for each layer, 0.5 mark for correct order]. Every layer exports/provides a service to the layer above it, implemented using the services exported/provided by the layer below it. This structured design greatly reduces complexity, as one only needs to worry about the interface provided by the layer below, and the interface expected by the layer above. [2 marks] (c) Consider the network graph pictured below. Nodes represent devices on the network, edges represent links and the numbers by the edges represent the cost of forwarding a message across that link. Assume that the network is using a Distance Vector protocol, that all message exchanges happen at the beginning of every round of the protocol, and that hosts update their state after they’ve received all messages destined to them in the current round. Show the initial routing state of all nodes in the network, and their routing state after every round of the protocol. In your answer please show the routing table entries (distance/next hop) of all nodes in the network (i.e., a 5 x 5 matrix), for each iteration of the algorithm. Your answer should include 3 such matrices, including the one for the original state (i.e., nodes only know of themselves and their 1-hop neighbours). 1 CONTINUED OVERLEAF 41 5 2 2 A B C D E 1 [8] Solution: (Bookwork for knowledge of the algorithm, Problem solving for computation of the solution) Step 1 (initialisation) A B C D E A 0/- 4/B 5/C 2/D ∞ B 4/A 0/- 2/C ∞ ∞ C 5/A 2/B 0/- ∞ 1/E D 2/A ∞ ∞ 0/- 1/E E ∞ ∞ 1/C 1/D 0/- 2 marks for correctly filling in the 1-hop neighbourhood. Step 2 A B C D E A 0/- 4/B 5/C 2/D 3/D B 4/A 0/- 2/C 6/A 3/C C 5/A 2/B 0/- 2/E 1/E D 2/A 6/A 2/E 0/- 1/E E 3/D 3/C 1/C 1/D 0/- 4 marks, 0.5 for each update. Step 3 A B C D E A 0/- 4/B 4/D 2/D 3/D B 4/A 0/- 2/C 4/C 3/C C 4/E 2/B 0/- 2/E 1/E D 2/A 4/E 2/E 0/- 1/E E 3/D 3/C 1/C 1/D 0/- 2 marks, 0.5 for each update. 2 CONTINUED OVERLEAF (d) At the network layer, the Internet is a connectionless best-effort packet network. On the other hand, the traditional telephone network provides a reliable circuit switched service. Discuss what are the advantages and disadvantages of these two approaches to network design. [6] Solution: (Bookwork/synthesis) Packet switching achieves more efficient use of the network by allowing links to be used by multiple pairs of communicating entities at the same time (1 mark). Allows for easier handling of errors, e.g. by forwarding a packet along a different route (1 mark). However, it doesn’t provide any guarantees regarding the available network capacity (1 mark), the order in which packets will arrive at their destination (1 mark), or whether packets will arrive at all (1 mark). Last but not least, the store-and-forward nature of packet switching introduces transmission delays (1 mark). Marks may be awarded for other reasons, as long as they are valid and properly worded. (e) You have written a basic server program in the first assessed exercise for this course, using the Python programming language and the Berkeley Sockets API. List the basic steps required to set up a server socket, receive a connection and serve it to completion. You can provide either code or a description of the function of the respective code. [6] Solution: (Bookwork/problem solving) • Create socket endpoint: srv sock = socket.socket(socket.AF INET, socket.SOCK STREAM) • Bind socket to address and port: srv sock.bind((ip, port)) • Set size of backlog for connection requests: srv sock.listen(5) • Block till a connection request arrives/is in the queue, return with a new socket variable connected to the client’s socket: cli sock, cli addr = srv sock.accept() • Serve the request via reading/writing to the new socket. • Close the connected socket on completing serving this request: cli sock.close() Note: it’s cli sock that is closed as the server socket (srv sock) remains open to accept further requests. 1 mark for each step. (f) Explain what important problem is solved by public-key cryptography that is not solved by symmetric cryptography. Briefly explain why and how public-key cryptography solves this problem. [4] 3 CONTINUED OVERLEAF Solution: (Bookwork) In symmetric cryptography, both communicating sides need to use the same secret/key for encrypting and decrypting the exchanged date. Said key needs to be exchanged via out-of-bounds means, as encrypted communication is not possible otherwise. (2 marks) Public-key cryptography solves this problem by alleviating the need for a predefined key or out-of-bounds communication. Each side shares openly its public key, while keeping their private key a secret. The sender encrypts their data using the public key of the receiver, while the receiver decrypts it using their private key. (2 marks) 2. Operating Systems (a) Consider a cache with 3 slots and the following stream of requests: C, D, A, B, D, A, C, B, C, D, A Give the contents of the cache after each request and indicate cache misses, when the cache is using (i) the LRU algorithm (5 marks) and (ii) the LFU algorithm (5 marks). Show your work (i.e., recentness order for LRU, frequency of access for LFU). [10] Solution: (Bookwork for knowledge of the algorithms, Problem solving otherwise) LRU: C D A B D A C B C D A C (0) C (0) C (0) B (3) B (3) B (3) C (6) C (6) C (8) C (8) C (8) – D (1) D (1) D (1) D (4) D (4) D (4) B (7) B (7) B (7) A (10) – – A (2) A (2) A (2) A (5) A (5) A (5) A (5) D (9) D (9) M M M M M M M M LFU: C D A B D A C B C D A C (1) C (1) C (1) B (1) B (1) B (1) C (1) B (1) C (1) C (1) C (1) – D (1) D (1) D (1) D (2) D (2) D (2) D (2) D (2) D (3) D (3) – – A (1) A (1) A (1) A (2) A (2) A (2) A (2) A (2) A (3) M M M M M M M 5 marks for each algorithm (divided per row/access). No penalty will be applied if the student does not use LRU as the fallback for access #4 in the LFU case, as long as the remainder of the solution is correct. 4 CONTINUED OVERLEAF (b) Consider the following set of processes: Process ID Arrival Time Burst Time Priority P1 0 5 2 P2 1 2 3 P3 1 3 1 P4 3 5 2 P5 6 1 1 Show the scheduling order and execution times of individual process, and compute the turnaround time of each process and the average waiting time over all processes, for each of the following scheduling algorithms: FCFS, SJF, non-preemptive priority (a smaller priority number implies a higher priority), and pre-emptive RR (quantum = 3). [16] Solution: (Bookwork for knowledge of algorithms, problem solving otherwise) The solution below also shows the line of thought. Students can provide the full tables or just the parts that are requested by the question (as discussed below). FCFS: Time point Processes in READY state Scheduled process Exec. time 0 P1 P1 0-5 5 P2,P3,P4 P2 5-7 7 P3,P4,P5 P3 7-10 10 P4,P5 P4 10-15 15 P5 P5 15-16 P1 P2 P3 P4 P5 Turnaround times 5-0 = 5 7-1 = 6 10-1 = 9 15-3 = 12 16-6 = 10 Waiting times 0-0 = 0 5-1 = 4 7-1 = 6 10-3 = 7 15 - 6 = 9 Average waiting time: 26/5 = 5.2 SJF: Time point Processes in READY state Scheduled process Exec. time 0 P1 P1 0-5 5 P2,P3,P4 P2 5-7 7 P3,P4,P5 P5 7-8 8 P3,P4 P3 8-11 11 P4 P4 11-16 P1 P2 P3 P4 P5 Turnaround times 5-0 = 5 7-1 = 6 11-1 = 10 16-3 = 13 8-6 = 2 Waiting times 0-0 = 0 5-1 = 4 8-1 = 7 11-3 = 8 7-6 = 1 5 CONTINUED OVERLEAF Average waiting time: 20/5 = 4 Non-preemptive priority: Time point Processes in READY state Scheduled process Exec. time 0 P1 P1 0-5 5 P2,P3,P4 P3 5-8 8 P2,P4,P5 P5 8-9 9 P2,P4 P4 9-14 14 P2 P2 14-16 P1 P2 P3 P4 P5 Turnaround times 5-0 = 5 16-1 = 15 8-1 = 7 14-3 = 11 9-6 = 3 Waiting times 0-0 = 0 14-1 = 13 5-1 = 4 9-3 = 6 8-6 = 2 Average waiting time: 25/5 = 5 Preemptive RR (quantum = 3): Time point Processes in READY state Scheduled process Exec. time 0 P1(5) P1 0-3 3 P2(2),P3(3),P4(5),P1(2) P2 3-5 5 P3(3),P4(5),P1(2) P3 5-8 8 P4(5),P1(2),P5(1) P4 8-11 11 P1(2),P5(1),P4(2) P1 11-13 13 P5(1),P4(2) P5 13-14 14 P4(2) P4 14-16 P1 P2 P3 P4 P5 Turnaround times 13-0 = 13 5-1 = 4 8-1 = 7 16-3 = 13 14-6 = 8 Waiting times 0-0 + 11-3 = 8 3-1 = 2 5-1 = 4 8-3 + 14-11 = 8 13-6 = 7 Average waiting time: 29/5 = 5.8 [2 marks for scheduling order & execution times (last two columns of large tables), 1 mark for turnaround times, 1 mark for average waiting time, for each of the algorithms] 6 END OF QUESTION PAPER
欢迎咨询51作业君
