บทที่ 11

การควบคุมความผิดพลาด (ARQ)

ถ้าเฟรมหาย หรือ ACK หาย ระบบจะรู้ได้ยังไง และจะส่งซ้ำแบบไหน — Stop-and-Wait, Selective Repeat, Go-Back-N คือคำตอบสามแบบที่ต่างกันที่ "ส่งซ้ำกี่เฟรม" กับ "ใช้บัฟเฟอร์เท่าไร"

อ่าน ~14 นาที ออกสอบเกือบทุกปี เชื่อมกับ ข้อสอบ Q8, Q9

ข้อสอบออกแบบไหน

ปีที่แล้วออก 2 ข้อจากบทนี้ — (1) วาด timing diagram ของ stop-and-wait เมื่อ Timeout สั้นกว่า RTT และ (2) วาด Selective Repeat 6 เฟรม โดยเฟรม 2 หาย และ ACK ของเฟรม 4 หาย ทั้งสองข้อ "วาดถูก = ได้คะแนน" ไม่ต้องคำนวณอะไรเลย จึงเป็นข้อที่คุ้มที่สุดในข้อสอบ

11.0ARQ คืออะไร

Error control คือกลไกที่ให้ "ภาครับ" แจ้งกลับไปว่าข้อมูลที่ส่งมามีปัญหาอะไรหรือไม่ ปัญหาที่เกิดได้มี 3 แบบ — ข้อมูลผิดเพี้ยนระหว่างทาง, ลำดับของข้อมูลผิด, และเฟรมสูญหายไปทั้งเฟรม

Error control ทำงานคู่กับ error detection (บทที่ 12 — parity, checksum, CRC) เสมอ กล่าวคือ error detection บอกว่า "เฟรมนี้เสีย" ส่วน error control บอกว่า "แล้วจะทำยังไงต่อ"

ถ้าเฟรมที่ได้รับไม่มีความผิดพลาด → ภาครับส่ง ACK (Acknowledgment) กลับไป
บางอัลกอริทึมใช้ NAK (negative acknowledgment) เพื่อบอกว่าเฟรมนั้นเสีย

วิธีการทั้งหมดนี้เรียกรวมกันว่า Automatic Repeat reQuest (ARQ) มีมาตรฐาน 3 แบบ:

แบบ	Window size (W)	เมื่อเฟรมหาย ส่งซ้ำอะไร	ภาครับเก็บ out-of-order ไหม
Stop-and-Wait	W = 1	เฟรมเดียวที่ค้างอยู่	ไม่ต้องเก็บ
Selective Repeat	W > 1	เฉพาะเฟรมที่หาย	เก็บ (ต้องมีบัฟเฟอร์ N)
Go-Back-N	W > 1	ตั้งแต่เฟรมที่หาย ไปจนหมด window	ทิ้งทั้งหมด

จำง่าย ๆ

ชื่อมันบอกอยู่แล้ว — Selective = เลือกส่งเฉพาะตัวที่หาย, Go-Back-N = ถอยกลับไป N เฟรมแล้วส่งใหม่ยกชุด, Stop-and-Wait = ส่งแล้วหยุดรอ

ในบทนี้จะกล่าวถึงเฉพาะการใช้ ACK เพราะเป็นวิธีที่ได้รับการยอมรับมากกว่า และถูกใช้จริงในเลเยอร์ถัดไปคือ TCP

11.1Stop-and-wait ARQ

หลักการ:

ภาคส่งสำเนาข้อมูลเก็บไว้ก่อน แล้วจึงส่งเฟรมออกไป โดยเริ่มที่หมายเลข 0
ภาคส่งหยุดรอ ACK0
ถ้าได้รับ ACK0 ก่อน timeout → ลบสำเนาทิ้ง แล้วส่งเฟรมถัดไปเป็นหมายเลข 1
ถ้าไม่ได้รับ ACK0 ก่อนหมดเวลา → ส่งเฟรมหมายเลข 0 ออกไปใหม่

หมายเลขเฟรมจะสลับ 0 → 1 → 0 → 1 ไปเรื่อย ๆ (ใช้แค่ 1 บิตก็พอ) และทุกครั้งที่ส่งเฟรมออกไป จะมีการตั้ง Timeout กำกับไว้เสมอ

ตำราวาดเรื่องเดียวกันนี้เป็นไดอะแกรมเวลาแนวนอน — รางบนคือ ด้านส่ง รางล่างคือ ด้านรับ เวลาไหลจากซ้ายไปขวา (ดูลูกศร "เวลา" ที่มุมขวา) กล่องบนรางคือช่วงที่กำลัง "ยิงบิตขึ้นสาย" ส่วนลูกศรทแยงคือเฟรมที่กำลังเดินทาง

