ls -lt | more CIS 451, Fall 2003 Dr Ott. For reading assignments see the page ``Books and other reading''. Because there were additional registrants on 09/08 the first quiz will be on Tuesday Sept 23. Homework to be handed in is due every Tuesday. There will be an envelope on the door to the Internet Laboratory, GITC 4325. Put the homework in that envelope, every Tuesday, BEFORE 18:00. (6:00 pm). Because previous instructors allowed a ``paper study'' project, I will allow that also, this semester. A list of possible topics is available elsewhere on this webpage. I prefer projects that include some programming. Ms Kanigiluppai is writing a simulation of a ``go back n'' protocol. It will be discussed in class. A possible project is to take that simulation and use it to study (predict) the relationship between Propagation Delay, Serialization Delay, Window, drop probability, damage probability, and throughput. The project then must include a discussion of why the results make sense. A more ambitious project would be to take the simulation and modify it to study a ``Selective Repeat'' protocol. One student will do a project in the Internet Laboratory, studying (by measurement) for TCP the relationship between Round Trip Time, packet loss probability, and throughput. --- Friday Sept 05, 2003: Go to http://www.prenhall.com/tanenbaum , get and print the figures for Ch 1, get and print the powerpoint slides for Ch 1. (Black and white is OK). If you can not do this: ask GOOD questions on Friday 09/05, and get the prints for Tuesday 09/09. Go to http://www.iana.org , Look at the list of ``ethertypes''. (On that page they are called ``ethernet numbers''). Which ones do you recognize? (Do not hand in). --- Tuesday 09/16: Hand in Tanenbaum p 81 problems 1, 3, 11, 17, 19. --- Tuesday 09/23 Hand in Tanenbaum p 81 problems 5, 6, (more to be assigned 09/16). Quiz: Tanenbaum pp 1 - 108. (I MAY make minor deductions in this up to 09/19) All classnotes up to and including 09/19. (For sure). I often ask questions based on homework. --- Henceforth, quizes will be unannounced. Every session a chance of 25 - 30%. Future quizes are likely to be smaller than the one on 09/23. --- Tuesday 09/30 Hand in Tanenbaum p 83 problems 28, 29. Hand in Tanenbaum p 177 problems 1, 2, 3. Hint for problem 3: Pretend you are sampling at the Nyquist rate, and that every sample is represented with an accuracy of 4 levels, without error. How many bits per sample do you need to get 4 levels? --- On the next quiz (whenever it is) it is likely that questions from quiz 1 will be repeated (with minor modifications). Tuesday 10/07 Hand in Tanenbaum p 177 problem 5. p 178 problem 9. p 243 problem 1. Hint for p 243 problem 1: Assume all 10 frames are sent without error detection or error correction. Once all 10 frames have arrived, error detection is done on the whole message. If an error is detected, all 10 frames must be re-transmitted. How many times (in average) are all 10 frames transmitted? How many frames (in average) are transmitted before the message has arrived intact? Also solve and hand in the following variation on p 243 problem 1: Now do error detection on each frame separately. If a frame contains an error, it must be retransmitted (until it has arrived intact). Once every frame has arrived intact once, the message has arrived. How many frames (in average) are transmitted before the message has arrived intact? - Do and hand in the following problem: Pretend you are doing error detection using the Internet Checksum. Only, you do it based on 8 bit words. (Not 16 bit words as in the Internet: to make it easy to do it by hand). Suppose you want to send the message (in binary) 10101100 00110011 1101 compute the 8 bit checksum you add to the message. Assume no error occurs. What is the computation that is done at the destination to check there is no error? (Make sure you write this down in such a way that it is easy to see what you are doing. This also holds if this or any question is asked in a quiz!). --- There will be a third quiz on either Tuesday 10/14 or Friday 10/17. (Depends on extraneous circumstances, wise people count on 10/14). To prepare: Study all problems in quiz 1 and quiz 2. Study the ``model solutions'' for those quizes on this website. Study the ``sample questions'' on this website. Study the classnotes on ``stop and wait'' and ``sliding window'' protocols. There WILL be questions on the use of Nyquist's result, Shannon's result, manipulations with decibels. Somewhat similar to the questions in previous quizes. No other homework for 10/14. --- Homework for 10/21: Do the assigned reading. (See the ``Books, and other reading'' page). Choose a partner for your project, and choose a project topic. Let me know who your partner is and what your topic is. Make sure to run the simulation at least once and check that the output ``makes sense''. If the output does not make sense, make sure to ask questions. Preferred by email, questions in class are OK, too. No further homework for 10/21/2003. --- Homework for Friday 10/31: Do the assigned reading. (See the ``Books, and other reading'' page). Hand in: p 81 problem 10. There is likely to be a miniquiz on Friday 10/31. --- Homework for Tuesday 11/04: Do the assigned reading. (See the ``Books, and other reading'' page). Hand in: p 83 problems 25, 26, 27. Do and hand in: A. Draw the Phase-Amplitude diagram for QAM-16 with 1 phase and 16 amplitudes. What other name would you give this scheme? In the language Tanenbaum uses: How many different SYMBOLS are possible in this scheme per SAMPLE ? (or per baud)? What is the number of bits per baud for this scheme? B. Draw the Phase-Amplitude diagram for QAM-16 with 16 phases and 1 amplitude. What other name would you give this scheme? In the language Tanenbaum uses: How many different SYMBOLS are possible in this scheme per SAMPLE ? (or per baud)? What is the number of bits per baud for this scheme? --- Homework for Friday 11/07. More reading has been assigned. See the ``Books and other reading'' page. Do and hand in: (1) There are two computers, called S (Source) and D (Destination). They are connected by a 20 km long link (full duplex, used only between S and D). The link has a data rate of 100 Mbit/sec and the speed of the signal on the link is (2/3)*c . Practically speaking, we have only 1500 Byte dataframes from S to D, and only 50 Byte ACKframes from D to S. This includes headers, trailers, ``wrappers'', etc. D acknowledges every dataframe it receives as soon as the whole frame is in. If S and D use a ``Sliding Window'' protocol, what window size (in frames) would you recommend? WHY? (The ``why'' is much more important than the actual answer, so try to be simultanously concise and very clear!) (2) In a bit-oriented protocol, we use the flag 01111110 , to indicate beginning and end of a frame. (I usually would write this as 0111 1110 , for readability). A. Bitstuff the following pattern: 01001111111001111100110011110 B. ``Unstuff'' the following pattern: 0110111110111110110011111001010 C. What is your reaction if asked to unstuff the following pattern? 01001111110010 D. What is your reaction if asked to unstuff the following pattern? 010011111110010 (Be polite!) --- Homework for Tuesday 11/11. Get the ``New Simulation'' to run. That is the one where you do commandline input of parameter values. Do the following two runs: (1) final_frame = 15 (15 data frames) , propagation_delay = .0015 ( .0015 sec, i.e. 1.5 msec) , window = 3 (three data frames) , Frame_size = 7680 ( 7680 data bits. With the header of 320 bits this makes for a frame of 8000 bits) , linespeed = 8000000 (8Mbit/sec) , Time_out = .01 ( .01 sec, i.e. 10 msec) , loss probability = .0 (never a lost frame) , damage probability = .0 (never a damaged frame) , seed_value = 101 (Does not matter, because there is no randomness, since there is no random loss or damage) . Put the output in a file (say) output1. If you have put the executable in a file called simexec2 , the line that causes the execution is simexec2 15 .0015 3 7680 8000000 .01 .0 .0 101 > output1 (order is important!) Please check: Serialization delay of a data_frame is .001 sec (1 msec). Please check: Since ACK and NACK frames are 100 Bytes (800 bits) long, their serialization delays are .0001 sec (.1 msec). Look through the simulation output, check that everything makes sense. (2) The same run as above, with ONE change: Time_out = .006 (.006 sec, i.e. 6 msec, instead of 10 msec). Put the output in a file (say) output2. Find, Describe, and Explain the difference between the two simulation runs. (Between output1 and output2). --- Homework for Friday 11/14/2003. A PPP frame can carry, in its ``data'' part, packets of many different protocols, including IPv4 and IPv6. (Internet Protocol version 4 and Internet Protocol version 6, see CIS 456 or CIS 656 for explanations of IPv4 , IPv6). We already saw in class that if the packet is IPv4 then the PPP Protocol field contains 0021 (in hexadecimal, i.e. in binary 0000 0000 0010 0001). What is the value of the PPP Protocol field if the PPP frame contains an IPv6 packet? Procedure: go to www.iana.org . In the Directory of General Assigned Numbers click on P . Click on PPP Number Assignments . Scroll down until you see the answer. To prove you did all this: copy 5 contiguous lines from the IANA page: The one with the answer, 2 above, and 2 below. Hand in these 5 lines. Feel free to look through the IANA database for whatever stuff hits your fancy. Next miniquiz: I am likely to ask ``What does IANA stand for?'' --- Homework for Tuesday 11/18: Run the simulation with: Final Frame = 22, Prop Delay = .0022 (2.2 msec), W = 3 (frames), databits = 7680 (bits, that makes the whole dataframe 8000 bits), linespeed 8000000 (bits/sec: 8Mb/s), Timeout = .02 (20 msec), loss prob = .0 (never loss), Damage prob = .0 (never damaged frames), seed = 101 (does not matter: nothing random). Put the output in a file. I called mine outW3 , because I am going to vary only the window size. For me, the commandline was simexec2C 22 .0022 3 7680 8000000 .02 .0 .0 101 > outW3 Please note: At time 0.0, the ack for a previous frame one arrives at node 1. No frames are ``outstanding'', so this triggers sending of 1 window. (Three frames: frames 2 , 3 , 4). At time 0.0, frame 2 is sent to buffer 1 and starts service. At time 1 msec that frame has left the source computer. At time 1 musec (.001 msec) frame 3 is sent to buffer 1. It waits there until time 1 msec, then starts service. It is done at time 2 msec. At time 2 musec (.002 msec) frame 4 is sent to buffer 1. It waits there until time 2 msec, then starts service. It is done at time 3 msec. So from time .002 msec until 1 msec, 2 frames are waiting in buffer 1 (frames 3 and 4), and 1 frame is in service (frame 2). We say that during that time the queue length in buffer 1 is 2. (2 frames). The frame ``in service'' (if any) does not count. The interface between buffer 1 and link 1 is idle from time 3 msec until time 5.5 msec. At that time, the ack for frame 2 arrives at node 1. This gives permission to send one more frame. (up to 2 + 3 = 5). Frame 5 is sent to buffer 1 at time 5.5 msec. It starts service right away and is done at time 6.5 msec. Etc. At time 38.5 msec the ack for frame 20 arrives at node 1. This would trigger sending of frame 23 (20 + 3 = 23) to buffer 1. But ``Final Frame'' = 22, so instead the simulation ends at time 38.5 msec. (0.0385 sec). The ``goodput'' of the system is the number of ``good'' dataframes per second. Retransmissions etc do not count. The goodput is computed as follows: Let the source_highest_acked at time t be SHA(t). For t1 << t2, (SHA(t2) - SHA(t1))/(t2 - t1) is a good approximation for the goodput over the time interval (t1, t2). In other words: only dataframes arrived safely at the dest AND acknowledgement received at the source count toward goodput. Questions (hand in 11/18) 1. What is the queue length in buffer 1 at time 1.5 msec? At time 2.5 msec? At time 3.5 msec? At time 5.25 msec? At time 5.75 msec? 2. If this simulation continues ``forever'', what fraction of the time is the interface between buffer 1 and link 1 busy? What fraction of the time is it idle? 3. If this simulation continues ``forever'', what is the ``goodput'' of the system? (In frames / sec). --- Homework for Friday 12/05/2003 Consider the ``Go Back N'' system that was part of the homework for 11/18: Prop Delay = .0022 (2.2 msec), W (Windows) will be a variable, databits = 7680 (bits), linespeed = 8000000 (8 Mb/s), Timeout = .02 (20 msec), loss prob = .0 (never loss), Damage prob = .0 (never damaged frames), seed = 101 (does not matter: nothing random). A. Try to predict the long-run goodput (frames/sec) of this system as function of W WITHOUT running the simulation. (Do not hand in this part). B. Run the simulation with W = 5 and with W = 6 and check whether the outcome you predicted in A is correct. Make sure to choose finalframe high enough but not absurdly high. (Do not hand in this part). C. Give the relationship between W and ``long-run goodput'' for this system, for W from 1 to 10. Add a SHORT paragraph on why this is theoretically correct relationship. DO hand in. --- Also for Friday 12/05: Do and hand in Tanenbaum p 340 problem 16. Hint: for QAM and similar schemes, the bit rate usually is larger than the baud rate. For Manchester encoding the bit rate is less than the baud rate. Why and how much? Look it up in Tanenbaum! Tanenbaum p 340 problem 24. ---