Andy Collins CSE 461 Winter 1998 Homework 4 Solutions ~~~~~~~~~~~~~~~~~~~~ 1. P&D 3.8 Basic answer: CRCs are better, checksum is easier to compute in software. CRCs are stronger mathematically in general (though not as strong as some of the more modern crypographically secure hashes, where strength is defined roughly as the odds that a normal process (or in the case of a crypto algorithm a poly-time adversary) can find/cause two inputs that give the same output), and better at handling burst errors that might be typical on a network link. However the polynomial math is a pain to understand and implement, and doing it in software on the computers that first made up the internet would have been impractial. Checksum was chosen because it was more feasible and because it was assumed that the link layer would do stronger error checks on links which were presumed to be noisy in nature. 2. P&D 4.2 The following is the complete table after the last addition, with the sections corresponding to each circuit opening marked. This workds largely because no connections are closed in this question, so they all end up using distinct resources. I started allocating ids at 1, starting at 0 also makes sense, and will knock one off of every id. Switch 1 Switch 2 Switch 3 Switch 4 in id out id in id out id in id out id in id out id (a) A -> B: 2 1 1 1 3 1 0 1 0 1 3 1 - - - - (b) C -> G: 3 1 1 2 3 2 1 1 - - - - 3 1 1 1 (c) E -> I: - - - - 2 1 0 2 0 2 2 1 - - - - (d) D -> B: 0 1 1 3 3 3 0 3 0 3 3 2 - - - - (e) F -> J: - - - - 1 2 0 4 0 4 1 1 2 1 3 2 (f) H -> A: 1 4 2 2 1 3 3 4 - - - - 0 1 3 3 If you actually copied each table for each part, then at each step the complete table is the set of all the rows at or above that line in my description. 3. P&D 4.3 (Note: I think the cost is optional. This is optimal routing where the edge weights are the cost metric) Node A dest link cost A - 0 B C 6 C C 3 D C 6 E C 4 F C 9 Node B dest link cost A B 6 B - 0 C B 3 D B 4 E B 2 F B 9 Node C dest link cost A A 3 B E 3 C - 0 D E 3 E E 1 F F 6 Node D dest link cost A E 6 B E 4 C E 3 D - 0 E E 2 F E 9 Node E dest link cost A C 4 B B 2 C C 1 D D 2 E - 0 F C 7 Node F dest link cost A C 9 B C 9 C C 6 D C 9 E C 7 F - 0 4. P&D 5.1 My ASCII art isn't up to task for actaully drawing the picture, so I'll just do text. The UNselected ports should be: B5: UP (that network prefers B2) B6: DOWN (that network prefers B4) B2: exactly one of UP or DOWN, I think its a toss up and the book doesn't clarify which path to root a bridge chooses when both are equal. 5. P&D 5.5 The general argument is to simplify the routers. If routers were to do reassembly then they would have to: (a) be sure to send all fragments along the same next hop (otherwise the next router could not reassemble them), which would complicate routing table updates. (b) buffer partail segments until all the fragments arrived, implement some policy to drop when it appears the missing fragments are gone. (b) will have to be done at the host, but it is easier to put more logic at the host. Also, reassembly in the routers might frustrate configurations where a segment starts in a large MTU network and then traverses a series of small MTU networks: do we want to fragment and reassemble at every hop? By not fragmenting the general routing logic is simplified. 6. P&D 5.7 If a host were to be connected to the internet through two different interfaces with the same IP address, then this would tend to confuse the routing protocols, and probably lead to unstable routes, since there would be two globally different paths to the same host. Lots of odd things might happen depending on the exact setup, so most any answer was okay. 7. P&D 5.10 10-15 minutes was chosen pretty much arbitrarily. What we need to think about is the cases where the data in an ARP cache might change, and reason about the frequency of them, and argue as to why much arger or much smaller would not be good. The times that an ARP cache entry needs to change are: * When a host changes its IP address, then the IP -> Ethernet mapping changes. * When an interface card fails and is replaced, then the host comes back up with a new interface card. Note that hosts coming and going do not lead to invalid data in the ARP cache: if a host appears, then the first packets to it will force an ARP message even without a timeout, since there is no entry. If a host goes away, then the ARP cache might erroneously report that it is still there, but that is not all that bad, because the packet will be dropped on way or the other (either because the router can't get the ethernet address or because no host on the ethernet picks up the packet since none of them have that address any more). The two cases listed above are both administrative tasks that generally involve rebooting computers. We wouldn't want the timeout to be in the hours range, because it is conceivable that we could complete these operations and expect the system to be back up and running in less than an hour. On the other hand, anything less than 5 minutes is probably overkill, since this is on the order of the administrative costs, so nobody will be bothered by stuff not working while the admin is hacking at the system (or at least they will blame the admin, not the IETF or the good PARC folks). Also note that overkill is bad, because it means wasted traffic. 8. P&D 5.13 (a) 128.96.39.10 matches 128.96.39.0 -> Interface 0 (b) 128.96.40.12 matches 128.96.40.0 -> R2 (c) 128.96.40.151 matches default -> R4 (d) 192.4.153.17 matches 192.4.153.0 -> R3 (e) 192.4.153.90 matches default -> R4 c and e are the interesting ones, because with each of those the given address fails to match the "obvious" router entry in the very bottom bit of the mask, and we have to go default.