โต๊ะทบทวน รายวิชาทั้งหมด
ITDS231 · บทที่ 3 · Lecture 5.0 – 5.2

Data Link Layer

ชั้นเชื่อมโยงข้อมูล — พื้นฐานและ framing, การตรวจจับ/แก้ไขข้อผิดพลาด (parity, checksum, CRC, Hamming) และ flow control กับ ARQ และ HDLC อ่านเนื้อหา ทบทวน cheat sheet แล้วลองทำแบบฝึกหัด 20 ข้อ

เนื้อหาแยกตามไฟล์สไลด์

Hop-by-hop delivery

Data Link Layer ทำหน้าที่ hop-by-hop delivery — แพ็กเก็ต IP เดียวกันถูก "reframe" (ถอดเฟรมเก่า สร้างเฟรมใหม่) ทุกครั้งที่ผ่าน router แต่ละ hop แม้ว่า application จะมองเห็นเป็นการสื่อสารแบบ end-to-end ก็ตาม

2 ซับเลเยอร์: LLC และ MAC

LLC Logical Link Control

เชื่อมกับ network-layer protocol ชั้นบน

MAC Media Access Control

framing, link addressing, medium access

หน้าที่หลักของ Data Link Layer

หน้าที่ทำโดย / หมายเหตุ
Network-layer interfaceLLC
Framing—
Link addressingMAC
Error detectionFCS / CRC
Error recoveryACK + retransmit optional
Flow controloptional
Medium accessMAC

โครงสร้างเฟรมทั่วไป

  1. Flag
  2. Address
  3. Control
  4. Data
  5. FCS
  6. Flag
เปรียบเหมือนซองจดหมาย: header บอกข้อมูลนำส่ง · FCS ช่วยตรวจว่าเนื้อหาเสียหายระหว่างทางหรือไม่

Framing 3 แบบหลัก

Byte / character-oriented
  • ข้อมูลเป็นตัวอักษร 8-bit (ASCII)
  • ใช้ special delimiter byte เป็นขอบเขตเฟรม
  • ถ้า pattern flag ไปปรากฏในข้อมูลต้องใช้ escape character แก้ปัญหา เรียกว่า byte stuffing
  • ตัวอย่าง: BISYNC, PPP
Bit-oriented
  • ข้อมูลเป็นลำดับบิตล้วนๆ
  • ใช้ flag bit pattern เป็นขอบเขต
  • ป้องกัน pattern ปรากฏซ้ำด้วย bit stuffing
  • ตัวอย่าง: HDLC, Frame Relay — HDLC ใช้ Flag = 0x7E = 01111110
Length / Fixed-size
  • ใช้ length field หรือขนาดคงที่กำหนดขอบเขตแทน
  • ตัวอย่าง: Ethernet
  • padding ของ Ethernet ไม่ใช่ stuffing เพราะแค่เติมให้ครบขนาดขั้นต่ำ ไม่ได้ป้องกัน pattern ชนกับ delimiter

Bit error และแนวทาง Error control

Bit error เกิดจาก: สัญญาณรบกวน · thermal noise · ฮาร์ดแวร์เสีย · ปรากฏการณ์ธรรมชาติ (ฟ้าผ่า) · หรือแม้แต่ EMP

ARQ Automatic Repeat reQuest

ตรวจพบ error แล้วขอส่งซ้ำ

FEC Forward Error Correction

เพิ่ม redundancy ให้ผู้รับแก้ไขเองได้

Redundancy = การเพิ่มบิตพิเศษเพื่อช่วยผู้รับตรวจสอบความถูกต้องของข้อมูล โดยบิตพิเศษเหล่านี้จะถูกทิ้งหลังตรวจสอบเสร็จ

Block coding

ข้อมูล k บิต + redundancy r บิต = codeword n บิต

n = k + r

ผลลัพธ์การตรวจสอบของผู้รับเรียกว่า "syndrome" — ถ้า syndrome = 0 แปลว่าไม่มี error

Parity check และ Two-dimensional parity

  • Parity check: เพิ่ม parity bit ให้จำนวนบิต 1 รวมเป็นเลขคู่ (even parity) หรือคี่ (odd parity)
  • ตรวจจับ single-bit error ได้ทุกกรณี แต่ตรวจจับ burst error ไม่ได้ถ้าจำนวนบิตที่ผิดเป็นเลขคู่
