Data Link  Data Link  Layer Layer

doanha86@gmail.com

LOGO

Đoàn Thị Thu Hà Khoa Công Nghệ Thông Tin Đại Học Nông Nghiệp Hà Nội

Contents

www.thmemgallery.com

1. Introduction and services 1. Introduction and services

2. Error detection and correction

3. Multiple access protocols & LAN

4. Link-layer addressing & ARP

Company Logo

5. Specific link layer technologies

1. Introduction and services 1. Introduction and services www.thmemgallery.com

Company Logo

Introduction  Introduction  www.thmemgallery.com Một số thuật ngữ ọ

 Hosts và routers đ c g i là các nút

ượ (notes) – các Bridges và switches cũng  v yậ

ề  Các kênh truy n thông k t n i các nút

ế ố ẫ ầ ng d n truy n

ườ c g i là các liên k t ( ề ế links)

ề ọ g n k  d c theo đ ọ ượ thông đ  Các liên kết hữu tuyến  Các liên kết vô tuyến  Các mạng cục bộ ơ  Đ n v  d  li u frame, đóng

ọ ị ữ ệ ở ầ gói/ bao b c gam d  li u

Company Logo

t ng 2 là   ữ ệ ề packet  nhi u frame

Introduction  Introduction  www.thmemgallery.com

ề

ệ

ế ữ ệ ừ ộ

ộ

ế

ề

T ng liên k t d  li u có trách nhi m truy n gam  ầ   m t  nút  g n  k   qua  m t  liên  k t

ầ ữ ệ d   li u  t ề truy n thông

Company Logo

Introduction Introduction

www.thmemgallery.com

Frame

M

M

M

data link protocol

MHtHn

Hl

M

Ht HtHn HtHn

Hl

frame

phys. link

Company Logo

network link physical application transport network link physical

Introduction Introduction

ể

ng t

ượ

ữ ệ

ươ ộ

ư ự ậ ừ

nh  s  v n chuy n ế  Thái Bình ra

ự T M t chuy n đi t Côn Đ oả

ừ

ế  TB đ n HN

ế

­Ô tô: Đi t ­Máy bay: HN vào TP.HCM ­Tàu thuỷ: TP.HCM  ra                    Côn Đ oả

= datagram

ạ

www.thmemgallery.com ữ ả Ng  c nh  Gam d  li u đ ở ở c chuyên ch  b i  ở ầ ứ  t ng    các giao th c khác nhau ề LKDL qua các liên k t truy n thông  khác nhau:  VD: Ethernet ở liên kết đầu tiên, frame relay ở các liên kết trung gian, 802.11 ở liên kết cuối cùng

ế

ươ

 M i giao th c

cung

ế

Khách du l chị Đo n v n chuy n ể ậ ề     = Liên k t truy n thông Ph ể   ậ ứ ng th c v n chuy n ứ ầ     = giao th c t ng LKDL Đ i lý du l ch ị ạ   ậ ị ả     = gi

i thu t đ nh tuy n

ứ ở ầ ỗ  t ng LKDL  ụ ị ấ c p các d ch v  khác nhau  VD: Có thể cung cấp các dịch vụ

chuyển dữ liệu tin cậy hoặc không qua liên kết truyền thông

Company Logo

ị ị

ụ ụ

Services – Các d ch v Services – Các d ch v

www.thmemgallery.com

ậ

ề

 Đóng frame và truy c p đ

ng truy n (framing, link access)

ữ ệ

ề

ể

ể

ườ  Đóng gói gam d  li u vào các

ỗ i

frame, thêm thông tin đi u ki n và ki m soát l

(header, trailer)

ậ

ề

ề

ắ

ậ

ng truy n (đ

ầ ng truy n dùng chung c n có quy t c truy nh p)

ị

ỉ ậ

ử ụ

ượ

ồ

 Truy nh p đ ườ ườ  Đ a ch  v t lý (physical addr) đ

c s  d ng đ  đ nh danh ngu n và đích.

ề

ữ ệ

ủ ầ

ạ

ả

ườ

ề

ấ ượ

ể ị  Truy n d  li u tin c y (reliable delivery): rdt. ậ  Đ m b o các gói tin c a t ng m ng không b  l ị ỗ ả i.  Tu  thu c ch t l

ng truy n.

ng đ

ượ

ế

ệ ở

ự

ế

ỷ ệ ỗ

ấ

c th c hi n

các liên k t có t

l

l

i bít th p( cáp quang,…)

ượ

ấ ở

