ข้อสอบเก่า · Q12

Binary Exponential Backoff & ALOHA

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

ระดับกลาง ควรใช้ ~15 นาที วาดรูป + ตาราง อ่านคู่กับ บทที่ 13 (CSMA/ALOHA) ต่อกับ Q13 (Collision Window)
ข้อนี้ให้คะแนน "รูปที่ครบองค์ประกอบ" ไม่ใช่เลขที่ถูก

ครึ่ง A เป็นการสุ่ม ดังนั้นอาจารย์ไม่มีทาง "เฉลย" ค่าที่สุ่มได้ — สิ่งที่ตรวจคือ ช่วงที่สุ่มของแต่ละรอบถูกไหม (2K − 1), คูณ Tslot หรือเปล่า และ อธิบายได้ไหมว่าทำไมช่วงต้องขยาย · ครึ่ง B เป็นกราฟที่มีจุดสูงสุด 2 จุดที่ต้องเขียนตัวเลขกำกับ — (0.5, 0.184) และ (1, 0.368) · กราฟที่ไม่มีตัวเลขกำกับ = ได้ครึ่งเดียว

โจทย์จริงจากข้อสอบปีที่แล้ว

Q12

A. จงแสดงการชนกันของสถานี 3 สถานี (A, B, C) โดยไล่ backoff 4–5 รอบ ว่าแต่ละรอบสุ่มจากช่วงไหน และใครส่งได้ก่อน

รอบที่ (K)ช่วงที่สุ่มค่า c
1c ∈ {0, 1}
2c ∈ {0, 1, 2, 3}
3c ∈ {0, …, 7}
4c ∈ {0, …, 15}

โดย 0 ≤ C ≤ 2K − 1 และ TB = C × Tp (Backoff time = เวลาที่ใช้รอหลังตรวจพบ Collision)

B. วาดกราฟ throughput เทียบกับ G (ภาระโหลด) ของ ALOHA

คิดยังไง (แนวคิดใน 30 วินาที)

ครึ่ง A — Backoff คือ "การกระจายตัวออกจากกัน"

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

ท่ามาตรฐาน: ① เขียนช่วงสุ่มของแต่ละรอบ ② สุ่มค่าให้ 3 สถานี ③ คนที่ได้ค่าน้อยที่สุดคนเดียวได้ส่งก่อน ④ ถ้าน้อยสุดซ้ำกัน → ชนซ้ำ → K+1 → ช่วงกว้างเป็น 2 เท่า ⑤ ทุกค่าต้องคูณ Tslot

ครึ่ง B — ALOHA คือ "ยิ่งยิงยิ่งเสีย"

กราฟที่ต้องวาดคือ โค้งคว่ำ 2 เส้น ที่ทั้งคู่ขึ้นแล้วตก · ตกเพราะเมื่อ G สูง แพ็กเก็ตชนกันเองจนไม่มีอะไรรอด

ท่ามาตรฐาน: ① แกน x = G, แกน y = S ② เขียนสูตรทั้งสองข้างกราฟ ③ จุดยอด Pure ที่ (0.5, 0.184) และ Slotted ที่ (1, 0.368) ④ ระบุว่า slotted สูงเป็น 2 เท่าของ pure

สูตร/ขั้นตอนที่ต้องใช้

0 ≤ C ≤ 2K − 1   ·   TB = C × Tp Backoff time = เวลาที่ใช้รอหลังตรวจพบ Collision · C สุ่มจากช่วง {0, 1, …, 2K−1} · K = จำนวนครั้งที่สถานีนั้นชน (ครั้งแรก K = 1) · Tp = ความยาว 1 สล็อต (Ethernet 10 Mbps = 51.2 µs)
Pure ALOHA: S = G·e−2G      Slotted ALOHA: S = G·e−G สมการ 13.4 และ 13.5 · เลข 2 ใน pure มาจากช่วงเสี่ยง 2Tp ส่วน slotted เสี่ยงแค่ Tp
สัญลักษณ์ความหมายหน่วย / ค่า
Kจำนวนครั้งที่สถานีพยายามส่งแล้วชน (เริ่มนับ 1 ที่การชนครั้งแรก)ครั้ง · สูงสุด 16 แล้วทิ้งเฟรม
cค่าสุ่มจำนวนสล็อตที่ต้องรอจำนวนเต็ม 0 ถึง 2K − 1
Tslotความยาว 1 สล็อต · Ethernet 10 Mbps = 51.2 µs (512 bit times)วินาที
TBเวลารอจริงก่อนลองส่งใหม่วินาที
GOffered load — ทราฟฟิกที่ยิงลงสายจริง รวมของที่ส่งซ้ำไม่มีหน่วย (normalized)
SThroughput — สัดส่วนที่รอดถึงปลายทางไม่มีหน่วย · S ≤ G เสมอ

