CS475: Computer Networks - The Physical Layer

Activity Goals

The goals of this activity are:
  1. To define the behaviors at the physical layer
  2. To define a 1 and a 0 on an electronic medium
  3. To explain the Ethernet protocol including protocols for collision avoidance
  4. To explain CSMA its use on the Internet
  5. To explain Non-CSMA Multiple Access protocols such as CDMA
  6. To explain the unique challenges of wireless technologies including 802.11 as a physical layer with respect to collisions and hidden peers

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Communication over a Shared Medium

Walkie-Talkie Public Domain Image

Questions

  1. How might you ensure that only one person speaks at a time?
  2. How do we know if a message is destined for us as opposed to someone else? What information would we need, and at what layer would we find it?
  3. At what point would you determine that your message was corrupted due to a collision? What would you do about it?
  4. Hubs are essentially repeater devices that echo the data from one sender to all ports on the hub. Why is this inefficient, and what could we do about it?
  5. Hubs even echo a packet back to the sender: why is this useful for collision detection purposes? Draw a diagram showing that a collision can occur even if two senders begin transmission on a clear line.
  6. We transmit data using bits, which are either 1 (on) or 0 (off). You can imagine this as a tone that is either on or off. Why can't we simply set the voltage or tone to high to transmit a 1, or simply turn it low or off to transmit a 0?

Model 2: One Approach to Multiple Access: Time Division Multiple Access (TDMA): The ALOHA Protocol

Pure ALOHA
Slotted ALOHA
Aloha PureVsSlotted

Questions

  1. In Pure ALOHA, those who wish to transmit do so without checking if the medium is clear. Collisions can happen at any time. If a collision occurs, the nodes back off for a random period of time. If any part of a transmission is corrupted, the whole frame is discarded; therefore, for how long is the transmission of two packets of size T vulnerable to collision with one another?
  2. What is the difference between Pure ALOHA and Slotted ALOHA? What is the vulnerable time period for two packets of size T using Slotted ALOHA? Which is more efficient?

Model 3: ALOHA Transmission Efficiency

The probability of x nodes transmitting a frame at the beginning of a Slotted ALOHA frame, when assuming that, on average, nodes transmit with probability G, is defined by a Poisson Distribution (an asymptotic extension of the Binomial Distribution): \(P(x) = \frac{G^{x} e^{-nG}}{x!}\), where n is 1 for slotted ALOHA, and 2 for ALOHA.

Questions

  1. Why do you think n = 2 for pure ALOHA in the formula above?
  2. What is P(1), the probability that exactly one node will transmit in a frame using Slotted ALOHA?
  3. In unslotted ALOHA, we must assume that only one node transmits during a specific frame, and also that no node transmits during the prior frame, to avoid a collision. These are independent events, so the unslotted probability is P = P(1) P(0). What is this, and how does it relate to the Slotted ALOHA probability of successful transmission?
  4. Take the derivative of the probability function for slotted ALOHA and for unslotted ALOHA with respect to G, and set it equal to 0 to maximize the function. Let x be a constant 1 for a single transmit node. At what value of G is each maximized? Plug in this value and set x equal to 1 to observe the maximum transmission efficiency. Hint: use the product rule!
  5. How many transmitters do you think there are on the Internet? Why do they not all collide with each other? Might a router (or switch) do something that a repeater hub does not that helps avoid collisions?
  6. What do you think a "collision domain" is?

Model 4: Communicating a bit via the Ethernet Standard IEEE 802.3

Manchester encoding both conventions

Questions

  1. In your own words, how is a 0 or a 1 represented by 802.3 Manchester Encoding?
  2. Look at a vew values of the 802.3 Manchester encoding, the data, and the clock. Write down a few sample values at a few snapshots in time. What binary expression might relate the data and clock to the Manchester encoding?

Model 5: Carrier Sense Multiple Access Protocols

Access Protocol Description
1-Persistent CSMA/CD (Ethernet - Unslotted) Listen before sending (CSMA) and send when clear; if a collision is detected via the receiving line (CD), stop transmitting and randomly wait before retrying when the medium is clear. Alternatively, CSMA without CD cannot stop transmitting as soon as the collision is detected, but rather it completes the frame despite the data corruption.
Non-Persistent CSMA Same as above, but also waits a random period of time even if the medium is clear.
P-Persistent CSMA (WiFi) Similar to above, but waits for a random period of time only if the medium was first detected to be busy. Transmit at the beginning of a known time slot interval.

Adapted from Wikipedia
CSMACD-Algorithm

Questions

  1. Why not use Non-persistent CSMA for Ethernet as opposed to 1-Persistent CSMA? What is the benefit, but what is the sacrifice?
  2. What might be an appropriate upper-bound for the random wait time if a collision occurs? How might this upper bound change if collisions continue to happen? What are the benefits and drawbacks of a very short or very long upper bound?
  3. In what ways is Ethernet more efficient than Aloha?

Model 6: Wired Ethernet

EthernetCableYellow3
Twisted pair based ethernet
CAT5e Cable

Questions

  1. What are some ways an Ethernet cable can be multiplexed to support faster throughput (or more "lanes")?
  2. What do you think are the speed limiting factors for throughput on an Ethernet cable?
  3. In a twisted-pair cable such as CAT5e or CAT6 Ethernet, there are two cables for each Ethernet connector pin (each of these pins has a pin connector and a ring connector). How might differential voltages on these lines be used to identify a 1 or a 0 bit?
  4. Do you think thicker copper wire can support higher frequency RF oscillations? What effect would this have on throughput?

Model 7: Frequency Division Multiple Access (FDMA): Wireless Protocols Including IEEE 802.11

Wifi hidden station problem
Csma ca
2.4 GHz Wi-Fi channels (802.11b,g WLAN)

Questions

  1. Why can't we use CSMA/CD with WiFi like we could with Ethernet? Hint: the problem described by the three wireless nodes A, B, and C above is called the "Hidden Node Problem"
  2. What are some ways we can mitigate the Hidden Node Problem?
  3. In the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) algorithm described in the flowchart above, what does RTS and CTS mean?
  4. To whom is an RTS or CTS message sent, if this feature is used?
  5. If a node hears an RTS message sent, but does not hear the corresponding CTS, what might be happening?
  6. How might we multiplex multiple WiFi access points across the 2.4GHz spectrum using Frequency Division Multiple Access (FDMA)? Which channel selections best avoid interference between access points in the 2.4GHz spectrum?

Model 8: The Code Division Multiple Access Protocol (CDMA)

Assuming orthogonal vectors a and b (called chip sequences or codes), generated from a Hadamard-Walsh Code: Orthogonal Vector Dot Product Definition from Wikipedia
Orthogonality Properties from Wikipedia
Orthogonality Properties from Wikipedia
Orthogonality Properties from Wikipedia
Orthogonality Properties from Wikipedia

Cdma orthogonal signals.png
CC BY-SA 3.0, Link

Questions

  1. What is a Walsh Matrix?
  2. A spreading sequence v is computed from each node's chip code such that each 1 in the vector remains a 1, and each 0 becomes a -1. Why do you think this is done?
  3. Each node transmits v for a 1 and -v for a 0 bit. What do you think is transmitted if no data is intended to be sent on the medium?
  4. What would happen if one takes the dot product of a received vector with a sender's spreading code? How might this change if there is interference due to simultaneous transmissions on the line? Specifically, what is the most important attribute of each value in the resulting vector of the dot product to determine what corresponding bit was transmitted (hint: it's not the magnitude of the value itself!)?
  5. How is constructive interference used to encode and, thus, to extract data from a shared medium when collisions occur between senders?
  6. What sacrifice was made to enable this spread-spectrum technique?

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.