Hi, I've looked through and corrected all of your exams. This year's students have exceeded all of my expectations! It seems like many of you will get a grade 5 in the course. Below is a list of questions asked in the exam, together with how I graded your corresponding answers. Instead of writing the comments on each of your papers, I've gathered my comments in this document, together with some simple rules on how I thought the points should be distributed. Remember, these rules are a guideline, I havent followed them to the letter. Cheers, and thanks for this period Mattias $Id: rattningsmall.20040309,v 1.7 2004/03/18 15:37:54 fimblo Exp $ ************************************************************ Rättningsmall tenta 20040309 1a) What is a routing table? (1p) Contains a list of routes to networksand next hops ½p Used to decide where to forward packets. ½p 1b) What is a routing protocol? (2p) A routing protocol is a set of rules which enable routers to share reachability information with each other. Communication protocol between routers 1p reachability information 1p 1c) What is route aggregation? (1p) It makes combining contiguous prefixes into one advertised prefix possible. 1p To re-word it: It makes possible the announcing one aggregated prefix instead of several contiguous prefixes. 1p Example is ok, as long as the "why do we do this" part is included. (note: contiguous prefixes cannot always be aggregated. Why? Well, thats not covered here) (note2: aggregating routes is good because it makes the number of routes you advertise lower) 1d) What is Administrative Distance? (2p) It allows the router to choose the best path when two or more routing protocols announce that they can reach the given network. 1p All routing protocols are given a metric measuring the administrative distance to the truth (low=good). These are compared to choose the "most believable route". 1p 1e) What is a static route, and when can it be useful? (2p) A static route is manually entered in the router ½p A static route is static. (i.e does not adapt if the topology changes) ½p o Good on very small networks o good for setting default routes o good on very stable networks 1p for any of the above, and for other imaginative answers. 1f) Main idea behine Distance Vector protocols? (2p) Name 2 pros and 2 cons. (4p) Routing table (actually a list of Distance Vectors) is sent to all neighbours periodically. This info is digested according to special rules (distributed Bellman-Ford), and resulting routing table is sent to all neighbours. Thus topology info can be (and is often) lost. routing table sent to neighbours, who digest it: 1p rules applied to update routing table: 1p Pros: (any of following 1p, max 2p) o Relatively simple to implement o Low overhead (mem, cpu, etc) o low bandwidth usage if # of networks is low o ... and more Cons: (any of following 1p, max 2p) o Slow convergence o Count-to-infinity o high bandwidth usage if # of nets is high o routing domain diameter set to infinity size o ... and more 1g) Main idea behind Link State protocols? (2p) Name 2 pros and 2 cons. (4p) Every router floods local topology to all other routers in routing domain. This raw material is then used to build a routing table on each router using an SPF algorithm. Note: all routers have same topology info. Raw material is unmodified at every hop, flooded: 1p routing table built after-the-fact: 1p Pros: (any of following 1p, max 2p) o Fast convergence o support for different metrics o avoids loops! o supports partitioning of routing domain o ... and more Cons: (any of following 1p, max 2p) o Larger specification -> harder to implement -> not as many implementations & can be hard to find bugs o lots of overhead (mem + cpu, etc) o ... and more ************************************************************ 2) RIP 2a) Two differences between rip v1 and v2 (2p) (any of following 1p, max 2p) o v2 supports classless interdomain routing o v2 supports simple authentication o v2 supports several rip processes o v2 lets you add an AS number into your DV o v1 was broadcast, v2 is multicast o next_hop field added in v2 2b) count to infinity (CTI) i. what is it, give simple example (2p) CTI is a deception process where there is a poisoned route which propagates its way in updates between routers implementing the distributed Bellman-Ford algorithm, its cost incremented by one every time it is sent on to the next router. This continues until inf is reached. 1p (Note: A packet looping is not CTI. This is a consequence) (Note2: in the generic description of DV, inf is NOT 16. Its really infinity, so the process continues... forever) A very general (but correct!) example is enough for 1p. (Note: due to ambiguous question, a detailed step-by-step but no definition gives 2p as well) ii. Split horizon (4p) If you use split horizon you don't advertize routes back to where they came from. 2p (note: By splitting the horizon you treat the neighbours on one side of the horizon and the other differently.) Example of when it works: loopless topology (tree) 1p Example of when it sucks: loopful topology 1p iii. Two other measures against CTI (4p) (Mentioning a method: ½p, details 1½p. max 4p) Triggered updates ½ When a distance vector changes or is introduced, the router sends this info along with other modified entries to its neighbours immediately. 1½p inf set to 16. ½ Makes counting to infinity much faster, but makes diameter of RIP domain max 15 hops 1½p Split horizon with poisoned reverse ½ Like plain split horizon, but here you send a DV back with a metric of 16 (unreachable). This lets you count to infinity in one step. 1½p c) Rips timers, Cisco-wise (8p) one point for mentioning each type, one point for a decent description. ******************************************************************************** 3) OSPF *** Please note that in the tenta I specifically asked the student to describe the LSA fields. Students who have not done this (instead described the LSAs (incorrectly) in words, or skipped many fields) have received a reduced total score. How much I reduced it depends on each student. 3a) Describe LSDB in Router G (10p) 1 point to understand that priority 0 means no DR/BDR 1 additional point if student understands that no DR means no exchanging of OSPF packets other than HELLO, so no network LSA is created, no p2p is created either (full mesh=n² problem) ½ point for each correct Router LSA Link i.e. total 6 points 2 points for correct network lsa -1 if the student incorrectly says that G will have LSAs originating from A and/or B G's LSDB ŻŻŻŻŻŻŻŻ LSTYPE LS ID ADV RT PAYLOAD # links, LINK TYPE, LINK ID, LINK DATA C 1 1.2.3.3 1.2.3.3 3 stub 1.2.3.0 255.255.255.224 stub 1.2.1.0 255.255.255.252 p2p 2.4.1.2 1.2.1.1 G 1 2.4.1.2 2.4.1.2 4 stub 1.2.1.0 255.255.255.252 p2p 1.2.3.3 1.2.1.2 stub 2.4.1.0 255.255.255.252 p2p 2.4.1.1 2.4.1.2 D 1 2.3.4.1 2.3.4.1 1 transit 2.3.4.1 2.3.4.1 E 1 2.3.4.2 2.3.4.2 1 transit 2.3.4.1 2.3.4.2 F 1 2.4.1.1 2.4.1.1 3 transit 2.3.4.1 2.3.4.3 stub 2.4.1.0 255.255.255.252 p2p 2.4.1.2 2.4.1.1 D 2 2.3.4.1 2.3.4.1 netmask 255.255.255.240 Attached routers D, E, F (Note:simple slash notation is a completely acceptable alternative to the dotted quad notation for the netmask) (Note2: Router priority 0 means no DR/BDR is elected. This because noone wants to be DR/BDR. Since there is no DR, we never proceed past phase 2-WAY. No Database synchronization is done. Thus all attached routers will have a stub link (not a transit link!) in their Router LSA describing the shared medium network. Finally, since we dont have full adjacency over the shared medium, routers A and B's Router LSAs will not be sent over the shared medium to router C, and on to G.) 3bi) How does F inform others of dead neighbour? (2p) F creates new Router LSA without the stub and p2p links facing router G. This LSA replaces the old one (incremented seq nr). If D is still DR F multicasts a LS Update (which carries the new LSA) to ALL_DR_ROUTERS. The DR multicasts the LS Update to ALL_SPF_ROUTERS. E unicasts an LS Acknowledgement back to D. F gots its ack implicitly when D multicasted the LS Update. ½ point for creation of new LSA ½ point for ALL_DR_ROUTERS ½ point for ALL_SPF_ROUTERS ½ point for Acknowledgements If F is now DR F multicasts the LS Update (carrying the new LSA) to ALL_SPF_ROUTERS, all other routers acknowledge it. 0.66 points for creation of new LSA 0.66 points for ALL_SPF_ROUTERS 0.66 points for Acknowledgements To get rid of silly grades, round off total to 0.5, 1, and 2. (note: see lecture notes on reliable flooding on shared mediums for more details. ) 3bii) When are the routes removed from routing table? 2p the graph will now be partitioned, so dijkstra will be conducted on the side router E is on. This implies that these routes will be removed from the routing table immediately. When are the LSAs removed from the LSDB? 2p when the LSA's LS_AGE field passes MAX_AGE (3600s) 3biii) G's LSDB 1p for correct Router LSA from C 1p for correct Router LSA from F 0p for G's Router LSA (its identical to earlier question), but it must be mentioned! 1p for each network summary LSA. -1 for skipping all details -½ for forgetting Gs Router LSA -½ for forgetting netmask in a netmask LSA G's LSDB ŻŻŻŻŻŻŻŻ LSTYPE LS ID ADV RT PAYLOAD # links, LINK TYPE, LINK ID, LINK DATA C 1 1.2.3.3 1.2.3.3 2 stub 1.2.1.0 255.255.255.252 p2p 2.4.1.2 1.2.1.1 G 1 2.4.1.2 2.4.1.2 4 stub 1.2.1.0 255.255.255.252 p2p 1.2.3.3 1.2.1.2 stub 2.4.1.0 255.255.255.252 p2p 2.4.1.1 2.4.1.2 F 1 2.4.1.1 2.4.1.1 2 stub 2.4.1.0 255.255.255.252 p2p 2.4.1.2 2.4.1.1 C 3 1.2.3.0 1.2.3.3 network mask 255.255.255.224 F 3 2.3.4.0 2.4.1.1 network mask 255.255.255.240