NGUYÊN CỨU VÀ ỨNG DỤNG CHƯƠNG TRÌNH LẬP LỊCH TRONG MẠNG IP CHƯƠNG 3_1 pps

ĐỒ ÁN HỆ THỐNG MẠNG

Đề tài:

NGUYÊN CỨU VÀ ỨNG DỤNG CHƯƠNG

TRÌNH LẬP LỊCH TRONG MẠNG IP

CHƯƠNG 3

SCHEDULING

3. 1. Khái niệm

3. 1. 1 Giới thiệu

Việc lập lịch cho thời gian xuất phát của các gói từ mỗi hàng đợi tại giao

diện đầu vào tới các router hoặc tiếp theo, nhưng cũng có thể là tại các điểm quản

lý hàng đợi khác trong router . Các router truyền thống có duy nhất một hàng đợi

cho một giao diện tuyến đầu vào. Vì thế, nhiệm vụ của bộ lập lịch chỉ đơn giản là

lôi kéo các gói từ đầu ra của hàng đợi một cách nhanh nhất và có thể truyền dẫn

chúng theo các tuyến đó. Trong các router có kiến trúc CQS, mỗi giao diện có một

giai đoạn lập lịch để phân chia khả năng kết nối đầu của các giao diện vào các

hàng đợi phù hợp. Việc phân chia tuyến kết nối sẽ thực hiện được nếu lập lịch

thành công và lúc đó các gói đã được kéo từ mỗi hàng đợi sẽ được truyền đi.

Bởi vì các thành phần của gói (hoặc lớp lưu lượng ) mà các hàng đợi chứa

chúng, việc lập lịch là sau cùng và bắt buộc phải tuân theo quan hệ ưu tiên, giới

hạn latency hoặc việc phân phối băng thông giữa các lớp lưu lượng khác nhau. Một

bộ lập lịch có thể thiết lập một giá trị băng thông sẵn có tối thiểu cho một lớp đặc

biệt hơn bằng cách bảo đảm rằng các gói thường xuyên được lôi kéo từ các hàng

đợi (tức là bảo đảm rằng hàng đợi thường xuyên được phục vụ). Một bộ lập lịch

cũng có thể cung cấp tốc độ định hình (đặt một giá trị băng thông “cho phép” tối

thiểu cho một lớp đặc biệt hơn) bằng việc giới hạn thường xuyên việc phục vụ của

hàng dợi dành cho lớp đó. Việc quyết định khi thiết kế một bộ lập lịch là phải cả

hai giới hạn băng thông thấp và cao cho mỗi hàng đợi hoặc đặt giới hạn băng thông

cao hơn vào một số hàng đợi và đặt giớ hạn băng thông thấp hơn vào các hàng đợi

khác.

Các thuật toán lập lịch là việc thoả thuận thường xuyên giữa thời gian thực

hiện thông thường và thời gian thực hiện mong muốn. Mỗi bộ lập lịch khi thiết kế

sẽ có một phần service discipline -tạm dịch là khả năng phục vụ, điều này nhằm

lựa chọn để phục vụ các hàng đợi. Các bộ lập lịch đơn giản sẽ tập trung vào việc

bảo dưỡng các hàng đợi có thể đoán trước được. Nhiều bộ lập lịch tiên tiến cho

phép các quan hệ hoặc các giá trị băng thông chính xác ứng với mỗi hàng đợi và

chúng có thể tiếp tục đặt vào các khả năng phục vụ của chúng để đảm bảo rằng

băng thông trung bình hoặc latency đạt được cho mỗi hàng đợi là đã được giới hạn.

3. 1. 2. Tốc độ định hình

Như các chính sách hay việc đánh dấu, tốc độ định hình được sử dụng để

giới hạn hoặc hạn chế lớp lưu lượng chắc chắn không thể đoán trước được. Khác

với các chính sách và việc đánh dấu ở chỗ tốc độ định dạng yêu cầu các hàng đợi,

quản lý hàng đợi, và lập lịch mà không hề để ý đến việc các chức năng định dạng

xây dựng thành một bộ lập lịch cung cấp khả năng phân chia tuyến kết nối hay vận

hành độc lập trong một hàng đợi FIFO tại một kết nối hay tại một cổng chuyển

mạch . Tốc độ định hình thay đổi các đặc điểm về thời gian trong một lớp. Các

hàng đợi trong một hệ thống có thể rỗng một cách nhanh nhất (được giới hạn bằng

tốc độ kết nối ở đầu ra hoặc tốc độ truyền dẫn của cơ cấu chuyển mạch ) khi lưu

lượng tràn khi đi qua các hàng đợi. Khi một nguồn lưu lượng gốc đã truyền đi các

gói với tốc độ tương đối thì việc kết hợp các nguồn lưu lượng bùng nổ nhỏ có thể

sẽ gây tràn lưu lượng tại các điểm hàng đợi. Việc định hình cũng có thể giúp cho

việc cân nhắc mong muốn của khách hàng. Tốc độ định hình được ưu tiên trước

khi khách hàng kết nối mong muốn được phân chia khả năng dài hạn của dịch vụ .

3. 1. 3 Quyền ưu tiên chặt

Việc lập lịch bao gồm các lệnh hàng đợi bằng việc duy trì quyền ưu tiên và

bảo dưỡng hàng đợi tại mức ưu tiên chỉ khi các hàng đợi có các mức ưu tiên cao là

rỗng. Bộ lập lịch vận hành như vậy được gọi là một bộ lập lịch ưu tiên chặt. Giả sử

bộ lập lịch đó có bốn hàng đợi trong đó hàng đợi 1 có quyền ưu tiên cao hơn hàng

đợi 2, hàng đợi 2 có quyền ưu tiên cao hơn hàng đợi 3, hàng đợi 3 có quyền ưu tiên

cao hơn hàng đợi 4. Hàng đợi 1 có thể phục vụ nhanh nhất và truyền các gói đi

trong khi các gói ở hàng đợi khác phải đợi. Chỉ khi hàng đợi 1 rỗng thì bộ lập lịch

mới xét đến hàng đợi 2. Và tương tự, hàng đợi 3 được phục vụ tại tốc độ kết nối

nếu hàng đợi 1 và 2 rỗng, hàng đợi 4 được phục vụ nếu hàng đợi 1, 2, 3 rỗng. Dù

sao thì dịch vụ này cũng cho phép các hàng đợi có độ ưu tiên cao hoạt động và “bỏ

đói” các hàng đợi có độ ưu tiên thấp hơn. Ví dụ nếu lớp lưu lượng bắt đầu được

sắp xếp vào hàng đợi 1 có khả năng kết nối đầu vào là 100% cho một thời gian duy

trì liên tục, bộ lập có thể sẽ không bao giờ vòng lại để phục vụ các hàng đợi 2, 3, 4.

Ngăn ngừa sự bỏ đói phải yêu cầu luồng xuống của các thiết bị mạng được xử lý

đều đặn, các chính sách của luồng xuống hoặc tốc độ phân chia phải được đưa ra

để đảm bảo rằng lớp lưu lượng được sắp xếp vào hàng đợi 1 là không bao giờ được

phép vượt quá vài phần của khả năng kết nối đầu vào. Việc xử lý này bảo đảm rằng

hàng đợi 1 sẽ rỗng tại một thời điểm nào đó, mỗi khi rỗng cho phép bộ lập lịch sẽ

phục vụ các hàng đợi có độ ưu tiên thấp hơn