Phân tích đánh giá một số thuật toán quản lý hàng đợi tích cực trong TCP Network

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 1

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP

---------------------------------------

LUẬN VĂN THẠC SĨ KỸ THUẬT

NGÀNH:

PHÂN TÍCH ĐÁNH GIÁ

MỘT SỐ THUẬT TOÁN QUẢN LÝ HÀNG ĐỢI

TÍCH CỰC TRONG TCP NETWORK

TN

2012 THÁI NGUYÊN 2012

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 2

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP

---------------------------------------

LUẬN VĂN THẠC SĨ KỸ THUẬT

PHÂN TÍCH ĐÁNH GIÁ MỘT SỐ THUẬT TOÁN

QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRONG TCP NETWORK

23

Ngành:

Mã số: 60.52.70

Học viên:

Người HD Khoa học: PGS.TS

THÁI NGUYÊN – 2012

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 3

CHƢƠNG 1

TỔNG QUAN CÁC THUẬT TOÁN VỀ QUẢN LÝ HÀNG ĐỢI

1.1 Truyền dữ liệu trên một hệ thống mạng

Trong các hệ thống truyền số liệu, thông tin muốn gửi đi được chia thành các

đơn vị dữ liệu nhỏ gọi là gói tin (packet). Ngoài việc gửi đi các gói tin, phía phát

đồng thời đóng gói những thông tin điều khiển việc vận chuyển gói tin và đặt nó ở

đầu của mỗi gói tin (packet header). Trong một

địa chỉ nguồn để chỉ rõ địa chỉ nơi gửi gói tin đó. Packet header cũng chứa địa

chỉ IP đích (distination IP address) là nơi gói tin phải chuyển đến. Các bộ định

tuyến sẽ dùng địa chỉ đích này để xác định đích đến của gói tin. Và thực hiện việc

chuyển gói tin đến đúng địa chỉ.

Đa số các trường hợp, thiết bị phát và thiết bị thu không được nối trực tiếp với

nhau mà chúng phải thông qua các bộ định tuyến trung gian. Trong những trường

hợp này, thiết bị gửi sẽ gửi các gói tin tới bộ định tuyến mà nó được nối trực tiếp.

Bộ định tuyến này sẽ sử dụng địa chỉ đích (địa chỉ nơi nhận) của gói tin như một

chìa khóa để tìm kiếm dữ liệu thông tin về lộ trình và đưa ra quyết định chuyển tiếp

các gói tin. Nếu bộ định tuyến này và thiết bị thu được kết nối trực tiếp với nhau thì

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 4

1.1: Kiến trúc mạng đơn giản

nó sẽ chuyển các gói tin đến thẳng thiết bị thu. Nếu không phải nối trực tiếp, bộ

định tuyến này sẽ chuyển gói tin đến một bộ định tuyến khác mà nó biết được qua

quá trình phân tích thông tin theo lộ trình ở trên. Quá trình như vậy được lặp lại cho

đến khi gói tin được chuyển đến một bộ định tuyến được kết nối trực tiếp với thiết

bị thu và được chuyển đến đích cuối cùng.

Trong một hệ thống mạng, một bộ định tuyến (router) thường có nhiều giao diện

mạng gắn với những mối liên kết khác nhau như trong hình 1.2. Những liên kết này

dùng để kết nối với các bộ định tuyến khác hay kết nối với các mạng con

(subnetwork). Một router sau khi nhận được một gói tin sẽ sử dụng địa chỉ nơi nhận

và dữ liệu thông tin lộ trình của gói tin để xác định liên kết đầu ra cho gói tin đó.

Khi có nhiều gói tin từ nhiều nguồn khác nhau cùng đến router với một lộ trình đầu

ra giống nhau thì chỉ có duy nhất một gói tin được đáp ứng còn các gói tin còn lại bị

đẩy vào một hàng đợi tại mối liên kết đầu ra mà chúng yêu cầu. Khi nhịp độ đến

router của các gói tin như vậy tăng lên, chúng sẽ tiếp tục được đưa vào hàng đợi đó.