Two-dimensional parity check: ตรวจสอบทั้งแถวและคอลัมน์ ทำให้หาตำแหน่งบิตที่ผิดได้ (ถ้ามี error เดียว) และแก้ไขได้ทันที ไม่ใช่แค่ตรวจจับ

Checksum

  1. แบ่งข้อความเป็นหน่วย m-bit
  2. บวกกันด้วย one's-complement arithmetic สร้างค่า checksum ส่งไปพร้อมข้อมูล
  3. ผู้รับบวกทุกส่วนรวม checksum — ถ้าได้ all-1s (complement = all-0s) แปลว่าไม่มี error

ใช้ใน: IPv4 header checksum, TCP/UDP checksum

CRC (Cyclic Redundancy Check)

  • ทรงพลังที่สุดในบรรดาวิธี redundancy checking
  • ใช้การหารเลขฐานสอง (modulo-2 division, เหมือน XOR) ด้วย divisor ที่ตกลงกันไว้ล่วงหน้า
  • CRC (remainder) ต้องมีขนาดน้อยกว่า divisor อยู่ 1 บิตเสมอ
  • ต่อท้าย dataword แล้วหารด้วย divisor ต้องลงตัวพอดี
  • ใช้กันแพร่หลายในเทคโนโลยีลิงก์เพราะตรวจจับ burst error ได้ดี
จำนวนบิต CRC = จำนวนบิต divisor − 1

Hamming code

  • แก้ไข single-bit error ได้ โดยระบุตำแหน่งบิตที่ผิด
  • วาง redundant bit ไว้ที่ตำแหน่ง 2k (1, 2, 4, 8, ...) ของ codeword
  • แต่ละ redundant bit ตรวจสอบ parity ของกลุ่มบิตที่กำหนดไว้
ตำแหน่งบิตผิด = (r8 r4 r2 r1)₂ → แปลงเป็นเลขฐานสิบ

Interleaving

แก้ปัญหา burst error ที่ทำให้ codeword เดิมเสียทั้งก้อน โดยสลับ (shuffle) บิตจากหลาย codeword ทำให้ burst error กลายเป็น single-bit error กระจายในแต่ละ codeword ซึ่งแก้ด้วย Hamming code ได้

เทคนิค: ให้ burst error โดนแค่ 1 บิตต่อ 1 หน่วย

Flow control

ควบคุมอัตราการส่งของ sender ให้สมดุลกับความสามารถประมวลผลของ receiver

ส่งเร็วเกินไป

receiver อาจ buffer overflow / frame loss

ส่งช้าเกินไป

เสียประสิทธิภาพ

  • ทั้งสองฝั่งใช้ buffer ช่วยพักข้อมูลระหว่างทาง
  • feedback ที่ receiver ส่งกลับ: ACK (ยืนยันรับสำเร็จ) และ NAK / retransmission request (ขอส่งซ้ำ)

Simple Protocol, Stop-and-Wait และ Pipelining

  • Simple Protocol: ไม่มี flow/error control เลย (baseline เปรียบเทียบ)
  • Stop-and-Wait ARQ: sender ส่งทีละ 1 เฟรม รอ ACK ก่อนส่งเฟรมถัดไป ใช้ sequence number แค่ 2 ค่า (0, 1) สลับกันไป ป้องกันเฟรมซ้ำ — เชื่อถือได้ แต่เสียเวลารอมากบนลิงก์ที่มี bandwidth สูง/delay นาน (ไม่มี pipelining)
  • Pipelining: การส่งหลายเฟรมพร้อมกันโดยไม่ต้องรอ ACK ทีละเฟรม ใช้ใน Go-Back-N และ Selective Repeat (ไม่มีใน Stop-and-Wait)

Go-Back-N ARQ vs Selective Repeat ARQ

Go-Back-N
  • sender window มากกว่า 1 (สูงสุด 2m − 1)
  • receiver window = 1 เสมอ — รับเฉพาะเฟรมที่คาดไว้ลำดับถัดไป เฟรมที่มาไม่เรียงลำดับจะถูกทิ้ง
  • ใช้ cumulative ACK (ACK n = ยืนยันทุกเฟรมก่อนหน้า n แล้ว)
  • timeout → retransmit เฟรมเก่าสุดที่ยังไม่ ACK พร้อมเฟรมทั้งหมดหลังจากนั้น
  • receiver ง่าย แต่สิ้นเปลือง bandwidth เมื่อเกิด error บ่อย
