Luận văn Điều khiển tắc nghẽn trên mạng ngang hàng có cấu trúc

nằm sau nó trong vòng Chord. Nếu một nút đột ngột không liên lạc được với successor thì nó sẽ sử dụng các nút liền sau trong danh sách. Tiếp nữa các khóa (các item liên quan tới khóa) sẽ được sao chép trên các nút có trong danh sách đó. Do đó một khóa (item liên quan đến khóa) sẽ chỉ bị mất khi có log2(N)+1 các nút trong danh sách phải đồng thời rời khỏi mạng. 16 Chương 2. Vấn đề điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc 2.1. Tắc nghẽn và tầm quan trọng của việc điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc Mạng ngang hàng có cấu trúc được xây dựng với mục đích đáp ứng được nhu cầu mở rộng về số lượng node, khóa cũng như khả năng đáp ứng của toàn mạng. Đối với một hệ thống chia sẻ file đơn giản khi mỗi node chỉ phải đáp ứng số lượng nhỏ query và chỉ phải index một số giới hạn các tập tin, hệ thống có thể hoạt động tốt với thiết kế ban đầu. Tuy nhiên trong thời gian gần đây, mạng ngang hàng có cấu trúc được phát triển để có thể phục vụ cho các ứng dụng có độ phức tạp cao, ví dụ như hệ thống truy vấn thông tin (P2P Information Retrieval – P2P-IR) [8] hay hệ thống quản trị cơ sở dữ liệu (P2P Database Management Systems - P2P-DBMS) [2]. Các ứng dụng ở lớp trên này tạo lượng truy vấn lớn hơn rất nhiều, ví dụ: với một hệ thống chia sẻ file đơn giản các nút chỉ phải đánh index và tạo một số lượng khóa nhỏ lấy từ tên của các file, với một hệ thống truy vấn sử dụng kĩ thuật tìm kiếm full-text số lượng khóa phải index và đưa vào mạng là vài nghìn với một văn bản. Trong DHT, cụ thể ở đây là mạng Chord một nút đảm nhận hai chức năng chính là trả lời truy vấn và chuyển tiếp truy vấn đến nút khác, do đó khi một nút có vấn đề cũng có thể gây ảnh hưởng tới nhiều nút khác trong mạng. Thông thường các nút trong mạng có cấu hình phần cứng và băng thông mạng rất đa dạng, do đó khả năng đáp ứng truy vấn của từng nút cũng hoàn toàn khác nhau. Ngoài ra với mạng ngang hàng thường xảy ra tình trạng một số lượng tài nguyên được truy vấn với tần suất cao, chỉ trong một khoảng thời gian nhất định. Những đặc điểm trên khiến cho mạng ngang hàng có cấu trúc dễ xảy ra tình trạng tắc nghẽn và có thể gây ảnh hưởng rộng trên toàn mạng. Tắc nghẽn trong DHT thường bắt đầu khi một nút nhận được số truy vấn vượt quá khả năng xử lý của nó, nếu không có cơ chế thích hợp các truy vấn sau đến hoặc đi qua nút đó sẽ tạo ra tắc nghẽn trên mạng, có thể gây sụp đổ toàn mạng. Việc điều khiển tắc nghẽn giúp một hệ thống DHT có khả năng xử lý lượng lớn truy vấn nhằm đáp ứng cho các ứng dụng phức tạp ở lớp trên. Việc xử lý tắc nghẽn trên DHT nằm ở tầng trên và độc lập với các cơ chế điều khiển tắc nghẽn ở các tầng bên dưới, như TCP. 17 2.2. Phân tích quá trình sụp đổ do tắc nghẽn trong mạng ngang hàng có cấu trúc [8] Trong mục này chúng ta sẽ phân tích quá trình sụp đổ của một mạng DHT khi có tắc nghẽn xảy ra và không có cơ chế điều khiển tắc nghẽn nào được sử dụng. Nhằm đơn giản hóa, ta xét mạng DHT trong trường hợp đặc biệt khi các nút có cùng khả năng đáp ứng truy vấn. Giả sử các nút tham gia vào mạng thực hiện các truy vấn với tốc độ chỉ phụ thuộc vào khả năng của từng nút (ví dụ như tốc độ của bộ vi xử lý hay đường truyền của nút đó). Các truy vấn đến từ các nút khác nhau sẽ phải “cạnh tranh” tài nguyên trên nút đích. Nếu như lượng truy vấn đến vượt quá khả năng xử lý của một nút thì nút đó sẽ phải loại bỏ một số truy vấn. 2.2.1. Khái quát Mục đích của việc phân tích này là nghiên cứu về thông lượng đạt được – A trong mạng DHT khi mỗi nút tạo ra lượng truy vấn với tốc độ x. Mỗi truy vấn có xác suất được thực hiện thành công là p. p=1 nếu như nút không bị quá tải, ngược lại 0<p<1. Một nút được xác định tắc nghẽn hay không dựa vào lượng truy vấn tới và tài nguyên trên máy (có thể là tốc độ vi xử lý hoặc băng thông). Do đó ta phải tính toán tổng tải O mà tài nguyên thấp nhất (bottleneck) trên nút phải xử lý và so sánh với khả năng của nút đã được cho trước: c, qua đó ta có thể tính p và thông lượng đạt được A là một hàm của x. p là đại lượng không thứ nguyên, còn x,O và A có đơn vị là số truy vấn/giây. 2.2.2. Định nghĩa Thông lượng đến: Mỗi nút khởi tạo các truy vấn, được chuyển qua các nút trong mạng. Để tính tổng tải đến O trước hết ta định nghĩa thông lượng đến od h là thông lượng đến với đích là d trước khi qua h nút. Như đã giả thiết ở trên, các nut có cùng khả năng đáp ứng truy vấn, và các nút cùng khởi tạo một số lượng truy vấn. Do đó, thông lượng đến độc lập với nguồn sinh truy vấn. Để đơn giản ta xét một mạng Chord nhỏ, tuy nhiên kết quả sẽ vẫn đúng cho bất kì mạng DHT log n nào. 18 Hình 10: (a) tải đến các nút tạo bởi P0, (b) Tải tới và rời khỏi nút Hình 10a thể hiện thông lượng đến các nút khác được sinh bởi nút P0. Mỗi nút có log2n = l (ở đây n=8 và l=3) mục trong bảng định tuyến, mỗi mục trỏ đến một nút với khoảng cách 2i với i=0…(l-1). Mỗi nút thực hiện việc định tuyến bằng cách gửi truy vấn đến nút gần khóa được tìm kiếm nhất. P0 tạo các truy vấn đến 7 nút còn lại trong mạng. Một trong số truy vấn được chuyển qua nút khác.Ví dụ o7 1 là thông lượng đến tại P0 với đích đến là P7 trước khi đi qua nút đầu tiên (P0 – P4). Thông lượng đạt được: Mỗi nút có khả năng đáp ứng c để xử lý thông lượng đến. c phụ thuộc vào tốc độ vi xử lý và đường truyền của nút. Nếu như tổng thông lượng đến không vượt quá khả năng xử lý của nút, tất cả truy vấn đều được xử lý. Ngược lại sẽ có một số truy vấn bị hủy. Ta định nghĩa thông lượng đạt được như sau: ad h là thông lượng đạt được với đích là d sau khi qua h nút. Ví dụ: a7 1 ≤ o7 1 là thông lượng với đích là nút 7 sau khi qua nút đầu tiên, ứng với thông lượng tới nút 4. Xác suất xử lý: thông lượng đã xử lý được định nghĩa bởi công thức: p= min (1, c/O) (1) ở đó c là khả năng xử lý của nút và O là tổng tải đến. Khi một nút không quá tải O≤c tất cả thông lượng tới đều được xử lý, khi đó p=1, ngược lại p <1. Giả sử nếu thông lượng đến lớn gấp 2 lần khả năng xử lý của nút thì khi đó xác suất xử lý là 0.5. 19 Nếu truy vấn đến nút đích đi qua một số các nút, tại các nút tiếp theo thông lượng đến được tính theo công thức: (2) 2.2.3. Các mô hình Mỗi nút phải xử lý các truy vấn đến và đi hình 10b: truy vấn đến bao gồm tổng thông lượng tới Ofinal, được xử lý bởi ứng dụng phía trên và thông lượng truyền qua Orel là các truy vấn được chuyển đến các nút khác. Ta xet hai trường hợp tắc nghẽn: Trường hợp 1: Đường truyền lên (uplink) là bottleneck: Trên thực tế rất nhiều máy tính cá nhân có đường truyền bất đối xứng với tốc độ download lớn hơn tốc độ upload. Vì thế băng thông của uplink quyết định đến khả năng xử lý của nút. Tuy nhiên chúng ta cũng phải chú ý tới đại lượng α được sinh ra bới các gói tin ack phục vụ cho việc tải thông tin xuống trên đường downlink. Do đó tổng tải đến nút là: Trường hợp 2: Khả năng xử lý của nút là bottleneck: Nếu một nút có đủ băng thông cho cả đường uplink và downlink thì khi đó bottleneck của nút là tốc độ của vi xử lý. Ta có: 2.2.4. Tổng tải đến O Chúng ta tính toán OM1 và OM2 cho mô hình mạng DHT trên, để có thể tính được khả năng xử lý p với c cho trước sử dụng công thức 1. Chúng ta xét trường hợp các nút đồng thời tạo ra các truy vấn ngẫu nhiên với tốc độ x. x ở đấy chứa cả các truy vấn mà nút khởi tạo có thể tự trả lời, tức không cần đi qua nút nào.Trước hết ta xét trường hợp ứng với mạng gồm 8 nút, sau đó sẽ xét tới trường hợp tổng quan. Với mạng gồm 8 nút: Trong trường hợp này số truy vấn không phải qua bất kỳ nút nào là x/8, và 7/8 . x truy vấn cần đi qua các nút trong mạng để đến được đích. Khi đó tải đến nút đầu tiên sẽ là: 20 ∀ d, 0 < d ≤ 7, od 1 = 1/8 · x (3) Ta sẽ tính tổng thông lượng O đến mỗi nút sinh bởi P0. Sử dụng công thức 2 và 3 ta có: Thông lượng tạo bởi ứng dụng đến tất cả các đích trong mạng DHT trước khi qua nút đầu tiên: Thông lượng đạt được tại tất cả các đích sau khi đi qua nút cuối cùng, được xử lý bởi ứng dụng và không chuyển tiếp nữa được tính bởi công thức: Thông lượng chuyển tiếp được chuyển qua các nút lân cận được tính bởi công thức: Thông lượng đến và đi có thể được tính như sau: Với trường hợp có n nút: với bất kỳ mạng DHT log n nào với n=2l trong đó mỗi nút có l=log2n liên kết đến các nút khác trong mạng. Tổng tải trên mỗi nút với đích đến là d ở nút đầu tiên là: ∀ d, 0 < d < n, od 1 = x/n = x/2 l Chúng ta có các tổng tải tương ứng là: 21 Thông lượng cuối hay còn gọi là thông lượng đạt được A thể hiện tổng tất cả các truy vấn được định tuyến thành công. Trong mạng DHT log n qua cách thức chọn lựa các mục định tuyến ta có thể tính toán số lượng các nút có thể đến sau khi đi qua một số nút nhất định bằng tam giác Pascal. Với l nút trong bảng định tuyến sau h lần đi qua các nút khác sẽ có thể tới: nút đích. Trên mỗi nút mà truy vấn đi qua, mỗi truy vấn sẽ được xử lý với xác suất là p. Do đó ta có: Ở đây ta chỉ xét các truy vấn được chuyển qua nút khác, các truy vấn được trả lời ngay trên host đó coi như không tốn tài nguyên, do đó h≥1. Thông lượng chuyển tiếp được tính bằng cách lấy tổng thông lượng đi ra trừ đi thông lượng mới được tạo Tổng thông lượng có thể được tính bằng tam giác Pascal. Tuy nhiên chúng ta xét tới tất cả các nút chứ không riêng ở nút đích. Do đó ta có: Sử dụng công thức 8 với l=3 ta sẽ có lại đúng công thức 4 đã xét ở phần trước. 22 2.2.5. Ví dụ với một triệu nút Ta lấy ví dụ trường hợp l=20, ứng với n=220 tức khoảng 1 triệu nút. Giả sử khả năng xử lý trên mỗi nút là c=120 truy vấn/giây. Ta xét hai trường hợp: M1 là trường hợp đường truyền lên của nút là bottleneck, M2 là trường hợp tốc độ vi xử lý của nút là bottleneck. Ta chọn α=5% cho trường hợp M1 ứng với thông lượng mà các gói tin ACK của TCP. Với các công thức 1, 5 và 8 ta có thể tính toán được xác suất xử lý p với 2l nút với c và x cho trước. Với p và công thức 6 ta có thể tính được Ofinal tức là thông lượng đạt được của mạng DHT. Hình dưới thể hiện thông lượng đạt được A. Thông lượng đạt được cao nhất đạt được khi x đạt giá trị tối ưu: x=11.4 trong trường hợp M1 và x=10,9 trong trường hợp M2. Khi tổng tải đến vượt quá giá trị x tối ưu, thông lượng đạt được sẽ giảm một cách nhanh chóng. Đó là hiện tượng sụp đổ do tắc nghẽn. Hình 11: Thông lượng đạt được so sánh với tốc độ truy vấn cho hệ thống DHT với một triệu nút trong hai trường hợp tắc nghẽn M1 và M2. Mạng DHT sụp đổ khi tải tới đạt đến giá trị xopt 2.2.6. Phân tích các trạng thái tiệm cận của A. Ta xét A trong trường hợp mạng DHT chạy với khả năng tối đa: p → 1 và trường hợp mạng DHT bị quá tải ở mức cao: p → 0 23 Sử dụng công thức )1/()1( 1 0 ppp h h j j    1)1( 1         lhl h pp h l 12 1         ll h h l để đơn giản các công thức từ 5 đến 8 ta có: Ta sẽ tính toán sự thay đổi của thông lượng đạt được A khi p→1 và khi p→0. Với trường hợp M1 ta có: 24 Ứng với p→1 tức là mạng được sử dụng hết khả năng tuy nhiên vẫn chưa quá tải có: Với O≥c mạng được sử dụng hết hoặc chưa sử dụng hết ứng với p ≤1 và O=c/p. Chúng ta có thể tính toán O khi p→1 Với trường hợp M2 tương tự ta có: Ứng với p→0 tức là đang xảy ra tình trạng tắc nghẽn ở mức độ cao. Sử dụng công thức 1/1 – p = 1+p+p 2 +. . ., với | p | < 1 ta có thể khai triển c/x=pO/x thành: a0p 0 + a1p 1 + a2p 2 + . . . và p thành: b0 + b1x -1 + b2x -2 + . . . Do đó ta có:    ... 2 12 21)1( )1(2 2 2      pappp p p x c l l ll l  25 ... 12 2 2 2 1     xbx c p l l Thay p vào công thức 9 và sử dụng công thức:   ...1... 210 1 210 0                            lpp l p l p l p k l p k l k l Do đó với trường hợp 1 và 2 khi p→0 ta có: 2.2.7. Kết luận Với hai trường hợp M1 khi đường uplink là bottleneck, và M2 khi tốc độ xử lý là bottleneck, mạng DHT có thể rơi vào trạng thái sụp đổ do tắc nghẽn nếu như các nút trong mạng tăng tốc độ truy vấn mà không tính toán đến khả năng chịu tải của mạng. Trong thực tế với mô hình mạng phức tạp, khả năng chịu tải của các nút là hoàn toàn khác nhau, thời gian truy vấn không theo quy luật, tình trạng mạng sụp đổ do tắc nghẽn sẽ xảy ra dễ dàng và nhanh chóng hơn. 26 Chương 3. Các nghiên cứu về điều khiển tắc nghẽn trên DHT Các nghiên cứu liên quan về vấn đề điều khiển tắc nghẽn của mạng DHT tập trung chủ yếu vào hai hướng giải quyết:  Điều khiển tốc độ truy vấn: giới hạn tốc độ gửi ở nút truy vấn hoặc tốc độ xử lý ở nút đích khi nút đích có hiện tượng quá tải. Gồm các phương pháp: Credit System Congestion Control (CSCC), Back-Pressure Congestion Control (BPCC), và phương pháp đánh dấu (Marking)  Thay đổi bảng định tuyến nhằm chuyển truy vấn đang đi qua nút quá tải sang nút không quá tải. Ý tưởng chung của các phương pháp này là việc không sử dụng thuật toán định tuyến tham lam (như trong Chord, nút được chuyển tiếp gói tin đến là nút trong bảng định tuyến có định danh gần với khóa nhất), mà dựa vào tình trạng từng nút để thay đổi đường đi của gói tin qua các nút ít tắc nghẽn hơn. Các phương pháp này đều có những ưu nhược điểm riêng sẽ được phân tích dưới đây. 3.1. Phương pháp CSCC[4] Ta có thể coi mô hình của mạng DHT (cụ thể là Chord) được phân tầng như hình dưới Hình 12: Phương pháp CSCC 27 Layer 1 đảm nhận việc truyền thông tin giữa 2 nút, layer 2 – overlay routing đảm nhận việc chuyển tiếp gói tin lên trên hoặc qua các nút khác tùy thuộc vào điểm đến của gói tin, layer 3 là tầng ứng dụng nằm trên mạng DHT. CSCC hoạt động phía trên của layer 2 – overlay routing và dưới layer 3. Tại nút đích mỗi khi nhận được gói tin đến CSCC sẽ trả lại gói tin ACK trực tiếp cho nút ban đầu gửi truy vấn bằng giao thức UDP. Tại nút nhận, CSCC duy trì trong bộ nhớ đệm của nó một hàng đợi cho các truy vấn đến. Khi hàng đợi đạt tới mức giới hạn của nút, các truy vấn đến sau sẽ bị loại bỏ mà không có thông báo gì cho nút gửi. Trên mỗi nút lưu một giá trị credit thể hiện số lượng truy vấn đã gửi đi mà chưa nhận được gói tin ACK trả về. Sử dụng thuật toán tương tự như thuật toán tính toán kích thước cửa sổ TCP cho giá trị credit, ta so sánh giá trị credit này với một giá trị threshold. Nếu credit nhỏ hơn threshold ta tiếp tục tăng nhanh giá trị credit, nếu credit đến ngưỡng threshold, ta sẽ tăng chậm hơn với mỗi gói ACK nhận được. Nếu như có gói tin bị mất (quá thời gian timeout mà chưa có gói ACK trả về) giá trị threshold sẽ được giảm xuống. Sau khi nhận biết một gói tin bị mất, nút gửi sẽ gửi lại gói tin đó. Có thể thấy phương thức hoạt động của CSCC gần tương tự như CC của TCP. Tuy nhiên nhược điểm của CSCC là sử dụng trên mạng DHT với quá trình kết nối tương đối phức tạp, chuyển tiếp giữa nhiều nút, không giống như TCP có kết nối 2 điểm trong thời gian dài và tương đối ổn định. Điều này gây khó khăn cho việc xác định các giá trị cần thiết như thời gian timeout. Thêm nữa, một gói tin có thể nhận được nhiều lần do đó mỗi nút cần phải tốn tài nguyên lưu giữ danh sách các gói nhận được ứng với mỗi nút gửi. CSCC thực hiện việc drop gói tin do đó thông lượng đạt được sẽ giảm. 3.2. Phương pháp BPCC[4] Tương tự như phương pháp CSCC mỗi nút đều lưu một hàng đợi cho các truy vấn đến. Tuy nhiên ở phương pháp này thay vì loại bỏ gói tin, nút đích gửi trạng thái hàng đợi của nó cho nút gửi. Khi đó nút gửi sẽ tự điều chỉnh lại tốc độ gửi để tránh tắc nghẽn xảy ra. BPCC sử dụng TCP ở layer 1. 28 Hình 13: Phương pháp BPCC Khi hàng đợi tại nút P đầy, thay vì loại bỏ gói tin, nút sẽ tạm ngưng việc đọc gói tin từ socket TCP của các kết nối đến. Khi đó thuật toán điều khiển lưu lượng sẵn có của TCP sẽ tự động làm chậm lại việc các nút gửi truy vấn đến nút P. Nguy cơ hình thành deadlock: Nguyên nhân của việc hình thành deadlock là khi một nút gửi đợi nút nhận xử lý các gói tin trong hàng đợi, trong khi nút nhận cũng đang phải đợi một nút khác. Deadlock xảy ra khi các nút đợi nhau tạo thành vòng kín, dễ thấy trong trường hợp mạng có dạng vòng như Chord. Có thể thấy khác biệt lớn nhất của BPCC là việc phương thức này không drop gói tin, do đó tăng thông lượng đạt được trên toàn hệ thống. Tuy nhiên phương pháp này có thể sinh ra deadlock và việc phát hiện, xử lý deadlock này là rất khó khăn, đặc biệt là trong môi trường mạng ngang hàng với sự tham gia của nhiều nút tự do, không thể kiểm soát. Ngoài ra việc chờ đợi trên các nút gây tăng thời gian đáp ứng của các truy vấn. 3.3. Phương pháp Marking[3] Hai phương pháp CSCC và BPCC ở trên có chung một nhược điểm là chỉ thực hiện việc chống tắc nghẽn tức là khi tắc nghẽn đã xảy ra trên mạng. Phương pháp Marking có gắng giải quyết vấn đề này. Để phân tích phương pháp này ta xét lần lượt từng thành phần tham gia vào việc điều khiển tắc nghẽn trong phương pháp này: Layer 3 BPCC Layer 2 Layer 1 - TCP Layer 3 BPCC Layer 2 Layer 1 - TCP Destination Queue state Source 29 Hàng đợi: Trên mỗi nút duy trì một hàng đợi chứa các truy vấn tới. Ta sử dụng các hàng đợi này để phản hồi tình trạng tắc nghẽn thông qua việc thêm một cờ h vào trong header. Mục đích là giữ cho các nút được chia sẻ tài nguyên đang bị bottleneck một cách công bằng mà không làm quá tải nút đang tắc nghẽn. Cờ h có kích thước 1 bit, mặc định được tắt trong gói tin truy vấn tại nguồn. Cờ h tắt thể hiện tình trạng mạng không tắc nghẽn, h bật thể hiện tình trạng tắc nghẽn. Mỗi nút đặt giá trị x thể hiện tốc độ truy vấn hiện tại của nó vào trong header của gói tin. Ngoài ra mỗi nút lưu số lượng trung bình xavg các gói tin, được tính toán thông qua giá trị x nhận được từ một số gói tin đến trước đó. Cờ h được bật với xác suất q được xác định thông qua việc xét xem gói tin đến có tốc độ nhanh hay chậm hơn giá trị trung bình xavg và giá trị trung bình kích thước của hàng đợi, cụ thể như sau: s: là số lượng gói tin trong hàng đợi δ: giá trị làm mềm, ví dụ bằng 0.9 s : số lượng trung bình các gói tin trong hàng đợi t: giá trị ngưỡng tối đa sẽ gửi phản hồi γ: giá trị đảm bảo độ công bằng s = (1 − δ) · s + δ · s q=min                   1, )(  avgx x stt s (10) Công thức 10 bao gồm 2 phần: phần thứ nhất dùng cho việc điều khiển tắc nghẽn, giá trị số gói tin trung bình s càng gần đến ngưỡng t sẽ làm tăng xác suất q dẫn tới việc khả năng cờ h được bật tăng. Nếu s ≥t, q=1 thì cờ h sẽ được bật với xác suất bằng 1. Giá trị ngưỡng t được đặt nhỏ hơn khả năng tối đa mà hàng đợi có thể lưu trữ, để đảm bảo khả năng phục vụ kể cả trong trường hợp có lượng lớn gói tin trong một thời điểm ngắn. Ngoài ra còn có thêm giá trị δ trong việc tính toán giá trị s để tránh việc bật cờ h trong trường hợp tốc độ truy vấn thay đổi đột biến trong thời gian ngắn. Phần thứ hai được dùng cho mục đích đảm bảo công bằng: khi tốc độ truy vấn x của một nút nguồn nhỏ hơn tốc độ trung bình xavg của truy vấn đến mà nút đích nhận được thì q giảm. Ngược lại 30 nếu x > xavg thì q tăng, thể hiện việc nút nguồn sẽ bị giới hạn tốc độ nếu như chiếm phần lớn tài nguyên của nút đích. Giá trị γ xác định xem mức độ quan trọng của việc chia sẻ công bằng. Nếu γ = 0 sẽ bỏ qua việc đảm bảo công bằng. γ càng lớn thì độ lệch giữa x và xavg sẽ ảnh hưởng càng nhiều đến xác suất p. Một khi cờ h được bật nó sẽ không bị tắt trên suốt quãng đường truyền tới đích cuối cùng. Nút đích sao chép giá trị của h vào gói tin overlay-acknowledgement được gửi trả lại cho nút nguồn kèm với trả lời cho truy vấn. Nút nguồn: Một nút sẽ nhận được gói tin trả lời truy vấn với overlay-ack có cờ h. Nếu h tắt, tức là không có tắc nghẽn, nút tăng tốc độ truy vấn của nó như sau: x c xx : c+ là một hằng số dương nhỏ thể hiện mức độ một nút kiểm tra lượng băng thông còn có thể sử dụng khi nhận được thông báo không tắc nghẽn. Với cờ h được bật nút giảm tốc độ truy vấn của nó như sau:  cxx : với 0 < c- < 1 là hằng số, thể hiện mức độ một nút giảm tốc độ truy vấn khi có tắc nghẽn xuất hiện. Qua hai công thức trên có thể thấy ta tăng tốc độ truy vấn theo cấp số cộng và giảm theo cấp số nhân của một nút tương tự như trong TCP. Giá trị c+ và c- được chọn dựa vào RTT và khả năng phục vụ của mạng. Lựa chọn giá trị RTT: Mỗi nút lưu một giá trị RTT ước lượng cho các truy vấn: với mỗi truy vấn RTT được tính dựa trên thời gian gửi và thời gian nhận được phản hồi. Giá trị RTT được sử dụng cho toàn mạng nghĩa là không phụ thuộc vào đích đến của truy vấn. Do thông thường mỗi truy vấn đến một nút khác nhau trong mạng do đó giá trị RTT có sự thay đổi rất lớn. Nếu như sau thời gian RTT mà nút không nhận được trả lời cho truy vấn, một nút giảm tốc độ gửi truy vấn và gửi lại truy vấn. Do không phải loại bỏ gói tin cũng như cơ chế gọn nhẹ trong việc gửi phản hồi tình trạng tắc nghẽn cho nút nguồn nên phương pháp Marking có kết quả về 31 thông lượng đạt được cũng như thời gian trả lời truy vấn tốt hơn nhiều so với hai phương pháp CSCC và BPCC đã trình bày ở phần trước. 3.4. Phương pháp định tuyến thích nghi[5] Các phương pháp trình bày ở trên đều có chung nhược điểm là nếu trong mạng có tồn tại các nút có khả năng đáp ứng thấp hơn hẳn các nút khác sẽ gây giảm thông lượng đạt được trên toàn mạng. Để giải quyết vấn đề này, phương pháp định tuyến thích nghi được đề xuất. Đây cũng là phương pháp gần nhất với giải pháp được nêu ra trong tài liệu này. Trong phương pháp này, thay vì chọn nút gần với khóa cần tìm nhất, ta chọn ra k nút gần với khóa và theo dõi hiệu năng của các nút đó. Khi gửi đi một truy vấn nút nguồn kiểm tra gói tin trả lời chứa cờ báo hiệu tắc nghẽn h trong header để xác định khả năng sử dụng của mỗi đường định tuyến qua k nút trên. Để đơn giản ta xét trường hợp k=2, nghĩa là một nút có hai đường định tuyến qua hai nút lân cận. Giả sử ta có mạng DHT như sau: Hình 14: Mạng DHT với 8 nút. Bảng dưới thể hiện các đường định tuyến mà P0 có thể sử dụng khi chuyển tiếp gói tin. 32 Ví dụ với dòng thứ 3, với đích là nút P3 lựa chọn đầu tiên của P0 là chuyển qua nút P2 sử dụng đường dẫn l0-2 và lựa chọn thứ hai là qua P1 sử dụng đường dẫn l0-1. Nếu như nút đích lưu khóa cần tìm thì sẽ không có lựa chọn thứ hai (N/A). Nếu hai nút có cùng khoảng cách đến khóa cần tìm ta chọn nút bên trái làm lựa chọn đầu tiên. Định tuyến thích nghi: Mỗi nút ghi nhận giá trị của cờ h trong gói trả về trên cả hai đường định tuyến. Với mỗi cặp đường định tuyến mỗi nút duy trì k (ở đây k=2) giá trị xác suất đã quan sát được (op) của giá trị cờ h trong gói trả về như bảng dưới: Các giá trị xác suất này là thông tin duy nhất mà mỗi nút cần phải duy trì cho việc định tuyến chống tắc nghẽn. Mỗi nút sẽ chỉ phải lưu thêm O(log(n)) thông tin thêm do đó mạng vẫn sẽ giữ được khả năng mở rộng cao. Thay đổi lưu lượng: Để đạt được mục đích tăng thông lượng đạt được trên toàn mạng ta thực hiện việc chuyển lưu lượng chuyển qua các nút. Mỗi nút có thể sử dụng k đường định tuyến để chuyển tiếp gói tin (ở đây k=2). Như ở bảng trên mỗi nút lưu xác suất op1 và op2, giữa vào các xác suất này một nút sẽ chuyển lượng f1 lưu lượng qua đường định tuyến thứ nhất và f2 lưu lượng qua đường thứ hai (f1+f2=1). Một nút cập nhật giá trị f1 và f2 bằng cách sử dụng công thức: δ = (op1 – op2 ) · φ f1 = f1 − δ, f2 = f2 + δ fmin ≤ fi, fj ≤ 1 – fmin trong đó δ là lưu lượng chuyển từ đường định tuyến thứ nhất sang đường định tuyến thứ hai. Giá trị φ là một hằng số xác định tốc độ chuyển lưu lượng từ đường định tuyến này sang đường khác. Nếu δ có giá trị âm lưu lượng sẽ được chuyển ngược lại. Các giá trị f được có cận dưới được xác định bởi giá trị fmin như công thức ở trên nhằm đảm bảo luôn luôn nhận được phản hồi về khả năng của mỗi đường định tuyến. 33 Với trường hợp k>2 đầu tiên chúng ta tính toán giá trị opmean là giá trị trung bình của tất cả các opi. Sau đó chúng ta sẽ tăng giảm fi dựa vào việc so sánh các giá trị opi và opmean. Một nút cập nhật các giá trị op mỗi khi có truy vấn mới. Khi một nút chuyển tiếp các truy vấn từ các nút khác, nó sẽ chia lưu lượng theo các hướng dựa vào các tính toán về khả năng của từng đường định tuyến. Do đó trên mỗi nút truy vấn sẽ được định tuyến theo đường tối ưu, qua đó sẽ tăng thông lượng đạt được trên toàn mạng. Nhược điểm của phương pháp này là khi muốn tăng số lượng các đường định tuyến, ta phải tăng kích thước bảng định tuyến. Sẽ là rất tốn kém tài nguyên nếu như mỗi nút phải duy trì bảng theo dõi trạng thái của nhiều nút khác. Đồng thời việc bỏ phương pháp định tuyến tham lam sẽ làm tăng số lượng gói tin truyền trên mạng. 34 Chương 4. Điều khiển tắc nghẽn sử dụng phương pháp thay đổi bảng định tuyến 4.1. Đề xuất phương pháp Như các phân tích ở chương trước về các cơ chế điều khiển tắc nghẽn đã có, ta thấy còn một số nhược điểm cần khắc phục. Khóa luận này nhằm đưa ra một phương pháp điều khiển tắc nghẽn sử dụng việc thay đổi bảng định tuyến với mục đích chính là: điều khiển tắc nghẽn, giảm thiểu tối đa sự gia tăng số lượng nút phải đi qua với mỗi truy vấn so với phương pháp định tuyến tham lam đã có, đồng thời không làm ảnh hưởng quá nhiều đến mô hình hoạt động của mạng Chord, tránh phát sinh lãng phí tài nguyên cho việc duy trì thêm nhiều thông tin và các gói tin phụ phục vụ cho việc thay đổi định tuyến này. Để thực hiện các yêu cầu trên ta sẽ tìm cách tác động đến bảng định tuyến trên từng nút để khi có nút tắc nghẽn trên bảng định tuyến, nút đó sẽ được thay thế bằng nút lân cận. Để tối thiểu số lượng nút phải đi qua với mỗi truy vấn ta sẽ ưu tiến thay thế nút tắc nghẹn bằng nút lân cận nằm ngoài khoảng giữa nút truy vấn và nút đang bị tắc nghẽn. Để đơn giản khi ta chuyển định tuyến đến nút lân cận nếu như nút đó cũng gặp tình trạng tắc nghẽn thì ta tiếp tục chuyển đến nút lân cận tiếp theo. Ta chỉ giữ trong mỗi mục của bảng định tuyến hai giá trị của nút đích đó là nút đích ban đầu và nút đích được chuyển định tuyến tới tại thời điểm hiện tại. 4.2. Nội dung chi tiết Ta đi vào nội dung chi tiết của phương pháp đã được khái quát ở trên. Để đảm bảo việc điều khiển tắc nghẽn ta xét lần lượt các bước gặp phải khi cần giải quyết bài toán tắc nghẽn trên một hệ thống. 4.2.1. Phát hiện tắc nghẽn. Trên mỗi nút ta tính toán tốc độ xử lý gói tin tối đa mà nút đó có thể xử lý được, ta có thể tính toán giá trị đó thông qua tốc độ xử lý và đường truyền của máy. Việc tính toán này không nằm trong nội dung của khóa luận này. Ta quy định trên mỗi nút sẽ tồn tại hai giá trị giới hạn gọi là hardLimitRate và softLimitRate, lần lượt ứng với tốc độ xử lý tối đa của máy trên một đơn vị thời gian: limitRate và x*limitRate (với x là hằng số 0<x<1). Khi tốc độ gói tin tới nút chạm tới mức softLimitRate ta coi như máy đó bước vào giai đoạn “tắc nghẽn mềm” và sẽ tiến 35 hành các phương thức chống tắc nghẽn với nút đó. Khi tốc độ gói tin tới mức hardLimitRate thì lúc đó máy bị tắc nghẽn hoàn toàn. Việc tính toán giá trị của hằng số x sẽ ảnh hưởng đến độ “nhạy” của việc phát hiện tắc nghẽn, nếu x quá nhỏ các nút sẽ dễ dàng bị coi là tắc nghẽn dù vẫn còn khả năng phục vụ, nếu x quá lớn sẽ khiến cho việc xử lý tắc nghẽn trên nút diễn ra quá muộn dẫn tới trường hợp nút bị tắc nghẽn hoàn toàn kéo theo số lượng gói tin bị loại bỏ sẽ tăng. 4.2.2. Xử lý trong trường hợp có tắc nghẽn Khi phát hiện “tắc nghẽn mềm” trên nút, nếu nút nhận được một truy vấn tới thì hệ thống sẽ tiến hành các động thái sau:  Nút nhận đang bị tắc nghẽn sẽ gửi gói tin đến nút vừa gửi truy vấn đến nó thông báo mình bị tắc nghẽn. Nút nhận lưu lại danh sách các nút nó đã gửi thông báo tắc nghẽn đến.  Nút gửi truy vấn (có thể là nút vừa chuyển tiếp truy vấn) đến nút tắc nghẽn tiến hành thay đổi bảng định tuyến của nó: chuyển nút tắc nghẽn thành các nút lân cận không bị tắc nghẽn.  Truy vấn đến nút đang bị “tắc nghẽn mềm” vẫn tiếp tục được xử lý như bình thường Để tiến hành thay đổi bảng định tuyến đồng thời giữ lại giá trị nút đích ban đầu ta thay đổi bảng định tuyến (bảng finger) bằng cách thêm một cột lưu giữ giá trị định tuyến ban đầu. Khi đó bảng finger có dạng ví dụ như sau: Finger Active Route Origin Route 1 (Pi + 1) Pa Pa 2 (Pi + 2) Pb Pb 3 (Pi + 4) Pc Pc … … … M (Pi + 2 m ) Px Px Giả sử khi nút Pb bị tắc nghẽn ta sẽ thay đổi bảng finger thành: 36 Finger Active Route Origin Route 1 (Pi + 1) Pa Pa 2 (Pi + 2) Pt Pb 3 (Pi + 4) Pc Pc … … … M (Pi + 2 m ) Px Px Với Pt là successor của Pa. Việc chọn lựa nút thay thế là nút “xa hơn” nút nguồn so với nút ban đầu nhằm mục đích giảm thiểu số lượng nút mà gói tin phải chuyển qua. Nếu có một truy vấn tới Pi mà theo bảng finger gốc truy vấn đó sẽ chuyển qua nút Pb, thì trong thời điểm này truy vấn đó sẽ được chuyển tới:  Pt nếu khóa của truy vấn không nằm trong khoảng của Pb và Pt  Pb nếu khóa của truy vấn nằm trong khoảng Pb và Pt Trong trường hợp gói tin đến khi nút đang bị tắc nghẽn hoàn toàn (tốc độ gói tin đến vượt quá hardLimitRate) thì gói tin đó sẽ bị loại bỏ. 4.2.3. Xử lý khi hết tắc nghẽn Các nút trong hệ thống thực hiện việc kiểm tra định kỳ số lượng truy vấn tới để so sánh với các giới hạn đã có. Khi một nút đang từ trạng thái tắc nghẽn chuyển về trạng thái không tắc nghẽn (có lượng truy vấn tới trong một đơn vị thời gian nhỏ hơn softLimitRate), hệ thống sẽ tiến hành các bước sau:  Nút vừa ra khỏi trạng thái tắc nghẽn sẽ gửi thông báo về tình trạng của mình cho một số nút trong danh sách các nút nó đã gửi thông báo tắc nghẽn mà nó đã lưu lại như mô tả ở bước trên.  Nút nhận được thông báo hết tắc nghẽn sẽ thay đổi các mục có liên quan về nút vừa gửi thông báo trong bảng định tuyến về trạng thái như ban đầu. 37 Ví dụ như trường hợp trên khi nhận được thông báo hết tắc nghẽn từ Pb, thì Pi sẽ chuyển Pt lại thành Pi trong bảng định tuyến của nó. Số lượng nút sẽ nhận được thông báo khi nút đích hết tắc nghẽn cũng cần được quan tâm ở đây. Ta chỉ chọn ra một số lượng nhất định trong số các nút trong danh sách nút đã nhận được thông báo tắc nghẽn. Số lượng nút nhận được thông báo hết tắc nghẽn sẽ gián tiếp ảnh hưởng đến mức độ khôi phục lại tải sau tắc nghẽn của một nút, nếu ta đặt giá trị này quá thấp sẽ làm cho nút chậm trở lại trạng thái phục vụ bình thường, nếu như quá cao sẽ dễ làm cho nút bị tắc nghẽn trở lại. 4.3. Ví dụ minh họa Ta xét một mạng Chord đơn giản với không gian khóa 8 bit để minh họa cho giải pháp vừa đưa ra: Hình 15: Truy vấn thông thường trên mạng Chord (m=8). Ta thực hiện việc truy vấn khóa 54 trên nút P8. Hình 13 mô tả quá trình truy vấn thông thường theo đúng như thuật toán ban đầu của Chord. Khi đó bảng finger trên nút P8 có dạng: 38 Hình 16: Bảng định tuyến ban đầu của nút P8 Giả sử ta phát hiện tắc nghẽn tại nút P42, khi đó nút này sẽ thông báo cho nút nguồn thực hiện truy vấn (nút P8) về tình trạng của mình. Với giải pháp đã nêu ta thực hiện việc thay đổi bảng finger trên nút P8 như sau: Hình 17: Bảng định tuyến của nút P8 khi xảy ra tình trạng tắc nghẽn trên nút P42. Trên nút P8 tất cả các mục định tuyến có nút đích là P42 sẽ được thay đổi thành successor của P42 là P48. Khi đó nếu tiếp tục phát sinh truy vấn từ nút P8 mà truy vấn đó theo như bảng finger ban đầu sẽ phải đi qua nút P42 sẽ được thay đổi để đi qua nút P48. Hình 18: Truy vấn được thay đổi đường đi khi áp dụng giải pháp chống tắc nghẽn 39 Như hình trên truy vấn thay vì đi qua nút P42 đang tắc nghẽn sẽ được điều chỉnh đi qua nút P48. Số lượng nút mà truy vấn phải đi qua vẫn là 3 bằng với số lượng cần thiết trong trường hợp ban đầu. Giả sử nút P48 cũng xảy ra tình trạng tắc nghẽn, trên bảng định tuyến nút P8 nút P48 sẽ được thay thế bằng nút P51. Vẫn trên nút P8 giả sử ta cần truy vấn khóa 49. Do 49 thuộc khoảng [42,51) nên truy vấn sẽ phải đi qua nút P42 và được thực hiện như bình thường. Trong quá trình hoạt động giả sử một số nút có bảng định tuyến đi qua nút P42 đều phải thay đổi để qua nút khác thì khi nút P42 hết tắc nghẽn các nút đã thay đổi bảng định tuyến sẽ được lần lượt phục hồi về trạng thái ban đầu. 4.4. Nhận xét về phương pháp Ta có thể rút ra một số nhận xét về phương pháp đã nêu ở trên:  Ưu điểm: Có thể thấy đây là một phương pháp đơn giản nhằm điều khiển tắc nghẽn trong mạng Chord. Việc thay đổi định tuyến sẽ giúp tránh khỏi nút tắc nghẽn qua đó tăng khả năng thực hiện truy vấn thành công. Việc thay đổi chỉ tác động một số nhỏ các nút (nút tắc nghẽn và nút nguồn) do đó số lượng gói tin và thông tin phụ cần để thực hiện quá trình thay đổi và phục hồi là không lớn. Hơn nữa việc chọn lựa nút thay thế nút tắc nghẽn như đã trình bày ở trên không làm tăng số lượng nút mà mỗi một truy vấn phải đi qua.  Nhược điểm: Do cơ chế thay đổi nút định tuyến rất đơn giản nên chỉ có thể giới hạn các nút thay thế có định danh nằm trong vùng định danh lân cận với nút tắc nghẽn, mà không xét đến yếu tố là khả năng đáp ứng của nút vào việc quyết định lựa chọn nút thay thế. Ngoài ra việc chuyển đổi có thể tiếp tục nếu như nút đích mới cũng bị tắc nghẽn nên có thể gây đến tình trạng số lượng gói tin thông báo tăng rất cao trong trường hợp toàn bộ các nút trên mạng đều rơi vào trạng thái tắc nghẽn khi không có một cơ chế giới hạn số lần chuyển đổi bảng định tuyến. Hơn thế nữa có thể dễ nhận thấy việc thay đổi đường định tuyến của gói tin không thể giải quyết triệt để tắc nghẽn nếu như các nút trong mạng tiếp tục đẩy tốc độ truy vấn lên quá cao so với khả năng đáp ứng của mạng. Dù còn tồn tại một số nhược điểm tuy nhiên phương pháp đã nêu có thể giải quyết được vấn đề tắc nghẽn ở mức độ nhẹ đặc biệt là các trường hợp tắc nghẽn cục bộ, qua đó tăng khả năng đáp ứng của toàn mạng. Mặt khác phương pháp 40 này hoàn toàn có thể kết hợp với các phương pháp điều khiển tắc nghẽn sử dụng phương pháp điều chỉnh lưu lượng đã có nhằm loại bỏ khả năng sụp đổ của mạng khi xảy ra tắc nghẽn ở mức độ cao. 41 5. Mô phỏng và kết quả 5.1. Mô phỏng Để kiểm chứng khả năng hoạt động chính xác cũng như những lợi ích đạt được, ta sử dụng một hệ thống mô phỏng mạng Chord và tiến hành cài đặt giải pháp đã đề xuất. 5.1.1. Chương trình mô phỏng Tổng quan cấu trúc mạng mô phỏng: Do mô hình mạng trên thực tế là rất phức tạp và khó có khả năng thể hiện hoàn thiện trên một chương trình mô phỏng do đó ta chỉ xét đến tính chất đặc trưng có ảnh hưởng lớn tới một hệ thống mạng ngang hàng đó là độ trễ giữa các nút trong mạng. Mô hình mạng mô phỏng bao gồm:  Nhiều miền (area) chứa một số nút nhất định, các miền độc lập với nhau  Mỗi miền có một nút biên, nút biên này nối với các nút khác theo mô hình hình sao.  Các miền được nối với nhau thông qua liên kết giữa hai nút biên của miền. Liên kết này được đặt ngẫu nhiên một giá trị độ trễ gọi là độ trễ liên miền.  Liên kết giữa các nút trong miền và nút biên cũng được lấy ngẫu nhiên một giá trị độ trễ gọi là độ trễ nội miền. Độ trễ nội miền sẽ nhỏ hơn nhiều so với độ trễ liên miền. Hình 19: Mô hình mạng mô phỏng 42 Với mô hình trên ta có thể tính toán được độ trễ giữa hai nút trong mạng bằng cách cộng giá trị độ trễ nội miền và liên miền của hai nút đó (nếu hai nút cùng miền thì độ trễ liên miền bằng 0). Có thể thấy với cách xác định độ trễ như vậy thì giá trị độ trễ ở đây là cố định, trong khi với mạng thực tế độ trễ là một giá trị biến đổi liên tục, ngoài ra mạng thực tế còn phức tạp hơn nhiều với cấu trúc đa tầng, tuy nhiên mô hình này cũng đã đủ đáp ứng mục đích mô phỏng độ trễ đa dạng giữa các nút có trong mạng. Cấu trúc chương trình: Chương trình bao gồm các lớp quan trọng sau:  Lớp Areas: gồm các đối tượng chứa thông tin về các miền có trong mạng mô phỏng, chứa các hàm truy xuất thông tin về miền, các hàm tính toán độ trễ liên miền.  Lớp Node: chứa thông tin về các nút có trong mạng. Một nút có các giá trị quan trọng như: tên, định danh, định danh miền chứa nó, độ trễ nội miền. Mỗi nút khi đưa vào mạng sẽ lưu thêm thông tin về các định danh của các nút successor, predecessor và bảng định tuyến. Bảng định tuyến (bảng finger) chứa thông tin về các finger của nút – là các đối tượng thuộc lớp FingerEntry. Lớp Node ngoài các phương thức để thiết lập và truy xuất các thông tin kể trên còn một số phương thức quan trọng sau: o fixFingerTable: thực hiện quá trình ổn định mạng bằng cách kiểm tra và chỉnh sửa lại tất cả các finger của nút. o findSuccessor: đảm nhận việc tìm kiếm nút successor của một khóa cho trước. Phương thức trả lại giá trị là định danh của chính nút đó Hình 20: Mô hình lớp Node 43 nếu nó là successor của khóa, hoặc sẽ chuyển tiếp truy vấn cho một nút gần nhất sau khóa trong bảng định tuyến bằng cách tiếp tục gọi đệ quy phương thức findSuccessor trên nút đó.  Lớp FingerEntry gồm các đối tượng là các mục trong bảng định tuyến của mỗi nút. Mỗi nút chứa fingerTable là tập hợp các đối tượng FingerEntry tạo nên bảng định tuyến của nút đó.  Lớp Network: Là lớp chứa toàn bộ thông tin về mạng mô phỏng. Sau khi khởi tạo các đối tượng miền và nút được thêm vào đối tượng network để xây dựng mô hình mạng. Đối tượng này tiếp tục thực hiện tất cả các quá trình phân bố tài nguyên vào các nút, sinh ra các truy vấn và thực hiện các truy vấn này. Các phương thức quan trọng là: o nodeBirth, nodeDeath o fixFingerTables o getNodeDistance  Lớp InputGenerator: Là lớp đảm nhận việc sinh các dữ liệu cần thiết cho mạng hoạt động gồm thông tin về mạng, nút, vị trí của nút.  Lớp ResourceGen: Là lớp đảm nhận việc sinh tài nguyên và các truy vấn theo phân phối Zipf.  Lớp DoSchedule: Đảm nhận nhiệm vụ lên lịch và thực thi lần các thao tác của chương trình mô phỏng. Quá trình thực thi: Quá trình thực thi chương trình sẽ được phân ra làm nhiều bước và thực hiện tuần tự: đầu tiên là việc sinh ra các dữ liệu về mạng, tiếp đến là dữ liệu về tài nguyên và các truy vấn. Sau khi hoàn tất việc sinh các dữ liệu cần thiết, chương trình sẽ tiếp tục thực hiện các truy vấn, sau quá trình truy vấn các thông tin về mạng và kết quả thu được sẽ được tổng hợp và xuất ra file hoặc màn hình. Quá trình sinh dữ liệu: Ban đầu một đối tượng Network được khởi tạo. Tiếp đó các thông tin về các đối tượng miền và nút được tạo ra từ các hằng số như số lượng miền, số lượng nút… Thời gian, thứ tự thực hiện truy vấn cũng như khả năng chịu tải của nút sẽ được sinh ngẫu nhiên bằng quá trình Poisson. Các thông số này được lưu lại thành file. Sau đó các đối tượng Areas và Node được sinh ra từ các file thông số đó. Sau khi tất cả các nút được sinh bằng cách gọi phương thức nodeBirth, bảng định tuyến của tất cả các nút được tính toán dựa vào phương thức fixFingerTables. Tiếp đến lớp ResourceGen được sử dụng để tạo số lượng các tài nguyên, cũng như danh sách truy vấn tương ứng. 44 Quá trình thực thi: Chương trình khởi tạo đối tượng thuộc lớp DoSchedule ứng với các thông số đã khởi tạo trước đó. Các thao tác thực hiện được đọc từ file schedule, bắt đầu bằng việc gán các tài nguyên vào từng nút, tiếp đến thực hiện các truy vấn từ file danh sách đã tạo ra trước đó. Quá trình thực hiện truy vấn theo đúng thiết kế của Chord thông qua hàm findSuccessor của lớp Node. 5.1.2. Các thay đổi đã áp dụng Để cài đặt phương pháp điều khiển tắc nghẽn đã nêu, ta tiến hành một số thay đổi trên chương trình:  Cấu trúc chương trình: với lớp FingerEntry ta thêm biến lưu trữ thông tin về nút đích ban đầu.  Quá trình sinh dữ liệu: ngoài các dữ liệu ban đầu, ta sinh thêm một số dữ liệu như: giới hạn khả năng đáp ứng của các nút, thời gian thực hiện các truy vấn, thứ tự các nút thực hiện các truy vấn.  Quá trình thực thi: thay đổi chủ yếu được thực hiện trên lớp Node bao gồm các phương thức nhằm thực hiện: o Phát hiện tắc nghẽn: trên mỗi nút duy trì một vector có kích thước bằng giới hạn khả năng đáp ứng của nút, chứa thời gian các truy vấn tới nút. Dựa vào vector này ta tính toán được tại thời điểm có một truy vấn tới nút đang trong tình trạng không tắc nghẽn, tắc nghẽn mềm hay tắc nghẽn hoàn toàn. o Xử lý tắc nghẽn: Ta tạo ra phương thức tìm kiếm Successor cho một khóa mới. Nếu nút đang nhận truy vấn không bị tắc nghẽn việc thực hiện tương tự như phương thức findSuccessor ban đầu. Nếu nút xảy ra tắc nghẽn “mềm” sẽ tiến hành đặt lại fingerTable trên nút gửi truy vấn: chuyển tất cả các mục có đích là nút tắc nghẽn thành nút lân cận. Đồng thời lưu định danh nút gửi truy vấn vào danh sách các nút đã tiến hành thay đổi định tuyến: nodeChangedRoute. Với mỗi truy vấn sau đó nếu khóa cần tìm thuộc khoảng nút đích ban đầu và nút đích đã thay đổi ta thực hiện hàm tìm kiếm successor trên nút đích ban đầu, ngược lại ta thực hiện trên nút đích mới. Nếu nút tắc nghẽn hoàn toàn truy vấn sẽ bị hủy bỏ và ghi lại để tiện thực hiện việc nhận xét sau này. o Xử lý khi nút hết tắc nghẽn: Khi một nút hết tắc nghẽn, sẽ thay đổi lại bảng fingerTable của một số nút thuộc danh sách nodeChangedRoute. Số lượng nút thay đổi lại fingerTable được 45 tính bằng kích thước danh sách nodeChangedRoute nhân với một hằng số quy định trước. 5.2. Kết quả 5.2.1. So sánh với mô hình Chord chuẩn Để xác định hiệu quả của phương pháp đã đưa ra chúng ta tiến hành so sánh với mô hình Chord truyền thống. Với cùng một số bộ dữ liệu ta sẽ chạy lần lượt hai chương trình, trong đó một là chương trình truyền thống, hai là chương trình có áp dụng việc điều khiển tắc nghẽn. Việc đánh giá sẽ dựa trên số lượng gói tin bị loại bỏ và số gói tin trung bình phát sinh thêm với mỗi một truy vấn thành công trong toàn quá trình thực thi. Mạng được xây dựng với một số thông số cơ bản như sau: số lượng node: 1000, độ dài khóa là 16 bit, số lượng query 10000, giá trị lambda để sinh ngẫu nhiên khả năng chịu tải của các nút trong mạng là 10. Ta lần lượt thay đổi tốc độ truy vấn của các nút trên mạng và quan sát sự thay đổi về số lượng truy vấn bị loại và số gói tin phát sinh. Kết quả thu được được trình bày ở biểu đồ dưới. Cột x thể hiện tốc độ truy vấn tính bằng số truy vấn gửi đi mỗi ms, cột y thể hiện phần trăm số query bị loại bỏ do được gửi đến nút bị tắc nghẽn hoàn toàn. Đường đứt thể hiện trường hợp Chord truyền thống, đường liền thể hiện trường hợp sử dụng phương pháp điều khiển tắc nghẽn. Hình 21: Biểu đồ số lượng gói tin bị loại bỏ khi áp dụng và không áp dụng việc điều khiển tắc nghẽn Thông qua biểu đồ trên ta có thể thấy phương pháp điều khiển tắc nghẽn đưa ra có khả năng làm giảm số lượng truy vấn bị loại bỏ qua đó tăng khả năng phục vụ 46 của toàn hệ thống. Tuy nhiên cũng có thể thấy rõ ràng rằng phương pháp đưa ra không có khả năng ngăn chặn việc mạng sụp đổ khi chịu tải quá cao do không có phương pháp điều khiển tắc nghẽn đi kèm. Tiếp đến ta xét tới số lượng trung bình gói tin mà một truy vấn thành công sử dụng nhằm đánh giá mức độ ảnh hưởng của việc sử dụng phương pháp điều khiển tắc nghẽn đã nêu. Hình 22: Biểu đồ thể hiện số gói tin trung bình phải sử dụng với mỗi truy vấn thành công Ở biểu đồ trên cột x ứng với tốc độ truy vấn, cột y thể hiện số gói tin trung bình trên mỗi truy vấn thành công. Ta tính toán giá trị một cách tương đối bằng cách chia tổng số gói tin sử dụng cho số truy vấn thành công. Qua biểu đồ có thể thấy khi tốc độ truy vấn tăng, tương ứng với mức độ tắc nghẽn tăng, số lượng các gói tin điều khiển và gói tin phát sinh thêm khi thay đổi đường định tuyến sẽ tăng. Tuy nhiên mức độ tăng có thể thấy là không quá lớn, chủ yếu là do các gói tin điều khiển. Qua đó có thể thấy mức độ ảnh hưởng khi sử dụng phương pháp là không quá lớn so với phương pháp định tuyến tham lam của Chord truyền thống. 47 5.2.2. Đánh giá hiệu năng khi tiến hành tùy chỉnh các tham số và cải tiến phương pháp Đầu tiên ta xét tới tham số xác định khi nào xảy ra hiện tượng tắc nghẽn “mềm” tính bằng số phần trăm mức chịu tải của từng nút. Hình 23: Ảnh hưởng của việc thay đổi giá trị xác định mức độ tắc nghẽn mềm của nút Ở biểu đồ trục x thể hiện giá trị xác định tắc nghẽn đã để cập bên trên, cột kẻ chéo thể hiện số truy vấn bị loại bỏ do tắc nghẽn, cột đặc thể hiện số gói tin trung bình trên một truy vấn thành công. Hai cột cuối tương ứng với việc không sử dụng việc điều khiển tắc nghẽn. Có thể thấy nếu ta thay đổi giá trị xác định tắc nghẽn lên quá cao sẽ khiến cho nút phản ứng chậm khi bị tắc nghẽn dẫn tới số lượng gói tin bị loại bỏ cao, nếu đặt giá trị này quá thấp làm nút phản ứng quá sớm với việc tắc nghẽn, làm tăng đột biến số lượng gói tin, đặc biệt là gói tin điều khiển, khiến cho tải trên các nút ngày càng cao và sẽ làm cho tình trạng tắc nghẽn trầm trọng hơn. Giá trị phù hợp nhất nằm trong khoảng từ 50% đến 70%. Khi đó ta giảm thiểu được số lượng truy vấn bị loại bỏ mà không làm số lượng gói tin phát sinh thêm tăng cao. Một tham số quan trọng khác đã được nhắc đến ở phần trước là số lượng các nút sẽ được phục hồi lại bảng định tuyến khi nút đích hết tắc nghẽn. Ta tiến hành thay đổi tham số này và quan sát kết quả thu được 48 Hình 24: Ảnh hưởng của số lượng nút được khôi phục bảng định tuyến lên hiệu năng của hệ thống Qua biểu đồ trên có thể thấy số lượng gói tin bị loại bỏ do tắc nghẽn giảm khi ta tiến hành phục hồi chậm trên các nút hết tắc nghẽn. Tuy nhiên cũng phải xét đến ảnh hưởng khi một nút phục hồi quá chậm mà ở đây chương trình mô phỏng chưa thể hiện được. Ta tiếp tục xét đến một hình thức cải tiến của phương pháp đã đưa ra. Trên một nút ta duy trì thêm một giá trị xác định tắc nghẽn thứ hai nhỏ hơn giá trị xác định mức độ tắc nghẽn “mềm” đã có. Khi một nút có lượng truy vấn đến vượt qua giá trị tắc nghẽn thứ hai, nút đó sẽ thực hiện việc gửi yêu cầu thay đổi bảng định tuyến đến các nút ở “xa”, khi nút đạt đến mức tắc nghẽn “mềm” nó sẽ gửi yêu cầu thay đổi bảng định tuyến đến tất cả các nút. Việc xác định một nút xa hay gần được dựa trên ID của các nút đó. Dưới đây là một số kết quả thu được khi áp dụng phương pháp này Hình 25: Hiệu năng của hệ thống thay đổi khi cải tiến phương pháp điều khiển tắc nghẽn. 49 Hai cột đầu tiên mô tả phương pháp ban đầu với mức tắc nghẽn mềm được đặt là 75% khả năng của nút. Hai cột tiếp theo mô tả phương pháp cải tiến với giá trị tắc nghẽn mềm được đặt là 75%, giá trị tắc nghẽn thứ hai được đặt là 50%. Hai cột cuối mô tả phương pháp ban đầu với mức tắc nghẽn mềm được đặt là 50%. Qua biểu đồ có thể thấy khi sử dụng phương pháp cải tiến sẽ cho kết quả tốt hơn thể hiện bằng việc có số lượng truy vấn bị loại bỏ nhỏ nhất, đồng thời không sử dụng thêm quá nhiều các gói tin điều khiển như trường hợp sử dụng phương pháp ban đầu với mức tắc nghẽn mềm là 50%. 50 6. Kết luận và hướng phát triển Luận văn đã đề xuất một phương thức điều khiển tắc nghẽn dựa vào việc điều chỉnh định tuyến trong mạng ngang hàng có cấu trúc. Tuy còn dừng ở mức đơn giản tuy nhiên thông qua thực nghiệm trên chương trình mô phỏng đã chứng tỏ khả năng giải quyết tắc nghẽn cục bộ, qua đó tăng thông lượng đạt được trên mạng. Phương pháp đưa ra vẫn còn một số vấn đề cần phát triển thêm như việc tính toán các thông số phù hợp để đem lại hiệu quả cao nhất. Ngoài ra có thể kết hợp phương pháp đã nêu với một phương pháp điều khiển tắc nghẽn dựa trên điều khiển lưu lượng nhằm giải quyết triệt để vấn đề tắc nghẽn khi mạng chịu tải cao, tránh bị sụp đổ do tắc nghẽn mà vẫn đảm bảo được khả năng phục vụ của toàn mạng. 51 Reference 1. Stephanos Androutsellis-Theotokis and Diomidis Spinellis. “A survey of peer-to-peer content distribution technologies”. ACM Computing Surveys, 36(4):335–371, December 2004. 2. R. Huebsch, B. N. Chun, J. M. Hellerstein, B. T. Loo, P. Maniatis, T. Roscoe, S. Shenker, I. Stoica, and A. R. Yumerefendi. “The architecture of pier: an internet-scale query processor”. In CIDR, pages 28–43, 2005. 3. F. Klemm, Jean-Yves Le Boudec, Dejan Kosti´c, and Karl Aberer, “Handling Very Large Numbers Of Messages In Distributed Hash Tables”, Proceeding COMSNETS'09 Proceedings of the First international conference on COMmunication Systems And NETworks, 2009. 4. F. Klemm, J.-Y. Le Boudec, and K. Aberer. “Congestion control for distributed hash tables”, In The 5th IEEE International Symposium on Network Computing and Applications (IEEE NCA06), 2006. 5. F. Klemm, J.-Y. Le Boudec, D. Kostic, and K. Aberer. “Improving the throughput of distributed hash tables using congestion-aware routing”. In International Workshop on Peer-to-Peer Systems (IPTPS), 2007. Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Lausanne, Switzerland 6. Rüdiger Schollmeier, “A Definition of Peer-to-Peer Networking for the Classification of Peer-to-Peer Architectures and Applications”, Proceedings of the First International Conference on Peer-to-Peer Computing, IEEE (2002). 7. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: “A scalable peer-to-peer lookup service for internet applications”. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols For Computer Communications (San Diego, California, United States). SIGCOMM „01. ACM, New York, NY, 149-160. 2001. 8. C. Tang and S. Dwarkadas. “Hybrid global-local indexing for efficient peer-to-peer information retrieval”. In NSDI, pages 211–224, 2004. 9.