Thông thường, hàng đợi này sẽ được duy trì với cơ chế FIFO (first in first out).

Với cơ chế này thì những gói tin đến sau sẽ được xếp vào cuối hàng đợi. Nếu mức

độ chuyển các gói tin đi của router lớn hơn mức độ các gói tin khác đến router thì

sau một khoảng thời gian nào đó hàng đợi sẽ trở nên rỗng. Ngược lại, nếu mức độ

chuyển các

gói tin đi nhỏ hơn mức độ các gói tin khác đến router thì sau một khoảng thời gian

hàng đợi sẽ đầy. Khi đó, router sẽ phải loại bỏ các gói tin theo một cơ chế nào đó,

nếu không hiện tượng tắc nghẽn sẽ xảy ra. [1].

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 5

Hình 1.2: Kiến trúc cơ bản của một router

1.2. Điều khiển tắc nghẽn

1.2.1. Khái niệm

Trong quá trình hoạt động, mạng có thể rơi vào trạng thái không đủ khả năng

đáp ứng các chỉ tiêu chất lượng cho các kết nối đã được thiết lập hay cho một yêu

cầu kết nối mới do sự biến đổi bất thường, không dự đoán được của dòng lưu lượng

cùng với tình trạng lỗi của các phần tử mạng (các chuyển mạch, đường truyền, …).

Trạng thái này được gọi là tắc nghẽn.

Các gói tin đi vào và đi ra các bộ đệm, hàng đợi thường dưới dạng bó từ một

hoặc nhiều nguồn khác nhau. Các bộ đệm sẽ giúp các router lưu trữ các bó cho đến

khi chúng được chuyển đi. Khi các bó gói tin đến vượt qua kích thước bộ đệm thì

các gói đến sau sẽ bị loại bỏ. Để khắc phục điều này, việc tăng bộ đệm không phải

là giải pháp tốt vì khi kích thước bộ đệm quá lớn thì sẽ tạo ra trễ lớn. Tắc nghẽn xảy

ra khi lưu lượng từ nhiều tuyến đổ dồn về một tuyến và tuyến này không có khả

năng xử lý hết được. Tắc nghẽn cũng xảy ra ngay bên trong bản thân router tại

mạng lõi của mạng khi các node nhận được nhiều lưu lượng hơn so với thiết kế của

nó.

Khi mạng xảy ra tắc nghẽn nếu không được xử lý kịp thời sẽ gây ra các hậu quả

nghiêm trọng: các gói tin không được xử lý, không chuyển được đến đầu cuối người

nhận và gây ùn tắc trong mạng, mạng không hoạt động được trong thời gian dài sẽ

không thể truyền tải được giữ liệu, các thành phần có thể bị hư hỏng. Do đó vấn đề

quan trọng là phải điều khiển được tắc nghẽn trong mạng. Đó có thể là hành động

điều khiển để phòng tránh tắc nghẽn và cũng có thể là điền khiển tắc nghẽn khi nó

đã xảy ra.

1.2.2. Các kỹ thuật được sử dụng trong quản lý tắc nghẽn

- Điều khiển luồng phía đầu cuối: đây không phải lược đồ điều khiển tắc nghẽn

nhưng cũng là cách để tránh trường hợp phía phát gửi quá nhiều lưu lượng vượt qua

cả không gian bộ đệm chia thu.

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 6

- Điều khiển tắc nghẽn mạng: trong lược đồ này, các hệ thống đầu cuối giảm tốc

độ của luồng lưu lượng để tránh tắc nghẽn trong mạng, cơ chế này tương tự như

điều khiển luồng đầu cuối, nhưng mục đích chính là để giảm tắc nghẽn trong mạng

chứ không phải phía thu.

- Tránh tắc nghẽn trên cơ sở mạng: trong lược đồ này, router sẽ cố gắng dò tìm

ra tắc nghẽn khi nó có khả năng xảy ra, và cố gắng giảm tốc độ của luồng đầu vào

trước khi hàng đợi đầy.

- Phân phối tài nguyên: kỹ thuật bao gồm tiến trình lập lịch có sử dụng các mạch