Selective Repeat
  • sender และ receiver window มีขนาดมากกว่า 1 เท่ากัน (ต้อง ≤ 2m−1 เพื่อไม่ให้ sequence number กำกวม)
  • receiver รับและ buffer เฟรมที่มาไม่เรียงลำดับได้ (ต่างจาก GBN)
  • เฟรมหาย → retransmit เฉพาะเฟรมนั้น ไม่ใช่ทั้งหมด
  • ประหยัด bandwidth กว่า GBN แต่ receiver ซับซ้อนกว่า

Piggybacking

การส่ง ACK แนบไปกับ data frame ที่เดินทางในทิศตรงข้าม เพื่อเพิ่มประสิทธิภาพในการสื่อสารสองทิศทาง

HDLC (High-Level Data Link Control)

โปรโตคอลมาตรฐานแบบ bit-oriented สำหรับลิงก์ point-to-point / multipoint ใช้ flag-based framing + bit stuffing รองรับทั้งโหมด connectionless และ connection-oriented (NRM, ABM)

ประเภทเฟรมหน้าที่ตัวอย่างรหัส
I-frameขนส่ง user data + piggybacked control info—
S-frameควบคุม flow/error อย่างเดียว เมื่อ piggyback ไม่เหมาะRR, RNR, REJ, SREJ
U-frameจัดการ sessionSABM, DISC, FRMR

Bandwidth-delay product

วัดจำนวนบิตที่ระบบส่งออกไปได้ระหว่างรอ ACK กลับมา

bandwidth-delay product = bandwidth (bps) × round-trip delay (วินาที)

ถ้าค่านี้สูง (ลิงก์ bandwidth สูงหรือ delay นาน) Stop-and-Wait จะใช้ประโยชน์จากลิงก์ได้ต่ำมาก

ตัวอย่างในสไลด์ (ลิงก์เดียวกัน): link utilization Stop-and-Wait เพียง 5% · Go-Back-N ที่ window 15 เฟรม 75%

Cheat sheet

ตาราง สูตร และคำที่มักออกสอบของบทที่ 3 รวมไว้ในหน้าเดียว

01 Framing 3 แบบ

Byte-orientedBit-orientedLength-based
ข้อมูลตัวอักษร 8-bit (ASCII)ลำดับบิตล้วน—
ขอบเขตเฟรมdelimiter byteflag bit patternlength field / ขนาดคงที่
กัน pattern ชนbyte stuffing (escape char)bit stuffingไม่ต้อง (padding ≠ stuffing)
ตัวอย่างBISYNC, PPPHDLC (0x7E), Frame RelayEthernet

02 HDLC 3 ประเภทเฟรม

I
user data + piggybacked control
S
flow/error control อย่างเดียว · RR, RNR, REJ, SREJ
U
จัดการ session · SABM, DISC, FRMR

bit-oriented · Flag 0x7E = 01111110 · โหมด NRM, ABM

03 Parity · Checksum · CRC · Hamming

วิธีหลักการตรวจจับ / แก้ไขใช้ที่ / จุดจำ
Parityparity bit ให้จำนวนบิต 1 เป็นคู่/คี่ตรวจจับsingle-bit ได้ทุกกรณี · burst ผิดเลขคู่ตรวจไม่ได้
2D parityตรวจทั้งแถวและคอลัมน์ตรวจจับ + แก้ไข (error เดียว)หาตำแหน่งบิตที่ผิดได้
Checksumบวก m-bit ด้วย one's complementตรวจจับผลรวมได้ all-1s = ไม่มี error · IPv4, TCP/UDP
CRCmodulo-2 division ด้วย divisorตรวจจับทรงพลังสุด · burst error ดี · ใช้ในลิงก์
Hammingredundant bit ที่ตำแหน่ง 2kแก้ไข single-bitคู่กับ interleaving แก้ burst error

04 สูตร error control

n = k + r CRC bits = divisor bits − 1 ตำแหน่งบิตผิด = (r8 r4 r2 r1)₂
  • syndrome = 0 → ไม่มี error
  • checksum ผู้รับได้ all-1s → ไม่มี error