สิ่งที่ต้องดูให้ออกในรูปนี้คือเส้นกำกับสองเส้นเหนือรางด้านส่ง — "เริ่มจับเวลา" ตอนที่เฟรมออกจากด้านส่ง และ "สิ้นสุดจับเวลา" ตอนที่ ACK กลับมาถึง ช่วงระหว่างสองเส้นนี้คือช่วงที่นาฬิกา timeout กำลังเดินอยู่ ถ้า ACK ไม่มาก่อนที่ช่วงนี้จะหมด ก็คือเกิด Timeout — ตำราย้ำว่า "การส่งเฟรมออกไปทุกครั้ง จะมีการกำหนดเวลาที่เฟรมนั้นสามารถอยู่ในระบบได้ หากเวลาสิ้นสุดลง ไม่ว่าเกิดจากสาเหตุใดเราเรียกว่า Timeout"

ไดอะแกรมเวลาแนวนอน 2 ราง ด้านส่งอยู่บน ด้านรับอยู่ล่าง บนรางด้านส่งมีกล่อง F(N), F(N+1), F(N+2) เรียงกัน มีลูกศรทแยงลง F(N) ไปยังด้านรับ และลูกศรทแยงขึ้น ACK(N) กลับมา เหนือรางด้านส่งมีเส้นกำกับ เริ่มจับเวลา และ สิ้นสุดจับเวลา คู่หนึ่งต่อหนึ่งเฟรม มุมขวาเป็นลูกศรบอกทิศทางของเวลา — รูปที่ 11.1 จากตำรา — การส่งข้อมูลแบบ Stop-and-wait (จุดที่ต้องสังเกต: ระหว่างเฟรม F(N) กับ F(N+1) บนรางด้านส่งมี**ช่องว่างยาว ๆ** นั่นคือเวลาที่ช่องสัญญาณถูกปล่อยทิ้งไว้เฉย ๆ เพราะต้องหยุดรอ ACK — คือที่มาของข้อเสียเรื่องประสิทธิภาพ)

เวลาทั้งหมดที่ใช้ส่ง 1 เฟรม

T = T_p + 2T_prop + 2T_proc + T_a สมการ 11.1

สัญลักษณ์	ความหมาย	คิดยังไง
`T`	เวลาทั้งหมดที่ใช้ส่งข้อมูล 1 รอบ	รวมทุกอย่างข้างล่าง
`T_p`	Transmission delay ของเฟรมข้อมูล	ขนาดเฟรม ÷ bit rate
`T_prop`	Propagation delay (คูณ 2 = ไป+กลับ)	ระยะทาง ÷ ความเร็วสัญญาณ
`T_proc`	Processing delay (คูณ 2 = ประมวลผลเฟรม + ประมวลผล ACK)	โจทย์กำหนดให้
`T_a`	Transmission delay ของ ACK	ขนาด ACK ÷ bit rate

ที่มาของสูตรนี้ดูง่ายที่สุดจากไดอะแกรมเวลา — เดินตามเฟรมหนึ่งเฟรมตั้งแต่บิตแรกออกจากผู้ส่ง จนกระทั่ง ACK ของมันถูกประมวลผลเสร็จที่ผู้ส่ง แล้วนับว่าผ่านก้อนเวลาอะไรบ้าง

ตำราวาดก้อนเวลาทั้ง 6 ก้อนนี้ไว้ใต้รางด้านรับ พร้อมเส้นประโยงขึ้นไปหาจุดที่มันเกิดจริง:

ไดอะแกรมเวลา Stop-and-wait แบบเดียวกับรูป 11.1 แต่ใต้รางด้านรับมีวงเล็บกำกับก้อนเวลา 6 ก้อน พร้อมเส้นประโยงขึ้นไป ได้แก่ เวลาหน่วงการส่งเฟรม การแพร่กระจายเฟรม การประมวลผลเฟรม การส่ง ACK การแพร่กระจายของ ACK และการประมวลผล ACK — รูปที่ 11.2 จากตำรา — เวลาที่ใช้ในการส่งข้อมูลแบบ Stop and Wait (ชื่อก้อนเวลาในรูปเทียบกับสูตร: เวลาหน่วงการส่งเฟรม = T_p · การแพร่กระจายเฟรม/ของ ACK = T_prop อย่างละครั้ง · การประมวลผลเฟรม/ACK = T_proc อย่างละครั้ง · การส่ง ACK = T_a)

