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

Chia sẻ: Tran Le Kim Yen Tran Le Kim Yen | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

76
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 .

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

ĐỒ Á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
Lập lịch ưu tiên chặt vô cùng hữu dụng trong việc cung cấp một lớp lưu lượng với latency thấp. Giả sử rằng lớp X yêu cầu latency xuyên suốt thấp sẽ được sắp xếp vào hàng đợi có độ ưu tiên cao nhất tại mỗi hop và có tốc độ phân chia hoặc nếu không thì phải được giới hạn để không bỏ đói các hàng đợi khác. Điều gì sẽ xảy ra nếu một gói từ lớp X đến. Nếu bộ lập lịch nhàn rỗi, hàng đợi có độ ưu tiên cao nhất sẽ được phục vụ ngay lập tức. Nếu bộ lập lịch bận truyền dẫn một gói từ các hàng đợi khác, hàng đợi có độ ưu tiên cao nhất phải đợi cho đến khi nào nó truyền dẫn xong gói đó. Trường hợp tồi tệ nhất, latency quyết định tốc độ của tuyến kết nối và kích thước tối đa của gói hoặc MTU (Maximum Transmission Unit)-khối truyền dẫn lớn nhất của tuyến kết nối. 3. 2. Lập lịch gói Gói tin của các mạng cho phép người sử dụng phân chia các tài nguyên thành các bộ đệm và các kết nối băng thông . Tuy nhiên sẽ nảy sinh một vấn đề tranh luận về việc phân chia tài nguyên một cách cần thiết : Đưa một số người sử dụng (các luồng hoặc các kết nối) đa thành phần tại tuyến kết nối, chương trình lập lịch gói sẽ rất cần thiết để định rõ xem gói nào tiếp theo sẽ được phục vụ (hoặc truyền đi). Nói cách khác, trong các nguồn tài nguyên mạng, các thuật toán phức tạp chỉ phục vụ cho các lưu lượng người dùng có độ ưu tiên cao phù hợp với các yêu cầu về QoS. Ví dụ, lưu lượng yêu cầu thời gian thực phụ thuộc vào trễ, trong khi các lưu lượng data lại không phụ thuộc. 3. 2. 1 Tổng quan Nhiều thuật toán lập lịch gói đã và đang được phát triển nhằm cung cấp cho các dịch vụ mạng chuyển mạch gói. Nhìn chung, s ự khác biệt ở các dịch vụ mạng là chúng cung cấp và có thể được phân loại thành các dạng như sau:
 “Best Effort” các dịch vụ không có sự bảo đảm về QoS . Thuật toán lập lịch của mạng này không yêu cầu thực hiện các thuộc tính về QoS của luồng gói . Ví dụ như trong sự sắp xếp vào trước ra trước FIFO (First In First Out) hoặc đến trước, phục vụ trước FCFS (First Come First Served ).  Tốt hơn Best Effort :các dịch vụ mà không qui định, bảo đảm về độ trễ, nhưng nó sẽ cố gắng là một Best Effort để thử cung cấp các yêu cầu về QoS. Khi sắp xếp đưa ra sự bảo đảm chính xác ở thời gian trễ, tuân theo nguyên tăc cách ly của các luồng gói. Loại này còn có thể đạt được ở mức cao hơn khi chia sẻ tài nguyên chuyển mạch mạng. Một ví dụ của loại sắp xếp này là FIFO+.  “Bảo đảm sự thông suốt”: Các dịch vụ bảo đảm mỗi luồng đều có sự thoả thuận về băng thông bất chấp sự xử lý của tất cả những luồng lưu lượng khác. Khi điều khiển được chấp nhận một cách chính xác và các điều khiển truy nhập lưu lượng được sử dụng để giới hạn tốc độ đến của các gói trong hệ thống, các giới hạn trễ cao cho mỗi luồng có thể đạt được. Ví dụ về sự sắp xếp này gồm WFQ, đồng hồ ảo và WF2Q.  Giới hạn trễ Jitter: Các dịch vụ bảo đảm các giới hạn cao và thấp về độ trẽ của các gói quan sát. Các dịch vụ này được thực hiện mà không duy trì công việc lập lịch. Điều khiển một cách chính xác trên cơ sở các đặc điểm ưu tiên của lưu lượng, và các lưu lượng được yêu cầu . Một ví dụ về hệ thống này là Jitter-EDD(Jitter-Earliest-Due-Date) tạm dịch là jitter thời kì đúng sớm nhất.
Dữ liệu bộ nhớ Các gói Các gói Gói vào gói ra địa chỉ ghi/đọc Gói Lập lịch gói đầu CPU Khối tìm gói Hình 3. 1: Lập lịch gói Hình vẽ trên minh hoạ việc lập lịch một gói mà, ví dụ có thể xác định vị trí tại đầu vào của khối chuyển mạch hoặc router . CPU là một trung tâm tính toán các giá trị thời gian và các hệ thống điều khiển khác. Khối tìm gói là khối lựa chọn các gói tiếp theo để truyền dẫn tuỳ thuộc vào các giá trị thời gian mà CPU đã tính. 3. 2. 2 Các thuật toán 3. 2. 2. 1 FIFO Thuật toán lập lịch đơn giản nhất là FIFO. Trong thuật toán này bộ lập lịch sẽ đưa ra lệnh để truyền các gói đến tại đầu vào của hàng đợi và loại bỏ các gói đến nếu hàng đợi đầy. Dù sao thì bộ lập lịch cũng không thể sử dụng gì khác, vì thế nó không thể cấp phát một cách rõ ràng cho những người sử dụng có độ trễ thấp hơn những người khác. Hơn nữa, jitter có khuynh hướng tăng lên một cách đột ngột tuỳ theo số lượng các Hop, khi độ trễ hàng đợi tại của các gói tại các Hop khác nhau một khoảng [35]. FIFO+ là một quá trình thử để gây ra sự phân chia các hàng FIFO (tất cả những người sử dụng trong cùng một lớp có độ jitter là ngang nhau) qua tất cả các Hop theo các đường có jitter tối thiểu. Với mỗi Hop chúng ta đo độ trễ trung b ình
cho các gói trong mỗi lớp tại node đó. Sau đó chúng ta tính toán cho mỗi gói khác nhau với độ trễ ngoại lệ của chúng và tính trung bình của lớp. Chúng ta cộng “hoặc trừ” giá trị khác nhau này vào một trường trong tiêu đề gói. Sau đó tính tổng cho các gói này từ giá trị trung bình của lớp. Trường này cho phép mỗi node tính toán khi các gói đã đến. Bộ lập lịch tập hợp các khả năng phân chia kết nối và lập bộ đệm đầu vào cho mỗi người sử dụng các dịch vụ đó. Chúng ta gói đó là phân phối phần chia hợp lý lớn nhất và nhỏ nhất-max-min fair share nếu giá trị lớn nhất và nhỏ nhất phân chia của một người sử dụng yêu cầu vẫn chưa đủ làm thoả mãn. Hàng đợi FIFO (bao gồm cả FIFO+) không thể cung cấp một sự phân chia hợp lý hay là không cung cấp “giấy thông hành”. Giấy thông hành có nghĩa là một cách cư xử xấu của một người sử dụng (bằng việc gửi đi các gói tại một tốc độ cao hơn phần phân chia hợp lý của nó) có thể không ảnh hưởng tới việc nhận của những người khác. Với hàng đợi FIFO trễ chính của người sử dụng có thể tăng lên nếu tổng các tốc độ đến của tất cả những người sử dụng tăng lên. Theo đó, chúng ta có thể đưa ra một số biện pháp lập lịch mà nó có thể cung cấp cả hai giá trị hợp lý và “giấy thông hành”. 3. 2. 2. 2 Leaky Buckets (Thuật toán gáo rò) Tốc độ phân chia đạt được bằng việc thường xuyên hạn chế khi mỗi lần hàng đợi được phục vụ và bộ lập lịch không làm gì cả. Nếu một gói đến với một khoảng thời gian ngắn hơn thời gian cho phép của bộ lập lịch, chúng được xếp hàng vào một ngưỡng có thể gây tràn. Hình vẽ 3. 2 cho thấy một bộ lập lịch không bao giờ thử cho hàng đợi đầu thường đến với mỗi T giây, điều này không quan trọng nếu các gói đến được bó chặt lại, chúng sẽ xuất phát sau khoảng T giây.
T Các gói đến đã được bó 1 2 3 4 1 2 3 4 Gói đi Gói đến Phân loại Hàng(được phân chia lớp) Schedule Hàng đợi(khác) Cổng M Ít nhất Tgiây giữa hai lần Hình 3. 2 :Sự phân chia yêu cầu lập lịch thời gian cho các hàng đợi Hình 3. 2 đề cập đến các hàng đợi chưa biết khác, việc phân chia không nhất thiết là phải lập lịch phân chia chung. Việc phân chia cũng có thể kết hợp với một hàng đợi độc lập với các hàng đợi khác trong hệ thống. Dù sao, nếu việc phân chia được dự định là bắt buộc tốc độ bit trung bình qua hàng đợi, thời gian phục vụ cần biến đổi linh hoạt, nó phụ thuộc vào số bytes truyền dẫn, độ dài gói tiếp theo trong hàng đợi và tốc độ bit trung bình. 3. 2. 2. 3 Round-Robin(RR) Trong thuật toán lập lịch RR, gói tin sẽ được tới xếp hàng trước bởi người sử dụng. Người phục vụ cắt mỗi hàng trong vòng và phục vụ gói tin từ một hàng không rỗng bất kì. Một sự cư xử không đúng đắn sẽ làm đầy hàng của nó, và người sử dụng khác sẽ không bị ảnh hưởng . Vì thế, RR có thể cung cấp một sự bảo hộ. RR là một cố gắng để đối xử với tất cả mọi người sử dụng như nhau và cung cấp cho họ một sự chia sẻ như nhau về các liên kết. Nó thực hiện một cách hợp lý khi
tất cả mọi người sử dụng có cùng khối lượng tin và tất cả các gói tin có cùng kích cỡ (như là những tế bào trong mạng ATM). Nếu người sử dụng có khối lượng tin khác nhau thì trọng số của RR(WRR) phục vụ một người sử dụng tương ứng với khối lượng tin của anh ta. Xét một RR có hai người sử dụng A và B có khối lượng tin WA=3, WB=7 tế bào đối với từng người, hệ thống sáp xếp sẽ đưa ra 30 % [=WA/ WA+ WB ] sự chia sẻ kết nối cho người A v à 70 % [=WB/ WA+ WB ] sự chia sẻ kết nối cho người B. Một tế bào đầu ra liên tục trong một vòng có thể là AAABBBBBB. Một sự tiến hành tốt hơn của WRR một cách hiệu quả đồng bộ tới cấu trúc hệ thống và đưa ra ABBABBBBB. Như thế, người sử dụng A không cần 7 đơn vị thời gian trước khi có tín hiệu gửi đi. DRR(Deficit RR)-vòng RR hụt có thể sửa đổi WRR để cho phép biến đổi kích cỡ gói tin theo một kiểu hợp lý. Ý tưởng cơ sở là sử dụng RR với một mức phục vụ ấn định cho mỗi hàng. Sự khác biệt duy nhất với RR truyền thống là: nếu một hàng không thể gửi một gói tin vào vòng trước vì kích cỡ của gói tin quá lớn (rộng), thì phần còn lại ở mức trước được cộng vào mức của vòng kế tiếp. Vì vậy, sự thiếu hụt được ghi lại chi tiết trong thuật toán. Giả sử rằng mối luồng i cấp cho Qi bít trong mỗi vòng ; sẽ có một sự kết hợp thay đổi trạng thái DCi ghi nhớ những sự thiếu hụt. Mỗi vòng là 1 RR ảnh hưởng qua lại lẫn nhau dưới hàng chưa thực hiện được. Để triệt tiêu những hàng rỗng, một bảng phụ lục Active được giữ và gồm có không những chỉ số của hàng mà bao gồm cả những phần tối thiểu của một gói tin. Gói tin đến từ đường truyền khác nhau thì sẽ được để ở các hàng khác nhau. Để số byte của đầu đường truyền (HDL) gói tin vào 1 hàng i trong vòng k bởi byte (k). Bất cứ lúc nào 1 gói tin đến hàng vòng i một cách nhanh chóng, i sẽ cộng tới cuối của thuật toán trong phép toán: DCi + Qi, gửi ra hàng ngoài HOL DCi
Tuy nhiên DRR chỉ sử dụng hợp lý khi thời gian kéo dài hơn thời gian vòng. Ở thời gian ngắn hơn, một vài người sử dụng có thể có thêm hình thức phục vụ ( chọn giới hạn bít được gửi ) hơn người khác. 3. 2. 2. 4 Stop-And-Go Stop-And-Go sử dụng một cấu trúc mang tính chiế n lược ở mỗi chiến lược, trục thời gian là đường chia trong cấu trúc đó là một khoảng dài không đổi T. Stop- And-Go định rõ sự khởi hành và đến đích cho mỗi liên kết. Tại mỗi chuyển mạch, khung chứa các gói của tuyến liên kết đến được sắp xếp lại để các khung của tuyến kết nối đầu ra xuất phát bằng cách thiết lập một giá trị trễ là ∂ với 0≤ ∂< T. Việc truyền dẫn của mỗi gói có đến được trên mỗi kết nối l trong một khung f luôn được trì hoãn cho tới khi khung tiếp theo bắt đầu. Stop-And-Go bảo đảm rằng các gói tin trên cùng một thứ tự ở nguồn sẽ được ở cùng một thứ tự trong mạng. Nếu hàm lưu lượng ở nguồn là (r;T) độ ê m (i. e, không thể hơn r. T bit được thay đổi trong suốt thứ tự T ). Nó đáp ứng những gói tin có cùng đặc điểm lưu thông trên mạng. Hình 3. 3 :Mức khung G với G = 4, f1 = 3, f2 = 2, f3 = 2
Để kết nối các vấn đề xoay quanh vòng, bản dịch tổng quát của “Stop-And- Go” với thứ tự có kích cỡ phức tạp được đưa ra các thứ bậc cấu trúc. Cho level-G với thứ tự cỡ T1, …, TG chúng ta có Tg =fgtg ( với g = 1, …, G) Như sự mô tả ở hình 3. 3. Gói tin ở level-g- kết nối cần phải được giám sát bởi các qui tắc của “Stop and Go” với cỡ frame, Tg, i. e, gói tin cấp g có thể đến đầu ra của liên kết trong suốt 1 khoảng thời gian sẽ không trở nên thích hợp cho quá trình truyền nữa, cho đến khi khởi động thứ tự Tg tiếp theo. Cũng như vậy đối với 2 gói tin có cỡ thứ tự khác nhau, gói tin có cỡ thứ tự nhỏ hơn sẽ không được ưu tiên trước gói tin có cỡ thứ tự lớn hơn. Đặc biệt, ở mỗi mắt xích, bất cứ một cấp g nào đến đầu vào liên kết i sẽ được sắp đặt tới một cấp g ở đầu ra của liên kết j bởi sự đưa ra giữ chậm liên tục như được thể hiện ở hình 3. 4 Hình 3. 4 Trễ khung ghép tại một node chuyển mạch Kết quả là, nếu luồng lưu lượng của một kết nối mô tả đặc điểm của nguồn như (r, Tg )- độ êm smoth, nó sẽ đáp ứng cả những dữ liệu có c ùng đặc điểm thông
suốt trên mạng. Thời gian trễ cảu cấp g ở nút vòng, có thể được giới hạn trong khoảng Tg  trạng thái trễ
kỳ được giới hạn bởi T khoảng thời gian. Ở HRR, gói tin được truyền đi trong cùng một frame ở đầu vào tới mạng không cần thiết ở lại trong c ùng một frame ở mạng, tuy nhiên về chi tiết không có gì hơn 3 gói tin từ kết nối được truyền trong suốt khoảng thời gian được giữ xuyên suốt mạng. Từ khi HRR sử dụng cấp chiến lược nó chỉ có vấn đề về sự liên kết giữa trễ và băng thông ấn định đều đặn. 3. 2. 2. 5 EDD Phí sớm nhất của ngày Ở lớp lập lịch EDD có thời gian chúng ta phân chia mỗi gói tin một đường giới hạn và lập lịch phục vụ các gói tin trong lệnh của nó ở dòng giới hạn. Nếu thời hạn vượt quá sự cho phép thì một vài gói tin sẽ lạc mất đường giới hạn của nó. Hiển nhiên là, với EDD, gói tin đã được phân chia đường trễ nhỏ hơn so với những gói tin phân chia theo giới hạn hơn từ thời gian đến của chúng. Trễ EDD là một sự mở rộng của EDD với quá trình đặc biệt là thời hạn phân chia đường giới hạn tới ở một tốc độ cao nhất. Lập lịch được thiết lập tại đường giới hạn của một gói tin có thể được gửi đi vì nó nhận được không nhanh hơn là tốc độ đỉnh của nó. Vì vậy mỗi gói từ một phiên bắt buộc phải tuân theo tốc độ đỉnh có giới hạn trễ mà nó độc lập với băng thông dành riêng, nhưng ở giá trị của việc sử dụng tốc độ đỉnh cung cấp sẽ loại bỏ thời gian thống kê lợi ích đa dạng. Jitter EDD đưa ra trễ EDD để cung cấp giới hạn trễ Jitter ( một giới hạn trên thời gian trễ lớn nhất khác biệt giữa 2 gói tin). Jitter EDD kết hợp chặt chẽ với một trễ EDD có thời hạn trước bởi một máy điều chỉnh trễ Jitter. Sau khi một gói tin được phục vụ bởi một người phục vụ, khoảng trống trong nó được đánh dấu với sự khác biệt giữa đường giới hạn của nó và thời gian kết thúc thực. Một máy điều chỉnh ở đầu vào của người phục vụ kế tiếp nắm lấy gói tin cho giai đoạn trước khi nó được làm cho tương thích với thời hạn.
Một thời hạn thực hiện trễ jitter được điều chỉnh có thể gỡ bỏ kết quả hàng trễ biến đổi ở nút trước vì vậy phải tránh sự phá vỡ cấu trúc của mạng chính xác hơn, nếu akn và ekn là quá trình đến và sự thích hợp về thời gian cho K của gói tin ở nút thứ n, tính riêng từng cái thì : eko= aok (3. 1) en+k= ekn + dn + ln, n+1 dn là giới hạn giữ chậm của nút trước và ln, n+1 là liên kết với giữ chậm với giữ chậm truyền lại giữa nút n và nút n+1. Gói tin thứ k thích hợp cho việc phục vụ ở nút sau nó chỉ thích hợp cho việc phục vụ sau khi một khoảng thời gian ấn định dài dn+ ln, n+1, - là khoảng thời gian giữ chậm dài nhất có thể ở nút trước và liên kết phía trước. Vì vậy, nếu một gói tin được phục vụ trước giới hạn trễ của nó ở nút trước, máy điều khiển trễ jitter ở nút dòng dưói sẽ cộng đủ trễ để chuyển đổi gói tin này thành trễ dài nhất có thể. Bởi thế cho nên, một mạng của lập lịch jitter EDD có thời hạn có thể đưa ra băng thông end-to-end, trễ, và giới hạn trễ jitter. Tuy nhiên, máy trễ jitter rất khó để thực hiện. Không chỉ nó đòi hỏi trễ trên mỗi liên kết, mà nó còn đòi hỏi mạng phải bảo vệ thời gian đồng bộ ở nút liền kề trong tất cả thời gian. Từ đó ở thế giới thực, đồng hồ thời gian trôi ra ngoài sự đồng bộ ngoại trừ chính xác, trễ jitter điều chỉnh bao hàm cả hệ thống của máy móc thực hiện được. 3. 2. 2. 6 RCSP ưu tiên tốc độ điều khiển cố định Khi thuật toán EDD có thể cung cấp linh hoạt giới hạn trễ và băng thông cung cấp, nó dựa trên một hạng cơ cấu ưu tiên mà không đi với một phần cứng cơ khí, rất khó để thực hiện mạng tốc độ cao . RCSP là mục đích để đạt được sự linh hoạt trong cung cấp thời gian trễ và băng rộng tốt đẹp như việc thực hiện một việc đơn giản.
Như mô tả ở hình (4. 4) một RCSP phục vụ bao gồm tốc độ điều khiển và ưu tiên thời hạn cố định một cách lôgíc, một tốc độ điều khiển phù hợp với mỗi phục vụ. Khi gói tin đến người phục vụ, một thời gian thích hợp được tính toán để gắn vào gói tin bởi máy điều chỉnh. Lưu lượng yêu cầu Mức độ bất lợi 1 Máy đc 1 FIFO 2 Máy đc 2 FIFO Lưu lượng vào Lưu lượng ra N Máy đc N FIFO Hình 3. 5 Một bộ điều chỉnh với N đường truyền Ví dụ, một dòng lưu thông được mô tả bằng (Xmin, XAVCI) nếu thời gian giữa 2 gói tin bất kỳ trong dòng hơn Xmin và khoảng thời gian trung bình của gói tin trong suốt quá trình truyền dài I và hơn XAVC. Ta có Xmin nhỏ hơn hoặc bằng Xavc
ai, k là thời gian mà gói tin thứ k từ vùng I chuyển đến người phục vụ. Từ công thức trên đây chúng ta có thể thấy rằng ei, k luôn luôn lớn hơn hoặc bằng ai, k. Thời gian tương thích của một gói tin ở chỗ phục vụ là liên tục thì nó luôn luôn thoả mãn quá trình lưu thông (Xmin, Xave, I). Lập lịch trong RCSP sử dụng một chính sách ưu tiên cố định (SP) nó luôn lựa chọn gói tin ở đầu của mức ưu tiên cao nhất mà không rỗng . Đánh số của giới hạn giữ chậm liên kết với mức ưu tiên P và d1, d2, . . ., d∞ (d1< d2< . . .
Nếu ta yêu cầu luồng đầu ra thoả mãn (Xmin, Xabe, 1), người lập lịch trình SP phải đưa thời gian khởi hành của gói thứ k từ phần thứ i, di, k trở lại phần điều chỉnh thông tin, vì vậy tính có thể chọn được thời gian thiết lập thuật toán đã được đưa ra trong (4. 2) có thể biến đổi dưới dạng: với k≤ 0, ei.k 1, ei,1  ai,1,   ei,k  max di,k  Xmin , di,k1/ Xave 1  I, ai,k (3. 5) với k > 1. 3. 2. 2. 7 GPS (Generalized Processor Sharing): Phân chia bộ xử lý chung GPS là một ý tưởng thực thi sáng suốt mà nó cung cấp một cặp max – min chính xác được định rõ ở nơi chia sẻ. GPS là khá hợp lí mà nó định rõ toàn bộ khả năng đưa tới tất cả các phần còn lại trong sự cân đối với giá trị yêu cầu băng thông. Một cách cơ bản thì thuật toán này được xây dựng trên cơ sở một mẫu dòng lí tưởng. Điều đó có nghĩa là chúng ta thừa nhận rằng một người lập lịch trình GPS có thể đáp ứng tất cả các phần còn lại một cách tức thời và chỉ định tới các phần này. Nhưng trong các hệ thống thực chỉ có một phiên có thể được đáp ứng tại một thời điểm và các gói không thể bị cắt thành các thành phần nhỏ hơn được. Một lớp quan trọng mà được gọi là thuật toán gói sắp xếp hợp lý (packet fair queuing – PFQ) có thể được định nghĩa trong đó người lập lịch trình cố gắng sắp xếp các gói còn lại bằng một lịch trình gần đúng GPS, như là sắp xếp hợp lý theo trọng lượng (weighted fair queuing – WFQ), đồng hồ ảo, hay sắp xếp hợp lý theo đồng hồ riêng
(self-clock fair queuing - SCFQ). Những nội dung này sẽ được thảo luận trong chương sau. Trước tiên chúng ta đi vào nghiên cứu ý tưởng thuật toán GPS. Thừa nhận rằng một tập hợp các phiên N (kết nối), được đánh số 1, 2, . . . N, chia sẻ các kết nối ngoài chung của một máy chủ GPS. Với i  (1, 2, . . . N), đặt ri là giá trị nhỏ nhất của của phiên i. Bằng phương pháp quy nạp có thể bảo đảm rằng: N (3. 6) r  r i i 1 ở đây r là công suất của đường liên kết ngoài. Đặt B(t) là sự thiết lập phiên sau tại thời điểm t, theo GPS [15], phiên sau i sẽ được định rõ bởi một chỉ số phục vụ gi(t) tại thời điểm t là: ri (3. 7) gi (t )  r  r jB ( t ) j Chúng ta sẽ dùng một ví dụ để minh hoạ cho chỉ số phục vụ chỉ rõ nguyên lí của hệ thống GPS. Đặt Ai(τ, t) là số cuộc khởi hành của phiên thứ i trong khoảng (τ, t). Wi(τ, t) là số dịch vụ nhận được bởi phiên i trong cùng khoảng, và Qi(t) là số phiên lưu thông i sắp xếp trong máy chủ tại thời điểm t, nghĩa là: Qi(t)= Ai(τ, t) - Wi(τ, t). Chú ý rằng, hệ thống trở thành rỗi (không thực hiện) thì tất cả các tham số có thể được reset khởi tạo về 0. Định nghĩa 3. 1: Một chu kỳ bận của hệ thống là khoảng thời gian lớn nhất mà trong đó máy chủ luôn luôn bận với các gói luôn được truyền qua. Định nghĩa 3. 2: Chu kỳ đợi của phiên i là bất kỳ chu kỳ thời gian nào mà trong đó các gói của phiên i được tiếp tục xếp hàng trong hệ thống
Định nghĩa 3. 3: Chu kỳ bận của phiên i là khoảng thời gian lớn nhất (τ1, τ2) mà đối với bất kỳ t  (τ1, τ2] các gói của phiên i rời đi lớn hơn hoặc bằng so với ri nghĩa là: Ai(τ1, t) ≥ ri(t – τ1) với t  (τ1, τ2). Sau khi xem xét hình 4. 5 chúng ta thấy rằng công suất của máy chủ là r = 1, và với 3 kết nối được đánh số 1, 2, và chia sẻ tới cùng một liên kết ra của máy chủ 1 1 1 thì ở đó có: r1  ; r2  ; r3  6 3 2 r1 = 1/6 r r= 1 Ser ver r2 = 1/3 r2 = 1/2 Hình 3. 6 GPS server với mức nhập vào Giả sử rằng mỗi một gói có độ dài xác định và cần đúng một đơn vị thời gian để truyền qua. Tại thời điểm t = 0, phiên 1 bắt đầu một chu kỳ bận phiên trong đó từ phiên 1 rời đi khỏi máy chủ với tốc độ 1 gói trên một đơn vị thời gian. Tại thời điểm t = 1, các gói từ phiên 2 cũng bắt đầu rời khỏi máy chủ với cùng một tốc độ như vậy. Phiên 3 bắt đầu một chu kỳ bận phiên tại t = 3, với tốc độ rời đi của các gói là tương tự. Máy chủ GPS sẽ chỉ rõ một tốc độ dịch vụ cho mỗi phiên theo công thức sau:
 1, 0  t  1  g1 (t )  1/ 3,1  t  3  1/ 6, t  3   0, 0  t  1  g 2 (t )  2 / 3,1  t  3  1/ 3, t  3  0, 0  t  3 g 3 (t )    1/ 2, t  3 Chú ý là gi(t) cũng là độ dốc của đường cong phục vụ của phiên i tại thời điểm t. Hơn nữa, tại bất kỳ thời điểm nào trong chu kỳ bận của hệ thống, luôn có: N  g i (t )  r do thuộc tính bảo toàn công việc. Thời điểm khởi hành của của gói đầu i 1 tiên của các phiên 1, 2, 3 theo thứ tự là 1, 2. 5, và 5. Chỉ số tính chất tốt của phần tồn phiên i có thể được định nghĩa là Wi ( 1 ,  2 ) / ri . Điều này có nghĩa là trong bất kỳ khoảng thời gian nào (τ1, τ2], đối với bất kỳ hai phần tồn nào của phiên i và j lịch trình được gọi là hoàn thiện khi và chỉ khi: Wi ( 1 , 2 ) W j ( 1 ,  2 )  ri rj Lúc này máy chủ GPS là đạt hiệu quả hoàn thiện. Theo một cách khác, PFQ là một sấp xỉ của lịch trình GPS mà không tạo ra một giả định GPS của kích cỡ gói rất nhỏ. Một cách trực quan, PFQ dựa trên cơ sở duy trì một hàm chức năng toàn cục. Hàm chức năng toàn cục này được sử dụng để tính toán thời gian kết thúc ảo cho mỗi gói hoặc cho gói HOL của mỗi phiên trong hệ thống. Biểu thời gian của một gói là tổng thời gian bắt đầu ảo của chúng và thời gian cần để truyền gói tại băng thông riêng của chúng. Các gói được cung cấp việc tăng bậc trong biểu thời gian của chúng.