Sample Solutions to selected homework problems from the textbook, chapters 2,3,5 (last updated 2019) Some of the homework problems also have very similar problems with sample solutions in the back of the book (starting on page 801). --- Chapter 2: #1, 2, 5, 6, 18, 39, 42, 45, 46, and 53 --- #5 stuffed bits seperated by spaces: 1101011111 0 01011111 0 101011111 0 110 this question is a bit ambiguous - I'm adding stuffed bits to the given sequence. If the question really is asking you to remove stuffed bits, then the sequence should have ended when 01111110 was seen. Also, the 7 consecutive 1's towards the end would indicate an error. What the question is really asking is for you to insert the stuff bits. The sequence shown in the text is the ORIGINAL DATA. You have to add the stuffed bits #6: 1101011111010111110010111110110 arrives: - - - The original *data* have the underscored lines removed. Note: the 7 consecutive 1's do not indicate an error in this case: they're part of the original data! #18 |---------------------------- 1001 |11001001 000 1001 ---- 01011 1001 ----- 001000 1001 ---- 11 00 10 01 ---- 1 010 1 001 ----- 011 <- remainder The data actually transmitted will be 11001001011 #18b: received |------------- 1001 |01001001011 1001 ---------- 0000001011 1001 ---- 010 -- non-zero remainder. The rule of polynomial division says that two polynomials of the same degree can always divide eachother, that's why you must line up the 1's. 19. a |----------------------------------- 100000111 |101100100100101100000000 100000111 -------- 00110001110 100000111 -------- 0100010010 100000111 -------- 101011011 100000111 --------- 101110000 100000111 --------- 111011100 100000111 --------- 0110110110 100000111 --------- 101100010 100000111 --------- 110010100 100000111 --------- 10010011 <- last 8 bits sent in place of 00000000 b. |------------------------ 100000111 |001100100100101110010011 ... same procedure yields a remainder of 10110110, which is not 00000000, so there's an error. 39. You can give many answers for this one, but please be detailed. For example: A packet meant for a particular hosts will be accepted by multiple hosts. These messages will in turn generate multiple responses for the original message. Or: Since a switch associates its physical ports with hardware addresses, it may not know what unique port to send a message over. Don't just say something vague like "it'll create massive confusion". I've gotten such answers before. 42. a. packet size will increase 10x to 640 bytes. b. This is a more interesting question and I talked about it briefly in class. The easy answer is that it would waste bandwidth when you only have to send out a few bytes. But the bigger problem is backwards compatibility. Software (device drivers) designed to send out 64 byte minimum-size packets will nolonger work. c. This question can be answered in several ways as long as you explain your reasoning carefully. A smaller minimum packet size and a higher bandwidth (100mbps) using CSMA/CD technology will entail a shortening of the maximum radius of the network. However, CSMA/CD technology can also be abandoned in favor of switched ethernets. The switches make the physical characteristics of the network transparent to software (by forming a layer of abstraction), which is then freed to adopt a specification that's more independent of physical limitations. 45. With the manchester encoding signals are equal to NRZ xor CLOCK: Manchester = NRZ ^ CLOCK, so Manchester ^ NRZ = CLOCK. If we xor the received manchester signal with the expected NRZ, we should get exactly a clock signal, and if we don't then there's collision. 46. This is not as hard as it sounds. There are many such scenarios and you just have to think carefully. Here's what I have. Time are given in units of 51.2 microseconds. A process backs for zero or more units after collision or carrier sense (busy signal) before reattempting. actions: tr = transmit, cs = carrier sense (detect busy), cd = detect collision and backs off, blank = waiting 1 2 3 4 5 6 7 8 9 10 11 12 13 Dtr Acs Atr Acd Atr Acd Atr Acd Atr Acd Acs Acs Atr Bcs Btr Bcd Btr Bcd Btr Bcd Btr Bcd Bcs Btr Ccs Ccs Ctr Ccd Ctr Ccd Ctr Ccd Ctr Notice that this is valid because it is possible, though unlikely, that all three processes choose to wait 0 time units before reattempting transmition. 53. This concerns the "hidden node" problem. There could still be a node that's in range of both, where collision occurs. --- Chapter 3: 33, 48, 55, 56 (56 has answers in back of book). 72, 73, 74. --- 33: If there's only one address per host then each host will only be able to connect to a single network an nobody can act as router. Everybody on the planet would be a happy "end user". The second part of this question concern bridging, which we haven't covered in detail. But bridging, for example, can be used by virtual machines (e.g. VirtualBox) so that each virtual host can have a different IP. #48 (dijsktra). Starting point is D. * means replacing an existing value format is (destination, cost, next-hop). Confirmed Tentative 0. (D,0,D) 1. (D,0,D) --> (A,8,A), (E,2,E) 2. (E,2,E) --> (B,4,E), (C,3,E) 3. (C,3,E) --> (F,9,E), (A,6,E)* 4. (B,4,E) (all neighbors already confirmed) 5. (A,6,E) 6. (F,9,E) 55. a. send directly over interface 0 b. R2 c. R4. 151 requires first bit to be 1, not 0, so not in 128.96.40.0/25 d. R3 e. R4. 90 has first two bits 01, not 00 as required by 192.4.153.0/26 72. a. B, it chooses the tighter match b. A c. E. the first bit is the same: 8=1000, C=1100 d. F. 5=0101, 4=0100, the first 2 bits are the same e. C. D=1101, 8=1000, so does not belong to C4.68.0.0/14 f. D. B=1011, 8=1000, so first 2 bits are the same This is a good problem, even though they use hexadecimal. 74. a. Say the /16 network was 148.8.0.0/16, you can allocate as follows: Marketing: 148.8.255.240/28 (4 bit host address==16 hosts) Engineering. Over 7 years, engineering will have 52*7+5=369, so allocate 512: 148.8.254.0/23 (9 bit host address==512 hosts) Sales: probabilities don't matter since they can take up the rest: The routing table for 148.8.0.0/16 will route all packets that don't belong to one of the first networks to the remainder. b. lasts when Engineering runs out of IP's after a few years. Use NAT. (this is not a quantitative question, there are many ways to answer it.) c. Give one class C subnet to Marketing and two to Engineering: Marketing: 198.8.255.0/24 Engineering: 198.8.254.0/24 and 198.8.253.0/24 Give rest of 198.8.0.0/16 to sales. ** technically, 148 does not represent a class C network, so I changed it to 198, which starts in binary with 110. 75. (extra just for you): Try a Trie! A hash table would still have to address the problem of matching with the longest prefix. -------------- Chapter 5 (TCP) problems: -- look for update, once these exercises have been collected.