บทที่ 13

การใช้งานช่องสัญญาณ

หลายเครื่องใช้สายเส้นเดียวกัน — จะแบ่งกันใช้ยังไงไม่ให้ข้อมูลชนกัน? บทนี้มีสองแนวคิดใหญ่ คือ จองล่วงหน้า (FDMA/TDMA) กับ ใครมีข้อมูลก็ส่งเลย แล้วค่อยแก้ตอนชน (ALOHA, CSMA, CSMA/CD)

อ่าน ~18 นาที ออกสอบ 2 ข้อ เชื่อมกับ ข้อสอบ Q12, Q13
ข้อสอบออกแบบไหน

บทนี้ออก 2 ข้อ และทั้งสองข้อเป็น "จำสูตร + แทนค่า" ล้วน ๆ ไม่มีอะไรลึกลับ:

  • Q12 — Binary Exponential Backoff & ALOHA · ถามว่ารอบที่ k สุ่มค่า c จากช่วงไหน และทรูพุตสูงสุดของ ALOHA แต่ละแบบเป็นเท่าไร ที่ G เท่าไร
  • Q13 — CSMA/CD Collision Window · ถามว่าทำไมเฟรมต้องยาวอย่างน้อย 2τ ถึงจะตรวจจับการชนได้ (ที่มาของ minimum frame size)

ภาพรวม — ทำไมต้องมีกติกาเข้าใช้ช่องสัญญาณ

แบนด์วิดท์มีจำกัด ไม่ว่าจะเป็นสื่อแบบมีสายหรือไร้สาย แต่ผู้ใช้มีจำนวนมาก และแต่ละคนใช้งานไม่เท่ากัน — บางช่วงเวลาผู้ใช้คนหนึ่งอยากโอนไฟล์ใหญ่ ๆ บางช่วงเวลาก็ไม่ส่งอะไรเลย บางคนส่งทีละนิดแต่ส่งบ่อยมาก

การมัลติเพล็กซ์ช่วยให้ใช้ทรัพยากรที่มีจำกัดร่วมกันได้อย่างมีประสิทธิภาพ แต่การใช้ร่วมกันก็ทำให้ต้องมี "การควบคุม" เพื่อป้องกันความเสียหายของข้อมูลจากการที่หลายคนเข้าใช้พร้อมกัน วิธีควบคุมแบ่งเป็นสองสายใหญ่:

① Deterministic Access (13.1)

จองล่วงหน้า — แบ่งทรัพยากรออกเป็นส่วนย่อยแล้วยกให้ผู้ใช้แต่ละคนเป็นเจ้าของ
แบ่งตามความถี่ → FDM / FDMA
แบ่งตามเวลา → TDM / TDMA
ชนไม่ได้เลย แต่ช่องว่างถูกทิ้งเปล่า

② Random Access (13.2)

ใครมีข้อมูลก็ร้องขอเลย ไม่ต้องจองล่วงหน้า
เหมาะกับข้อความขนาดเล็กที่ส่ง ๆ หยุด ๆ
ได้แก่ Pure ALOHA, Slotted ALOHA, CSMA, CSMA/CD
ใช้ช่องได้เต็มเมื่อมีคนเดียว แต่ชนกันได้

เส้นเรื่องของทั้งบท

ทุกโพรโตคอลใน 13.2 คือความพยายาม "ลดช่วงเวลาที่เสี่ยงจะชน" ทีละขั้น — Pure ALOHA เสี่ยง 2T → Slotted ALOHA บังคับให้เริ่มที่ขอบสล็อต เหลือ T → CSMA ฟังก่อนส่ง เหลือแค่ช่วง propagation delay → CSMA/CD ฟังระหว่างส่งด้วย ทำให้หยุดกลางคันได้ ไม่ต้องส่งเฟรมเสียจนจบ ทรูพุตจึงไล่จาก 0.184 → 0.368 → เกือบ 1

13.1Deterministic Access Methods

การจัดสรรทรัพยากรแบบ Deterministic Access คือผู้ใช้จองช่องสัญญาณล่วงหน้า เพื่อให้เกิดการใช้ทรัพยากรร่วมกัน ทำได้โดยการแบ่งช่องสัญญาณออกเป็นส่วนย่อย

  • แบ่งในเชิงความถี่ → Frequency Division Multiplexing (FDM) → เมื่อใช้เป็นวิธีเข้าถึงของผู้ใช้หลายคน เรียกว่า FDMA
  • แบ่งในเชิงเวลา → Time Division Multiplexing (TDM) → TDMA

13.1.1Frequency Division Multiple Access (FDMA)

FDMA ถือเป็นวิธีที่ง่ายที่สุดในการใช้ทรัพยากรร่วมกัน — ผู้ใช้แต่ละคนได้รับการจัดสรรช่องความถี่ที่ต่างกัน และต้องกำหนดให้มี Guard band ระหว่างช่องความถี่ของแต่ละผู้ใช้ เพื่อลดผลของครอสทอล์ก (crosstalk) ที่อาจเกิดขึ้น ฝั่งผู้ใช้ดึงข้อมูลของตัวเองออกมาได้ด้วย bandpass filter ตัวเดียว

ข้อดีของ FDMA

  • ไม่ต้องมีอุปกรณ์ควบคุมกลาง (coordinator)
  • รองรับการทำงานในระบบแอนะล็อกได้
  • พัฒนาง่าย ผู้ใช้ใช้เพียง bandpass filter เพื่อแยกสัญญาณที่ต้องการ

ข้อเสียของ FDMA

  • ใช้ช่องสัญญาณอย่างไม่มีประสิทธิภาพ — ถ้าช่องไหนไม่มีการใช้งาน ช่องนั้นจะถูกทิ้งไป ไม่ได้ถูกนำมาเพิ่มความจุให้ระบบ
  • จำเป็นต้องมี Guard band ทำให้สูญเสียแบนด์วิดท์บางส่วน

13.1.2Time Division Multiple Access (TDMA)

ใน TDMA ผู้ใช้ ใช้ช่องสัญญาณทั้งหมด (แบนด์วิดท์เต็ม) แต่ใช้ได้เฉพาะในช่วงเวลาหนึ่ง โดยแต่ละช่วงเวลาถูกแบ่งเท่า ๆ กัน เรียกว่า สล็อต (slot) ข้อมูลของผู้ใช้จะถูกใส่เข้าไปในสล็อตเพื่อรวมกันเป็นเฟรมต่อไป และผู้ใช้คนหนึ่งสามารถใช้หลายสล็อตพร้อมกันได้ เพื่อให้ได้บิตเรทที่สูงขึ้น

ข้อดีของ TDMA

  • ปรับบิตเรทได้ โดยใช้หลายช่องสัญญาณ (หลายสล็อต) พร้อมกัน เพื่อให้มีอัตราการส่งที่เร็วขึ้น
  • ใช้แบนด์วิดท์ได้อย่างมีประสิทธิภาพ เพราะไม่จำเป็นต้องมี Guard band ระหว่างช่องสัญญาณ

ข้อเสียของ TDMA

  • ต้องทำซิงโครไนเซชัน (synchronization) เพื่อป้องกันการชนของสัญญาณ — ถ้านาฬิกาเพี้ยน สล็อตจะเหลื่อมกันแล้วชนทันที
แผนภาพ FDMA แบ่งแบนด์วิดท์เป็นช่องความถี่ F1–F6 พร้อม Guard Band
รูปที่ 13.1 จากตำรา — การทำงานของ FDMA (แบ่งตามความถี่ มี Guard Band คั่น)
แผนภาพ TDMA แบ่งเวลาออกเป็นสล็อต T1–T6 โดยแต่ละสล็อตใช้แบนด์วิดท์เต็ม
รูปที่ 13.2 จากตำรา — การทำงานของ TDMA (แบ่งตามเวลา ใช้แบนด์วิดท์เต็มทุกสล็อต)
จุดที่คนพลาดบ่อย

อย่าสลับ "ข้อเสียหลัก" ของสองตัวนี้ — FDMA เสีย Guard band (เสียแบนด์วิดท์) และช่องที่ไม่ได้ใช้ก็ถูกทิ้งเปล่า ส่วน TDMA ไม่ต้องมี Guard band แต่ต้อง synchronize ข้อสอบชอบเอาสองข้อนี้มาสลับกันแล้วให้ตอบว่าถูกหรือผิด

13.2การเข้าใช้ช่องสัญญาณแบบสุ่ม (Random Access Methods)

การเข้าใช้ช่องสัญญาณแบบสุ่มทำให้การส่งข้อความขนาดเล็กมีประสิทธิภาพมากขึ้น — ผู้ใช้ร้องขอช่องสัญญาณเมื่อมีข้อมูลที่ต้องการส่ง ไม่จำเป็นต้องจองการใช้ล่วงหน้า

แต่วิธีนี้ก็มีปัญหาที่ตามมาคือ การชนกัน (collision) เพราะมีมากกว่าหนึ่งเครื่องเข้าใช้ช่องสัญญาณ ณ เวลาพร้อมกัน ทำให้ต้องส่งข้อมูลใหม่อีกครั้ง วิธีที่นิยมใช้มี 4 แบบ:

วิธีฟังสายก่อนส่งไหมฟังระหว่างส่งไหมช่วงเสี่ยงจะชนทรูพุตสูงสุด
Pure ALOHAไม่ฟังไม่2Tp0.184 ที่ G = 0.5
Slotted ALOHAไม่ฟัง (แต่ต้องรอขอบสล็อต)ไม่Tp0.368 ที่ G = 1
CSMAฟัง (carrier sense)ไม่≈ τ (propagation delay)สูงกว่า ALOHA มาก (สมการ 13.6–13.9)
CSMA/CDฟังฟัง (collision detection)≈ τ แต่ตัดจบได้เร็วสูงที่สุดในกลุ่มนี้ (สมการ 13.10–13.11)

สรุปภาพรวมของ 13.2 — อ่านจากบนลงล่างคือลำดับวิวัฒนาการของโพรโตคอล

13.2.1การประมาณประสิทธิภาพของเน็ตเวิร์ก

ก่อนจะดูโพรโตคอลแต่ละตัว ต้องรู้ก่อนว่า "ประสิทธิภาพ" ที่จะเอามาเทียบกันคืออะไร ค่าที่ได้รับความสนใจมี 2 ตัว:

  • เวลาหน่วงเฉลี่ยของแพ็กเก็ต (average packet delay) ของการเข้าใช้ช่องสัญญาณ
  • ทรูพุต (throughput)

ประสิทธิภาพของเน็ตเวิร์กขึ้นอยู่กับปฏิสัมพันธ์ของตัวแปรสองตัว คือ ทราฟฟิกที่เข้ามายังระบบ (traffic load) และ ทรัพยากรของเน็ตเวิร์ก (network resource) เช่น ขนาดของบัฟเฟอร์ หรือความเร็วในการประมวลผล

โมเดลแถวคอย (Queueing model)

วิธีที่นิยมใช้ประเมินทรูพุตคือ โมเดลแถวคอยแบบหน่วยบริการช่องเดียว (single queue model) ตามรูปที่ 13.3 ด้านล่าง — หมายถึงมีบัฟเฟอร์เก็บแพ็กเก็ตเพียงแถวเดียว เพื่อเก็บแพ็กเก็ตที่รอการประมวลผล โดยแพ็กเก็ตมีขนาด Lp

จำนวนแพ็กเก็ตในบัฟเฟอร์ขึ้นอยู่กับจำนวนสเตชันที่ต่ออยู่บนช่องสัญญาณ — สเตชันยิ่งมาก อัตราการเข้ามาของแพ็กเก็ต (packet arrival rate) ยิ่งสูง ส่วนแพ็กเก็ตที่ส่งเข้ามาจะส่งสำเร็จหรือไม่ ขึ้นอยู่กับวิธีการใช้ช่องสัญญาณที่เลือกใช้ (ซึ่งก็คือหัวข้อ 13.2.2–13.2.5 ทั้งหมด)

แผนภาพโมเดลแถวคอยช่องเดียว ทางซ้ายมีลูกศร lambda เข้ามารวมกับ lambda ไพรม์ ที่ย้อนกลับมาจากด้านขวา กลายเป็น lambda T ผ่านกล่องสองกล่องที่กำกับขนาดของแพ็กเก็ต Lp แล้วเข้าสู่แถวคอยที่มีช่องเก็บแพ็กเก็ตห้าช่องกำกับว่าขนาดของบัฟเฟอร์และแพ็กเก็ตที่อยู่ในคิว ก่อนออกไปยังวงกลมที่เขียนว่าคอนโทรเลอร์
รูปที่ 13.3 จากตำรา — โมเดลแถวคอยแบบหน่วยบริการช่องเดียว (Single queue model) (สังเกตลูกศร λ′ ที่วนย้อนกลับมาจากด้านขวา — นั่นคือแพ็กเก็ตที่ชนแล้วต้องส่งซ้ำ มันถูกบวกเข้ากับ λ กลายเป็น λT ที่ยิงลงช่องสัญญาณจริง นี่คือรูปภาพของสมการ 13.2 กับ 13.3 ทั้งคู่)
ส่วนขยาย (นอกต้นฉบับ)

โมเดล "แถวคอยแถวเดียว + หน่วยบริการหนึ่งตัว + แพ็กเก็ตขาเข้าแบบ Poisson" ที่หนังสือเรียกว่า single queue model นี้ ในตำรา queueing theory ทั่วไปจะรู้จักกันในชื่อ M/M/1 (M ตัวแรก = Markovian arrivals แบบ Poisson, M ตัวที่สอง = เวลาบริการแบบ exponential, 1 = มีหน่วยบริการตัวเดียว) — หนังสือเล่มนี้ไม่ได้ใช้ชื่อนี้ตรง ๆ แต่ถ้าเจอชื่อ M/M/1 ในข้อสอบหรือสไลด์ ให้เข้าใจว่าคือรูปที่ 13.3 ตัวเดียวกัน

Poisson Statistics

การกำหนดให้แพ็กเก็ตขาเข้าเป็น Poisson Statistics ถือเป็นวิธีที่นิยมเพื่อศึกษาทรูพุต โดยอยู่บนสมมุติฐานว่าแพ็กเก็ตแต่ละแพ็กเก็ตที่ได้รับไม่มีความสัมพันธ์ต่อกัน แต่มีการกระจายแบบ Poisson distribution ความน่าจะเป็นที่จะมีแพ็กเก็ตเข้ามาจำนวน n ในช่วงเวลา t ใด ๆ เป็น:

Pn(t) = (λt)n e−λtn! สมการ 13.1 · n = 0, 1, 2, …
สัญลักษณ์ความหมายหน่วย
λอัตราเร็วเฉลี่ยของแพ็กเก็ตที่มา (average packet arrival rate) — นับเฉพาะแพ็กเก็ตใหม่แพ็กเก็ต/วินาที
tช่วงเวลาที่พิจารณาวินาที
nจำนวนแพ็กเก็ตที่เข้ามาในช่วง tแพ็กเก็ต

แทนค่าจริง — ถ้า λ = 100 แพ็กเก็ต/วินาที และเราสนใจช่วง t = 10 ms = 0.01 s แล้ว λt = 1
โอกาสที่ช่วงนี้จะไม่มีแพ็กเก็ตเลย (n = 0) = (10 · e−1) / 0! = e−1 = 0.368
โอกาสที่จะมีพอดี 1 แพ็กเก็ต (n = 1) = (11 · e−1) / 1! = 0.368 เช่นกัน
โอกาสที่จะมี 2 แพ็กเก็ต = (12 · e−1) / 2! = 0.184 ← ตัวเลข 0.368 กับ 0.184 คุ้น ๆ ไหม? นี่คือที่มาของทรูพุต ALOHA พอดีเป๊ะ

Normalized throughput (S) และ Offered load (G)

การคำนวณทรูพุตเป็นการประเมินเฉพาะกรณีที่แพ็กเก็ตส่งสำเร็จเท่านั้น (บิต/วินาที หรือ แพ็กเก็ต/วินาที) ไม่รวมแพ็กเก็ตที่เสียหาย เพื่อให้การวิเคราะห์ไม่ขึ้นกับอัตราเร็วของการส่ง จึงเขียนในรูป normalized throughput:

S = λ LpR สมการ 13.2 — normalized throughput · ค่าอยู่ระหว่าง 0 – 1

ส่วน Offered load (G) คือ load ที่เกิดขึ้นจริงในเน็ตเวิร์ก หรือทราฟฟิกที่ต้องส่ง รวมแพ็กเก็ตที่ส่งซ้ำ (retransmitted) ด้วย ดังนั้น offered traffic (λT) = แพ็กเก็ตที่ส่งสำเร็จตั้งแต่ครั้งแรก (λ) + แพ็กเก็ตที่ถูกส่งซ้ำเพราะเสียหายระหว่างส่ง (λ′)

G = λT LpR สมการ 13.3 — normalized offered load · โดย λT = λ + λ′ และ λT ≥ λ
สัญลักษณ์ความหมาย
Lpขนาดความยาวของแพ็กเก็ต (บิต)
Rอัตราเร็วของการส่ง (transmission rate) หน่วยบิต/วินาที
λอัตราแพ็กเก็ตใหม่ที่ส่งสำเร็จ
λ′อัตราแพ็กเก็ตที่ต้องส่งซ้ำ
λTทราฟฟิกรวมที่ยิงลงช่องสัญญาณจริง = λ + λ′
จุดที่คนพลาดบ่อย

อย่าสับสน S กับ G — G คือ "ยิงลงสายไปเท่าไร" (รวมของที่ยิงซ้ำ) ส่วน S คือ "รอดถึงปลายทางเท่าไร" ดังนั้น S ≤ G เสมอ และเมื่อ G สูงมาก ๆ (คนแย่งกันส่งจนชนกันหมด) S จะไม่โตตาม แต่จะตกลง — นี่คือสาเหตุที่กราฟ ALOHA เป็นรูปโค้งคว่ำ ไม่ใช่เส้นที่ขึ้นเรื่อย ๆ
(หมายเหตุ: ในต้นฉบับ สมการ 13.3 พิมพ์ตัวแปรฝั่งซ้ายเป็น "S" แต่จากประโยคนำหน้าที่ว่า "ค่า normalized offered load (G) จะหาได้จาก" ตัวแปรฝั่งซ้ายต้องเป็น G)