ครึ่ง A — Backoff ของ 3 สถานี

ตาราง 2K − 1 ทุกรอบ (ตารางนี้คือคำตอบครึ่งหนึ่งของข้อ A)

รอบที่ (K)ขอบเขต 2K − 1เซตของค่า cมีกี่ค่าเวลารอต่ำสุด – สูงสุด
(Tslot = 51.2 µs)		โอกาสที่ 2 สถานีได้ค่าเท่ากัน
121 − 1 = 1{0, 1}20 – 51.2 µs1/2 = 50%
222 − 1 = 3{0, 1, 2, 3}40 – 153.6 µs1/4 = 25%
323 − 1 = 7{0, …, 7}80 – 358.4 µs1/8 = 12.5%
424 − 1 = 15{0, …, 15}160 – 768 µs1/16 = 6.25%
525 − 1 = 31{0, …, 31}320 – 1,587.2 µs1/32 = 3.125%
… ชนครบ 16 ครั้ง (K > 15 ในผังงานรูปที่ 13.11) → ทิ้งเฟรม (discard) + แจ้ง error ขึ้นเลเยอร์บน
ส่วนขยาย (นอกต้นฉบับ) — IEEE 802.3 หยุดขยายที่ K = 10

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

จำลองการชนของ A, B, C — กดสุ่มใหม่ได้เรื่อย ๆ

ภาพนี้สุ่มจริงทุกครั้งที่กดปุ่ม — ลองกดหลาย ๆ ที จะเห็นว่าบางครั้งจบใน 2 รอบ บางครั้งลากไป 4–5 รอบ นั่นแหละคือคำตอบที่ถูกต้องของข้อนี้: ไม่มีคำตอบตายตัว มีแต่กติกาที่ตายตัว

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

นี่คือตารางที่ต้องลอกลงกระดาษ · จุดที่กินคะแนนคือ C เพิ่งชนครั้งแรกในรอบที่ 4 ⇒ KC = 1 ไม่ใช่ 4 — K เป็นของใครของมัน ไม่ได้แชร์กัน

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

ทั้งสามค่า 1, 4, 11 ไม่ซ้ำกันเลย ⇒ ไม่เกิดการชนอีก · ลำดับที่ได้ส่งเรียงตามค่า C จากน้อยไปมาก: C (รอ 1Tp) → B (รอ 4Tp) → A (รอ 11Tp) · สังเกตว่า C ที่เพิ่งเข้ามาใหม่กลับได้ส่งก่อน เพราะช่วงสุ่มของมันแคบที่สุด ({0,1}) — นี่คือความไม่เป็นธรรมของ binary exponential backoff (capture effect) ที่ควรเขียนปิดท้ายถ้ามีเวลา

ค่าที่สุ่มได้เป็นเพียงตัวอย่างตามเฉลย — ในกระดาษให้เขียนกำกับว่า "สมมติสุ่มได้ …" แล้วเดินตามกติกาให้ถูกต้อง อาจารย์ตรวจที่ช่วงสุ่ม 0 ≤ C ≤ 2K−1 และการคูณ TB = C × Tp ไม่ใช่ที่ตัวเลขสุ่ม

เห็นเป็นเส้นเวลา — ใครรอเท่าไร ใครได้ส่งก่อน

ครึ่ง B — กราฟ Throughput ของ ALOHA

เลื่อนสไลเดอร์ G เพื่ออ่านค่า S จริงของทั้งสองเส้น · สังเกตว่าหลังจุดยอด ยิ่งยิงยิ่งได้น้อย