ườ

ề

ế

ỷ ệ ỗ

ỳ ộ  Hi m khi đ  Đ c cung c p

các đ

ng truy n vô tuy n vì t

l

l

i cao

Company Logo

Services Services

www.thmemgallery.com  Flow control (đi u khi n l u l

ề ng!!!)

 Error detection – Phát hi n l

ể ư ượ  Đảm bảo lưu lượng truyền hợp lý, nút nhận không bị quá tải, điều chỉnh tốc độ giữa các nút gửi và nhận ệ ỗ i  Lỗi có thể phát sinh do nhiễu, sự suy giảm tín hiệu …  Nút nhận phát hiện lỗi, bỏ qua hoặc yêu cầu nút gửi

gửi lại.

 Error correction ­ S a l

ử ỗ i  Nút nhận xác định bit bị lỗi và sửa các bit lỗi mà

không cần yêu cầu nút gửi phải gửi lại.

 Half­duplex and Full­duplex

Company Logo

 Half-duplex: các nút không thể truyền nhận đồng thời.  Full-duplex: các nút có thể truyền nhận đồng thời.

2. Error detection and correction

www.thmemgallery.com

ể

ệ ỗ

ể ả

ử

Trong quá trình truyền dữ liệu có thể xảy ra lỗi  Đ  phát hi n l i có th  x y ra trong quá  trình truy n:ề  Bên g i thêm vào các gói tin m t s   ộ ố

thông tin

ự

ậ

 Bên nh n d a vào các thông tin trên đ   ể

ể

ki m tra     D = Data

ụ

ể

ớ

ỗ i.

ả

ớ

ng bit EDC càng l n thì kh  năng

EDC= Error Detection and  Correction bits  Bits thêm vào v i m c đích ki m soát l  S  l ố ượ ể

ỗ

ố

ki m soát l

i càng t

t.

Company Logo

2. Error detection and correction

www.thmemgallery.com

ậ

ỹ

ỗ

ổ ế

Các k  thu t dò tìm l

i ph  bi n

Kiểm tra tính chẵn lẻ (Parity bit checking)

Kiểm tra tổng (Checksum)

Kiểm dư vòng (Cyclic Redundancy Check)

ả

Error detection: không ph i lúc nào cũng phát

ệ hi n đ

ượ ỗ c l

i!

Company Logo

ẵ ẻ

ể

Ki m tra tính ch n l

(Parity checking)

www.thmemgallery.com

ằ ẵ ẻ ).