13.2.2Pure ALOHA

หลักการเรียบง่ายที่สุดในโลก — มีข้อมูลเมื่อไร ส่งเลยทันที ไม่ต้องฟัง ไม่ต้องรอ:

  1. ผู้ใช้ส่งข้อมูลออกไปเป็นแพ็กเก็ตทันทีที่มีข้อมูล
  2. หลังส่งเสร็จ ผู้ใช้รอเท่ากับเวลาหน่วงของการส่งไปและกลับ (Round-trip delay) เพื่อรอ ACK จากผู้รับ
  3. ถ้าไม่ได้รับ ACK ในช่วงเวลาที่กำหนด → ถือว่าแพ็กเก็ตนั้นเสียหายเพราะการชนกัน
  4. ผู้ส่งจะสุ่มหาเวลาในการส่งแพ็กเก็ตออกไปใหม่

ถ้า ACK ไม่มา แล้วยังไงต่อ — ผังงานเต็มของ Pure ALOHA (รูปที่ 13.4)

สี่ข้อด้านบนคือกรณีส่งสำเร็จ แต่หัวใจของ ALOHA อยู่ที่กรณีชน ซึ่งตำราเขียนไว้ครบเป็นผังงานในรูปที่ 13.4 — และวงจรนี้คือวงจรเดียวกับผังงาน CSMA/CD (รูปที่ 13.11) ต่างกันแค่ ALOHA รู้ว่าชนจาก "ACK ไม่มาภายใน timeout" ส่วน CSMA/CD รู้จากการฟังสายด้วยตัวเอง

ขั้นกล่องในผังงานทำอะไร
1เริ่ม → ให้ K = 0สเตชันมีเฟรมพร้อมส่ง — เคลียร์ตัวนับจำนวนครั้งที่พยายามส่งเป็นศูนย์ก่อน
2ส่งเฟรมยิงออกไปเลย ไม่ต้องฟังสาย (นี่คือนิยามของ ALOHA)
3รอ Timeout (2 × TP)รอ ACK นาน 2 × TP — ก็คือ round-trip delay (ไป TP · กลับ TP)
4ได้รับ ACK? → ได้ส่งสำเร็จ จบงาน
5ได้รับ ACK? → ไม่ได้ถือว่าเฟรมเสียหายเพราะการชน → เพิ่มค่า K (K = K + 1)
6K > Kmax? → ใช่ยกเลิก ทิ้งเฟรมไป (ตำรากำกับข้างกล่องว่า "โดยทั่วไป Kmax มีค่าไม่เกิน 15")
7K > Kmax? → ไม่ใช่สุ่มค่า C ระหว่าง 0 ถึง 2K − 1
8รอเวลาหน่วง TBTB = C × TP หรือ C × Tfr แล้ววนกลับไปข้อ 2 ส่งใหม่
สัญลักษณ์ในรูปที่ 13.4ความหมาย (คำต่อคำจากตำรา)
Kจำนวนครั้งที่จะพยายามส่ง
TPเวลาหน่วง propagation time สูงสุด
Tfrค่าเฉลี่ยเวลาหน่วงของการส่งข้อมูล (transmission time) ของเฟรม
TBเวลาในการทำ Back-off
ผังงานการทำงานของ Pure ALOHA เริ่มจากสเตชันมีเฟรมพร้อมส่ง กำหนดให้ K เท่ากับ 0 แล้วส่งเฟรม จากนั้นรอ Timeout เท่ากับ 2 คูณ T_P ถ้าได้รับ ACK ถือว่าส่งสำเร็จ ถ้าไม่ได้รับให้เพิ่มค่า K ขึ้นหนึ่ง แล้วตรวจว่า K มากกว่า K max หรือไม่ ถ้าใช่ให้ยกเลิก ถ้าไม่ใช่ให้สุ่มค่า C ระหว่าง 0 ถึง 2 ยกกำลัง K ลบ 1 แล้วรอเวลาหน่วง T_B ซึ่งเท่ากับ C คูณ T_P หรือ C คูณ T_fr ก่อนวนกลับไปส่งเฟรมใหม่
รูปที่ 13.4 จากตำรา — การทำงานของ Pure ALOHA ([14]) (เดินตามลูกศรฝั่งขวาลงมาคือกรณีส่งสำเร็จ · ลูกศรที่วิ่งย้อนกลับไปทางซ้ายผ่านกล่องเหลือง "K > Kmax" คือกรณีชนแล้วต้องส่งซ้ำ ซึ่งเป็นเส้นทางที่ข้อสอบถาม)
รูปนี้สำคัญกว่าที่คิด

กล่อง "สุ่มค่า C ระหว่าง 0 ถึง 2K − 1" และ "TB = C × TP หรือ C × Tfr" ในรูปที่ 13.4 คือกล่องเดียวกันเป๊ะกับที่โผล่อีกครั้งในผังงาน CSMA/CD (รูปที่ 13.11) และเป็นสูตรที่ ข้อสอบ Q12 ถามตรง ๆ — จำผังเดียวตอบได้สองเรื่อง

ช่วงเวลาที่เสี่ยงจะชน (Vulnerable period) = 2Tp

สมมติสเตชัน A เริ่มส่งที่เวลา T0 และเฟรมยาว Tp เฟรมของ A จะชนกับใครได้บ้าง?

  • สเตชันที่เริ่มส่งก่อน A ไม่ถึง Tp → เฟรมนั้นยังส่งไม่จบตอน A เริ่ม → ท้ายของมันทับหัวของ A
  • สเตชันที่เริ่มส่งหลัง A แต่ก่อน A จะส่งจบ → หัวของมันทับท้ายของ A

รวมแล้วช่วงอันตรายกว้าง Tp + Tp = 2Tp — ถ้ามีใครเริ่มส่งในช่วงนี้ เฟรมของ A พังทันที

ไดอะแกรมเวลาแสดงเฟรมสามเฟรมวางเหลื่อมกัน เฟรม B จบพอดีตรงเวลา T0 ซึ่งเป็นจุดที่เฟรม A เริ่มส่ง ทำให้ช่วงท้ายของ B ทับกับส่วนเริ่มต้นของ A และเฟรม C เริ่มก่อนที่ A จะจบที่เวลา T0 บวก Tp ทำให้ช่วงท้ายของ A ทับกับส่วนเริ่มต้นของ C แถบสีฟ้าสองแถบทำเครื่องหมายจุดที่เฟรมทับกัน ด้านล่างมีลูกศรสองหัวกว้าง 2Tp กำกับว่าเป็นช่วงเวลาที่จะเกิดการส่งพร้อมกัน
รูปที่ 13.5 จากตำรา — ช่วงเวลาที่จะทำให้เฟรมเกิดการชนกันในการส่งแบบ Pure ALOHA (แถบฟ้าสองแถบคือจุดที่เฟรมทับกันจริง: ช่วงท้ายของ B ชนกับส่วนเริ่มต้นของ A และ ช่วงท้ายของ A ชนกับส่วนเริ่มต้นของ C — วัดจากซ้ายสุดถึงขวาสุดได้ 2Tp พอดี)

อ่านรูปที่ 13.5 ทีละเฟรม — ยึดเฟรม A เป็นตัวตั้ง A เริ่มที่ T0 และจบที่ T0 + Tp
• B เริ่มก่อน A ไม่ถึงหนึ่งเฟรม → ตอน A เริ่ม B ยังส่งไม่จบ → ท้าย B ชนหัว A (แถบฟ้าซ้าย)
• C เริ่มก่อน A จะจบ → ท้าย A ชนหัว C (แถบฟ้าขวา)
• เฟรม A จะรอดก็ต่อเมื่อไม่มีใครเริ่มส่งเลยตลอดช่วง [T0 − Tp , T0 + Tp] ซึ่งกว้าง 2Tp
จุดที่คนมักมองข้าม: เวลาชนกัน เฟรมพังทั้งคู่ ไม่ใช่พังแค่คนที่มาทีหลัง — ทั้ง A และ B ต่างไม่ได้ ACK แล้วต้องเข้าลูป backoff ตามผังงานรูปที่ 13.4 ด้วยกันทั้งสองเครื่อง นั่นแปลว่าหนึ่งการชน = สอง เฟรมที่ต้องส่งซ้ำ ซึ่งก็คือ λ′ ในรูปที่ 13.3 นั่นเอง

S = G e−2G สมการ 13.4 — normalized throughput ของ Pure ALOHA · G = normalized offered traffic load

จากสมการ 13.4 ค่าทรูพุตสูงสุดเกิดขึ้นเมื่อ traffic load อยู่ที่ G = 50% (G = 0.5) ได้ S = 1/2e ≈ 0.184 ดังนั้นประสิทธิภาพการใช้งานของ Pure ALOHA อยู่ที่ 18.4%