รูปที่ได้คะแนนเต็มต้องมีอะไรบ้าง
  1. แกน x เขียนว่า G (offered load / ภาระโหลด) · แกน y เขียนว่า S (throughput)
  2. เส้นโค้งคว่ำ 2 เส้น — เส้นหนึ่งเตี้ยและยอดอยู่ซ้าย (Pure) อีกเส้นสูงกว่าและยอดอยู่ขวา (Slotted)
  3. เขียนสูตรกำกับเส้น: S = Ge−2G และ S = Ge−G
  4. จุดยอดพร้อมตัวเลข: Pure ที่ (G = 0.5, S = 0.184) · Slotted ที่ (G = 1, S = 0.368)
  5. ลากเส้นประจากจุดยอดลงแกน x และไปแกน y ให้เห็นว่าอ่านค่ายังไง
  6. เขียน 18.4% และ 36.8% กำกับ พร้อมประโยคเดียวว่า "slotted ดีกว่า pure 2 เท่า เพราะช่วงเสี่ยงลดจาก 2Tp เหลือ Tp"
พิสูจน์จุดยอด (เขียนได้ถ้าโจทย์ขอ "แสดงวิธี") 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
ทำไม pure ถึงเสี่ยงเป็น 2 เท่า — ประโยคที่ต้องเขียนกำกับกราฟ

Pure ALOHA: เฟรมของ A จะพังถ้ามีใครเริ่มส่งก่อน A ไม่ถึง Tp (ท้ายเขาทับหัวเรา) หรือ เริ่มหลัง A แต่ก่อน A จะส่งจบ (หัวเขาทับท้ายเรา) → ช่วงอันตรายกว้าง 2Tp
Slotted ALOHA: บังคับให้เริ่มส่งได้เฉพาะที่ขอบสล็อต กรณี "เริ่มก่อนนิดหน่อย" จึงหายไปหมด เหลือแค่ "เลือกสล็อตเดียวกัน" → ช่วงอันตรายเหลือ Tp → เลขชี้กำลังจึงเป็น −G ไม่ใช่ −2G

กับดักที่ทำให้เสียคะแนน

กับดักที่ 1 — สุ่มจาก 0 ถึง 2K (ไม่ลบ 1)

คำตอบผิดที่เจอจริง: "รอบที่ 3 สุ่มจาก {0, …, 8}" — ต้องเป็น {0, …, 7} · เนื้อความในหนังสือพิมพ์เป็น 0 ≤ c ≤ 2K แต่ผังงานรูปที่ 13.11 เขียนชัดว่า "สุ่มค่า C ระหว่าง 0 ถึง 2K − 1" ซึ่งตรงกับ IEEE 802.3 และตรงกับที่โจทย์ให้มาในตาราง (รอบ 1 = {0,1} มี 2 ค่า ไม่ใช่ 3 ค่า) · วิธีตรวจเร็ว: จำนวนค่าต้องเป็น 2, 4, 8, 16 — เลขยกกำลังสองสวย ๆ ถ้านับได้ 3, 5, 9 แสดงว่าผิด

กับดักที่ 2 — ตอบเป็นค่า c เฉย ๆ ไม่คูณ Tslot

คำตอบผิดที่เจอจริง: "A ต้องรอ 5" — 5 อะไร? · c คือจำนวนสล็อต ไม่ใช่เวลา · เวลาจริงคือ TB = c × Tslot เช่น 5 × 51.2 µs = 256 µs · โจทย์เขียนสูตร TB = c × Tslot มาให้แล้ว การไม่ใช้มันคือการทิ้งคะแนนฟรี · ถ้าโจทย์ไม่ให้ค่า Tslot ก็ให้ตอบเป็นสัญลักษณ์ 5Tslot ก็ยังได้คะแนน

กับดักที่ 3 — คิดว่า K เป็นของ "ระบบ" ไม่ใช่ของ "สถานี"

ในตารางเฉลย C เข้ามาชนครั้งแรกตอนรอบที่ 4 · คำตอบผิดที่เจอจริงคือเขียนว่า "รอบที่ 4 ทุกคนสุ่มจาก {0, …, 15}" — ผิด · K นับ "จำนวนครั้งที่สถานีนั้น ๆ ชน" ⇒ A กับ B ชนมาแล้ว 4 ครั้ง จึงได้ K = 4 → {0, …, 15} ส่วน C เพิ่งชนครั้งแรก จึงได้ KC = 1 → {0, 1} · วิธีกันพลาด: เขียนคอลัมน์ K แยกเป็น KA, KB, KC ในตารางเสมอ แล้วจะไม่มีทางสับสน · ผลพลอยได้คือได้อธิบาย capture effect ว่าสถานีมาใหม่มักได้เปรียบ

กับดักที่ 4 — เข้าใจว่า C = 0 แปลว่า "ไม่ส่ง"

