all the stations whose addresses are prime numbers suddenly become ready at once, how many bit slots are needed to resolve the contention?
11.A collection of 2n stations uses the adaptive tree walk protocol to arbitrate access to a shared cable. At a certain instant, two of them become ready. What are the minimum, maximum, and mean number of slots to walk the tree if 2n 1?
12.The wireless LANs that we studied used protocols such as MACA instead of using CSMA/CD. Under what conditions, if any, would it be possible to use CSMA/CD instead?
13.What properties do the WDMA and GSM channel access protocols have in common? See Chap. 2 for GSM.
14.Six stations, A through F, communicate using the MACA protocol. Is it possible that two transmissions take place simultaneously? Explain your answer.
15.A seven-story office building has 15 adjacent offices per floor. Each office contains a wall socket for a terminal in the front wall, so the sockets form a rectangular grid in the vertical plane, with a separation of 4 m between sockets, both horizontally and
vertically. Assuming that it is feasible to run a straight cable between any pair of sockets, horizontally, vertically, or
diagonally, how many meters of cable are needed to connect all sockets using
a. (a) a star configuration with a single router in the middle? b. (b) an 802.3 LAN?
16.What is the baud rate of the standard 10-Mbps Ethernet?
17.Sketch the Manchester encoding for the bit stream: 0001110101. 18.Sketch the differential Manchester encoding for the bit stream of the previous problem. Assume the line is initially in the low state. 19.A 1-km-long, 10-Mbps CSMA/CD LAN (not 802.3) has a propagation speed of 200 m/μsec. Repeaters are not allowed in this system. Data frames are 256 bits long, including 32 bits of header, checksum, and other overhead. The first bit slot after a successful transmission is reserved for the receiver to capture the channel in order to send a 32-bit acknowledgement frame. What is the effective data rate, excluding overhead, assuming that there are no collisions?
20.Two CSMA/CD stations are each trying to transmit long (multiframe) files. After each frame is sent, they contend for the channel, using the binary exponential backoff algorithm. What is the probability that the contention ends on round k, and what is the mean number of rounds per contention period?
16
21.Consider building a CSMA/CD network running at 1 Gbps over a 1-km cable with no repeaters. The signal speed in the cable is 200,000 km/sec. What is the minimum frame size?
22.An IP packet to be transmitted by Ethernet is 60 bytes long, including all its headers. If LLC is not in use, is padding needed in the Ethernet frame, and if so, how many bytes?
23.Ethernet frames must be at least 64 bytes long to ensure that the transmitter is still going in the event of a collision at the far end of the cable. Fast Ethernet has the same 64-byte minimum frame size but can get the bits out ten times faster. How is it possible to maintain the same minimum frame size? 24.Some books quote the maximum size of an Ethernet frame as 1518 bytes instead of 1500 bytes. Are they wrong? Explain your answer.
25.The 1000Base-SX specification states that the clock shall run at 1250 MHz, even though gigabit Ethernet is only supposed to deliver 1 Gbps. Is this higher speed to provide for an extra margin of safety? If not, what is going on here?
26.How many frames per second can gigabit Ethernet handle? Think carefully and take into account all the relevant cases. Hint: the fact that it is gigabit Ethernet matters.
27.Name two networks that allow frames to be packed back-to-back. Why is this feature worth having?
28.In Fig. 4-27, four stations, A, B, C, and D, are shown. Which of the last two stations do you think is closest to A and why?
29.Suppose that an 11-Mbps 802.11b LAN is transmitting 64-byte frames back-to-back over a radio channel with a bit error rate of 10-7. How many frames per second will be damaged on average?
30.An 802.16 network has a channel width of 20 MHz. How many bits/sec can be sent to a subscriber station?
31.IEEE 802.16 supports four service classes. Which service class is the best choice for sending uncompressed video?
32.Give two reasons why networks might use an error-correcting code instead of error detection and retransmission. 33.From Fig. 4-35, we see that a Bluetooth device can be in two piconets at the same time. Is there any reason why one device cannot be the master in both of them at the same time?
34.Figure 4-25 shows several physical layer protocols. Which of these is closest to the Bluetooth physical layer protocol? What is the biggest difference between the two?
35.Bluetooth supports two types of links between a master and a slave. What are they and what is each one used for?
36.Beacon frames in the frequency hopping spread spectrum variant of 802.11 contain the dwell time. Do you think the analogous beacon
17
frames in Bluetooth also contain the dwell time? Discuss your answer.
37.Consider the interconnected LANs showns in Fig. 4-44. Assume that hosts a and b are on LAN 1, c is on LAN 2, and d is on LAN 8. Initially, hash tables in all bridges are empty and the spanning tree shown in Fig 4-44(b) is used. Show how the hash tables of different bridges change after each of the following events happen in sequence, first (a) then (b) and so on.
a. (a) a sends to d. b. (b) c sends to a. c. (c) d sends to c.
d. (d) d moves to LAN 6. e. (e) d sends to a.
38.One consequence of using a spanning tree to forward frames in an extended LAN is that some bridges may not participate at all in forwarding frames. Identify three such bridges in Fig. 4-44. Is there any reason for keeping these bridges, even though they are not used for forwarding?
39.Imagine that a switch has line cards for four input lines. It frequently happens that a frame arriving on one of the lines has to exit on another line on the same card. What choices is the switch designer faced with as a result of this situation?
40.A switch designed for use with fast Ethernet has a backplane that can move 10 Gbps. How many frames/sec can it handle in the worst case?
41.Consider the network of Fig. 4-49(a). If machine J were to suddenly become white, would any changes be needed to the labeling? If so, what?
42.Briefly describe the difference between store-and-forward and cut-through switches.
43.Store-and-forward switches have an advantage over cut-through switches with respect to damaged frames. Explain what it is. 44.To make VLANs work, configuration tables are needed in the switches and bridges. What if the VLANs of Fig. 4-49(a) use hubs rather than multidrop cables? Do the hubs need configuration tables, too? Why or why not?
45.In Fig. 4-50 the switch in the legacy end domain on the right is a VLAN-aware switch. Would it be possible to use a legacy switch there? If so, how would that work? If not, why not?
第五章
Problems
18
1. Give two example computer applications for which
connection-oriented service is appropriate. Now give two examples for which connectionless service is best.
2. Are there any circumstances when connection-oriented service will (or at least should) deliver packets out of order? Explain.
3. Datagram subnets route each packet as a separate unit, independent of all others. Virtual-circuit subnets do not have to do this, since each data packet follows a predetermined route. Does this observation mean that virtual-circuit subnets do not need the capability to route isolated packets from an arbitrary source to an arbitrary destination? Explain your answer. 4. Give three examples of protocol parameters that might be negotiated when a connection is set up. 5. Consider the following design problem concerning implementation of virtual-circuit service. If virtual circuits are used internal to the subnet, each data packet must have a 3-byte header and each router must tie up 8 bytes of storage for circuit identification. If datagrams are used internally, 15-byte headers are needed but no router table space is required. Transmission capacity costs 1 cent per 106 bytes, per hop. Very fast router memory can be purchased for 1 cent per byte and is depreciated over two years, assuming a 40-hour business week. The statistically average session runs for 1000 sec, in which time 200 packets are transmitted. The mean packet requires four hops. Which implementation is cheaper, and by how much?
6. Assuming that all routers and hosts are working properly and that all software in both is free of all errors, is there any chance, however small, that a packet will be delivered to the wrong destination? 7. Consider the network of Fig. 5-7, but ignore the weights on the lines. Suppose that it uses flooding as the routing algorithm. If a packet sent by A to D has a maximum hop count of 3, list all the routes it will take. Also tell how many hops worth of bandwidth it consumes. 8. Give a simple heuristic for finding two paths through a network from a given source to a given destination that can survive the loss of any communication line (assuming two such paths exist). The routers are considered reliable enough, so it is not necessary to worry about the possibility of router crashes. 9. Consider the subnet of Fig. 5-13(a). Distance vector routing is used, and the following vectors have just come in to router C: from B: (5, 0, 8, 12, 6, 2); from D: (16, 12, 6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The measured delays to B, D, and E, are 6, 3, and 5, respectively. What is C's new routing table? Give both the outgoing line to use and the expected delay.
19
10.If delays are recorded as 8-bit numbers in a 50-router network, and delay vectors are exchanged twice a second, how much bandwidth per (full-duplex) line is chewed up by the distributed routing algorithm? Assume that each router has three lines to other routers. 11.In Fig. 5-14 the Boolean OR of the two sets of ACF bits are 111 in every row. Is this just an accident here, or does it hold for all subnets under all circumstances? 12.For hierarchical routing with 4800 routers, what region and cluster sizes should be chosen to minimize the size of the routing table for a three-layer hierarchy? A good starting place is the hypothesis that a solution with k clusters of k regions of k routers is close to optimal, which means that k is about the cube root of 4800 (around 16). Use trial and error to check out combinations where all three parameters are in the general vicinity of 16.
13.In the text it was stated that when a mobile host is not at home, packets sent to its home LAN are intercepted by its home agent on that LAN. For an IP network on an 802.3 LAN, how does the home agent accomplish this interception?
14.Looking at the subnet of Fig. 5-6, how many packets are generated by a broadcast from B, using
a. (a) reverse path forwarding? b. (b) the sink tree?
15.Consider the network of Fig. 5-16(a). Imagine that one new line is added, between F and G, but the sink tree of Fig. 5-16(b) remains unchanged. What changes occur to Fig. 5-16(c)?
16.Compute a multicast spanning tree for router C in the following subnet for a group with members at routers A, B, C, D, E, F, I, and K.
17.In Fig. 5-20, do nodes H or I ever broadcast on the lookup shown starting at A? 18.Suppose that node B in Fig. 5-20 has just rebooted and has no routing information in its tables. It suddenly needs a route to H. It sends
20