ẵ  Parity: cân b ng!!! (ch n l  Parity ch n (even parity)

ố ổ ẵ

ủ  T ng s  các bit 1 là ch n.  Vd: parity c a 1011 1101 là 0

ẻ  Parity l

ẻ ổ ố .

Company Logo

ủ (odd parity):  T ng s  các bit 1 là l  Vd: parity c a 1101 0101 là 1.

Parity checking

www.thmemgallery.com

0

0

Company Logo

Two Dimensional Bit Parity: Detect and correct single bit errors Single Bit Parity: Detect single bit errors

ổ

ể

Ki m tra t ng (Checksum)

www.thmemgallery.com Xem slide 21­22 Chapter 3

Company Logo

Cyclic Redundancy Check

www.thmemgallery.com

ể

ọ

Dùng các hàm toán h c đ  xét d  li u ữ ệ

ơ ấ

Tính toán ph c t p h n r t nhi u ề ứ ạ

ể ử

ượ

ề ỗ ơ

Có th  x  lý đ

c nhi u l

i h n

Company Logo

Cyclic Redundancy Check

ượ ư ộ ố c xem nh  m t s  nh  phân: D

www.thmemgallery.com  D  li u đ ữ ệ  Ch n m t chu i  ộ ọ  Tìm m t chu i  ộ

ị ỗ ỗ r + 1 bit, G (chu i sinh­ Generator)

Company Logo

ộ ố ế ị ộ ỗ R đ  dài thành m t s  nh  phân chia h t cho r bit, sao cho ghép c a ủ D và R  G( chia modunlo 2)

Cyclic Redundancy Check

www.thmemgallery.com Cách tìm R

Company Logo

3. Multiple Access

ạ

www.thmemgallery.com Hai lo i “links”:  point­to­point

ế ố ạ  PPP (dial­up access: k t n i Internet t i nhà qua

modem)

 point­to­point link gi a Ethernet switch và host

ữ  broadcast (chia s : shared wire or medium)

Company Logo

ẻ  Radio; Bus LAN;  802.11 wireless LAN

MAP: Multiple Access Protocols

www.thmemgallery.com

ộ ườ

ề

ạ

ng truy n.

ữ ệ

ố

ề

ề

ạ

 Các nút m ng dùng chung m t đ  Có lúc nhi u nút m ng cùng mu n truy n d  li u.

 Xung đ t (collision). ộ

ề

ộ

ỉ

 Ch  có m t nút truy n thành công!!!

ắ Multiple Access Protocol (MAP):Các quy t c quy

ị ệ ử ụ ườ ữ ề ng truy n chung gi a các

Company Logo

đ nh vi c s  d ng đ nút m ng.ạ

ứ

ậ

ưở

Giao th c đa truy c p lí t

ng

www.thmemgallery.com

ề ộ ố ườ

ố ộ ố ộ ề

ộ ố ố ề

ề ể ậ

ệ ể ề ầ ặ ộ ự Đ ng truy n có t c đ  (rate) = R  Khi m t nút mu n truy n, t c đ  là R.  Khi M nút mu n truy n, t c đ  TB là R/M.  Đi u khi n truy nh p phân tán:  Không c n m t nút đ c bi ể t đ  đi u khi n (các nút t

ề ể đi u khi n).

ệ ầ ồ ộ  Không c n các tín hi u đ ng b

Company Logo

ơ ả  Đ n gi n.

MAP: taxonomy (phân lo i)ạ www.thmemgallery.com  Channel partitioning – Chia kênh

 Kênh truyền được chia thành các “phần” nhỏ (theo Thời gian - TDMA, Tần số - FDMA, MÃ - CDMA).  Chia từng phần đó cho các nút mạng  không xung

đột (collision).

ậ ẫ  Random access ­ truy nh p ng u nhiên

 Kênh không được chia, cho phép đồng thời truy

nhập, chấp nhận là có xung đột

 Cần khả năng phát hiện, xử lý xung đột

 Taking turns ­ truy nh p l n l

Company Logo

ậ ầ ượ t  Các nút phối hợp chặt chẽ trong việc sử dụng đường truyền  không xung đột: Token Ring, Token Bus…

TDMA: time division multiple access

www.thmemgallery.com

ậ ườ t truy c p đ ề ng truy n trong

 Các nút đ ả ượ ầ ượ c l n l ờ ị kho ng th i gian xác đ nh (time slot).

ố ề ả  Không ph i nút nào cũng mu n truy n: unused slot

Company Logo

(idle slot).  Vd: 6 slots, 3 idle do nút 2,5,6 không có nhu c u.ầ

FDMA: frequency division multiple access

www.thmemgallery.com

ổ ủ ả ầ ượ ề ề c chia thành nhi u d i t n.

ỗ ả ầ ộ

ả ầ ư ậ ề ầ  Ph  c a kênh truy n đ  M i d i t n dành riêng cho m t nút.  Nh  v y, nút không có nhu c u truy n thì d i t n dành

Company Logo

ị cho nó b  lãng phí (unused, idle).

CDMA (Code Division Multiple Access)

www.thmemgallery.com

ượ ở ấ ị c xác đ nh b i mã duy nh t (code).

ấ ả ử ụ ư ố ầ ạ  M i nút đ ỗ  T t c  các nút s  d ng chung t n s  nh ng l

ể i có mã  ả ữ i mã d

riêng (CQ ­ chipping sequence) đ  mã hoá và gi li u.ệ

 encoded signal = (data) X (CQ)

 decoding: tích trong của encoded signal và CQ.

Company Logo

 Sử dụng chủ yếu trong mạng wireless (cellular, satellite…).

CDMA example:

www.thmemgallery.com

Company Logo

CDMA example: two­sender interference

www.thmemgallery.com

sender 1

sender 2

Company Logo

Random Access Protocols

www.thmemgallery.com

ố ề  Khi nút mu n truy n:

 truy nhập đường truyền và truyền với tốc độ R

 không có chế độ ưu tiên cho nút nào cả.

ề  N u nhi u nút cùng truy n ề  xung đ t.ộ

ế  cần có cơ chế phát hiện xung đột (collision detection).

 khôi phục khi có xung đột (recovery): chờ một lúc rồi

ứ truyền lại…  M t s  giao th c:

ộ ố  slotted ALOHA, ALOHA.

Company Logo

 CSMA, CSMA/CD.

Slotted ALOHA

www.thmemgallery.com

ầ ả ờ ờ  Chia thành các kho ng th i gian (time slot) = th i gian c n đ   ể

ề ộ truy n m t frame.

ắ ầ ề ừ ờ ể ắ ầ th i đi m b t đ u slot.

ẽ ắ ầ ể ờ i th i đi m b t đ u slot

 Nút luôn b t đ u truy n t  N u xung đ t, s  truy n l ộ ớ ướ ấ ế ế ti p theo v i xác su t p ch n tr ạ ề ạ i frame t ọ c.

At best: channel use for useful  transmissions 37% of time!

Success (S), Collision (C), Empty (E) slots

Company Logo

VD

CSMA (Carrier Sense Multiple Access)

www.thmemgallery.com

ắ ướ ề  Carrier Sense:   L ng nghe tr

ề ỗ ế ề

ỳ ơ ứ ế ề c khi truy n.  N u kênh truy n r i thì truy n toàn b  frame. ộ  N u kênh truy n b n, tu  c   ng bi n: ậ

ậ ứ ấ ớ ớ i ngay l p t c v i xác su t p cho t i khi kênh ế  Th  l

ử ạ ề ỗ truy n r i.

Company Logo

ử ạ ẫ ả ộ  Th  l ờ i sau m t kho ng th i gian ng u nhiên.

CSMA collisions

www.thmemgallery.com

 Space:

ữ  Kho ng cách gi a các nút.

ờ ả  Time: th i gian.

 Xung đột vẫn có thể xảy ra nếu trong khoảng thời gian t1-t0 tín hiệu chưa lan truyền được từ B tới D.

 Lãng phí!, cần cơ chế phát

Company Logo

hiện xung đột.

CSMA/CD (Collision Detection)

www.thmemgallery.com CSMA/CD:

 Nghe trước khi truyền.  Dò xung đột trong một khoảng thời gian ngắn

(đủ lớn).

 Nếu phát hiện xung đột thì dừng truyền để

ộ

ệ

tránh lãng phí. Phát hi n xung đ t:

 wired LAN: đo hiệu điện thế.  …

Company Logo

CSMA/CD: example

www.thmemgallery.com

Company Logo

ươ

So sách hai ph

ng pháp

www.thmemgallery.com Channel partitioning MAP:

 Hiệu quả khi nhiều nút cùng sử dụng  Ngược lại, gây lãng phí khi chỉ có vài nút cần

truyền tin.

Random Access MAP:

 Hiệu quả khi ít nút sử dụng: một nút có thể

toàn quyền sử dụng đường truyền với tốc độ cao nhất.

 Nhiều nút cùng sử dụng: xung đột.

Taking turns:

 Tìm kiếm giải pháp tốt cho cả hai tình huống.

Company Logo

“Taking Turns” MAP: Polling

ệ ể

t “thông báo” cho các nút khác bi

ề ố ượ

www.thmemgallery.com ụ ề Có m t nút đi u khi n (master) có nhi m v : ế ế t đ n  ộ ố i đa m t s

c phép truy n t

ộ  l n l ầ ượ ượ l ượ l ề t truy n và đ ng frame nào đó.

ế ộ  khi m t nút k t thúc truy n, master thông báo cho  ề

ấ ờ

ộ ố ả ạ ự ố ừ ặ nút khác.  Không xung đ t.ộ  V n đ : ề ấ  m t th i gian thông báo: t c đ  trung bình < R.  khi master g p s  c  thì c  m ng ng ng ho t  ạ

Company Logo

đ ng!ộ

“Taking Turns” MAP: Token passing

www.thmemgallery.com

Company Logo

LAN

www.thmemgallery.com  MAP đ

ộ c s  d ng r ng rãi:

ượ ử ụ  satellite, wireless…  LAN (Local Area Network).

 LAN:

 Mạng nội bộ, có phạm vi hẹp (toàn nhà, trường

ĐH…)

 Vd: LAN kết nối Internet • chia sẻ đường truyền.

 Các lo i LAN: ạ

 Ethernet: phổ biến, sử dụng Random Access MAP.  FDDI (Fiber Distributed Data Interface): Token-

passing.

Company Logo

 …

Link layer address

www.thmemgallery.com

ượ ồ c đóng trong các gói tin (ngu n, đích).

ố ớ ầ ế

ượ

32­bit IP address:   network­layer address  IP đ LAN (or MAC or physical) address:   48 bit (6 bytes) MAC address (đ i v i h u h t LANs)  đ

c ghi trong adapter ROM

*MAC: Media Access Control (Link layer = MAC + LLC

Company Logo

(Logical Link Control)

LAN Addresses and ARP

www.thmemgallery.com

1A­2F­BB­76­09­AD

Broadcast address = FF­FF­FF­FF­FF­FF

= adapter

LAN (wired or wireless)

71­65­F7­2B­08­53

58­23­D7­FA­20­B0

0C­C4­11­6F­E3­98

Company Logo

ộ ị ỉ ậ ấ ươ ỗ ự ư ố M i adapter có m t đ a ch  v t lý duy nh t, t ng t nh  s  CMTND.

MAC address (cont)

ị ổ ở c phân b  b i IEEE.

ượ ả ả ị ỉ ớ

www.thmemgallery.com  Đ a ch  v t lý đ ỉ ậ  Nhà s n xu t ph i đăng ký d i đ a ch  v i IEEE. ả  Khi di chuy n t ị ổ

ỉ

ạ  m ng này sang m ng khác: đ a ch  IP  ị ấ ể ừ ạ ư ỉ ậ ổ thay đ i nh ng đ a ch  v t lý không thay đ i.

 So sánh:

ố

ị ị

 đ a ch  v t lý: s  CMTND.  đ a ch  IP: đ a ch  hòm th . ư ị ố ỉ ử ớ ỉ ậ ầ ị ỉ ậ ỉ  Các frame mu n g i t ứ i đích thì c n ch a đ a ch  v t lý

Company Logo

ủ c a nút đích.

When packet sent from A to B

223.1.1.1

A

ử ứ

ị

ẽ i B, A s :  Tra c u đ a ch  m ng c a B,  ủ ớ

ệ

223.1.2.1

223.1.1.2

ạ ớ

ử

www.thmemgallery.com ớ A g i packet t ỉ ạ phát hi n ra B cùng m ng v i A i B thông

 link layer g i packet t

223.1.1.4 223.1.2.9

qua frame.

B

223.1.2.2

223.1.3.27

223.1.1.3

E

223.1.3.2

223.1.3.1

frame source, dest address

packet source, dest address

IP payload

A’s IP addr

B’s IP addr

B’s MAC addr

A’s MAC addr

datagram

frame

Company Logo

ARP: Address Resolution Protocol

www.thmemgallery.com

ỗ

 M i nút m ng (Host,  ạ ề ARP

Router) đ u có   table

237.196.7.78

ế ị ế ể ???: Làm th  nào đ   ủ bi bi ế ỉ ậ t đ a ch  v t lý c a B khi  ủ t IP c a B? ừ

ứ ả

ấ ạ

1A­2F­BB­76­09­AD

 ARP Table: cho phép t IP tra c u ra MAC addr C u t o b n ghi:

< IP address; MAC address;

237.196.7.23

237.196.7.14

LAN

71­65­F7­2B­08­53

TTL>  TTL (Time To Live): thời gian tồn tại của bản ghi tới khi bị xoá.

58­23­D7­FA­20­B0

0C­C4­11­6F­E3­98

237.196.7.88

Company Logo

ư

ế

ợ

ng h p ch a bi

t MAC addr

ế

ố

ườ Tr ủ c a nút www.thmemgallery.com N u A mu n bi

ủ t MAC addr c a B (không có

ế trong ARP table)  A đã biết IP của B (ipb).  A gửi ARP query packet tới tất cả các nút

(broadcast), trong đó có chứa IP của B (ipb) hỏi xem nút nào có địa chỉ IP là ipb.

 Tất cả các nút đều nhận được và kiểm tra

xem ipb có trùng với IP của mình không, nếu trùng thì trả lời (nút B).

Company Logo

ợ

ở

ạ

ng h p hai nút

hai m ng khác

ử ố ớ

ườ Tr nhau www.thmemgallery.com  A (111.111.111.111) mu n g i tin t

i B

(222.222.222.222)

ủ ử ỏ ế  A không bi

ả ờ LAN1  không có nút nào tr  l ế t MAC addr c a B, n u g i ARP pkt h i  i.

A

R

Company Logo

B

 A creates IP packet with source A, destination B   A uses ARP to get R’s physical layer address for 111.111.111.110  A creates frame with R's physical address as dest, frame contains A­

www.thmemgallery.com to­B IP datagram

 A’s data link layer sends frame   R’s data link layer receives frame   R removes IP datagram from frame, sees its destined to B  R uses ARP to get B’s physical layer address   R creates frame containing A­to­B IP datagram sends to B

A

R

Company Logo

B

www.themegallery.com

LOGO