Tài liệu Thiết kế và thực thi lõi ip phân luồng dữ liệu trên fpga

i Mục lục Mục lục i Danh mục hình vẽ ii Danh mục bảng biểu iii MỞ ĐẦU 1 TỔNG QUAN VỀ PHÂN LUỒNG DỮ LIỆU 3 3 1.1 Giới thiệu chƣơng . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 3 1.2 Khái niệm phân luồng dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .... . 3 1.3 Vai trò của phân luồng dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … 3 1.4 Các chức năng chính của phân luồng dữ liệu . . . . . . . . . . . .. . . . . . . . . 4 1.5 2 1 1.4.1 Phân loại luồng dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 5 1.4.2 Chính sách lƣu lƣợng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..... 8 1.4.3 Định hình luồng lƣu lƣợng . . . . . . . . . . . . . . . . . . . . .. . . . . . … 8 1.4.4 Lập lịch gói tin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9 1.4.5 Quản lý bộ đệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..10 Kết luận chƣơng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 CƠ SỞ LÝ THUYẾT CÁC THUẬT TOÁN LẬP LỊCH 12 2.1 Giới thiệu chƣơng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …12 2.2 Thuật toán First Come First Serve . . . . . . . . . . . . . . . . . . . . . . . . . . . … 12 2.3 Thuật toán lập lịch Max-Min . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …12 2.4 Thuật toán Round-Robin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …14 2.5 Thuật toán Weighted Round-Robin . . . . . . . . . . . . .. . . . . . . . . . . . . . ..15 2.6 Thuật toán Deficit Round-Robin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..16 2.7 Kết luận chƣơng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...18 THIẾT KẾ LÕI IP PHÂN LUỒNG DỮ LIỆU 19 3.1 Tổng quan quá trình thiết kế . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . …19 3.2 Thiết kế kiến trúc lõi IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …. 19 3.3 Thiết kế khối quản lý bộ đệm (Buffer Management) . . . . . . . . . . . . . . . 22 ii 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.3.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … 22 3.3.2 Sơ đồ kết nối . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ….23 3.3.3 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .... . 23 Thiết kế khối xử lý ghi gói tin vào hàng đợi (Enqueue) . . . . . . . . . . . . 24 3.4.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … 24 3.4.2 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...25 3.4.3 Máy trạng thái . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..27 Thiết kế khối xử lý đọc gói tin từ hàng đợi ra (Dequeue) ... . . . . . . . . . . 28 3.5.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...28 3.5.2 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 28 3.5.3 Máy trạng thái . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..31 Thiết kế khối hỗ trợ giao tiếp bộ nhớ (Memory Accessor) . . . . . . . . ... 32 3.6.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 32 3.6.2 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . ... 32 3.6.3 Máy trạng thái . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34 Thiết kế khối quản lý hàng đợi (Queue Management) . . . . . . . . . . . . . 36 3.7.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36 3.7.2 Cấu Trúc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 38 3.7.3 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.7.4 Máy Trạng Thái . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 41 Thiết kế khối cấp phát bộ nhớ động(Dynamic Allocator) . . . . . . . . . . . 44 3.8.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 44 3.8.2 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.8.3 Máy trạng thái . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. 46 Thiết kế khối lập lịch(Scheduler) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 48 3.9.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 48 3.9.2 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.9.3 Máy trạng thái khối Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . 50 Thiết kế khối chống tắc nghẽn(Congestion) . . . . . . . . . . . . . . . . . . . . . 54 3.10.1 Chức năng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.10.2 Mô tả tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Kết luận chƣơng . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 59 iii 4 MÔ PHỎNG VÀ THỰC HIỆN LÕI IP PHÂN LUỒNG DỮ LIỆU TRÊN NỀN FPGA 60 4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...60 4.2 Yêu cầu phần mềm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60 4.3 Kết quả tổng hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .61 4.4 Kết quả mô phỏng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.5 Năng lực xử lý của lõi IP . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 65 4.6 Thực hiện trên nền FPGA . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 65 4.7 4.6.1 Công nghệ FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.6.2 Phần cứng sử dụng . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . .. 67 4.6.3 Quá trình thực hiện . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 68 4.6.4 Kiểm tra thực tế . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 70 Kết luận chƣơng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Kết luận và hƣớng phát triển Tài liệu tham khảo 72 iv THIẾT KẾ VÀ THỰC THI LÕI IP PHÂN LUỒNG DỮ LIỆU TRÊN FPGA Học viên: Võ Thành Văn. Chuyên ngành: Kỹ thuật Điện tử. Mã số: ...........Khóa: K31. Trƣờng Đại học Bách khoa - ĐHĐN Tóm tắt – Phân luồng dữ liệu là một kỹ thuật đƣợc áp dụng để giải quyết nhiều bài toán, đặc biệt là trong bài toán đảm bảo chất lƣợng dịch vụ QoS trong các thiết bị mạng hiện nay. Trong đề tài này, tác giả sẽ trình bày các khái niệm cùng các chức năng cơ bản liên quan đến phân luồng dữ liệu. Bên cạnh đó, còn đề cập đến các thuật toán lập lịch, chỉ rõ ƣu nhƣợc điểm cùng cách thực hiện trên phần cứng các thuật toán, từ đó đề xuất thiết kế và thực hiện chức năng phân luồng dữ liệu trên FPGA. Kết quả tổng hợp của lõi IP đƣợc thực hiện trên board mạch Zynq ZC706 cho thấy lõi IP chỉ chiếm 1% số thanh ghi cùng 4% số bảng tìm kiếm LUT trong tổng số tài nguyên của board, và tần số clock tối đa đạt đƣợc là 200MHz. Cuối cùng, tác giả đã tóm tắt các kết quả đạt đƣợc và đƣa ra các hƣớng phát triển tiếp theo. Từ khóa - Phân luồng dữ liệu; Lập lịch; QoS; FPGA; Thiết bị mạng DESIGN AND IMPLEMENT TRAFFIC MANAGEMENT IP CORE ON FPGA Abstract – Traffic management is a technique used to solve many problems, especially in quality of service (QoS) for today‟s networking devices. In this thesis, we present fundamental definetions and functions related to traffic management. In addition, several scheduling algorithms are considered in order to compare their advantages and disadvantages and the ability to implement into hardware. Based on these principles, we describe the design and implementation of the Traffic Management IP Core on FPGA. The synthesis results using Zynq ZC706 board showed that it consumes 1% of slice registers and 4% of slice LUTs in hardware resource, and the maximum frequency is up to 200MHz. At the end of the thesis, we summarize the key results achieved and provide perspectives of the work. Key words - Traffic management; Scheduling; QoS; FPGA; Networking devic. v Danh mục hình vẽ 1.1 Sơ đồ khối của phân luồng dữ liệu trong router/switch . . . . . . . 5 1.2 Trƣờng CoS trong 802.1Q header . . . . . . . . . . . . . . . . . . 6 1.3 IP Precedence và DSCP trong header của gói tin IPv4 . . . . . . . 6 1.4 Bộ chính sách lƣu lƣợng . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Cách hoạt động của bộ định hình lƣu lƣợng . . . . . . . . . . . . . 8 1.6 Cơ chế hoạt động của mô hình thùng thẻ - Token Bucket . . . . . . 9 2.1 Ví dụ về thuật toán công bằng Max-Min . . . . . . . . . . . . . . . 13 2.2 Thực thi thuật toán Round-robin . . . . . . . . . . . . . . . . . . . 14 2.3 Cách thức quản lý FQ . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Thực hiện thuật toán WRR trên phần cứng . . . . . . . . . . . . . 16 2.5 Lƣợt rà soát Round robin thứ nhất . . . . . . . . . . . . . . . . . . 17 2.6 Lƣợt rà soát Round robin thứ hai . . . . . . . . . . . . . . . . . . 18 3.1 Sơ đồ kết nối lõi IP phân luồng dữ liệu . . . . . . . . . . . . . . . . 19 3.2 Sơ đồ kết nối khối Quản lý Bộ đệm . . . . . . . . . . . . . . . . . . 22 3.3 Máy trạng thái của Khối Enqueue . . . . . . . . . . . . . . . . . . 27 3.4 FSM của khối Dequeue . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5 Máy trạng thái wr_state . . . . . . . . . . . . . . . . . . . . . . . . 35 3.6 Máy trạng thái rd_state . . . . . . . . . . . . . . . . . . . . . . . . 36 3.7 Cấu trúc dữ liệu quản lý hàng đợi . . . . . . . . . . . . . . . . . . 37 3.8 Sơ đồ cấu trúc module QueueManagement . . . . . . . . . . . . . 38 3.9 Máy trạng thái module QueueManagement . . . . . . . . . . . . . 41 3.10 Máy trạng thái con của DEACTIVE . . . . . . . . . . . . . . . . . 42 3.11 Máy trạng thái tƣơng ứng lệnh ACTIVE . . . . . . . . . . . . . . 43 3.12 Tổ chức dữ liệu một ô nhớ của khối DynamicAllocator . . . . . . 44 3.13 Máy trạng thái của khối DynamicAllocator . . . . . . . . . . . . . 47 3.14 Máy trạng thái con của trạng thái ACTIVE . . . . . . . . . . . . . 47 3.15 Sơ đồ tín hiệu khối Scheduler . . . . . . . . . . . . . . . . . . . . . 49 3.16 Máy trạng thái wr_dq_state . . . . . . . . . . . . . . . . . . . . . . 51 3.17 Máy trạng thái dq_empty_state . . . . . . . . . . . . . . . . . . . . 52 vi 3.18 Máy trạng thái schedule_state . . . . . . . . . . . . . . . . . . . . 53 3.19 Sơ đồ tín hiệu khối Congestion . . . . . . . . . . . . . . . . . . . . 55 3.20 Sơ đồ tín hiệu khối WRED . . . . . . . . . . . . . . . . . . . . . . 56 3.21 Máy trạng thái của trƣờng hợp xử lý gói tin đến . . . . . . . . . . 58 3.22 Máy trạng thái của trƣờng hợp xử lý gói tin đi . . . . . . . . . . . 59 4.1 Kết quả tổng hợp phần cứng . . . . . . . . . . . . . . . . . . . . . 62 4.2 Mô hình kiểm tra mô phỏng . . . . . . . . . . . . . . . . . . . . . 63 4.3 Kết quả mô phỏng ở ngõ ra 2 . . . . . . . . . . . . . . . . . . . . . 64 4.4 Kết quả mô phỏng trên Modelsim . . . . . . . . . . . . . . . . . . 64 4.5 Cấu trúc tổng thể của một FPGA . . . . . . . . . . . . . . . . . . . 66 4.6 Kit phát triển Zynq ZC706 . . . . . . . . . . . . . . . . . . . . . . 67 4.7 Kết nối lõi IP và các thành phần vào hệ thống . . . . . . . . . . . . 69 4.8 Kết quả của quá trình tạo file bitstream . . . . . . . . . . . . . . . 69 4.9 Mô hình kết nối . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 vii Danh mục bảng biểu 1.1 Bảng các vấn đề khi không có QoS . . . . . . . . . . . . . . . . . . 4 1.2 Bảng giá trị IP precedence . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Bảng giá trị DSCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1 Bảng mô tả tín hiệu lõi IP . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Bảng mô tả tín hiệu module BuffMan . . . . . . . . . . . . . . . . 23 3.3 Bảng mô tả tín hiệu Khối Enqueue . . . . . . . . . . . . . . . . . . 25 3.4 Bảng mô tả tín hiệu module Dequeue . . . . . . . . . . . . . . . . 28 3.5 Bảng mô tả tín hiệu Khối Memory Accessor . . . . . . . . . . . . . 32 3.6 Bảng mô tả lệnh khối QueueManagement . . . . . . . . . . . . . . 37 3.7 Bảng mô tả tín hiệu module QueueManagement . . . . . . . . . . 39 3.8 Bảng mô tả lệnh khối DynamicAllocator . . . . . . . . . . . . . . 44 3.9 Bảng mô tả tín hiệu khối DynamicAllocator . . . . . . . . . . . . . 45 3.10 Bảng mô tả tín hiệu Khối Scheduler . . . . . . . . . . . . . . . . . 50 3.11 Bảng mô tả tín hiệu Khối Congestion . . . . . . . . . . . . . . . . 55 3.12 Bảng mô tả tín hiệu Khối WRED . . . . . . . . . . . . . . . . . . . 56 4.1 Kết quả thực nghiệm khi thay đổi tốc độ truyền dữ liệu . . . . . . 71 viii Danh mục từ viết tắt CIR Committed Information Rate CoS Class of Service DQ Departure Queue DRR Deficit Round Robin DSCP Differentiated Services Code Point FPGA Field-Programmable Gate Array FQ Flow Queue HDL Hardware Description Language HTTP Hypertext Transfer Protocol IP Internet Protocol OSI Open Systems Interconnection PQ Priority Queueing RAM Random Access Memory QoS Quality of Service RED Random Early Detection RFC Request for Comments RTL Register Transfer Language RTP Real Time Protocol WFQ Weighted Fair Queueing WRED Weighted Random Early Detection WRR Weighted Round Robin 1 MỞ ĐẦU Tính cấp thiết của đề tài Trong giai đoạn đầu của dịch vụ Internet, do băng thông và các tài nguyên khác đủ để cung cấp cho các ứng dụng trong mạng nên vấn đề phân biệt và ƣu tiêncho các gói tin chƣa đƣợc quan tâm. Ban đầu, các nhà cung cấp dịch vụ đƣa ra mô hìnhbesteffort, trong đó tất cả các khách hàng sẽ đƣợc đối xử nhƣ nhau và chỉ khác nhauở loại kết nối. Đây là dịch vụ phổ biến trên mạng Internet hay mạng IP nói chung. Nhƣng khi internet càng ngày càng phát triển và phát triển thêm các dịch vụ HTTP, voice, video. . . thì điều này sẽ làm cho chất lƣợng của các dịch vụ giảm đi rõ rệt vì độ trễ lớn, độ biến động trễ lớn và không đủ băng thông để truyền, phƣơng án tăng băng thông của mạng cũng không giải quyết đƣợc vấn đề này mà lại còn rất tốn kém. Chính vì vậy, giải pháp về phân luồng dữ liệu ra đời để đảm bảo các ứng dụng thời gian thực chạy đƣợc trên Internet và các ứng dụng truyền thống đƣợc bảo đảm chất lƣợng tốt hơn. Bên cạnh đó, các thiết bị mạng nhƣ router, firewall đã đƣợc sử dụng rộng rãi tại nhiều gia đình, cơ quan, doanh nghiệp tại Việt Nam. Tuy nhiên, toàn bộ các thiết bị này hiện đƣợc nhập khẩu từ nƣớc ngoài, do các nhà sản xuất nƣớc ngoài cung cấp hoàn toàn, dẫn đến một nguy cơ lệ thuộc và mất quyền kiểm soát rất lớn đối với tầng thông tin quốc gia khi xảy ra sự cố. Vì vậy, từng bƣớc tạo ra các sản phẩm do chính công dân Việt Nam nghiên cứu sản xuất để bảo đảm an toàn thông tin là hết sức cần thiết. Xuất phát từ những yêu cầu trên, luận văn của em nghiên cứu về đề tài: “Thiết kế và thực thi lõi IP phân luồng dữ liệu trên FPGA” Mục tiêu nghiên cứu Nghiên cứu thiết kế kiến trúc lõi IP phân luồng dữ liệu trên FPGA, thực hiệnbằng ngôn ngữ mô tả phần cứng Verilog HDL. Đối tƣợng và phạm vi nghiên cứu  Mô hình và kĩ thuật phân luồng dữ liệu.  Ngôn ngữ mô tả phần cứng Verilog HDL và công nghệ FPGA.  Thực hiện và đánh giá lõi IP phân luồng dữ liệu dựa trên công cụ mô phỏng 2 ModelSim và trên nền tảng FPGA. Phƣơng pháp nghiên cứu  Nghiên cứu lý thuyết: - Tìm hiểu và phân tích các tài liệu về phân luồng dữ liệu. - Nghiên cứu kiến trúc lõi IP phân luồng dữ liệu, đặc biệt là các thành phần có liên quan nhƣ phƣơng pháp quản lý hàng đợi, thuật toán lập lịch.  Nghiên cứu thực nghiệm: - Sử dụng ngôn ngữ mô tả phần cứng Verilog HDL để mô tả các phƣơng pháp, thuật toán. - Mô phỏng mức RTL trên công cụ mô phỏng ModelSim, thực thi trên nền FPGA và đánh giá kết quả. Ý nghĩa khoa học và thực tiễn của đề tài Đề tài tạo ra lõi IP phân luồng dữ liệu, đƣợc ứng dụng trong các thiết bị mạng,góp phần thực tiễn vào việc nâng cao chất lƣợng dịch vụ của các thiết bị này, đồng thời làm chủ đƣợc công nghệ giúp đảm bảo an toàn thông tin. Kết cấu của luận văn Luận văn gồm các phần chính sau đây:     Chƣơng 1: TỔNG QUAN VỀ PHÂN LUỒNG DỮ LIỆU. Chƣơng 2: CƠ SỞ LÝ THUYẾT CÁC THUẬT TOÁN LẬP LỊCH. Chƣơng 3: THIẾT KẾ LÕI IP PHÂN LUỒNG DỮ LIỆU. Chƣơng 4: MÔ PHỎNG VÀ THỰC HIỆN LÕI IP PHÂN LUỒNG DỮ LIỆU TRÊN NỀN FPGA.  KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI  PHỤ LỤC 3 Chƣơng 1 TỔNG QUAN VỀ PHÂN LUỒNG DỮ LIỆU 1.1. Giới thiệu chƣơng Trong chƣơng này sẽ trình bày khái niệm về phân luồng dữ liệu cũng nhƣ vai trò của phân luồng dữ liệu trong hệ thống mạng internet ngày nay. Bên cạnh đó, sơ đồ khối và các khối chức năng chính của phân luồng dữ liệu cũng đƣợc giới thiệu để có cái nhìn khái quát và tổng quan hơn. 1.2. Khái niệm phân luồng dữ liệu Phân luồng dữ liệu là công việc đƣợc sử dụng trong nhiều ứng dụng, nhằm mục đích phân loại các gói dữ liệu vào các tập dữ liệu khác nhau để xử lý tiếp theo; mỗi tập dữ liệu có một quy tắc hành động riêng, đặc biệt là trong chức năng nâng cao chất lƣợng dịch vụ (QoS - Quality of Service) của hệ thống mạng ngày nay. Tiêu chuẩn mới nhất của phân luồng dữ liệu đƣợc định nghĩa trong các tài liệu RFC 5777 [8] và RFC 7640 [9]. 1.3. Vai trò của phân luồng dữ liệu Ngày nay, Internet phát triển rất nhanh kèm theo đó là sự phát triển nhiều loại dịch vụ khác nhau. Có thể kể đến các dịch vụ sử dụng các ứng dụng đa phƣơng tiện hoặc các ứng dụng thời gian thực nhƣ thoại IP (IP Telephony), hệ thống hội nghị video (video conference system), truyền hình trực tiếp video (livestream) là các ứng dụng mới cần nhiều băng thông hơn rất nhiều so với các ứng dụng đã đƣợc sử dụng rất sớm trên Internet. Mặt khác các ứng dụng này yêu cầu việc truyền dữ liệu đi qua mạng phải liên tục, độ trễ thấp. Chất lƣợng của các ứng dụng thoại phụ thuộc vào chất lƣợng đƣờng truyền kết nối từ đầu cuối đến đầu cuối. Các dấu hiệu của tín hiệu thoại không đƣợc đảm bảo chất lƣợng có thể kể đến nhƣ truyền lỗi, nhiễu tín hiệu, tiếng vọng,... Ngay cả việc truyền dữ liệu thời gian thực sử dụng giao thức thời gian thực RTP (Real Time Protocol) vẫn phụ thuộc vào việc tận dụng các tài nguyên đƣợc phân phát trên cơ sở giao thức IP. Bảng 1.1 cho thấy các dấu hiệu của mạng khi không có cơ chế và các kỹ thuật để đảm bảo chất lƣợng dịch vụ: 4 Bảng 1.1: Bảng các vấn đề khi không có QoS Kiểu lƣu lƣợng Voice Các vấn đề khi không có QoS Voice nghe khó hiểu Voice không liên tục, tiếng nói bị méo Ngƣời gọi không biết ngƣời nhận kết thúc khi nào hay kết thúc chƣa Video Hình ảnh hiển thị chập chờn Âm thanh không đồng bộ với video Sự di chuyển của hình ảnh chậm lại Data Dữ liệu đƣợc chuyển đến khi nó không còn giá trị nữa Dữ liệu phản hồi không đúng so với ban đầu Thời gian truyền bị gián đoạn làm cho ngƣời dùng thất vọng và từ bỏ hoặc thực hiện lại dịch vụ Chính vì vậy phân luồng dữ liệu ra đời để giải quyết các vấn đề trên, thông qua việc phân chia các ứng dụng thành các luồng dữ liệu khác nhau, áp dụng các kỹ thuật lập lịch gói tin, giúp đảm bảo đƣợc chất lƣợng của các dịch vụ chạy trên Internet. 1.4. Các chức năng chính của phân luồng dữ liệu Hình 1.1 biểu diễn vị trí của phân luồng dữ liệu trong một router/switch với 2 cổng vào, trong đó cả ngõ vào và ngõ ra của mỗi cổng đều sử dụng chức năng phân luồng dữ liệu. Các khối chức năng chính của phân luồng dữ liệu đƣợc mô tả nhƣ sau:  Phân loại luồng dữ liệu (Traffic classification).  Chính sách lƣu lƣợng (Traffic policing).  Định hình luồng lƣu lƣợng (Traffic shaping).  Lập lịch (Traffic scheduling).  Quản lý bộ đệm (Buffer Management). Tại ngõ vào của mỗi cổng, chức năng giới hạn tốc độ xác định luồng dữ liệu có phùhợp với các chính sách lƣu lƣợng đã đề ra hay không, sau đó khối quản lý bộ đệm xácđịnh gói tin đó đƣợc cho phép đi vào hay bị loại bỏ và nếu bị loại bỏ thì sẽ loại bỏ theophƣơng pháp nào. Bên cạnh đó, khối lập lịch gói tin và tối ƣu hóa luồng lƣu lƣợng xác định gói tin nào sẽ đƣợc tháo ra tiếp theo và đƣợc gửi tới cổng nào thông qua Fabric, đồng thời kiểm soát tốc độ truyền của gói tin trƣớc khi đi ra khỏi router. 5 Hình 1.1: Sơ đồ khối của phân luồng dữ liệu trong router/switch Phân loại luồng dữ liệu Phân loại luồng dữ liệu là phƣơng pháp đƣợc sử dụng để nhóm các gói tin IP lại với nhau theo lớp dịch vụ. Trong mạng, các gói tin đƣợc lựa chọn dựa trên các trƣờng ở phần header của gói tin IP, các trƣờng này cũng đƣợc sử dụng cho việc đánh dấu gói tin nhƣ: Giao diện đầu vào, IP Precedence, DSCP, địa chỉ nguồn hoặc địa chỉ đích và các ứng dụng. Có hai kiểu phân loại luồng dữ liệu: 1.4.1.  Phân loại đa trƣờng (Multi Field classification) – MF  Phân loại kết hợp hành vi (Behavior Aggregate classification) – BA Phân loại đa trƣờng MF Trong phƣơng pháp phân loại đa trƣờng, các gói tin đƣợc phân loại dựa trên tổ hợp các giá trị của một hoặc nhiều trƣờng trong phần header của gói tin IP. Thông thƣờng sẽ dựa theo các trƣờng: địa chỉ MAC nguồn, địa chỉ MAC đích, địa chỉ IP nguồn, địa chỉ IP đích, port nguồn, port đích và giao thức (protocol) để phục vụ tốt cho việc phân loại này. Phân loại kết hợp hành vi BA Phƣơng pháp phân loại kết hợp hành vi thực hiện việc phân loại gói tin dựa trên trƣờng IP Precedence hoặc rộng hơn nữa là trƣờng chứa giá trị DSCP trong phần header của gói tin IPv4. Bên cạnh đó, ở tầng liên kết dữ liệu theo mô hình OSI, trƣờng CoS trong chuẩn 802.1Q cũng đƣợc sử dụng với mục đích nhƣ trên. 6 Hình 1.2: Trƣờng CoS trong 802.1Q header Trƣờng IP Precedence là 3 bit đầu tiên trong trƣờng ToS (Type of Service) trong header của gói tin IPv4. Với 3 bit của trƣờng IP Precedence chúng ta có 8 giá trị tƣơng ứng với 8 mức ƣu tiên khác nhau đối với các gói tin IPv4, dựa trên mức độ ƣu tiên đó, các bộ định tuyến đƣa ra các quyết định chuyển tiếp các gói tin qua mạng. Hình 1.3: IP Precedence và DSCP trong header của gói tin IPv4 Bảng giá trị IP precedence đƣợc xác định theo RFC 791 [10] nhƣ sau: Bảng 1.2: Bảng giá trị IP precedence Giá trị Mô tả 000 (0) Bình thƣờng (Routine or Best Effort) 001 (1) Ƣu tiên (Priority) 010 (2) Tức thời (Immediate) 011 (3) Truyền nhanh (Flash) 100 (4) Truyền cực nhanh cho phép ghi đè (Flash Override) 7 101 (5) Tới hạn, tối đa (Critical -mainly used for Voice RTP.) 110 (6) Internet 111 (7) Điều khiển mạng (Network) Càng ngày, sự đa dạng về các dịch vụ ngày càng gia tăng, khi 3 bit của trƣờng IP Precedence không đủ để phân loại cụ thể và chi tiết các lớp dịch vụ nữa thì trƣờng DSCP ra đời để bổ sung cho sự phát triển đó. Trƣờng DSCP sử dụng 6 bit trong trƣờng ToS trong header của gói tin IPv4, mở rộng 3 bit ban đầu của trƣờng IP Precedence. Lúc đó, chuẩn RFC 2475 đã quy định các giá trị của trƣờng DSCP nhƣ sau Bảng 1.3: Bảng giá trị DSCP Giá trị Mô tả Giá trị IP Precedence tƣơng đƣơng 101 110 High Priority (EF) 101 - Critical 000 000 Best Effort 000 - Routine 001 010 AF11 001 - Priority 001 100 AF12 001 - Priority 001 110 AF13 001 - Priority 010 010 AF21 010 - Immediate 001 100 AF11 010 - Immediate 010 110 AF22 010 - Immediate 011 010 AF31 011 - Flash 011 100 AF32 011 - Flash 011 110 AF33 011 - Flash 100 010 AF41 100 - Flash Override 100 100 AF42 100 - Flash Override 8 100 110 1.4.2. AF43 100 - Flash Override Chính sách lưu lượng Chính sách lƣu lƣợng luôn theo dõi, điều chỉnh lƣu lƣợng truy cập mạng cho phù hợp với hợp đồng lƣu lƣợng, và nếu nhƣ đƣợc yêu cầu, nó sẽ làm giảm hoặc thậm chí vứt bỏ lƣu lƣợng vƣợt quá ngƣỡng nhằm mục đích thực thi chính sách phù hợp trên đƣờng truyền. Khối chính sách lƣu lƣợng bao gồm các bộ đo các lƣu lƣợng để xác định lƣu lƣợng đầu vào và đầu ra, trên cơ sở đó, áp dụng chính sách điều khiển tốc độ lƣu lƣợng phù hợp với đầu ra bởi bộ đánh dấu gói tin. Các gói tin có thể bị loại bỏ nếu không phù hợp với chính sách lƣu lƣợng. Hình 1.4 biểu diễn sơ đồ khối của bộ chính sách lƣu lƣợng và hai khối nhỏ của nó là bộ đo lƣu lƣợng và bộ đánh dấu gói tin. Hình 1.4:Bộ chính sách lƣu lƣợng Thông thƣờng, chính sách lƣu lƣợng kiểm tra tốc độ của lƣu lƣợng đi vào theo một tham số lƣu lƣợng chính nhƣ: Tốc độ thông tin cam kết (CIR - Committed Information Rate) và tốc độ thông tin đỉnh (PBS - Peak Burst Size), kích thƣớc bùng nổ cam kết (CBS - Committed Burst Size) và kích thƣớc bùng nổ vƣợt ngƣỡng (EBS Excess Burst Size) [12] [13] [14]. 1.4.3. Định hình luồng lưu lượng Hình 1.5: Cách hoạt động của bộ định hình lƣu lƣợng 9 Các công cụ định hình lƣu lƣợng (Traffic Shaping -TS) làm chậm các gói tin khi các gói đi ra khỏi một router sao cho tốc độ truyền tổng thể không vƣợt quá một giới hạn đã định nghĩa. Nếu lƣu lƣợng đầu vào có độ bùng nổ cao, thì luồng lƣu lƣợng phải có bộ đệm để đầu ra giảm sự bùng nổ và mềm hơn. Bằng cách này, định hƣớng lƣu lƣợng làm cho luồng lƣu lƣợng đƣợc điều chỉnh theo dạng lƣu lƣợng đã xác định trƣớc. Việc điều chỉnh tốc độ lƣu lƣợng giuống nhƣ một quá trình “truyền và nghỉ”, router làm việc luân phiên giữa hai trạng thái: truyền gói tin và giữ gói tin trong hàng đợi. Bộ định hình lƣu lƣợng trì hoãn một lƣu lƣợng lớn vào hàng đợi định hình khi lƣu lƣợng đó vƣợt quá mức cho phép đƣợc coi là Committ Information Rate – CIR. Hình 1.6: Cơ chế hoạt động của mô hình thùng thẻ - Token Bucket Để làm điều này, bộ định hình lƣu lƣợng sử dụng mô hình thùng thẻ - token bucket để xác định lƣu lƣợng truy cập vƣợt quá mức giới hạn đã đƣợc cấu hình với CIR. Mỗi lần một gói tin xếp vào hàng đợi, bộ định hình lƣu lƣợng sẽ so sánh kích thƣớc của gói tin với kích thƣớc hiện tại của token bucket. Nếu kích thƣớc gói tin nhỏ hơn hoặc bằng khoảng trống còn trong token bucket thì gói tin đó đƣợc gửi đi. Ngƣợc lại, nếu vƣợt quá nó sẽ bị trì hoãn trong hàng đợi định hình. 1.4.4. Lập lịch gói tin Thực hiện phân loại lƣu lƣợng trong thiết bị mạng bằng cách định hƣớng các gói tin đến các hàng đợi khác nhau và áp dụng thuật toán để gửi các gói tin ứng với độ ƣu tiên của các hàng đợi đó. Các thuật toán lập lịch sẽ đƣợc trình bày rõ trong Chƣơng 2 - Cơ sở lý thuyết các thuật toán lập lịch. 10 1.4.5. Quản lý bộ đệm Thực hiện công việc cung cấp bộ nhớ cho từng hàng đợi, quản lý tình trạng của các hàng đợi và đƣa ra thông báo để loại bỏ gói tin khi hàng đợi chuẩn bị đầy nhằm mục đích chống tắc nghẽn. Một bộ quản lý bộ đệm thƣờng bao gồm các hoạt động:  Thêm gói tin vào hàng đợi khi hàng đợi chƣa đầy.  Loại bỏ gói tin nếu hàng đợi đã đầy.  Xóa bỏ gói tin khi đƣợc yêu cầu bởi bộ lập lịch. Mục đích chính của hàng đợi là điều khiển lƣu lƣợng, chống tắc nghẽn trong mạng, đặc biệt là tại các nút cổ chai. Kĩ thuật quản lý bộ đệm trƣớc đây là cấp phát một kích thƣớc lớn nhất cho mỗi hàng đợi, các gói tin đến sẽ đƣợc đƣa vào trong hàng đợi cho đến khi hàng đợi đầy, sau đó nếu còn có gói đến thì sẽ loại bỏ các gói mới tới này. Khi số lƣợng các gói trong hàng đợi giảm đi sau mỗi lần đƣợc lập lịch tháo ra thì lúc đó, hàng đợi mới nhận tiếp các gói mới. Đây cũng chính là kĩ thuật “loại bỏ phần đuôi” (drop tail). Tuy nhiên cách này có hai hạn chế:  Kĩ thuật này không có sự ƣu tiên lƣu lƣợng nên khi có luồng dữ liệu quan trọng đến hàng đợi trong lúc hàng đợi đang bị đầy thì gói tin đó vẫn bị loại bỏ.  Thƣờng thì các luồng lƣu lƣợng đến hàng đợi dƣới dạng bó. Khi hàng đợi đầy thì bất kì luồng nào đến cũng đều bị loại bỏ cho tới khi số gói trong hàng đợi giảm xuống. Kĩ thuật này sẽ loại bỏ các bó thông tin chứ không chỉ là các gói, do đó việc mất mát thông tin rất lớn. Để giải quyết các nhƣợc điểm của quản lý bộ đệm nêu trên và chống tắc nghẽn, các phƣơng pháp thƣờng đƣợc áp dụng là RED (mở rộng WRED), hàng đợi cân bằng có trọng số (WFQ), hàng đợi ƣu tiên (PQ),... Thuật toán RED [1] đƣợc phát minh bởi Sally Floyd và Van Jacobson, dựa trên tính toán kích thƣớc hàng đợi trung bình để đánh giá tắc nghẽn và gửi phản hồi nhằm phát hiện sớm để tránh tắc nghẽn. Do đó, RED đƣợc sử dụng để phát hiện ra tắc nghẽn ngay khi nó mới bắt đầu hình thành để duy trì mạng trong miền độ trễ thấp. RED đƣợc chia thành 2 phần chính: dự báo tắc nghẽn và loại bỏ gói tin. Dựa vào đặc điểm gói tin, RED thực hiện ƣớc lƣợng kích thƣớc trung bình của hàng đợi và quyết định loại bỏ hay cho gói tin đi vào. Nội dung của thuật toán đƣợc trình bày nhƣ sau: 11 Algorithm 1 Thuật toán RED for mỗi gói tin do tính toán kích thƣớc trung bình của queue 𝑎𝑣𝑔; if 𝑚𝑖𝑛𝑡𝑕 ≤ 𝑎𝑣𝑔 ≤ 𝑚𝑎𝑥𝑡𝑕 then tính toán xác suất loại bỏ 𝑝𝑎 ; if 𝑝𝑎 = 1 then loại bỏ gói tin; else if 𝑚𝑎𝑥𝑡𝑕 ≤ 𝑎𝑣𝑔 then loại bỏ gói tin; else cho phép gói tin đi vào bộ đệm; Trong đó, 𝑚𝑖𝑛𝑡𝑕 và 𝑚𝑎𝑥𝑡𝑕 lần lƣợt là các giá trị ngƣỡng thấp nhất và cao nhất của mỗi hàng đợi. Cơ chế RED dựa vào quyết định loại bỏ gói tin ngẫu nhiên khi dung lƣợng bộ đệm vƣợt quá ngƣỡng cho trƣớc, vì vậy các luồng dữ liệu với dung lƣợng lớn sẽ bị loại bỏ một số lƣợng lớn gói tin trong trƣờng hợp tắc nghẽn. Do đó, thuật toán WRED đƣợc bổ sung nhằm mục đích xử lý các luồng dữ liệu theo tỷ lệ loại bỏ gói tin khác nhau để đảm bảo rằng, với các luồng dữ liệu quan trọng thì xác suất gói tin bị loại bỏ thấp hơn các luồng dữ liệu khác. 1.5. Kết luận chƣơng Trong chƣơng này, ta đã có cái nhìn tổng quan về phân luồng dữ liệu cũng nhƣ các thành phần tạo nên nó. Chƣơng sau sẽ trình bày rõ ràng và chi tiết về các thuật toán lập lịch, một phần rất quan trọng trong phân luồng dữ liệu và cách thực hiện từng thuật toán trên phần cứng. 12 Chƣơng 2 CƠ SỞ LÝ THUYẾT CÁC THUẬT TOÁN LẬP LỊCH 2.1. Giới thiệu chƣơng Bộ lập lịch sẽ quyết định xem hàng đợi nào đƣợc phép tháo gói tin ra, gói tin ra sẽ đƣợc đƣa tới giao diện đầu ra nào. Các router truyền thống chỉ có một hàng đợi đơn cho một đầu ra cố định, do vậy bộ lập lịch của nó rất đơn giản. Nó sẽ tìm cách tháo gói tin ra khỏi hàng đợi nhanh nhất có thể. Tuy nhiên, với bộ phân luồng dữ liệu có số lƣợng hàng đợi lớn hơn, việc lựa chọn thuật toán lập lịch phù hợp sẽ giúp giải quyết đƣợc các vấn đề ƣu tiên dịch vụ. Một số kiểu thuật toán lập lịch thƣờng sử dụng gồm: thuật toán FCFS, thuật toán Max-Min, thuật toán Round robin, thuật toán Round robin theo trọng số (Weighted Round robin - WRR), thuật toán thâm hụt Round robin (Deficit Round robin - DRR), thuật toán cân bằng theo trọng số (Weighted Fair Queueing - WFQ). 2.2. Thuật toán First Come First Serve Ở thời điểm các router áp dụng mô hình best-effort cho tất cả các gói tin truyền qua mạng IP thì thuật toán First Come First Serve (FCFS) thƣờng xuyên đƣợc sử dụng. Nội dung của thuật toán này là các gói tin sau khi đã đƣợc phân loại sẽ đƣợc đƣa vào một hàng đợi duy nhất và các gói tin đƣợc tháo ra đúng theo nguyên tắc: Gói nào vào hàng đợi trƣớc sẽ đƣợc tháo ra trƣớc. Ƣu điểm của phƣơng pháp này là đơn giản, không phải tốn tài nguyên phần cứng và thời gian xử lý các thuật toán điều khiển. Thuật toán FCFS chỉ việc lƣu trữ các gói tin đi vào và gửi các gói tin đi ra theo thứ tự mà chúng đi vào. FCFS đối xử với các gói tin nhƣ nhau, hoạt động theo cùng một phƣơng pháp, do đó, phù hợp với mô hình best-effort trƣớc đây. Nhƣợc điểm của FCFS là không phân biệt đƣợc các luồng dữ liệu khác nhau, dẫn đến việc không có cơ chế đối xử khác nhau với các luồng dữ liệu đó, làm cho các luồng dữ liệu bị suy giảm chất lƣợng khi có tắc nghẽn xảy ra. 2.3. Thuật toán lập lịch Max-Min Một trong những mục tiêu của lập lịch là phân bổ băng thông có sẵn cho các luồng dữ liệu khác nhau. Ví dụ băng thông sẵn có giữa ngƣời dùng A và router R1 là 10 Mb/s, giữa ngƣời dùng B và router R1 là 100 Mb/s, và giữa R1 và đích đến C là