ข้อสังเกตเล็ก ๆ ตอนเทียบรูปกับ animation: ตำราลากวงเล็บ T_prop จากจังหวะที่บิตแรกออกจากผู้ส่งถึงจังหวะที่บิตแรกถึงผู้รับ ส่วน animation ข้างบนลากจากบิตสุดท้าย — ได้ค่าเท่ากันเพราะเป็นเวลาเดินทางของสัญญาณอันเดียวกัน แค่เลือกจุดวัดคนละจุด ผลรวม T จึงเท่ากันทั้งสองแบบ

จุดที่คนพลาดบ่อย

ทำไม T_prop และ T_proc คูณ 2 แต่ T_p กับ T_a ไม่คูณ? เพราะ การเดินทาง เกิดขึ้นสองรอบ (ขาไป-ขากลับ) และ การประมวลผล ก็เกิดสองครั้ง (ที่ปลายทางกับที่ต้นทาง) แต่ การยิงบิตขึ้นสาย เกิดครั้งเดียวสำหรับเฟรม และครั้งเดียวสำหรับ ACK ซึ่งขนาดต่างกัน จึงแยกเป็น T_p กับ T_a

ประสิทธิภาพ (Efficiency / Utilization)

ถ้าไม่มีความผิดพลาดเลย ประสิทธิภาพคือสัดส่วนของเวลาที่ "ใช้ส่งข้อมูลจริง" ต่อเวลาทั้งหมด:

η(0) = T_pT สมการ 11.2

ถ้าให้ p = ความน่าจะเป็นที่เฟรมข้อมูลหรือเฟรม ACK จะผิดพลาดระหว่างส่ง (สำเร็จด้วยความน่าจะเป็น 1−p) ประสิทธิภาพในกรณี full duplex จะเป็น:

η_FD = (1 − p) T_p(1 − p) T + p T_p สมการ 11.3

ข้อดี

พัฒนาง่ายที่สุด
ใช้บัฟเฟอร์แค่ 1 เฟรม ฝั่งส่ง
ฝั่งรับไม่ต้องบัฟเฟอร์เลย

ข้อเสีย

ต้องรอ ACK ก่อนถึงจะส่งเฟรมถัดไป → ช่องสัญญาณว่างเปล่าเป็นส่วนใหญ่
ยิ่งระยะไกล (ดาวเทียม / ข้ามประเทศ) ยิ่งแย่ เพราะ T_prop ใหญ่มาก

11.2Selective Repeat ARQ

เพื่อเพิ่มประสิทธิภาพจาก stop-and-wait, Selective Repeat จะส่งเฟรมออกไปอย่างต่อเนื่องตามขนาด Window size (W) โดยไม่ต้องรอ ACK ทีละตัว

ภาคส่ง เก็บเฟรมที่ส่งแล้วไว้ในบัฟเฟอร์ จนกว่าจะได้ ACK ของเฟรมนั้น จึงจะกำจัดทิ้ง
ภาครับ ถ้าได้เฟรมมาตามลำดับ → ส่งขึ้นเลเยอร์ถัดไปทันที
ถ้าได้เฟรมไม่ตามลำดับ (เช่นเฟรมแรกหาย แต่เฟรมที่สองมาถึง) → เก็บไว้ในบัฟเฟอร์ก่อน รอเฟรมที่ขาดมาเติมให้ครบ แล้วค่อยส่งขึ้นไปพร้อมกันตามลำดับ

เงื่อนไขที่ทำให้ภาคส่ง "ส่งซ้ำ" มี 2 อย่าง: ไม่ได้รับ ACK ของเฟรมนั้น หรือ เกิด timeout ของเฟรมนั้น

จุดที่คนพลาดบ่อย — ตำราเล่มนี้ไม่ใช้ NAK ในรูป

หลายคนจำมาว่า "Selective Repeat = ผู้รับส่ง NAK กลับไปบอกว่าเฟรมไหนเสีย" ซึ่งไม่ใช่สิ่งที่รูปที่ 11.4 ในตำราแสดง ตำราบอกไว้ตั้งแต่ต้นบทว่า "ในที่นี้เราจะกล่าวถึงการใช้ ACK เท่านั้น เนื่องจากเป็นวิธีที่ได้รับการยอมรับมากกว่า และมีการใช้งานในเลเยอร์ถัดไปใน TCP" — NAK มีอยู่จริงในหัวข้อ 11.0 แต่ในรูปที่ 11.4 การส่งซ้ำเกิดจาก "ไม่ได้รับ ACK" + "timeout" ล้วน ๆ ถ้าข้อสอบให้วาดตามตำรา อย่าเผลอวาดลูกศร NAK เพิ่มเข้าไป

ขนาดหน้าต่างและการนับหมายเลข