c = 0 แปลว่า รอ 0 สล็อต คือส่งทันที — และนี่คือสาเหตุที่รอบที่ 1 ชนซ้ำได้ง่ายมาก เพราะช่วงมีแค่ 2 ค่า โอกาสที่สองสถานีได้ 0 เหมือนกัน (หรือ 1 เหมือนกัน) สูงถึง 50% · ในการจำลอง 3 สถานี โอกาสที่รอบที่ 1 จะจบเรียบร้อย (มีคนได้ค่าน้อยสุดคนเดียว) มีแค่ 3/8 = 37.5% เท่านั้น

กับดักที่ 5 — วาดกราฟ ALOHA เป็นเส้นที่ขึ้นเรื่อย ๆ หรืออิ่มตัวแบน

กราฟ ALOHA ต้องเป็นโค้งคว่ำที่ตกลงจนเกือบเป็นศูนย์ ไม่ใช่เส้นที่ขึ้นแล้วแบนราบ (แบบนั้นคือกราฟ throughput ของระบบที่ไม่มีการชน) · เหตุผล: G ที่สูงแปลว่าทุกคนแย่งกันยิง → ชนกันหมด → S ตกลง · ถ้าวาดเส้นแบน อาจารย์รู้ทันทีว่าไม่เข้าใจว่าทำไม ALOHA ถึงมีประสิทธิภาพแค่ 18%

กับดักที่ 6 — สลับสูตร pure กับ slotted

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

เขียนยังไงให้ได้คะแนนเต็ม

ครึ่ง A — เช็กลิสต์

  1. เขียนกติกาก่อน: "ชนครั้งที่ K → สุ่ม C จาก 0 ≤ C ≤ 2K−1 → รอ TB = C × Tp"
  2. ตารางรอบชนครบ 4 รอบ โดยมีคอลัมน์: รอบชน · โหนดที่ชนกัน · K แยกรายสถานี · ช่วงสุ่ม · ค่า C · TB = C×Tp · ผลลัพธ์
  3. เขียน "สมมติสุ่มได้ …" แล้วไล่ทีละรอบว่าใครชนะ ใครชนซ้ำ
  4. ทุกรอบให้เขียน TB = C × Tp ของทุกสถานี (เช่น 11Tp, 4Tp, 1Tp) — ถ้าโจทย์ให้ Tp = 51.2 µs ก็คูณออกมาเป็น µs ด้วย
  5. วาดเส้นเวลา 3 เส้น (A, B, C) แสดงจุดชนที่ t = 0, jam, ช่วงรอ และช่วงส่งสำเร็จ
  6. ปิดท้ายด้วยประโยค: "ช่วงสุ่มขยาย 2 เท่าทุกรอบ ทำให้โอกาสชนซ้ำลดจาก 1/2 → 1/4 → 1/8 → 1/16" และ "รอบที่ 4 ค่า 11, 4, 1 ไม่ซ้ำกันเลย จึงไม่เกิดการชนอีก"
  7. เขียนเงื่อนไขจบ: ชนครบ 16 ครั้ง → ทิ้งเฟรม แจ้ง error

ครึ่ง B — เช็กลิสต์

  1. แกน x = G · แกน y = S (เขียนคำเต็มกำกับด้วย)
  2. สเกลแกน y ถึง 0.4 ก็พอ (ไม่ต้องถึง 1) เพราะยอดสูงสุดแค่ 0.368
  3. เส้น Pure: ยอดที่ (0.5, 0.184)
  4. เส้น Slotted: ยอดที่ (1, 0.368)
  5. เขียนสูตรกำกับแต่ละเส้น
  6. เขียน 18.4% / 36.8% และประโยค "slotted = 2 เท่าของ pure"
  7. ถ้ามีที่ว่าง เขียนวิธีหาจุดยอดด้วยอนุพันธ์ — ได้คะแนนเพิ่มแทบทุกครั้ง

โจทย์ฝึก 5 ข้อ

ไล่จากง่ายไปยากกว่าของจริงเล็กน้อย · ทุกตัวเลขคำนวณจริง ตรวจซ้ำได้

