Bài giảng Mạng máy tính - Chapter 6: The link layer and LANs

Computer Networks

Lectured by:

Nguyen Le Duy Lai

([email protected])

Computer

Networking: A Top

Down Approach

7^thEdition, 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

7^thEdition, 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

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

* Check out the online interactive exercises for more

examples: h ttp://gaia.cs.umass.edu/kurose_ross/interactive/

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^.2^rXOR R = nG

equivalently:

D^.2^r= nG XOR R

equivalently:

if we divide D^.2^rby

G, want remainder R

to satisfy:

D^.2^r_]

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

(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

Bài giảng Mạng máy tính - Chapter 6: The link layer and LANs - Nguyễn Lê Duy Lai