›
›

Bài giảng Mạng máy tính - Chapter 5: The data link layer (Part I) - Hồ Phương Đắc

Download
Chapter 5: The Data Link Layer  
Our goals:  
Overview:  
understand principles  
behind data link layer  
services:  
link layer services  
error detection, correction  
multiple access protocols and  
error detection,  
LANs  
correction  
link layer addressing, ARP  
specific link layer technologies:  
Ethernet  
sharing a broadcast  
channel: multiple access  
link layer addressing  
hubs, bridges, switches  
IEEE 802.11 LANs  
PPP  
reliable data transfer,  
flow control: done!  
instantiation and  
implementation of various  
link layer technologies  
5: DataLink Layer  
5a-1  
Link Layer: setting the context  
5: DataLink Layer  
5a-2  
Link Layer: setting the context  
two physically connected devices:  
host-router, router-router, host-host  
unit of data: frame  
M
application  
M
M
M
Ht  
HnHt  
Hl HnHt  
transport  
network  
link  
network  
link  
physical  
data link  
protocol  
M
Hl HnHt  
frame  
physical  
phys. link  
adapter card  
5: DataLink Layer  
5a-3  
Link 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, dest  
• different from IP address!  
Reliable delivery between two physically connected  
devices:  
we learned how to do this already (chapter 3)!  
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  
5a-4  
Link Layer Services (more)  
Flow Control:  
pacing between sender and receivers  
Error Detection:  
errors caused by signal attenuation, noise.  
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  
5a-5  
Link Layer: Implementation  
implemented in “adapter”  
e.g., PCMCIA card, Ethernet card  
typically includes: RAM, DSP chips, host bus  
interface, and link interface  
M
application  
M
M
M
Ht  
HnHt  
Hl HnHt  
transport  
network  
link  
network  
link  
physical  
data link  
protocol  
M
Hl HnHt  
frame  
physical  
phys. link  
adapter card  
5: DataLink Layer  
5a-6  
Error Detection  
EDC= Error Detection and Correction bits (redundancy)  
D = Data protected by error checking, may include header fields  
• Error detection not 100% reliable!  
• protocol may miss some errors, but rarely  
• larger EDC field yields better detection and correction  
5: DataLink Layer  
5a-7  
Parity Checking  
Two Dimensional Bit Parity:  
Single Bit Parity:  
Detect and correct single bit errors  
Detect single bit errors  
0
0
5: DataLink Layer  
5a-8  
Internet checksum  
Goal: detect “errors” (e.g., flipped bits) in transmitted  
segment (note: used at transport layer only)  
Receiver:  
Sender:  
treat segment contents  
as sequence of 16-bit  
integers  
checksum: addition (1’s  
complement sum) of  
segment contents  
sender puts checksum  
value into UDP checksum  
field  
compute checksum of  
received segment  
check if computed checksum  
equals checksum field value:  
NO - error detected  
YES - no error detected.  
But maybe errors  
nonethless? More later ….  
5: DataLink Layer  
5a-9  
Checksumming: Cyclic Redundancy Check  
view data bits, D, as a binary number  
choose r+1 bit pattern (generator), G  
goal: choose r CRC bits, R, such that  
<D,R> exactly divisible by G (modulo 2)  
receiver knows G, divides <D,R> by G. If non-zero remainder:  
error detected!  
can detect all burst errors less than r+1 bits  
widely used in practice (ATM, HDCL)  
5: DataLink Layer  
5a-10  
CRC Example  
Want:  
D.2r XOR R = nG  
equivalently:  
D.2r = nG XOR R  
equivalently:  
if we divide D.2r by  
G, want reminder R  
R = remainder[ D.2r ]  
G
5: DataLink Layer  
5a-11  
Multiple Access Links and Protocols  
Three types of “links”:  
point-to-point (single wire, e.g. PPP, SLIP)  
broadcast (shared wire or medium; e.g, Ethernet,  
Wavelan, etc.)  
switched (e.g., switched Ethernet, ATM etc)  
5: DataLink Layer  
5a-12  
Multiple Access protocols  
single shared communication channel  
two or more simultaneous transmissions by nodes:  
interference  
only one node can send successfully at a time  
multiple access protocol:  
distributed algorithm that determines how stations share  
channel, i.e., determine when station can transmit  
communication about channel sharing must use channel itself!  
what to look for in multiple access protocols:  
• synchronous or asynchronous  
• information needed about other stations  
• robustness (e.g., to channel errors)  
• performance  
5: DataLink Layer  
5a-13  
Multiple Access protocols  
claim: humans use multiple access protocols  
all the time  
class can "guess" multiple access protocols  
multiaccess protocol 1:  
multiaccess protocol 2:  
multiaccess protocol 3:  
multiaccess protocol 4:  
5: DataLink Layer  
5a-14  
MAC Protocols: a taxonomy  
Three broad classes:  
Channel Partitioning  
divide channel into smaller “pieces” (time slots,  
frequency)  
allocate piece to node for exclusive use  
Random Access  
allow collisions  
“recover” from collisions  
“Taking turns”  
tightly coordinate shared access to avoid collisions  
Goal: efficient, fair, simple, decentralized  
5: DataLink Layer  
5a-15  
Channel Partitioning MAC protocols: TDMA  
TDMA: time division multiple access  
access to channel in "rounds"  
each station gets fixed length slot (length = pkt  
trans time) in each round  
unused slots go idle  
example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6  
idle  
5: DataLink Layer  
5a-16  
Channel Partitioning MAC protocols: FDMA  
FDMA: frequency division multiple access  
channel spectrum divided into frequency bands  
each station assigned fixed frequency band  
unused transmission time in frequency bands go idle  
example: 6-station LAN, 1,3,4 have pkt, frequency  
bands 2,5,6 idle  
5: DataLink Layer  
5a-17  
Channel Partitioning (CDMA)  
CDMA (Code Division Multiple Access)  
unique “code” assigned to each user; ie, code set partitioning  
used mostly in wireless broadcast channels (cellular,  
satellite,etc)  
all users share same frequency, but each user has own  
“chipping” sequence (ie, code) to encode data  
encoded signal = (original data) X (chipping sequence)  
decoding: inner-product of encoded signal and chipping  
sequence  
allows multiple users to “coexist” and transmit  
simultaneously with minimal interference (if codes are  
“orthogonal”)  
5: DataLink Layer  
5a-18  
CDMA Encode/Decode  
5: DataLink Layer  
5a-19  
CDMA: two-sender interference  
5: DataLink Layer  
5a-20  
Tải về để xem bản đầy đủ
ppt 32 trang myanh 12020
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng máy tính - Chapter 5: The data link layer (Part I) - Hồ Phương Đắc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pptbai_giang_mang_may_tinh_chapter_5_the_data_link_layer_part_i.ppt