การคัดแยกแพ็กเก็ตแบบ 2 มิติ โดยการจัดกลุ่มพรีฟิก

Abstract

บทคัดย่อ

งานวิจัยนี้นำเสนอโครงสร้างข้อมูลและขั้นตอนวิธีในการคัดแยกแพ็กเก็ตแบบ 2 มิติ โดยการจัด filter ออกเป็นกลุ่มตามค่า prefix ซึ่งทำให้โครงสร้างข้อมูลสามารถรองรับ filter set ที่มีขนาดใหญ่และรองรับ filter set ได้ทุกประเภท ขั้นตอนวิธีในการคัดแยกแพ็กเก็ตได้ถูกออกแบบให้การคัดแยกแต่ละมิติทำคู่ขนานไปพร้อม ๆ กัน จึงทำให้การคัดแยกแพ็กเก็ตสามารถทำได้อย่างรวดเร็ว จากผลการทดสอบทั้งในแง่ของการใช้หน่วยความจำของโครงสร้างข้อมูล และการวัดจำนวนครั้งที่ติดต่อหน่วยความจำเพื่ออ่านข้อมูลขณะทำการคัดแยกแพ็กเก็ต โดยใช้ benchmark ที่มีชื่อว่า Classbench ซึ่งเป็นเครื่องมือในการสร้าง filter set จำลอง โดยเปรียบเทียบผลกับงานวิจัยอื่น ๆ พบว่าโครงสร้างข้อมูลที่ filter set ขนาด 50,000 filters ใช้หน่วยความจำสูงสุดเพียงแค่ 5 MB และมีจำนวนครั้งที่ติดต่อหน่วยความจำสูงสุดเพียง 26 ครั้ง ต่อการคัดแยก 1 แพ็กเก็ต โดยขนาดหน่วยความจำของโครงสร้างข้อมูลและจำนวนครั้งที่ติดต่อหน่วยความจำในการคัดแยกแพ็กเก็ตเพิ่มขึ้นเพียงเล็กน้อยเมื่อจำนวน filter ของ filter set เพิ่มขึ้น จึงทำให้งานวิจัยนี้มีสมบัติในเรื่องของ scalability นอกจากนี้ เนื่องจากขั้นตอนวิธีในการแมทช์ค่า filter ไม่ซับซ้อน จึงทำให้งานวิจัยนี้สามารถนำไปประยุกต์เพื่อออกแบบและติดตั้งลงในอุปกรณ์ฮาร์ดแวร์ได้ด้วยเทคโนโลยีที่มีอยู่ในปัจจุบันได้

คำสำคัญ : การคัดแยกแพ็กเก็ต; การจัดกลุ่มพรีฟิก; การแมทช์ค่าฟิลเตอร์; การแมทช์พรีฟิก

Abstract

Nowadays, packet classification is still an essential methodology to serve the needs of Internet applications. Several researches have overcome speed of packet classification but none of them has been scalable for over tens of thousands filter sets. This paper proposes a two-dimensional packet classification scheme. Based on grouping prefix fields of filters, the data structure takes very small memory requirements. The packet classification rate is also fast since each dimension is classified in a parallel manner. The scheme performance is measured by using filter sets generated from the well-known benchmark called ClassBench. Based on experimental results, the memory taken for the data structures is about 5 MB and it takes at most 26 memory accesses when classifying a packet. Also, the scheme can apply to all types of filter sets. In summary, it is found that the size of the filter set does not have any significant impact on the scheme performance. The proposed scheme tremendously improves performance of packet classification in terms of scalability and can be easily implemented with today’s technology.

Keywords: packet classification; prefix grouping, filter match, prefix match