4003-420-01/4005-740-01 Data Communications and Networks I Selected Exercises Prof. Alan Kaminsky -- Fall Quarter 2012 Rochester Institute of Technology -- Department of Computer Science Module 1. Network Protocol Architectures Module 2. Data Transmission Module 3. Packet Transmission Module 4. Network Layer Module 5. Transport Layer Module 6. Internet Applications Module 7. Network Security Module 8. Network Application Design Module 9. Support Protocols Module 1. Network Protocol Architectures Required Reading Module 1 Lecture Notes Comer, Chapters 1, 2 Selected Exercises A system has an n-layer protocol hierarchy. Applications generate messages of length M bytes. At each of the layers, an h-byte header is added. What fraction of the network bandwidth is filled with headers? [Andrew S. Tanenbaum, Computer Networks, Third Edition (Prentice Hall PTR, 1996), page 75.] Because they view an internet through application services, users are only aware of Layer 5 in the TCP/IP reference model. When a programmer creates a new application, which layer(s) does the programmer need to understand? Explain. [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 17, Exercise 8.] Comer, Chapter 2, Exercise 3. Comer, Chapter 2, Exercise 12. Solutions Module 2. Data Transmission Required Reading Module 2 Lecture Notes Comer, Chapters 5, 6, 7, 9, 10, 11, 12 Selected Exercises Comer, Chapter 6, Exercise 11. Comer, Chapter 6, Exercise 20. Comer, Chapter 6, Exercise 21. Comer, Chapter 7, Exercise 18. Comer, Chapter 7, Exercise 22. Comer, Chapter 7, Exercise 23. Comer, Chapter 7, Exercise 24. Comer, Chapter 7, Exercise 25. Comer, Chapter 10, Exercise 9. Comer, Chapter 11, Exercise 5. Comer, Chapter 11, Exercise 12. Comer, Chapter 11, Exercise 13. (Note: "OC-12" and "OC-48" are defined in Chapter 12.) Comer, Chapter 12, Exercise 7. Comer, Chapter 12, Exercise 14. Solutions Module 3. Packet Transmission Required Reading Module 3 Lecture Notes Comer, Chapters 8, 13, 14, 15, 16 The Hamming Code Supplemental Reading Comer, Chapters 17, 19 Selected Exercises Each of the following decimal numbers is transmitted as one byte with an even parity bit. Give the codewords in binary, with the parity bit at the end. 186     1     227     225     240     62     214     185 The decimal numbers in Problem 1 are transmitted, one byte each, in a packet with a checksum at the end. The checksum is computed using the Internet Checksum algorithm in RFC 1071. Give the checksum bytes that are transmitted, in binary. Bytes are transmitted with an odd parity bit. The following codewords are received. For which codewords is an error detected? 100011101     001111101     101100010     111101100     000111000     101011011     101010001     100001110 4-bit data words are transmitted using a (7,4) Hamming code. The following codewords are received. What data words were transmitted? (Assume there is a negligible probability of two or more bit errors in a codeword.) 0010010     1100001     0010001     0011101     0111100     0010100     0000010     1010000 A 4-bit data word is encoded using a (7,4) Hamming code. What is the probability that an uncorrectable error occurs if the bit error rate (BER) is 1x10−4? If the BER is 1x10−3? (Assume independent bit errors.) Using the concept of Hamming distance, explain why a parity bit is able to detect all single-bit errors. Suppose malfunctioning hardware in a character-oriented transmission system sets all bits transferred to zero. Does a parity bit catch the problem? Why or why not? [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 7, Exercise 7.] Checksum computation is often implemented with conventional computer software, but most CRC computations are performed with special-purpose hardware. Why? [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 7, Exercise 11.] Assume a one megabyte file must be transferred across a network. Ignoring delays caused by waiting for access and other overhead (i.e., counting only the data transferred), how would would it take to send the file across a Fast Ethernet? Across a network operating at 2.4 Gbps? [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 8, Exercise 6.] In most technologies, a sending station can choose the amount of data in a frame, but the frame header is a fixed size. Calculate the percentage of bits in a frame devoted to the header for the largest and smallest Ethernet frames. [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 9, Exercise 4.] Solutions Module 4. Network Layer Required Reading Module 4 Lecture Notes Comer, Chapters 18, 20, 21, 22 Supplemental Reading Comer, Chapters 23, 24, 27 Selected Exercises Consider the network shown below with routers A through E. The routers forward packets along the shortest path to the destination, where the shortest path is defined to be the one with the smallest total link weight. Give each router's routing table. [Diagram: James F. Kurose and Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Second Edition (Addison-Wesley, 2003), page 409.] Repeat question 1, except the shortest path is defined to be the one with the fewest hops. A computer's IP address in binary is 10110101100010000101111111011100. What is its IP address in dotted decimal notation? The computer in Question 3 is attached to a network that uses class-based addressing. What is the computer number within the network? Give your answer as a binary number. A computer's IP address is 29.73.12.24/20. What is the computer number within the network? Give your answer as a binary number. My home network includes a router with two ports, the "LAN" port that connects to the local area network inside my house and the "WAN" port that connects to my Internet Service Provider's network. Here is my router's routing table: Destination Mask Next Hop Port 0.0.0.0 0.0.0.0 65.37.80.1 WAN 67.37.80.0 255.255.248.0 (deliver direct) WAN 192.168.1.0 255.255.255.0 (deliver direct) LAN Does my ISP's network use class-based or classless addressing? Explain why. What is the IP address of my ISP's router? What is the network portion of the IP address of every computer in my house? Give your answer as a binary number with 0s and 1s for the network portion and dashes for the rest. Is the computer with IP address 67.37.85.42 located on my home network, my ISP's network, or somewhere else? What about the computer with IP address 67.37.88.193? A source computer sends an IP datagram of 56,000 total bytes (including the IP header). The IP header includes none of the optional fields. The path from the source computer to the destination computer has 10 routers. The MTU on each hop is 500 bytes. The probability that a router will drop a packet (e.g., due to congestion) is 1%. What is the probability that the IP datagram will arrive at the destination? (Note: The MTU is the maximum size payload that a data link frame can carry.) Comer, Chapter 18, Exercise 7. Comer, Chapter 18, Exercise 9. Comer, Chapter 21, Exercise 3. Comer, Chapter 21, Exercise 7. Comer, Chapter 21, Exercise 8. Comer, Chapter 21, Exercise 9. Comer, Chapter 21, Exercise 10. Comer, Chapter 21, Exercise 11. Comer, Chapter 21, Exercise 12. Comer, Chapter 21, Exercise 17. Comer, Chapter 21, Exercise 18. Comer, Chapter 22, Exercise 7. Comer, Chapter 22, Exercise 10. Comer, Chapter 22, Exercise 12. Comer, Chapter 22, Exercise 13. Comer, Chapter 22, Exercise 14. Comer, Chapter 22, Exercise 15. Comer, Chapter 22, Exercise 17. Comer, Chapter 22, Exercise 18. Comer, Chapter 22, Exercise 19. Solutions Module 5. Transport Layer Required Reading Module 5 Lecture Notes Comer, Chapters 25, 26 Selected Exercises Comer, Chapter 25, Exercise 3. Comer, Chapter 25, Exercise 4. Comer, Chapter 25, Exercise 5. Comer, Chapter 25, Exercise 6. Comer, Chapter 25, Exercise 8. Comer, Chapter 26, Exercise 3. Comer, Chapter 26, Exercise 7. Comer, Chapter 26, Exercise 8. Comer, Chapter 26, Exercise 11. Comer, Chapter 26, Exercise 15. Comer, Chapter 26, Exercise 18. Questions 12-15. A PC is connected to a server over the Internet. The connection uses the TCP/IP protocols with no optional header fields. The path from the PC to the server has 2 intermediate routers. Each data link in the path is a 100 megabit per second Ethernet. Each data link in the path is 500 meters long. The bit error rate on each data link is 2x10−5, and bit errors are independent. Each router operates as follows: For each incoming packet, the router receives the packet in its entirety, then the router immediately begins to send the packet on the proper outgoing line. The PC sends to the server one application-layer message consisting of 900 bytes. How many bytes long is the data link layer packet the PC transmits? How much time elapses from when the PC starts transmitting the packet until when the server finishes receiving the packet? What is the probability that the correct packet will be received by the router attached directly to the PC? What is the probability that the correct packet will be received by the server? Solutions Module 6. Internet Applications Required Reading Module 6 Lecture Notes Comer, Chapter 4 Supplemental Reading Comer, Chapters 28, 29, 31, 32 Selected Exercises Questions 1-3. You are running a web browser on your PC, host A, and have requested the web page at URL http://neo.jpl.nasa.gov/neo.html. The DNS local name server for your PC is host B. The DNS authoritative name server for the google.com domain is host C. The DNS authoritative name server for the nasa.gov domain is host D. The DNS authoritative name server for the rit.edu domain is host E. The DNS root name server is host F. Your PC does not cache DNS information. The local name server caches DNS information, but at the moment the cache is empty. Host A and host B communicate through a local area network; all other communication goes through the Internet. It takes 1 millisecond to send a datagram from one host to another host over the local area network. It takes 64 milliseconds to send a datagram from one host to another host over the Internet. Processing time for each DNS message is negligible. On the diagram below with all the hosts, show the sequence of DNS messages needed for your browser to translate the URL to an IP address. Draw each message as an arrow from the sender to the receiver. Number the messages 1, 2, 3, and so on in the order they are sent. How much time elapses from the time your browser starts translating the URL to the time your browser has the IP address? As soon as you finish downloading the first web page, you immediately request the web page at URL http://neo.jpl.nasa.gov/stats/index.html. How much time elapses from the time your browser starts translating the URL to the time your browser has the IP address? True or false?   Suppose a user requests a Web page that consists of some text and two images. For this page the client will send one request message and receive three response messages. Two distinct Web pages (for example, www.mit.edu/research.html and www.mit.edu/students.html) can be sent over the same persistent connection. With nonpersistent connections between browser and origin server, it is possible for a single TCP segment to carry two distinct HTTP request messages. The Date: header in the HTTP response message indicates when the object in the response was last modified. [James F. Kurose and Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Third Edition (Addison-Wesley, 2006), page 171.] Consider an HTTP client that wants to retrieve a Web document at a given URL. The IP address of the HTTP server is initially unknown. The Web document at the URL has one embedded GIF image that resides at the same server as the original document. What transport and application-layer protocols besides HTTP are needed in this scenario? [James F. Kurose and Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Third Edition (Addison-Wesley, 2006), page 172.] Suppose within your Web browser you click on a link to obtain a Web page. Suppose that the IP address for the associated URL is not cached in your local host, so that a DNS look-up is necessary to obtain the IP address. Suppose that n DNS servers are visited before your host receives the IP address from DNS; the successive visits incur RTTs of RTT1, . . . , RTTn. Further suppose that the Web page associated with the link contains exactly one object, a small amount of HTML text. Let RTT0 denote the RTT between the local host and the server containing the object. Assuming zero transmission time of the object, how much time elapses from when the client clicks on the link until the client receives the object? [James F. Kurose and Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Third Edition (Addison-Wesley, 2006), page 172.] Referring to Problem 6, suppose the HTML file references three very small objects on the same server. Neglecting transmission times, how much time elapses with: Nonpersistent HTTP with no parallel TCP connections? Nonpersistent HTTP with parallel connections? Persistent HTTP with pipelining? [James F. Kurose and Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Third Edition (Addison-Wesley, 2006), page 172.] A client's web browser sends all its HTTP requests to a caching proxy server. If the proxy server does not have the requested object in its cache, the proxy server obtains the object from the origin server using HTTP, stores the object in its cache, and returns the object to the client. If the proxy server has the requested object in its cache, the proxy server returns the object directly to the client, without checking whether the object has been modified at the origin server. The web browser does not do any caching. All the processes use non-persistent, non-parallel HTTP connections. The round trip time between the client and the proxy server is RTT1. The round trip time between the proxy server and the origin server is RTT2. The objects are all small, so it takes zero time to transmit an HTTP request message or transmit an HTTP response message. Also, it takes zero time to store an object in the proxy server's cache. Omit the time needed for DNS lookups. One morning, the client requests a web page that contains text plus four images. Neither the web page nor any of the images are in the proxy server's cache at this point. How long does it take for the client's web browser to obtain all the information needed to display the web page? That afternoon, the client requests the exact same web page. How long does it take for the client's web browser to obtain all the information needed to display the web page? Suppose a link from one Web document to another contains a typo that causes the reference to contain an invalid computer name. What does a browser report if a user attempts to access the link? [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 35, Exercise 1.] In the previous question, what does a browser report if an error causes the link to refer to a valid computer that is not running a web server? [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 35, Exercise 2.] Should a browser cache a copy of all bookmarked pages? Why or why not? [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 35, Exercise 7.] What interpreters can a browser contain besides HTML and FTP? [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 35, Exercise 8.] Read the HTTP specification. What is a conditional get operation? Explain how it can produce a substantial increase in retrieval speed. [Douglas E. Comer, Computer Networks and Internets, Fourth Edition (Prentice Hall PTR, 2004), Chapter 35, Exercise 16.] Solutions Module 7. Network Security Required Reading Module 7 Lecture Notes Comer, Chapter 30 Selected Exercises Eve has managed to obtain both a plaintext block and the corresponding ciphertext block encrypted using DES. All she needs now is the key and she will be in business. Eve has a special-purpose DES chip that takes 1 nanosecond (1x10−9 seconds) to encrypt or decrypt a block. In the worst case, how long will it take Eve to recover the key using an exhaustive search? Give your answer in seconds and in years. In the previous question, what could Eve do to find the key in one day? Assume that Eve can build any hardware she wants, but she doesn't want to spend more money than necessary. The binary plaintext P below was encrypted using a stream cipher to create the binary ciphertext C below. What was the keystream K? P = 0001010101011001000100011100110000011110100101000110001010100111 C = 1011101011010101000001011111010001100110111100101100101000100101 The hashCode() method for class java.lang.String is computed as follows, according to the Javadoc:     h = s0*31n−1 + s1*31n−2 + . . . + sn−1 where n is the length of the string and si is the numerical value of the i-th character. Is this a one-way hash function? Explain why or why not. Programming libraries often provide a multiplicative congruential pseudorandom number generator. The PRNG's initial state (seed) is an integer x. To generate the next pseudorandom number, the PRNG calculates     x' = a x (mod m), outputs x' as the next pseudorandom number, and replaces x with x'. Successive calls generate a sequence of pseudorandom integers in the range 0 through m−1; dividing these by m yields a sequence of pseudorandom floating point numbers in the range 0.0 (inclusive) through 1.0 (exclusive). Typical parameters might be a = 16,807 and m = 2,147,483,647. Is this a cryptographically strong PRNG? Explain why or why not. Alice and Bob need to do a Diffie-Hellman key exchange. They decide to use modulus p = 23 and generator g = 4. What is the order of the subgroup generated by g? Alice chooses a secret number a = 7. What number does she send to Bob? Bob chooses a secret number b = 10. What number does he send to Alice? What is the value of the shared secret Alice and Bob calculate? Alice needs to digitally sign messages using RSA. She chooses secret primes p = 17, q = 23, and public exponent e = 3. What is Alice's public signature verifying key? What is Alice's private signature generating key? Alice signs a message whose one-way hash is the number 154. What is her signature? Bob tries to verify Alice's signature on the message. Does the signature verify? Prove your answer. Comer, Chapter 30, Exercise 3. Comer, Chapter 30, Exercise 5. Comer, Chapter 30, Exercise 11. Comer, Chapter 30, Exercise 12. Comer, Chapter 30, Exercise 13. Solutions Module 8. Network Application Design Required Reading Module 8 Lecture Notes Comer, Chapter 3 Selected Exercises Questions 1-4. You are designing an instant messaging (IM) application. The application consists of an IM server process and multiple IM client processes. The client and the server communicate as follows: The client tells the server that the client's user went online. The user is identified by his or her screen name (a string). The client tells the server that a certain user (screen name) is in the client's buddy list. The server tells the client that one of the client's buddies went online or went offline. The client asks the server to send an IM to a certain user (screen name). The IM consists of a text string. The server replies stating whether the IM was delivered or not. The server delivers an IM to the client from a certain sender (screen name). The client tells the server that the client's user went offline. Give the Java interface for the server proxy. Give the Java interface for the client proxy. Design a textual wire protocol for the messages sent from client to server, and state the interface and method to which each message corresponds. Design a textual wire protocol for the messages sent from server to client, and state the interface and method to which each message corresponds. Questions 5-8. You are designing the wire protocol for a numerical application. One of the messages consists of an array of 256 integers (Java type int). You are trying to decide between a textual wire protocol and a binary wire protocol. In the textual wire protocol, each array element's value is sent as a string of decimal digits (characters) including a minus sign (- character) if the value is negative, with a tab character after each array element except the last, and with a newline character after the last array element; each character occupies one byte. In the binary wire protocol, each array element's value is sent using the writeInt() method of class java.io.DataOutputStream. Recall that the range of values for type int is −231 .. 231−1, or −2147483648 .. 2147483647. If the textual wire protocol is used, how many bytes is the smallest possible integer array message? The largest possible integer array message? If the binary wire protocol is used, how many bytes is the smallest possible integer array message? The largest possible integer array message? Which wire protocol would you choose, the textual or the binary? Give a justification for your choice. Suppose you knew that each integer in the array was in the range 0 through 100 inclusive. Now how would you choose to encode the integer array message? Why? Solutions Module 9. Support Protocols Required Reading Module 9 Lecture Notes Comer, Chapter 23 Selected Exercises Comer, Chapter 23, Exercise 1. Comer, Chapter 23, Exercise 3. Comer, Chapter 23, Exercise 4. Comer, Chapter 23, Exercise 5. Comer, Chapter 23, Exercise 6. Comer, Chapter 23, Exercise 7. Comer, Chapter 23, Exercise 8. Comer, Chapter 23, Exercise 9. Comer, Chapter 23, Exercise 11. Comer, Chapter 23, Exercise 12. Comer, Chapter 23, Exercise 13. Comer, Chapter 23, Exercise 15. Comer, Chapter 23, Exercise 19. Comer, Chapter 23, Exercise 22. Comer, Chapter 23, Exercise 23. Comer, Chapter 23, Exercise 24. Comer, Chapter 23, Exercise 25. Comer, Chapter 23, Exercise 26. Solutions Data Communications and Networks I • 4003-420-01/4005-740-01 • Fall Quarter 2012 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2012 Alan Kaminsky. All rights reserved. Last updated 30-Oct-2012. Please send comments to ark­@­cs.rit.edu.