vật lý hoặc các luồng tài nguyên khác. Một mạch ảo được xây dựng qua nhiều

chuyển mạch cùng với băng thông đảm bảo cũng là một loại phân phối tài nguyên.

Kỹ thuật này rất khó nhưng nó có khả năng loại trừ tắc nghẽn trong mạch bằng việc

khóa các lưu lượng vượt quá khả năng của mạng.

Giải pháp quan trọng nhất trong điều khiển tắc nghẽn đó là sử dụng kỹ thuật

quản lý hàng đợi. Các bộ đệm trong các thiết bị mạng được quản lý bởi rất nhiều kỹ

thuật hàng đợi. Nói đúng ra quản lý hàng đợi có thể tối thiểu hóa việc mất gói trong

mạng và tắc nghẽn xảy ra cũng như cải thiện được hiệu năng của mạng.

Kỹ thuật hàng đợi cơ bản nhất là FIFO, các gói được xử lý theo trật tự mà chúng

đến hàng đợi, còn hàng đợi ưu tiên sử dụng cấu trúc đa hàng đợi với các mức ưu

tiên khác nhau sẽ ưu tiên xử lý các gói quan trọng nhất và truền tới các node kế tiếp.

Một kỹ thuật hàng đợi quan trọng nữa là tự ấn định các luồng cho chính bản thân

các hàng đợi. Với các luồng khác nhau thì độ ưu tiên cũng được khác nhau, và mỗi

luồng đều được xử lý để chắc chắn rằng chúng không làm tràn hàng đợi. Việc tách

rời các hàng đợi theo các này đảm bảo rằng các hàng đợi sẽ chỉ chứa các gói từ một

nguồn đơn lẻ.

1.2.3. Điều khiển tắc nghẽn và tránh tắc nghẽn trong mạng TCP

Trong những năm 1980 Internet dễ xảy ra hiện tượng “sụp đổ tắc nghẽn”, do có

quá ít chức năng điều khiển quản lý mạng. Các kết nối đơn lẻ sử dụng điều khiểu

luồng giữa những người gửi và người nhận để tránh phía gửi làm tràn lưu lượng tại

phía nhận.

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 7

Nhưng việc điều khiển luồng trong thời điểm đó mới chỉ tránh tràn lụt lưu lượng

tại các bộ đệm phía thu chứ chưa giải quyết được tại các bộ đệm phía trong các

node mạng. Tuy nhiêu lưu lượng sử dụng trên mạng Intrernet ngày đó chưa lớn và

nó bao gồm một số lượng các kết nối tốc độ chậm do đó vấn đề tắc nghẽn không

quan trọng như ngày nay.

Sau những năm 1980 Van Jacopson đã phát triển các cơ chế điều khiển tắc

nghẽn, tạo ra các đáp ứng TCP để hạn chế tắc nghẽn trong mạng. Nền tảng cơ bản

là loại bỏ các gói sẽ làm cho các host ngừng lại hoặc chậm dần.

Thông thường khi một host nhận một gói hoặc một tập các gói thì nó sẽ gửi một

ACK (acknowlegement) cho phía phát để thông báo là đã nhận được gói tin. Cơ chế

cửa sổ cho phép host nhận đa gói tin mà chỉ dùng một ACK. Việc phía gửi không

nhận được ACK chứng tỏ rằng phía thu bị tràn bộ đệm hoặc mạng bị nghẽn do đó

phía phát phải dừng việc chuyển gói hoặc giảm tốc độ.

Một chiến lược được đưa ra là “Giảm theo cấp số nhân, tăng theo cấp số cộng”

để điều chỉnh số lượng các gói đến trong cùng một thời điểm. Nếu vẽ lược đồ về

luồng dữ liệu ta sẽ thấy số lượng các gói tăng lên cho đến khi có tắc nghẽn xuất

hiện trong mạng (tăng theo cấp số cộng) và khi gói bắt đầu bị loại bỏ thì ta giảm

nhanh các gói truyền cho đến khi việc truyền gói bắt đầu dừng (giảm theo cấp số

nhân). Kích thước cửa sổ sẽ lần lượt giảm một nửa khi có tắc nghẽn xảy ra. Các

host sẽ tìm ra tốc độ truyền dẫn tối ưu bằng việc thường xuyên kiểm tra mạng với

tốc độ cao hơn. Thỉnh thoảng tốc độ truyền cao hơn này được chấp nhận nhưng khi

mạng bận thì các gói bắt đầu bị loại bỏ và host lại quay trở lại tốc độ ban đầu. Lược

đồ này coi mạng như một hộp đen loại bỏ các gói khi có tắc nghẽn. Do đó điều

khiển tắc nghẽn được thực hiện bới các hệ thống đầu cuố

gói là để chỉ thị tắc nghẽn. Phía người gửi sẽ truyền một số lượng lớn các file để

đẩy lên tốc độ cao hơn cho tới khi nó đạt được tất cả băng thông. Các host khác có

thể gặp vài vấn đề khi chuyển gói qua mạng. Các host bị túm lấy băng thông thì chỉ

truyền tải được rất ít lưu lượng quan trọng.

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

P

Trang 8

Tất nhiên, mạng có thể sử dụng vai trò tích cực trong điều khiển tắc nghẽn. Cơ

chế điều khiển và tránh tắc nghẽn có thể chia ra thành các quá trình:

- Khôi phục tắc nghẽn: hoàn trả lại trạng thái hoạt động của mạng khi yêu cầu

vượt quá khả năng.

- Đoán trước được tắc nghẽn xảy ra và có thể phòng tránh được không cho tắc

nghẽn có thể xảy ra.

Ngày nay tránh tắc nghẽn là công cụ cải thiện hiệu năng và QoS trong mạng

Internet. Chuẩn RFC 2309 (giới thiệu quản lý hàng đợi và tránh tắc nghẽn trong

Internet) đưa ra cơ chế tránh tắc nghẽn dựa trên cơ cấu router. Cơ chế này chia ra

thành các thuật toán quản lý hàng đợi và thuật toán lập lịch.

Mục đích quan trọng là tối thiểu số lượng các gói bị loại bỏ. Nếu một host

truyền tại tốc độ cao hơn và mạng bị nghẽn thì số lượng các gói bị mất sẽ tăng

RFC2309 chỉ ra rằng thà chấp nhận các luồng dạng bó đến làm tràn hàng đợi còn

hơn là cố gắng duy trì trạng thái không đầy của hàng đợi.

TCP có xử lý điều khiển tắc nghẽn, UDP được điển hình sử dụng cho các luồng

video và audio thời gian thực bởi vì nó không cần khôi phục lại các gói bị mất.

UDP là giao thức truyền tải không đảm bỏa do nó không truyền lại các báo hiệu

ngược trở lại nguồn. Các luồng UDP không thể được điều khiển bởi các điều khiển

tắc nghẽn như trong TCP truyền thông.

Trong chuẩn RFC 2581 giới thiệu 4 thuật toán cho điều khiển tắc nghẽn: Khởi

đầu chậm, truyền lại nhanh, khôi phục nhanh, tránh tắc nghẽn.

Điều khiển tắc nghẽn khởi đầu chậm:

Khởi đầu chậm làm giảm ảnh hưởng của bó khi một host đầu tiên được truyền.

Nó yêu cầu một host khởi đầu việc truyền dẫn của nó chậm hơn, sau đó nó sẽ xử lý

các điểm có tắc nghẽn xảy ra. Một host lúc đầu không biết có bao nhiêu gói được

gửi do đó nó sẽ sử dụng cách khởi đầu chậm để định giá dung lượng của mạng. Một

host bắt đầu việc truyền dẫn bằng cách gửi hai gói tin tới phía thu. Khi phía thu

nhận được các segment thì nó sẽ gửi phản hồi lại phía nhận một ACK để xác nhận.

Phía phát sẽ tăng số gói gửi theo cơ số hai, tức là sẽ gửi 4 gói. Việc chỉ thị này tiếp