编程代写 IEEE 802.11 LANs  PPP

The Data Link Layer
Our goals: Overview:
 understand principles behind data link layer services:
 link layer services

 error detection, correction
 sharing a broadcast
 multiple access protocols and LANs
channel: multiple access
 link layer addressing, ARP
 link layer addressing
 specific link layer technologies:  Ethernet
 reliable data transfer, flow control: done!
 hubs, switches
 IEEE 802.11 LANs  PPP
 instantiation and implementation of various link layer technologies
 error detection, correction
5: DataLink Layer

Encapsulation in the Link-layer
IP datagram
IP address MAC address
Port number
Transport Layer – TCP

Link Layer: setting the context
Node: Host/Router
Different link-layer protocols on the different links in the path
• Ethernet
• Link-layer WAN protocol
Network Layer: End-to-End job of moving transport-layer segments from source host to destination host
Link-Layer Protocol: Node-to-Node job of moving network-layer datagrams over a single-
link in the path
5: DataLink Layer

Link Layer: setting the context
 two physically connected devices:  host-router, router-router, host-host
 unit of data: frame
Ht M transport
application Hn Ht M network
data link protocol
network link physical
Ht M link physical
phys. link adapter card
5: DataLink Layer

Link Layer Services
Parallels transport layer services
 Framing, link access:
 encapsulate datagram into frame, adding header, trailer
 implement channel access if shared medium,
 ‘physical addresses’ used in frame headers to identify
source, destination
Catch the error on the link where it occurs
• different from IP address!
 Reliable delivery between two physically connected
Mechanisms: Seq.Nos, Timers, ACKs
 we learned how to do this already!
 seldom used on low bit error link (fiber, some twisted pair)  wireless links: high error rates
• Q: why both link-level and end-end reliability?
5: DataLink Layer

Link Layer Services (more)
 Flow Control:
pacing between sender and receivers
 Error Detection: More sophisticated; hardware-implemented errors caused by signal attenuation &
electromagnetic noise.
 Sender sets error-detection bits in the frame; receiver detects presence of errors:
• signals sender for retransmission or drops frame  Error Correction:
 receiver identifies and corrects bit error(s) without resorting to retransmission
5: DataLink Layer

Link Layer: Implementation
Network Interface Card implemented in adapter (NIC)
 e.g., PCMCIA card, Ethernet card
 typically includes: RAM, DSP chips, host bus
interface, and link interface
Ht M transport
application Hn Ht M network
data link protocol
network link physical
Ht M link physical
phys. link adapter card
5: DataLink Layer

Where is the link layer implemented?
 link layer implemented in “network adapter” (aka network interface card NIC) or on a chip
 Ethernet card, 802.11ac card; Ethernet chipset
application transport network link
cpu memory
 implements link, physical layer
 attaches into host’s system buses
controller
(e.g., PCI)
 combination of hardware, software, firmware
link physical
physical transmission
network adapter card
Link Layer 5-8

Error Detection
EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields
11010111001 11001
Error detection is not 100% reliable! – protocol may miss some errors, but rarely
Data and header EDC fields
larger EDC field yields better detection and correction, but incurs larger overhead
5: DataLink Layer

Error Detection
EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields
5: DataLink Layer

Parity Checking
• In an odd parity scheme, the sender includes a parity bit, whose value is chosen such that there is an odd number of 1s.
Single Bit Parity:
• Detect single bit errors
Count of 1 bits = 9 (odd)
• The parity bit is used in parity error checking to find errors that may occur during data transmission.
odd parity bit
• Alternatively, in an even parity scheme, the parity bit is chosen such that there is an even number of 1s.
Odd Parity Scheme – will not be able to detect an odd number of bit errors
Not sufficient, as errors are often clustered together in ‘bursts’.
5: DataLink Layer

Parity Checking
Even Parity Scheme
Two Dimensional Bit Parity: Detect and correct single bit errors
Even parity bit
5: DataLink Layer

a single error in the parity bits themselves is also detectable and correctable
Two-dimensional parity can also detect (but not correct!) any combination of two errors in a packet
5: DataLink Layer
Parity Checking
FEC- Reed- – commonly used in Audio storage & playback devices
Immediate error correction at the receiver (Forward Error Correction) or FEC
Even Parity Scheme
Two Dimensional Bit Parity: Detect and correct single bit errors