ข้อ 1 ง่าย — Ethernet 10 Mbps มี Tslot = 51.2 µs
(ก) สถานีชนไปแล้ว 3 ครั้ง และสุ่มได้ c = 5 ต้องรอนานเท่าไร
(ข) สถานีชนไปแล้ว 4 ครั้ง และสุ่มได้ c = 12 ต้องรอนานเท่าไร
(ค) ถ้ามีคนตอบว่า "K = 4 สุ่มได้ c = 20" ให้วิจารณ์

เฉลยข้อ 1

(ก) K = 3 → ช่วงสุ่มคือ {0, 1, …, 2³−1} = {0, …, 7} · c = 5 อยู่ในช่วง ✓

TB = 5 × 51.2 µs = 256 µs = 0.256 ms

(ข) K = 4 → ช่วง {0, …, 15} · c = 12 อยู่ในช่วง ✓

TB = 12 × 51.2 µs = 614.4 µs = 0.6144 ms

(ค) K = 4 ให้ช่วงสุ่ม {0, …, 15} ซึ่งสูงสุดคือ 15 · c = 20 จึงเป็นไปไม่ได้ — ต้องชนอย่างน้อย K = 5 ({0, …, 31}) ถึงจะมีโอกาสสุ่มได้ 20 · นี่คือคำถามที่ข้อสอบชอบใช้ดักว่าเข้าใจขอบเขต 2K − 1 จริงหรือแค่ท่องสูตร

ข้อ 2 ง่าย–กลาง — สถานี 2 ตัวชนกัน
(ก) เขียนช่วงสุ่มของรอบที่ 1 ถึง 6 พร้อมจำนวนค่าในแต่ละรอบ
(ข) โอกาสที่ทั้งสองจะสุ่มได้ค่าเท่ากัน (ชนซ้ำ) ในแต่ละรอบเป็นเท่าใด
(ค) ถ้าชนต่อเนื่องจนถึงรอบที่ 16 จะเกิดอะไรขึ้น และเวลารอสูงสุดในรอบที่ 10 เป็นเท่าไร (Tslot = 51.2 µs)

เฉลยข้อ 2

(ก) และ (ข)

รอบ Kช่วง {0 … 2K−1}จำนวนค่า 2KP(ค่าเท่ากัน) = 1/2K
1{0, 1}21/2 = 50%
2{0 … 3}41/4 = 25%
3{0 … 7}81/8 = 12.5%
4{0 … 15}161/16 = 6.25%
5{0 … 31}321/32 = 3.125%
6{0 … 63}641/64 ≈ 1.56%

ที่มาของ 1/2K: สถานีแรกสุ่มได้อะไรก็ได้ (ไม่สำคัญ) สถานีที่สองต้องสุ่มได้ค่าเดียวกันพอดี ซึ่งมีโอกาส 1 ใน 2K

(ค) ชนครบ 16 ครั้ง → สถานีทิ้งเฟรมนั้น (discard) และแจ้ง error ขึ้นไปเลเยอร์บน (ในผังงานรูปที่ 13.11 คือเงื่อนไข K > 15)

เวลารอสูงสุดในรอบที่ 10: ช่วงสุ่มคือ {0 … 2¹⁰−1} = {0 … 1023}

TB,max = 1023 × 51.2 µs = 52,377.6 µs ≈ 52.4 ms

ลองเทียบดู — 52 มิลลิวินาที นานกว่าเวลาส่งเฟรม 1500 ไบต์ที่ 10 Mbps (1.2 ms) ถึง 43 เท่า · นี่คือเหตุผลที่ IEEE 802.3 หยุดขยายช่วงที่ K = 10 (truncated backoff) ไม่งั้นรอบที่ 16 จะรอกันเป็นวินาที

ข้อ 3 กลาง — ช่องสัญญาณ 1 Mbps ส่งเฟรมขนาด 1000 บิต (ดังนั้นความจุเชิงทฤษฎี = 1000 เฟรม/วินาที)
จงหา throughput เป็น เฟรม/วินาที ของทั้ง Pure และ Slotted ALOHA ที่ (ก) G = 0.5 (ข) G = 1.0 (ค) G = 2.0 · แล้วสรุปว่าแต่ละแบบควรคุม G ไว้ที่เท่าไร

เฉลยข้อ 3

ขั้นที่ 1 — แทนค่าในสูตร (S เป็นสัดส่วน ต้องคูณ 1000 เฟรม/วินาทีเพื่อได้จำนวนเฟรมจริง)

