Các giải thuật chống tắc nghẽn

Các nguyên tắc chung để điều khiển tắc nghẽn

Nhiều bài toán trong các hệ thống phức tạp, ví dụ như trong mạng máy tính, có thể được xem xét theo quan điểm của lý thuyết điều khiển (control theory). Cách tiếp cận này dẫn đến việc chia các giải pháp thành hai loại: vòng đóng và vòng mở (closed loop and open loop). Các giải pháp dạng vòng đóng cố gắng giải quyết vấn đề tắc nghẽn bằng cách đưa ra thiết kế tốt cho mạng, thực chất là để đảm bảo tắt nghẽn sẽ không xảy ra. Một khi mạng được khởi động và chạy, sẽ không có việc sửa chữa giữa kỳ.

Các công cụ thực hiện việc điều khiển kiểu vòng mở bao gồm việc quyết định khi nào nên chấp nhận luồng giao thông mới, quyết định khi nào thì bỏ qua các gói tin và bỏ qua gói nào. Tất cả các công cụ trên đều có đặc điểm chung là chúng đưa ra các quyết định mà không quan tâm đến trạng thái hiện hành của mạng.

Ngược lại, các giải pháp kiểu vòng đóng dựa trên quan niệm về chu trình phản hồi thông tin. Cách tiếp cận này bao gồm 3 phần:

1. Giám sát hệ thống để phát hiện nơi nào và khi nào xảy ra tắc nghẽn.
2. Chuyển thông tin đến những nơi cần có những hành động ứng phó.
3. Điều chỉnh lại hoạt động của hệ thống để khắc phục sự cố.

Nhiều kiểu đo lường có thể được sử dụng để giám sát một mạng con để phát hiện ra tắc nghẽn ở đó. Các kiểu đo lường thường dùng nhất là tỉ lệ các gói tin bị bỏ qua do thiếu không gian trữ đệm, chiều dài trung bình của các hàng đợi, số lượng các gói tin bị mãn kỳ và được tái truyền, thời gian trì hoãn gói tin trung bình. Trong mọi tình huống, các số đo tăng đồng nghĩa với việc tăng tắc nghẽn.

Bước thứ hai trong chu trình phản hồi là chuyển thông tin về tắc nghẽn từ điểm được phát hiện bị tắc nghẽn đến điểm có trách nhiệm xử lý tình huống đó. Cách dễ nhất là để cho router phát hiện ra tắc nghẽn phát thông báo đến nút nguồn vừa gởi thông tin đến làm tắc hệ thống. Dĩ nhiên, thông báo này làm cho tắc nghẽn tăng thêm tạm thời.

Một cách thông báo tắc nghẽn khác là: Người ta dành riêng một bit hoặc một trường trong gói tin để trong trường hợp có tắc nghẽn, router có thể bật bit hoặc trường này lên và gởi nó đến mọi ngõ ra nhằm thông báo cho các láng giềng của nó biết.

Hoặc cũng có thể dùng cách phản hồi sau: Cho các host hoặc router thường xuyên gởi các gói tin thăm dò ra ngoài để hỏi thẳng về tình hình tắc nghẽn. Thông tin này có thể được sử dụng để chuyến hướng vạch đường vòng qua khu vực bị tắc nghẽn. Ví dụ thực tế: Một số đài phát thanh thường phái một số máy bay trực thăng bay vòng quanh thành phố để báo cáo lại những trục đường bị tắc, từ đó thông báo đến thính giả giúp họ chuyển hướng lái xe tránh những điểm nóng.

Sự hiện diện của tắc nghẽn đồng nghĩa với việc: tài nguyên của hệ thống không đủ để tải gánh nặng thông tin truyền qua. Vì thế ta nghĩ ra hai giải pháp: tăng tài nguyên hoặc giảm tải. Ví dụ, một mạng con có thể bắt đầu sử dụng các đường điện thoại quay số để tạm thời tăng băng thông giữa một số điểm nào đó. Trong các hệ thống vệ tinh, việc tăng công suất truyền đồng nghĩa với việc cung cấp băng thông lớn hơn. Chia tách lưu lượng thông tin cho chúng chạy trên nhiều đường đi khác nhau cũng có thể giúp tăng băng thông. Cuối cùng, các router dự phòng (thường để dự phòng tình huống các router chính bị sự cố) có thể được mang ra chạy trực tuyến để tăng dung lượng truyền tải của hệ thống khi tắc nghẽn nghiêm trọng xảy ra.

Tuy nhiên, đôi khi ta không thể tăng tài nguyên của hệ thống lên nữa, hoặc tài nguyên đã tăng tối đa. Cách thức duy nhất để chống lại tắc nghẽn là giảm tải. Có nhiều cách giảm tải, ví dụ: từ chối phục vụ một số người dùng, giảm cấp dịch vụ đối với vài hoặc tất cả người dùng, và buộc người dùng cung cấp lịch trình phát ra yêu cầu của họ.

Các biện pháp phòng ngừa tắc nghẽn

