Bài giảng Mạng máy tính - Chapter 6: The link layer and LANs - Nguyễn Lê Duy Lai
Computer Networks
Lectured by:
Nguyen Le Duy Lai
(lai@hcmut.edu.vn)
Computer
Networking: A Top
Down Approach
7th Edition, Global Edition
Jim Kurose, Keith Ross
Pearson
April 2016
The Link Layer and LANs 6-1
Chapter 6
The Link Layer
and LANs
Computer
Networking: A Top
Down Approach
7th Edition, Global Edition
Jim Kurose, Keith Ross
Pearson
April 2016
Link Layer and LANs 6-2
Chapter 6: Link layer and LANs
our goals:
▪ understand principles behind link layer services:
• error detection, correction
• sharing a broadcast channel: multiple access
• link layer addressing
• local area networks: Ethernet, VLANs
▪ instantiation, implementation of various link
layer technologies
Link Layer and LANs 6-3
Link layer, LANs: outline
6.1 introduction, services 6.5 link virtualization:
MPLS
6.6 data center
networking
6.7 a day in the life of a
web request
6.2 error detection,
correction
6.3 multiple access
protocols
6.4 LANs
• addressing, ARP
• Ethernet
• switches
• VLANS
Link Layer and LANs 6-4
Link layer: introduction
terminology:
▪ hosts and routers: nodes
▪ communication channels that
connect adjacent nodes along
communication path: links
• wired links
• wireless links
• LANs
▪ layer-2 packet: frame,
encapsulates datagram
data-link layer has responsibility of
transferring datagram from one node
to physically adjacent node over a link
Link Layer and LANs 6-5
Link layer: context
transportation analogy:
▪ trip from Princeton to Lausanne
• limo: Princeton to JFK
▪ datagram transferred by
different link protocols over
different links:
• plane: JFK to Geneva
• train: Geneva to Lausanne
• e.g., Ethernet on first
link, frame relay on
intermediate links,
▪ tourist = datagram
802.11 on last link
▪ transport segment =
▪ each link protocol provides
communication link
different services
▪ transportation mode = link
• e.g., may or may not
provide reliable data
transfer (rdt) over link
layer protocol
▪ travel agent = routing
algorithm
Link Layer and LANs 6-6
Link layer services
▪ framing, link access:
• encapsulate datagram into frame, adding header, trailer
• channel access if shared medium
• “MAC” addresses used in frame headers to identify
source, destination
▪ different from IP address!
▪ reliable delivery between adjacent nodes
• 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?
Link Layer and LANs 6-7
Link layer services (more)
▪ flow control:
• pacing between adjacent sending and receiving nodes
▪ 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
▪ half-duplex and full-duplex
• with half duplex, nodes at both ends of link can transmit, but not
at same time
Link Layer and LANs 6-8
Where is the link layer implemented?
▪ in each and every host
▪ link layer implemented in
“adapter” (aka network
interface card, NIC) or on a
chip
application
transport
O
S
• Ethernet card, 802.11
cpu
memory
network
link
card; Ethernet chipset
• implements link, physical
host
bus
layer
controller
Physical
(e.g., PCIe)
link
physical
▪ attaches into host’s system
buses
▪ combination of hardware,
software, firmware
transmission
network adapter
card
Link Layer and LANs 6-9
Adapters communicating
datagram
datagram
controller
controller
sending host
frame
receiving host
datagram
▪ sending side:
▪ receiving side
• encapsulates datagram in
• looks for errors, rdt,
frame
flow control, etc.
• adds error checking bits,
• extracts datagram, passes
to upper layer at
rdt, flow control, etc.
receiving side
Link Layer and LANs 6-10
Link layer, LANs: outline
6.1 introduction, services 6.5 link virtualization:
MPLS
6.6 data center
networking
6.7 a day in the life of a
web request
6.2 error detection,
correction
6.3 multiple access
protocols
6.4 LANs
• addressing, ARP
• Ethernet
• switches
• VLANS
Link Layer and LANs 6-11
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
otherwise
Link Layer and LANs 6-12
Parity checking
two-dimensional bit parity:
single bit parity:
▪ detect single bit
errors
▪ detect and correct single bit errors
O
O
* Check out the online interactive exercises for more
Link Layer and LANs 6-13
Internet checksum (review)
goal: detect “errors” (e.g., flipped bits) in transmitted packet
(note: used at transport layer only)
sender:
receiver:
▪ compute checksum of
▪ treat segment contents
as sequence of 16-bit
integers
received segment
▪ check if computed
checksum equals checksum
field value:
▪ checksum: addition (1’s
complement sum) of
segment contents
▪ sender puts checksum
value into UDP checksum
field
• NO - error detected
• YES - no error detected.
But maybe errors
nonetheless?
Link Layer and LANs 6-14
Cyclic redundancy check (CRC)
▪ more powerful error-detection coding
▪ 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 (Ethernet, 802.11 WiFi, ATM)
Link Layer and LANs 6-15
CRC example
want:
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by
G, want remainder R
to satisfy:
D.2r]
R = remainder[
G
* Check out the online interactive exercises for more
examples: http://gaia.cs.umass.edu/kurose_ross/interactive/
Link Layer and LANs 6-16
Link layer, LANs: outline
6.1 introduction, services 6.5 link virtualization:
MPLS
6.6 data center
networking
6.7 a day in the life of a
web request
6.2 error detection,
correction
6.3 multiple access
protocols
6.4 LANs
• addressing, ARP
• Ethernet
• switches
• VLANS
Link Layer and LANs 6-17
Multiple access links, protocols
two types of “links”:
▪ point-to-point
• Point-to-Point Protocol (PPP) for dial-up access
• point-to-point link between Ethernet switch, host
▪ broadcast (shared wire or medium)
• old-fashioned Ethernet
• Upstream Hybrid fiber-coaxial (HFC)
• 802.11 wireless LAN
shared RF
shared RF
(satellite)
shared wire (e.g.,
cabled Ethernet)
humans at a
cocktail party
(e.g., 802.11 WiFi)
(shared air, acoustical)
Link Layer and LANs 6-18
Multiple access protocols
▪ single shared broadcast channel
▪ two or more simultaneous transmissions by nodes:
• interference
• collision if node receives two or more signals at the same
time
multiple access protocol
▪ distributed algorithm that determines how nodes share channel,
i.e., determine when node can transmit
▪ communication about channel sharing must use channel itself!
• no out-of-band channel for coordination
Link Layer and LANs 6-19
An ideal multiple access protocol
given: broadcast channel of rate R bps
desiderata:
1. when one node wants to transmit, it can send at rate R.
2. when M nodes want to transmit, each can send at average
rate R/M
3. fully decentralized:
▪ no special node to coordinate transmissions
▪ no synchronization of clocks, slots
4. simple
Link Layer and LANs 6-20
Tải về để xem bản đầy đủ
98 trang
14760
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 6: The link layer and LANs - Nguyễn Lê Duy Lai", để 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:
- bai_giang_mang_may_tinh_chapter_6_the_link_layer_and_lans_th.pdf