ตำราให้สมมุติว่า Window size (W) คือจำนวนเฟรมในบัฟเฟอร์ที่ภาครับและภาคส่งเก็บได้ และหมายเลขเฟรมนับแบบ modulo 2W — เหตุผลคือต้องมีเลขให้ใช้มากพอที่ผู้รับจะแยกออกว่า "เฟรมที่มาถึงคือเฟรมใหม่ หรือเฟรมเก่าที่ถูกส่งซ้ำ" ถ้าใช้เลขน้อยกว่านี้ หมายเลขจะวนกลับมาชนกันเองแล้วผู้รับจะแยกไม่ออก

กรณีที่ 1 — ปราศจากความผิดพลาดใด ๆ (รูปที่ 11.3)

ก่อนจะดูตอนพลาด ต้องเห็นตอนปกติก่อน ตำราให้ดูรูปที่ 11.3 โดยสมมุติให้ไม่มีความผิดพลาดเกิดขึ้นเลย สิ่งที่ต้องจับให้ได้มี 2 อย่าง

ฝั่งส่ง — "เก็บเฟรมเพื่อรอส่งใหม่หากจำเป็น และกำจัดเฟรมในบัฟเฟอร์เมื่อได้รับ ACK" กองบัฟเฟอร์จึงเลื่อนขึ้นเรื่อย ๆ แต่ความสูงคงที่
ฝั่งรับ — "ส่งเฟรมที่ได้รับตามลำดับให้กับเลเยอร์ถัดไป" ทันทีที่ได้ ไม่ต้องเก็บอะไรค้างไว้เลย เพราะทุกเฟรมมาถูกลำดับอยู่แล้ว

ไดอะแกรมเวลาแนวนอน ด้านส่งและด้านรับ ส่งเฟรม F(N) ถึง F(N+5) ต่อเนื่องกันโดยไม่รอ ACK ทีละตัว มี ACK(N) ถึง ACK(N+4) ทแยงกลับขึ้นมา เหนือรางด้านส่งเป็นกองบัฟเฟอร์สูงสามช่องที่เลื่อนหมายเลขขึ้นเรื่อย ๆ ใต้รางด้านรับเป็นกล่องเฟรมที่ถูกส่งขึ้นเลเยอร์ถัดไปทีละหมายเลขตามลำดับ — รูปที่ 11.3 จากตำรา — การทำงานของ ARQ โดยปราศจากความผิดพลาดใด ๆ (กล่องเขียวบนบอกว่าฝั่งส่งกำจัดเฟรมในบัฟเฟอร์เมื่อได้ ACK · กล่องเขียวล่างบอกว่าฝั่งรับส่งเฟรมที่ได้ตามลำดับขึ้นเลเยอร์ถัดไป)

รูปในตำราพิมพ์ตกอยู่จุดหนึ่ง

บนรางด้านส่งของรูปที่ 11.3 กล่องที่ 6 พิมพ์ว่า F(N+1) ทั้ง ๆ ที่กองบัฟเฟอร์ด้านบนและกล่องที่ฝั่งรับเดินเป็น N, N+1, N+2, … ต่อเนื่องกันตลอด — ที่เป็นแบบนี้เพราะตำราใช้ภาพเดียวกันกับรูปที่ 11.4 (ซึ่งกล่องที่ 6 คือการส่ง N+1 ซ้ำ) แล้วลืมแก้กลับ ในกรณี "ไม่มีความผิดพลาด" กล่องที่ 6 ควรเป็น F(N+5) ให้ยึดตามลำดับ ไม่ต้องงงตาม

กรณีที่ 2 — เฟรม N+1 สูญหาย (รูปที่ 11.4)

นี่คือกรณีที่ตำราใช้แยก Selective Repeat ออกจาก Go-Back-N ตำราเขียนว่า "รูปที่ 11.4 แสดงตัวอย่างหากเกิดการสูญหายของเฟรมที่ N+1 ในการทำงานของ selective repeat ARQ ภาคส่งจะเลือกส่งเฉพาะเฟรมที่สูญหายเท่านั้น โดยภาครับจะจัดเก็บเฟรมที่ได้รับในบัฟเฟอร์ไว้ก่อน เพื่อรอให้ได้รับตามลำดับก่อนที่จะส่งไปในเลเยอร์ถัดไป"

ไล่ตามรูปทีละจังหวะ:

F(N) ถึงปลายทางปกติ → ผู้รับส่งขึ้นเลเยอร์ถัดไป และตอบ ACK(N) → ผู้ส่งลบ N ออกจากบัฟเฟอร์
F(N+1) หายกลางทาง (กากบาทบนลูกศร) → ผู้รับไม่เคยเห็นเฟรมนี้ ในรูปจึงเป็นช่องเส้นประว่าง ๆ บนรางด้านรับ พร้อมข้อความ "ภาครับไม่ได้รับ N+1"
F(N+2), F(N+3), F(N+4) ยังเดินทางไปถึงตามปกติ ผู้รับเก็บทั้งสามไว้ในบัฟเฟอร์ (ข้อความในรูป: "N+2 ถึง N+4 เก็บในบัฟเฟอร์จนกระทั่งได้รับ N+1") และยังตอบ ACK ของแต่ละเฟรมกลับไป เพราะ SR ตอบรับเป็นราย ๆ เฟรม
ฝั่งผู้ส่ง N+1 ยังค้างอยู่ในบัฟเฟอร์ (ช่องสีเทาในรูป) เพราะยังไม่ได้ ACK กองบัฟเฟอร์จึงสูงขึ้นเรื่อย ๆ ไม่ได้เลื่อนขึ้น
timeout ของ N+1 ดัง → "ทำการส่ง N+1 ใหม่" (ลูกศรชี้ลงด้านบนของรูป) — ส่งซ้ำเฉพาะ N+1 เฟรมเดียว ไม่แตะ N+2…N+4 เลย
เมื่อ N+1 มาถึง ลำดับครบ → ผู้รับปล่อย N+1, N+2, N+3, N+4 ขึ้นเลเยอร์ถัดไปพร้อมกัน แล้วตอบ ACK(N+1)

ไดอะแกรมเวลาแนวนอนของ Selective Repeat เฟรม F(N+1) ถูกกากบาทว่าหายกลางทาง รางด้านรับมีช่องเส้นประว่างตรงตำแหน่ง N+1 พร้อมป้ายว่าภาครับไม่ได้รับ N plus 1 เฟรม N+2 ถึง N+4 ถูกกองไว้ในบัฟเฟอร์ใต้รางด้านรับ ด้านบนมีลูกศรชี้ลงพร้อมข้อความ ทำการส่ง N+1 ใหม่ ตรงกองบัฟเฟอร์ที่ N+1 ถูกไฮไลต์ — รูปที่ 11.4 จากตำรา — การทำงานของ Selective Repeat Protocol (จุดชี้ขาด: บนรางด้านส่งมีการส่งซ้ำโผล่มา**กล่องเดียว** คือ F(N+1) แล้วต่อด้วย F(N+5) ทันที — ไม่มีการส่ง N+2…N+4 ซ้ำ)

อ่านกองบัฟเฟอร์ในรูปยังไง

กองสี่เหลี่ยมเหนือรางด้านส่งคือ "ภาพนิ่ง" ของบัฟเฟอร์ผู้ส่ง ณ เวลานั้น ๆ (ตัวใหม่ทับขึ้นข้างบน) ส่วนกองใต้รางด้านรับคือบัฟเฟอร์ผู้รับ ช่องที่ถูกแรเงาเทา = เฟรมที่ยังรอ ACK / เฟรมที่กำลังจะถูกส่งซ้ำ ในรูปที่ 11.4 จะเห็น N+1 เทาค้างอยู่ตลอดจนกว่าจะส่งซ้ำสำเร็จ

กรณีที่ 3 — แบบข้อสอบ (เฟรมหาย + ACK หาย)

ข้อสอบ Q9 โหดกว่ารูปในตำราตรงที่ให้ ACK หายด้วย ลองเดินดูเคสเต็มแบบมีตัวเลขเวลา (timeout 2.5 วินาที, เดินทางทางเดียว 1 วินาที) — สังเกตว่าตอน ACK หาย ผู้ส่งจะส่งเฟรมซ้ำทั้ง ๆ ที่ปลายทางได้ไปแล้ว และผู้รับต้องทิ้งเฟรมซ้ำแต่ยังต้องตอบ ACK ใหม่

ประสิทธิภาพ

η(0) = min{ W T_pT , 1 } สมการ 11.4 — กรณีไม่มีความผิดพลาด

η(p) = 1 − p สมการ 11.5 — กรณี W ใหญ่มาก

η(p) = 2 + p(W − 1)2 + p(3W − 1) สมการ 11.6 — เมื่อ W·T_p คือค่า Timeout

Selective Repeat มีประสิทธิภาพดีที่สุดในสามแบบ แต่ต้องใช้บัฟเฟอร์มากทั้งสองฝั่ง เพราะภาครับต้องเก็บเฟรมที่มาก่อนเวลาไว้รอ

11.3Go-Back-N ARQ

จุดประสงค์เหมือน Selective Repeat คือเพิ่มการใช้งานช่องสัญญาณ แต่ต่างกันที่ฝั่งรับ:

ภาครับ รับเฉพาะเฟรมที่มาตามลำดับเท่านั้น ถ้าไม่ตรงลำดับที่รออยู่ → ทิ้งทันที (ไม่เก็บ)
ภาคส่ง เก็บเฟรมทั้งหมดใน window ไว้ รอจนได้ ACK จึงกำจัด
เมื่อไม่ได้รับ ACK ในเวลาที่กำหนด → ส่งใหม่ตั้งแต่เฟรมที่สูญหายเป็นต้นไปทั้งหมด

เฟรม N+1 สูญหาย — ตามรูปที่ 11.5

ตำราเขียนว่า "ในการทำงานของ go-back-N หากไม่ได้รับการตอบ ACK ในเวลาที่กำหนด เฟรมตั้งแต่หมายเลขที่สูญหายจะถูกส่งออกไปทั้งหมด แตกต่างจากการทำงานของ selective-repeat ARQ ซึ่งจะส่งเฉพาะเฟรมที่เกิดการสูญหายเท่านั้น"

รูปที่ 11.5 ใช้สถานการณ์เดียวกันเป๊ะกับรูปที่ 11.4 (N+1 หาย) เพื่อให้เทียบกันได้ตรง ๆ ความต่างอยู่ที่สองจุด:

ฝั่งรับ — ทิ้ง ไม่เก็บ

ข้อความในรูป: "N+2 ถึง N+4 ถูกกำจัดทิ้งไป เนื่องจากไม่เป็นตามลำดับ" — กล่องบัฟเฟอร์ใต้รางด้านรับจึงเป็นกล่องเดี่ยว ๆ ที่ไม่กองทับกัน ต่างจากรูปที่ 11.4 ที่กองสูงขึ้นเรื่อย ๆ

ฝั่งส่ง — ถอยกลับไปส่งใหม่ยกชุด

ข้อความในรูป: "ตั้งแต่ N+2 ถูกส่งใหม่ แม้ได้รับแล้ว" — บนรางด้านส่งหลัง timeout จึงเป็น F(N+1) แล้วตามด้วย F(N+2) ต่อทันที (และจะไล่ N+3, N+4 ต่อไปอีก) ส่วนกองบัฟเฟอร์ผู้ส่งไม่ยุบลงเลย เพราะปลดอะไรไม่ได้จนกว่า N+1 จะผ่าน

อ่าน animation: กล่องที่ถูกไฮไลต์สีส้มคือ "เฟรมที่มีปัญหา" — เหนือรางด้านส่งหมายถึงเฟรมที่ยังปลดไม่ได้เพราะรอ ACK ส่วนใต้รางด้านรับหมายถึงเฟรมที่เพิ่งถูกทิ้งเพราะมาไม่ตรงลำดับ

ไดอะแกรมเวลาแนวนอนของ Go-Back-N เฟรม F(N+1) ถูกกากบาทว่าหาย รางด้านรับมีช่องเส้นประว่าง เฟรม N+2 ถึง N+4 ปรากฏเป็นกล่องเดี่ยว ๆ ใต้รางด้านรับพร้อมป้ายว่าถูกกำจัดทิ้งเนื่องจากไม่เป็นตามลำดับ กองบัฟเฟอร์เหนือรางด้านส่งสูงสี่ช่องและไม่ลดลง ด้านบนมีลูกศรพร้อมข้อความ ทำการส่ง N+1 ใหม่ — รูปที่ 11.5 จากตำรา — การทำงานของ Go-Back-N (เทียบกับรูปที่ 11.4 ให้ดูสองที่: กล่องใต้รางด้านรับ**ไม่กองทับกัน** และหลัง timeout รางด้านส่ง**ยิงซ้ำมากกว่าหนึ่งเฟรม**)

จุดที่ต้องระวังตอนอ่านรูปที่ 11.5

รูปที่ 11.5 วาดทับบนภาพเดียวกับรูปที่ 11.4 จึงยังมีลูกศร ACK(N+2), ACK(N+3), ACK(N+4) ติดมาด้วย และกล่องสุดท้ายบนรางด้านรับยังเขียนว่า F(N+5) ทั้งที่รางด้านส่งกำลังส่ง F(N+2) ซ้ำอยู่ — ให้ยึดข้อความในตำราเป็นหลัก คือ "ภาครับจะกำจัดเฟรมทิ้งไป และรอจนกระทั่งเฟรมที่ต้องการมาถึง" ตอนวาดเองในข้อสอบ เฟรมที่ผู้รับทิ้งไม่ต้องตอบ ACK (animation ตัวถัดไปวาดตามหลักนี้)

เดินเคสเต็มแบบไล่ทีละสเต็ป