Parity Checking
Two Dimensional Bit Parity: Detect and correct single bit errors
• Two-dimensional parity can also detect (but not correct!) any combination of two errors in a packet.
Sender-side
Receiver-side
0110 0 1101 1 0011 0 1000 1
0100 0 0101 1 0011 0 1000 1
Flipped bits
5: DataLink Layer

Check summing: Cyclic Redundancy Check
Based on CRC codes, also known as polynomial codes
 view data bits, D, as a binary number 11010111001 11001
CRC of size r bits
 Calculate CRC based on generator G of size r+1 bits, with leftmost bit=1
 Both sender and receiver knows G.
 receiver divides by G. If non-zero remainder: error is detected!
 can detect all burst errors less than r+1 bits
errors are often clustered together in “bursts.”
 will detect error bursts longer r+1 bits with probability 1 – 0.5r
 CRC standards can detect any odd number of bit errors
5: DataLink Layer

How to compute the CRC?
Mathematical background
5: DataLink Layer

Check summing: Cyclic Redundancy Check
Based on CRC codes, also known as polynomial codes
11010111001
CRC of size r bits
5: DataLink Layer

Check summing: Cyclic Redundancy Check
Based on CRC codes, also known as polynomial codes
1101011100100000
CRC of size r bits
– shift D to the left by r bits.
5: DataLink Layer

Check summing: Cyclic Redundancy Check
Based on CRC codes, also known as polynomial codes
1101011100100000
CRC of size r bits
– shift D to the left by r bits, then append
the CRC bits by XORing it to D. 5: DataLink Layer

Check summing: Cyclic Redundancy Check
Based on CRC codes, also known as polynomial codes
 widely used in practice (ATM, HDCL)
Multiplication by 2r is the same as bitpattern << r D2r XORR G (D*2r XOR R) is perfectly divisible by G; division operation returns no remainder 5: DataLink Layer CRC Example Done in modulo-2 arithmetic without carries in addition or borrows in subtraction (XOR) Addition and subtraction are equal to the XOR operation 1011 0101 1110 5: DataLink Layer R = remainder[ We are interested only in the remainder. 5: DataLink Layer CRC Example Done in modulo-2 arithmetic without carries in addition or borrows in subtraction (XOR) Addition and subtraction are equal to the XOR operation 1011 0101 1110 D.2r XOR R = nG equivalently: D.2r = nG XOR R equivalently: if we divide D.2r by G, want remainder R R = remainder[ CRC Example Given: D=101110, d=6, G=1001, r=3 Compute for the CRC bits. Steps in computing the CRC code with r bits: 1. ShiftDtotheleftr D = 101110000 2. DivideDbyG. 3. Theremainderisthe 5: DataLink Layer R = remainder[ CRC Example Given: D=101110, d=6, G=1001, r=3 Compute for the CRC bits. Steps in computing the CRC code with r bits: 1. ShiftDtotheleftr 2. DivideDbyG. 3. Theremainderisthe 5: DataLink Layer R = remainder[ CRC Example Given: D=101110, d=6, G=1001, r=3 Compute for the CRC bits. Steps in computing the CRC code with r bits: 1. ShiftDtotheleftr 2. DivideDbyG. 3. Theremainderisthe 101 xor 000 101110000 xor 1001 5: DataLink Layer D.2r R = remainder[ G ] CRC Example Given: D=101110, d=6, G=1001, r=3 Output: transmitted=101110011 Steps in computing the CRC code with r bits: 1. ShiftDtotheleftr 2. DivideDbyG. 3. Theremainderisthe r = 3 and so we need 3 bits for the CRC (we count the number of bits from right to left; therefore, including the zero bit). 5: DataLink Layer 28 D.2r R = remainder[ G ] CRC Example Given: D=101110, d=6, G=1001, r=3 Output: transmitted=101110011 Steps in computing the CRC code with r bits: 1. ShiftDtotheleftr 2. DivideDbyG. 3. Theremainderisthe To send => D, CRC code => 101110011
5: DataLink Layer

CRC Example
continuation…
Tosend=> D+CRCcode => 101110011
Given: D=101110, d=6 G=1001, r=3
At the receiver side,
At the receiver side,
To check for any packet corruptions, divide 101110011 by G: 101011
1001 101110011
Remainder = 0
This means the packet arrived correctly.
1001 1001 0
Note: Both sender and receiver knows G.
5: DataLink Layer

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts