Link Layer Flashcards
What does the link layer do?
It deals with transmission of packets between neighbouring nodes
Link Layer Format
Link layer packets have an additional field to mark the exact time frame they occupy during transmission
Headers and footers are predefined byte sequences (syncwords) so that participants that freshly joined or have just woken up, i.e. all listeners, can be sure that a packet started when they hear the syncword
How do we make sure that the syncword/preamble doesn’t appear anywhere in the paket’s body?
- Byte Stuffing:
Naive approach would be to replace every occurence of the critical byte X with another byte Y. But if we do this we can longer distinguish between the Y that was used to replace X and the Y that was initially part of the message
Therefore we use escape sequences YA and YB (with A and B not euqal to X) Whenever a Y appears in the text we replace it with YA and each appearance of X in message is replaced by YB
This is inversible, so the receiver has to simply make the substiution in reverse
Problem: Packet’s body can become twice as long compared to its original value - Consistent Overhead Byte Stuffing:
Treat original body as a sequence of byte strings s0, s1, s2, … that are interrupted by the forbidden X byte
Alternating send the length of the string (|si|) and the string itself (si)
Receiver can construct initial message by joining the strings back together with X’s inbetween
si may be an empty string if there are multiple X’s in the message
If strings are short the encoded body is always exactly 1 byte longer than inital message, regardless of how often X occurs
The two concepts of the link layer
MAC: dictates access pattern to underlying wired or wireless medium
Phyical Layer: specifies encoding of data stream on medium
Checksum
Ziel: Fehlerübertragung schnell feststellen
Im Ethernet: wir XORen die ganzen Bytes die man hat
e.g. wir nehmen jedes Byte und schauen ob die Summe gerade oder ungerade ist. Und dann schreibe ich in die Checksum ein Bit rein, ob das ganze gerade oder ungerade ist. Aber wir bilden hier 1500 Bytes auf 4 Bytes ab, d.h. es kann vorkommen, dass wir zwar gewisse Bytes ändern, es aber noch immer dieselbe checksum ergibt. Funktioniert aber in der Praxis eigentlich recht gut.
Checksum over whole packet, including header and payload
Bei Bluetooth ist der Header gleich dreimal eingefügt, dass man Fehler nicht nur erkennt, sondern auch gleich verbessern kann.
Forward error correction: Man kriegt drei header, einer von den dreien sieht vielleicht anders aus als der Rest, schau einfach die Mehrheit an. Obwohl da Fehler drin sind, kann ich also trotzdem rausfinden, was die korrekte Information ist -> direkt korrigieren
Eine weitere Error detection methode sind acknowledgments
What are MAC addresses?
Used to identify nodes below network layer. Formatted as 6 two digit hexacdecimal number seperated by columns
On LINK LAYER ONLY MAC Addresses are valid source and destination addresses for packets
How are MAC addresses assigned?
Every device is assigned unique MAC address by the manufacturer
Which device operates strictly below network layer?
Switch: is a central network node with the task of mediating traffic between neighbouring nodes
Unlike Routers, Switches are UNAWARE of IP addresses -> switches only operate on link layer
In their most basic form: they simply copy the arriving packet and to all other connected neighbours without further inspection or modification
Most switches, however, remember the MAC addresses of incoming packets at its port. If a packet arrives with a destination MAC addresses that the switch already knows, it is forwarded directly to that node without involving other ports
A switch can assign multiple MAC addresses to the same port -> chaining
Wie komme ich von IP auf MAC
ARP (Address Resolution Protocol)
Send a query including the IP address a to ff:ff:ff:ff:ff:ff (you make a broadcast, denn an dieser Addresse hört jedes Gerät zu)
Falls es ein Gerät gibt, das diese IP Addresse hat, dann antwortet es mit der dazugehörenden MAC Adresse
Wenn wir nach dem timeout noch immer kein Ergebnis erhalten haben -> IP Adresse exisitiert nicht oder ist nicht erreichbar
Das Protokoll benutzt Caching, somit werden lookups nur für neue IP Addressen durchgeführt
Wie komme ich von MAC auf IP
DHCP (Dynamic Host Configuration Protocol)
Client sends a request with its MAC addresses to 255.255.255.255 (global broadcast address)
DCHP Server decides on an unused address a, marks it as reserved and replies with the offer a
Client replies by broadcasting the acceptance of the offer
Server marks a as used and replies with final confirmation
Client receives confirmation and uses a as its IP address from there on
Physical Layer: Line Coding
Line Coding: physical encoding representing a data stream as a series of values from {-1,0,1}
Simple Line Coding: 0 is mapped to -1 and 1 is mapped to +1
Potential Problems with simple line coding when there is long string of equal bits:
Hard to verify if signal is still being send
Receiver and Sender’s clock have to be running at exactly the same rate
Undesirable bias towards +1 or -1
2. Manchester Coding Every bit is represented by two states: 0: first -1 then 1 1: first 1 then -1 Receiver may use ongoing signal's edges to keep in sync
- Amplitude Modulation: but if a signal is reflected from a surface to reach to reach location behind corner, the signal’s power is decreased -> amplitude decreases. Amplitude Modulatopn is subjective to noise
- Frequency Modulation: Frequency is varied only by small amounts, staying within narrow frequency band. Very robust to noise
- Phase Modulation: Wie verschiebe ich das Signal? Starte ich früher oder später
Symbols: Multiple data bits can be grouped into symbold before encoding, allowing to make use of the ability to represent more than two states at time in the coding
Wireless Phenomena
Wireless transmissions transmit and receive radio waves using antennas Typical phenomena: shadowing (wir übermitteln drahtlos dann kommt eine Wand ->dahinter hören wir viel weniger), reflection, diffraction Transmission is a broadcast: any wireless receiver physyically within range will receive sent message, not just intended recipient Within range means signal is sufficiently stronger than electromagnetic noise and interfering signals - SINR Threshold beta (SINR) depends on hardware and modulation
Fading: in vauum: electromagnetic signal’s strength decreases quadratically with distance. When travleling through other materials even quicker
Multipath: Signal has different travel time over different paths. Hence, received signal may be sum of several components delayed by different amounts
Full-duplex: Devices can send and receive simultaneously: wired communication
Half-duplex: Devices can’t send and receive at the same time: wireless communication: outgoining signal at local antennas is of orders magnitude stronger than incoming signal
MAC: Multiple Access
Multiple devices use a shared medium, how to we avoid transmission collisions?
- Time division (wir lassen den anderen zuerst ausreden): Avoid collision by having senders take turns instead of continously sending out packets
1.1 Carrier Sensing: listen to the medium for a short while before sending, such that one might pick up on an ongoing transmission
Problem:
Hidden Terminal: One may not always hear other transmissions due to fading
Exposed Terminal: Senders are close to each other but want to reach different receivers. Since they definitely hear each other, one will be forbidden from sending, even though there would be no collision
Solution for Hidden Terminal: RTS/RTC protocol:
Before sending, the sender sends out a ready to send packet (im broadcast, jeder kriegt es mit)
If recipient hears the broadcast it answers with a clear to send packet
If the sender receives CTS packet, it starts transmission, otherwise it waits for a certain amount of time and tries again later
Other nodes hearing the CTS will abstain from sending, because they know that one of their neighbours is about to receive a package
This protocol also helps with the exposed terminal problem, as long as one of the nodes is not already transmitting
Collision Response: not avoidance, but rather how to deal with them once occurred
Collisions are detected when sender doesn’t receive ACK packet
If devices are full-duplex collision can be detected as they occur
1.2 How does the packet know how long it has to wait before resending packet? -> Exponential Backoff
1.3 How would a strategy
maximize the probability of exactly one node sending at a time? -> Slotted Aloha
- Space Division (Zwei Räume können unabhängig voneinander gleichzeitig reden): Wenn man zwei Leute hat die gleichzeitig senden wollen, und man sicherstellt dass diese weit genug voneinander entfernt sind, dann stören sie einander nicht
- Frequency Division (Wenn zwei Leute komplett unterschiedliche Stimmen haben, kann man sich auf einen fokussieren): Wenn zwei Leute völlig verschiedene Frequenzen benutzen, können die Frequenzen aneinander vorbeigehen
- Code Division (Zwei Leute sprechen unterschiedliche Sprache, it doesn’t directly avoid collisions but allows resolving them): GPS Satelliten senden gleichzeitig und auf gleicher Frequenz, verwenden aber einen anderen Code. Jeder Sender bekommt einen unique Code bestehend aus -1 und +1
Um 0 zu senden schickt der Sender einfach seinen Code, um 1 zu senden, negiert er seinen Code
Walsh Code: +1 entspricht 0 und -1 entspricht 1. Walh Codes orthogonal sind: Gleich viele Bits wo sie gleich sind, und gleich viele Bits wo sie ungleich sind
List a few differences between MAC addresses and IP addresses
They operate on different layers in the network stack: link layer vs network layer.
• Different size (6 bytes vs 4 or 16 bytes) and notation
• Assigned by hardware manufacturer vs by network administrator or DHCP
• Used for routing vs used as unique identifier (esp. before an IP address is assigned)
Why don’t we only use MAC addresses?
MAC addresses are impractical for routing on the Internet as they are not grouped by
network or location. (Instead they are grouped by manufacturer.)