แทนค่าจริง — ช่องสัญญาณ 1 Mbps เฟรมละ 1000 บิต ⇒ ส่งได้สูงสุดตามทฤษฎี 1000 เฟรม/วินาที
• ที่ G = 0.5 → S = 0.5 × e−1 = 0.184 ⇒ ส่งสำเร็จจริง 184 เฟรม/วินาที
• ที่ G = 1.0 → S = 1 × e−2 = 0.135 ⇒ 135 เฟรม/วินาที (ยิงมากขึ้นแต่ได้น้อยลง!)
• ที่ G = 2.0 → S = 2 × e−4 = 0.037 ⇒ 37 เฟรม/วินาที (ระบบเกือบล่ม)

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

เลข 2 ใน e−2G มาจากช่วงเสี่ยง 2Tp ไม่ใช่มาจากอย่างอื่น จำคู่กันไว้: ช่วงเสี่ยง 2T → เลขชี้กำลัง −2G → ทรูพุตสูงสุดครึ่งเดียวของ slotted ถ้าจำสลับเป็น S = Ge−G สำหรับ pure จะได้ 0.368 ซึ่งผิด

13.2.3Slotted ALOHA

ปรับปรุงจุดอ่อนของ Pure ALOHA ด้วยกฎข้อเดียว — ห้ามเริ่มส่งกลางคัน ต้องเริ่มที่ขอบสล็อตเท่านั้น

  • การส่งข้อมูลจะถูกแบ่งออกเป็นสล็อต แต่ละสล็อตถูกแบ่งเท่า ๆ กัน
  • ผู้ใช้แต่ละคนกำหนดเวลาเริ่มส่งเท่ากับการเริ่มต้นของสล็อต
  • เมื่อพบว่ามีแพ็กเก็ตที่ต้องการส่ง แพ็กเก็ตจะถูกรอไว้ก่อน และจะถูกส่งออกในสล็อตถัดไป

ผลก็คือ ช่วงเวลาที่เกิดการชนกันของแพ็กเก็ตลดลงครึ่งหนึ่ง เมื่อเทียบกับ Pure ALOHA (จาก 2Tp เหลือ Tp) เพราะกรณี "เริ่มก่อนนิดหน่อยแล้วท้ายไปทับหัว" หายไปหมด — เหลือแค่กรณีเลือกสล็อตเดียวกันเท่านั้นที่จะชน

S = G e−G สมการ 13.5 — normalized throughput ของ Slotted ALOHA

จากสมการ 13.5 ค่าทรูพุตสูงสุดของ Slotted ALOHA มีค่าเป็น 1/e ≈ 0.368 เกิดขึ้นเมื่อ G = 1 หมายถึงระบบมีประสิทธิภาพการใช้งานอยู่ที่ 36.8% หรือเป็นสองเท่าของ Pure ALOHA

ภาพเคลื่อนไหวข้างบนคือรูปที่ 13.5 (Pure) และรูปที่ 13.6 (Slotted) ในตำรา วาดใหม่ให้เดินทีละสเต็ปได้ — ส่วนรูปจากตำราตัวจริง อยู่ที่หัวข้อ 13.2.2 (รูปที่ 13.5) และด้านล่างนี้ (รูปที่ 13.6)

ไดอะแกรมเวลาของ slotted ALOHA เส้นประแนวตั้งแบ่งเวลาออกเป็นสล็อต เฟรม B อยู่ในสล็อตก่อนหน้าจึงไม่ชนกับใคร ส่วนเฟรม A และเฟรม C เริ่มพร้อมกันที่ขอบสล็อตเดียวกันตั้งแต่ T0 ถึง T0 บวก Tp ทั้งสล็อตถูกระบายสีฟ้าแสดงว่าชนกัน ด้านล่างมีลูกศรสองหัวกว้างเท่ากับ Tp กำกับว่าเป็นช่วงเวลาที่จะเกิดการส่งพร้อมกัน
รูปที่ 13.6 จากตำรา — ช่วงเวลาที่จะทำให้เฟรมเกิดการชนกันในการส่งแบบ slotted ALOHA (ป้ายบนรูปเขียนไว้ตรง ๆ ว่า "A และ C เริ่มส่งในสล็อตเดียวกัน" จึงชนกันเต็มสล็อต ส่วน B อยู่คนละสล็อตจึงรอด — ช่วงเสี่ยงจึงเหลือแค่ Tp คือความกว้างของสล็อตเดียว)
เทียบรูปที่ 13.5 กับ 13.6 — ต่างกันบรรทัดเดียว

รูปที่ 13.5 (Pure) เฟรม B ที่เริ่มก่อน A ยังชน A ได้ เพราะใครจะเริ่มส่งกลางคันก็ได้ → ช่วงเสี่ยง = 2Tp
รูปที่ 13.6 (Slotted) B ถูกบังคับให้เริ่มที่ขอบสล็อต จึงจบลงพอดีก่อนสล็อตของ A → เหลือแค่กรณี "เลือกสล็อตเดียวกัน" (A กับ C) → ช่วงเสี่ยง = Tp
ช่วงเสี่ยงลดครึ่ง → เลขชี้กำลังในสูตรเปลี่ยนจาก −2G เป็น −G → ทรูพุตสูงสุดขึ้นจาก 0.184 เป็น 0.368 พอดีเป๊ะ

ตัวเลขที่ต้องท่องให้ได้ (ออกสอบ Q12 แน่นอน)
โพรโตคอลสูตรG ที่ทำให้สูงสุดS สูงสุดคิดเป็น %
Pure ALOHAS = G e−2GG = 0.51/2e = 0.18418.4%
Slotted ALOHAS = G e−GG = 11/e = 0.36836.8%

วิธีจำ: pure = ครึ่งหนึ่งของ slotted ทั้งค่า G และค่า S (0.5 กับ 1, 0.184 กับ 0.368)

กราฟทรูพุต S(G) — จุดสูงสุดอยู่ตรงไหน

เลื่อนสไลเดอร์ G ดูว่าทรูพุตเปลี่ยนไปยังไง สังเกตว่าเมื่อ G เกินจุดสูงสุด ยิ่งยิงมาก ยิ่งได้น้อย เพราะแพ็กเก็ตชนกันเองจนต้องส่งซ้ำวนไปไม่จบ

พิสูจน์จุดสูงสุด (ถ้าข้อสอบให้แสดงวิธี)

Slotted: S = Ge−G → dS/dG = e−G(1 − G) = 0 → G = 1 → S = 1·e−1 = 1/e = 0.368
Pure: S = Ge−2G → dS/dG = e−2G(1 − 2G) = 0 → G = 0.5 → S = 0.5·e−1 = 1/2e = 0.184

13.2.4Carrier Sense Multiple Access (CSMA)

CSMA เป็นวิธีที่นิยมใช้ทั้งในเน็ตเวิร์กแบบสายและเครือข่ายไร้สาย หลักการคือ สเตชันจะตรวจสอบ (Sense) ว่าช่องสัญญาณมีการใช้งานอยู่ (busy) หรือไม่ ก่อนที่จะส่งข้อมูล ทำให้ลดปัญหาการชนกันของเฟรมลงได้มาก

CSMA ใช้วิธีตรวจสอบช่องสัญญาณในลักษณะหนึ่งในสามแบบ:

แบบเมื่อพบว่า idleเมื่อพบว่า busyรูปในตำรา
Nonpersistentส่งเฟรมออกไปทันทีรอ เพื่อกลับมาส่งเฟรมใหม่ภายหลัง (ไม่เฝ้าฟังต่อ)รูปที่ 13.7
p-persistentส่งด้วยความน่าจะเป็น p · ด้วยความน่าจะเป็น 1−p จะเลื่อนการส่งไปสล็อตถัดไป (ตรวจสอบทุกครั้งที่จะส่งเฟรม)รอแล้วตรวจใหม่ทุกสล็อตรูปที่ 13.8
1-persistentส่งทันที (คือ p-persistent ที่ p = 1)เฝ้าฟังต่อจนกว่าจะ idle แล้วส่งทันทีรูปที่ 13.9 / 13.14

1-persistent CSMA เป็นการทำงานที่ง่ายที่สุดของ p-persistent CSMA คือให้ p = 1 เพื่อเน้นความสำคัญของการส่งเฟรม ดังนั้นเฟรมจะถูกส่งทันทีที่ช่องสัญญาณไม่มีการใช้งาน

อ่านรูปที่ 13.7–13.9 ของตำรา — ต่างกันแค่ "ตอนสายไม่ว่าง" ล้วน ๆ

