Math 343 Sample Midterm Fall 1999 Dordal Exam will be Wednesday, Oct 27 (week 9) The exam will cover the following sections from Peterson & Davie. Also read your notes on ethernet, or check my ethernet notes page http://www.math.luc.edu/~pld/courses/443/ethernet.html. Chapter 1: sections 1.2; 1.3 Chapter 2: omit Chapter 3: sections 3.1; 3.2 (skim); 3.3, 3.4, 3.5; 3.6 (+ ethernet notes). Chapter 4: sections 4.1; 4.2; 4.3 Chapter 5: 5.1; 5.2; 5.3.1; 5.3.3, and 5.3.2 if we get to it. Peterson & Davie exercises that are worth reading: chapter 3: 21, 22, 24 chapter 4: 1, 2, 3 chapter 5: 2, 3, 4, 5, 7, 8, 9, 10, 13, 17, 18, 21 Some additional exercises: ====================================================================== 1. This problem concerns an adaptive bridge, which maintains a "do not forward" table of physical destination addresses that do not require forwarding on each side. Recall that all packets must be forwarded unless the bridge knows that the packet destination is on the same side as the source. In each problem, assume that the tables are initially empty. (a) Draw the "do-not-forward" tables for bridge M after the following packets are sent: a packet is sent to X from A a packet is sent to B from X a packet is sent to C from B M A_____B_____C_____________/ \__________X_____Y____Z (b). After the exchanges of part (a), give four different (dest, src) packet transactions that would now not be forwarded by M. (c). Draw the "do-not-forward" tables for bridges M and N after the following packets are sent: a packet is sent to U from A a packet is sent to B from W a packet is sent to C from B a packet is sent to V from X M N A_____B_____C____/ \_____X_____Y____Z_____/ \_____U____V____W (d). What would the answer be if there were only one bridge, M, and each of the segments ABC, XYZ, and UVW connected directly to M? ====================================================================== 2. Consider the following arrangement of learning bridges: B3----C | A-----B1------B2 | B4----D Assuming all are initially empty, give the forwarding tables for each of the bridges B1-B4 after the following transmissions: A sends to C C sends to A D sends to C ====================================================================== 3. Suppose two learning bridges B1 and B2 form a loop as shown, and do *not* implement the spanning-tree algorithm. Each bridge has a single table of pairs. +---L---+ B1 B2 +---M---+ (a) What will happen if M sends to L? (b) Suppose a short while later L replies to M. Give a sequence of events that leads to one packet from M and one packet from L circling the loop in opposite directions. Try to get a general sense here of what might happen, even if you don't work through all the details. ====================================================================== 4. Consider the following ATM network. For a given connection, recall that each link is assigned a separate VCI, and routers do lookup based on and then reroute to port_out and rewrite the VCI to VCI_out. Give table entries for the following connections, created in the order shown: A has a connection with B A has a connection with C A has a *second* connection with B B has a connection with C As each connection is made, assign that connection the smallest VCI available on that link, starting with 1. A-------- R1 -------- R2 --------B | | | C ====================================================================== 5. The following problem deals with IP routing tables as maintained by routers; machines A, B, C, D, etc. are routers. No host machines are shown. The special machine DEFAULT is also a router, but you need not give its routing table (it represents a default destination). Nets involved are all class C, with addresses 200.0.5, 200.0.6, 200.0.7, .... The following convention is used: machine A always has host portion of its address equal to 1; e.g. 200.0.5.1, 200.0.6.1, etc. Similarly, B has host portion 2, C has 3, D has 4. The special machine DEFAULT has host portion 100. (a). Give the routing tables for the following connections. You may use symbolic names (A, B, C...) for routers instead of IP addresses. Use default routes whenever possible, but be sure that a packet destined for some net other than 200.0.x gets routed to machine DEFAULT. net net net net 200.0.5____A_____200.0.6_____B______200.0.7_______D____ 200.0.8______DEFAULT | 200.0.8.100 | net 200.0.9 | | C | net 200.0.10 b. Do the same for the following configuration. B / \ / \ net 200.0.5 net 200.0.6 / \ / \ A D------------200.0.9 \ / \ \ / \ net 200.0.7 net 200.0.8 DEFAULT \ / 200.0.8.100 \ / C c. Suppose two routers, A and B, have tables as below. What will happen to an IP packet sent from A to address 147.126.4.9? 200.0.5----A----------------------B----200.0.6 A: ___________________ 200.0.5 | direct default | B B: ___________________ 200.0.6 | direct default | A ====================================================================== 6. Consider the following router, A, using vector-distance (RIP) routing. Give the changes A will make to its routing table upon receiving the given report from B. Also give a one-sentence explanation of each change. A's routing table B's report net dist 1st hop net dist 1 2 C 5 3 5 4 B 9 2 9 5 C 13 2 13 4 B 15 5 17 4 B 17 4 ====================================================================== 7. In real implementations of ARP, hosts are allowed to extract address mapping info from any broadcast ARP query packet: every machine sending such a packet includes its own IP-to-physical address binding info, and every machine receiving such a broadcast (whether or not intended for that machine) adds the source IP-to-physical address info to its ARP cache. Thus, in the example above, not only would A get B's address info but also every machine on the net would get A's address info. (a). Explain why this means that if A broadcasts an ARP query "where is B?" A sends B a regular IP packet B wants to send an IP packet in reply to A then A's physical address will already be in B's ARP cache. (b). Suppose A broadcasts a request "where is B", but inadvertently lists the physical address of another machine C instead of its own (i.e. the ARP packet has IP src=A, phys src = ethernet address of C). What will happen? Specifically, Will A get a reply? What entries will be made in the ARP caches on A, B, C, and a 4th machine D? Suppose D uses its newly updated cache to send to A. Will the packet arrive atA? What if C tries to send to A? ====================================================================== 8. In the source routing example of section 4.1.1, the address received by B is not reversible and doesn't help B know how to reach A. Propose a modification to the addressing mechanism that does allow for reversibility. Your mechanism should *not* require giving all switches globally unique names. Do not worry too much about details; try to focus on the general idea. ====================================================================== 9. For the network in Fig 4.30, suppose the forwarding tables are all established [as in ch 4 exercise 3] and then the C-E link fails. Give: (a) The tables of A, B, D, and F after C and E have reported the news. (b) The tables of A and D after their next mutual exchange. (c) The table of C after A exchanges with it. ====================================================================== 10. Consider the situation involving the creation of a routing loop described in [the end of the first full paragraph on page 167; in fig 4.10 the A-E link breaks]. List *all* sequences of table updates among A, B, and C, pertaining to destination E, that lead to the loop. Assume that table updates are done one at a time, that the split-horizon technique is observed by all participants, and that A sends its initial report of E's unreachability to B before C. You may ignore updates that don't result in changes. A complete solution is a little messy if you write down all the details; try to give a general overview of what update sequences result in loops and what sequences end with no loops. ====================================================================== 11. Give the steps (as in Table 4.6) in the forward-search algorithm as it builds the routing database for node A below: D---5---E / \ / \ 2 2 2 1 / \ / \ A---5---B---4---C ====================================================================== 12. A site is diagramed below. R1 and R2 are routers; R2 connects to the outside world. Individual LANs are Ethernet. RB is a bridge-router; it routes traffic addressed to it and acts as a bridge for other traffic. A | C-----R1-----RB--------R2---rest of Internet ---D | B Subnetting is used inside the site; ARP is used on each subnet. Unfortunately, host A has been misconfigured and doesn't use subnets. Which of B,C,D can A reach? This was based on a true situation at Loyola. ====================================================================== 13. An organization has a class C network 200.1.1 and wants to form subnets for four departments, with hosts as follows: A 72 hosts B 35 hosts C 20 hosts D 18 hosts There are 145 hosts in all. (a). Give a possible arrangement of subnet masks to make this possible. (b). Suggest what the organization might do if department D grows to 34 hosts. ====================================================================== 14. Give an argument that the small ATM cell size discourages the use of datagram routing. ====================================================================== 15. Suppose hosts A and B are on an Ethernet LAN with class-C IP network address 200.0.0. It is desired to attach a host C to the network via a direct connection to B. Explain how to do this with subnets; give sample subnet assignments. Assume that an additional network address is not available. What does this do to the size of the Ethernet LAN? C | A B ...--+----+--... ====================================================================== 16. An alternative method for connecting host C in problem 12 is to use _proxy ARP_ and routing: B agrees to route traffic to and from C, and also answers ARP queries for C received over the Ethernet. (a). Give all packets sent, with physical addresses, as A uses ARP to locate and then send one packet to C. (b). Give B's routing table. What peculiarity must it contain? Hint for (b): it's called "host-specific" routing. ====================================================================== 17. Suppose the fragments of Figure 5.9(b) all pass through another router onto a link with an MTU of 380 bytes. Show the fragments produced. If the packet were originally fragmented for this MTU, how many fragments would be produced? ====================================================================== 18. The following is a routing table using CIDR. Address bytes are in hexadecimal. The "/12" in C4.50.0.0/12 denotes a netmask with 12 leading 1-bits, ie 255.240.0.0. Note that the last three entries cover every address and thus serve in lieu of a default route. net/masklength nexthop C4.50.0.0/12 A C4.5E.10.0/20 B C4.60.0.0/12 C C4.68.0.0/14 D 80.0.0.0/1 E 40.0.0.0/2 F 00.0.0.0/2 G State to what next hop the following will be delivered. (a). C4.5E.13.87 (b). C4.5E.22.09 (c). C3.41.80.02 (d). 5E.43.91.12 (e). C4.6D.31.2E (f). C4.6B.31.2E ====================================================================== 19. Suppose P, Q, and R are providers, with respective CIDR allocations (using the notation of problem 7) C1.0.0.0/8, C2.0.0.0/8, and C3.0.0.0/8. P has customers PA with allocation C1.A3.0.0/16 and PB with allocation C1.B0.0.0/12. Q has customers QA with allocation C2.0A.10.0/20 and QB with allocation C2.0B.0.0/16. Now suppose customer PA switches to provider Q and customer QB switches to provider R. Give routing tables for each provider that allow PA and QB to switch without renumbering. ====================================================================== 20. In the following problem, IP addresses are followed with /n, where n is the number of initial 1 bits in the mask. Remaining bits are 0. For example, /8 implies a mask of FF.00.00.00. All address components are in *hexadecimal*. Addressing is assumed to use the CIDR approach. Suppose a certain country uses IP address 30.0.0.0/8 Two providers use provider addresses P1 = 30.80.0.0/10 and P2 = 30.40.0.0/10. Converting the second byte to binary, these we have $80 = 1000 0000 and $40 = 0100 0000. (a). Give two more possible provider addresses, with masks (/n format). (b). Let A be a customer of P1, originally assigned address 30.84.10.00/20. Give routing tables for P1, P2, and the regional 30.0.0.0/8 backbone assuming A changes to provider P2 but does NOT wish to change IP address.