η_FD = 11 + (p1−p) W สมการ 11.7 — full duplex

ตำราสรุปไว้ตรง ๆ ว่า "go-back-N ARQ สามารถเพิ่มประสิทธิภาพการใช้งานเมื่อเทียบกับ stop-and-wait ARQ แต่อย่างไรก็ตาม go-back-N มีประสิทธิภาพด้อยกว่า selective repeat ARQ" — ลำดับที่ต้องจำคือ SR > GBN >> Stop-and-Wait ซึ่งจะเห็นเป็นตัวเลขจริงในตัวอย่าง 11.1 ข้างล่าง (0.928 > 0.925 >> 0.763)

เปรียบเทียบทั้งสามแบบ

Protocol	Send window	Receive window
Stop-and-wait	1	1
Selective repeat	N	N
Go-Back-N	N	1

ตารางที่ 11.1 — ขนาดของบัฟเฟอร์ที่ใช้ใน ARQ แบบต่าง ๆ

กุญแจของตารางนี้

ตัวเลข Receive window คือสิ่งที่แยก Go-Back-N ออกจาก Selective Repeat — GBN ฝั่งรับ = 1 เพราะทิ้งทุกอย่างที่ไม่ตรงลำดับ จึงไม่ต้องมีที่เก็บ ส่วน SR ฝั่งรับ = N เพราะต้องเก็บของที่มาก่อนเวลา ข้อสอบชอบถามตรงนี้

ตัวอย่าง 11.1 (คำนวณเต็มรูปแบบ)

โจทย์ — พิจารณาระบบ WLAN ที่มี propagation delay 4 µs ทำงานที่อัตราเร็ว 10 Mbps ขนาดข้อมูลที่ส่ง = 400 บิต, ขนาด ACK = 20 บิต, processing delay ของทั้งข้อมูลและ ACK = 1 µs ให้ความน่าจะเป็นที่เฟรมสูญหาย p = 0.01 จงหาประสิทธิภาพของ (1) Stop-and-wait (full duplex) (2) Selective Repeat, W = 8 (3) Go-Back-N, W = 8

ลองทำเองก่อน แล้วค่อยกดดูเฉลย

ขั้นที่ 1 — หาเวลาแต่ละส่วน

T_p    = 400 / (10×10⁶) = 40 µs
T_a    = 20 / (10×10⁶) = 2 µs
T_prop = 4 µs  (โจทย์ให้)
T_proc = 1 µs  (โจทย์ให้)

ขั้นที่ 2 — รวมเป็น T

T = 40 + (2 × 4) + (2 × 1) + 2 = 52 µs

ขั้นที่ 3 — แทนสูตรทีละแบบ

Stop-and-wait (สมการ 11.3):

η = (1 − 0.01) × 40(1 − 0.01) × 52 + 0.01 × 40 = 0.763

Selective Repeat, W = 8 (สมการ 11.6):

η = 2 + 0.01(8 − 1)2 + 0.01(24 − 1) = 0.928

Go-Back-N, W = 8 (สมการ 11.7):

η = 11 + 8 × (0.01 / (1 − 0.01)) = 0.925

อ่านผลลัพธ์

SR (0.928) > GBN (0.925) >> S&W (0.763) — ตรงกับทฤษฎีเป๊ะ ๆ ถ้าคำนวณได้ตัวเลขที่เรียงลำดับผิดจากนี้ แปลว่าแทนสูตรผิด ให้กลับไปเช็ค T ก่อนเป็นอันดับแรก

Sliding Window

ทั้ง Selective Repeat และ Go-Back-N ใช้แนวคิด sliding window — หน้าต่างที่ "เลื่อน" ไปข้างหน้าเมื่อได้รับ ACK ของเฟรมที่อยู่ซ้ายสุดของหน้าต่าง

แถบช่องเฟรมเรียงกันเป็นแนวยาว มีกรอบครอบกลุ่มช่องที่อยู่ในหน้าต่างปัจจุบัน และแสดงการเลื่อนกรอบไปทางขวาเมื่อได้รับ ACK ของช่องซ้ายสุด — รูปที่ 11.6 จากตำรา — Sliding Windows (กรอบเลื่อนไปข้างหน้าได้ก็ต่อเมื่อ ACK ของเฟรมซ้ายสุดมาถึง)

เช็คความเข้าใจ

ระบบใช้ Go-Back-N, W = 5 ส่งเฟรม 1,2,3,4,5 ต่อเนื่อง ถ้าเฟรมที่ 2 หาย ภาคส่งจะต้องส่งอะไรใหม่บ้าง?

