Week 8 : Data Link Control

Automatic Repeat Request (ARQ)

Main ARQ protocols

- Stop and Wait ARQ (A half duplex technique)
- Continuous ARQ (A full duplex technique)

Stop and Wait ARQ (A half duplex technique)
- เป็นกลไกลที่ง่ายและไม่มีความซับซ้อนมากนัก หลักการทำงาน มีดังนี้
- ผู้ส่งจะทำสำเนาเฟรมข้อมูลที่จัดส่งไปเอาไว้ก่อน จนกว่าผู้รับจะยืนยันว่าได้รับข้อมูลแล้ว
- ผู้รับจะส่งเฟรม acknowledgment (ACK) มาให้กับผู้ส่ง เช่น ผู้รับส่งเฟรม ACK1 มาให้ จะมีความหมายว่าได้รับเฟรม 0 แล้วให้ส่งเฟรม 1 มาได้เลยเป็นต้น
- ถ้าเกิดผู้รับได้เฟรมข้อมูลที่ผิดพลาด จะทำการทิ้งเฟรมนั้นไป
- ผู้ส่งจะใช้ตัวแปร S ในการเก็บข้อมูลว่าได้ส่งเฟรมอะไรไป ส่วนผู้รับใช้ตัวแปร R ในการเก็บข้อมูลว่าเฟรมถัดไปที่ต้องการคือเฟรมอะไร
- ผู้ส่งจะมีการกำหนดเวลาหลังจากส่งเฟรมออกไปแล้ว ถ้าไม่ได้รับ เฟรม ACK กลับมาในเวลาที่กำหนด จะต้องส่งเฟรมข้อมูลนั้นกลับไปอีกครั้ง
- ผู้รับจะส่งเฟรม ACK กลับไป เมื่อได้รับเฟรมข้อมูลที่ไม่มีความผิดพลาด ถ้ามีการผิดพลาดจะไม่ส่งข้อมูลใดๆ กลับไปแบ่งสถานการณ์ที่จะเกิดขึ้นออกเป็น 4 กรณีด้วยกัน คือ
1. กรณีปกติ ( Normal operation ) เมื่อผู้ส่งได้ส่งเฟรม 0 และจะทำการคอยรับเฟรม ACK 1 เมื่อได้รับ ACK1 แล้วถึงจะส่งเฟรม 1 ไป แล้วก็คอยรับเฟรม ACK0 ต่อไป จะเป็นแบบนี้ไปเรื่อยๆ ดังรูป

2. กรณีเฟรมข้อมูลสูญหายหรือเสียหาย ( Stop-and-Wait ARQ, lost frame ) ถ้าเฟรมผิดพลาด ผู้รับจะทิ้งเฟรมนั้นไป แล้วไม่ส่งACKกลับไป ดังนั้นตัวแปร R จะยังคงเท่ากับ 1 อยู่ เมื่อผู้ส่งไม่ได้รับเฟรม ACK กลับมาตามเวลาที่กำหนด ผู้ส่งจะส่งเฟรมข้อมูลนั้นกลับไปใหม่ ดังรูป

3. กรณีเฟรม ACK สูญหาย Stop-and-Wait ARQ, lost ACK frame จะทำเหมือนกับกรณีเฟรมข้อมูลหาย จากรูป ACK 0 ได้หายไปในระหว่างการส่ง เมื่อถึงเวลาที่กำหนด ผู้ส่งยังไม่ได้รับเฟรม ACK0 ผู้ส่งจะส่งเฟรม 1 กลับไปใหม่อีกครั้ง และเมื่อผู้รับได้เฟรม 1 แต่ไม่ใช่เฟรมที่ต้องการ (R=0) ผู้รับจะทำการทิ้งเฟรมนั้นไป และส่งเฟรม ACK 0 กลับไปอีกครั้ง