GPure: S = Ge−2Gเฟรม/วินาทีSlotted: S = Ge−Gเฟรม/วินาที
0.50.5 × e−1 = 0.1839 ← ยอด183.90.5 × e−0.5 = 0.3033303.3
1.01 × e−2 = 0.1353135.31 × e−1 = 0.3679 ← ยอด367.9
2.02 × e−4 = 0.036636.62 × e−2 = 0.2707270.7

ขั้นที่ 2 — อ่านผล

  • Pure ALOHA ควรคุม G ไว้ที่ 0.5 ได้ 183.9 เฟรม/วินาที (18.4% ของความจุ) · ถ้ายิงเป็น 2 เท่า (G = 1) กลับได้น้อยลงเหลือ 135.3 และถ้ายิง 4 เท่า (G = 2) เหลือแค่ 36.6 — ยิ่งยิงยิ่งเสีย
  • Slotted ALOHA ควรคุม G ไว้ที่ 1 ได้ 367.9 เฟรม/วินาที (36.8%) · ทนโหลดเกินได้ดีกว่า pure มาก (ที่ G = 2 ยังได้ 270.7)
  • ที่จุดยอดของแต่ละแบบ slotted ได้เป็น 2 เท่าของ pure พอดี (367.9 ≈ 2 × 183.9) ✓ ตรงกับทฤษฎี

ข้อ 4 กลาง
(ก) พิสูจน์ด้วยอนุพันธ์ว่า Slotted ALOHA มี S สูงสุดที่ G = 1 และ Pure ที่ G = 0.5
(ข) ที่จุดสูงสุดนั้น โดยเฉลี่ยต้องยิงกี่ครั้งต่อเฟรมที่ส่งสำเร็จ 1 เฟรม
(ค) ระบบมี 100 สถานี แต่ละสถานีส่งเฉลี่ย 1 เฟรมทุก 2 วินาที เฟรมละ 1000 บิต ช่องสัญญาณ 100 kbps · จงหา G และ throughput จริง (เฟรม/วินาที) ของ Pure ALOHA

เฉลยข้อ 4

(ก) พิสูจน์ — ใช้กฎผลคูณ d/dG [G·e−aG] = e−aG + G·(−a)e−aG = e−aG(1 − aG)

Slotted (a = 1): dS/dG = e−G(1 − G) = 0 · เนื่องจาก e−G > 0 เสมอ → 1 − G = 0 → G = 1
   Smax = 1 · e−1 = 1/e = 0.3679

Pure (a = 2): dS/dG = e−2G(1 − 2G) = 0 → 1 − 2G = 0 → G = 0.5
   Smax = 0.5 · e−1 = 1/2e = 0.1839

(ข) จำนวนครั้งที่ต้องยิงต่อ 1 เฟรมสำเร็จ = G / S (ยิงไปเท่าไร ÷ รอดเท่าไร)

Pure: G/S = G / (Ge−2G) = e2G · ที่ G = 0.5 → e1 = 2.718 ครั้ง
Slotted: G/S = eG · ที่ G = 1 → e1 = 2.718 ครั้ง

ผลลัพธ์ที่สวยงาม: ที่จุดสูงสุด ทั้งสองแบบต้องยิงเฉลี่ย e ≈ 2.72 ครั้งต่อเฟรมที่รอด 1 เฟรมเท่ากันพอดี — ต่างกันตรงที่ slotted ทำแบบนั้นได้ที่โหลดสูงกว่า 2 เท่า จึงได้ throughput 2 เท่า

(ค) แทนค่าจริง

λT = 100 สถานี × (1 เฟรม / 2 วินาที) = 50 เฟรม/วินาที
G = λT · Lp / R = (50 × 1000) / 100,000 = 0.5
S = G·e−2G = 0.5 × e−1 = 0.1839
throughput จริง = S × (R / Lp) = 0.1839 × 100 = 18.39 เฟรม/วินาที

อ่านผล: ยิงลงสาย 50 เฟรม/วินาที แต่รอดแค่ 18.4 เฟรม/วินาที — เสียไป 63% เพราะการชน · และนี่คือจุดที่ดีที่สุดแล้ว ถ้าเพิ่มสถานีเป็น 200 ตัว (G = 1) จะเหลือแค่ 13.5 เฟรม/วินาที — เพิ่มคน แต่ได้งานน้อยลง

