Điều khiển tắc nghẽn trong NGN

Chia sẻ: Khinh Kha Kha | Ngày: | Loại File: PDF | Số trang:16

0
143
lượt xem
67
download

Điều khiển tắc nghẽn trong NGN

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

ĐIỀU KHIỂN TẮC NGHẼN TRONG NGN 2.1 Giới thiệu chương Nhu cầu về các dịch vụ mạng ngày càng đa dạng, phong phú và đòi hỏi nhiều mức độ chất lượng dịch vụ khác nhau. Xu hướng phát triển là tiến tới hội tụ về mạng và hội tụ về dịch vụ. Tài nguyên của mạng có giới hạn trong khi nhu cầu truyền thông tin ngày càng tăng, chính vì vậy mà hiện tượng tắc nghẽn mạng là khó tránh khỏi. Chương 2 trình bày về vấn đề tắc nghẽn, nguyên nhân phân loại cũng như các tiêu chí đánh...

Chủ đề:
Lưu

Nội dung Text: Điều khiển tắc nghẽn trong NGN

  1. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Chương 2 ĐIỀU KHIỂN TẮC NGHẼN TRONG NGN 2.1 Giới thiệu chương Nhu cầu về các dịch vụ mạng ngày càng đa dạng, phong phú và đòi hỏi nhiều mức độ chất lượng dịch vụ khác nhau. Xu hướng phát triển là tiến tới hội tụ về mạng và hội tụ về dịch vụ. Tài nguyên của mạng có giới hạn trong khi nhu cầu truyền thông tin ngày càng tăng, chính vì vậy mà hiện tượng tắc nghẽn mạng là khó tránh khỏi. Chương 2 trình bày về vấn đề tắc nghẽn, nguyên nhân phân loại cũng như các tiêu chí đánh giá phương pháp điều khiển tắc nghẽn. Ngoài ra, thuật toán tăng giảm tuyến tính cũng được đề cập trong chương này. 2.2 Vấn đề tắc nghẽn trong NGN Tắc nghẽn là một hiện tượng rất quen thuộc trên mạng, mà nguyên nhân nói chung là do tài nguyên mạng giới hạn trong khi nhu cầu truyền thông tin của con người là không có giới hạn. Hình 2.1 trình bày hiện tượng tắc nghẽn trên mạng và hình 2.2 trình bày hiệu quả của việc có điều khiển. Thông thường, nút mạng được thiết kế với một bộ đệm lưu trữ có hạn. Nếu tình trạng nghẽn mạng kéo đủ dài, bộ đệm bị tràn, các gói sẽ bị mất hoặc trễ quá thời gian cho phép. Nếu một gói bị mất trên mạng thì tại thời điểm ấy các tài nguyên mạng mà gói đó đã sử dụng cũng bị mất theo. 18
  2. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Xảy ra tắc nghẽn 3 6 1 8 4 2 7 5 Hình 2.1 Hiện tượng xảy ra tắc nghẽn Hình 2.2 Hiệu quả của việc điều khiển tắc nghẽn [7] Hình 2.3 minh họa môi trường mạng hỗn tạp trong NGN. Các mạng riêng lẻ được kết nối với nhau thông qua các bộ định tuyến hay các cổng (MG), tại đây các gói tin đến sẽ được lưu giữ (store) trong bộ đệm và chuyển tiếp (forward) theo một trong các đường kết nối đầu ra. Tốc độ của các gói tin đầu ra bị giới hạn bởi băng thông (bandwidth) của các đường kết nối, thường nhỏ hơn băng thông của các đường đến do phải phân chia cho nhiều luồng. 19
  3. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Máy Mạng chủ truyền hình MG MG Mạng lõi MG MG Mạng di Mạng cố Mạng động định dữ liệu Hình 2.3 Môi trường mạng hỗn tạp trong NGN 2.2.1 Nguyên nhân xảy ra tắc nghẽn Nguyên nhân xảy ra tắc nghẽn trong môi trường mạng mới đó là: 1. Tràn bộ đệm: thường nút mạng được thiết kế với 1 bộ đệm lưu trữ có hạn. Nếu tình trạng nghẽn mạng kéo đủ dài, bộ đệm bị tràn, các gói sẽ bị mất hoặc trễ quá thời gian cho phép. Đây cũng là nguyên nhân giống như trong mạng truyền thống. 2. Lỗi do đường truyền vô tuyến 3. Do nghẽn cổ chai: tại điểm đấu nối từ các mạng tốc độ thấp vào các mạng tốc độ cao. 4. Nhu cầu băng thông cao của các dịch vụ đa phương tiện và các loại hình dịch vụ mới 5. Lưu lượng lớn, thay đổi đột biến và biến đổi động 6. Tính biến động của mạng, topo mạng: Đây là một đặc tính mới của mạng NGN so với mạng truyền thống. Các nút mạng có thể dịch chuyển làm topo mạng thay đổi gây ra những biến đổi về phân chia lưu lượng trên mạng. 2.2.2 Nguyên lý chung điều khiển chống tắc nghẽn 20
  4. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Điểm gãy Điểm vách (knee) (cliff) Thông lượng (Throughput) Lưu lượng đầu vào (offered load) Hình 2.4 Quá trình diễn ra tắc nghẽn [7] Quá tải làm thông lượng (throughput) suy biến như được chỉ ra trên hình 2.4. Đồ thị biểu diễn mối quan hệ giữa thông lượng với lưu lượng đưa vào (offered load). Ở mức lưu lượng đưa vào nhỏ (phía trái của điểm gãy - Knee), thông lượng tăng tuyến tính với lưu lượng đưa vào. Đó là lúc băng thông chưa sử dụng hết. Thông lượng lớn nhất khi lưu lượng đưa vào gần với băng thông thắt cổ chai (bottleneck bandwidth) và thông lượng tăng chậm tương ứng với kích thước dữ liệu trong bộ đệm. Khi lưu lượng đưa vào tiếp tục tăng, thông lượng giảm đột ngột từ điểm vách (Cliff) xuống một giá trị rất nhỏ, đó là lúc tất cả các luồng cùng gửi dữ liệu nhưng dữ liệu không được truyền đến phía nhận. Lúc đó, hầu hết các gói bị mất và hiện tượng tắc nghẽn xảy ra . Nguyên lý chung để điều khiển chống tắc nghẽn là: - Duy trì điểm hoạt động của mạng luôn ở mức lưu lượng đưa vào nhỏ. - Đảm bảo cho các bộ đệm của bộ định tuyến không bị tràn. - Đảm bảo phía gởi dữ liệu nhanh mà phía nhận vẫn có thể xử lý, giúp sử dụng tài nguyên một cách hiệu quả nhất. 21
  5. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn 2.3 Các phương pháp điều khiển chống tắc nghẽn 2.3.1 Các đặc điểm chung Các phương pháp điều khiển chống tắc nghẽn có thể được phân loại dựa trên các đặc điểm chung như sau: • Điều khiển tiếp nhận (Admission control): cho phép một kết nối mới chỉ khi mạng có thể đáp ứng một cách thích hợp. Trong pha thiết lập kết nối có chứa một tập các mô tả về lưu lượng (tốc độ truyền dẫn cực đại, tốc độ truyền dẫn trung bình, trễ cực đại cho phép…). Mạng chỉ cho phép người sử dụng truy nhập đến chỉ khi nào có đủ tài nguyên sẵn sàng trên mạng. Ngược lại, yêu cầu kết nối bị từ chối. Mạng giám sát, kiểm soát các luồng lưu lượng để xem liệu người dùng có tuân theo các mô tả về lưu lượng không. • Kiểm soát (Policing): Kiểm tra kết nối nào vi phạm các mô tả về lưu lượng để đưa ra xử lý trừng phạt bằng cách: 1) Xóa các gói vi phạm mô tả 2) Gán cho chúng quyền ưu tiên thấp hơn • Điều khiển luồng lưu lượng (Flow control) là những hoạt động của mạng để tránh xảy ra tắc nghẽn. Ngoài ra điều khiển lưu lượng còn nhằm sử dụng tối ưu tài nguyên mạng để đạt được một hiệu suất mạng thực sự. 2.3.2 Phân loại Theo các đặc điểm chung nêu trên, các phương pháp điều khiển tắc nghẽn có thể được phân loại như sau: Điều khiển tắc nghẽn vòng hở (Open-loop congestion control) là sự kết hợp của điều khiển tiếp nhận, kiểm soát và nguyên lý thùng rò (leaky bucket). Trong đó không có thông tin phản hồi từ mạng hoặc phía nhận. Điều khiển chống tắc nghẽn vòng kín (Close-loop congestion control) là dựa trên trạng thái của mạng với sự giám sát tắc nghẽn và điều khiển lưu lượng dựa trên thông tin phản hồi. Trong đó, thông tin phản hồi có thể là: 22
  6. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn • Phản hồi Nn (implicit feedback) nguồn phát sử dụng thời gian chờ (time-out) để xác định liệu có xảy ra tắc nghẽn hay không. Ví dụ: điều khiển chống tắc nghẽn trong TCP thực hiện theo kiểu này. • Phản hồi rõ (explixit feedback) một số bản tin tường minh được gửi đến nguồn phát. Điều khiển theo tốc độ: điều khiển một cách trực tiếp tốc độ truyền tại phía gửi (nguồn gửi tin). Điều khiển theo kích thước cửa sổ: điều khiển gián tiếp tốc độ truyền thông qua việc thay đổi kích thước cửa sổ (số gói tin hoặc số byte tồn tại ở đó). 2.4 Các tiêu chí đánh giá phương pháp điều khiển chống tắc nghẽn Trong phần này đề xuất một số tiêu chí đánh giá cơ bản nhất dựa trên cơ sở những tiêu chí truyền thống [7], song có xem xét đến những đặc tính của môi trường mạng mới N GN . N hững tiêu chí cơ bản nhất dùng cho phân tích, đánh giá các phương pháp điều khiển chống tắc nghẽn bao gồm: 2.4.1 Tính hiệu quả (Efficient) Tính hiệu quả được định nghĩa là tỉ số giữa tổng tài nguyên phân phối cho các ứng dụng và tổng tài nguyên mong muốn tại điểm Knee của mạng, nghĩa là trước thời điểm mạng xảy ra bão hòa. N ếu Xgoal biểu thị mức lưu lượng đưa vào mong muốn tại điểm Knee, X(t) biểu thị tổng tài nguyên phân phối cho các ứng dụng, nghĩa là X (t ) = ∑ xi (t ) , thì tính hiệu quả được xác định bởi tỉ số: X (t ) η= (2.1) X goal Quá tải (X (t ) > X goal ) hay dưới mức tải (X (t ) < X goal ) đều không mong muốn và được coi là không có hiệu quả như nhau. Thuật toán hiệu quả khi η tiến gần tới 1, nghĩa là X(t) tiến gần tới Xgoal. 23
  7. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Chú ý, tính hiệu quả chỉ có liên quan đến tổng lượng phân phối và do đó 2 lượng phân phối khác nhau có thể cả hai đều hiệu quả miễn là tổng lượng phân phối là gần đến “goal”. Sự phân bố của tổng lượng phân phối giữa các người dùng được đo bởi chỉ tiêu bình đẳng. 2.4.2 Tính bình đẳng (Fairness) Khi nhiều người dùng chia sẻ tài nguyên, tất cả người dùng trong cùng một lớp dịch vụ phải có chia sẻ như nhau về tài nguyên. Thường thì sự phân bổ không bằng nhau một cách chính xác, mức độ bình đẳng được đo bởi chỉ số bình đẳng. Chỉ số bình đẳng được định nghĩa khái quát trong [7] như sau: (∑ x ) 2 F ( x) = (2.2) i n(∑ x ) 2 i Chỉ số này có các đặc tính sau đây: • 0 ≤ F ( x ) ≤ 1 . Lượng phân phối bình đẳng (với tất cả lượng xi bằng nhau) có tính bình đẳng là 1 và lượng phân phối không bình đẳng (với tất cả các tài nguyên chỉ dùng cho một người) có tính bình đẳng là 1/n đạt đến 0 khi n tiến tới vô cùng. • Tính bình đẳng độc lập vào thang đo, tức là, đơn vị đo là không quan trọng. • Tính bình đẳng là hàm liên tục. Một vài sự thay đổi nhỏ trong lượng phân bố cũng thấy trong tính bình đẳng. • N ếu chỉ có k trong n người dùng chia sẻ tài nguyên như nhau với (n - k) người dùng không nhận tài nguyên nào, thì tính bình đẳng là k/n. Ta có các đặc tính khác trong [13] Thuật toán bình đẳng khi F tiến gần tới 1. Tuy nhiên, chỉ số này chỉ biểu diễn tính bình đẳng giữa các người dùng mạng nói chung mà chưa thể hiện được bản chất đa dịch vụ trong mạng thế hệ mới. Trong mạng N GN sẽ có nhiều lớp dịch vụ khác nhau, sử dụng nhiều hệ giao thức vận chuyển khác nhau. Vì vậy, cần thiết phải đưa thêm hai chỉ số bình đẳng mới [2]: − Chỉ số bình đẳng giữa các giao thức cùng họ: F1 = θ i / θ j (2.3) 24
  8. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn trong đó θi và θj là thông lượng của các giao thức i và j cùng sử dụng cho một lớp ứng dụng. − Chỉ số bình đẳng giữa các giao thức khác họ: F2 = θi (2.4) ωj trong đó θi và ωj là thông lượng của các giao thức i và j khác họ sử dụng cho các lớp ứng dụng khác nhau. 2.4.3 Tính hội tụ (Convergence) Sự hội tụ được đánh giá bởi thời gian cần để hệ thống đạt đến trạng thái mong muốn từ một trạng thái xuất phát bất kỳ. Một cách lý tưởng, hệ thống đạt tới trạng thái đích nhanh và có biên độ dao động rất nhỏ xung quanh nó. N hư vậy, tính hội tụ được đánh giá qua 3 yếu tố: • Trạng thái cân bằng tiệm cận với Xgoal . • Thời gian cần thiết để thuật toán hội tụ đến Xgoal . • Biên độ của dao động xung quanh giá trị Xgoal nhỏ dần. Thời gian để đạt được trạng thái cân bằng (equilibrium) xác định độ nhạy (responsiveness) và độ dao động xác định độ mịn (smoothness) của phương pháp điều khiển. Một cách lý tưởng, chúng ta muốn thời gian cũng như sự dao động phải nhỏ. Do đó, điều khiển với thời gian nhỏ và biên độ nhỏ của dao động gọi là nhạy hơn và mịn hơn, như trong hình 2.5. 2.4.4 Thời gian đáp ứng nhanh (Small response time) Thuật toán phải nhanh chóng phát hiện được tắc nghẽn và thời gian kể từ khi phát hiện tắc nghẽn đến khi có tác động của điều khiển chống tắc nghẽn phải càng nhanh càng tốt: Tresp ≤ Tgoal - trong đó Tgoal là cơ sở để so sánh các thuật toán điều khiển. 25
  9. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Độ nhạy “Goal” Độ mịn Tổng lưu lượng mạng Thời gian Hình 2.5 Độ nhạy (responsiveness) và độ mịn (smoothness). 2.4.5 Độ mịn trong điều khiển (Smoothness) Trong thực tế, tác động của điều khiển không thể đưa hệ thống đến trạng thái mong muốn ngay lập tức. Vì vậy, các thuật toán điều khiển chống tắc nghẽn phải thiết kế sao cho tác động điều khiển có độ mịn cần thiết, tránh đưa hệ thống vào trạng thái mất ổn định thêm. Đại lượng để đo độ mịn có thể là hiệu số giữa lưu lượng tại 2 thời điểm điều khiển liên tiếp t1 và t2: xi (t 2) − xi (t1 ) hoặc hiệu số giữa tổng lưu lượng mạng tại 2 thời điểm điều khiển liên tiếp t1 và t2: X (t 2 ) − X (t1 ) . 2.4.6 Tính phân tán (Distributedness) Đây là điều cần thiết bởi vì một mô hình tập trung đòi hỏi thông tin đầy đủ về trạng thái của mạng cũng như các luồng riêng lẻ, và điều này là không thể không có đối với mạng cỡ lớn. Chẳng hạn, chúng ta muốn biết về các nhu cầu cá nhân hay toàn bộ. Thông tin này có thể hữu dụng tại nguồn tài nguyên. Tuy nhiên, truyền đạt thông tin này cho nhiều người dùng làm chúng ta quan tâm đến mào đầu (overhead), đặc biệt khi một người dùng có thể dùng vài nguồn tài nguyên (resource) tại cùng một thời điểm. Do đó, chúng ta phải quan tâm hàng đầu đến phương pháp điều khiển có thể thực hiện trong hệ thống thực và giả sử rằng hệ 26
  10. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn thống có lượng phản hồi ít nhất. N ó chỉ cho ta biết nơi nào là không đủ tải hay quá tải thông qua bit phản hồi nhị phân. Thông tin khác như Xgoal và số lượng người dùng cùng chia sẻ nguồn tài nguyên được giả thiết là không được biết bởi người dùng. Điều này hạn chế phương pháp khả thi. N hư vậy, mô hình có thể xây dựng để đánh giá các phương pháp điều khiển chống tắc nghẽn cho mạng N GN có thể được thiết kế dựa trên sáu tiêu chí cơ bản nêu trên. 2.5 Thuật toán tăng giảm 2.5.1 Thuật toán tăng giảm Trong hình 2.6 mô tả mạng với n người dùng nó. Tình trạng tắc nghẽn của hệ thống được xác định bởi số gói trong hệ thống. Thời gian được chia thành các khe rời rạc. N hững khe đó đặc trưng căn bản cho các khoảng bắt đầu khi người dùng thiết lập mức tải dựa vào phản hồi mạng nhận trong các khoảng trước. N ếu trong suốt khe thời gian t, người dùng thứ i là xi (t ) , sau đó tải tổng cộng tại tài nguyên thắt cổ chai là ∑ x (t ) , và trạng thái của hệ thống biểu thị bởi vector có độ dài n i x(t ) = {x1 (t ), x 2 (t ),..., x n (t )} . Khi chúng ta đang hoạt động tại hay gần điểm Knee, mọi tài nguyên yêu cầu bởi người dùng được chấp nhận (điều này không đúng tại điểm cliff). Do đó, xi(t) biểu thị người dùng thứ i. 27
  11. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn N gười dùng 1 x1 N gười ∑ ∑x i > X goal ? dùng 2 xn N gười dùng n y Hình 2.6 Hệ thống gồm n người dùng chia sẻ một mạng Trong suốt khoảng thời gian, hệ thống xác định mức tải của nó và gởi phản hồi nhị phân y(t),với N ếu y (t ) = 0 ⇒ tăng tải N ếu y (t ) = 1 ⇒ giảm tải N hững người dùng cùng hoạt động trong hệ thống và thay đổi (tăng hay giảm) yêu cầu bởi một lượng u i (t ) . Do đó, xi (t + 1) = xi (t ) + u i (t ) (2.5) Sự thay đổi của u i (t ) mô tả sự điều khiển của người dùng thứ i. N ó là hàm theo yêu cầu trước đó của người dùng và phản hồi hệ thống: u i (t ) = f (xi (t ), y (t ) ) (2.6) Do đó, ta có: xi (t + 1) = xi (t ) + f i ( xi (t ), y (t ) ) Chú ý rằng người dùng không biết được yêu cầu của người khác, và do đó, u i (t ) không thể là hàm của x j (t ), j ≠ i . Thông thường, hàm điều khiển f có thể là tuyến tính hay không tuyến tính. Tuy nhiên, trước hết chúng ta sẽ tập trung đến điều khiển tuyến tính. Hàm trạng thái (2.1) trở thành ⎧aI + bI xi (t ) nếu y (t ) = 0 ⇒ Tăng xi (t + 1) = ⎨ ⎩aD + bD xi (t ) nếu y (t ) = 1 ⇒ Giảm 28
  12. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Ở đây, aI, bI, aD, bD là hằng số. Dưới đây là 4 trường hợp của hàm điều khiển: • Tăng nhân/giảm nhân (MIMD- Multiplicative Increase/Multiplicative Decrease) ⎧bI xi (t ) nếu y (t ) = 0 ⇒ Tăng (2.7) xi (t + 1) = ⎨ ⎩bD xi (t ) nếu y (t ) = 1 ⇒ Giảm Với bI > 1 và 0 < bD < 1 . Mọi người dùng tăng nhu cầu bằng cách nhân yêu cầu trước đó với hệ số hằng (constant factor). Giảm cũng bằng cách nhân. • Tăng cộng/giảm cộng (AIAD- Additive Increase/ Additive Decrease) ⎧a I + xi (t ) nếu y (t ) = 0 ⇒ Tăng (2.8) xi (t + 1) = ⎨ ⎩a D + xi (t ) nếu y (t ) = 1 ⇒ Giảm Ở đây, a I > 0 và a D < 0 . Tất cả người dùng tăng nhu cầu bằng cách cộng lượng hằng với nhu cầu trước đó. Giảm cũng bằng phép cộng. • Tăng cộng/giảm nhân (AIMD- Additive Increase/Multiplicative Decrease) ⎧a I + xi (t ) nếu y (t ) = 0 ⇒ Tăng xi (t + 1) = ⎨ ⎩bD xi (t ) nếu y (t ) = 1 ⇒ giảm (2.9) Tăng bằng cách cộng với lượng không đổi nhưng giảm bằng nhân hệ số hằng • Tăng nhân/giảm cộng (MIAD- Multiplicative Increase/Addative Decrease). ⎧bI xi (t ) nếu y (t ) = 0 ⇒ Tăng xi (t + 1) = ⎨ ⎩a D + xi (t ) nếu y (t ) = 1 ⇒ giảm (2.10) Để đánh giá hiệu quả của những phương pháp điều khiển, chúng ta đề cập trong phần tiếp theo. 2.5.2 Biểu diễn thuật toán bằng vector Khi xác định phương pháp điều khiển khả thi, chúng ta nên xem sự chuyển đổi trạng thái hệ thống như quỹ đạo trong không gian vector n chiều. Chúng ta xét phương pháp này trong trường hợp 2 người dùng, có thể xem như không gian 2 chiều. 29
  13. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Phân (1) bố x2 của (2) người dùng 2 (5) X0 (3) (6) (4) Phân bố x1 của người dùng 1 Hình 2.7 Vector biểu diễn cho 2 người dùng. Trong đó: (1) Đường đồng đẳng (Equi-Fairness Line) (2) Đường bình đẳng (Fairness Line) (3) Điểm tối ưu (Optimal point) (4) Đường hiệu quả (Efficiency Line) (5) Quá tải (Overload) (6) Không đủ tải (underload) N hư hình 2.7, tài nguyên phân bố của 2 người dùng bất kỳ {x1 (t ), x 2 (t )} có thể biểu diễn như điểm {x1, x2 } trong không gian 2 chiều. Trong hình này, trục ngang mô tả phân phối (allocation) cho người dùng 1, và trục đứng mô tả phân phối cho người dùng 2. Tất cả sự phân phối với x1+x2=Xgoal là phân phối có hiệu quả. N ó tương ứng với đường thẳng là “đường hiệu quả” (efficiency line). Tất cả phân phối mà x1= x2 là phân bố bình đẳng. N ó tương ứng với đường thẳng được gọi là “đường bình đẳng” (fairness line). Hai đường này cắt nhau tại điểm (Xgoal/2, Xgoal/2) là điểm tối ưu. Mục tiêu (goal) của phương pháp điều khiển là làm cho hệ thống đến hoạt động tại điểm này mà không quan tâm đến vị trí bắt đầu. Tất cả các điểm bên dưới đường hiệu quả mô tả hệ thống “không đủ tải”(underload) và một cách lý tưởng hệ 30
  14. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn thống sẽ yêu cầu người dùng tăng tải. Theo quan sát, chẳng hạn, điểm x0=(x10, x20). N guyên tắc tăng cộng tăng phân phối của cả 2 người dùng bởi a1 tương ứng với việc dịch chuyển dọc đường tạo với trục ngang góc 45 0 . N guyên tắc tăng nhân tăng phân phối cho cả 2 người dùng bằng hệ số b1 tương ứng với việc dịch theo đường nối điểm đó với gốc toạ độ. Tương tự, tất cả các điểm trên đường hiệu quả mô tả hệ thống quá tải (overload) và giảm cộng mô tả bởi đường tạo với trục ngang góc 45 0 , khi giảm nhân được mô tả bởi đường nối điểm đó với gốc. Tính bình đẳng tại điểm bất kỳ (x1, x2) được cho bởi: (x1 + x 2 )2 F= ( 2 x12 + x 2 2 ) Chú ý rằng nhân cả hai phân bố với hệ số b không thay đổi tính bình đẳng. Đó là, (bx1,bx2) có cùng tính bình đẳng với (x1, x2) cho tất cả các giá trị của b. Do đó, tất cả các điểm trên đường nối điểm đó với gốc có cùng tính bình đẳng. Chúng ta, gọi đường đi qua gốc là đường “đồng đẳng” (equi-fairness). Tính bình đẳng giảm khi độ dốc của đường này hoặc tăng lên trên hoặc giảm xuống dưới đường bình đẳng. Hình 2.8 cho ta thấy quỹ đạo của hệ thống 2 người dùng bắt đầu từ điểm x0 dùng nguyên tắc điều khiển tăng cộng/giảm nhân. Điểm x0 nằm dưới đường hiệu quả và do đó cả hai người dùng đều được yêu cầu tăng. Chúng di chuyển dọc đường tạo với trục ngang góc 45 0 . N ó di chuyển đến x1 nằm trên đường hiệu quả. N gười dùng được yêu cầu giảm và thực hiện phép nhân, tương ứng với việc chuyển động đến điểm gốc trên đường nối x1 và gốc. N ó di chuyển đến điểm x2, nằm dưới đường hiệu quả và lập lại theo chu kỳ. Chú ý rằng x2 có tính bình đẳng cao hơn x0. Do đó, với mỗi chu kỳ, tính bình đẳng tăng chậm, và cuối cùng, hệ thống hội tụ đến trạng thái tối ưu, dao động quanh điểm “goal”. Quỹ đạo tương tự có thể vẽ cho nguyên tắc điều khiển khác. Mặc dù không phải tất cả các nguyên tắc điều khiển đều hội tụ. Chằng hạn, hình 2.9 cho ta thấy quỹ đạo của nguyên tắc điều khiển tăng cộng/giảm cộng AIAD bắt đầu từ vị trí x0. Hệ thống giữ chuyển động lùi và đến dọc theo đường qua điểm x0, tạo với trục 31
  15. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn ngang góc 45 0 . Với nguyên lý như thế, hệ thống có thể hội tụ đến hiệu quả, nhưng nó không bình đẳng. Phân Đường bình đẳng bố x2 của người dùng 2 Đường hiệu quả Phân bố x1 của người dùng 1 Hình 2.8 AIMD hội tụ đến điểm tối ưu Điểm làm việc dao động dọc đường này Phân Đường bình đẳng bố x2 của người dùng thứ 2 Đường hiệu quả Phân bố x1 của người dùng 1 Hình 2.9 AIAD không hội tụ 32
  16. Chương 2: Điều khiển tắc nghẽn trong NGN www.4tech.com.vn Điều kiện để hội tụ đến hiệu quả và bình đẳng được đưa ra theo phương pháp đại số trong [7]. 2.6 Kết luận chương Hiện tượng tắc nghẽn xảy ra trong mạng là vấn đề khó tránh khỏi, do đó điều khiển tắc nghẽn ngày càng trở nên cấp thiết. Chương 2 đã nêu tổng quan về nguyên lý, phân loại các phương pháp điều khiển tắc nghẽn, tiêu chí đánh giá những phương pháp điều khiển. N goài ra, thuật toán tăng giảm (ở đây chỉ nói đến tăng giảm tuyến tính) cũng đã đề cập đến. Từ đó, ta thấy rằng AIMD được sử dụng nhiều hơn các thuật toán khác do nó đảm bảo hội tụ đến tính hiệu quả và bình đẳng. Phần tiếp theo sẽ đi sâu vào các phương pháp điều khiển tắc nghẽn. 33

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản