Quản lý hàng đợi đưa ra khả năng chia sẻ của một kết nối trong một kiểu điều khiển lưu lượng có sự cạnh tranh lưu lượng được phân phối qua nhiều hàng đợi tại giao diện đầu ra. Mọi lớp lưu lượng có yêu cầu đặc điểm lập lịch riêng phải được đặt trong chính hàng đợi của nó với mỗi gói trực tiếp tới hàng đợi thích hợp sử dụng thông tin tình huống thu thập từ tầng phân loại trước đó. Không có các hàng đợi riêng biệt nó không thể có khả năng cho tầng lập lịch sau phân biệt giữa nhiều lớp lưu lượng cạnh tranh một đường kết nối đơn. Một chức năng bộ quản lý hàng đợi đó là chịu trách nhiêm thiết lập và duy trì hàng đợi và phương thức hàng đợi trong router. Chức năng này bào gồm bốn hoạt động cơ bản:
Thêm một gói vào hàng đợi được chỉ rõ bằng tình huống của gói (như được thiết lập trong tầng phân loại) nếu hàng đợi không đầy.
Loại bỏ môt gói nếu hàng đợi đầy.
Loại bỏ một gói khi được yêu cầu bởi bộ lập lịch.
Giám sát lựa chọn sự chiếm dụng hàng đợi (số gói hoặc byte chiếm dụng hàng đợi ) và dựa vào một trong các bước thực hiện sau để giữ mức chiếm dụng thấp:
- Loại bỏ một gói (hoặc không chọn thêm một gói ) khi hàng đợi đã đầy
- Đánh dấu một gói khi hàng đợi bắt đầu đầy.
Tại một vài điểm mọi hàng đợi công bố đầy để đảm bảo rằng không một lớp lưu lượng nào dùng tất cả không gian nhớ hạn chế của router để tạo hàng đợi.
Tuy nhiên chỉ chắc chắn rằng một hàng đợi không thiếu các hàng đợi khác không đủ. Thêm vào đó một vài độ chiếm dụng trung bình của hàng đợi riêng biệt được giữ ở mức thấp. Việc quản lý hàng đợi tích cực có thời hạn thường áp dụng phương pháp giám sát và điều khiển độ chiếm dụng hàng đợi trung bình. Độ chiếm dụng trung bình thấp có hai lợi ích:
- Tồn tại các hàng đợi giải quýêt vấn đề bùng nổ lưu lượng không thể tránh khỏi mà không làm mất gói.
- Trễ trung bình trải qua bởi sự chia sẻ lưu lượng một hàng đợi cho trước tăng lên.
Giữ cho độ chiếm dụng giảm giúp giữ cho trễ end – to – end giảm.
Chú ý: Khi một sự bùng nổ xảy ra trong khi độ chiếm dụng ở mức cao nhiều gói có thể bị loại bỏ đồng thời nếu sự loại bỏ ảnh hưởng tới nhiều luồng TCP cùng một lúc thì phương thức tránh nghẽn ở tất cả các luồng trở nên đồng bộ và một sự chia sẻ loại bỏ xảy ra trong sự thực hiện trung bình.
Sự quan sát này nắm giữ cân bằng cho các router chỉ có một hàng đợi FIFO đơn trên mỗi đầu ra, như vậy tiện ích của quản lý hàng đợi tích cực là là có hiệu quả cân bằng mà không cần nhiều hàng đợi và bộ lập lịch.
4.4.1 Tránh ghi lại
Trước khi đi sâu tranh luận về cơ chế quản lý hàng đợi riêng biệt, điều quan trọng cần chú ý là việc đánh dấu gói được sử dụng như thế nào. Đánh dấu cho biết rằng một router đường lên tìm một gói ngoài hồ sơ, nhưng không đủ để biện minh cho việc loại bỏ tức thời. Với mục đích là để các router đường xuống có thể đối sử với các gói bị đánh dấu như là hệ thống lớp 2 khi nghẽn nội xuất hiện.
Tuy nhiên, có hai khả năng để giải quyết các gói như là hệ thống lớp 2. Một là hạ thấp quyền ưu tiên chuyển tiếp của chúng bằng ấn định chúng tới các hàng đợi khác dựa vào dấu hiệu của chúng. Cách khác là thay đổi thuật toán, một bộ quản lý hàng đợi được sử dụng để giữ độ chiếm dụng hàng đợi ở mức thấp là hạn chế độ chiếm dụng được phép cho các gói bị đánh dấu hơn là các gói không bị đánh dấu.
Gợi ý thứ nhất có thể dẫn tới việc sắp xếp lại các gói bị đánh dấu liên quan tới các gói không bị đánh dấu trong một lớp lưu lượng. Có thể là hàng đợi đi vào mà các gói bị đánh dấu bị loại bỏ được thiết kế một bộ lập lịch khác quyền ưu tiên liên quan tới hàng đợi thiết kế cho các gói thông thường trong cùng một lớp lưu lượng (xem hình 3.7). Việc sắp xếp lại xảy ra khi một gói bị đánh dấu đến trước một gói không bị đánh dấu.
Mặc dù IP không ngăn ngừa gói được sắp xếp bởi mạng nhưng hầu hết các giao thức end – to – end không lưu giữ trường hợp có khả năng này. Gần với điểm này hồ sơ gốc được đánh dấu gói ảnh hưởng tới việc quản lý hàng đợi tích cực được áp dụng trong mỗi gói – trong một hàng đợi đơn phục vụ tất cả các gói thuộc về lớp end – to – end cho trước không kể chúng được đánh dấu như thế nào.
4.4.2 Giảm thời gian chiếm đóng hàng đợi
Độ chiếm dụng của một hàng đợi tăng lên khi tải trọng cung cấp (lưu lượng đến) vượt quá tốc độ mà bộ lập lịch lưu thoát gói khỏi hàng đợi. Bởi vì tốc độ tại một bất kì hàng đợi riêng để lưu thoát phụ thuộc vào bộ lập lịch của nó tác động lại các lưu lượng từ các hàng đợi cạnh tranh khác cho việc truy cập kết nối đầu ra. Độ chiếm dụng có thể được xem như phản ánh mức nghẽn hiện thời tại giao diện đầu ra của router.
Để làm giảm độ chiếm dụng của một hàng đợi yêu cầu một vài phương pháp khơi mào phương thức tránh nghẽn trong giao thức truyền tải thông thường các luồng đi qua hàng đợi. Bởi sự xuất hiện trễ hạn chế trước bất kỳ giao thức truyền tải có thể bắt đầu tác động lại tới nghẽn trong một router, quản lý hàng đợi phải nhận hai loại nghẽn cơ bản sau:
- Nghẽn tạm thời, xuất hiện trong khoảng thời gian ngắn hơn thời gian phản ứng lại tránh nghẽn truyền tải vào các giao thức.
- Nghẽn dài hạn, kết quả của tình huống không đổi do tốc độ của tất cả các luồng đi qua hàng đợi.
Nghẽn tạm thời gây nên thường ngắn và liên quan đến sự bùng nổ lưu lượng từ một hoặc nhiều luồng. Thông thường một router không muốn loại bỏ các gói từ một bùng nổ trừ phi khi thực sự cần thiết và như vậy người vận hành và nhân viên lựa chọn kích cỡ hàng đợi để bảo vệ sự bùng nổ mà họ thường thấy. Tuy nhiên điều này luôn tình cờ một sự bùng nổ sẽ lấp đầy hàng đợi tại một điểm mà sự loại bỏ gói có khả năng lựa chọn.
Nghẽn trung bình của một hàng đợi được đo trong vài khoảng thời gian gần đây, độ chiếm dụng trung bình ảnh hưởng đến trễ trải qua bởi tất cả các gói đi qua hàng đợi đó.
Một bộ quản lý hàng đợi cần tiếp tục cung cấp phản hồi các giao thức truyền tải để giảm độ chiếm dụng dài hạn. Về nguyên tắc có thể áp dụng phản hồi theo hai cách:
- Trong dải đánh dấu của gói.
- Loại bỏ các gói.
Trong dải đánh dấu của các gói yêu cầu giao thức truyền tải tác động lại để nhận được các gói bị đánh dấu bởi sự tránh nghẽn ban đầu. Thực tế là việc loại bỏ được đề cập đến gần mạng IP. Bởi vì TCP sử dụng các gói mất để khơi mào phương thức tránh nghẽn của nó. Sự loại bỏ gói cũng có một lợi ích bên cạnh hiệu quả làm giảm tải đường xuống ngay lập tức.
4.4.2.1 Thông báo nghẽn tường minh
Mặc dù việc loại bỏ gói hiện thời là một cách được ưu tiên hơn để áp dụng phản hồi, nhưng là phương pháp tích cực (phương pháp đó không liên quan tới việc mất gói) của việc báo hiệu nghẽn được thiết kế và ước lượng. Sự loại bỏ gói thực chất lãng phí nguồn tài nguyên được sử dụng thiết lập gói tới router khi thấy sắp xảy ra nghẽn, như vậy chỉ dẫn nghẽn để tránh sự loại bỏ nếu tất cả khả năng đều có thể được để ý đến.
Một ví dụ về “thông báo nghẽn tường minh” ECN (explicit congestion notification) được mô tả trong RFC2481 [RFC2481]. Hai bít không sử dụng hiện tại CU (currently unused) từ trường DiffServ được định nghĩa lại như là bít ECT (capable Transport) và bit CE (congestion experience). Một người gửi giao thức truyền tải thiết lập bit ECT trên các gói ngoài giới hạn khi nó biết rằng cả hai điểm cuối luồng đều hiểu bít CE. Nếu không phản hồi điều khiển nghẽn được yêu cầu, bit CE không cần để ý. Khi một router dọc đường truyền muốn áp dụng phản hồi điều khiển nghẽn sẽ có hai lựa chọn:
• Nếu bít ECT được lập, lập bít CE.
• Nếu bít ECT được lập lại, loại bỏ gói.
Nếu RFC 2481 cũng để xuất sự thay đổi TCP, cho phép khách hàng TCP có khả năng khai báo nghẽn cụ thể thừa nhận mỗi mỗi điểm khác trong khi thiết lập kết nối và thiết lập bít ECT thích hợp trên gói dữ liệu kế tiếp.
4.4.2.2 Sự loại bỏ phía trước
Một vấn đề đặt ra khi loại bỏ gói là sẽ loại bỏ những gói nào. Từ một viễn cảnh thực hiện, loại bỏ gói vừa đến là đơn giản vì gói đó có thể loại bỏ một cách dễ dàng bằng cách không chèn nó vào trong hàng đợi. Tuy nhiên, một chiến lược thay thế là loại bỏ gói hiện thời tại đầu hàng đợi - loại bỏ phía trước DFS.
DFS xúc tiến phương thức tránh nghẽn của TCP - một gói bị mất thậm trí tại đầu hàng đợi được thông báo sớm hơn ở cuối hàng đợi có thể đã có một mức nghiêm trọng các gói bị ùn tắc [DFS94]. Tuy nhiên DFS thỉnh thoảng được coi như là một sự phức tạp không cần thiết, yêu cầu thao tác vận hành hàng đợi cụ thể loại bỏ tiếp nhận vào đang tồn tại.
DFS đặc biệt không phủ nhận tác động trên lưu lượng điều khiển không phải luồng, và một vài lợi ích không đáng kể có thể diễn đạt cho những luồng thời gian thực.
Một hàng đợi không rỗng đưa đến tất cả các gói phải chịu trễ, và gói đầu hàng đợi hầu như có khả năng sống sót không tin cậy bởi thời gian tới đích của nó.
4.4.4.3 Khi nào thực hiện?
Phần phức tạp nhất của thiết lập bộ quản lý hàng đợi là xác lập hệ thống điều khiển của chính nó để quyết định khi nào (mức độ nào) áp dụng phản hồi. Các thuật toán phải dựa vào tài khoản của ngữ cảnh gói được cung cấp bởi tầng phân loại gói. Ví dụ, sự phân loại MF luồng trọng điểm dẫn tới sự tách rời các hàng đợi trong tất cả các luồng ứng dụng, mỗi luồng được cách ly từ phương thức thụ động hoặc phương thức xâm chiếm của các luồng khác nhau. Router có thể có đủ khả năng áp dụng một quá trình quyết định ngưỡng đầy/không đầy đơn giản trên mỗi hàng đợi, chính các mục đích luồng riêng này là nguyên nhân gây ra nghẽn tạm thời.
Tuy nhiên nơi mà các router sử dụng phân loại TOS/DS cơ sở, hàng chục, hàng trăm, thậm chí hàng nghìn luồng ứng dụng có thể được sắp xếp vào cùng một hàng đợi. Trong trường hợp này sơ đồ phản hồi phải làm việc với các luồng thực sự gây nên nghẽn dài hạn tại các thời điểm cho trước. Một số sơ đồ địa chỉ hoá vấn đề bằng cách đưa vào các tín hiệu phản hồi thống kê, nó được bắt nguồn từ sự kết hợp các đầu vào biến đổi được, như là độ chiếm dụng trung bình của hàng đợi và đánh dấu trước khi áp dụng cho gói từ các router đường xuống. Một cơ chế phản hồi được biết đến như là một bộ tách sớm ngẫu nhiên (RED: Random Early Detection) được mô tả kỹ hơn trong phần tiếp theo.
4.4.3 Tìm kiếm ngẫu nhiên sớm
Trải qua nhiều năm nghiên cứu vấn đề điều khiển độ chiếm dụng trung bình của hàng đợi chia sẻ bởi nhiều luồng thay đổi khác nhau, tổ chức IRTF kết luận rằng giải pháp tốt nhất với router thực hiện trong tài khoản gồm tín hiệu phản hồi phân phối ngẫu nhiên, thống kê. Điển hình mà IRTF sử dụng cho phương thức này như là bộ tách sớm ngẫu nhiên RED.
RED sử dụng độ chiếm dụng trung bình của hàng đợi như là một tham số, một chức năng ngẫu nhiên mà nó quyết định có chế tránh nghẽn phải được khơi mào hay không.
Sau khi độ chiếm dụng trung bình tăng lên thì khả năng loại bỏ gói cũng sẽ tăng lên.
Hình 4.9 biểu diễn một hàm khả thi đơn giản.
- Độ chiếm dụng lên tới một ngưỡng thấp hơn minTH, các gói chuyển qua không bị ảnh hưởng (khả năng loại bỏ gói bằng không). Trên giới hạn minTH, khả năng loại bỏ gói tăng theo đường thẳng với khả năng vươn tới maxP cho một độ chiếm dụng của maxTH. Tại và trên maxTH các gói chắc chắn bị loại bỏ.
- Ba giai đoạn này thỉnh thoảng chỉ dẫn đến tránh nghẽn và điều khiển nghẽn.
Trường hợp xấu nhất kích thước hàng đợi bị giới hạn bởi maxTH. RED bắt đầu khai mào sự chỉ dẫn nghẽn trước khi hàng đợi bị đầy.
Độ chiếm dụng trung bình được tính toán lại tại mọi thời điểm một gói đến và dựa vào bộ lọc thông thấp hoặc độ chiếm dụng trung bình hoạt động trọng số hàm mũ (EWMA) của độ chiếm dụng hàng đợi tức thời. Công thức của nó là:
q inst avg
avg Q Q W
Q =(1−Wq). + . Qavg là độ chiếm dụng trung binh.
Qinst. là độ chiếm dụng tức thời.
Wq là trọng số của hàm di chuyển trung bình.
Wq có ảnh hưởng mật thiết tới tham số chiếm dụng trung bình theo độ chiếm dụng tức thời của hàng đợi. Giá trị cao hơn thì mức xung đột nhiều hơn và giá trị thấp hơn thì mức duy trì hơn. Mục đích là chọn lựa một giá trị cho phép RED bỏ qua tạm thời ngắn hạn mà không gây mất gói khi truyền dẫn nhưng có tác dụng duy trì các mức độ chiếm dụng trước độ trễ của mọi tác động một cách vô hạn hoặc những luồng đồng bộ của việc tránh nghẽn của TCP chịu ảnh hưởng.
Khả năng loại bỏ
Thời gian chiếm dụng trung bình 0
1 max
Min th Max th
100%
Không mất gói Khả năng loại bỏ tăng
Không bị loại bỏ
Loại bỏ đảm bảo
Hình 4.9: khả năng loại bỏ biến thay đổi với thời gian chiếm dụng hàng đợi
Một router có thể giữ các giá trị minTH, maxTH và maxP khác nhau cho các hàng đợi khác nhau, cân bằng với tổng không gian khả dụng của hàng đợi, số lượng hàng đợi yêu cầu và độ trễ, độ rung pha hạn chế của lớp lưu lượng sử dụng các hàng đợi khác nhau. Thêm vào đó Wq phải khác nhau trong mỗi hàng đợi.
Chiến lược loại bỏ ngẫu nhiên có những đặc điểm hữu ích sau:
• Chúng tạo ra một cơ chế phản hồi không tích cực cho TCP và cường độ tăng lên theo hàm mức nghẽn trong router.
• Các luồng chịu sự chi phối chia sẻ thông qua hàng đợi (các gói vào hàng đợi thường xuyên hơn) thì chịu cường độ phản hồi tốt hơn.
• Sự đồng bộ được giảm tới mức cực tiểu giữa nỗ lực tránh nghẽn của phiên truyền dẫn độc lập chia sẻ một hàng đợi riêng biệt.
Sự bắt đầu loại bỏ ngẫu nhiên sớm (trước khi hàng đợi thực sự sử dụng hết hoàn toàn không gian cho phép của nó) tăng lên thì có thể dễ dàng xếp ngoài vùng nghẽn tạm thời trước độ chiếm dụng hàng đợi là quá cao. Quá trình ngẫu nhiên phân phối loại bỏ trong giai đoạn đầu làm giảm tính ngẫu nhiên của nhiều luồng cho loại bỏ gói.
Hai khoá giả định làm nền tảng cho loại bỏ dựa vào quản lý hàng đợi tích cực :
• Nhiều hoặc hầu hết các tầng gây ra nghẽn tạm thời là nền tảng TCP và trước đó đáp lại tới phản hồi không tích cực của mất gói sớm.
• Các gói thực sự loại bỏ thuộc về luồng (hoặc các luồng) TCP gây ra nghẽn.
Sự vắng mặt của các phương tiện phân loại và hàng đợi mỗi luồng mà các giả định này có thể không luôn có hiệu lực. Lúc này chúng thường hợp lý. Việc các gói đến trong suốt một khoảng thời gian nghẽn sẽ thuộc về các luồng chiếm dụng nhiều hơn là các luồng khác. Nó giữ vững lý do để loại bỏ gói trong suốt khoảng thời gian nghẽn như gặp phải một luồng góp phần gây nghẽn. Đặc tính thời gian của các luồng gây nghẽn cho phép RED và biến thể của nó tập trung các luồng thích hợp.
4.4.3.1 RED theo trọng số
Các bộ quản lý hàng đợi không hạn chế việc cung cấp một loại phương thức đơn trên một vài hàng đợi cho trước thông tin thêm vào từ tình huống của gói có thể lựa chọn một trong nhiều chức năng huỷ bỏ gói. Ví dụ, một gói được đánh dấu tại một số điểm đường xuống cho quyền ưu tiên trong một hồ sơ lưu lượng là đối tượng để kiểm soát, huỷ bỏ, xâm chiếm thêm. So sánh các gói khác được phân loại trong cùng một hàng đợi (các gói được đánh dấu vẫn được qua khi mạng gần như không bị nghẽn). Chủ