ทั้งสามรูปใช้แกนเดียวกันหมด: แถบฟ้า = ช่องสัญญาณไม่ว่าง · ถัดจากแถบฟ้าไป = ช่องสัญญาณว่าง · ลูกศรชี้ลง = จังหวะที่สเตชันตรวจสอบช่องสัญญาณ ดูแค่สองอย่างคือ ลูกศรถี่แค่ไหน และ เริ่มส่งตรงจุดไหน ก็แยกออกทั้งสามแบบ · ภาพเคลื่อนไหวข้างบนให้กดสลับดูทีละแบบว่าใครได้ส่งเมื่อไร ส่วนสามรูปข้างล่างนี้คือรูปต้นฉบับจากตำราที่โจทย์อ้างถึง

ไดอะแกรมเวลาของ non-persistent CSMA แถบสีฟ้าคือช่วงที่ช่องสัญญาณไม่ว่าง มีลูกศรตรวจสอบช่องสัญญาณสามครั้งวางห่างกัน โดยมีคำว่ารอคั่นระหว่างครั้ง ลูกศรครั้งที่สามตกอยู่ในช่วงที่ช่องสัญญาณว่างไปแล้วนานพอควรจึงเริ่มทำการส่ง
รูปที่ 13.7 จากตำรา — การทำงานของ non-persistent CSMA (ตรวจแล้วไม่ว่าง → เลิกฟังทันที แล้วสุ่มเวลา "รอ" ไปก่อน → ค่อยกลับมาตรวจใหม่ · สังเกตว่าลูกศรอันสุดท้ายมาถึงหลังจากสายว่างไปแล้วพักใหญ่ — ช่องว่างตรงนั้นคือแบนด์วิดท์ที่ถูกปล่อยทิ้งเปล่า ซึ่งเป็นราคาที่ non-persistent จ่ายเพื่อแลกกับการชนน้อยลง)
ไดอะแกรมเวลาของ p-persistent CSMA มีลูกศรตรวจสอบช่องสัญญาณจำนวนมากเรียงถี่ตลอดช่วงแถบฟ้าที่ช่องสัญญาณไม่ว่าง หลังจากช่องสัญญาณว่างแล้ว เวลาถูกแบ่งเป็นสล็อตเวลาสามสล็อต สองสล็อตแรกกำกับว่าเป็นความน่าจะเป็นที่ยังไม่สามารถส่งได้ แล้วจึงเริ่มทำการส่งที่สล็อตที่สาม
รูปที่ 13.8 จากตำรา — การทำงานแบบ p-persistent CSMA (เฝ้าฟังตลอดระหว่างสายไม่ว่าง — ลูกศรถี่ยิบ · พอสายว่าง เวลาจะถูกซอยเป็น สล็อตเวลา แต่ละสล็อตส่งด้วยความน่าจะเป็น p · ในรูปนี้สองสล็อตแรกตกอยู่ในกรณี 1−p ที่ป้ายเขียนว่า "ความน่าจะเป็นที่ยังไม่สามารถส่งได้" จึงเลื่อนไปเรื่อย ๆ แล้วเพิ่งได้ส่งที่สล็อตที่สาม)
ไดอะแกรมเวลาของ 1-persistent CSMA มีลูกศรตรวจสอบช่องสัญญาณเรียงถี่ตลอดช่วงแถบฟ้าที่ช่องสัญญาณไม่ว่าง และลูกศรอันสุดท้ายอยู่ตรงขอบพอดีที่ช่องสัญญาณเปลี่ยนเป็นว่าง กำกับว่าตรวจสอบช่องสัญญาณและเริ่มทำการส่งทันที
รูปที่ 13.9 จากตำรา — การทำงานแบบ 1-persistent (เฝ้าฟังถี่เหมือน p-persistent แต่ไม่มีสล็อตให้ลุ้นเลย — ลูกศรสุดท้ายอยู่ตรงขอบที่สายเปลี่ยนจากไม่ว่างเป็นว่างพอดี แล้วส่งทันที เพราะ p = 1)
จุดที่คนพลาดบ่อย — 1-persistent คือแบบที่ "ชนแน่นอน" ถ้ามีคนรอหลายคน

ลองคิดต่อจากรูปที่ 13.9: ถ้ามีสองสเตชันขึ้นไปเฝ้ารออยู่พร้อมกัน ทุกตัวจะเห็นขอบ "ว่าง" ที่วินาทีเดียวกันเป๊ะ แล้วยิงออกไปพร้อมกันหมด → ชนกันแน่นอน 100% ไม่ใช่แค่ "มีโอกาสชน"
นี่คือเหตุผลทั้งหมดที่ต้องมี p-persistent (รูปที่ 13.8) มาคั่น — ให้แต่ละตัวโยนเหรียญด้วยความน่าจะเป็น p ก่อนกระโดดเข้าไป ทุกตัวจึงไม่เข้าพร้อมกัน · และเป็นเหตุผลที่ในกราฟรูปที่ 13.10 กับ 13.13 เส้น 1-persistent CSMA พีคต่ำกว่า nonpersistent CSMA อย่างชัดเจน

ภาพวาดลายเส้นการ์ตูนสองช่อง ช่องซ้ายเป็นผู้หญิงที่ถือช่อดอกไม้และมีกล่องข้อความชวนคุยเต็มไปหมดรอบตัว เช่น ไปเที่ยวกัน ไปมั้ย ไปวันนี้ ช่องขวาเป็นผู้หญิงอีกคนนั่งหน้าคอมพิวเตอร์ท่ามกลางกองซองจดหมาย และพูดว่าไม่ว่างไง ไปเช็กก็ยังไม่เสร็จ ด้านล่างเขียนว่า 1-Presistance CSMA
รูปที่ 13.14 จากตำรา — 1-persistence (ภาพวาดของนักศึกษาที่ตำราเอามาลงปิดท้ายบท: ฝั่งซ้ายคือสเตชันแบบ 1-persistent ที่ยิงข้อความรัวไม่หยุด พอปลายทางว่างเมื่อไรก็ทะลักเข้าไปทันที ส่วนฝั่งขวาคือช่องสัญญาณที่ไม่ว่าง (busy) และมีคิวค้างเต็มไปหมด — เป็นภาพจำของคำว่า persistent ได้ดีที่สุดในบทนี้)

ทรูพุตของ CSMA แต่ละแบบ

S = G e−aGG(1 + 2a) + e−aG สมการ 13.6 — Unslotted nonpersistent CSMA
S = aG e−aG1 − e−aG + a สมการ 13.7 — Slotted nonpersistent CSMA
S = G[1 + G + aG(1 + G + aG/2)] e−G(1+2a)G(1 + 2a) − (1 − e−aG) + (1 + aG) e−G(1+a) สมการ 13.8 — Unslotted 1-persistent CSMA
S = G e−G(1+a) [1 + a − e−aG](1 + a)(1 − e−aG) + a e−G(1+a) สมการ 13.9 — Slotted 1-persistent CSMA
สัญลักษณ์ความหมาย
Snormalized throughput
Gnormalized offered traffic load
aa = τ / Tp
τmaximum propagation delay
Tppacket transmission time

ค่า a คืออะไรกันแน่ — มันคืออัตราส่วน "เวลาที่สัญญาณใช้เดินทาง" ต่อ "เวลาที่ใช้ยิงเฟรมขึ้นสาย"
ตัวอย่าง: LAN ยาว 2 km, ความเร็วสัญญาณ 2×108 m/s → τ = 2000 / (2×108) = 10 µs
เฟรม 1000 บิต ที่ 10 Mbps → Tp = 1000 / (10×106) = 100 µs
⇒ a = 10/100 = 0.1 · a ยิ่งเล็ก CSMA ยิ่งทำงานได้ดี เพราะสายสั้น/เฟรมยาว ทุกคน "รู้ทัน" กันเร็ว ถ้า a ใหญ่มาก ๆ CSMA จะเสื่อมลงจนใกล้เคียง ALOHA

การพัฒนาของ CSMA ทำให้การใช้ช่องสัญญาณร่วมกันมีประสิทธิภาพเพิ่มขึ้น เห็นได้จากการเปรียบเทียบทรูพุตของ nonpersistent, p-persistent, 1-persistent CSMA เทียบกับ Pure ALOHA และ Slotted ALOHA:

กราฟเปรียบเทียบทรูพุต S เทียบกับ G ของ CSMA แบบต่าง ๆ กับ Pure/Slotted ALOHA
รูปที่ 13.10 จากตำรา — เปรียบเทียบประสิทธิภาพของ ALOHA และ CSMA · สังเกตว่า Pure ALOHA อยู่ล่างสุด (พีค 0.184) Slotted ALOHA อยู่ถัดขึ้นมา (พีค 0.368) ส่วน CSMA ที่ค่า p ยิ่งเล็ก (0.01-persistent) ยิ่งได้ทรูพุตเข้าใกล้ 1
อ่านกราฟรูปที่ 13.10 ให้เป็น

ค่า p ยิ่งเล็ก ทรูพุตยิ่งสูง เพราะทุกคนสุภาพขึ้น (โอกาสกระโดดเข้าไปพร้อมกันน้อยลง) แต่แลกมาด้วย delay ที่สูงขึ้น เพราะต้องรอหลายสล็อตกว่าจะได้ส่ง — นี่คือ trade-off คลาสสิกของ p-persistent ที่หนังสือไม่ได้เขียนตรง ๆ แต่ดูออกจากกราฟ

