Computer Science 825 Quiz 1 Name _______________________ Terminology: the very highest layer is the APPLICATION LAYER = Layer N the very lowest layer is the PHYSICAL LAYER = Layer 1 1. a. Which of the seven layers of the ISO-OSI model is the LOWEST layer that is typically found in each host computer but not found in an IMP. b. At which layer is it necessary that a common protocol be supported within all hosts and IMPs of a network. 2. Protocol headers used by a layer N are handled by layer K (K > N) as follows: a. The are removed before b. They are treated as user data. the packet arrives at Layer K c. They are deleted by layer K. 3. For two separate implementations of a specific network architecture to interoperate correctly it is necessary that: a. Intra-level peer protocols b. Internal inter-level interface be compatible definitions be compatible at both end-points. c. Both a and b. d. Neither a or b. 4. Suppose a channel is equipped with high and low pass filters that pass only harmonics in the range 32,000 hz to 48,000 hz. On this channel what is the MINIMUM sampling rate required to reconstruct the exact signalling function? 5. Suppose a noise-free channel has a Bandwidth of 20,000 hz and a 16 state signalling scheme is in use what is the maximum data rate of this channel? 6. a. What is the maximum SNR in DB required to carry a 40000 BPS over a 5,000 hz bandwidth channel. b. How many signalling states must be used. Recall the Bell 212A modem discussed in class. It signalled using 4 phase angles, 45, 135, 225, and 315 degrees. 7. When a long burst of 00000000000000000000 is transmitted, a. The modem will emit a b. There will be a +45 degree pure sine wave of the form phase shift in the signal f(t) = sin(wt + 45dg) every bit time. for the duration of the burst c. There will be a +45 degree phase shift every other bit time. 8. The use of the phase angles 0, 90, 180, 270 would not be desirable. One of the above numbers is the source of the problem. Which one is it? a. 0 b. 90 c. 180 d. 270 9. In the model of synchonous transmission that we described in class a. the sender USART and modem b. the clocks in both USARTS were driven by the sender and modems were derived modem and the receiver end from the clock in the clocks where driven by the receiver USART. receiver modem. c. the clocks in both USARTSs d. the clocks in both USARTS and modems were derived and modems were derived from the clock in the from the clock in the sender modem. receiver modem. 10. The main reason digital channels have much lower error rates than analog when used over long distances is: a. Digital signalling is baseband c. Digital signals are amplified instead of analog. rather than regenerated. b. Digital signals are regenerated d. Digital channels have much higher rather than amplified. SNR's than analog. 11. The term "asynchronous communication" is commonly used to refer to channels in which: a. The sender and receiver b. The sender and receiver resynchronize clocks are unsynchronized between every bit transmitted. c. The sender and receiver resynchronize at the start of every byte transmitted. Computer Science 825 Quiz 2 Name _______________________ 1. Suppose a network has links that carry data at a rate of 10,000 bits per second. Suppose Node A and Node B are connected by a path that requires 10 hops (transmissions). a. What is the minimum time required to send a 200,000 bit message from A to B if message switching is used. b. Suppose packet switching is used and no additional bits are required for headers. How long will it take to send the entire message if 2000 bit packets are used. 2. Suppose headers of length H bits are used in the packet switching scheme described above. Suppose packet size is P (where P now includes header+data bits). Under this new scheme the time to send a complete packet is: a. 10000 * P b. P / 10000 c. 10000 / (P + H) d. 10000 / (P - H) 3. Under the new scheme the total number of packets that must now be transmitted is: a. 200,000 * P b. 200,000 / P c. 200,000 / (P + H) d. 200,000 / (P - H) 4. Suppose a PCM transmission system has a bit rate of 2^20 bps and can carry frequencies between 0 and 2^15 Hz. Into how many discrete levels can the input signal be quantized by the A-D converter. 5. The use of very small slot sizes in TDM is a. Inefficient and shouldn't b. Generally shouldn't be used for be used in either STDM or ATDM SDTM but is OK for ATDM c. Generally shouldn't be used d. Perfectly OK for both for ATDM but is OK for STDM 6. Measurements of an infinite user slotted aloha channel show that 40% of the slots are idle. What is the throughput, S. 7. If k stations share a CSMA-CD bus and the probability that any station will transmit on a given contention slot is "p", then the probability that a successful transmission will take place in a slot is: a. p c. k * p * (1 - p) ^ (k - 1) b. p * k * (1 - k) ^ (p - 1) d. None of the above. 8. If the probability that one station successfully transmits in a slot is "A". The expected value for the number of slots between successful transmissions is: a. A ^ j * (1 - A) ^ (j - 1) b. Summation j * (A ^ j) (1 - A)^ (j - 1) j=0,infinity c. Summation j * A * (1 - A)^ (j - 1) d. None of the above j=0,infinity 9. Suppose the value "t" represents the ONE WAY signal propogation delay between two stations on an ethernet and that the two stations transmit and cause a collision. Suppose station 1 began transmitting first and station 2 began transmitting second. Hint: the correct answers can be drawn (w/ replacement} from the following "urn": {0 t/2 2t 8t} \ t/4 4t / \____t____/ a. What is the shortest possible amount of time after station 1 starts transmitting that station 1 can hear the collision? b. What is the longest possible amount of time after station 2 starts transmitting that station 2 can hear the collision? c. What is the shortest possible amount of time after station 2 starts transmitting that station 2 can hear the collision. 10. In a dual persistent protocol a station transmits with prob p when it initially sense a channel idle and with prob q when it has to wait for a busy channel to become idle. The proper relationship between p and q is: a. p > q b. p < q c. p = q d. q = 1 and p < q Computer Science 825 Quiz 3 Name _______________________ 1. A token ring monitor will set the "M" bit on whenever it sees: (Check all that apply) ___ a. A high priority data frame. ___ b. A high priority token ___ c. A 0 priority token. 2. In the TOKEN BUS it is necessary for a station to know and use its PREDECESSOR's address when: a. It wants to issue SET_SUCCESSOR b. It wants to issue SOLICIT_SUCCESSOR and leave the logical ring. to invite a new station to join c. In both cases d. In neither case. 3. When a station issues WHO_FOLLOWS, the frame contains a. The address of the station's b. The address of the station's present successor. present predecessor c. Both d. Neither 4. Suppose all traffic has EQUAL priority. Order the following from 1 to 4 (1 = lowest, 4 = highest) in terms of expected transmission latency (= avg time for a station to successfully put the frame at the head of the transmission queue on the wire) ____ a. Token Ring under very low loads. ____ b. Token Ring under very high loads. ____ c. Ethernet under very low loads ____ d. Ethernet under very high loads 5. Suppose the following bit sequence is subject to SDLC style bit stuffing.. How many bits will actually be transmitted? 2 1 65432109876543210987654321 -------------------------- Last bit --> 11100111111101111011111000 <- First bit transmitted 6. Suppose a 15 bit codeword with ODD parity is being used in a single bit hamming ECC. Suppose the following codeword is received. X 0 1 0 1 X 1 1 1 1 0 1 0 -------------------------------------------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a. Fill in the missing ECC bits above .. (Don't worry about the ECC bits that are X'ed out!) b. Suppose a single bit Hamming ECC is to be performed on a 511 bit codeword. How many bits are in each of the 10 parity checked groups (include the parity bit itself). c. How many bits does any pair of parity checked groups have in common with each other? c. Suppose a two bit error occurs. Circle the correct description of the result. 1. The fact that there is a two error can be detected, but the error can't be corrected. 2. The two bit error will be undetected and the value that results from the correction process will be a legal code word but it will be the wrong one. 3. The two bit error will be undetected and the corrected value will be either the wrong codeword or it might be the correct codeword. 4. The two bit error will be undetected and the corrected value MAY be an illegal code word. d. What is the minimum Hamming distance of a code that is capable of doing triple bit error correction? 7. Suppose a codeword consists of 2400 bits and a Hamming Code is used to correct bursts of 40 bits or less. How many bits in the codeword must be used as ECC bits. (Schemes involving fractional bits are not likely to be warmly received.) 8. When the SDLC standard bit stuffing is used the loss of the end flag (framing character) can be detected by: a. The appearance of some 0's b. The appearance of some 1's where where there should only be 1's there should only be 0's. c. The appearance of all 1's d. The appearance of all 0's where where there should be a mix of there should be a mix of 1's 1's and 0's and 0's. Computer Science 825 Quiz 4 Name _______________________ 1. Consider the following shift register: a. What will be the contents of the shift register after the input digits 1 and 1 are processed. b. What generator polynomial is represented by this shift register. c. Does this shift register represent standard long division or is it the pre-multiplying version? (Yes is not the correct answer). 2. Suppose A generator polynomial of x + 1 is used. Answer the following T or F ___ a. Some, but not all double bit errors in which the 2 error bits are adjacent in the message will be detected. ___ b. All seventeen (not necessarily adjacent) bit errors can be detected. ___ c. Some double bit errors in which the error bits are of the pattern E O E (the two broken bits are separated by EXACTLY one "OK" bit) will be detected. 3. Suppose a generator polynomial of G(x) = x^4 is used. G(x) can detect (check all that are correct) ___ a. E(x) = x^3 + x ___ b. E(x) = x^6 + x^2 ___ c. E(x) = x^8 + x^4 4. In protocol 3, frames's had sequence numbers but ACKS did not. Protocol 3 could fail in the presence of: a. ACK's that were lost b. ACK's that were excessively delayed c. Frames that were lost. d. Either a or b 5. When protocol 3 failed, the failure resulted in: a. The loss of 1 frame b. The loss of 1 frame and the duplication of 1 frame. c. The duplication of 2 d. The loss of 2 frames frames. 6. Consider the following simplex connection.. Since the connection is simplex the sender side needs only nxtack and nxtsend state variables and the receiver side needs only nxtrecv. Assume that: the "ACK next frame expected" convention is used; the protocol uses sender and receiver window size = N; sequence numbers never wrap; and NO timeout and retransmits occur. nxtack --------------------> nxtrecv nxtsend Answer the following T or F. At any instant in time: ____ a. nxtack must always be <= nxtsend ____ b. nxtrecv may be = nxtack ____ c. nxtrecv may be > nxtsend ____ d. nxtsend may be < nxtack 7. Suppose that a satellite channel is in use and that the ROUND TRIP propogation delay is 540 ms. Suppose bit transmission rate is 100,000 bits per second and packets are 1000 bits long. a. What will the efficiency of this channel be if stop and wait protocal is used. b. How large (in packets) must the SWS be in order to obtain 100% efficiency if the channel is guaranteed error free. (i.e. give me the MINIMUM SWS). c. How large (in packets) must the RWS be in order to obtain 100% efficiency if the channel is guaranteed error free. 8. The principal factor used in deciding between the use of stop and wait protocol and a go back N protocol should be a. the propogation delay b. the error rate of the channel on the channel c. both equally important d. neither at all relevant. 9. The principal factor used in deciding between the use of a go back N protocol and a selective reject protocol should be a. the propogation delay b. the error rate of the channel on the channel c. both equally important d. neither at all relevant. Computer Science 825 Quiz 5 Name _______________________ 1. A buffer in the protocol discussed in class cycled though a number of queues.. Associate each transition with the process that caused it. (Some answers may be used more than once or not at all). ____ 1. Sender window to free a. Network layer process list. ____ 2. Network input to link b. Queuemsg process station output c. Timeout process ____ 3. Link output to sender window. d. Writelink process e. Readlink process 2. Suppose that a 3 bit sequence number were being used in the protocol discussed in class. In that case the LARGEST value that the semaphore "numslots" could be safely initialized to is: a. 2 b. 3 c. 7 d. 8 3. The value of the counting semaphore "wpcount" (that counted the number of packets waiting to be written is given by: (assume no sequence # wrap). a. nxtqueue - nxtack b. nxtqueue - nxtsend c. nxtsend - nxtack d. none of the above 4. As written, the protocol presented in class becomes deadlocked when: a. any readlink process is blocked b. all readlink processes are in dequeue due to lack of free blocked in dequeue due to buffers. lack of free buffers c. the network layer input process d. Either (a.) or (c.) occurs blocks in dequeue because its input queue is empty 5. When a process becomes blocked on a counting semaphore it necessarily depends upon some OTHER process to signal the semaphore and unblock it. For each of the following identify the process that is responsible for unblocking it AFTER IT BLOCKS ON A COUNTING SEMAPHORE. ___ a. network layer 1. queuemsg ___ b. readlink 2. readlink ___ c. writelink 3. writelink 4. network layer 6. Supervisory frames in SDLC carry a. Both sequence numbers and b. Sequence numbers but no ack ack numbers. numbers c. Ack numbers but no sequence d. No numbers at all. numbers. 7. Which of the following is NOT a use of supervisory frames in SDLC a. Sending a standalone ack b. Seeing if another station is back up after a crash. b. Polling d. Telling another station to temporarily stop sending. 8. The address byte in an S/HDLC packet always carries the address of a. The sender b. The receiver c. The primary station. d. The secondary station. 9. The "failure" that the SDLC unnumbered protocol is susceptible to is: a. Undetected loss b. Undetected duplication of of a frame. a frame. c. Reordering of frames d. Both a. and b. 10. Suppose a new connection is established between the Host at router "A" to the host at router "D" and that it follows the route H->A->E->C->D->H. Update the circuit assignment tables in the diagram. Computer Science 825 Quiz 6 Name _______________________ 1. Let N = number of nodes in a network and M = the average number of links / node. a. The size of each routing update packet transmitted in an SPF net is proportional to 1. M 2. N 3. N ^ 2 4. N * M b. The size of a routing info packet in Bellman-Ford is of order 1. M 2. N 3. N ^ 2 4. N * M c. The number of routing packets transmissions (for the entire network) at each Bellman-Ford exchange is proportional to: 1. M 2. N 3. N ^ 2 4. M ^ 2 5. N * M 2. In a network that uses SPF suppose station B constructs the following cost matrix To A B C D E A 0 2 - 3 4 F B 5 0 6 - 9 r o C - 2 0 7 2 m D 3 - 7 0 4 E 1 9 1 5 0 Draw the routing tree from node B to all destinations. Label the ARCs of the graph in the order in which they are made permanent in the SPF algorithm (Break any ties alphabetically). 3. Suppose the Bellman-Ford routing algorithm is being used and station B receives the following routing updates from neighbors A, C and E A C E Cost VIA A 0 6 1 | --------------------------------- B 6 11 2 | -------------------------------- C 3 0 4 | -------------------------------- D 8 5 2 | -------------------------------- E 2 8 0 | -------------------------------- F 11 2 7 | -------------------------------- Suppose BA delay = 4, BC delay = 6 and BE delay = 3. Complete the routing table for B. (Break ties alphabetically) 4. Order the following broadcast algorithms according to the number of packet transmissions needed to complete a broadcast (1 = least transmissions; 3 = most). ______ a. Reverse Path Forwarding ______ b. Flooding ______ c. Spanning tree. 5. Suppose that "leaky bucket" and "token bucket" admission control algorithms support identical maximal long-term sustained admission rates. Which of the following best characterizes their response to short high-rate arrival bursts: a. Leaky bucket allows short b. Token bucket allows short term admission rate to exceed term admission rate to exceed long term rates but token bucket long term rates but leaky bucket does not. does not. c. Both allow short term admission d. Neither allows short term rates rates to exceed long term rates. to exceed long term. 6. Which routing algorithm is used by the spanning tree bridge if the location of the destination node is UNKNOWN? a. Spanning tree. b. Flooding c. Backward learning. d. Shortest past first. 7. Which routing algorithm does the spanning tree bridge employ in order to minimize the occurrences of destination unknowns. a. Spanning tree. b. Flooding c. Backward learning. d. Bellman-Ford. 8. Which of the following best characterizes "self-similarity" in network traffic arriving at a router: a. The variance in the number b. The mean of the number of of packet arrivals per packet arrivals per second second is large. is large. c. There is a signficant statistical correlation in the number of arrivals at time N+j with then number of arrivals at time N, for j = 1, 2, 3, ... 9. Suppose three traffic arrival streams have the same mean arrival rate. Order the streams from 1 (smallest queue length) to 3 (largest queue length) according to the the following characteristics: ____ a. High variance ... no self-similarity ____ b. High variance ... high degree of self-similarity ____ c. Very low variance ... high degree of self-similarity. Computer Science 825 Quiz 7 Name _______________________ 1. In the old "class oriented" IP address assignment scheme, which class supported roughly 2^14 distinct networks: a. Class A b. Class B c. Class C d. Class D 2. In the new class-less inter-domain routing (CIDR) strategy the length of the prefix associate with an old-style Class C network would be: a. 16 bits b. 8 bits c. 32 bits d. 24 bits 3. We discussed in class two functions performed in IPV4 that were totally eliminated in IPV6. Identify both of them. a - b - 4. In IPV4 fragmentation and reassembly are performed as follows: a. Both can occur anywhere b. Source host must fragment but reassembly is done just past the "bottleneck" router c. Fragmentation may occur d. Fragmentation always occurs at anywhere but reassembly occurs the source and reassembly at only at the destination. the destination. 5. In IPV4, precisely why must router RECOMPUTE the header checksum? 6. Consider the bridged network shown. Circles are bridges and lines LANs. Mark EACH interface on each bridge "R", "D", or "N" depending up whether it is the "Root Port", or "Designated bridge port for a LAN" on "NOT in the spanning tree". 7. The number of distinct ATM addresses (not connection id's) is: a. 1 b. 2^8 c. 2^20 d. 2^160 8. It is necessary to include a full ATM address in (circle all that apply) a. All cells flowing on PVC's b. All cells flowing on SVC's c. In AAL5 CS trailers d. In Q.2931 call setup messages 9. Which of the following is NOT one of the factors used in defining the ORIGINAL ATM service categories a. reliable vs non reliable b. real time vs non real time service c. connection oriented vs d. constant vs variable bit connection less service rate 10. Since AAL5 frames have no SAR headers or trailers, it is necessary that the CS trailer be: a. Right justified in the last b. Left justified in the cell of the frame. last cell of the frame c. Present in EVERY cell of the d. Both b and c frame 11. Suppose a 242 byte packet of user data is to be transmitted using an AAL5 frame. a. How many ATM cells will be required. b. How many bytes of padding will be in the last cell. Computer Science 825 Quiz 8 Name _______________________ Suppose a 3 way handshake is being used to establish a connection. Let SYN-1 represent a packet that carries SYN and no ack. Let SYN-2 represent a packet that carries both SYN and ACK that is sent in response to a SYN. 1. A delayed duplicate SYN1 received in the SYN-sent state is detected because: a. The SEQ number is wrong. b. The ACK number is wrong. c. Both SEQ and ACK are d. Undetected and causes the known to be wrong. recipient to respond with a SYN-2 2. A delayed duplicate SYN1 received in the ESTABLISHED state is: a. Responded to with RESET. b. Responded to with a data packet specifying current ACK and SEQ. c. Responded to with SYN2 d. Always causes TCP to crash. 3. A delayed duplicate SYN1 received in the ESTABLISHED state is: a. Responded to with RESET. b. Responded to with a data packet specifying current ACK and SEQ. c. Responded to with SYN2 d. Always causes TCP to crash. 4. Suppose a TCP connection has SND.UNA = 2400 and SND.NXT = 3450 and a packet arrives with ACK = 3200 and WINDOW = 800. a. How many more bytes may be transmitted before the sending TCP must stop sending because it runs out of usable space in the sender window. b. Suppose the sending application has an allocation of 6000 bytes of transmit buffer space. At what sequence number will the application be "put to sleep" if no additional acks are received. 5. Suppose an application has an allocation of 10,000 bytes of TCP buffer space. The last byte that the application has consumed is 2000 and the present offered window is 4000. What is RCV.NXT? 6. Suppose Tomlinson's clock proposal is used with a 20 bit sequence number and a clock that ticks 8192 times a second. Suppose maximum packet lifetime is 60 seconds. a. What is the MINIMUM amount of time in seconds that can elapse before sequence number resynchronization must occur. b. How often will synchronization be needed if packets are generated at 3/4 the maximum allowed rate. c. If the initial sequence number is 0 what will be the sequence number at the time resequencing takes place. (in question b). 7. Suppose the following is a diagram of an SNA network: B E / \ / \ A D G \ / \ / C F Answer the following T or F. ___ a. Nodes A and C can both have explicit routes with the identity (3, G) if A's (3,G) passes through E and C's (3, G) passes through F. ___ b. Nodes B and C can't both have explicit routes with the identity (3, F). ___ c. For node B to have a functional explicit route with identity (3, G), node D must also have an explicit route with identity (3, G). 8. In an SNA network the Current Pacing Group Size limits the number of packets in flight.. a. On a particular session b. Between any pair of hosts (connection) c. On a virtual route d. On an explicit route