ข้อ 5 ยากกว่าของจริง — สถานี A, B, C ชนกันที่ t = 0 บน Ethernet 10 Mbps (Tslot = 51.2 µs) สมมติค่าที่สุ่มได้เป็นดังนี้
รอบ 1: A = 1, B = 0, C = 0 · รอบ 2: A = 2, B = 3, C = 1 · รอบ 3: A = 5, B = 5 · รอบ 4: A = 11, B = 3 · รอบ 5: A = 7
(ก) ไล่ทีละรอบว่าเกิดอะไรขึ้น ใครได้ส่งเมื่อไร และ TB ของแต่ละคนเป็นเท่าไร
(ข) A ต้องรอรวมกี่ไมโครวินาที (นับเฉพาะเวลา backoff)
(ค) โอกาสที่รอบที่ 1 จะจบเรียบร้อย (มีผู้ชนะคนเดียว) สำหรับ 3 สถานีเป็นเท่าใด · แล้วรอบที่ 2 ล่ะ

เฉลยข้อ 5

(ก) ไล่ทีละรอบ — กติกา: ใครได้ค่าน้อยที่สุดคนเดียวได้ส่งก่อน ถ้าค่าน้อยสุดซ้ำกัน = ชนซ้ำ K เพิ่ม 1 ช่วงสุ่มกว้างเป็น 2 เท่า

รอบ Kช่วงสุ่มค่าที่ได้ค่าน้อยสุดผลTB ของผู้ชนะ
1{0, 1}A=1 · B=0 · C=00 (B และ C)ชนซ้ำ — น้อยสุดไม่ unique—
2{0 … 3}A=2 · B=3 · C=11 (C คนเดียว)C ส่งสำเร็จ ออกจากการแข่ง1 × 51.2 = 51.2 µs
3{0 … 7}A=5 · B=55 (ทั้งคู่)ชนซ้ำ—
4{0 … 15}A=11 · B=33 (B คนเดียว)B ส่งสำเร็จ3 × 51.2 = 153.6 µs
5{0 … 31}A=77เหลือคนเดียว A ส่งสำเร็จ7 × 51.2 = 358.4 µs

ลำดับที่ได้ส่ง: C → B → A · สังเกตว่า C ซึ่งสุ่มได้ 0 ในรอบแรก (เร็วที่สุด) กลับต้องรอถึงรอบ 2 เพราะดันไปชนกับ B ที่ได้ 0 เหมือนกัน — ค่าน้อยไม่ได้แปลว่าชนะ ต้องน้อยแบบไม่ซ้ำใครเท่านั้น

(ข) เวลารอรวมของ A — A ผ่านทุกรอบ จึงต้องรอ backoff ทุกครั้งที่สุ่มได้ (รอบที่ตนแพ้ก็ยังต้องรอครบตามค่าที่สุ่มก่อนจะรู้ว่าสายไม่ว่าง)

c ที่ A สุ่มได้ทั้งหมด = 1 + 2 + 5 + 11 + 7 = 26 สล็อต
TB,รวม = 26 × 51.2 µs = 1,331.2 µs ≈ 1.33 ms

เทียบให้เห็นภาพ: เวลาส่งเฟรม 1500 ไบต์ที่ 10 Mbps = 1.2 ms — แปลว่า A เสียเวลารอนานกว่าเวลาส่งจริงของตัวเอง นี่คือราคาของการแย่งช่องสัญญาณ

(ค) โอกาสที่รอบหนึ่งจะจบเรียบร้อย (3 สถานี) — ต้องมีสถานีเดียวที่ได้ค่าต่ำสุด

รอบ 1 ช่วง {0, 1} มี 2 ค่า → ผลลัพธ์ทั้งหมด 2³ = 8 แบบ
แบบที่มีผู้ชนะคนเดียว = "มีคนได้ 0 พอดี 1 คน อีก 2 คนได้ 1" = 3 แบบ (เลือกว่าใครได้ 0)
(ถ้าได้ 0 สองคนขึ้นไป → ชน · ถ้าได้ 1 ทั้งสามคน → ชน)
⟹ P = 3/8 = 37.5% · โอกาสชนซ้ำสูงถึง 62.5%

รอบ 2 ช่วง {0 … 3} มี 4 ค่า → ผลลัพธ์ 4³ = 64 แบบ
นับตามค่าต่ำสุด m: จำนวนแบบ = 3 × (จำนวนค่าที่มากกว่า m)²
  m = 0 → 3 × 3² = 27 · m = 1 → 3 × 2² = 12 · m = 2 → 3 × 1² = 3 · m = 3 → 0
  รวม = 42 แบบ ⟹ P = 42/64 = 65.6%

