COS 109: Problem Set 8

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.

 

1. Watching and monitoring the internet

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 (213.186.37.162): 56 data bytes
64 bytes from 213.186.37.162: icmp_seq=0 ttl=46 time=97.337 ms
64 bytes from 213.186.37.162: icmp_seq=1 ttl=50 time=95.102 ms
64 bytes from 213.186.37.162: icmp_seq=2 ttl=46 time=97.724 ms
64 bytes from 213.186.37.162: icmp_seq=3 ttl=50 time=94.348 ms
64 bytes from 213.186.37.162: icmp_seq=4 ttl=50 time=94.729 ms
64 bytes from 213.186.37.162: icmp_seq=5 ttl=50 time=94.026 ms
64 bytes from 213.186.37.162: icmp_seq=6 ttl=50 time=94.358 ms
64 bytes from 213.186.37.162: 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 (213.186.37.162), 64 hops max, 52 byte packets
192.168.1.1  		 1.519 ms  
71.245.121.1  		 5.849 ms  
100.41.137.102  	13.197 ms
140.222.237.225  	13.033 ms  
192.99.146.253  	 8.129 ms 
192.99.146.126  	86.485 ms
94.23.122.215  		96.601 ms 
94.23.122.147  		94.997 ms
213.186.32.153  	96.997 ms 
91.121.215.133  	95.044 ms
91.121.128.75  		95.914 ms
213.186.32.251  	93.459 ms
213.186.37.162  	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 IP address.
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.

 

2. You Can't Get There From Here

One of the original design goals of ARPANET, the precursor of the Internet, was that it should be fault-tolerant and able to survive incidents that destroyed parts of it. In that spirit, here is a fake network with routers (the green circles) and links between them (the lines). There are no connections except at routers.

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?

 

3. A Bit More Bits and Bytes

(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?

 

4. ASCII and encoded messages

Please do this problem without referring to web resources for either ASCII codes or conversions to and from hexadecimal and binary

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.