4 กรณีส่งเฟรม ACK ล่าช้า Stop-and-Wait ARQ, delayed ACK ดังรูป เฟรม ACK 1 เกิดความล่าช้า เมื่อครบระยะเวลาที่กำหนด ผู้ส่งยังไม่ได้รับเฟรม ACK 1 ก็จะส่งเฟรม 0 ไปใหม่อีก แต่ผู้รับจะไม่รับเฟรมนี้ เนื่องจาก R=1 คือ ผู้รับต้องการเฟรม 1 ไม่ใช่เฟรม 0

การส่งข้อมูลแบบสองทาง

จะเป็นการส่งข้อมูลทิศทางเดียว จะมีผู้ส่งและรับข้อมูลที่แยกจากัน แต่ถ้าต้องการที่จะเป็นทั้งผู้ส่งและรับข้อมูลในว่าลาเดียวกัน จะมีการเก็บทั้งตัวแปร S และ R เอาไว้

Piggybacking เป็นการส่งข้อมูลเฟรมและเฟรม ACK ไปพร้อมกัน ดังรูป เครื่อง A และ B จะส่งข้อมูล จึงรวมทั้ง 2 เฟรมเข้าด้วยกันแล้วส่งออกไป จะสามารถช่วยลดแบนด์วิดธ์ลงได้

Go-Back-N

Go-Back-N จะทำการส่งเฟรมข้อมูลจำนวน W เฟรม ก่อนที่จะได้รับเฟรม ACK ดังนั้น ผู้ส่งต้องทำสำเนาเฟรมข้อมูลทั้ง W เฟรมเอาไว้ด้วย ในHeader ของเหรมข้อมูลที่เฟรมจะมีหมายเลขลำดับ (Sequence number) จะเริ่มต้นจากหมายเลย 0 เป็นต้นไป จะเริ่มจากซ้ายไปขวา

Sender Sliding Window เฟรมข้อมูลที่อยู่ด้านซ้ายของหน้าต่างหมายถึงเฟรมที่ได้รับ ACK แล้ว ลบทิ้งเฟรมนั้นออกจากบัฟเฟอร์ได้ ส่วนเฟรมที่อยู่ด้านขวาของหน้าต่าง เป็นเฟรมที่ยังไม่ได้มีการส่งออกไป จะต้องรอจนกระทั่งหน้าต่างเลื่อนมาถึงจึงจะสามารถส่งเฟรมข้อมูลได้

Receiver Sliding Window ขนาดหน้าต่างของผู้ส่งจะมีขนาดเท่าใดก็ได้ แต่ขนาดหน้าต่างของผู้รับจะมีค่าเท่ากับ 1 เสมอ ข้อมูลที่ถูกหน้าต่างครอบไว้คือเฟรมที่ผู้รับต้องการและยังไม่ได้รับเฟรมนั้นจากผู้ส่ง

Go-Back-N ARQ, normal operation ในกรณีที่การส่งเฟรมข้อมูลและเฟรม ACK ไม่มีข้อผิดพลาด ผู้ส่งจะเก็บค่าหมายเลขลำดับของเฟรมที่ถูกส่งออกไปเอาไว้ก่อน เมื่อได้รับเฟรม ACK กลับมาจึงจะทำการเลื่อนหน้าต่างไปตามเฟรม ACK ที่รับเข้ามา

Go-Back-N ARQ, lost frame ถ้ามีเฟรม ACK ใดตอบกลับมาก่อนที่จะหมดเวลาที่ได้กำหนดไว้สำหรับเฟรม ACK นั้นๆ ผู้ส่งไม่จำเป็นต้องส่งเฟรมข้อมูลก่นอหน้านั้นกลับไปใหม่ ถึงแม้ว่าเฟรม ACK ก่อนหน้าบางเฟรมจะสูญหายไปก็ตาม ถ้าหมดเวลาในการรับเฟรม ACK แล้วผู้ส่งจะต้องทำการส่งเฟรมข้อมูลก่อนหน้านั้นใหม่ทั้งหมดอีกครั้ง

Go-Back-N ARQ : sender window size ขนาดของหน้าต่างส่งต้องน้องกว่า 2 ยกกำลัง m ขนาดของหน้าต่างรับต้องเป็น 1 เสมอ