%% LyX 1.1 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. \providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \setlength{\oddsidemargin}{-0.5in} \setlength{\evensidemargin}{-0.5in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \setlength{\textwidth}{7.0in} \setlength{\textheight}{9.5in} \setlength{\parindent}{0in} \setlength{\parskip}{0.1in} \makeatother \makeatother \makeatother \makeatother \makeatother \makeatother \makeatother \begin{document} Name: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \textbf{Directions: Work only on this sheet (on both sides, if needed); do not turn in any supplementary sheets of paper. There is actually plenty of room for your answers, as long as you organize yourself BEFORE starting writing. In order to get full credit, SHOW YOUR WORK. In fill-in questions, the number of blanks shown has no relation to the number of characters in the answer. Note that earlier questions tend to be easier.} \textbf{1.} (15) TCP breaks a message into segments. Leon-Garcia cites two reasons for doing this. State them, giving the page numbers and sentences. \textbf{2.} (15) Suppose that we know which path our packets are taking to reach a certain destination, and assume that this path will remain fixed. Describe, in as much detail as possible, how we could write a program to determine the smallest MTU of all links within that path. \textbf{3.} (10) First review the material in Sections 2.1.2 and 2.1.3 on p3 of our printed lecture notes unit on Level 2 routing. Then apply it to Figure 6.86 of Leon-Garcia. Suppose at the very beginning B2 and B3 receive BPDUs from each other, but no other BPDUs are out on the extended LAN yet. List the contents (in the format shown in Sec. 2.1.2) of all BPDUs (if any) which will be on the extended LAN after B2 and B3 process those first two BPDUs, again assuming that no more BPDUs have been generated yet. \textbf{4.} The following questions concern \textbf{ethereal} and its sample output distributed in class. In parts (b) and (c), you must have real, compilable/executable C code for full credit. \begin{itemize} \item (a) (10) What is the numerical IP address of the machine which reports the numerical IP address of heather.cs.ucdavis.edu? Your answer must be in the familiar \char`\"{}dotted decimal\char`\"{} format, e.g. 169.237.6.184. \item (b) {[}(10){]} Write C code for a function which could be part of \textbf{ethereal} with header \\ \begin{verbatim} int ishttp(char *ipdatagram); \end{verbatim} Here ipdatagram points to an IP frame. The function will return 1 or 0, according to whether this frame contains an HTTP transaction from the client side. (For instance, in the example in the handout, I am counting frames 3, 5 and 6 as such transactions, but not frames 4, 7 and 8.) \item (c) (10) Write C code for a function which could be part of \textbf{ethereal} with header \\ \begin{verbatim} int intact(char *ipdatagram); \end{verbatim} Again ipdatagram points to an IP frame. The function will return 1 or 0, according to whether the checksum in this IP frame indicates an error (1 means intact, 0 means error). You should call one or more of the various functions presented in our course. \end{itemize} \textbf{5.} (15) Look at the example on pp.410-411 of Leon-Garcia, and consider the first ring, with R = 4 Mbps, M = 20, etc. Continue to assume all messages have L = 400. Suppose the ring policy is \textbf{destination removal}, which means that a message is removed from the ring as soon as its last bit reaches the destination, at which time the destination is allowed to send a message if it has one. Assume that destinations are chosen randomly; for the purposes here, this means that you can assume that the destination is always 10 nodes away from the source. Find the utilization, expressed as a simple ratio of two integers. (Make use of the computations already done for you on p.410; if you feel an urge to use a calculator, you are doing something wrong.) \textbf{6.} (15) Look at the analysis leading to the formula Lp+LP+(k-1)P on p.478 of Leon-Garcia. Suppose P = 10p and k = 6, but that right after the fourth packet leaves the source node, routing is changed; the last two packets travel a two-hop route, with each hop still having the same values of p and P as in the original route. What will be the new value for the total delay? Your answer should be an expression in p and constants, no other symbols. \textbf{Solutions:} \textbf{1.} For instance, on p.477: {}``...probability of error in a transmitted block increases with the length of the block...Message switching is also not suitable for interactive applications.{}'' \textbf{2.} Send very large datagrams, with the Do Not Fragment bit set, and wait for the ICMPs. Experiment with different message lengths. \textbf{3.} B2 does nothing. B3 update's its old BPDU and sends it to two of the three LANs it's connected to: 3 2 1 2 3 2 1 2 \textbf{4(a).} Frame 1 is the DNS request. Its Destination Address field, Bytes 16-19, contain the address of the DNS server: 0xcfd97e51 = 207.217.126.81. \textbf{4(b).} \begin{verbatim} int ishttp(char *ipdatagram) { int hdlng; short dport; // get headher length in bytes hdlng = (*ipdatagram & 0xf) * 4;; // need protocol = TCP and destination port = 80; check the former // first if (*(ipdatagram+9) == 6) { // get destination port, guarding against big/little-endian problems memcpy(dport,ipdatagram+hdlng+2,2); dport = ntohs(dport); // check destination port if (dport == 80) return 1; } else return 0; } \end{verbatim} \textbf{4(c).} \begin{verbatim} int intact(char *ipdatagram) { int hdlng; // get headher length in bytes hdlng = (*ipdatagram & 0xf) * 4;; // note: checksum checks header only tmp = cksum(ipdatagram,hdlng); return 1-tmp; } \end{verbatim} \textbf{5.} First, what about the token insertion/removal policy? Since the problem states that the destination station gets the next crack at sending, that station will either send right away, if it has a message to send, or else put a new token on the ring. Now, it takes the sender 400 bit times to get the message on the ring, and the last bit arrives 90/2 = 45 bit times later. Then, under the conditions of maximum utilization (as in the textbook pages cited), the destination will start sending a new message. So, out of a time 400+45, 400 bit times have been used for sending. Thus the utilization is 400/445. \textbf{6.} Using the formula Lp+LP+(k-1)P, the fourth frame arrives at time 3p+3P+3P = 63p. The fifth frame will start at time4P = 40p. Using the formula, the sixth frame will then arrive 2p+2P+1P time units later, i.e. at time 40p+32p = 72p. (Or, look at it this way: The sixth frame will start at time 5P, and then will traverse two links in time P+p each, for a total of 5P+2(P+p) = 72p.) The total delay will then be max(63p,72p) = 72p. Note that we must use the max() function because it is conceivable that the sixth packet may actually overtake the fourth one. \end{document}