A network consists of a central hub router, with links (spokes) to a set of routers at outlying sites. A network designer is trying to choose which routing protocol to deploy. (i) Illustrate the operation of Link State and Distance Vector routing algorithms over this simple topology. [6 marks] (ii) What are the overall packet counts for each protocol in the whole network from turning the system on until all routers know where all destinations are? [2 marks] (b) Another network consists of a set of sites with routers, connected in a long line. (i) Illustrate the operation of Distance Vector routing when one link at one end fails. [6 marks] (ii) What are two common techniques to improve the performance of the protocol in these scenarios? [4 marks] (c) Why do path vector protocols not have this problem? [2 marks] 5 (TURN OVER)

REG is a unit-delay register initialising to some unknown value, the combinational devices TEST and STEP compute the functions test (which returns a Boolean) and step, respectively, and MUX is a multiplexer. These are specified by: REG(in, out) = ?t. out(t+1) = in t TEST(in, out) = ?t. out t = test(in t) STEP(in, out) = ?t. out t = step(in t) MUX(select, in1, in2, out) = ?t. out t = if select t then in1 t else in2 t These components can be used to design a device, INIT, that attempts to initialise to an output value satisfying test by applying step zero or more times to the initial value of REG (i.e. the value output at time 0) until test yields T. INIT indicates that initialisation has succeeded by outputting T on the output line done; it simultaneously outputs the value found by repeatedly applying step on the output line out. Formally, INIT is specified by two properties: INIT(done, out) ? ?t. done t = test(out t) INIT(done, out) ? ?t. out(t+1) = if done t then out t else step(out t) (a) Give a design for INIT in the form of a circuit diagram using REG, TEST, STEP and MUX. [6 marks] (b) Carefully explain why your design meets its specification. [4 marks] (c) Write down a formal model of your design. [4 marks] (d) Outline how you could prove that your design meets its specification (you need not give a detailed proof, but you should provide evidence that you know how to produce such a proof, and what the main steps would be).

A hardware FIFO is a type of memory component. It has two ports, one for reading and one for writing, and implements the first-in/first-out queuing discipline. (a) Why is flow control important when using FIFOs and what net-level signals must a hardware FIFO accept and generate for proper handshaking? [3 marks] (b) Give a suitable signature of such a FIFO component in either a Register Transfer or Transactional Level Modelling language (RTL or TLM). Explain in detail how the handshaking works with your signature. Comment on how it would differ for the other signature. Note: the signature of a component is its interface type, where method bodies or implementation logic are missing, such as (input [6:0] foo, output bar) in Verilog. [6 marks] (c) In an embedded system, a FIFO is to be used for passing messages, in one direction, between a pair of processors that share no memory but which each have memory-mapped access to one of the FIFO's ports. An interrupt-driven device driver would offer no advantage in the target application. Using assembler, C or pseudocode, give either the read or write methods of a polling device driver and explain how the other would differ. [5 marks] (d) An alternative approach for passing data between the pair of processors is to use shared memory. You are asked to predict the performance and energy use of the two designs in advance of making the hardware. Discuss the role a TLM model might have and whether there is a better alternative model or technique. [6 marks] 12 CST2.2017.8.13 13 Topical Issues A key challenge for autonomous vehicles is the classification of nearby objects, particularly in urban environments. For example, understanding whether an object is a static litter bin or a child about to cross the road should alter a vehicle's behaviour. (a) As a first step many autonomous vehicles form a point cloud representing their local environment. Explain how this is done using lidar sensors. Your explanation should cover the pulsed and continuous-wave variants and the resolution of range ambiguities. [6 marks] (b) One approach to classifying objects is for the vehicle to match against a detailed world model containing the positions of all street furniture. Discuss the advantages and disadvantages of this approach and describe how such a large model could be built. [8 marks] (c) An alternative IoT-based approach has all street furniture tagged using Bluetooth Low Energy beacons. Suggest how a vehicle could reliably associate beacon broadcasts with point-cloud objects. How could your solution be improved if a cluster of nearby vehicles were able to communicate? [6 marks] 13 (TURN OVER) CST2.2017.8.14 14 Topics in Concurrency Recall that basic Petri nets can be considered to be general Petri nets where all multiplicities (including the capacity of conditions) are less than or equal to 1, so the initial marking and pre- and post-conditions form sets. (a) Give the token game for basic Petri nets, specifiying when M e ?? M0 . [3 marks] (b) Draw basic Petri nets to illustrate the concepts of forwards conflict, backwards conflict and independence (also called concurrency). [4 marks]

(a) (i) Explain the difference with respect to polymorphic occurrences of variables between the way let-bound and lambda-bound variables are treated in languages featuring ML-style polymorphism. Illustrate your answer by explaining why in the Mini-ML language one of the two expressions ?g (let f = ?x (let u = g x in x) in f f) let f = ?x (let u = x in x) in f f is typeable and the other is not. As part of your answer you should define what it means for a type to be a specialisation of a type scheme and give the Mini-ML typing rules for variables, function abstractions, function application and let-expressions. [14 marks] (ii) What property of the type system is lost if one attempts to treat polymorphic occurrences of lambda-bound variables in the same way as let-bound ones? [1 mark] (b) Give the typing rules for expressions associated with ML-style reference types, namely reference creation ref M, reference look-up !M and assignment M :=M0 expressions. What is the value-restriction that is imposed on the typing rule for let-expressions in the presence of these forms of expression and what is its purpose?

: Write Java program to read a character and push the character on to the stack a Java program to read two data items and print their sum, difference, product, and quotient.

(a) Carefully state and prove Tarski's fixed-point theorem for the maximum fixed point ?X.?(X) of a monotonic function ? on the powerset P(A) of a set A. [6 marks] (b) Let S ? A. Prove S ? ?X.?(X) ? S ? ?(?X.(S ? ?(X))) [7 marks] (c) Describe the syntax and semantics of the modal mu-calculus. Describe a model checking algorithm which uses the fact in part (b) to decide whether an assertion of the modal mu-calculus holds of a state in a finite transition system.

1-Write an evaluation for Java, using the criteria described in chapter 1. (at least 10 lines) 2-Is the following grammar ambiguous? Why ? a b blb a la 3-Write a denotational semantics mapping function for java while loop 4-Compute the weakest precondition for the following statements A. B. x = 4 * (2*x+y); y = 4 *x-1 {y> 7} if (x ==y) y=3*x+ 3 else y= 2 * x; {y > 2} 5-Write an EBNF rules that describes the following while statement of Java. Then, write the recursive-descent subprogram in Java for the EBNF rule. Please summit your source code and a screen shot of the parsing of the following exam- ples. do { if (number % 2 == 0 ) even ++; number=number+1; } while (number