บทเรียน: โอกาสจบเรียบร้อยพุ่งจาก 37.5% → 65.6% → (รอบ 3) 82.0% → (รอบ 4) 90.8% เพียงเพราะช่วงสุ่มกว้างขึ้นเป็น 2 เท่าทุกรอบ — นี่คือเหตุผลทั้งหมดที่อัลกอริทึมนี้ชื่อว่า exponential backoff และเป็นประโยคปิดท้ายที่ควรเขียนในข้อสอบ

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

สถานีชนไปแล้ว 5 ครั้ง (K = 5) ค่า c ที่เป็นไปได้มีกี่ค่า และค่ามากที่สุดคือเท่าไร?
ช่วงคือ {0, 1, …, 2K − 1} = {0, …, 31} · มี 25 = 32 ค่า (เพราะนับ 0 ด้วย) แต่ค่ามากที่สุดคือ 31 · สองตัวเลขนี้ต่างกัน 1 เสมอ ซึ่งเป็นจุดที่คนสับสนบ่อยที่สุด — จำนวนค่า = 2K · ค่าสูงสุด = 2K − 1
Pure ALOHA ที่ G = 1.0 ได้ throughput เท่าไร และดีกว่าหรือแย่กว่าที่ G = 0.5?
แทนค่า: S = G·e−2G = 1 × e−2 = 0.1353 · จุดยอดของ pure อยู่ที่ G = 0.5 (S = 0.184) ส่วน G = 1 เป็นจุดยอดของ slotted เท่านั้น · ที่ G = 1 pure จึงเลยยอดมาแล้วและกำลังตกลง — ยิงเป็น 2 เท่าแต่ได้น้อยลง 26% นี่คือใจความทั้งหมดของกราฟข้อ B
ในการจำลอง 3 สถานี รอบแรกทั้ง B และ C สุ่มได้ c = 0 เหมือนกัน จะเกิดอะไรขึ้น?
c = 0 แปลว่า "รอ 0 สล็อต = ส่งทันที" ดังนั้นสองสถานีที่ได้ 0 เหมือนกันจะส่งพร้อมกันและชนซ้ำ · ผลคือ K ของทั้งคู่เพิ่มเป็น 2 และช่วงสุ่มขยายเป็น {0, 1, 2, 3} ทำให้โอกาสชนซ้ำลดจาก 1/2 เหลือ 1/4 · ไม่มีการใช้ MAC address ตัดสิน (นั่นคือ STP ไม่ใช่ CSMA/CD) และการชนซ้ำก็ไม่ได้ทำให้ทิ้งเฟรม — จะทิ้งก็ต่อเมื่อชนครบ 16 ครั้ง
เก็บก่อนออกจากข้อนี้
  • 0 ≤ C ≤ 2K − 1 — จำนวนค่า = 2K (2, 4, 8, 16) แต่ค่าสูงสุด = 2K − 1
  • TB = C × Tp — ห้ามตอบ C เปล่า ๆ · Ethernet 10 Mbps: Tp = 51.2 µs
  • ตารางเฉลย 4 รอบ: รอบ 1–3 A กับ B ได้ค่าเท่ากัน (1,1 → 3,3 → 6,6) ชนซ้ำตลอด · รอบ 4 C เข้ามาใหม่ (KC = 1) ได้ 11, 4, 1 ไม่ซ้ำกัน → จบ
  • K เป็นของแต่ละสถานี ไม่ใช่ของระบบ — สถานีที่เพิ่งชนครั้งแรกได้ K = 1 เสมอ
  • ชนซ้ำเมื่อค่าน้อยสุดซ้ำกัน · c = 0 = ส่งทันที ไม่ใช่ไม่ส่ง · ชนครบ 16 ครั้ง → ทิ้งเฟรม + แจ้ง error
  • Pure: S = Ge−2G → ยอด (0.5, 0.184) = 18.4% · Slotted: S = Ge−G → ยอด (1, 0.368) = 36.8%
  • กราฟต้องเป็นโค้งคว่ำที่ตกลง พร้อมตัวเลขกำกับจุดยอดทั้งสอง — ไม่มีตัวเลข = ได้ครึ่งเดียว
  • เลข 2 ใน e−2G มาจากช่วงเสี่ยง 2Tp ของ pure ALOHA