Review Questions

1) If all the links in the Internet were to provide the reliable-delivery service, would the TCP reliable-delivery service be completely redundant? Why or why not?

2) What are some of possible services that a link-layer protocol can offer to the network layer? Which of these link-layer services have corresponding services in IP? In TCP?

3) Suppose the information content of a packet is the bit pattern 1010101010101011 and an even parity scheme is being used. What would be the value of the checksum field in a single parity
  scheme?

4) Suppose two nodes start to transmit at the same time a packet of length L over a broadcast channel of rate R. Denote the propagation delay between the two nodes as t_prop. Will there be a collision if  t_prop < L/R? Why or why not?

5) In section 5.2.1, we listed for desirable characteristics of a broadcast channel. Slotted ALOHA has which of these charateristics? Token passing has which of these characteristics?

6) What are human cocktail analogies for polling, and token passing protocols?

7) Why would the token-ring protocol be inefficient if the LAN has a very large perimeter?

8) How big is the LAN address space? The IPv4 address space? The IPv6 address space?

9) Suppose nodes A, B, and C each attach to the same broadcast LAN (through their adapters). If A sends thousands of frames to B with each frame adddressed to the LAN address of B, will C's adapter process these frames? If so, will C's adapter pass the IP datagrams in these frames to C (i.e., the adapter's parent node)? How will your answers change if A sends frames with the LAN broadcast address?

10) Why is an ARP query sent within a broadcast frame? Why is an ARP response sent within a frame with a specific LAN address?

11) For the network in Figure 5.3-4, the router has two ARP modules each with its own ARP table. Is it possible that the same LAN address appear in both tables?

12) Compare the frame structures for 10BaseT, 100BaseT and Gigabit Ethernet. How do they differ?

13) Suppose a 10 Mbps adapter sends into a channel an infinite stream of 1s using Manchester encoding. The signal emerging from the adatper will have how many transitions per second?

14) After the 5th collision, what is the probability that the value of K that a node chooses is 4? The result K=4 corresponds to a delay of how many seconds on a 10 Mbps Ethernet.

15) Does the TC sublayer at the transmitter fill in any of the fields in the ATM header? Which ones

Section 5.6

16) In the IEEE 802.11 specification, the length of the SIFS period must be shorter than the DIFS paeriod.  Why?

17)  Suppose the IEEE 802.11 RTS and CTS frames were as long as the standard DATA and ACK frames.  Would there be any advantage to using the CTS and RTS frames?  Why?

Section 5.9

18) Does the TC sublayer distinguish between different VCs at either the transmitter or receiver?

19) Why is it important for the TC Sublayer in the transmitter to provide a continuous stream of cells when the PMD Sublayer is cell based?

20) Does the TC sublayer at the transmitter fill in any of the fields in the ATM header? Which ones?
 

Problems

2) Give an example (other than the one in Figure 5.2-3!) showing that two-dimensional parity checks can correct and detect a single bit error. Show by counterexample that a double bit error can not always be corrected. Show by example that some double bit errors can be detected.

3) Suppose the information portion of a packet (D in Figure 5.2-1 contains 10 bytes consisting of the 8-bit unsigned binary representation of the integers 0 through 9. Compute the Internet checksum for this data.

4) Consider the 4-bit generator, G shown in Figure 5.2-5,  and suppose that D has the value 10101010.  What is the value of R?

5) Consider the single sender CDMA example in Figure 5.3-4.  What would be the sender's output (for the two data bits shown)  if the senders CDMA code were (1, -1, 1, -1, 1, -1, 1, -1)?

6) Consider sender 2 in Figure 5.3-5.  What is the sender's output to the channel (before it is added to the signal from sender 1), Z_i,m ² ?

7) Suppose that the receiver in Figure 5.3-5 wanted to receive the data being sent by sender 2.  Show (by calculation), that the receiver is indeed able to recover sender 2's data from the aggregate channel signalby using sender 2's code.

8) In  section 5.3, we provided an outline of the derivation of the efficiency of slotted ALOHA. In this problem we''ll complete the derivation.

a) Recall that  when there are N active nodes the efficiency of slotted ALOHA is Np(1-p)^N-1 . Find the value of p that maximizes this expression.

b) Using the value of p found in part (a), find the efficiency of slotted ALOHA by letting N approach infinity. Hint: (1 - 1/N)^N approches 1/e as N approaches infinity.

