Data-Link Layer 2 Flashcards
Multiple Access Protocols
Types of Random Access Protocols
- ALOHA
- CSMA
- CSMA/CD
- CSMA/CA
Random Access Protocols: CSMA
CSMA
- Carrier Sense Multiple Access
- Listen before transmit
- Reduce possibility of collision
- Cannot completely eliminate possibility of collision
Random Access Protocols: CSMA
Simple CSMA
If channel sensed idle: transmit entire frame
If channel sensed busy: defer transmission
Random Access Protocols: CSMA
CSMA: Persistance Method Types
- 1-persistent
- Non-persistent
- p-persistent
Random Access Protocols: CSMA
CSMA: 1-Persistent
- Continuously senses at the beginning of each time unit.
- Transmits when channel finally idle.
Random Access Protocols: CSMA
CSMA: Non-Persistent
- Wait to sense for a random amount of time.
- Transmits when channel finally idle.
Random Access Protocols: CSMA
CSMA: p-Persistent
- Continuously sense at the beginning of each time slot.
- When channel finally idle, send based on probability p (doesn’t send every time).
- If probability p prevents sending, wait for set amount of time and try to retransmit with probability p again. (repeats until successful)
Random Access Protocols: CSMA
CSMA: Persistence Method Downfall
- If 2 stations send frame at same time, collision occurs but station continues transmitting until whole frame sent
- Wastes time instead of immediately interrupting transmission
Random Access Protocols: CSMA
CSMA/CD
- Carrier Sense Multiple Access/Collision Detection
- Collisions detected within short time
- Colliding transmissions aborted, reduces amount of time wasted in collisions
- Collision detection easy in wired, difficult in wireless
Random Access Protocols: CSMA
CSMA: Collisions
- Collision: entire packet and transmission time wasted
- Collisions can still occur even if carrier is sensing (two nodes can start at exact same time)
Random Access Protocols: CSMA
CSMA/CD: Algorithm
- NIC receives datagram from network layer, creates frame
- NIC senses channel (if idle: transmit, if busy: wait until channel idle)
- If NIC transmits entire frame without collision, then complete
- If NIC detects collision, abort and send jam signal
- After aborting: NIC enters Binary (Exponential) Backoff
Random Access Protocols: CSMA
CSMA/CD: Binary (Exponential) Backoff
- After mth collision, NIC chooses K at random from {0, 1, 2, …, 2^m - 1}
- NIC waits K x 512 bit times, returns to step 2 in algoritm
- More Collisions = longer backoff interval
Random Access Protocols: CSMA
CSMA/CA
- Carrier Sense Multiple Access/Collision Avoidance
- Specficially designed for wireless networks
- In Wired: if collision occured then energy of received signal almost doubles, allowing station to sense possibility of collision
- In Wireless: can’t increase energy bc most of it used for transmission and can only increase energy by small amount
Random Access Protocols: CSMA
CSMA/CA: Three Strategies
- InterFrame Space (IFS)
- Contention window
- Acknowledgments
Random Access Protocols: CSMA
CSMA/CA Strategies: InterFrame Space (IFS)
- When station finds channel busy: it senses the channel again
- When station finds channel idle: it wait for a period of time called IFS time before transmitting
- Can also be used to define priority of station or frame (higher IFS means lower priority)
Random Access Protocols: CSMA
CSMA/CA Strategies: Contention Window
- Amount of time is divided into slots
- Station that is ready to transmit chooses random value for wait time
Random Access Protocols: CSMA
CSMA/CA Strategies: Acknowledgments
Positive ACKs and time-out timer are used to help guarantee successful transmission
Random Access Protocols: MAC Protocols
MAC Protocol Types
- Channel partitioning MAC protocols
- Random access MAC protocols
- “Taking turns” protocols
Random Access Protocols: MAC Protocols
MAC Protocols: Channel Partitioning
- Share channel efficiency and fairly at high load
- Inefficient at low load; delay in channel access (1/N bandwidth allocated even if only 1 active node)
Random Access Protocols: MAC Protocols
MAC Protocols: Random Access
Efficient at low load: single node can fully utilize channel
High load: collision overhead
Random Access Protocols: MAC Protocols
MAC “Taking Turns” Protocol Types
- Polling
- Token Passing
- Reservation
Random Access Protocols: MAC Protocols
MAC “Taking Turns”: Polling
- Master node “invites” other nodes to transmit in turn
- Typically used with “dumb” devices
- Concerns: polling overhead, latency, single point of failure (master)
Random Access Protocols: MAC Protocols
MAC “Taking Turns”: Token Passing
- Control token passed from one node to next sequentially
- Token message
- Concerns: token overhead, latency, single point of failure
Random Access Protocols: MAC Protocols
MAC “Taking Turns”: Reservation Method
- Stations reserve specific time-slots
- When ready to send, uses reserved time slot
- When all time slots reserved, waits until one is avaliable
LANs: MAC Addressing
IP Addresses
- 32-bit IP address (uses decimal)
- Network-layer address for interface
- Used for network layer forwarding
- Like postal address
- Not portable, changes upon IP Subnet change
LANs: MAC Addressing
MAC Addresses
- 48-bit MAC address (uses hex)
- Each interface on LAN as unique MAC address (permenant at manufacturing)
- Function: used “locally” to get frame from one interface to another physically-connected interface (like IP addressing but for same subnet)
- Like social security number
- Portable, always the same
LANs: MAC Addressing
ARP
- Address Resolution Protocol
- Used to determine interface’s MAC address knowing its IP address
- Uses ARP Table
LANs: MAC Addressing
ARP Table
- Each IP node (host, router) on LAN has table
- IP/MAC address mappings for some LAN nodes (as well as TTL for mapping)
- TTL: time after which address mapping will be forgotten
LANs: MAC Addressing
ARP Steps
- Sender broadcasts ARP query with target IP address
- Target responds with ARP response
- Sender receives targets reply and adds MAC address to ARP table
LANs: Ethernet
Data-Link Layer Responsibility
Tells what kind of medium (wired or wireless)
LANs: Ethernet
Physical Layer Responsibility
Tells what specific version of medium type (if wired, then what kind of wire?)
LANs: Ethernet
Ethernet Frame
Sending an interface encapsulates IP datagram into an Ethernet Frame
<preamble, dest address, src address, type, data, crc>
Preamble: used to synchronize receiver/sender clock rates
Addresses: 6 bytes src/dest MAC addresses (if adapter gets not matching dest address then discards, otherwise passes to network layer)
Type: indicates what higher layer protocol (usually IP)
CRC: cyclic redundancy check at receiver
LANs: Switches
Switch
- Link-layer device that takes an active role (are Ethernet participants)
- Transparent and plug-and-play/self-learning
- Able to handle multiple messages at once without collisions (as long as not same path)
- Stores and forwards Ethernet frames
- Examines incoming frame’s MAC address and selectively forwards frame to one-or-more outgoing links
LANs: Switches
Hubs
- Simple repeaters
- Plug and play
- Not able to handle multiple message at once, collision will occur
- Don’t interpret Ethernet, just repeats PHY signals
LANs: Switches
Plug-and-play
Device does not need to be configured
LANs: Switches
Transparent
Hosts unaware of presence of device
LANs: Switches
Self-Learning
- Switch learns which hosts can be reached through which interfaces and records in switch table
- If dest location unknown: flood (broadcast to all hosts in LAN)
- If dest location known: selectively send on just one link
LANs: Switches
Switch Forwarding Table
- holds pair of <MAC address of host, interface to reach host, TTL>
- Looks like routing table
LANs: Switches
Small Institutional Networks
Switch:Info meant for specific department is flooded to all departments if dest location not known
Router: Info meant for specific department can be directed to just one specific department
LANs: Switches
Switches VS Routers
Both are store and forward:
Routers: network-layer devices (examine network-layer headers)
Switches: link-layer devices (examine link-layer headers)
Both have forwarding tables:
Routers: compute tables using routing algorithms, IP addresses
Switches: learn forwarding tables using flooding, learning, MAC addresses
LANs: VLANs
VLAN
- Virtual Local Area Network
- Switches supporting VLAN capabilities can be configured to define multiple virtual LANs over single physical LAN infrastructure
LANs: VLANs
Port-Based VLAN
Switch ports are grouped so that single physical switch operates as multiple virtual switches
LANs: VLANs
VLAN Frame Format
( preamble, dest address, src address, type (2-byte tag protocol ID + tag control info), data, crc )
2-byte tag protocol ID: indicates that dest device is on a VLAN
Tag control info: indicates which VLAN the dest device is in