Go-Back-N ฝั่งรับทิ้งเฟรม 3, 4, 5 ทันทีเพราะมาไม่ตรงลำดับ ภาคส่งจึงต้อง "ถอยกลับ" ไปส่งใหม่ตั้งแต่เฟรมที่หาย (2) จนหมด window คือ 2, 3, 4, 5 — ส่วนเฟรมที่ 1 ได้ ACK ไปแล้ว จึงไม่ต้องส่งซ้ำ

โจทย์เดิม แต่เปลี่ยนเป็น Selective Repeat จะส่งใหม่กี่เฟรม?

Selective Repeat ฝั่งรับเก็บ 3, 4, 5 ไว้ในบัฟเฟอร์ รอแค่เฟรม 2 มาเติม ภาคส่งจึงส่งซ้ำเฉพาะเฟรม 2 เท่านั้น — นี่คือเหตุผลที่ SR มีประสิทธิภาพสูงกว่า แต่แลกมาด้วยบัฟเฟอร์ฝั่งรับขนาด N

ในรูปที่ 11.4 (Selective Repeat, เฟรม N+1 หาย) อะไรคือสิ่งที่ทำให้ผู้ส่งรู้ว่าต้องส่ง N+1 ใหม่?

ตำราระบุเงื่อนไขการส่งซ้ำของ Selective Repeat ไว้ 2 อย่างเท่านั้น คือ "การที่ไม่ได้รับ ACK ของเฟรม" และ "การเกิด timeout ของเฟรม" — และประกาศไว้ตั้งแต่ต้นบทว่าจะกล่าวถึงเฉพาะการใช้ ACK รูปที่ 11.4 จึงไม่มีลูกศร NAK เลย ส่วน duplicate ACK เป็นกลไกของ TCP ไม่ใช่สิ่งที่บทนี้สอน

รูปที่ 11.4 กับรูปที่ 11.5 ใช้สถานการณ์เดียวกัน (N+1 หาย) ความต่างที่มองเห็นได้ชัดที่สุดในรูปอยู่ตรงไหน?

หัวใจอยู่ที่ฝั่งรับ — SR (11.4) เขียนว่า "N+2 ถึง N+4 เก็บในบัฟเฟอร์จนกระทั่งได้รับ N+1" กองจึงสูงขึ้น ส่วน GBN (11.5) เขียนว่า "N+2 ถึง N+4 ถูกกำจัดทิ้งไป เนื่องจากไม่เป็นตามลำดับ" จึงเป็นกล่องเดี่ยว ๆ ไม่กองกัน · ผลที่ตามมาบนรางด้านส่งคือ 11.4 ส่งซ้ำเฟรมเดียว แต่ 11.5 ต้องส่งซ้ำตั้งแต่ N+1 ไปทั้งชุด

Stop-and-wait ARQ ฝั่งรับต้องใช้บัฟเฟอร์กี่เฟรม?

ตามตารางที่ 11.1 Receive window ของ Stop-and-wait = 1 — เพราะรับได้ทีละเฟรมเดียว ประมวลผลเสร็จก็ส่งขึ้นเลเยอร์ถัดไปทันที (ในเนื้อหาระบุว่า "ภาครับไม่จำเป็นต้องบัฟเฟอร์ข้อมูลใด ๆ" ในความหมายว่าไม่ต้องเก็บรอเรียงลำดับ แต่ในตารางนับ receive window = 1)

เก็บก่อนออกจากบทนี้

วาด timing diagram ให้เป็น — เส้นตั้ง 2 เส้น (ผู้ส่ง/ผู้รับ) ลูกศรเฉียงลง เขียนชื่อเฟรมกำกับ และเขียนเส้นประ timeoutทุกเฟรมที่ส่ง
T = T_p + 2T_prop + 2T_proc + T_a — ท่องให้ได้
ตารางบัฟเฟอร์ 1/1, N/N, N/1
Timeout < RTT → เกิดการส่งซ้ำที่ไม่จำเป็น และเกิด เฟรมซ้ำ (duplicate) ที่ฝั่งรับ
ตำรามีทั้งกรณีสำเร็จและกรณีพลาด — รูปที่ 11.3 = ARQ ไม่มีความผิดพลาด · รูปที่ 11.4 = SR ตอน N+1 หาย · รูปที่ 11.5 = GBN ตอน N+1 หาย ถ้าโจทย์ให้ "วาดการทำงาน" ต้องดูให้ดีว่าขอกรณีไหน
ตัวกระตุ้นการส่งซ้ำในตำราคือ ไม่ได้รับ ACK + timeout เท่านั้น (ไม่ใช่ NAK) และ เฟรมที่ผู้รับทิ้งใน GBN ไม่ต้องตอบ ACK