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, 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. 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: #2: UDP is connection-less, which means it does not keep track of packets that are part of the same connection (but the OS kernel might track it). The only way to know if a two packets *might* be related is to look at their port numbers. So the following is possible client 1 connects to server from source port 50000 client 1 exists abrupted client 2 connects to same server from same port 50000 server responds with file fragment to destination port 50000 client 2 gets part of file requested by client 1 A related question would be can this happen with TCP. Not likely, because even if client 1 exited without initiating the closing handshake (and TIMEWAIT state), client 2 would need to establish a new connection using the opening handshake. The server (the OS of the server) would clearly see that the new connection request conflicts with an existing one, which is using the same port and ip numbers. A malicious program may try to assemble a TCP packet to hijack a connection, but it would have to guess correctly the sequence numbers being used (as well as masquerade as the same ip/port numbers because the original client is likely still running). This is theoretically possible, and the solution to most of these kinds of vulnerabilities is to use cryptographic encryption and authentication (i.e. use sftp instead of ftp). #5: Both the active (initiating) and passive sides have to exchange fin's and ack's. Each side's fin should be acknowledged. In this scenario, the active side's last action is to send, and the passive side is to receive. Once the passive side received the ack for it's final fin, it knows that the other side has completed the closing sequence (that is, it knows it's OK to close), and therefore can close safely. It need not wait any longer. The purpose of the timeout on the active side is to ensure that the final ack has been successfully received by the passive side. If the active side closes immediately after the final send, it cannot be certain that that the other side will also close, since the final ack can been lost. In that case, the passive side will not know that's it's OK to close, and will try to retransmit its final fin, which could have unpredictable consequences. #8: This question sounds more complicated than it actually is. The initial sequence number is not 0, but some random number, so of course it could wrap around to 0 before 4gigs are sent. #14a: How does the passive side ("server") distinguish between a new syn and a retransmission of the old syn from the same ip:port? First, there's the sequence number again, which will be likely different if the syn is that of a completely new connection. Secondly, the initial 3-way handshake would not have been complete - for the syn could be a retransmission only if the client did not receive the server's syn+ack. So any new syn received in the ESTABLISHED state from the same port and ip must be that of a completely new connection. #26: (Jacobson/Karels) - using initial deviation of 25: #include #include #define delta 0.125 int main(int argc, char **argv) { double ERTT,SRTT,Diff,Dev,Timeout; ERTT = 4.0; SRTT = 1.0; Dev = 25; // (same as suggested in book) int counter = 0; Timeout = ERTT + 4*Dev; // initial timeout while (Timeout >= 4.0) { printf("ERTT %f\t Dev %f\t Timeout %f\n",ERTT,Dev,Timeout); Diff = SRTT - ERTT; ERTT = ERTT + delta*Diff; Dev = Dev + delta*(abs(Diff)-Dev); Timeout = ERTT + 4*Dev; counter++; } printf("--Final--\nERTT %f\t Dev %f\t Timeout %f\n",ERTT,Dev,Timeout); printf("counter == %d\n",counter); exit(0); } /* output: ERTT 4.000000 Dev 25.000000 Timeout 104.000000 ERTT 3.625000 Dev 22.250000 Timeout 92.625000 ERTT 3.296875 Dev 19.718750 Timeout 82.171875 ERTT 3.009766 Dev 17.503906 Timeout 73.025391 ERTT 2.758545 Dev 15.565918 Timeout 65.022217 ERTT 2.538727 Dev 13.745178 Timeout 57.519440 ERTT 2.346386 Dev 12.152031 Timeout 50.954510 ERTT 2.178088 Dev 10.758027 Timeout 45.210196 ERTT 2.030827 Dev 9.538274 Timeout 40.183922 ERTT 1.901973 Dev 8.470989 Timeout 35.785931 ERTT 1.789227 Dev 7.412116 Timeout 31.437690 ERTT 1.690573 Dev 6.485601 Timeout 27.632979 ERTT 1.604252 Dev 5.674901 Timeout 24.303856 ERTT 1.528720 Dev 4.965539 Timeout 21.390874 ERTT 1.462630 Dev 4.344846 Timeout 18.842015 ERTT 1.404801 Dev 3.801740 Timeout 16.611763 ERTT 1.354201 Dev 3.326523 Timeout 14.660293 ERTT 1.309926 Dev 2.910708 Timeout 12.952756 ERTT 1.271185 Dev 2.546869 Timeout 11.458662 ERTT 1.237287 Dev 2.228510 Timeout 10.151329 ERTT 1.207626 Dev 1.949947 Timeout 9.007413 ERTT 1.181673 Dev 1.706203 Timeout 8.006486 ERTT 1.158964 Dev 1.492928 Timeout 7.130675 ERTT 1.139093 Dev 1.306312 Timeout 6.364341 ERTT 1.121707 Dev 1.143023 Timeout 5.693798 ERTT 1.106493 Dev 1.000145 Timeout 5.107074 ERTT 1.093182 Dev 0.875127 Timeout 4.593689 ERTT 1.081534 Dev 0.765736 Timeout 4.144478 --Final-- ERTT 1.071342 Dev 0.670019 Timeout 3.751418 counter == 28 */