Homework 4 Solution - MAC Layer (Due 09/28) (100 pts)

• (15 pts.) Problem 1: Why does Ethernet use Manchester encoding? Sketch the Manchester encoding for the bit stream: 0001110101. Sketch the differential Manchester encoding for the same bit stream.
  Ethernet uses Manchester encoding for two reasons. First, binary encoding does not differentiate between a 0 bit (0 volt) and an idle sensor (also 0 volts). Manchester encoding in Ethernet systems use +0.85 volts for a high signal and -0.85 volts for a low signal. Second, by using Manchester encoding, the receiver can determine the start, middle, and end of each bit without referencing some external clock. A high-to-low or low-to-high transition is used for every bit so that the receiver can synchronize with the sendor at any time.
  • Manchester: low-high|low-high|low-high|high-low|high-low|high-low|low-high|high-low|low-high|high-low|
  • Diff Manchester: l-h|l-h|l-h|h-l|l-h|h-l|h-l|l-h|l-h|h-l|

  Note: choose one from problem 2 and 3

• (20 pts.) Problem 2: 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? (Hint: In order to solve this problem, you need to be aware that the Ethernet technique always specifies a minimum frame size. There are two reasons for this: First, it makes it easier to distinguish between valid frame and garbage. Secondly, if the frame is too short, the transmission will be finished before the collision signal returns (the worst case takes 2tao where "tao" is the propagation delay). That is, the frame has to be longer than 2tao. See details on page 277. Make sure you understand this).
  The frame size should be long enough such that if there is a collision at the receiver's side, the sender can still hear it DURING the transmission. This way, the sender wouldn't mistakenly thought that the frame has been transmitted successfully. That is, the transmission time should be equal to or larger than the summation of time it takes for the first bit to propagate to the receiver and if collision occurs, for the jam signal to travel all the way back to the sender. Suppose the frame size is f, transmission rate is r, and propagation delay is t. Then f/r >= 2*t ==> f >= r * 2 * t = 1Gbps * 2 * (1km / 200000km/s) ==> f >= 10,000 bits = 1,250 bytes.
• (20 pts.) Problem 3: For a 10-Mbps LAN with a maximum length of 2500 meters and four repeaters (802.3 specification), the round-trip propagation delay has been determined to be nearly 50 musec in the worst case, including the time to pass through the repeaters. What is the smallest frame size? Explain how 512 bits or 64 bytes minimum Ethernet frame size comes from. (Note that 512 is not the answer to the first part of the problem. Again, refer to page 277 for help.)
  Similar to Problem 2, f/r >= 2*t ==> f >= r * 2 * t = 10Mbps * 50musec = 500 bits.

  Theoretically, the minimum frame size is 500 bits. To add some margin of safety, the value was rounded up to 512 bits (or 64 bytes) for Ethernet standards.

• (25 pts.) Problem 4: What is exponential backoff? After a collision, time is divided into discrete slots whose length is equal to 512 bit times, or 51.2 musec because of the reason explained in problem 3. Each station needs to wait K slots in order to transmit again, where K is a random number obtained using exponential backoff. 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 both 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? (Hint: Suppose A and B begin transmission at t=0 bit times. They both detect collisions at t=225 bit times. They finish transmitting a jam signal at t=225+48 = 273 bit times. Suppose K_A=0 and K_B=1. Think about at what time B schedules its retransmission? and at what time A begins transmission? At what time A's signal reaches B?)
  Exponential backoff is how randomization is done after a collision. After the first collision, each transmitter waits a random time between 0 and 1 frame time. If the retransmission collides, the transmitters wait for a random time between {0, 1, 2, 3} frame time. This pattern continues after each collision and the waiting time is randomly selected from 0 to 2^k-1 frame time until either the transmission occurs successfully or 10 collisions have been reached. After the 10th collision, the random number pool does not increase any more. When the 16th collision occurs, the sender simply gives up the transmission.

  Assume A and B transmit at the same time, t=0. Then their messages collide midway (after 112.5 bit times). It takes another 112.5 bit times for A and B to detect the collision. Both A and B then send out a 48-bit noise burses. The current time would be t=273 bit times. If K_A = 0 and K_B = 1, then A retransmits at t=273 bit times (B will not retransmit until t=273+512 = 785 bit times). Due to the propagation delay of 225 bit times, A's retransmission reaches B at t=273+225 = 498 bit times. Therefore, A will not collide with B.

• (20 pts.) Problem 5: Explain the exposed station problem and the hidden station problem. 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? Explain how the usage of RTS and CTS can avoid collision. (Note: there are three questions in this problem.)

  The exposed state problem occurs when a transmitter (B) erronenously thinks it cannot send data to another station (C) because a third party (A) that is in the range of B but NOT c is currently transmitting to a fourth party. Even though it is clear to send to C, transmitter B does not know this.

  The hidden station problem occurs when a station (A) tries to send data to another station (B), but A does not know that B is busy receiving a transmission from C that is outside the range of A.

  In Fig. 4-27, C is closer to A because we know that C is in the range of A, but D is not. This is known because C responds to A's RTS with a NAV channel, whereas D does not acknowledge the request until B sends its CTS.

  Using RTS and CTS helps avoid collisions because any other station that is in the range of the transmitter or receiver knows to hold transmissions until the ACK frame is received. Also, the transmitter knows it must wait until the CTS is received because it means that the receiver is busy and a collision would occur in the meantime.

• (20 pts.) Problem 6: Multiple choice problem. For each type of switching devices, hub, bridge, switch, and router, choose all the corresponding features from the following options:
  • Hub: a, i, p, r, u, w, y
  • Bridge: b, f, h, j, n, p, s, t, w, x
  • Switch: b, g, j, n, p, s, t, w, x
  • Router: c, f, h, k, o, q, s, t, w, y
  • a) physical layer device
  • b) link layer device
  • c) network layer device
  • d) transport layer device
  • e) application layer device
  • f) store-and-forward switching
  • g) cut-through switching
  • h) buffering
  • i) treat message as bit streams
  • j) treat message as frames
  • k) treat message as datagram
  • l) treat message as segment
  • m) treat message as message
  • n) data forwarding using hardware address
  • o) data forwarding using IP address
  • p) plug-and-play
  • q) manual configuration
  • r) if used as backbone (i.e. backbone hub, backbone bridge, backbone switch, backbone router) to connect three 10BaseT LAN segments, the collision areas of the three LAN segments are combined
  • s) if used as backbone (i.e. backbone hub, backbone bridge, backbone switch, backbone router) to connect three 10BaseT LAN segments, the collision areas of the three LAN segments are still separated
  • t) can connect LAN segments using different Ethernet techniques
  • u) cannot connect LAN segments using different Ethernet techniques
  • v) the maximum number hosts connected is infinity
  • w) the maximum number hosts connected is limited
  • x) runs CSMA/CD
  • y) doesn't run CSMA/CD

• (0 pts.) Problem 7: Briefly describe the difference the following concepts in the context of data link layer:
  • CS, CA, CD
  • persistency vs. non-persistency
  • 1-persistency vs. p-persistency
  • ALOHA vs. slotted ALOHA
  • store-and-forward vs. cut-through switches