10) Graph the efficiency of slotted ALOHA and pure ALOHA as a function of p for N=100.

11) Consider a broadcast channel with N nodes and a transmission rate of R bps. Suppose the broacast channel uses polling (with an additional polling node) for multiple access. Suppose the amount of time from when a node completes transmission until the subsequent node is permitted to transmit (i.e., the polling delay) is t_poll. Suppose that within a polling round, a given  node is allowed to transmit at most Q bits. What is the maximum throughput of the broadcast channel.

12) Consider three LANs interconnected by two routers, as shown in the diagram below.

a) Redraw the diagram to include adapters.
b) Assign IP addresses to all of the interfaces. For LAN 1 use addresses of the form 111.111.111.xxx ; for LAN 2 uses addresses of the form 122.222.222.xxx ; and for LAN 3 use addresses of the form 133.333.333.xxx .
c) Assign LAN addresses to all of the adapters.
d) Consider sending an IP datagram from host A to host F. Suppose all the ARP tables are up-to-date. Enumerate all the steps as done for the single-router example in section 5.3.2.
e) Repeat (d), now assuming that the ARP table in the sending host is empty (and the other tables are up-to-date).

13) Recall that with the CSMA/CD protocol, the adapter waits K*512 bit times after a collision, where K is drawn randomly. For K=100, how long does the adapter wait until returning to Step 2 for a 10 Mbps Ethernet? For a 100 Mbps Ethernet?

14) Suppose nodes A and B are on the same 10 Mbps Ethernet segment, and the propagation delay between the two nodes is 225 bit times. Suppose node A begins transmitting a frame, and before it finishes station B begins transmitting a frame. Can A finish transmitting before it detects that B has transmitted? Why or why not? If the answer is yes, then A incorrectly believes that its frame was successfully transmitted without a collision.

Hint: Suppose at time t=0 bit times, A begins transmitting a frame. In the worst case, A transmits a minimum size frame of 512+64 bit times. So A would finish transmitting the frame at t=512+64 bit times. Thus the answer is no if B's signal reaches A before bit time t=512+64 bits. In the worst case, when does B's signal reach A?

15) Suppose nodes A and B are on the same 10 Mbps Ethernet segment, and the propagation delay between the two nodes is 225 bit times. Suppose A and B send frames at the same time, the frames collide, and then A and B choose different values of K in the CSMA/CD algorithm. Assuming no other nodes are active, can the retransmissions from A and B collide? For our purposes, it suffices to work out the following example. Suppose A and B begin transmission at t=0 bit times. They both detect collisions at t=225 bit times. They finish transmitting jam signal at t= 225+48= 273 bit times. Suppose K_A=0 and K_B=1. At what time does B schedule its retransmission? At what time does A begin transmission? (Note, the nodes must wait for an idle channel after returning to Step 2-- see protocol.) At what time  does A's signal reach B? Does B refrain from transmitting at its scheduled time?

16) Consider a 100Mbps 100BT Ethernet. In order to have an efficiency of .50, what should be the maximum distance between a node and the hub? Assume a frame length of 64 bytes and that there are no repeaters. Does this maximum distance also ensure that a transmitting node A will be able to detect whether any other node transmitted while A was transmitting? Why or why not? How does your maximum distance compare to the actual 100 Mbps standard?

17) In this problem you will derive the efficiency of a CSMA/CD-like multiple access protocol. In this protocol, time is slotted and all adapters are synchronized to the slots.  Unlike slotted ALOHA, however, the length of a slot (in seconds) is much less than a frame time (the time to transmit a frame). Let S be the length of a slot. Suppose all frames are of constant length L = k R S, where R is the transmission rate of the channel and k is a large integer. Suppose there are N nodes, each with an infinite number of frames to send. We also assume that t_prop < S, so that all nodes can detect a collision before the end of a slot time. The protocol is as follows:

• If for a given slot, no node has possession of the channel, all nodes contend for the channel; in particular, each node transmits in the slot with probability p. If exactly one node transmits in the slot, that node takes possession of the channel for the subsequent k-1 slots and transmits its entire frame.
• If some node has possession of the channel, all other nodes refrain from transmitting until the node that possesses the channel has finsished transmitting its frame. Once this node has transmitted its frame,  all nodes contend for the channel.

a) For fixed N and p, determine the efficiency of this protocol.
b) For fixed N, determine the p that maximizes the efficiency.
c) Using the p (which is a function of N) found in part (b), determine the efficiency as N approaches infinity.
d) Show that this efficiency approaches 1 as the frame length becomes large.