13.2.5CSMA with Collision Detection (CSMA/CD)

CSMA/CD เป็นการพัฒนาต่อยอดจาก CSMA โดยเพิ่มการตรวจจับการชนกันของสัญญาณ (Collision Detection) เข้าไป

ปัญหาของ CSMA ธรรมดาคือ — เฟรมจะถูกส่งจนสิ้นสุดความยาวทั้งหมด แม้ว่าสเตชันต้นทางจะพบว่าเฟรมนั้นเกิดการชนกันแล้ว (เสียเวลาสายเปล่า ๆ) การเพิ่ม Collision Detection ทำให้:

  1. สเตชันหยุดส่งส่วนที่เหลือของเฟรมทันทีที่พบว่ามีการชนกัน
  2. สเตชันส่งสัญญาณขนาดเล็กไปในช่องสัญญาณแทน เรียกว่า jamming signal เพื่อแจ้งให้ทุกสเตชันทราบว่าเกิดการชนกันขึ้น
  3. สเตชันภาคส่งเข้าสู่กระบวนการส่งซ้ำ (re-transmission) โดยใช้ Exponential Backoff Algorithm

ทำไม CSMA/CD ยังชนได้ ทั้ง ๆ ที่ฟังก่อนส่ง?

เพราะสัญญาณใช้เวลาเดินทาง พิจารณาตามรูปที่ 13.12 ของหนังสือ:

  • สเตชัน A เริ่มส่งข้อมูลของตนออกไป
  • สเตชัน B เริ่มส่งหลังจาก A ส่งไปเพียงเล็กน้อย (Δt) — คือก่อนที่เฟรมของ A จะมาถึงยัง B
  • ดังนั้นแม้ B จะตรวจสอบ (sense) ว่ามีสเตชันอื่นส่งอยู่หรือไม่ ก็จะพบว่าช่องสัญญาณยังว่างอยู่ เพราะสัญญาณจาก A ยังมาไม่ถึงจุดที่ B ตรวจสอบ
  • B จึงเข้าใจว่าเริ่มส่งได้ → พอเฟรมของ A มาถึง B ก็พบว่าเกิดการชนกัน → B หยุดส่งส่วนที่เหลือ พร้อมส่ง jamming signal

ภาพเคลื่อนไหวข้างบนเดินตามเวลาทีละสเต็ป (เห็นช่วง Δt ชัด ๆ) ส่วนรูปจากตำราข้างล่างสรุปเรื่องเดียวกันเป็นภาพนิ่ง 4 จังหวะ — ไล่คู่กันจะเห็นว่าตรงกันทุกจังหวะ

ภาพสี่ขั้นตอนของ CSMA/CD: A ส่ง, B ส่ง, สัญญาณชนกลางสาย, ทั้งคู่ส่ง jamming signal
รูปที่ 13.12 จากตำรา — การส่งข้อมูลของ CSMA/CD · จากบนลงล่าง: A เริ่มส่ง → B เริ่มส่ง (ยังไม่รู้ว่ามี A) → สัญญาณชนกันกลางสาย → ทั้งคู่ส่ง Jamming signal ออกไปทั้งเส้น

ทรูพุตของ CSMA/CD

S = G e−aGG e−aG + bG(1 − e−aG) + 2aG(1 − e−aG) + (2 − e−aG) สมการ 13.10 — Unslotted nonpersistent CSMA/CD
S = aG e−aGaG e−aG + b(1 − e−aG − aG e−aG) + a(2 − e−aG − aG e−aG) สมการ 13.11 — Slotted nonpersistent CSMA/CD (ต้นฉบับพิมพ์หัวสมการซ้ำกับ 13.10 แต่ประโยคนำหน้าระบุว่าเป็นคู่ "unslotted persistent และ slotted nonpersistent")

โดยที่ b = jamming signal length (ความยาวของสัญญาณ jam) ส่วน a และ G ความหมายเดิม การเพิ่มส่วนตรวจจับการชนกัน (collision detection) ทำให้ทรูพุตของระบบสูงขึ้น ตามรูปที่ 13.13 ด้านล่าง

กราฟเปรียบเทียบทรูพุต S บนแกนตั้งกับ offered traffic load G บนแกนนอนแบบสเกลลอการิทึมจาก 0.1 ถึง 1000 กำหนด a เท่ากับ 0.01 และ b เท่ากับ a มีเส้นโค้งห้าเส้นเรียงจากต่ำไปสูงคือ Pure ALOHA, Slotted ALOHA, 1-persistent CSMA, Nonpersistent CSMA และ Nonpersistent CSMA/CD ซึ่งขึ้นสูงสุดใกล้ 0.95
รูปที่ 13.13 จากตำรา — เปรียบเทียบทรูพุตของการเข้าใช้ช่องสัญญาณแบบสุ่มแบบต่าง ๆ (กราฟนี้คือรูปที่ 13.10 ที่เติมเส้น CSMA/CD เข้าไปอีกเส้น · เงื่อนไขมุมซ้ายบนคือ a = 0.01 และ b = a · แกนนอนเป็นสเกลลอการิทึม 0.1 → 1000 ไม่ใช่สเกลปกติ อย่าอ่านตำแหน่งพีคผิด)
เส้นในรูปที่ 13.13 (ล่าง → บน)ทรูพุตสูงสุดที่อ่านได้จากกราฟทำไมถึงสูงขึ้น
Pure ALOHA≈ 0.18 (ตรงกับ 1/2e = 0.184 ที่ G = 0.5)ยิงมั่ว ช่วงเสี่ยง 2Tp
Slotted ALOHA≈ 0.37 (ตรงกับ 1/e = 0.368 ที่ G = 1)บังคับเริ่มที่ขอบสล็อต → ช่วงเสี่ยงเหลือ Tp
1-persistent CSMA≈ 0.53ฟังก่อนส่ง — แต่ทุกคนกระโดดเข้าพร้อมกันตอนสายว่าง จึงยังชนเยอะ
Nonpersistent CSMA≈ 0.82ฟังก่อนส่ง + เจอ busy แล้วถอยไปสุ่มเวลาใหม่ ไม่แย่งกันเข้าพร้อมกัน
Nonpersistent CSMA/CD≈ 0.95เพิ่ม collision detection — ชนแล้วตัดจบทันที ไม่ต้องเปลืองสายส่งเฟรมเสียจนจบ

นี่คือ "เส้นเรื่อง" ทั้งบทในกราฟเดียว — ทุกก้าวที่ขยับขึ้นมาคือการลดเวลาที่สายถูกใช้ไปกับเฟรมที่ชนแล้ว ทั้งสิ้น

ทำไม CSMA/CD ใช้กับไร้สาย (WLAN) ไม่ได้

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

① ต้นทุนของฮาร์ดแวร์

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

② ไม่มีใครรู้สภาพช่องของคนอื่น

ในเครือข่ายไร้สายไม่สามารถรับประกันได้ว่าทุกโนดจะรับทราบถึงการใช้ช่องสัญญาณของโนดทุกโนด — แม้จะพบว่าช่องสัญญาณในด้านส่งว่างอยู่ พร้อมที่จะส่ง ก็มิได้หมายความว่าช่องสัญญาณในทางด้านรับจะว่างเสมอ

ส่วนขยาย (นอกต้นฉบับ)

ปัญหาข้อ ② มีชื่อเรียกว่า hidden node problem และเป็นเหตุผลที่ Wi-Fi (802.11) ใช้ CSMA/CA (Collision Avoidance) แทน — คือหลีกเลี่ยงไม่ให้ชนตั้งแต่แรกด้วยการรอสุ่ม + ใช้ ACK/RTS-CTS แทนที่จะตรวจจับตอนชนแล้ว

Binary Exponential Backoff — เจาะละเอียด (ข้อสอบ Q12)

เมื่อชนแล้ว จะส่งใหม่เมื่อไร? ถ้าทุกคนส่งใหม่ทันทีพร้อมกัน ก็จะชนซ้ำไปเรื่อย ๆ ไม่จบ จึงต้องใช้ exponential backoff เพื่อหลีกเลี่ยงการชนกันอีกครั้งของสเตชันที่ต้องการส่งเฟรมใหม่

กติกาตามหนังสือ (รูปที่ 13.11):

  1. สเตชันที่ส่งเฟรมไม่สำเร็จ ถ้าต้องการส่งใหม่ ต้องสุ่มเวลาหน่วงเป็น C เท่าของเวลาหน่วงของการแพร่กระจาย (tprop หรือ Tp) หรือของค่าเฉลี่ยเวลาหน่วงการส่งเฟรม (Tfr)
  2. ค่า C เป็นค่าสุ่ม ในช่วง 0 ถึง 2K − 1 โดย K = จำนวนรอบที่สเตชันพยายามส่ง
  3. ในอีเทอร์เน็ต สเตชันจะพยายามส่งเป็นจำนวน 16 ครั้ง — หากยังส่งไม่ได้ เฟรมนั้นจะถูกกำจัดทิ้ง (discard) และแจ้งความผิดพลาด (error) ขึ้นไปเลเยอร์บน
