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

Note 1: please TYPE your answer whenever possible. This requirement doesn't imply that you don't need to show the details. If you feel that the detail is better shown by using paper and pencil, feel free to do so.

• (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.

  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).
• (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.)

• (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?)

• (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.)

• (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:
  • 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