Comp 346 Final Exam Study Guide Answers Final Exam is Tuesday, May 10, 1:45-2:45 7.1/1 (a) throughput is unchanged unless frame size changes. (b) this means decreasing the size of the frame, which decreases throughput (c) increasing frame size increases the data per RTT, and thus increases throughput. 7.2/2 As usual, we assume ACKs are so small as to be negligible. RTT = 40ms; the sender is idle in stop-and-wait for one full RTT. Utilization is 50% when we transmit for 40ms; at 4 bits per ms this is 160 bits, or 20 bytes. If the size of ACKs is taken into account, the cutoff is slightly larger. 20 bytes is a very small packet, but note that any larger packet size has utilization > 50%. 7.3/3 We have 1 frame per ms, with a 270 msdelay. The book does not make clear whether that 270ms includes the 1ms needed to send a frame, or doesn't. I will assume the former. (a) 1/270 (the fraction, that is) (b) 7/270 (c) 127/270 (d) 255/270 7.4/4 (discussed before midterm in class) RTTs for the two links are 40ms and 10ms respectively. The time to send one packet on the AB link is 10ms. The time on the AB link to send one packet and get an ACK is thus 10+40=50 ms; the data rate with a window size of 3 is 3 packets per 50 ms or 16.7 ms per packet. If the BC data rate is X ms per packet, then stop-and-wait has a throughput of 1 packet in X+10ms. Solving X+10 = 16.7 we get X = 6.7 packets per ms, or 3 packets in 20 ms, or 150 bits/ms, or 150kbps. 7.6/14 REJ is for receipt of later packets in the window, when an earlier packet has not arrived. In stop-and-wait, the window size is 1; there are never two packets in the window at the same time. 7.9/17 Diagrams as indicated. Note that there are no packet losses, so the ARQ mechanism does not matter. For (c), A has sent 0,1,2,3,4,5, B has sent ACKs 0, 1, 2, 3, and just sent ACK 4 8.4/4 I have no idea why I included this one. Self-clocking codes are things like Manchester, with enough 0/1 transitions that the receiver will not get lost. Including one such channel in a bunch sent via TDM will not affect the receipt of that channel at all. 8.7/7 The receiving station monitors this frame bit position to be sure that, over a series of several frames, a specified pattern is seen. T1 uses a pattern of 12 bits, so 12 frames must be observed. According to Stallings, p 254, a typical bit pattern is 101010101010. 8.9/9 FDM bandwidth = 4kHz * 24 = 96 kHz PCM = 64kbps; for 24 PCM channels sent using TDM this is 1.536mbps. At 1Hz for 1bps, this is 1.536mHz. 9.4 (a) The period of the PN sequence can't be determined, but the PN sequence is stated to be the same as in 9.5, and 9.5 shows a longer piece of it so the period there *can* be determined. It is 5; the sequence repeats after every 5 values. (b) I assume Stallings is referring to "MFSK", that is, the use of 2^L frequencies to encode all possible combinations of a chunk of L bits. Here, L=2. (c) 2 bits per symbol (the L value above) (d) 4 symbol values * 8 PN-sequence values = 32 frequencies (e) 2 hops per PN sequence value (f) slow; the PN interval is longer than the symbol interval (which in this case is just the frequency interval) (g) I am not sure if Stallings is counting the 32 frequencies as hops, or the 8 values of the PN sequence. 9.5 (a) PN period is 5 (b) Plain FSK; there is one frequency per bit. (c) 2 bits per symbol;this is not so obvious but if it were not so then the selection of frequencies would not make sense (and in particular 16 frequencies would have been enough). The two input bits determine the two low-order bits of the frequency number (eg if the input is 11 then the frequency is one of 3,7,11,15,19,23,27,31), and the 3-bit PN value determines the three high-order bits (5 bits in all, for 32 frequencies). (d) 32 frequencies (e) 1 hop per PN sequence value (f) Fast; PN interval is half the symbol interval. (g) I am not sure if Stallings is counting the 32 frequencies as hops, or the 8 values of the PN sequence. Chapter 11 11.2ab/2ab (a) Call roundup(Y) the smallest integer >=Y. THen the message requires N=roundup(X/L) cells. Overhead consists of N*H headers plus N*L-X padding in the last packet. (b) This is not answerable unless one knows the maximum length of a cell; otherwise, one could send the entire message in a single cell with overhead H+Hv. If the maximum cell size is L, then what one saves with variable-length cells is the padding in the last packet, and the total overhad is N*(H+Hv). 11.3b/3b The time to acquire L bytes from a data source that generates R bytes/sec is just L/R. 11.5/4 (a) BOM = Beginning Of Message, the first cell of the message. If the receiver fails to get this, the message is lost. (b). COM is Continuation of MEssage, one of the middle cells. If this is lost, then the MID field in the next cell shows an increase of +2 instead of +1 and the receiver can thus detect that a cell was skipped. (c) The loss is simply not detectable by ATM (d) Same as (c) 11.6/5 (a) if the End of Message cell from the first message is lost, the receiver sees a sequence of Continuation cells (of the first message) and then the BOM (beginning of message) of the second message. The partial first message is discarded, because it is missing EOM, and the second message is received correctly (unless there are further errors). (b) If the message1 EOM and the message2 BOM are both lost, there is still a gap in the 4-bit sequence number field, and this enables the receiver to reject the messages. Note that the receiver *thinks* it is rejecting a single large message, though. 11.7/6 (a) A single-bit error in one cell is detected by a bad CRC checksum for the entire message (sent in the final cell). (b) This is one of the first/middle cells. Again, the final CRC will almost certainly be bad, resulting in rejection of that message. (c). If the final cell of a message is lost, then the receiver sees a concatenation of that message and the following message (minus the one missing cell). However, the crc of the second message is again almost certainly wrong for the concatenated sequence, and so both messages will be discarded (note that the receiver thinks it is discarding only a single message). ================ Recall the GCRA algorithm (this same definition will be given to you on the exam): GRCA(T,tau): Avg time T between packets, tau = variation Suppose current cell is expected at time tat, actually arrives at t Case 1: t < tat - tau (too EARLY): NONCONFORMING; do not change tat Case 2: t >= tat - tau: CONFORMING; newtat = max(t,tat) + T > Consider the following set of packet arrival times. > > 0 0 3 5 7 9 16 16 > > 1. For GCRA(3,2), which packets are conforming? We proceed by calculating the tat values. A packet is conformant if it arrives no more than tau before its tat; in that case the next tat is max(t,tat)+T. If a packet is nonconformant, tat does not change conf: y n y y y n y n t: 0 0 3 5 7 9 16 16 tat: 0 3 3 6 9 12 12 19 Note the last one in particular; the tat is 16+3, not 12+3. > 2. For GCRA(3,1), which packets are conforming? conf: y n y y n y y n t: 0 0 3 5 7 9 16 16 tat: 0 3 3 6 9 9 12 19 > 3. For GCRA(2,10), which packets are conforming? conf: y y y y y y y y t: 0 0 3 5 7 9 16 16 tat: 0 2 4 6 8 10 12 18 (fixed) > 4. For a GCRA(4,25) flow, > (a) how many packets can be sent as a burst at T=0? > (b) if that burst is sent, at what time can the next packet be sent? Here is the "fastest" sequence. For a "fastest" sequence, the nth tat value will always be n*T. We send at t=0 as long as tat <= tau=25; after that point, t = tat - tau. t: 0 0 0 0 0 0 0 3 7 11 15 tat: 0 4 8 12 16 20 24 28 32 36 40 > 5. For each of the ATM traffic classes CBR, rt-VBR, nrt-VBR, and UBR, > list the Quality-of-Service (QoS) and Traffic parameters they request. CBR and rt-VBR specify maxCTD. Everyone specifies PCR (Peak Cell Rate) and CDVT (Cell Delay Variation Tolerance). The two VBR classes also specify SCR (sustained cell rate) and BT (Burst Tolerance); the traffic must conform to GCRA(1/SCR, BT). > 6. Outline the differences between AAL3/4 and AAL5 in terms of: > (a) data bytes per packet > (b) bits used in ATM header > (c) error detection (a). 44 v 48 (b). AAL5 fills the ATM cell body with user data; there is no room for control information. One bit from the ATM header is taken over for use in marking the final cell of a packet. Note that header bits are "expensive" in that all are pretty much accounted for. > 7. Suppose an ATM connection meets GCRA(6, 18). > (a) What is the maximum size of a packet burst? 4 packets: t: 0 0 0 0 tat: 0 6 12 18 > (b) Assume the available output bandwidth is 1 packet per 4 time units. > How long does it take to send a packet burst? 16 = 4 packets * 4 time_units/packet > (c). What outbound bandwidth is needed if the maximum delay > is 8 time units? 2 time_units per packet (T=2). > (d). What outbound bandwidth is needed if the maximum delay > is 20 time units? 20 time_units / 4 packets = 5 time_units per packet > 8. Compare and contrast ATM connection admission with RSVP. Note that the question is specifically about connection admission. ATM has to take maxCTD into account; RSVP allows in effect only nrt-VBR-type traffic (senders specify a Sustained Rate and Burst), but in practice rather precise (and rather small) delay bounds can be calculated. > 9. Give an equivalent definition of GCRA in terms of token/leaky > buckets. The bucket fills at a rate of 1 units of fluid per time unit. The maximum capacity of the bucket is T+tau. A cell is conformant if there is T units of fluid available; if so, that amount is subtracted from the bucket. > 10. Explain the differences and similarities between admission > control and policing. Both can be addressed by using CGRA (and maxCDT). Policing, though, is equivalent to verifying that all packets are conformant (or marking the nonconformant ones, at least). Admission control has to do only with determining whether a connection can be guaranteed the service it asks for, assuming that it stays within its stated limits.