Computer Science 825 Quiz 1 Name _______________________ 1. Identify the primary function of each of the following ISO/OSI layers: a. Network - b. Data link - c. Transport - 2. Name the other 4 layers: 1 - 3 - 2 - 4 - 3. a. Which is the highest layer considered part of the communications subnetwork? b. Which is the lowest layer having end to end responsibility? c. Which layer's function is most greatly diminished in a broadcast architecture such as an Ethernet LAN when compared with a point to point store and forward network. 4. Select the best answer to each of the following: a. The network and datalink protocols of the ISO/OSI architecture: 1. X.21 3. TCP 5. SDLC 2. X.25 4. IP b. The internet uses protocols primarily developed: 1. By IBM 3. By the ISO 2. In the Arpanet project 4. By the CCITT c. A transport layer protocol used in the internet is: 1. X.21 3. TCP 5. SDLC 2. X.25 4. IP 5. As packets travel down a protocol stack are headers generally added xor removed. 6. Suppose Westall's motorcycle courier service can carry 10 cartridge tapes each containing 100 megabytes of data to an offsite storage site located 7 miles from town at a rate of 70 miles per hour. At what rate in BIT's per second must data be transmitted in order that the whole backup be transmitted as fast as the delivery service can carry the tapes. Computer Science 825 Quiz 2 Name _______________________ 1. If the BIT_RATE of a channel and the number of distinct signalling states V are known then the Baud rate can be determined. Express the baud rate as a function of BIT_RATE and V. Baud rate = 2. Suppose 4 khz bandwidth line has a 20db snr. a. What is the maximum data rate of the channel? b. How many signalling levels must be used to attain it? 3. For each of the follwing pairs of transmission media identify the one for which a high data rate would typically be associated. a. Voice grade telephone / Private twisted pair. b. Baseband coax / Private twisted pair. c. Optical fiber / Broad band coax. 4. One way in which to modulate a sine wave carrier is called phase modulation what are the other two? 1. 2. 5. Consider the two phase modulation based encoding schemes: DiBit Phase Shift 00 0 45 01 90 135 10 180 225 11 270 315 Which one is used in the standard 1200 bps modem? Why is it better than the other? 6. Suppose a signal f(t) consists of two harmonics of frequency 1 hz and 2 hz. (i.e. The period = T = 1 sec and f = fundamental freq = 1 / T = 1 also). Suppose we sample incoming signal and obtain the following table of values: t .2 | .4 | .6 | .8 ----------------------------------------- f(t) 2 | 3 | 6 | 4 On the back of the paper set up the linear system needed to determine the fourier coefficients of f. (Hint: c = 0) Computer Science 825 Quiz 3 Name _______________________ 1. We discussed two basic mechanisms for multiplexing a channel (sharing one physical channel among multiple users). Name both and for each identify whether the technique would be more suitable for multiplexing channels using analog xor digital encoding. Mux Method Name Analog or Digital? a. | | | b. | | 2. Precisely why is it that digitally encoded channels transmitting data over very long distances can achieve far lower error rates than can analog channels? 3. What bit rate would be needed to support a "high fidelity" voice telephone circuit that would transmit frequencies as high as 20KHz and encoded voltage samples at a resolution of 1024 discrete levels. 4. Suppose I have a 10 mbyte core dump I need to send across the country. The path will be routed 5 intermediate switching centers. Me --- SC1 --- SC2 --- SC3 --- SC4 --- SC5 --- Dest If bit transmission rate is 100k bits / second, how many seconds will the transmission take using message switching and and packet switching (1000 bit packets). Assume no interference competing traffic. Message: Packet: 5. In what ways is the IBM SNA approach to attaching terminals to systems SUPERIOR to that typically found in Unix or VMS systems. Computer Science 825 Quiz 4 Name _______________________ The 1st question pertains to queueing delays experienced by N stations attempting to use a shared channel in a FIFO manner with no collisions. 1. If packets are generated at random (exponentially distributed) by each station then statically assigning 1/Nth of the bandwidth to each station (rather than having a central queueing mechanism) a. Will have no appreciable effect c. Will cause the delay to increase on the queueing delay. by a factor of N b. Will cause the delay to be reduced d. Will cause the delay to increase by a factor of N by N seconds. 2. The window of collision vulnerability for pure aloha is: a. 1 Packet transmission time. c. 1 Signal Propogation time. b. 2 Packet transmission times. d. 2 Signal Propogation times. 3. The window of collision vulnerability for slotted aloha is: a. 1 Packet transmission time. c. 1 Signal Propogation time. b. 2 Packet transmission times. d. 2 Signal Propogation times. 4. The window of collision vulnerability for a CSMA-CD LAN is a. 1 Packet transmission time. c. 1 Signal Propogation time. b. 2 Packet transmission times. d. 2 Signal Propogation times. 5. Throughput of a contention based MAC protocol can be improved by: - Minimizing the amount of time wasted when a collision occurs. - Reducing the probability of a collision on a transmission attempt Which of the above two items is the objective of the following: a. CSMA b. CD 6. a. Collision free protocols such as BitMap and BRAP have no collisions at all and thus no time wasted due to collisions. What is their most UNDESIRABLE characteristic when compared to contention based protocols. b. Are the advantages of using collision free protocols more significant at high xor low workload levels. 7. Suppose a satellite channels supports a 200,000 bit/second bit rate. Suppose pure aloha ground stations generate a 500 bit packet every 50 seconds on average. a. What average bit rate in bit/second is each station generating? b. What is the maximum throughput in bits/second that the channel can sustain on average. c. What is the maximum number of stations the network can sustain. Computer Science 825 Quiz 4 Name _______________________ 1. 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. p * k * (1 - k) ** (p - 1) b. k * p * (1 - p) ** (k - 1) d. None of the above. 2. If the probability computed above is denoted A, then the probability that a contention interval will last exactly j slots is: a. A ** j c. A / j b. (1 - A) ** (j - 1) d. None of the above. 3. Suppose the adaptive tree walk protocol is in use (see the tree on the board) and stations 0, 2, 3, 6, 7 all become ready. Write down the "sequence of events" describing the use of each contention slot until all stations have transmitted: Use the following notation: C(1,5,6),T(2),N,... to describe what occurs in each slot. 4. Indicate whether each of the following statements is True or False: ___ a. Ethernet is a CSMA-CD Lan. ___ b. Ethernet is non-persistent. ___ c. The mean amount of time each ethernet station waits after a collision increases by 2 after each successive collision. ___ d. IEEE assigned Ethernet station addresses are 48 bits long. 5. For the IEEE token bus match the control packets with the condtions underwhich they are used. ____ a. A station is powered up, listens 1. SOLICIT_SUCCESSOR_2 for the token and doesn't hear one. 2. WHO_FOLLOWS ____ b. A station wishes to leave the net. 3. SET_SUCCESSOR ____ c. A station transmits the token twice 4. RESOLVE_CONTENTION without hearing its successor transmit a token or a packet. 5. CLAIM_TOKEN ____ d. A station wishes to invite a new 6. SOLICIT_SUCCESSOR station to enter the network. 6. In the IEEE token bus stations transmit the token in station addresss order. Could the protocol be made to work at all if that restriction were removed. If not, why not. If so, what functions would be made more complex or less efficient. Computer Science 825 Quiz 6 Name _______________________ 1. a. What is an "orphan" frame on a token ring? b. How is an orphan frame detected and eliminated? 2. Answer the following T or F. ___ a. The Token Ring uses a global priority scheme which can lead to starvation of low priority traffic. ___ b. If the monitor station on a token ring "dies", the whole ring is not usable until the broken monitor station can be unplugged and physically replaced by a new monitor station. ___ c. In an IEEE 802.5 Token ring the recipient of a message is responsible for removing it from the ring. 3. Suppose a ring transmits at 10,000,000 bits per second and the signal propogates at a rate of 200,000 km / second. How many bits will fit on a 500 meter ring? 4. A token ring frame has two bits which the recipient can set. What do the bits specify. A - C - 5. Suppose a message is 7 bits long and C1, C2, and C3 represent the standard Hamming check bits.. What should the value of each be? (assume ODD parity) C1 C2 1 C3 1 0 1 6. Assume the message 1 0 1 0 1 1 0 arrives. Which if any the bits is in error? 7. Suppose message packets are 1000 bits (including data and ECC bits) and are to be transmitted in such a way that any error burst of up to 20 bits can be corrected. How many bits of the 1000 must be reserved for ECC. (NO FRACTIONAL BITS please.) Computer Science 825 Quiz 7 Name _______________________ 1. The number of bits in a CRC is equal to: a. The number of terms in the c. 16 generator b. The degree of the generator d. The degree of the generator + 1 2. Suppose a generator polynomial is x**7 + x**4 + x + 1. Draw the shift register representation of long division. 3. Consider the shift register shown on the board. Show the contents after each of the bits in the sequence 1 0 1 is processed. 1 - 2 - 3 - 4. Under what conditions can a CRC detect all errors consisting of an odd number of corrupted bits. 5. What is the maximum size of an error burst that can be guaranteed to be detected by a CRC. What must be true of the generator in order for this burst detection to be guaranteed. 6. Write down the resultant bit pattern after the following is subjected to SDLC type bit stuffing (flag = 01111110). (Assume the bits are processed by the bit stuffer in left to right order.) 0111011110111110111111011111110 7. One type of framing we discussed was using a flag byte with bit stuffing. Identify two other approaches to framing. a. b. Computer Science 825 Quiz 8 Name _______________________ 1. Demonstrate that a sliding window protocol with a 2 bit sequence number, a sender window size of 4 and a receiver window size of 1 can fail. 2. Demonstrate that a sliding window protocol with a 3 bit sequence number and a sender window size of 6 and a receiver window size of 4 can fail. 3. What is the cost in lost packet times caused by a single transmission error in each of the following schemes: (Here large means sufficiently large that no further performance benefits accrue from making it larger). a. Large SWS, RWS = 1, No SREJ. b. Large SWS, Large RWS, No SREJ. c. Large SWS, Large RWS, SREJ 4. Suppose that two way propogation delay is "N" packet times. a. How large should the SWS of question 3c be? b. How large should the RWS of question 3c be? c. How many bits should the sequence number be in protocol 3c. 5. Under what combinations of propogation delay (Short..Long) and error rate (Low..High) would each of the following protocols be good choices. There may be protocols in the following list that would NEVER be particularly good choices. If so, say so. a. SWS = 1, RWS = 1, No SREJ b. SWS = LARGE, RWS = 1, No SREJ c. SWS = 1, RWS = LARGE, SREJ d. SWS = LARGE, RWS = LARGE, No SREJ e. SWS = LARGE, RWS = LARGE, SREJ Computer Science 825 Quiz 9 Name _______________________ 1. a. In SDLC do supervisory frames carry a frame sequence number xor an ack number? (Yes is not a correct answer) b. In SDLC unnumbered frames carry no sequence number or ack number at all. This would appear to make it impossible to construct a reliable protocol (one in which exactly one copy of each frame transmitted is accepted by the receiver). Is such the case? If not why not? If so, why doesn't this cause problems. 2. a. The queuemsg procedure in the protocol 5 implementation could be blocked two possible conditions. What were the conditions and what events would eventually lead to unblocking? Condition | Unblocked by.. when... 1. | | --------------------------------------------------------- | 2. | | b. A buffer in the protocol 5 implementation cycled though a number of queues.. Associate each transition with the process that effected it. (Some answers may be used more than once or not at all). ____ 1. Free to network input a. Writer process ____ 2. Network input to link b. Timeout process station output ____ 3. Link station output to c. Reader process sender window. ___ 4. Sender window to free d. Queuemsg process list 3. Answer the following T or F. ____ a. A virtual circuit network layer is better than a datagram network layer in responding to localized network congestion. ____ b. Virtual circuit service can generally be provided more efficiently by a virtual circuit network layer than by a virtual circuit transport layer on top of a datagram network layer. 4. Assume a new virtual circuit is added to the network shown on the screen. Its route is ABCD. What are the new entries in each nodes routing tables: A B C D Computer Science 825 Quiz A Name _______________________ 1. a.In the backward learning routing algorithm describe PRECISELY what the network layer does with regard to routing whenever a packet is received. b. How can the backward learning algorithm be made to respond to adverse changes in topology WITHOUT undergoing a complete cold start. 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 proportional to: 1. M 2. N 3. N ** 2 4. N * M b. The size of a routing info packet in SPF is proportional to: 1. M 2. N 3. N ** 2 4. N * M c. The number of routing packets transmitted throughout the entire network at each routing exchange in Bellman-Ford is proportional to: 1. M 2. N 3. N ** 2 4. N * M d. 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 e. Routing information exchanges in the Bellman-Ford ARPANET scheme took place at least as often as once a 1. Second 2. Minute 3. Hour 4. Day f. Routing information exchanges in the SPF ARPANET scheme take place at least as often as once a 1. Second 2. Minute 3. Hour 4. Day g. What routing technique is used to route the routing information packets themselves in the SPF ARPANET scheme. h. In terms of computational complexity the Bellman-Ford algorithm as performed by a single node is of order. 1. M 2. N 3. N ** 2 4. M ** 2 5. N * M i. What routing technique is the basis for routing in IBM SNA networks. Computer Science 825 Quiz B Name _______________________ 1. Explain whether each of the following congestion control techniques is applicable to virtual circuit or datagram based or both types of network layers: a. Packet discarding: b. Preallocation of buffers: c. Choke packets: 2. Identify two significant disadvantages of the use of the "Isarithmic" congestion control technique. 1 - 2 - 3. Irland's rule placed a bound on the number of buffers that could be allocated to an outbound link in an Imp with N links and M buffers. a. What was the bound? b. Was it an upper bound or a lower bound. 4. Identify the layer associated with each of the following internetworking techniques. Use the terminology of the text. a. Protocol converter. b. Repeater c. Bridge d. Gateway 5. How many NETWORKS of each of the following type are supported in the Internet protocol. Class B - Class C - Computer Science 825 Quiz C Name _______________________ 1. In SNA each explicit route is uniquely identified by a two component "address" (xxxx,yyyyy) what are the two components. 1 - 2 - 2. In SNA each routing table is indexed by the ER unique identifier referred to in question 1. What value is associated with each ER in the table?? 3. If multiple Links exist between nodes, it is possible to group them all into a single transmission group or to create as many transmission groups as there are links.. What is the advantage of each approach. a. Single TG b. As many TG's as Links 4. When a session is established in SNA a virtual route is selected based on two parameters.. What are they? (Hint: One should be obvious and the answer to question 3 should remind you of the other. 1 - 2 - 5. How does the table of virtual routes used in question 4 get constructed? 6. Does the flow control scheme used as a congestion control mechanism by SNA imposed on a (session, session) xor (source, destination) xor virtual route granulity xor explicit route granularity. 7. How does a node in SNA respond to both Mild and Severe congestion. Mild - Severe - 7. What combination of network layer provided and application demanded quality of service makes the transport layer most complicated. Computer Science 825 Quiz D Name _______________________ 1. a. Precisely why is it a bad idea for Transport Connections to always start a session using sequence number 0. b. The problem with using sequence number 0 can be reduced by using a sequence number is a an 8 bit incarnation number concatenated to a 24 bit sequence number that still always starts at 0. Why can this technique still lead to problems. c. Is always using 0 as an initial sequence # a problem in data link connections??? If so, why. If not, what difference between datalin and transport connections eliminates the problem. 2. Suppose Tomlinson's clock proposal is used with a 16 bit sequence number and a clock that ticks once a millisecond. Suppose maximum packet lifetime is 10 seconds. a. What is the MINIMUM amount of time that can elapse before sequence number resynchronization must occur. b. How often will synchronization be needed if a packet is generated every 2 milliseconds. 3. a. Distinguish between the offered window and the usable window in TCP Offered - Usable - b. Suppose a TCP connection has SND.UNA = 2000 and SND.NXT = 2600 and a packet arrives with ACK = 2200 and WINDOW = 1000. What size are the offered and usable windows now? offered - usable - 4. Suppose a receiver in a stop and wait file transfer protocol uses a write then ack policy and the sender uses a policy of retransmitting only if an unacked packet is outstanding. Identify whether each of the following sequence of events will result in correct behavior (OK) a lost packet (LOST) or a duplicate (DUP). WAC WC(A) C(WA) 5. Does there exist a protocol that will permit the blue army to guarantee a victory.