Data-Link Layer 2 Flashcards
1
Q
Multiple Access Protocols
Types of Random Access Protocols
A
- ALOHA
- CSMA
- CSMA/CD
- CSMA/CA
2
Q
Random Access Protocols: CSMA
CSMA
A
- Carrier Sense Multiple Access
- Listen before transmit
- Reduce possibility of collision
- Cannot completely eliminate possibility of collision
3
Q
Random Access Protocols: CSMA
Simple CSMA
A
If channel sensed idle: transmit entire frame
If channel sensed busy: defer transmission
4
Q
Random Access Protocols: CSMA
CSMA: Persistance Method Types
A
- 1-persistent
- Non-persistent
- p-persistent
5
Q
Random Access Protocols: CSMA
CSMA: 1-Persistent
A
- Continuously senses at the beginning of each time unit.
- Transmits when channel finally idle.
6
Q
Random Access Protocols: CSMA
CSMA: Non-Persistent
A
- Wait to sense for a random amount of time.
- Transmits when channel finally idle.
7
Q
Random Access Protocols: CSMA
CSMA: p-Persistent
A
- 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)
8
Q
Random Access Protocols: CSMA
CSMA: Persistence Method Downfall
A
- 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
9
Q
Random Access Protocols: CSMA
CSMA/CD
A
- 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
10
Q
Random Access Protocols: CSMA
CSMA: Collisions
A
- Collision: entire packet and transmission time wasted
- Collisions can still occur even if carrier is sensing (two nodes can start at exact same time)
11
Q
Random Access Protocols: CSMA
CSMA/CD: Algorithm
A
- 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
12
Q
Random Access Protocols: CSMA
CSMA/CD: Binary (Exponential) Backoff
A
- 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
13
Q
Random Access Protocols: CSMA
CSMA/CA
A
- 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
14
Q
Random Access Protocols: CSMA
CSMA/CA: Three Strategies
A
- InterFrame Space (IFS)
- Contention window
- Acknowledgments
15
Q
Random Access Protocols: CSMA
CSMA/CA Strategies: InterFrame Space (IFS)
A
- 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)
16
Q
Random Access Protocols: CSMA
CSMA/CA Strategies: Contention Window
A
- Amount of time is divided into slots
- Station that is ready to transmit chooses random value for wait time
17
Q
Random Access Protocols: CSMA
CSMA/CA Strategies: Acknowledgments
A
Positive ACKs and time-out timer are used to help guarantee successful transmission
18
Q
Random Access Protocols: MAC Protocols
MAC Protocol Types
A
- Channel partitioning MAC protocols
- Random access MAC protocols
- “Taking turns” protocols
19
Q
Random Access Protocols: MAC Protocols
MAC Protocols: Channel Partitioning
A
- 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)
20
Q
Random Access Protocols: MAC Protocols
MAC Protocols: Random Access
A
Efficient at low load: single node can fully utilize channel
High load: collision overhead
21
Q
Random Access Protocols: MAC Protocols
MAC “Taking Turns” Protocol Types
A
- Polling
- Token Passing
- Reservation
22
Q
Random Access Protocols: MAC Protocols
MAC “Taking Turns”: Polling
A
- Master node “invites” other nodes to transmit in turn
- Typically used with “dumb” devices
- Concerns: polling overhead, latency, single point of failure (master)
23
Q
Random Access Protocols: MAC Protocols
MAC “Taking Turns”: Token Passing
A
- Control token passed from one node to next sequentially
- Token message
- Concerns: token overhead, latency, single point of failure
24
Q
Random Access Protocols: MAC Protocols
MAC “Taking Turns”: Reservation Method
A
- Stations reserve specific time-slots
- When ready to send, uses reserved time slot
- When all time slots reserved, waits until one is avaliable
25
# 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
26
# 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
27
# LANs: MAC Addressing
ARP
* Address Resolution Protocol
* Used to determine interface's MAC address knowing its IP address
* Uses ARP Table
28
# 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
29
# LANs: MAC Addressing
ARP Steps
1. Sender broadcasts ARP query with target IP address
2. Target responds with ARP response
3. Sender receives targets reply and adds MAC address to ARP table
30
# LANs: Ethernet
Data-Link Layer Responsibility
Tells what kind of medium (wired or wireless)
31
# LANs: Ethernet
Physical Layer Responsibility
Tells what specific version of medium type (if wired, then what kind of wire?)
32
# LANs: Ethernet
Ethernet Frame
Sending an interface encapsulates *IP datagram* into an *Ethernet Frame*
```
```
**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
33
# 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
34
# 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
35
# LANs: Switches
Plug-and-play
Device does not need to be configured
36
# LANs: Switches
Transparent
Hosts unaware of presence of device
37
# 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
38
# LANs: Switches
Switch Forwarding Table
* holds pair of
* Looks like routing table
39
# 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
40
# 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
41
# LANs: VLANs
VLAN
* **Virtual Local Area Network**
* Switches supporting VLAN capabilities can be configured to *define multiple virtual LANs* over *single physical LAN* infrastructure
42
# LANs: VLANs
Port-Based VLAN
Switch ports are grouped so that single physical switch operates as multiple virtual switches
43
# 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
