%% 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[twocolumn,english]{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} \usepackage[latin1]{inputenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{babel} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \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 \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.7in} \setlength{\parindent}{0in} \setlength{\parskip}{0.05in} \setlength{\columnseprule}{0.2pt} \makeatother \makeatother \makeatother \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. Earlier problems tend to be easier.} Notation: {}``PLN{}'' means {}``printed lecture notes,{}'' and {}``LG{}'' means {}``Leon-Garcia.{}'' \textbf{1.} (20) Look at Fig. 6.85 of LG. B1's table is incomplete now, but later the one remaining blank entry will be completed. Fill in the blanks in the following with a correct set of answers (there may be some blanks in which more than one answer would work): The missing entry will be completed when Node \_\_\_\_\_\_ sends a frame to Node \_\_\_\_\_. Then the newly-completed entry will show address \_\_\_\_\_\_\_ and port \_\_\_\_\_\_\_\_. \textbf{2.} Consider the \textbf{traceroute} example on p.4 of the PLN unit on routing issues. Fill in the blanks with numbers: \begin{itemize} \item (a) (5) The \textbf{traceroute} program sent out \_\_\_\_\_\_\_\_ messages and received \_\_\_\_\_\_\_. \item (b) (5) At the IP level, the initial values of byte offset \_\_\_\_\_\_\_ in the messages sent by \textbf{traceroute} varied from \_\_\_\_\_\_\_\_\_ to \_\_\_\_\_\_\_\_\_\_\_\_. \end{itemize} \textbf{3.} (15) Suppose I am downloading something from the Web, and during the download my browser gives me continuing reports on the speed of the download, e.g. {}``4K read, at 1.2K bytes per second.{}'' The speed does seem to increase as we go along. Fill in the blanks: The low speed at the beginning is an example of a technique whose official name is \_\_\_\_\_\_\_\_\_\_\_\_. However, the speed will accelerate rapidly near the beginning of the download, increasing by a factor of approximately \_\_\_\_\_\_\_\_\_ with each segment sent by the server. \textbf{4.} Look at the analysis of ring latency on p.415 of LG. \begin{itemize} \item (a) (5) LG says that the ring {}``...can hold more than two maximum length frames!{}'' Find the exact value which would replace 2 in this sentence if LG had been exact. (Write your answer as an arithmetic expression, not as a finished number. E.g. write \( 9+\frac{10}{2.5} \)instead of 13.) \item (b) (5) Find the value in seconds of the parameter \( \alpha \) from our PLN unit on FDDI. \end{itemize} \textbf{5.} (10) Suppose we are writing code which will be used in the Ethernet driver for a bridge. Assume that the program contains a global variable IncomingBPDU, declared as \begin{verbatim} char *IncomingBPDU; \end{verbatim} which is an array containing the BPDU which has just arrived at the card. There is a global \textbf{int} variable IncomingPort which gives the port number into which this BPDU came. Suppose there is also a global variable MyBPDU, declared also of type \textbf{char {*}}, which contains the BPDU which this bridge has been sending. Assume that the Sender ID, Claimed Root ID, Distance to Root and Age fields consist of one byte each. There is also a global \textbf{int} variable KeepOriginatingBPDUs, which is 1 if true and 0 if false, and an i\textbf{nt} variable NPorts, where this bridge's ports are numbered 0 to NPorts-1. Assume that you have available a function whose declaration is \begin{verbatim} void SendToPort(char *F, int Port) \end{verbatim} which sends the BPDU data pointed to by F through the specified port. Write C code which will do the proper processing of an incoming BPDU. \textbf{6.} Consider the worst-case analysis for \( \tau _{actual} \) in our PLN unit on FDDI. \begin{itemize} \item (a) (10) What is the value of \( \tau _{actual} \) when the token makes its second visit to \( N_{1} \)? \item (b) (10) At what time will \( N_{4} \) start to send the token to \( N_{5} \), after the token's second visit to \( N_{4} \)?\\ \\ In parts (c) and (d), suppose in the third cycle of the token we have the following situation: Each \( \sigma _{i} \) is 1.0; each node has 2.0 amount of asynchronous data ready to send if given the chance to do so; each node either has 1.0 amount of synchronous data to send, or none at all, with probabilities p and 1-p, respectively; the value of \( \beta \) is negligible. \item (c) (10) Find the probability that \( N_{3} \) will be able to send 2.0 amount of asynchronous data. \item (d) (5) What are the smallest and largest possible values of \( \tau _{actual} \) when the token visits \( N_{1} \) for the fourth time, if there are four nodes total on the ring? \end{itemize} \textbf{Solutions:} \textbf{1.} S5, S1-S3, S5, 2 \textbf{2.a.} 45, 43 \textbf{2.b.} 8, 1, 15 \textbf{3.} {}``slow start{}'', 2 \textbf{4.a.} \( \frac{105,000}{36,000} \) or \( \frac{105,000}{40,000} \) \textbf{4.b.} \( \alpha =10\, bit\, times=10\, bits\cdot \frac{1}{100\times 10^{6}\, bps}=10^{-7}\, sec \) Or, divide the entire ring length by 500 times the propagation speed. \textbf{5.} \begin{verbatim} if (*(IncomingBPDU+1) < *(MyBPDU+1) || ...) { ~~~*(MyBPDU+1) = *(IncomingBPDU+1); ~~~... ~~~for (I = 0; I < NPorts; I++) ~~~~~~if (I != IncomingPort) ~~~~~~~~SendToPort(IncomingBPDU,I); ~~~KeepOriginatingBPDUs = 0; } \end{verbatim} \textbf{6.a.} From the chart, \( \tau _{actual}=(\beta +\sigma _{0}+\sigma +\beta _{0})-\beta _{0}=\beta +\sigma _{0}+\sigma \) . \textbf{6.b.} The token will arrive at \( N_{4} \) at time d after it arrivs at \( N_{1} \), where \( d=\sigma _{1}+\beta _{1}+\sigma _{2}+\beta _{2}+\sigma _{3}+\beta _{3} \). \( N_{4} \) will then send for \( \sigma _{4} \) amount of time, and then send the token. So, the latter event occurs at time \[ \beta +\sigma +\sum ^{3}_{i=0}(\sigma _{i}+\beta _{i})+\sigma _{4}\] \textbf{6.c.} There are only two situations in which \( N_{3} \) will be able to send 2.0 amount of asynchronous data: \( N_{0} \) has data, \( N_{1} \) and \( N_{2} \) don't, \( N_{3} \) does; \( N_{0} \), \( N_{1} \) and \( N_{2} \) have no data, \( N_{3} \) does. (In the latter case, \( N_{3} \) could even send 3.0 amount of asynchronous data, but it will not have that much.) No other case works. For example, if \( N_{0} \) and \( N_{1} \) have nothing to send but \( N_{2} \) does, then the latter will {}``hog{}'' all the accumulated earliness, so none will be left for \( N_{3} \). So, the probability in question is \[ p^{2}(1-p)^{2}+p(1-p)^{3}\] \textbf{6.d.} The minimum possible is 0.0, which occurs if during round 3 \( N_{1} \), \( N_{2} \) and \( N_{3} \) have nothing to send, and then \( N_{0} \) has nothing to send in round 4. The maximum possible is 5.0, which occurs if for example during round 3 \( N_{0} \), \( N_{2} \) and \( N_{3} \) have nothing to send but \( N_{1} \) has something to send and then \( N_{0} \) has something to send in round 4. Here is what will happen in that situation: At the beginning of round 3, the token arrives to \( N_{0} \) an amount 4.0 late; \( N_{0} \) sends nothing, so the token arrives 1.0 early to \( N_{1} \); the latter then sends 2.0 (1.0 synchronous data, 1.0 asynchronous), so the token arrives on time to \( N_{2} \); but the latter sends nothing, as does \( N_{3} \), resulting in the token arriving 2.0 early to \( N_{4} \) in round 4; the latter sends 3.0, for a total \( \tau _{actual} \) for \( N_{1} \) of 2.0+3.0 = 5.0. \end{document}