05 Stop-and-Wait vs Go-Back-N vs Selective Repeat

Stop-and-WaitGo-Back-NSelective Repeat
Sender window1 เฟรม> 1 (สูงสุด 2m − 1)> 1 (≤ 2m−1)
Receiver window—1 เสมอ> 1 เท่ากับ sender
Out-of-order frame—ทิ้งbuffer ไว้
Retransmitเฟรมที่รอ ACKเฟรมเก่าสุดที่ยังไม่ ACK + ทุกเฟรมหลังจากนั้นเฉพาะเฟรมที่หาย
จุดจำseq 0, 1 · ไม่มี pipeliningcumulative ACK · receiver ง่ายประหยัด bandwidth · receiver ซับซ้อน

06 Bandwidth-delay product

bandwidth (bps) × round-trip delay (s)

= จำนวนบิตที่ส่งออกไปได้ระหว่างรอ ACK · ค่าสูง → Stop-and-Wait ใช้ลิงก์ได้ต่ำ

  • Stop-and-Wait → 5%
  • Go-Back-N window 15 → 75%

Piggybacking = แนบ ACK ไปกับ data frame ทิศตรงข้าม

แบบฝึกหัด 20 ข้อ

เลือกคำตอบให้ครบแล้วกด "ตรวจคำตอบ" ด้านล่าง ระบบจะเฉลยพร้อมคำอธิบายทุกข้อ

01การจัดกรอบข้อมูล (framing) ใหม่เกิดขึ้นที่ใดในการส่งข้อมูลแบบ hop-by-hop?

Data Link Layer ทำงานแบบ hop-by-hop: แพ็กเก็ต IP เดียวกันถูก reframe (ถอดเฟรมเก่า สร้างเฟรมใหม่) ทุกครั้งที่ผ่าน router แต่ละ hop แม้ application จะมองเห็นเป็นการสื่อสารแบบ end-to-end

02ซับเลเยอร์ใดของ Data Link Layer ทำหน้าที่ระบุอุปกรณ์บน link ท้องถิ่น (link addressing)?

MAC (Media Access Control) ดูแล framing, link addressing และ medium access · LLC (Logical Link Control) เชื่อมกับ network-layer protocol ชั้นบน

03Framing คืออะไร?

Framing กำหนดขอบเขตของเฟรม ทำได้ 3 แบบหลัก: byte/character-oriented (delimiter byte), bit-oriented (flag bit pattern) และ length/fixed-size (length field หรือขนาดคงที่)

04การป้องกันไม่ให้ pattern ของ flag ปรากฏในข้อมูลจริงของ byte-oriented framing เรียกว่าอะไร?

Byte-oriented framing ใช้ escape character เมื่อ pattern flag ไปปรากฏในข้อมูล เรียกว่า byte stuffing (เช่น BISYNC, PPP) · bit stuffing ใช้กับ bit-oriented · padding ของ Ethernet แค่เติมให้ครบขนาดขั้นต่ำ ไม่ใช่ stuffing

05HDLC ใช้ bit stuffing เพื่ออะไร?

HDLC เป็น bit-oriented ใช้ Flag = 0x7E = 01111110 เป็นขอบเขตเฟรม และใช้ bit stuffing ป้องกันไม่ให้ pattern นี้ปรากฏซ้ำในข้อมูล

06Parity check (even parity) แบบพื้นฐานตรวจจับ error ประเภทใดไม่ได้?

Parity check ตรวจจับ single-bit error ได้ทุกกรณี แต่ตรวจจับ burst error ไม่ได้ถ้าจำนวนบิตที่ผิดเป็นเลขคู่

07Two-dimensional parity checking มีข้อดีเหนือ parity check ธรรมดาอย่างไร?

Two-dimensional parity ตรวจสอบทั้งแถวและคอลัมน์ จึงหาตำแหน่งบิตที่ผิดได้ (ถ้ามี error เดียว) และแก้ไขได้ทันที ไม่ใช่แค่ตรวจจับ

08Checksum ใช้เลขคณิตแบบใดในการคำนวณ?

Checksum แบ่งข้อความเป็นหน่วย m-bit แล้วบวกกันด้วย one's-complement arithmetic · ผู้รับบวกทุกส่วนรวม checksum ถ้าได้ all-1s (complement = all-0s) แปลว่าไม่มี error

