Due 5:00 PM, Tuesday, December 12,
by submission to
drop box at https://dropbox.cs.princeton.edu/COS109_F2017/Problem_Set_8
Answers need not be long, merely clear so we can understand what you have done. Please submit typed material, not hand-written, if at all possible, and keep a copy for yourself just in case something goes astray. Thanks.
Collaboration policy for COS 109:
Working together to really understand the material in problem sets and
labs is encouraged, but once you have things figured out, you must part
company and compose your written answers independently. That helps
you to be sure that you understand the material, and it obviates questions
of whether the collaboration was too close.
You must list any other class members with whom you collaborated.
As mentioned in class, there are a variety of tools that are used to monitor the internet. In this assignment we will look into some of these tools and interpret their workings.
For this problem, you can assume that signals propagate in electronic circuits at about 1/3 of the speed of light in vacuum which is 186,000 miles per second, and there may be some overhead as well. So your answers will be approximations.
(a) The first tool we will explore is ping. Ping sends a small packet to another site and reports back whether the packet was received and how long it took for the packet to get to the other site. The times reported by ping are round trip times since the packet has to be transmitted and a return message has to come back to you. The following is a transcript from a ping I ran to the site vatican.it, which is at the Vatican in Rome. Based on these times, what is your estimate of the distance from me to the Vatican?
PING vatican.it (18.104.22.168): 56 data bytes 64 bytes from 22.214.171.124: icmp_seq=0 ttl=46 time=97.337 ms 64 bytes from 126.96.36.199: icmp_seq=1 ttl=50 time=95.102 ms 64 bytes from 188.8.131.52: icmp_seq=2 ttl=46 time=97.724 ms 64 bytes from 184.108.40.206: icmp_seq=3 ttl=50 time=94.348 ms 64 bytes from 220.127.116.11: icmp_seq=4 ttl=50 time=94.729 ms 64 bytes from 18.104.22.168: icmp_seq=5 ttl=50 time=94.026 ms 64 bytes from 22.214.171.124: icmp_seq=6 ttl=50 time=94.358 ms 64 bytes from 126.96.36.199: icmp_seq=7 ttl=50 time=94.732 ms --- vatican.it ping statistics --- 8 packets transmitted, 8 packets received, 0.0% packet loss round-trip min/avg/max/stddev = 94.026/95.294/97.724/1.329 ms
(b) The second tool is traceroute (which is abbreviated to tracert on Windows machines). Traceroute finds a path from your machine to a destination and then sends a ping to each location on the path. Typically, the results of a traceroute will have the names of all nodes on the path along with their IP addresses and the time a ping took. The information below is the result of a traceroute run to the machine vatican.it. I have eliminated names and just give IP addresses and time for the pings. Based on this information, can you identify at which point in the path, the signal crossed the ocean?
traceroute to vatican.it (188.8.131.52), 64 hops max, 52 byte packets 192.168.1.1 1.519 ms 184.108.40.206 5.849 ms 220.127.116.11 13.197 ms 18.104.22.168 13.033 ms 22.214.171.124 8.129 ms 126.96.36.199 86.485 ms 188.8.131.52 96.601 ms 184.108.40.206 94.997 ms 220.127.116.11 96.997 ms 18.104.22.168 95.044 ms 22.214.171.124 95.914 ms 126.96.36.199 93.459 ms 188.8.131.52 94.830 ms
(c) A third tool is speedtest which is a tool to measure the speed of your internet connection. Speedtest is available at the website www.speedtest.net (or you may want to visit beta.speedtest.net for a newer version). Run speedtest to determine the speed of your connection to the internet (measured by ping, download and upload speeds) and report your results here.
(d) A final tool presents itself as a phone book for the internet.
If you go to the site www.arin.net, it will tell you what your IP address
is at the top of the page. You can then enter that address into the
box labeled SEARCH Whois (also at the top of the page) to find out
various information about your current address. In particular,
the field labeled Net Range will tell you how many IP addresses
are owned by the organization from whom you are getting your current
Visit this site and record your IP address as well as the Organization who owns it and the range of addresses they own.
Do not use the data from this web site in solving part (b) of this problem.
Let's test its survivability. There may be multiple answers to some of these questions; you only need to give one.
(a) What is the smallest set of links that you would have to destroy to completely disconnect Princeton from Stanford? List the links by their endpoints, for example A-B or Stanford-E.
(b) If a router is destroyed, any link connected to it no longer works. What is the smallest set of routers (not including Stanford or Princeton themselves) that you would have to destroy to disconnect Princeton from Stanford? List the routers by letter.
(c) What routers are exactly two "hops" away from Princeton? That is, what routers can you reach from Princeton by following a path that goes through exactly two links? Don't count direct loopbacks like Princeton-F-Princeton; that is, Princeton is not two hops from Princeton. (Note that there are some situations where a node can be reached by paths of different lengths.)
(d) What is the shortest path (that is, the path with the fewest links) from Princeton to Stanford? Give the sequence of routers that make up the path.
(e) What is the longest path from Princeton to Stanford that doesn't have a loop, that is, that doesn't go through any router more than once?
(f) Suppose that you want to build a network in which every router can communicate with every other router, either directly or indirectly by passing information through other routers. For that kind of network, what is the absolute minimum number of links necessary to connect R routers?
(a) Cookies that come from some Unix or Linux servers expire on a specific day in 2038, a very long time from now. Given that (i) Unix and Linux systems store times as the number of seconds since the beginning of 1970, and (ii) one bit of a 4-byte integer in a modern CPU is used to represent the sign of the value, explain why a particular date in 2038 might have been chosen by programmers.
(b) What is the ratio of possible Ethernet (MAC) addresses to the number of possible IPv4 addresses?
(c) Assume that the number of Ethernet address in use is the same as the number of IPv4 addresses in use and that no more IPv4 addresses are available. Also, assume that the number of Ethernet addresses in use doubles every 18 months. Based on these assumptions, how long will it be before no Ethernet addresses are available?
The ASCII codes for letters of the alphabet begin at 65 (decimal) for A (capital A) an go through 90 for Z. Lower case letters begin at 97 for a (lower case a) and go through 122 for z. Letters come in order so that e.g. B is 66, C is 67, ,.... X is 88, Y is 89, b is 98, c is 99, ... x is 120 and y is 121. Space is the ASCII code 32 (in decimal) The simplest of encoding algorithms (which dates back to Caeser) involves shifting each letter by a few places in order to encoded a message that looks like nonsense to someone who doesn't know the encoding scheme and is easily decoded by the recipient.
(i) To start, write your name as a character string (e.g. David Dobkin) and then write in in ASCII first as a string of decimal numbers (so, 68-97-118-105-100-32-68-111-98-107-105-110 for my name) and then rewrite your name as a string as hexadecimal characters and as a string of binary characters.
(ii) If you want to implement a Caesar cipher for your name, a simple thing to do is to shift each character by a few letters. For example, a Caesar cipher for my name with a shift of 2 would yield the name Fcxkf Fqdmkp. Figure out the Caesar cipher of shift size 2 for your name in letters, in decimal, in hexadecimal and in binary. Note that if you have a y or z in your name, it will be shifted to an a or b.
(iii) A more effective version of the Caesar cipher is to shift each character by a different number of spaces. For example, we could shift the first letter by 1, the second by 2, ... In the case of my name this would transform things to Ecymi Kwkutz. Perform this transform on your name and present the result in decimal, hexadecimal and binary.