Computer Science 851 Quiz 1 Name _______________________ 1. a. Identify one layer of the ISO/OSI 7 layer stack that is present only in hosts and not in routers b. Identify one layer that is present in BOTH hosts and routers. 2. Which best characterizes the handling of network and session layer headers with respect to transport layer headers when the packet traverses the physical layer: a. Both network and session layer b. Both network and session layer headers will come before the headers will come after the transport header transport header c. The session layer header will d. The network layer header come before and the network come before and the session layer header after layer header after. 3. For each of the following layers answer E, G, or P depending upon whether the interoperability issues confronting the layer are primarily (E) end-to-end, (G) global, or (P) point to point ____ a. Network layer ____ b. Datalink layer ____ c. Transport layer 4. Two things that a protocol can do to earn the term "unreliable" are (1) deliver packets with bits that have been inverted and (2) drop or lose packets. Identify two others: a. b. 5. In the bad-old-days of early networking it was common to build the network protocol right into the application itself. List as many reasons as you can why this is a bad idea: 6. From the perspective of building a correct implementation of a protocol, the simplest and easiest type of service to provide is: a. reliable connection oriented b. unreliable connection oriented c. reliable connection less d. unreliable connection less 7. Why was it once a good idea to provide error recovery at the datalink layer, but with the passage of time and change in technologies and applications of networking its now not such a good idea. 8. Place the following protocols at the correct location in the boxes below: TCP, IP, ATM Connection Connection Oriented Less ___________________________________ | | | Reliable | | | | | | |_________________|_______________| | | | Unreliable| | | | | | |_________________|_______________| 9. Do protocols (as the term is normally used in networking, e.g in SDLC, TCP, or IP) define the rules under which a layer communicates a. With the layer above it b. With a peer layer in another node. c. With the layer below it. d. All of the above. 10. In the ISO/OSI model at what layer did checkpointing and recovery from network failures reside? 11. In the Linux network stack, the AF_INET layer is the "top half" of the implementation of the a. datalink layer b. transport layer c. the network layer d. device driver layer Computer Science 851 Quiz 2 Name _______________________ 1. What bandwidth in Hz is required to support a bit rate of 64,000 BPS on a channel with a 30dB SNR? 2. How many signaling states are needed to achieve a bit rate of 40000 bits / second while signalling at a rate of 4000 baud 3. Suppose a channel passes harmonics in the range 20Khz - 30Khz. In decribing bandwidth and bit rates "K" always represents 10^3 and not 2^10) What is the minimum useful duration (in seconds) for signalling states. 4. What bit rate is required to support a new "hi-fi" PCM phone that supports frequencies to 16Khz and quantizes the signal into 1024 discrete levels. 5. Suppose a PCM scheme supports a bit rate of 35,000 bps and quantizes the signal into 128 distinct levels. What is the highest frequency that it can carry? 6. Recall the Bell 212A modem discussed in class. It signalled using 4 phase angles, 45, 135, 225, and 315 degrees. 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 + 45deg) every bit time. for the duration of the burst c. There will be a +45 degree phase shift every other bit time. 7. 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. 8. In QAM the two carriers that are amplitude modulated a. use the same frequency and b. use the same frequency but are phase 90 degrees out of phase c. use different frequencies and d. use the same frequency but are are 90 degrees out of phase 180 degrees out of phase 9. QAM-16 sends a. 4 bits per baud time b. 16 bits per baud time c. 1 bit per baud time 10. In QAM 16 the each of the two carriers use a. 2 different amplitudes b. 4 different amplitudes c. 8 different amplitudes d. 16 different amplitudes The Bit rate = buad_rate x log2(V) 11. The maximum baud rate on a channel is primarily constrained by a. the bandwidth b. the SNR c. both equally d. neither one is a direct factor 12. The number of possible signalling states V is primarily constrained by a. the bandwidth b. the SNR c. both equally d. neither one is a direct factor Computer Science 851 Quiz 3 Name _______________________ 1. The number of voice telephone connections that can be simultaneously multiplexed onto a single OC-1/STS-1 circuit is closest to: a. 51 b. 775 c. 6,480 d. 1.5 Million 2. The bit rate of an OC-192 carrier is closest to: a. 50 Mbps b. 1 Gbps c. 10 Gbps d. 100 Gbps 3. 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 8 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 from A to B if 4000 bit packets are used. 4. 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 + H) b. 10000 / (P - H) c. 10000 * P d. P / 10000 5. 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) 6. The use of very small slot sizes in a TDM multiplexing scheme 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 7. Suppose a BISYNCH message consists of the following byte pattern while it is "on the wire". Write down the data part of the message AFTER the receiver removes the "stuffed" bytes. | this is the data part of the msg | ------------------------------------------------------------------ | DLE | STX | 'A' | DLE | DLE | 'B' | DLE | DLE | ETX | DLE | ETX | ------------------------------------------------------------------ 8. In SDLC bit stuffing algorithm the loss of a 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. 9. Suppose a code uses 4 bit code words. What is the Hamming distance between the code words 0110 and 1101 10. ATM is an example of which type of multiplexing. a. FDM b. Synchronous TDM c. Asynchronous TDM 11. The DMT technology used in ADSL is best characterized as a. Pure ATDM b. Pure STDM c. QAM over FDM subchannels d. QAM over ATDM subchannels. 12. The payload of an ATM cell (packet) is a. 32 bits b. 32 bytes c. 48 bits d. 48 bytes Computer Science 825 Quiz 4 Name _______________________ 1. Suppose a 7 bit codeword with ODD parity is being used in a single bit hamming ECC. Suppose the following data bits are to be sent. Fill in the ECC bits 1 0 0 1 -------------------- 1 2 3 4 5 6 7 2. Suppose a 7 bit codeword with ODD parity is being used in a single bit hamming ECC. Suppose the following codeword is received. 1 1 0 0 0 1 1 -------------------- 1 2 3 4 5 6 7 Which (if any) bit is in error? 3. a. Suppose a single bit Hamming ECC is to be performed on a 255 bit codeword. How many bits are in each of the parity checked groups (include the parity bit itself). b. How many bits does any pair of parity checked groups have in common with each other? c. How many distinct parity groups does bit 47 belong to. 4. Suppose 2000 bit code words are to be transmitted and it is desired to use a Hamming code to correct error bursts of up to 50 bits. How many of the 2000 bits must be used for ECC. (Hint: Fractional bit based strategies are not likely to be rewarded!) 5. Suppose a 12 bit code word is used. How many code words are at a Hamming distance of exactly 2 from a given code word. a. 12 b. 144 c. 132 d. none of the above 6. Suppose a generator polynomial of G(x) = x^4 is used. Identify the errors that G(x) can detect. ____ a. E(x) = x^2 ____ b. E(x) = x^6 + x^2 ____ c. E(x) = x^8 + x^6 7. Suppose a generator polynomial of G(x) = x + 1 is used. Identify the errors that G(x) can detect. ____ a. E(x) = x ____ b. E(x) = x^2 + 1 ____ c. E(x) = x^2 + x + 1 8. For the shift register shown above: a. What generator polynomial is represented b. What will be the NEW contents of the shift register after an input bit of "1" is processed. 9. In the error detection business it is in general easier to detect errors in which a. An even number of bits are b. An odd number of bits are inverted inverted c. It makes no difference 10. Suppose a generator polynomial of degree 4 is used. ___ a. The maximum number of terms in the generator polynomial is... ___ b. The maximum number of terms in the remainder when a polynomial of degree 179 is divided by this generator is ... ___ c. The number of CRC bits that such a generator produces is ... Computer Science 825 Quiz 5 Name _______________________ 1. For the shift register shown above: a. What generator polynomial is represented b. What will be the NEW contents of the shift register after an input bit of "1" is processed. 2. How should the pre-multiplying shift register be initialized? a. all 0's b. 1st 4 bits of the message c. both ways work fine 3. In protocol 2, ACK's were used but no sequence numbers were used on frames or ACK's. Which of the following problems could occur. a. Lost frames would go b. Lost ACK's would result in undetected. lost frames c. Lost acks would result in d. Lost frames would result in duplicate frames. duplicate frames. 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 2 frames b. The loss of 1 frame and the duplication of 1 frame. c. The duplication of 2 d. The loss of 1 frame frames. 6. One way to prevent the specific failure that protocol 3 suffered is to not send an ACK when a duplicate frame is received. Adopting that strategy produces a protocol a. which is correct b. which deadlocks on a lost frame c. which deadlocks on a lost d. which deadlocks on both a lost ACK frame and on a lost ack. 7. The bisynch protocol introduced the use of the ENQ packet. An ENQ is used a. by the sender to request b. Used by the receiver to that the last ACK be request that the last retransmitted. packet be retransmitted c. Both of the above d. Neither of the above. 8. 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 <= nxtrecv ____ b. nxtrecv may be < nxtack ____ c. nxtsend may be < nxtrcv 9. Suppose in a connection such as described in question 8 that after the connection has been idle for a while with nxtsend=nxtack=nxrecv=0 and the sender sends a burst of 5 packets. Which of the following values will reach "5" last a. nxtsend b. nxtrecv c. nxtack d. They will all reach 5 at the same instant 10. For each of the following flavors of sliding window protocol, identify the correct choice of sndwnd and rcvwnd ____ a. Stop and Wait a. sndwnd = N > 1 rcvwnd = N > 1 ____ b. Go back N b. sndwnd = 1 rcvwnd = N > 1 c. sndwnd = 1 rcvwnd = 1 d. sndwnd = N > 1 rcvwnd = 1 Computer Science 825 Quiz 8 Name _______________________ 1. Suppose that a satellite link has a ROUND TRIP propagation delay of 500 ms. Suppose bit transmission rate is 100,000 bits per second and packets are 5000 bits long. a. What will the efficiency of this channel be if stop and wait protocol is used. b. How large (in packets) must the sender window be in order to obtain 100% efficiency if the channel is guaranteed error free. (i.e. give me the MINIMUM Sender Window Size I can use). c. What is the MINIMUM size of the seq/ack number in bits that is required to support receiver buffering with out of order retransmission. 2. Suppose an Ethernet LAN has a ROUND TRIP propagation delay of 100 usec. Suppose bit transmission rate is 10 Mbps. What is the minimum packet size in bits that can obtain 90% efficiency using a Stop and Wait protocol. 3. Produce a packet exachange diagram similar to the one in the notes to show how a sliding window protocol that uses a 2 bit sequence number, a sender window of 3 and a receiver window of 2 can fail. 4. For each of the following combinations of propogation delay and error rate identify the most suitable variation of sliding window protocol. (The most suitable choice is the SIMPLEST one that doesn't incur a big performance penalty.) ___ a. No errors but packet time 1. Stop and Wait << propagation delay ___ b. No errors but packet time 2. Receiver buffering w/ out of >> propagation delay. order retransmission ___ c. High errors and packet time << propagation delay 3. Receiver buffering w/ go back N sender 4. Go back N. 5. The sender window logic used three indexes: nxtsend; nxtqueue; and nxtack. We said these values always remained in a specific relative order. The order was a. send <= queue <= ack b. queue <= ack <= send c. ack <= queue <= send d. send <= ack <= queue e. None of the above 6. 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. Read pending to network a. Network layer process input. ____ 2. Network input to link b. Queuemsg process station output c. Timeout process ____ 3. Link output to sender window. d. Writelink process ___ 4. Sender window to free e. Readlink process list 7. 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. queue - ack b. send - queue c. send - ack d. queue - send 8. Suppose the sequence number has 4 bits. Then the value of the semaphore numslots is: (assume modular arithmetic is properly handled) a. 16 - (queue - ack) b. 16 - (queue - send) c. 15 - (queue - send) d. 15 - (queue - ack) Computer Science 851 Quiz 7 Name _______________________ 1. One flaw in the "Westall protocol was susceptibility to deadlock. 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 2. Identify the two major capabilities that are required in a robust and reliable datalink protocol that were not implemented in the sample protocol. (Hint: possible susceptibility to deadlock under extreme loads is NOT one of them). For each of the missing features identify the SDLC frame type that adds the feature: a - missing feature: sdlc frame type: b - missing feature: sdlc frame type: 3. The address byte in an SDLC packet always carries the address of a. The sender b. The receiver c. The primary station. d. The secondary station. 4. Select the description which most accurately matches the use of the P/F bit in SDLC. a. 1 -> Poll and 0 -> Final b. The bit means poll or not poll when a secodary sends final or not final when a primary sends. c. The bit means poll or not d. The bit means poll or not poll poll to the sender final when the primary sends final or or not final to the receiver not final when a secondary sends. 5. 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. 6. Which of the following is NOT a use of supervisory frames in SDLC a. Sending a standalone ack b. Requesting initialization after power-on. b. Polling d. Telling another station to temporarily stop sending. 7. The "failure" that the 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. 8. In ATM framing, after a transition from the HUNT to PRE_SYNCH occurs the HUNT to PRE_SYNCH states. a. The algorithm continues b. The algorithm delays 32 bits to test every bit to see before making another CRC test if the most recent 8 bits are a valid CRC for the previous 32. c. The algorithm delays 424 bits before testing again. 9. In the SSCOP, when NO packets have been lost, a STAT packet will contain three fields. Identify what they are in a way the indicates you understand their usage (i.e. abstract notation such as N(X) doesn't get the job done). a - b - c - 10. Which of the following ways of characterizing sliding window protocols is best descriptive of the operation of the SSCOP a. Stop and Wait b. Go Back In c. Receiver buffering with out of order retransmission Computer Science 825 Quiz 8 Name _______________________ 1. Select the appropriate window of vulnerability for collision OCCURRENCE in each of the following MAC protocols: (n.b. the question says occurrence and not detection) ____ a. Pure aloha 1. One byte time 2. One packet time ____ b. CSMA-CD ethernet 3. Two packet times 4. The one way propogation delay 5. The two way propogation delay 2. Measurements of an infinite user slotted aloha channel show that 20% of the slots are idle. a. What is the total load (mean number of transmission attempts per packet time) = G. b. What is the throughput (successful transmissions per unit time). 3. For a slotted aloha system for each value of "S" (except the S corresponding to G = 1.0) there are two different values of G which will result in the throughput being "S". For a given "S" the average delay before a packet is successfully transmitted is: a. The same for both "G"s b. Larger for the small "G" than for the big "G". c. Larger for the big "G" d. Totally independent of than for the small "G". the "G" value. 4. The main function of the CD portion of a CSMA-CD protocol is to: a. Reduce the probability that b. Reduce amount of wasted time a collision will occur. when a collision occurs. c. Ensure that no collisions d. Both a and b. occur at all. 5. The probability of a successful Tx occuring during a slot is maximized if p = a. k b. 1/e c. 1/k d. None of the above 6. The objective of the CS part of the CSMA-CD protocol is to: a. Reduce the amount of time b. Reduce the number of caused by collisions that collisions that occur do occur c. Reduce the amount of idle d. All of the above. time in which all stations are silent 7. If K stations share a CSMA 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 b. k * p * (1 - p) ^ (k - 1) c. k * p * (1 - k) ^ (p - 1) d. None of the above. 8. If the probability computed above is denoted A, then the probability that a contention interval will last exactly j slots is: a. A ^ (j - 1) * (1 - A) ^ j b. A / j c. j * (1 - A) ^ (j - 1) d. None of the above. 9. Answer the following T or F. (Assume only the parameter indicated is being varied and all of the others remain fixed in each case. This question refers to a "traditional" shared bus ethernet.) ___ a. Increasing the average packet size will tend to make the efficiency of a CSMA CD LAN higher. ___ b. Increasing the physical length of a CSMA CD LAN will increase the length of the contention interval. ___ c. Decreasing the bit transmission rate from 10 Mbps to 1 Mbps increase the efficiency of a CSMA LAN 10.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 shortest possible amount of time after station 1 starts transmitting that station 2 can hear the collision? c. What is the longest possible amount of time after station 1 starts transmitting that station 2 can hear the collision? Computer Science 851 Quiz 9 Name _______________________ 1. Identify all pairs of the following 4 chip sequences that are NOT mutually orthogonal a. (+1 +1 -1 -1) b. (+1 -1 +1 -1) c. (-1 +1 -1 +1) 2. In Direct Sequence Spread Spectrum the receiver takes the dot product of the chip sequence received with the senders chipping code. A value of exactly 0 indicates: a. A zero bit was sent b. a one bit was sent c. the channel is so noisy it is not possible to tell what was sent. 3. Which of the following does 802.3 ethernet DO but 802.11 wireless does NOT DO. (Identify ALL that apply) a. sense the carrier before b. detect collisions transmitting c. Jam the medium after a collision is detected 4. The primary motivation for the use of fragmentation in 802.11 but not in 802.3 (ethernet) is: a. Ethernet has a higher b. 802.11 uses much larger bit rate packets c. 802.11 has a much higher bit error probability 5. In an 802.11 system answer the following T or F if be Tx'ed immediately following the SIFs but before the DIF's expires a. an ACK b. RTS c. a packet 6. 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. 7. When a station wants to leave a Token bus network it sends a SET_SUCCESSOR frame a. to its successor identifying b. to its successor identifying its current predecessor itself c. to its predecessor identifying d. to its predecessor identifying its current successor itself. 8. 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 9. When a station issues a SOLICIT_SUCCESSOR_1 and a collision follows the next frame issued is: a. CLAIM_TOKEN b. WHO_FOLLOWS c. SOLICIT_SUCCESSOR_2 d. RESOLVE_CONTENTION 10. Suppose three wireless stations are situated geographically as follows: A ------------------ B -------------------- C Describe the "hidden station problem". 11. In an 802.11 network what type(s) of frames may be transmitted in the slot that immediately follows the SIF? 12. The type of wireless lan most likely to be deployed in home and office locations typically operates in: a. ad hoc mode b. infrastructure mode with PCF c. infrastructure mode with DCF Computer Science 851 Quiz A Name _______________________ 1. In an 802.11b network suppose that while station A is waiting for its backoff slot counter to count down to zero station B begins transmission. Which best characterizes the behavior of station A during the transmission of station B. a. its backoff slot counter will b. the count down will be continue to count down and if suspended during station B's it reaches 0 station A will Tx Tx and will resume as soon as station B finishes as soon as station B finishes c. When station B finishes station d. When station B finishes, station A will reset the counter to its A will double the size of the CWin original starting value and draw a new random number and restart the countdown. restart the countdown. 2. In an 802.11b network, stations must execute the backoff procedure (i.e. draw a random number of slots to delay) a. Every time a packet is sent b. Only if the channel is initially sensed busy c. Only after a collision occurs 3. Which best characterizes the physical layers of 802.11 and DOCSIS a. Both use shared medium b. Dedicated point to point physical channels channels are used in both c. 802.11 uses shared but d. 802.11 uses dedicate but DOCSIS uses dedicated DOCSIS uses shared 4. If you are operating a home wireless network what are two different mechanisms that you might use to make it more difficult for a hacker to connect to your network: a - b - 5. Clemson uses the only the stronger of the two mechanisms. Identify the main logistical problem associated with deploying the mechanism in an environment with 20,000 legitmate users. 6. Suppose a DOCSIS system is set up as follows: Basic tick = 6.25 usec, and that a mini-slot consists of 8 basic tick and that a MAP is sent out every 5 msec. How many mini-slots does the MAP map?? (Downstream means -> the end-user system ) (Upstream means -> the Cable modem ISP) 7. In DOCSIS the MAP a. is transmitted downstream and b. is transmitted upstream and describes how the downstream describes how the upstream channel is to be allocated channel is to be allocated a. is transmitted upstream and b. is transmitted downstream and describes how the downstream describes how the upstream channel is to be allocated channel is to be allocated 8. Suppose two cable modem customers are on the same cable segment and one wishes to send a file to another. Which of the following best describes the situation a. since they are on the same b. Since they are on the same cable segment the data can segment it is impossible for be sent directly from one CM them to exchange any IP to the other. packets at all. c. They can communicate but all packets must be sent upstream to the CMTS and then back downstream to the other CM Suppose that EXACTLY 2 stations, both with an infinite backlog of traffic are contending for access to a shared channel. Suppose station A always randomly sets its backoff counter to one of the values {0, 1} and station B always sets its counter to one of the values {0, 1, 2, 3} 9. In the long term in what fraction of the slots will station B be successful in starting a Tx a. 1/2 b. 1/4 c. 1/8 d. 1/16 10. In the long term in what fraction of the slots will there be collisions a. 1/2 b. 1/4 c. 1/8 d. 1/16 Hint: The easiest way to do this is just to enumerate all the possible combinations of backoff values and count 'em up. 11. Order the following wireless technology according to range. (1) is the longest range: ___ a. 802.11 ___ b. 802.16 ___ c. Bluetooth Computer Science 851 Quiz B Name _______________________ 1. The use of a RELIABLE network layer is more desirable a. with very unreliable links b. with very reliable links than with very reliable links than with very unreliable links c. has to relation to the reliability of the links. 2. Let N = number of nodes in a network and M = the average number of links / node. a. The size of a routing info packet in Bellman-Ford is of order 1. M 2. N 3. N ^ 2 4. N ^ M b. The minimum number of routing packets transmissions at each complete exchange in Bellman Ford within the entire network is of order: 1. M 2. N 3. N ^ 2 4. M ^ 2 5. N * M 3. Let N = number of nodes in a network and M = the average number of links / node. a. In terms of computational complexity the SPF algorithm as performed by a single node is of order: 1. M 2. N 3. N ^ 2 4. M ^ 2 5. N ^ M b. The minimum number of routing packets transmissions at each complete exchange in an SPF network within the entire network is of order: 1. M 2. N 3. N ^ 2 4. M ^ 2 5. N * M 4. Each routing update packet propagates a. Across the entire net in SPF b. Only to adjacent neighbors in SPF and in Bellman-Ford and Bellman Ford c. Across entire net in SPF but d. Across entire net in B-F but only only to adjacent neighbors in B-F to adjacent neighbors is SPF 5. The routing algorithm used to transmit routing updates in an SPF network is typically: a. Static tables built by b. Backward learning sysadmin c. Bellman-Ford d. Flooding 6. Routing loops can occur in SPF a. only when all nodes use the same b. only when some nodes use a cost matrix different matrix than others c. in both cases a. and b. d. Never, the SPF algorithm ALWAYS guarantees optimal routes 7. One of the problems with the original use of the Bellman-Ford algorithm in the ARPANet was unstable routing and loops. A contributing factor to the instability was that: a. Routing information was b. Old duplicate copies of often lost routing info was delivered c. Routing info exchanges d. Routing info exchanges were not frequent enough were too frequent. 8. Suppose the Bellman-Ford routing algorithm is being used and station B receives the following routing updates from neighbors A, C and E Suppose BA delay = 2, BC delay = 4 and BE delay = 3. Complete the routing table for B., A C E Cost VIA A 0 9 6 | ------------ ---------- B 5 11 7 | ------------ ---------- C 2 0 3 | ------------ ---------- D 8 5 2 | ------------ ---------- E 6 8 0 | ------------ ---------- F 11 2 7 | ------------ ---------- 9. Identify a primary disadvantage of each of the following routing algorithms _____ a. Flooding 1. Not robust (incorrect routing) 2. May cause excess congestion _____ b. Backward learning 3. Unlearning broken routes requires count to infinity _____ c. Hot Potato 4. The basic algorithm doesn't only learns for the better _____ d. Bellman Ford 10. In a network that uses SPF suppose station C constructs the following cost matrix. Draw Node C's routing tree labeling the edges in the order they become "permanent". To A B C D E A 0 1 2 - 2 F B 1 0 - 5 2 r o C 2 - 0 1 5 m D - 5 1 0 5 E 2 2 5 5 0 Computer Science 851 Quiz C Name _______________________ 1. a. Suppose network addresses are 20 decimal digits and flat routing tables are used. What is the maximum number of entries that may be required in a routing table. b. Suppose hierarchical routing is used and the addresses are partitioned as an 6 digit Area address; an 8 digit Network address and a 6 digit host addres. Now what is the maximum number of routing table entries. 2. Suppose a wide-area multicast protocol is in effect and a router receives a message indicating that a host to which it was forwarding the multicast no longer wants to receive it. That request should be forwarded upstream toward the source of the m'cast if: a. there are no more hosts downstream b. there are additional hosts of the router who are receiving the downstream who continue mcast. to receive it. c. it must always be forwarded upstream d. it should never be forwarded upstream 3. Adding support for which of the following is most likely to require additional persistent state in a router: a. multicasting b. broadcasting c. both d. neither 4. In the network shown suppose all hosts know the optimal route to A (hop count metric) and A initiates a reverse path forwarding broadcast. How many unnecessary transmissions will occur? 5. 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. Spanning tree. ______ c. Flooding 6. The main factor that determines whether or not packet-discarding can be used as a congestion control mechanism in a network layer is: a. Whether the network layer b. Whether the network layer is is connection oriented or reliable or unreliable connection less. c. Both are equally important. d. Neither is important at all. 7. Flow control is used as a congestion control mechanism in the Internet a. on a source router to b. on a source host to dest router basis dest host basis c. on a source application to dest application basis 8. Suppose three traffic arrival streams have the same mean arrival rate of 400 pkts/second and that the service rate is 600 pkts / second. Order the streams from 1 (smallest queue length) to 3 (largest queue length) according to the the following characteristics: ___ 1. Variance = 10,000 No significant correlation ___ 2. Variance = 100 Evidence of long-range dependence ___ 3. Variance = 10,000 Evidence of long-range dependence Suppose an ATM cell arrival process is found to have a mean arrival rate of 1000 cells per second and the outgoing link can send at a rate of 1500 cells per second. 9. In the long term what percent of the time is the link busy? 10. The observed queue length will increase a. only when more that 1000 cells b. only when more than 1500 arrive in a second cells arrive in a second c. only when more that 2000 cells arrive in a second. 11. The likelihood of observing 2000 arrivals in a given second is a. increases as the variance of b. decreases as the variance of the distribution increases increases c. is independent of the variance and depends on the degree of self-similarity. Computer Science 851 Quiz D Name _______________________ 1. The full 20 byte ATM address is used in (circle all that require the full address). a. SVC setup b. Routing of individual cells of an established SVC c. PVC setup d. Routing of PVC cells 2. The number of address bytes that each ATM host "inherits" from the switch to which it is attached is: a. 6 b. 13 c. 14 d. 19 3. Provide the order in which the following components of an type 2 ATM address appear: __1__ a. The 0x47 that identifies this is a type 2 address _____ b. The 6 byte MAC address on a host systems ATM NIC ____ c. The international standards body that assigned the ATM network address (DIN, NIST, etc) ____ d. The selector (or ATM port) byte ____ e. The public ATM network identifier 4. The connection identifier (vpi, vci) for a new SVC is assigned by a. the switch to which the host b. the originating host O/S is connected c. the application program d. the destination host O/S 5. The connection identifier (vpi, vci) for a specific SVC a. never changes b. MUST change at each hop c. MAY change at each hop 6. Which of the following is an ATM network layer not permitted to do a. Discard cells b. Deliver cells with multiple bit errors c. Reorder cells d. All of the above 7. Suppose a host connected to router A wants to connect to router D through the path (A, B, E, D). Update the routing tables using the label switching algorithm described in class: (you will need to add one line to each of the 4 tables). Router A Router B Router E Router D From To From To From To From To H 0 B 0 A 0 E 0 G 0 D 0 E 0 H 0 H 1 B 1 A 1 E 1 B 0 F 0 K 0 F 0 B 0 C 0 E 0 A 0 B 1 F 1 K 1 F 1 H 2 C 1 G 0 E 2 B 2 G 0 H 0 E 0 D 0 B 0 8. The primary objective of the spanning tree algorithm in a transparent bridge system is to: a. Reduce the number of b. Prevent indefinite packet looping. destination unknowns c. Ensure that the optimal d. All of the above. route is taken. 9. 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. 10. With respect to the objective of Shortest Path Routing, which of the two bridging techniques we studied is superior. a. Spanning tree b. Source routing c. Both provide optimal paths 11. 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", "Designated bridge port for the LAN", on "NOT in the spanning tree".