09CRC ใช้หลักการใดในการสร้าง redundancy bits?

CRC ใช้การหารเลขฐานสอง (modulo-2 division เหมือน XOR) ด้วย divisor ที่ตกลงกันไว้ล่วงหน้า · การบวกแบบ one's complement คือวิธีของ checksum

10ขนาดของ CRC (redundancy bits) สัมพันธ์กับ divisor อย่างไร?

CRC (remainder) มีขนาดน้อยกว่า divisor อยู่ 1 บิตเสมอ ต่อท้าย dataword แล้วหารด้วย divisor ต้องลงตัวพอดี

11Hamming code วาง redundant bit ไว้ที่ตำแหน่งใดของ codeword?

Hamming code วาง redundant bit ที่ตำแหน่ง 2k (1, 2, 4, 8, ...) แต่ละบิตตรวจ parity ของกลุ่มบิตที่กำหนด ตำแหน่งบิตผิดคำนวณจาก (r8 r4 r2 r1) แปลงเป็นเลขฐานสิบ

12Interleaving ช่วยแก้ปัญหา burst error ได้อย่างไร?

Interleaving สลับบิตจากหลาย codeword ให้ burst error โดนแค่ 1 บิตต่อ 1 หน่วย กลายเป็น single-bit error ที่แก้ด้วย Hamming code ได้

13วัตถุประสงค์หลักของ Flow Control คืออะไร?

Flow control ควบคุมอัตราการส่งของ sender ให้สมดุลกับความสามารถของ receiver — ส่งเร็วเกินไป receiver อาจ buffer overflow/frame loss ส่งช้าเกินไปก็เสียประสิทธิภาพ

14ใน Stop-and-Wait ARQ sequence number ที่ใช้มีกี่ค่า?

Stop-and-Wait ส่งทีละ 1 เฟรม รอ ACK ก่อนส่งเฟรมถัดไป ใช้ sequence number แค่ 2 ค่า (0, 1) สลับกันเพื่อป้องกันเฟรมซ้ำ

15Pipelining ในบริบทของ ARQ หมายถึงอะไร?

Pipelining = ส่งหลายเฟรมพร้อมกันโดยไม่ต้องรอ ACK ทีละเฟรม ใช้ใน Go-Back-N และ Selective Repeat (ไม่มีใน Stop-and-Wait)

16ใน Go-Back-N ARQ ขนาด receiver window เท่ากับเท่าใดเสมอ?

Go-Back-N: sender window มากกว่า 1 (สูงสุด 2m − 1) แต่ receiver window = 1 เสมอ รับเฉพาะเฟรมที่คาดไว้ลำดับถัดไป เฟรมที่มาไม่เรียงลำดับถูกทิ้ง · window ขนาดเท่ากันทั้งสองฝั่งคือ Selective Repeat

17ข้อแตกต่างหลักระหว่าง Go-Back-N และ Selective Repeat คือข้อใด?

SR: receiver buffer เฟรมที่มาไม่เรียงลำดับได้ และ retransmit เฉพาะเฟรมที่หาย · GBN: ทิ้งเฟรมที่ไม่เรียงลำดับ เมื่อ timeout ส่งเฟรมเก่าสุดที่ยังไม่ ACK พร้อมทุกเฟรมหลังจากนั้น

18Piggybacking คืออะไร?

Piggybacking = ส่ง ACK แนบไปกับ data frame ที่เดินทางในทิศตรงข้าม เพื่อเพิ่มประสิทธิภาพในการสื่อสารสองทิศทาง

19HDLC I-frame ใช้สำหรับอะไร?

I-frame ขนส่ง user data + piggybacked control info · S-frame ควบคุม flow/error อย่างเดียว (RR/RNR/REJ/SREJ) · U-frame จัดการ session (SABM, DISC, FRMR)

20Bandwidth-delay product ใช้วัดอะไร?

Bandwidth-delay product = bandwidth (bps) × round-trip delay (วินาที) คือจำนวนบิตที่ส่งออกไปได้ระหว่างรอ ACK — ค่าสูงทำให้ Stop-and-Wait ใช้ประโยชน์จากลิงก์ได้ต่ำมาก

0 / 20 ข้อ