TB = C × Tp เวลาที่ใช้รอหลังตรวจพบ Collision · C สุ่มจาก {0, 1, 2, …, 2K − 1} · Tp = เวลาหน่วง propagation สูงสุด
ผังงานในหนังสือ (รูปที่ 13.4 และ 13.11) เขียนไว้ว่า TB = C × Tp หรือ C × Tfr — จะใช้ Tfr (เวลาส่งเฟรม) แทนก็ได้ถ้าโจทย์ให้มา · ในอีเทอร์เน็ตจริงหน่วยนี้คือ slot time = 51.2 µs ที่ 10 Mbps
รูปแบบคำตอบที่ข้อสอบ Q12 ต้องการ (ตามเฉลยใหม่)

ข้อ a — ช่วงสุ่มของโหนด A ในแต่ละรอบ ใช้สูตรเดียวคือ 0 ≤ C ≤ 2K − 1

รอบที่ชนK (หลังเพิ่ม)ช่วงสุ่มของ C
ชนครั้งที่ 1K = 1C ∈ {0, 1}
ชนครั้งที่ 2K = 2C ∈ {0, 1, 2, 3}
ชนครั้งที่ 3K = 3C ∈ {0, 1, …, 7}
ชนครั้งที่ 4K = 4C ∈ {0, 1, …, 15}

ข้อ b — A กับ B ชนกัน 4 รอบ แล้ว C เข้ามาร่วมในรอบที่ 4 (ตัวเลข C ตามเฉลย)

รอบชนโหนดที่ชนกันK (หลังเพิ่ม)ช่วงสุ่ม {0,…,2K−1}ค่า C ที่สุ่มได้TB = C × Tpผลลัพธ์
1A, BKA=1, KB=1{0,1}CA=1, CB=11Tp, 1Tpเท่ากัน → ชนซ้ำ
2A, BKA=2, KB=2{0,1,2,3}CA=3, CB=33Tp, 3Tpเท่ากัน → ชนซ้ำ
3A, BKA=3, KB=3{0,…,7}CA=6, CB=66Tp, 6Tpเท่ากัน → ชนซ้ำ
4A, B, CKA=4, KB=4, KC=1 (ชนครั้งแรกของ C)A, B: {0,…,15}
C: {0,1}		CA=11, CB=4, CC=111Tp, 4Tp, 1Tpค่าไม่ซ้ำกันเลย → ไม่ชนอีก

จุดที่ต้องเขียนให้ครบ 3 อย่างต่อแถว — (1) ค่า K ของแต่ละโหนด (2) ช่วงสุ่ม {0,…,2K−1} (3) TB = C × Tp พร้อมสรุปว่าซ้ำกันหรือไม่ · โหนดที่เพิ่งเข้ามาชนครั้งแรกเริ่มที่ K = 1 เสมอ ไม่ใช่ K เท่ากับคนอื่น — นี่คือกับดักหลักของข้อนี้

ตารางที่ข้อสอบ Q12 ถามตรง ๆ
รอบที่ (K)ช่วงที่สุ่ม 0 … 2K−1เซตของค่า Cมีกี่ค่าโอกาสที่สองสเตชันจะได้ค่าเท่ากัน
10 … 21−1 = 1{0, 1}21/2 = 50%
20 … 22−1 = 3{0, 1, 2, 3}41/4 = 25%
30 … 23−1 = 7{0, 1, …, 7}81/8 = 12.5%
40 … 24−1 = 15{0, 1, …, 15}161/16 = 6.25%
……………
16ชนครบ 16 ครั้ง → ยกเลิก ทิ้งเฟรม + แจ้ง error ขึ้นเลเยอร์บน (ในผังงานคือเงื่อนไข K > 15)

แล้วเวลารอจริง = TB = C × Tp — ห้ามตอบแค่ตัวเลข C เฉย ๆ ต้องคูณหน่วยเวลา (Tp หรือ slot time) ด้วยเสมอ

ภาพเคลื่อนไหวข้างบนคือการจำลองสุ่มจริง (กดสุ่มใหม่ได้) ส่วนรูปข้างล่างคือผังงานต้นฉบับที่บอกว่ากล่องไหนอยู่ตรงไหน — เวลาเขียนตอบข้อสอบให้ยึดตามผังงาน

ผังงาน CSMA/CD พร้อมกล่อง Exponential Back-off ที่สุ่มค่า C ระหว่าง 0 ถึง 2 ยกกำลัง K ลบ 1 และเงื่อนไข K มากกว่า 15
รูปที่ 13.11 จากตำรา — ผังงานการทำงานของ CSMA/CD · สังเกตกล่องเขียว TB = C × Tp หรือ C × Tfr กับกล่อง "สุ่มค่า C ระหว่าง 0 ถึง 2K − 1" และเงื่อนไข K > 15 → ยกเลิก
จุดที่คนพลาดบ่อย
  • ขอบเขตบนคือ 2K − 1 ไม่ใช่ 2K — เนื้อความในหนังสือพิมพ์เป็น 0 ≤ c ≤ 2K แต่ผังงานรูปที่ 13.11 เขียนชัดว่า "สุ่มค่า C ระหว่าง 0 ถึง 2K − 1" ซึ่งตรงกับมาตรฐาน IEEE 802.3 และตรงกับที่ข้อสอบใช้ — ให้ยึด 2K − 1
  • รอบแรกคือ K = 1 ไม่ใช่ K = 0 — ในผังงานเริ่มที่ K = 0 แต่จะเพิ่ม K ก่อนเข้ากล่อง backoff เสมอ ดังนั้นการชนครั้งแรกทำให้ K = 1 → สุ่มจาก {0, 1}
  • C = 0 แปลว่ารอ 0 สล็อต คือส่งทันที ไม่ใช่ "ไม่ส่ง" — และถ้าสองสเตชันได้ 0 เหมือนกันก็ชนซ้ำทันที
  • 16 ครั้งแล้วทิ้ง ไม่ใช่ "พยายามไปเรื่อย ๆ"

ตัวอย่างคำนวณแบบข้อสอบ — Ethernet 10 Mbps มี slot time = 51.2 µs สเตชันชนไปแล้ว 3 ครั้ง (K = 3) และสุ่มได้ C = 5
→ C สุ่มจาก {0, 1, …, 7} ✓ (5 อยู่ในช่วง)
→ เวลารอ TB = 5 × 51.2 µs = 256 µs
ถ้าโจทย์ให้ K = 4 และ C = 12 → TB = 12 × 51.2 = 614.4 µs · ถ้าโจทย์ให้ C = 20 ที่ K = 4 ให้ตอบว่าเป็นไปไม่ได้ เพราะเกิน 15

ส่วนขยาย (นอกต้นฉบับ)

มาตรฐาน IEEE 802.3 จริง ๆ หยุดขยายช่วงสุ่มที่ K = 10 (เรียกว่า truncated binary exponential backoff) คือรอบที่ 11–16 ยังคงสุ่มจาก {0 … 210−1} = {0 … 1023} เท่าเดิม แล้วจึงยกเลิกเมื่อครบ 16 ครั้ง — หนังสือเล่มนี้ไม่ได้กล่าวถึงส่วนนี้ ถ้าข้อสอบไม่บอกอะไรเพิ่ม ให้ตอบตามสูตร 2K − 1 ตรง ๆ

Collision Window — ทำไมเฟรมต้องยาวอย่างน้อย 2τ (ข้อสอบ Q13)

ต่อยอดจากสถานการณ์ในรูปที่ 13.12 ให้คิดกรณีเลวร้ายที่สุด คือสองสเตชันอยู่ที่ปลายสุดคนละข้างของสาย ระยะห่างทำให้ propagation delay สูงสุดเท่ากับ τ:

เวลาเกิดอะไรขึ้น
t = 0A ตรวจสาย พบว่าว่าง → เริ่มส่ง
t = τ − εสัญญาณของ A เกือบถึง B · B ตรวจสาย ยังเห็นว่าว่าง → B เริ่มส่ง (นี่คือ Δt ในหนังสือ)
t = τสัญญาณ A ถึง B → B ตรวจพบการชน → B หยุดส่ง + ส่ง jam signal
t = 2τสัญญาณของ B (และ jam) เดินทางกลับถึง A → A เพิ่งจะตรวจพบการชน

สรุปได้ว่า A ต้อง "ยังส่งอยู่" ณ เวลา 2τ ถึงจะรู้ตัวว่าเฟรมของตนชน — ถ้า A ส่งเฟรมจบไปก่อนหน้านั้น A จะเข้าใจผิดว่าส่งสำเร็จ ทั้ง ๆ ที่เฟรมพังไปแล้ว และจะไม่มีการส่งซ้ำเกิดขึ้นเลย

Tfr ≥ 2τ เงื่อนไขของ collision window · Tfr = เวลาที่ใช้ส่งเฟรม (transmission time) · τ = propagation delay สูงสุดของเน็ตเวิร์ก

แปลงเป็นขนาดเฟรมขั้นต่ำ (คูณด้วยอัตราการส่ง R):