18) Suppose two nodes, A and B, are attached to opposite ends of a 900 m cable, and that they each have one frame of 1000 bits (including all headers and preambles) to send to each other. Both nodes attempt to transmit at time t=0. Suppose there are four repeaters between A and B, each inserting a 20 bit delay. Assume the transmission rate is 10 Mbps, and CSMA/CD with backoff intervals of multiples of 512 bits is used. After the first collision, A draws K=0 and B draws K=1 in the exponential backoff protocol. Ignore the jam signal.

a) What is the one-way propagation delay (including repeater delays) between A and B in seconds. Assume that the signal propragation speed is 2 * 10⁸ m/sec.

b) At what time (in seconds) is A's packet completely delivered at B.

c) Now suppose that only A has a packet to send and that the repeaters are replaced with bridges. Suppose that each bridge has a 20 bit processing delay in addition to a store-and-forward delay. At what time in seconds is A's packet delivered at B?
 

a) How many IP networks are there in the above figure? Provide class C IP addresses for all of the interfaces including the router interfaces.

b) Provide LAN addresses for all of the adaptors.

c) Consider sending a datagram from host A to host F. Trace the steps assuming all the ARP tables are up-to-date.

d) Repeat c), but now assume that all ARP tables are up to date, except for the ARP tables in router, which are empty.

20) You are to design a LAN for the campus layout shown below.

You may use the following equipment:
 
 

Thin Coax	$1 per meter
UTP	$1 per meter
Fiber Optic Cable - pair	$2 per meter
NIC - thin coax ports	$70
NIC - UTP port	$70
2-Port Repeater	$800
Multiport Repeater (8 thin coax ports)	$1,500
Multiport Fiber Repeater (6 Fiber ports)	$2,000
2-Port Bridge (any combo of thin coax, UTP, fiber)	$2,200
Hub - 36 UTP ports	$4,000
Hub - 6 fiber ports, 24 UTP ports	$6,000
Pentium File Server - w/NOS (max. 30 users)	$9,000

Bridges always include interface cards.

You must respect the followng design requirements:

1. Each department must have access to the resources of all other departments.
2. The traffic generated by users of one department cannot affect another department's LAN unless accessing a resource on that other department's LAN.
3. A file server can support only 30 users.
4. File servers may not be shared by multiple departments.
5. All repeaters, bridges, and hubs must reside in the wiring closets (WCs).

b) Repeat (a), but using UTP (no thin coax) and, if deemed necessary, fiber optics.

21) Suppose a frame-relay VC generates packets of fixed lenght L. Let R, T_c and CIR denote the access rate, the measurement interval and the committed information rate, respectively. (a) As a function of these variables, determine how many high-priority packets the VC can send in a measurement interval. (b) As a function of these variables, determine how many low-priority packets the VC can send in a measurement interval. For part (b) assume that in each measurement interval, the VC first generates the maximum number of high-priority packets permitted and then generates low-priority packets.

22)  In Figure 5.9.1, suppose the source Ethernet includes a Web server which is very busy serving requests from clients in the destination Ethernet. Each HTTP response message is carried in one or more IP datagrams. When the IP datagrams arrive to the frame relay interface, each datagram is encapsulated in a frame-relay frame. Suppose that each Web object is of size O and each frame-relay packet is of size L. Suppose that the Web server begins to serve one object at the beginning of each measurement interval. Ignoring all packet overheads (at the application, transport, IP and frame-relay layers!), determine the maximum size of O (as a function of T_c, CIR and L) such that each object is entirely carried by high-priority frame-relay packets.

Discussion Questions

1) Roughly,what is the current price range of a 10 Mbps Ethernet adapter? Of a 10/100 Mbps adapter? Of  a Gigabit Ethernet adapter?

2) Hubs and switches are often priced in terms of number of interfaces (also called ports in LAN jargon). Roughly, what is current per-interface price range for a 10 Mbps hub? For a  100 Mbps hub? For a switch consisting of only 10 Mbps interfaces? For a switch consisting of only 100 Mbps interfaces?

3) Many of the functions of an adapter can be performed in software that runs on the node's CPU. What are the advantages and disadvantages of moving this functionality  from the adapter to the node?

4) Use the Web to find the protocol numbers used in a Ethernet frame for IP and ARP.

5) Is some form of ARP protocol necessary for IP over frame relay? Why or why not?