Tại tầng mạng, việc chọn sử dụng mạch ảo hay datagram sẽ tác động đến tắc nghẽn do nhiều giải thuật điều khiển tắc nghẽn chỉ chạy trên mạch ảo. Giải pháp “lập hàng đợi cho các gói tin và phục vụ chúng” liên quan đến việc một router có một hàng đợi cho mỗi ngõ vào, một hàng đợi cho mỗi ngõ ra hay cả hai. Nó cũng liên quan đến trình tự xử lý các gói tin trong hàng đợi ( round-robin hay dựa trên sự ưu tiên). Chính sách hủy bỏ gói tin sẽ chỉ ra gói tin nào cần bị hủy bỏ khi không còn không gian chứa. Một chính sách tốt có thể giúp làm giảm tắc nghẽn, ngược lại có thể làm tắc nghẽn trầm trọng thêm.

Một giải thuật vạch đường tốt có thể giúp tránh được tắc nghẽn bằng cách trải đều giao thông trên tất cả đường nối, trong khi một giải thuật tồi chỉ đơn giản gởi quá nhiều thông tin lên một đường tải đã quá tải rồi. Cuối cùng, việc quản lý thời gian sống của gói tin sẽ phải đưa ra quyết định là một gói tin có thể sống bao lâu trong hàng đợi trước khi bị hủy bỏ. Thời gian sống quá dài sẽ làm trì trệ công việc rất lâu. Nhưng nếu thời gian sống quá ngắn, các gói tin thỉnh thoảng sẽ bị mãn kỳ (timed-out) trước khi chúng đến được đích, vì thế dẫn đến việc tái truyền.

Điều khiển tắc nghẽn trong các mạng con dạng mạch ảo

Một giải pháp đơn giản là điều khiển cấp phép (admission control). Ý tưởng như sau: một khi có cảnh báo về tắc nghẽn, hệ thống sẽ không thiết lập thêm mạch ảo nào nữa đến khi sự cố qua đi. Vì thế, trong lúc tắc nghẽn xảy ra, những cố gắng thiết lập mạch ảo đều thất bại. Lý do: cho phép nhiều người vào đấy sẽ làm cho vấn đề trở nên trầm trọng hơn.

Cách tiếp cận khác là cho phép tạo ra các mạch ảo mới nhưng cẩn trọng vạch đường cho các mạch ảo mới này đi vòng qua khu vực bị vấn đề tắc nghẽn. Ví dụ, xem xét mạng con như trong hình H6.20, trong đó hai router bị tắc nghẽn.

(a) Một mạng con bị tắc nghẽn. (b) Mạng con được vẽ lại sau khi loại trừ các điểm gây tắc nghẽn (H6.20)

H6.20 (a) Một mạng con bị tắc nghẽn.

(b) Mạng con được vẽ lại sau khi loại trừ các điểm gây tắc nghẽn.

Giả sử một host được nối với router A muốn thiết lập nối kết tới một host của router B. Thường thì nối kết này sẽ chạy qua một trong hai nút bị tắc nghẽn. Để tránh chuyện này, chúng ta vẽ lại mạng con như trong hình (b), bỏ qua các router bị tắc nghẽn cùng với các đường nối của chúng. Đường chấm chỉ ra một đường đi có thể tránh được tắc nghẽn.

Một chiến lược khác liên quan đến mạch ảo là: host và mạng con thỏa thuận với nhau về việc thiết lập mạch ảo. Thỏa thuận này thường bao gồm dung lượng và đường đi của thông tin, chất lượng dịch vụ được yêu cầu và các thông số khác. Để đảm bảo thực hiện được thỏa thuận, mạng con sẽ dành riêng tài nguyên trên suốt con đường mạch ảo đi qua. Các tài nguyên này bao gồm không gian bảng vạch đường và buffer trên các router, cùng với băng thông trên các đường nối. Trong tình huống này, tắc nghẽn hầu như không xảy ra trên một mạch ảo mới bởi vì tất cả tài nguyên cần thiết đã được đảm bảo sẵn dùng.

Kiểu dành riêng tài nguyên này có thể được thực hiện toàn thời gian như là một phương thức hoạt động chuẩn, hoặc chỉ được thực hiện khi tắc nghẽn xảy ra. Nếu được thực hiện toàn thời gian sẽ có hạn chế là lãng phí tài nguyên. Nếu đường truyền 6 Mbps được tận hiến cho 6 mạch ảo, mỗi mạch ảo tiêu tốn 1 Mbps, thì đường truyền này luôn được đánh dấu là đầy, cho dù hiếm có khi nào 6 mạch ảo con của nó truyền hết công suất tại cùng thời điểm.

Điều khiển tắc nghẽn trong mạng con dạng Datagram

Trong mạng dạng Datagram, mỗi router có thể dễ dàng kiểm soát hiệu năng của các đường ra và các tài nguyên khác. Ví dụ, nó có thể gán cho mỗi đường nối một biến thực u, với giá trị từ 0.0 đến 1.0, dùng phản ánh hiệu năng gần đây của đường nối đó. Để duy trì độ chính xác tốt cho u, một mẫu hiệu năng tức thời f của đường nối sẽ được lấy thường xuyên, và u sẽ được cập nhật như sau

trong đó hằng số a quyết định router quên đi lịch sử gần đây nhanh như thế nào.

Khi u vượt qua ngưỡng, đường ra rơi vào trạng thái “cảnh báo”. Mỗi gói tin mới tới sẽ được giữ lại và chờ kiểm tra xem đường ra có ở trạng thái cảnh báo không. Nếu có, một số hành động sẽ được thực hiện, và chúng ta sẽ thảo luận ngay sau đây.