Data Link layer
จะเตรียมส่งผ่านข้อมูลข้ามเครือข่ายทางกายภาพ Data link layer ที่ต่างกันก็มีรายละเอียดของเครือข่าย และ
protocol ที่ต่างกัน รวมไปถึง physical address, network topology ,การประกาศข้อผิดพลาด , ลำดับของ
frame และการควบคุมการไหลของข้อมูล Data Link layer จะแปลข้อมูลจาก Network layer ให้เป็น bits
สำหรับ Physical layer เพื่อถ่ายโอนข้อมูล โดยรูปแบบ คือ จากข้อมูลแปลงเป็น frame แล้วเพิ่มส่วนหัวของข้อมูล
ซึ่งได้แก่ แหล่งกำเนิดและที่อยู่ของอุปกรณ์หลายทางData link layer จะรับผิดชอบการค้นหาอุปกรณ์บนเครือข่าย
กระบวณการ media access control คือ วิธีในการควบคุมการเข้าใช้งานสื่อกลาง จะเป็นข้อตกลงที่ใช้ในการรับส่งข้อมูลผ่านสื่อกลางซึ่งทุกโหนดในเครือข่ายจะ ต้องใช้มาตรฐานเดียวกัน การทำงานจะเกิดอยู่ในส่วนของแผงวงจรเชื่อมต่อเครือข่าย (Network Interface Card : NIC) และทำงานอยู่ในครึ่งท่อนล่างของ Data link Layer
Point-to-Point Topology
- เป็นการเชื่อมต่อระหว่างอุปกรณ์ได้เพียง 2 อุปกรณ์(หรือ 2 จุด)เท่านั้น
- ความน่าเชื่อถือต่ำ เนื่องจากถ้าหาก Link ที่มีอยู่เพียงเส้นเดียวเสียหาย จะทำให้เครือข่ายทั้งสองด้านของ Link ถูกตัดขาดออกจากกันทันที
- เป็นพื้นฐานของการเชื่อมต่อเครือข่ายประเภทอื่นๆที่ซับซ้อนมากขึ้นเนื่องจาก ต้องอาศัยการเชื่อมต่อแบบ Point-to-Point เป็นพื้นฐานนั้นเอง
- ในกระบวณการ media access method ที่ถูกทำโดย Data Link protocol จะถูกพิจารณาโดย logical point-to-point topology
Multi-Access Topology
- เป็นการเชื่อมต่อโดยอาศัยอุปกรณ์มากกว่า 2 อุปกรณ์ขึ้นไป ซึ่งอุปกรณ์สามารถ Share ร่วมกันได้
- อุปกรณ์สามารถส่งข้อมูลหากันได้ (ส่งได้เมื่อไม่มีการใช้สื่ออยู่)
- โดยปกติในการ media access control methods จะใช้ CSMA/CD or CSMA/CA, token passing
MAC for Shared Media
- กระบวณการขั้นพื้นฐานในการ media access control สำหรับการแชร์ไฟล์
1. Controlled : แต่ละโหนดจะมีช่วงเวลาในการใช้งานสื่อของตัวเอง
2. Contention-based : ทุกๆโหนดมีความพร้อมสำหรับการใช้งานสื่อ
- Controlled Access for Shared Media
- เมื่อใช้ กระบวณการ Controlled Access อุปกรณ์ในเครือข่ายจะผลัดกันในการใช้งานสื่อเป็นลำดับ โดยอาจเรียกกระบวณการนี้ว่า scheduled access or deterministic
- อุปกรณ์ในเครือข่ายสามารถส่งได้ทีละอัน อุปกรณ์อื่นต้องรอให้ถึงตาของตัวเอง
- ไม่มีการชนกันของข้อมูล
- ตัวอย่างเช่น Token Ring, FDDI
o Poll คือ Message ที่ Central computer ส่งไปถาม secondary ว่ามีอะไรจะส่งไหม
o ถ้าไม่ได้รับการอนุญาติ secondary ก็ไม่มีสิทธิส่ง
o ทั้งหมดควบคุมโดย central computer , สำหรับระบบ Multipoint จะรับประกันว่าจะส่งตรงเวลา
o ถ้า central computer พร้อมที่จะรับข้อมูลจะส่ง ask (Poll) ออกไปถาม secondary ว่ามีอะไรจะส่งหรือไม่
o ถ้า secondary ไม่มีอะไรจะส่งก็จะตอบ nothing to send control message(NAK) กลับมาบอก
o และถ้าได้รับ NAK frame , central computer ก็จะส่ง Poll ออกไปถาม secondary ตัวต่อไป
o จนกว่าจะมีข้อมูลที่จะส่ง
o และถ้าส่งข้อมูลเสร็จเรียบร้อย central computer ก็จะส่ง acknowledgement(ACK) ออกไป
o เพื่อเป็นการยืนยันว่าได้รับข้อมูลแล้ว
Roll-Call Polling
Roll-call polling protocol จะถูกส่งไปยังผู้ใช้งานรอบๆ โดยทั่ว, ที่ central control จะเลือกผู้ใช้เพียงหนึ่งราย ผู้ใช้งานรายอื่นจะถูกกำหนดให้ใช้หลังจากนั้นทีละราย ถ้าผู้ใช้รายนั้นได้รับ polling message จาก central control ก็ทำการส่ง message ไปจนไม่มีสิ่งใดจะส่งอีก หรือส่งทุก message ที่เก็บไว้ในหน่วยความจำกลาง หลังจากทำการส่งถึง message สุดท้าย มันก็จะส่งข้อความ “ready” ไปยัง central control หลังจาก central control ได้รับข้อความนี้ ตัว controller ก็จะส่ง polling message ไปยังผู้ใช้ในลำดับต่อไป
Token-Passing Protocol
ตัวอย่างหนึ่งของ token-passing protocol คือ token-bus protocol ใน protocol ชนิดนี้ ผู้ใช้งานทั้งหมดจะถูกต่อไปยัง bus เดียวกัน ผู้ใช้แต่ละรายจะให้ address ไว้อันหนึ่ง,ผู้ใช้ bus ถูกจัดลำดับเป็นวงแหวนโดยรหัสของผู้ใช้แต่ละราย ที่รู้จักกันใน
successor’s address ผู้ใช้จะมี address ที่แน่นอน และข้อมูลที่ส่งออกไปจะมี address ของผู้ใช้ถูกส่งออกไปด้วย ผู้รับที่รู้จัก address นั้น จะรู้ว่าข้อมูลที่ส่งมานั้นมีเจตนาที่จะส่งมาเพื่อเขา
ในความเป็นจริงผู้ใช้ที่จะส่งได้ขึ้นอยู่ว่าผู้ใช้รายนั้นได้รับส่วนของ control information ที่เรียกว่า token ก่อนหน้านั้นหรือไม่ ถ้าผู้ใช้ได้รับ token และต้องการที่จะส่งข้อมูลจริงๆ,ก็ทำการส่งข้อมูลนั้นออกไปได้จนถึงข้อมูลสุดท้าย,ก็ทำการส่ง token ไปยังผู้รับช่วงรายต่อไป ถ้าผู้รับช่วงรายนี้ยังไม่มีข้อมูลอะไรส่งในขณะนั้น มันก็จะส่ง token ไปยังผู้รับช่วงรายลำดับต่อไปทันที ถ้าผู้รับช่วงรายปัจจุบัน holds the token ก็ยอมให้ผู้ใช้รายนั้นส่งข้อมูลออกไปได้ อันนี้เป็นหลักการของ distributed demand assignment protocol
- Contention-based Access for Shared Media
- เรียกอีกอย่างว่า non-determistic ซึ่งจะอนุญาตให้อุปกรณ์มาสามารถใช้สื่อเมื่อไรก็ได้
- ซึ่งอาจจะมีการชนกันของข้อมูลได้
- เพื่อป้องการใช้กระบวณการ Carrier Sense Multiple Access (CSMA)ซึ่งจะคอยตรวจสอบสื่อกลางเสียก่อนว่าว่างหรือไม่ ถ้าว่างจึงจะสามารถส่งได้
- ตัวอย่างเช่น Eternet, wireless
- ไม่เหมาะกับระบบที่มีการใช้งานสื่อมากๆ เพราะว่าถ้าจำนวนโหนดเพิ่มขึ้น ความน่าจะเป็นนการประสบความสำเร็จในการใช้งานสื่อโดยไม่มี Collision หรือการชนกันของข้อมูลจะลดลง
Poll
Contention (Random) Multiple Access Protocols
สำหรับ contention multiple access จะไม่มีหมายกำหนดการในการใช้ช่องการสื่อสาร นั้นคือผู้ใช้รายใดพร้อมที่จะส่งก็ส่ง โดยไม่สามารถรู้ได้อย่างแน่ชัดว่าการส่งออกไปนั้นจะไปรบกวนกับผู้ใช้รายอื่นหรือไม่ ผู้ใช้อาจจะรู้หรือไม่รู้การดำเนินการของช่องการสื่อสารขณะนั้นอย่างแน่ชัดเกี่ยวกับผู้ใช้รายอื่น ดังนั้นเมื่อมีผู้ใช้พร้อมที่จะส่งมากกว่าหนึ่งรายในเวลาเดียวกัน ทุกการสื่อสารที่ทำการส่งในขณะนั้นของทุกรายก็จะ fail การสื่อสารที่ failure จะแสดงถึงสภาวะการประสบผลสำเร็จของการสื่อสารมากหรือน้อยในขบวนการของ random process, การเข้าถึงช่องสัญญาณแบบ random process protocol ควรมีการตัดสินใจในกรณีเกิดการ แย่งกันส่งในเวลาเดียวกันของผู้ใช้แต่ละราย
หากบังเอิญมีการส่งสัญญานตรวจสอบสายออกมาพร้อมกันมากกว่าหนึ่งเครื่อง จะเกิดการชนกันขึ้น เรียกปรากฎการณ์นี้ว่า Collision คือการชนกันของสัญญาน เมื่อเกิดการชนกันของสัญญานขึ้น เครื่องที่ต้องการส่งจะสุ่มเวลารอคอยใหม่ แล้วจึงจะส่งสัญญานถามออกไปใหม่ ซึ่งเวลาในการรอคอยนั้นๆ จะเป็นเวลาสุ่มซึ่งไม่เท่ากัน ( โดยมีวงจร Random ที่อยู่บนการ์ดแลน เป็นตัวทำงาน ) โดยวิธีการนี้จะแยกเป็น CSMA/CA และ CSMA/CD
การตรวจจับความผิดพลาด(Error detection) และ การแก้ไขความผิดพลาด(Error correction)
* การตรวจจับความผิดพลาดเป็นความสามารถในการตรวจจับความผิดพลาดที่เกิดจาก ถูกรบกวนระหว่างการส่งผ่านจากตัวส่ง(transmitter) ไปยังตัวรับ(receiver)
* การแก้ไขความผิดพลาดเป็นการเพิ่มคุณสมบัติด้านการจำแนกแยกแยะและแก้ไขความผิดพลาดที่เกิดขึ้น
* การตรวจจับความผิดพลาดเกิดขึ้นก่อนการแก้ไขความผิดพลาดเสมอ
วิธีตรวจหาข้อมูลผิดพลาดแบบง่ายที่สุดทำได้โดยใช้ พาริตี้บิต (parity bit) เป็นข้อมูลที่เพิ่มเข้าไป ซึ่งพาริตี้แบ่งได้เป็น 2 ชนิดคือ พาริตี้คี่ (odd parity) และพาริตี้คู่ (even parity) พาริตี้คี่คือจำนวนบิตทั้งหมดที่มีค่าเป็น 1 ของบิตข้อมูล ซึ่งรวมทั้งพาริตี้บิตด้วยจะเป็นจำนวนคี่ เช่น หากข้อมูลมีค่าเป็น 1010101011 แล้ว พาริตี้บิตต้องมีค่าเป็น 1 ทำให้ข้อมูลที่ส่งไปรวมพาริตี้บิตมีค่าเป็น 10101010111 นั่นคือจำนวนบิตทั้งหมดที่มีค่าเป็น 1 มีจำนวน 7 บิตนั่นเอง ส่วนพาริตี้คู่คือจำนวนบิตทั้งหมดที่มีค่าเป็น 1 ของบิตข้อมูลซึ่งรวมทั้งพาริตี้บิตด้วยจะเป็นจำนวนคู่ สำหรับตัวอย่างข้อมูลข้างต้นจะได้ว่า ในกรณีของพาริตี้คู่นั้น ข้อมูลที่ส่งไปรวมพาริตี้บิตมีค่าเป็น 1010101011
ในการหาพาริตี้ทำได้โดยการ XOR ของทุก ๆ บิต เช่น ในกรณีของพาริตี้คู่จะเอาค่า 0 มาทำการ XOR ตั้งแต่บิตแรกจนถึงบิตสุดท้ายของบิตข้อมูล ผลลัพธ์ที่ได้คือค่าพาริตี้บิต และสำหรับพาริตี้คี่นั้นจะนำเอาค่า 1 มาทำการ XOR กับทุกบิตข้อมูล วิธีการหาพาริตี้บิตนี้เป็นวิธีง่าย ๆ และใช้ข้อมูลที่เพิ่มเข้าไปน้อย แต่ประสิทธิภาพของการตรวจหาข้อมูลผิดพลาดจะมีแค่ 50% เท่านั้น กล่าวคือวิธีนี้จะตรวจหาข้อมูลผิดพลาดได้ในกรณีที่จำนวนบิตที่ผิดพลาดเป็นจำนวนคี่เท่านั้น
การเข้ารหัสแบบ LRC (Longitudinal Redundancy Check) การเข้ารหัสแบบ LRC (Longitudinal Redundancy Check) เป็นการนำบล็อกของบิตข้อมูลมาจัดในตาราง(จัดเป็นแถวและหลัก) โดยการนำบล็อกของข้อมูล 32 บิตมาจัดในตารางให้เป็น 4 แถวและ 8 หลัก แล้วทำการตรวจสอบพาริตี้บิตของหลักทุกหลักแล้วจะได้แถวของข้อมูล 8 บิตขึ้นมาใหม่ 1 แถว การทำพาริตี้บิต บิตที่ 1 ในแถวที่ 5 ได้จากการทำพาริตี้คู่ของบิตแรกในทุกๆ แถว, พาริตี้บิต บิตที่ 2 ในแถวที่ 5 ได้จากการทำพาริตี้คู่ของบิตที่ 2 ในทุกๆ แถว และเป็นเช่นนี้จนถึงบิตที่ 8 จากนั้นทำการส่งพาริตี้บิต 8 บิตนี้ต่อจากข้อมูลเดิมส่งไปยังผู้รับ
ข้อแตกต่างระหว่าง Parity bit กับ CRC
- CRC มีประสิทธิภาพสูงว่าแบบ พาริตี้บิต - แบบพาริตี้บิต ใช้การบวก แต่ CRC ใช้การหาร - แบบพาริตี้บิต จะแทรกบิตตรวจสอบลงในข้อมูล แต่แบบ CRC จะต้องนำบิตตรวจสอบไปต่อท้ายข้อมูล
ข้อเสียของ Parity bit
การใช้ Parity bit คือ เสียเวลา และไม่ได้ประโยชน์เท่าไรนัก เพราะไม่สามารถบอกได้ว่าผิดที่ตำแหน่งตรงไหน และแก้ไขข้อผิดพลาดไม่ได้ บอกได้แค่เพียงว่ามีความผิดพลาดเกิดขึ้นเท่านั้น และ ถ้าสมมติข้อมูลเกิดผิดพลาดทีเดียว 2 บิต เช่น 10001001 เปลี่ยนเป็น 10101011 เราก็ไม่สามารถเช็คข้อผิดพลาดโดยใช้วิธี Parity ได้
cyclic redundancy checking (CRC)
cyclic redundancy checking เป็นวิธีการของการตรวจความผิดพลาดของข้อมูล ที่มีการส่งผ่านระบบการเชื่อมติดต่อ อุปกรณ์การส่งจะประยุกต์ข้อมูลขนาด 16 หรือ 32 บิต แบบ polynomial ไปยังบล๊อคข้อมูล โดยการส่งบิตแบบ polynomial จับผลลัพธ์ cyclic redundancy code (CRC) ไปยังบล๊อคข้อมูล ในด้านการรับประยุกต์ข้อมูลแบบ polynomial และเปรียบเทียบผลลัพธ์ ของด้านรับกับด้านส่ง ถ้ายอมรับ ข้อมูลจะได้รับเรียบร้อย ถ้าไม่ ผู้ส่งจะสามารถแจ้งให้ส่งบล๊อคข้อมูลใหม่
ITU-TS(CCITT) มีมาตรฐานสำหรับ 16 บิต polynomial ที่ใช้การตรวจสอบแบบ cyclic redundancy code (CRC) สำหรับ IBM มีระบบ Synchronous Data Link Control และโปรโตคอลอื่นได้ CRC -16 และ 16 บิตแบบ polynomial ซึ่ง 16 บิตของ cyclic redundancy code จะค้นหาบิตผิดพลาดถึงแบบเดี่ยวและคู่ เพื่อทำให้มั่นใจการค้นหาทำได้ 99.998 % ของความผิดพลาดที่เป็นไปได้ การค้นหาระดับนี้ รับประกันได้อย่างเพียงพอ สำหรับบล๊อคข้อมูลการส่ง 4 KB หรือน้อยกว่า สำหรับการส่งขนาด 32 บิตให้ CRC จะได้รับการส่งขนาดใหญ่ ซึ่งโปรโตคอลของเครือข่ายแบบ LAN คือ Ethernet และ Token ring ใช้ CRC ขนาด 32 - บิต
วิธีการตรวจสอบที่ซับซ้อนน้อยกว่า แต่ความสามารถน้อยกว่า คือ วิธีการ Checksum
CRC Check ใช้หลัก การหารเลขฐาน 2 โดยการเพิ่ม กลุ่มของบิต ต่อท้ายหน่วยข้อมูล เพื่อให้ ผลลัพธ์สามารถหารด้วย จำนวนที่กำหนดไว้ล่วงหน้า (เรียกว่า ตัวหาร –Divisor หรือ กุญแจรหัส) ลงตัวทางด้านรับตรวจสอบ โดยการ หารข้อมูลที่รับได้ด้วย กุญแจรหัส ซึ่งถ้าผลลัพธ์เป็นการหารลงตัวแสดงว่าข้อมูลถูกต้อง มิฉะนั้น แสดงว่าเกิด Error ขึ้น
คุณสมบัติของ CRC มี 2 ประการ
1.ความยาวของ CRC Bits น้อยกว่าของตัวหาร (Divisor) อยู่ 1
2.เมื่อ CRC นำมาต่อท้ายข้อมูลเดิมแล้ว ทำให้หารด้วย Divisor ลงตัว
หลักการคำนวณ Binary Division(คล้ายกับการหารยาวปกติ)
1.ตัวตั้งที่สามารถหารด้วย Divisor ได้ต้องมีจำนวนบิต (ความยาว) เท่ากับตัวหาร และผลหารที่ได้มีค่าเท่ากับ1
2.การลบตัวตั้งด้วยตัวหารในแต่ละขั้น ใช้การลบเลขฐานสองแบบไม่มีตัวทด
3.ถ้าตัวตั้งมีความยาวน้อยกว่า Divisor ผลหารมีค่าเท่ากับ 0 และแทนค่าตัวหารในขั้นตอนนั้น ด้วยเลข 0 ที่มีความยาวเท่ากับ Divisor
4.เศษเหลือในขั้นตอนสุดท้าย เมื่อใช้เลขตัวตั้งครบทุกบิต
การสร้าง CRC Bits สำหรับข้อมูลที่กำหนดให้มีขั้นตอนดังนี้
1.กำหนดให้ความยาวของ CRC เท่ากับ nBits
2.เลือกตัว Divisor ที่มีความยาว n + 1Bits และมีบิตซ้ายมือเท่ากับ 1
3.นำเลข 0 จำนวน nBits มาต่อท้ายข้อมูล
4.หารผลลัพธ์ที่ได้ในข้อ 3 ด้วย Divisor ด้วยวิธี Binary Division
5.เศษที่เหลือคือ CRC – ทำให้มีความยาว nBits โดยเติม 0 ไปด้านซ้ายมือ
6.แทนที่เลข 0 ในข้อ 3 ด้วย CRC Bits ที่ได้ในข้อ 5
Divisor Polynomial
Divisor สำหรับ CRC มักจะแสดงในรูปของฟังก์ชันพหุนาม (Polynomial) เพราะ1.เป็นการแสดงในรูปแบบที่กระชับ สื่อความหมายได้ดี
2.เอื้อประโยชน์ต่อการพิสูจน์การทำ CRC ทางคณิตศาสตร์
พหุนามดีกรีเท่ากับ 7
คุณสมบัติของ Divisor มีดังนี้
1.ต้องหารด้วย x ไม่ลงตัว
2.ต้องหารด้วย x + 1 ลงตัว
3.สามารถ Detect Burst Error ความยาว ≤degree ได้
Checksum
Checksum มีหลักการคล้ายกับ Parity และ CRC ตรงที่มีการใช้ข้อมูลซ้ำซ้อน (Redundancy)หลักการทำงานของ Checksum สามารถอธิบายได้ดังต่อไปนี้
1.ข้อมูลต้นฉบับจะถูกแบ่งออกเป็น Segment ซึ่งมีความยาว n bits(เช่น n = 16)
2.ข้อมูลในแต่ละ segment จะนำมาบวกกันด้วยวิธี One’s Complement ผลลัพธ์ที่ได้จะมีขนาด n bits.
3.ผลลัพธ์ที่ได้ในข้อ 2 จะถูกทำ Complement ซ้ำ แล้วนำไปต่อท้ายข้อมูลต้นฉบับ กลายเป็น Redundant Bits.
4.ข้อมูลต้นฉบับ พร้อมกับ Redundant Bits จะถูกส่งออกไปยังเครื่องรับปลายทาง ผ่านระบบเครือข่าย
Block Diagram
ในการสื่อสารทั่วไป มักจะทำ Checksum กับข้อมูลหลาย segments พร้อมๆ กัน ดังรูป แสดงการทำ Checksum กับข้อมูล k segments แต่ละ segment ยาว n
Check Sum ไม่สามารถตรวจพบ Error ได้ถ้าความผิดพลาดใน segment หนึ่ง สมดุลกับความผิดพลาดในอีก segment หนึ่ง ซึ่งเกิดในตำแหน่งเดียวกัน“จำนวน 1 และ 0 คงที่”
Forward Error Correction (FEC)คือวิธีที่แก้ไข Error อัตโนมัติที่ด้านรับ ทั้งนี้โดยอาศัยกลไกของการเข้ารหัสแบบพิเศษ เรียกว่า Error Correcting Code ซึ่งมีความซับซ้อนมากกว่าการตรวจจับ Error ทั่วไป และต้องการ Redundant Bits มากกว่า
Forward Error Correction
ในทางทฤษฎี Error Correcting Code สามารถแก้ไข Error ได้ทุกชนิด ทุกรูปแบบ เรียกการแก้ไข Error แบบนี้ว่า FECตัวอย่าง Single Bit Errorการตรวจจับและแก้ไข Error ชนิดนี้ ต้องสามารถระบุ “ข่าวสาร”2 ประการ–มี Error เกิดขึ้นหรือไม่ (Detection)–Error ที่เกิดขึ้นนั้น อยูที่ตำแหน่งใด (Identification)เพียงตรวจจับ Error ต้องการ Redundant Bit อีกเพียง 1 บิตเท่านั้นเพื่อระบุว่าชุดข้อมูลนั้นมี Error เกิดขึ้น (1) หรือไม่ (0)แต่การแก้ไข Error นั้นต้องสามารถ “ระบุตำแหน่งที่เกิด Error”(Identification of Invalid Bit) ได้ ซึ่งอุปกรณ์ด้านรับ เพียงกลับค่าบิต ของข้อมูล ณ ตำแหน่งนั้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น