Tài liệu Thử nghiệm các giải pháp đảm bảo chất lượng dịch vụ trên các thiết bị định tuyến sử dụng hệ điều hành nguồn mở vyos

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THANH TÙNG THỬ NGHIỆM CÁC GIẢI PHÁP ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ TRÊN CÁC THIẾT BỊ ĐỊNH TUYẾN SỬ DỤNG HỆ ĐIỀU HÀNH NGUỒN MỞ VYOS LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH AN TOÀN THÔNG TIN HÀ NỘI – 05/2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THANH TÙNG THỬ NGHIỆM CÁC GIẢI PHÁP ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ TRÊN CÁC THIẾT BỊ ĐỊNH TUYẾN SỬ DỤNG HỆ ĐIỀU HÀNH NGUỒN MỞ VYOS Ngành: Công nghệ thông tin Chuyên ngành: An toàn thông tin Mã số: 8480202.01 LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH AN TOÀN THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN ĐẠI THỌ HÀ NỘI – 05/2019 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của cá nhân tôi dưới sự hướng dẫn của TS. Nguyễn Đại Thọ. Mọi tài liệu tham khảo đều được tôi trích dẫn nguồn đầy đủ, đồng thời các số liệu, kết quả trong luận văn đều không sao chép của ai. Hà Nội, ngày….tháng….năm…. Học viên Phạm Thanh Tùng LỜI CẢM ƠN Đầu tiên, tôi xin cảm ơn tất cả các thầy, cô trường Đại học Công Nghệ Đại Học Quốc Gia Hà Nội đã giảng dạy, giúp đỡ tôi trong suốt thời gian học tập tại trường. Tiếp theo, tôi xin gửi lời cảm ơn chân thành tới TS. Nguyễn Đại Thọ, người thầy đã nhiệt tình giúp đỡ, hướng dẫn tôi để đi đến thành quả cuối cùng. Tuy tôi đã rất cố gắng để hoàn thiện luận văn này, nhưng không thể không mắc những thiếu sót. Do đó, tôi rất mong được sự góp ý và nhận xét chân thành nhất của các thầy cô và các bạn. Hà Nội, ngày….tháng….năm…. Học viên Phạm Thanh Tùng 2 MỤC LỤC DANH MỤC CÁC TỪ VIẾT TẮT ........................................................................ 5 DANH MỤC CÁC HÌNH VẼ................................................................................. 6 DANH MỤC CÁC BẢNG ...................................................................................... 8 MỞ ĐẦU .................................................................................................................. 9 CHƯƠNG 1. TỔNG QUAN VỀ QOS VÀ 1 SỐ CƠ CHẾ QOS CƠ BẢN ...... 11 1.1. Tổng quan về QoS [1,4] ................................................................................ 11 1.2. Các tham số hiệu suất QoS [1,4] ................................................................... 12 1.3. Các cơ chế QoS cơ bản ................................................................................. 13 1.3.1. Cơ chế bỏ đuôi - DropTail ....................................................................... 13 1.3.2. Cơ chế loại bỏ ngẫu nhiên –‘ RED [5]..................................................... 13 1.3.3. Cơ chế Adaptive-RED (A-RED) [6] ........................................................ 20 1.4. Kết chương .................................................................................................... 24 CHƯƠNG 2. CÁC CƠ CHẾ QOS VÀ CẤU TRÚC TRONG VYOS .............. 25 2.1. Giới thiệu chung về thiết bị định tuyến hệ điều hành nguồn mở VyOS ....... 25 2.2. Cấu trúc file hệ thống trong VyOS ............................................................... 25 2.2.1. Thư mục /opt/vyatta/bin ........................................................................... 26 2.2.2. Thư mục /opt/vyatta/sbin ......................................................................... 27 2.2.3. Thư mục /opt/vyatta/share........................................................................ 28 2.3. Các kiểu QoS trong VyOS [8,9] ................................................................... 29 2.4. Kiến trúc QoS trong VyOS ........................................................................... 31 2.5. Xác định mã nguồn giải thuật QoS trong kernel VyOS................................ 37 2.6. Kết chương .................................................................................................... 41 CHƯƠNG 3. THỰC HIỆN THỬ NGHIỆM VÀ KẾT QUẢ ............................ 42 3.1. Tổng quan về chương trình giả lập EVE-NG [13]........................................ 42 3.2. Xây dựng sơ đồ mạng mô phỏng hệ thống ................................................... 43 3.4. Thực hiện thử nghiệm ................................................................................... 45 3.4.1. Cấu hình ................................................................................................... 45 3.4.2. Kết quả kiểm thử ...................................................................................... 46 3 3.5. Kết chương .................................................................................................... 51 KẾT LUẬN ............................................................................................................ 52 TÀI LIỆU THAM KHẢO .................................................................................... 53 4 DANH MỤC CÁC TỪ VIẾT TẮT QoS Quality of service AQM Active Queue Management RED Random Early Detection A-RED Adaptive Random Early Detection IoT Internet of things FIFO First In First Out WDA Web farm DDoS Attack attenuator ISP Internet Service Provider EVE-NG Emulated Virtual Environment – Next Generation TC Traffic Control ECN Explicit Congestion Notification 5 DANH MỤC CÁC HÌNH VẼ Hình 1: Giải thuật tổng quát RED ................................................................... 16 Hình 2: Giải thuật chi tiết RED ....................................................................... 17 Hình 3: Giải thuật chi tiết A-RED................................................................... 22 Hình 4: Cấu trúc File system của VyOS. ........................................................ 26 Hình 5: Cấu trúc file bên trong bin/. ............................................................... 26 Hình 6: Cấu trúc file bên trong sbin/ ............................................................... 27 Hình 7: Cấu trúc file vyatta-qos-up ................................................................. 27 Hình 8: Cấu trúc file vyatta-qos.pl .................................................................. 28 Hình 9: Cấu trúc bên trong share/perl5/Vyatta ............................................... 28 Hình 10: Cấu trúc bên trong share/QoS .......................................................... 29 Hình 11: Câu lệnh cấu hình QoS là fair queue................................................ 31 Hình 12: Phân cấp thư mục template hệ thống ............................................... 32 Hình 13: Phân cấp thư mục template hệ thống theo dạng hình cây qua 2 Câu lệnh cấu hình QoS là fair queue ...................................................................... 32 Hình 14: Hiển thị thông số lúc cấu hình tương đương với các thư mục phân cấp trong template cấu hình ............................................................................ 33 Hình 15: Hiển thị thông số lúc cấu hình tương đương với các thư mục phân cấp trong template cấu hình droptail ............................................................... 33 Hình 16: Hiển thị thông số lúc cấu hình queue-limit trong droptail ............... 34 Hình 17: Thử nghiệm thêm thông số cấu hình trong thư mục template ......... 34 Hình 18: Nội dung file traffic-policy/fair-queue/node.def.............................. 35 Hình 19: Nội dung file interfaces/ethernet/node.tag/traffic-policy/out/node.def ......................................................................................................................... 35 Hình 20: Nội dung file vyatta-qos.pl định nghĩa các loại Qos và gọi đến module QoS tương ứng ................................................................................... 36 Hình 21: Nội dung module FairQueue.pm ...................................................... 37 Hình 22: Trạng thái qdisc thay đối khi cấu hình QoS ..................................... 37 6 Hình 23: Thông tin phiên bản kernel VyOS 1.2 ............................................. 38 Hình 24: Thao tác thêm vào và lấy một đối tượng ra khỏi hàng đợi RED ..... 38 Hình 25: Mô tả giải thuật RED trong mã nguồn kernel .................................. 39 Hình 26: Mô tả giải thuật Adaptive RED (A-RED) trong mã nguồn kernel .. 39 Hình 27: Hệ thống mạng mô phỏng ................................................................ 44 Hình 28: Công thức tính các tham số của RED .............................................. 45 Hình 29: Cấu hình traffic policy với queue type là drop-tail .......................... 46 Hình 30: Lưu lượng gói tin đo ở đầu ra eth1 VyOS với trường hợp là DropTail .......................................................................................................... 46 Hình 31: Lưu lượng gói tin đo ở đầu ra eth1 VyOS với trường hợp là RED-1 ......................................................................................................................... 47 Hình 32: Lưu lượng gói tin đo ở đầu ra eth1 VyOS với trường hợp là RED-2 ......................................................................................................................... 47 Hình 33: Lưu lượng gói tin đo ở đầu ra eth1 VyOS với trường hợp là A-RED ......................................................................................................................... 48 Hình 34: Lưu lượng gói tin đo ở đầu ra eth1 VyOS trong 4 trường hợp từ nguồn đến là thiết bị R2 .................................................................................. 48 Hình 35: Kết quả lượng gói tin bị loại bỏ cụ thể từng trường hợp ................. 49 Hình 36: Kết quả so sánh tổng hợp lượng gói tin bị loại bỏ của 4 trường hợp ......................................................................................................................... 50 7 DANH MỤC CÁC BẢNG Bảng 1: So sánh chương trình giả lập EVE-NG với GNS3 ............................. 43 Bảng 2: Các tham số cài đặt thử nghiệm .......................................................... 44 Bảng 3: Kết quả lượng gói tin bị loại bỏ cụ thể từng trường hợp .................... 49 8 MỞ ĐẦU Trong xu hướng phát triển bùng nổ thông tin ngày này, các nhu cầu về thông tin liên lạc ngày càng mở rộng, đi đôi với nhu cầu cao về chất lượng dịch vụ. Vấn đề đặt ra là làm thế nào để tăng tốc độ truyền tin, sao cho lượng thông tin có thể được chuyển tải nhanh nhất, đạt độ tin cậy cao nhất mà không xảy ra tình trạng tắc nghẽn. Vì vậy, vấn đề rất quan trọng là phải thiết kế, xây dựng các mạng, hệ thống mạng đáp ứng được các yêu cầu chung nhất nêu trên. Thông tin ở đây được gọi là “dữ liệu”. Dữ liệu được truyền đi không chỉ đơn thuần là dạng văn bản (text) đơn giản, mà là dữ liệu đa phương tiện (multimedia) bao gồm cả hình ảnh tĩnh, động (video), âm thanh (audio),… Các ứng dụng đa phương tiện phổ biến hiện nay như điện thoại qua mạng, hội thảo trực tuyến (video conference)... đang ngày càng được sử dụng rộng rãi. Đối với truyền thông đa phương tiện, điều quan trọng nhất là phải đảm bảo chất lượng dịch vụ (QoS), tức là đảm bảo độ trễ và biến thiên độ trễ - jitter đủ nhỏ, băng thông đủ lớn, và tỷ lệ mất gói tin không vượt quá một mức độ nhất định có thể chấp nhận được. Để làm được điều này cần phải thực hiện ở các thiết bị định tuyến. Các thiết bị định tuyến cần theo dõi độ dài hàng đợi và sử dụng các tín hiệu điều khiển để thông báo với các máy tính trên mạng rằng đã hoặc sắp xảy ra tắc nghẽn để chúng có phản ứng phù hợp giúp giải quyết tình trạng tắc nghẽn. Ngoài ra chúng cũng cần có các chiến lược quản lý hàng đợi thích hợp và hiệu quả để tùy vào từng trường hợp cụ thể, xử lý một cách tối ưu việc vận chuyển thông tin trong mạng. Từ trước đến nay đã có không ít những công trình nghiên cứu đánh giá hiệu năng của các phương pháp quản lý hàng đợi tích cực nhưng đều bằng cách mô phỏng nhưng chưa có công trình nào thực sự cài đặt dánh giá các phương pháp này trên thiết bị thật hoặc là sát với thực tế thông qua giả lập. Trước đây tại trường Đại học Công Nghệ - Đại Học Quốc Gia Hà Nội, đã có một số đồ án, luận văn xoay quanh vấn đề chống tấn công DdoS bằng cách thực hiện cài đặt giải thuật WDA (Web farm DDoS Attack attenuator, được giới thiệu bởi Ehud Doron và Avisha Wool, là một kiến trúc được xây dựng nhằm bảo vệ các Web server. Theo đó, các Web server sẽ được kết nối với Internet thông qua Router ISP. Để nâng cao khả năng chống đỡ của hệ thống trước các cuộc tấn công, WDA sẽ được thêm vào như một phần trong cơ chế quản lý của thiết bị định tuyến của ISP) cụ thể có luận văn của Nguyễn Xuân Hưởng [2] đã thực 9 hiện cài đặt một phần cơ bản của giải thuật WDA lên thiết bị thật là router của Cisco, luận văn của Nguyễn Anh Tú [3] thử nghiệm mức độ có thể cài đặt giải thuật WDA lên thiết bị định tuyến của Cisco, qua kết quả cài đặt và kiểm thử để đi tới việc đề xuất cài đặt giải thuật WDA lên một thiết bị định tuyến mã nguồn mở VyOS. Tuy nhiên sau khi đọc báo cáo luận văn của Tú, tôi thấy việc cài đặt lên thiết bị định tuyến mã nguồn mở VyOS vẫn đang còn bỏ ngỏ khi Tú mới chỉ đang ở mức nghiên cứu được cấu trúc thư mục chứa các lệnh của VyOS chứ chưa thử nghiệm cài đặt, cấu hình trên VyOS. Do đó, ở luận văn này, tôi muốn tiếp tục nghiên cứu trên thiết bị định tuyến hệ điều hành nguồn mở VyOS mà không phải trên giả lập simulator bởi vì hướng triển khai trên các thiết bị định tuyến của các hãng lớn như Cisco không cho phép ta xâm nhập vào bên trong mã nguồn để thay đổi cấu trúc cũng như thêm các tính năng. Mặt khác do vấn đề về chi phí, nên luận văn này được làm trên một môi trường emulator EVE-NG, sử dụng hoàn toàn các firmware của thiết bị định tuyến thật do nhà cung cấp phát hành, nên vẫn đảm bảo không có sự sai khác khi so sánh với việc làm trên thiết bị thật. Mục tiêu lâu dài của luận văn là có thể can thiệp vào các giải thuật quản lý hàng đợi trong nhân hệ điều hành để có thể chống tấn công trong các thiết bị mạng. Luận văn sẽ đi từ việc tìm hiểu cấu trúc, các cơ chế QoS, xác định được nơi chứa source code các giải thuật về QoS, từ đó có thể áp dụng cài đặt các giải pháp tăng chất lượng dịch vụ và thực hiện thử nghiệm đánh giá hiệu năng của một số giải thuật quản lý hàng đợi tích cực tiêu biểu (DropTail, RED) trên công cụ giả lập mạng EVE-NG tích hợp hệ điều hành mã nguồn mở cho các thiết bị định tuyến VyOS. Phần tiếp theo của luận văn được tổ chức theo bố cục như sau: Chương I: Chương này sẽ cho ta một cái nhìn khái quát về QoS và cụ thể một số cơ chế quản lý dịch vụ cơ bản hiện nay. Chương II: Chương này tập trung nghiên cứu các cơ chế quản lý dịch vụ và cấu trúc trong thiết bị định tuyến hệ điều hành nguồn mở VyOS. Chương III: Chương này sẽ áp dụng mô phỏng thử nghiệm các cơ chế quản lý dịch vụ trên thiết bị định tuyến hệ điều hành nguồn mở VyOS, từ đó rút ra được kết luận và hướng phát triển sau này. 10 CHƯƠNG 1. TỔNG QUAN VỀ QOS VÀ 1 SỐ CƠ CHẾ QOS CƠ BẢN 1.1. Tổng quan về QoS [1,4] Chất lượng dịch vụ (QoS) đang trở thành một khía cạnh ngày càng quan trọng của cơ sở hạ tầng CNTT doanh nghiệp ngày nay. QoS không chỉ cần thiết cho truyền phát giọng nói và video qua mạng, đây còn là một yếu tố quan trọng trong việc hỗ trợ Internet vạn vật (IoT) đang phát triển. Một ví dụ là trong lĩnh vực sản xuất, nơi các máy móc đang bắt đầu tận dụng mạng để cung cấp thông tin trạng thái thời gian thực về bất kỳ vấn đề nào có thể xảy ra. Bất kỳ sự chậm trễ nào trong việc xác định một vấn đề có thể dẫn đến những sai lầm trong sản xuất tốn hàng chục ngàn đô la mỗi giây. Với QoS, luồng dữ liệu trạng thái sản xuất có thể được ưu tiên trong mạng để đảm bảo luồng thông tin kịp thời. Một trường hợp sử dụng khác có thể là cho các dự án IoT quy mô lớn như tòa nhà thông minh hoặc thành phố thông minh. Phần lớn dữ liệu được thu thập và phân tích, như nhiệt độ, độ ẩm và nhận thức vị trí, rất nhạy cảm với thời gian. Do độ nhạy thời gian này, dữ liệu này cần được xác định chính xác, đánh dấu và xếp hàng phù hợp. Tại sao QoS quan trọng? Một số ứng dụng chạy trên mạng rất nhạy cảm với độ trễ. Các ứng dụng này thường sử dụng giao thức UDP trái ngược với giao thức TCP. Sự khác biệt chính giữa TCP và UDP là khi sử dụng TCP nếu bất kỳ gói tin nào bị mất, không đúng định dạng hoặc bị lỗi, giao thức TCP có thể truyền lại và sắp xếp lại các gói để tạo lại tệp trên PC đích. Nhưng đối với các ứng dụng UDP như cuộc gọi điện thoại IP, bất kỳ gói bị mất nào cũng không thể được truyền lại vì các gói thoại đi vào dưới dạng luồng được đặt hàng; truyền lại các gói là vô ích. Do đó bất kỳ gói bị mất hoặc bị trì hoãn cho các ứng dụng chạy giao thức UDP là một vấn đề thực sự. Trong ví dụ về cuộc gọi thoại, việc mất thậm chí một vài gói sẽ dẫn đến chất lượng giọng nói trở nên khó hiểu và không thể hiểu được. Nếu mạng của bạn có nhiều băng thông và không có lưu lượng truy cập vượt quá những gì nó có thể xử lý, bạn sẽ không gặp vấn đề với mất gói, trễ hoặc biến thiên độ trễ - jitter. Nhưng trong nhiều mạng doanh nghiệp, sẽ có lúc các liên kết bị tắc nghẽn quá mức đến mức các bộ định tuyến và bộ chuyển 11 mạch bắt đầu loại bỏ các gói vì các gói vào/ra nhanh hơn những gì các bộ định tuyến có thể được xử lý. Đây là nơi QoS xuất hiện. Thông thường, mạng thường phải truyền tải nhiều loại gói tin với các yêu cầu về hiệu năng là khác nhau. Có thể loại gói tin đó là rất quan trọng trong dịch vụ này nhưng lại không quá quan trọng trong dịch vụ khác. Vì thế một cơ chế đảm bảo chất lượng dịch vụ được triển khai trong một mạng phải xem xét đến sự xung đột các yêu cầu về hiệu năng và cân bằng các yếu tố khác nhau để đạt được sự kết hợp tốt nhất giữa chúng. 1.2. Các tham số hiệu suất QoS [1,4] Các tham số hiệu suất QoS thường được sử dụng bao gồm: − Thông lượng (throughput): số đơn vị thông tin tính trung bình được vận chuyển qua mạng trong một đơn vị thời gian. Đơn vị thông tin ở đây có thể là bit, byte hay gói số liệu. Ví dụ packet/s. − Thời gian trễ (delay time, delay): thời gian trung bình để vận chuyển một gói số liệu qua mạng từ nguồn tới đích. Tốc độ truyền tin càng lớn thì độ trễ càng nhỏ và ngược lại. Delay liên quan chặt chẽ tới băng thông. Với các ứng dụng giới hạn băng thông thì băng thông càng lớn độ trễ càng nhỏ. − Jitter (biến thể của độ trễ): là sự khác nhau về độ trễ của các gói tin khác nhau trong cùng một dòng lưu lượng. Một số ứng dụng rất nhạy cảm với jitter là các ứng dụng thời gian thực như voice, video. − Tốc độ mất gói (Packet loss): Các gói có thể bị mất trong mạng vì chúng có thể bị hủy khi bộ đệm trong nút mạng tràn. Ngoài ra, theo quan điểm của ứng dụng thời gian thực, một gói tin đến đích sau một thời gian nhất định (giới hạn độ trễ) có thể là vô ích và do đó có thể được tính là bị mất. Hầu hết các ứng dụng thời gian thực đều có mức dung sai nhất định đối với việc mất gói. Thông thường hơn là đặt tỷ lệ mất gói cụ thể phụ thuộc vào các cơ chế bảo vệ / phục hồi mất gói được sử dụng bởi các ứng dụng và đánh giá chủ quan của người dùng về mức chất lượng. Nó thường được coi là chấp nhận được nếu tốc độ mất gói của một luồng cụ thể có thể được giữ dưới mức dung sai cụ thể trong hầu hết thời gian. 12 1.3. Các cơ chế QoS cơ bản 1.3.1. Cơ chế bỏ đuôi -DropTail Drop Tail là cách thức quản lý hàng đợi đơn giản, truyền thống dựa vào cơ chế FIFO và chỉ đặt độ dài tối đa cho mỗi hàng đợi tại bộ định tuyến. Theo cơ chế này, tất cả các gói tin đến được xếp vào hàng đợi; khi hàng đợi đầy thì các gói tin đến sau đều bị loại bỏ; để chọn các gói tin truyền đi thì gói tin nào đến trước được phục vụ trước. Trong Drop Tail, lưu lượng không được phân biệt, mỗi gói đều có cùng mức độ ưu tiên. Drop Tail sẽ tiếp tục loại bỏ / thả gói tin cho đến khi hàng đợi có đủ chỗ cho các gói mới. Do đặc tính đơn giản, dễ triển khai mà DropTail đã được sử dụng nhiều năm trên thiết bị định tuyến ở Internet, tuy nhiên giải thuật này có những nhược điểm như sau: − Hiện tượng đầy Queue: các gói tin đến thiết bị định tuyến thường theo từng cụm chứ không phải lần lượt. Vì thế cơ chế hoạt động của DropTail khiến cho hàng đợi có thể dễ dàng bị đầy trong 1 khoảng thời gian dài, dẫn đến thời gian trễ trung bình của các gói tin lớn. Để tránh hiện tượng này thì với DropTail chỉ có cách là tăng bộ đệm của thiết bị định tuyến, cách này tỏ ra hết sức tốn kém và không hiệu quả. − Không đảm bảo QoS: Với cơ chế DropTail thì không có cách nào để ưu tiên những gói tin quan trọng được truyền qua thiết bị định tuyến sớm hơn khi tất cả đang ở trong hàng đợi. 1.3.2. Cơ chế loại bỏ ngẫu nhiên – RED [5] 1.3.2.1. Tổng quan RED (Random Early Detection of congestion; Random Early Drop) là một trong những thuật toán AQM đầu tiên được đề xuất vào năm 1993 bởi Sally Floyd và Van Jacobson, hai nhà khoa học của Phòng thí nghiệm Lawrence Berkeley thuộc Đại học Califonia, Mỹ. Điểm cơ bản nhất trong công trình của họ là cho rằng nơi hiệu quả nhất để phát hiện tắc nghẽn và phản ứng lại hiện tượng này chính là tại các gateway hay router. Chỉ có gateway mới có cái nhìn đúng đắn về trạng thái của hàng đợi và có thể phân biệt đáng tin cậy giữa độ trễ lan truyền (propagation delay) và độ trễ hàng đợi (persistent queueing delay). 13 RED gateway theo dõi độ dài trung bình của hàng đợi, dựa vào đó để phát hiện sớm dấu hiệu tắc nghẽn sắp xảy ra. RED gateway có thể loại bỏ gói tin ở gateway hoặc đánh dấu bằng cách đặt bit “có tắc nghẽn” trong header gói tin tùy thuộc vào giao thức tầng giao vận. Mục tiêu chính của RED là tránh tắc nghẽn bằng cách điều khiển kích thước hàng đợi trung bình nằm trong một vùng đủ nhỏ và ổn định. Việc thực hiện mục tiêu này cũng giúp: tránh hiện tượng đồng bộ toàn cục, không chống lại các dòng lưu lượng có đặc tính đột biến và duy trì cận trên của kích thước hàng đợi trung bình ngay cả khi không có được sự hợp tác từ các giao thức tầng giao vận. Để đạt được các mục tiêu trên, các RED gateways phải làm được các việc sau: − Việc đầu tiên của cơ chế tránh tắc nghẽn tại gateway là phát hiện tắc nghẽn, duy trì mạng trong khu vực có độ trễ thấp và thông lượng cao. Kích thước hàng đợi trung bình nên được giữ ở mức thấp, trong khi các dao động trong kích thước hàng đợi thực tế phải được phép để phù hợp với lưu lượng truy cập bùng nổ và tắc nghẽn tạm thời. Bởi vì gateway có thể theo dõi kích thước của hàng đợi theo thời gian, nên gateway là tác nhân thích hợp để phát hiện tắc nghẽn. Và gateway có một cái nhìn thống nhất về các nguồn khác nhau góp phần vào sự tắc nghẽn này đồng thời cũng là nơi thích hợp để quyết định những nguồn nào cần thông báo về sự tắc nghẽn này. − Việc thứ hai là thông báo tắc nghẽn tới nguồn phát. Việc này được thực hiện bằng cách đánh dấu và thông báo cho nguồn phát giảm lưu lượng xuống. Nếu tắc nghẽn được phát hiện trước khi bộ đệm gateway đầy, thì gateway đó không cần thiết phải loại bỏ các gói và thông báo tới các nguồn phát. Việc đánh dấu và thông báo này có thể bao gồm việc loại bỏ một gói, đánh dấu bằng cách đặt bit trong header gói tin hoặc một số phương thức khác được hiểu bởi các giao thức tầng giao vận. − Việc thứ ba mà các RED gateway cần đạt được là tránh hiện tượng đồng bộ toàn cục và không chống lại các dòng lưu lượng có đặc tính đột biến. Với Drop Tail gateway và Random Drop gateway có sự sai lệch chống lại lưu lượng truy cập đột biến. Khi lưu lượng truy cập từ một kết nối cụ thể càng tăng thì càng có nhiều khả năng hàng đợi 14 gateway sẽ bị tràn. Còn hiện tượng đồng bộ toàn cục xảy ra khi tất cả các kết nối đồng loạt giảm kích thước cửa sổ, dẫn tới mất thông lượng trong mạng ở cùng một thời điểm. Để tránh hai hiện tượng này, các gateway có thể dùng các thuật toán riêng biệt để phát hiện tắc nghẽn và quyết định kết nối nào sẽ được thông báo tắc nghẽn tại gateway. RED gateway chọn ngẫu nhiên các gói tin đến để đánh dấu; với phương pháp này xác suất đánh dấu một gói tin từ một kết nối cụ thể gần như tỉ lệ thuận với phần băng thông được chia sẻ của kết nối đó tại gateway. Phương pháp này có thể được thực hiện một cách hiệu quả mà không cần duy trì trạng thái mỗi kết nối tại gateway. − Một công việc nữa là khả năng kiểm soát được kích thước hàng đợi trung bình ngay cả khi không có sự hợp tác từ các nguồn phát. Điều này có thể được thực hiện nếu gateway loại bỏ gói tin đến khi kích thước trung bình vượt quá ngưỡng tối đa (thay vì đánh dấu bằng cách đặt bit trong header gói tin). Phương pháp này có thể được sử dụng để kiểm soát kích thước hàng đợi trung bình ngay cả khi hầu hết các kết nối có khoảng thời gian phát nhỏ hơn khoảng thời gian khứ hồi, hoặc ngay cả khi các kết nối không giảm lưu lượng để đáp ứng với việc đánh dấu hoặc loại bỏ gói tin. 1.3.2.2. Giải thuật RED gateways tính kích thước hàng đợi trung bình bằng một bộ lọc thông thấp (Low-Pass Filter). Kích thước hàng đợi trung bình này được so sánh với hai ngưỡng: ngưỡng tối thiểu minth và ngưỡng tối đa maxth. Khi kích thước hàng đợi trung bình bé hơn ngưỡng tối thiểu thì không gói tin đến nào bị đánh dấu hay loại bỏ; khi kích thước hàng đợi trung bình lớn hơn ngưỡng tối đa thì tất cả các gói tin đến đều bị loại bỏ. Khi kích thước hàng đợi trung bình nằm giữa minthvà maxth thì mỗi gói tin đến được đánh dấu hoặc loại bỏ theo một xác suất pa, trong đó pa là một hàm của kích thước hàng đợi trung bình avg; xác suất đánh dấu hoặc loại bỏ một gói tin của một kết nối cụ thể sẽ tỷ lệ thuận với phần băng thông chia sẻ của kết nối đó tại gateway. Giải thuật tổng quát của RED gateway được mô tả như sau: 15 Hình 1: Giải thuật tổng quát RED Giải thuật tại RED gateway gồm hai giải thuật riêng biệt: − Giải thuật tính kích thước hàng đợi trung bình xác định mức độ bùng nổ cho phép trong hàng đợi tại gateway. − Giải thuật tính xác suất đánh dấu gói tin xác định mức độ thường xuyên của việc đánh dấu gói tin của gateway với mức độ tắc nghẽn hiện tại. Mục tiêu của việc đánh dấu gói tin của gateway phải đảm bảo sao cho các gói tin được đánh dấu tại những khoảng thời gian đều nhau, để tránh hiện tượng sai lệch, đồng bộ toàn cầu và đánh dấu các gói thường xuyên đủ để kiểm soát kích thước hàng đợi trung bình. Giải thuật chi tiết của RED tại gateway được mô tả như hình 2 dưới đây. 16 Hình 2: Giải thuật chi tiết RED Các biến thay đổi: avg: kích thước hàng đợi trung bình q_time: điểm bắt đầu hàng đợi rỗng count: số lượng các gói đến ngay sau gói cuối cùng bị đánh dấu Các tham số cố định: wq: trọng số hàng đợi minth: chiều dài ngưỡng nhỏ nhất của hàng đợi maxth: chiều dài ngưỡng lớn nhất của hàng đợi maxp: xác suất loại bỏ tối đa Các tham số khác: 17 pa: xác suất đánh dấu gói tin hiện tại pb: xác suất đánh dấu hoặc loại bỏ tạm thời q: kích thước hàng đợi hiện tại time: thời gian hiện tại f(t): một hàm tuyến tính của thời gian Theo giải thuật, mỗi khi có một gói tin đến, sẽ tính kích thước hàng đợi trung bình – avg bằng công thức: avg  (1 – wq) * avg + wq * q Khi avg chạy từ minth đến maxth thì xác suất pb thay đổi tuyến tính từ 0 đến maxp: pb  maxp * (avg – minth) / (maxth - minth) Xác suất đánh dấu gói tin pa tăng chậm khi count tăng kể từ gói cuối cùng được đánh dấu: pa  pb / (1 – count * pb) Một tùy chọn cho cổng RED là đo hàng đợi theo byte thay vì theo gói. Với tùy chọn này, kích thước hàng đợi trung bình phản ánh chính xác độ trễ trung bình tại gateway. Khi tùy chọn này được sử dụng, thuật toán sẽ được sửa đổi để đảm bảo rằng xác suất gói được đánh dấu tỷ lệ thuận với kích thước gói theo byte như sau: pb  maxp * (avg – minth) / (maxth - minth) pb  pb * PacketSize / MaximumPacketSize pa  pb / (1 – count * pb) 1.3.2.3. Các tham số của RED a. Trọng số hàng đợi wq: RED gateway sử dụng bộ lọc thông thấp để tính toán kích thước hàng đợi trung bình. Theo đó, sự gia tăng ngắn hạn trong kích thước hàng đợi xuất phát từ lưu lượng truy cập lớn hoặc do tắc nghẽn tạm thời không sẽ ít ảnh hưởng lớn đến kích thước hàng đợi trung bình. Bộ lọc thông thấp là trung bình dịch chuyển có trọng số tăng theo cấp số nhân avg  (1 – wq) * avg + wq * q 18