Lmin = 2τ × R ขนาดเฟรมขั้นต่ำ (บิต) · 2τ ยังมีชื่อเรียกว่า slot time ของ Ethernet

ตัวอย่าง ① — LAN สั้น

สาย 2 km, v = 2×108 m/s, R = 10 Mbps
τ = 2000 / (2×108) = 10 µs
2τ = 20 µs
Lmin = 20×10−6 × 10×106 = 200 บิต = 25 ไบต์

ตัวอย่าง ② — ที่มาของเลข 64 ไบต์

มาตรฐาน Ethernet 10 Mbps กำหนด slot time = 512 bit times = 51.2 µs (คือ 2τ ที่เผื่อระยะทางสูงสุด 2500 m + repeater)
Lmin = 51.2×10−6 × 10×106 = 512 บิต = 64 ไบต์
นี่คือเหตุผลที่เฟรม Ethernet ขั้นต่ำ = 64 ไบต์ และต้องมี Padding เมื่อข้อมูลสั้นกว่านั้น

ไทม์ไลน์การชนแบบมีตัวเลขจริง (รูปแบบที่เฉลย Q13 ต้องการ)

โจทย์: R = 10 Mbps · d = 800 m · S = 2×108 m/s · เฟรมยาว L = 50,000 ไบต์ = 400,000 บิต · A อยู่ที่ x = 0 และ C อยู่ที่ x = 800 m

ค่าวิธีคิดผลลัพธ์
dtransL / R = 400,000 / (10×106)0.04 s
dprop (= τ)d / S = 800 / (2×108)4 µs
เวลาเหตุการณ์
t = 0 µsA เริ่มส่งข้อมูล
t = 3 µsC ตรวจสาย พบว่าว่าง (สัญญาณ A ยังมาไม่ถึง) จึงเริ่มส่งข้อมูล
t = 3.5 µsเกิดการชนกัน (Collision) ที่ระยะ x = 700 m จาก A
t = 4.0 µsสัญญาณของ A ถึง C → C รับรู้การชน
t = 7.0 µsสัญญาณของ C ถึง A → A รับรู้การชน

Collision window = 2 × tprop = 8 µs · จุดที่ต้องเขียนให้ครบคือ จุดชนกลางสาย (x = 700 m ที่ t = 3.5 µs) ไม่ใช่แค่บอกว่า "ชนแล้ว" — คิดจาก: A วิ่งมาได้ 3.5 µs × 2×108 = 700 m ขณะที่ C วิ่งมาได้ 0.5 µs × 2×108 = 100 m รวมกันพอดี 800 m
ในโจทย์นี้ dtrans = 0.04 s = 40,000 µs ซึ่งยาวกว่า collision window 8 µs อยู่มหาศาล ทั้ง A และ C จึง "ยังส่งอยู่" ตอนรู้ตัว → ตรวจจับการชนได้ทันแน่นอน แล้วเข้า backoff ตามผังงานรูปที่ 13.11

ส่วนขยาย (นอกต้นฉบับ)

หนังสือบทที่ 13 อธิบายกลไกการชนแบบ Δt ไว้ครบ (รูปที่ 13.12) แต่ไม่ได้เขียนสูตร Tfr ≥ 2τ หรือเลข 64 ไบต์ตรง ๆ — ส่วนนั้นมาจากมาตรฐาน IEEE 802.3 ซึ่งจะไปเจออีกทีใน บทที่ 14 (Ethernet MAC Frame) ตรงฟิลด์ Pad และค่าขั้นต่ำ 46 ไบต์ของ Data

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

อย่าตอบว่า "เฟรมต้องยาวกว่า τ" — ต้องเป็น 2τ เพราะสัญญาณต้องเดินทางไป-กลับ (ไปให้ถึงคนที่ไกลสุด แล้วสัญญาณชน/jam ต้องเดินทางกลับมาถึงเรา) ถ้าตอบ τ จะได้เฟรมขั้นต่ำแค่ครึ่งเดียว = 32 ไบต์ ซึ่งผิด

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

ระบบ Pure ALOHA มี offered load G = 0.5 ทรูพุต normalized (S) เป็นเท่าไร?
แทนในสมการ 13.4: S = G·e−2G = 0.5 × e−2(0.5) = 0.5 × e−1 = 0.5/2.718 = 0.184 ซึ่งเป็นค่าสูงสุดของ Pure ALOHA พอดี (18.4%) · ส่วน 0.368 คือค่าสูงสุดของ Slotted ALOHA ที่ G = 1 และ 0.135 คือค่าของ Pure ALOHA ที่ G = 1
สเตชัน Ethernet ชนกันเป็นครั้งที่ 4 (K = 4) ตามอัลกอริทึม Binary Exponential Backoff จะสุ่มค่า c จากเซตใด?
ช่วงคือ 0 ถึง 2K − 1 ดังนั้น K = 4 → 0 ถึง 24 − 1 = 0 ถึง 15 รวม 16 ค่า · เริ่มที่ 0 เสมอ (c = 0 หมายถึงส่งทันทีไม่ต้องรอ) และจบที่ 2K−1 ไม่ใช่ 2K · จากนั้นเวลารอจริง TB = C × Tp (ในอีเทอร์เน็ตคือ c × slot time)
การเปลี่ยนจาก Pure ALOHA เป็น Slotted ALOHA ทำให้ทรูพุตสูงสุดเพิ่มเป็นสองเท่า เพราะเหตุใด?
Slotted ALOHA บังคับให้ทุกสเตชันเริ่มส่งที่ขอบสล็อตเท่านั้น กรณี "เริ่มก่อนนิดหน่อยแล้วท้ายเฟรมไปทับหัวเฟรมคนอื่น" จึงหายไป เหลือแค่กรณีเลือกสล็อตเดียวกัน → ช่วงเสี่ยงลดครึ่งหนึ่ง → เลขชี้กำลังเปลี่ยนจาก −2G เป็น −G → ทรูพุตสูงสุด 0.184 → 0.368 · ข้ออื่นผิดเพราะ ALOHA ไม่ฟังช่องสัญญาณเลย (นั่นคือ CSMA) และไม่มี collision detection (นั่นคือ CSMA/CD)
เหตุใดมาตรฐาน Ethernet จึงต้องกำหนดขนาดเฟรมขั้นต่ำ (ต้องส่งนานอย่างน้อย 2τ)?
กรณีเลวร้ายที่สุด: A เริ่มส่งที่ t = 0 · สเตชันปลายสุดเริ่มส่งที่ t ≈ τ (ก่อนสัญญาณ A จะไปถึง) · สัญญาณชน/jam เดินทางกลับถึง A ที่ t = 2τ ถ้า A ส่งเฟรมจบไปแล้วก่อน 2τ มันจะไม่มีทางรู้ว่าเฟรมชน จึงไม่ส่งซ้ำ ข้อมูลหายเงียบ ๆ · ที่ 10 Mbps ค่า 2τ = 51.2 µs ⇒ 512 บิต = 64 ไบต์
เก็บก่อนออกจากบทนี้
  • FDMA = แบ่งความถี่ · ต้องมี Guard band · ช่องที่ไม่ใช้ถูกทิ้งเปล่า · ไม่ต้องมี coordinator
    TDMA = แบ่งเวลาเป็นสล็อต ใช้แบนด์วิดท์เต็ม · ไม่ต้องมี Guard band · แต่ต้อง synchronize · จองหลายสล็อตเพื่อเพิ่มบิตเรทได้
  • Pure ALOHA: S = Ge−2G · สูงสุด 0.184 ที่ G = 0.5 (ช่วงเสี่ยง 2Tp)
  • Slotted ALOHA: S = Ge−G · สูงสุด 0.368 = 1/e ที่ G = 1 (ช่วงเสี่ยง Tp)
  • CSMA 3 แบบ: nonpersistent (idle→ส่งทันที, busy→รอแล้วค่อยกลับมาตรวจ) · p-persistent (idle→ส่งด้วยโอกาส p, 1−p เลื่อนไปสล็อตหน้า) · 1-persistent (p = 1)
  • CSMA/CD: ชน → หยุดส่งทันที → ส่ง jamming signal → backoff → ส่งใหม่
  • Backoff: C สุ่มจาก 0 ถึง 2K−1 · เวลารอ TB = C × Tp (หรือ C × Tfr) · ครบ 16 ครั้ง → ทิ้งเฟรม + แจ้ง error · โหนดที่เพิ่งชนครั้งแรกเริ่มที่ K = 1 เสมอ แม้คนอื่นจะชนมาแล้วหลายรอบ
  • Collision window = 2τ → เฟรมต้องยาวอย่างน้อย 2τ → ที่ 10 Mbps ได้ 512 บิต = 64 ไบต์
  • CSMA/CD ใช้กับ WLAN ไม่ได้ เพราะ (1) ตรวจจับการชนแบบไร้สายแพงมาก (2) ช่องว่างฝั่งส่ง ≠ ช่องว่างฝั่งรับ
  • ฝึกต่อที่ Q12 และ Q13