Data-Link Layer 1 Flashcards
Introduction
Differences between layers
Transport Layer: communication between applications
Network Layer: communication between source and destination
Link Layer: communication between nodes (routers and hosts)
Introduction
Nodes
Hosts and routers
Introduction
Data-Link Layer
- Communication between nodes
- Has responsibility of transferring datagram from one node to a physically adjacent node over a link
- 2-Layer Packet: frame encapsulates datagram
Introduction
Link
Communication channels that connect adjacent nodes along communication path
Introduction
Link Types
- Wired
- Wireless
- LANs
Introduction
Link-Layer: Context
- Datagrams are transferred by different protocols over different links (wifi, ethernet, …)
- Each link protocol provides different services (may not be reliable)
Introduction
Link Layer: Services
- Framing, link access
- Reliable delivery between adjacent nodes
- Flow control
- Error detection and correction
- Half-duplex and full-duplex
Introduction: Services
Framing, link access
- Encapsulates datagram into frame, adding header/trailer
- Controls channel access if shared medium
- “MAC address” in frame headers identifies source/dest
Introduction: Services
Flow Control
Pacing between adjacent sending and receiving nodes
Introduction: Services
Error detection and correction
- Errors caused by singal attentuation, noice
- Receiver detects errors and signals retransmission or drops frames
Introduction: Services
Half-duplex and full-duplex
With half-duplex, nodes at both ends of link can transmit, but not at same time
Introduction
Where is the link-layer implemented?
- In each and every host
- Uses network interface card (NIC) or on a chip
- Attaches into host’s system buses
- Combination of hardware, software, and firmware
Introduction
Interface Communication: Sender Side
- Encapsulates datagram in frame
- Adds error checking bits, reliable data transfer, flow control, etc.
Introduction
Interface Communication: Receiver Side
- Looks for errors, reliable data transfer, flow control, etc.
- Extracts datagram, passes to upper layer at receiving side
Introduction
Error Detection
Datagram: d data bits + EDC
EDC: error detection and correction bits, larger EDC yields better detection
D: data protected by error checking, may include header fields
Introduction
Parity Checking: Single Bit Parity
Detects single bit errors
Even Parity: Set parity bit so there is an even number of 1s
Introduction
Parity Checking: Two-Dimensional Bit Parity
Detect and correct single bit errors
(if more then one error, cannot correct)
Introduction
CRC
- Cyclic Reduncancy Check
- Goal: choose CRC bits, R, such that <D, R> exactly divisible by G (mod 2)
- If non-zero remainder: error detected
- D: data bits (given, binary)
- G: bit pattern (generator), of R+1 bits (given)
Multiple Access Protocols
Link Types
Point-to-Point: link between Ethernet switch and host
Broadcast: Uses old-fashioned Ethernet, cable-based access network (shared)
Multiple Access Protocols
Multiple Access Protocol
- Used on single shared broadcast channels
- Determines how nodes share channel (determines when node can transmit)
- Collision: if simultaneous transmission/two or more signals received by node
Multiple Access Protocols
Three Broad Protocol Classes
- Channel Partitioning
- Random Access
- “Taking Turns”
Multiple Access Protocols
Protocol Classes: Channel Partitioning
- Divide channel into smaller partitions
- Allocate partition to node for exclusive use
Multiple Access Protocols
Protocol Classes: Random Access
- Channel not divided, allow collisions
- Specifies how to detect collisions and how to recover from them
- Examples: ALOHA/slotted ALOHA, CSMA/CD/CA
Multiple Access Protocols
Protocol Classes: “Taking Turns”
- Nodes take turns using the shared channel
- Nodes with more to send can take longer turns
Multiple Access Protocols
Channel Partitioning MAC Protocols: FDMA
- Frequency Division Multiple Access
- Channel spectrum divided into frequency bands
- Each station assigned fixed frequency band
- Con: Unused transmission time in frequency bands go idle
Multiple Access Protocols
Channel Partitioning MAC Protocols: TDMA
- Time Division Multiple Access
- Access to channel is given in “rounds”
- Each station gets fixed length slot in each round (length = packet transmission time)
* Con: unused slots go idel
Multiple Access Protocols
Random Access Protocols: Pure ALOHA
- Simpler then slotted bc no synchronization (when frame arrives, transmit immediately)
- Higher collision probability bc no synchronization
- Vulnerable Time: 2t (if a single bit overlaps, then both frames with value t have to retransmit)
Multiple Access Protocols
Random Access Protocols: Slotted ALOHA (Assumptions)
- All frames same size
- Time divided into equal size slots
- Nodes to start transmission only at beginning of slot
- Nodes are synchronized
- If 2 or more nodes transmit in slot, all nodes detect collision
Multiple Access Protocols
Random Access Protocols: Slotted ALOHA (Operation)
When node obtains frame, transmits in next slot:
If no collision: node can send new frame in next slot
If collision: node retransmits frame in each subsequent slot with prob b until success
Vulnerable Time: t
Multiple Access Protocols
Random Access Protocols: Slotted ALOHA (Pros)
- Single active node can continuously transmit at full rate of channel
- Highly decentralized: only slots in nodes need to be in sync
- Simple
Multiple Access Protocols
Random Access Protocols: Slotted ALOHA (Cons)
- Collisions, wasting slots
- Idle slots
- Nodes may be able to detect collision in less time then time to transmit packet
- Clock synchronization
Multiple Access Protocols
Slotted ALOHA Channel Utilization
Channel Utilization = # of slots / # of successes
