Đề tài: Conservative Synchronization of Large-Scale Network Simulations (Đồng bộ thận trọng trong mô phỏng mạng truyền thông quy mô lớn)

Chia sẻ: Doan Vu Giang | Ngày: | Loại File: DOC | Số trang:23

Thêm vào BST

Báo xấu

90
lượt xem 13
download

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

Đến với nội dung đề tài "Conservative Synchronization of Large-Scale Network Simulations (Đồng bộ thận trọng trong mô phỏng mạng truyền thông quy mô lớn)" để nắm bắt được những nội dung tổng quan về mô phỏng mạng truyền thông, phân tích các mô hình CMB, áp dụng mô hình phân tích null message để dự đoán hiệu suất mô phỏng, phần mềm mô phỏng network simulation,... Mời các bạn cùng tham khảo để nắm bắt nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Đề tài: Conservative Synchronization of Large-Scale Network Simulations (Đồng bộ thận trọng trong mô phỏng mạng truyền thông quy mô lớn)

T R ƯỜ N G Đ Ạ I H Ọ C B Á C H K H O A H À N Ộ I VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG BÀI TẬP LỚN MÔN HỌC CÁC KỸ THUẬT HIỆN ĐẠI TRONG CNTT MÔ PHỎNG HIỆU NĂNG CAO Đề tài: “Conservative Synchronization of LargeScale Network Simulations” (Đồng bộ thận trọng trong mô phỏng mạng truyền thông quy mô lớn) Giảng viên hướng dẫn : TS. Phạm Đăng Hải Học viên thực hiện : Hồ Thị Lợi (CA150114) Đoàn Vũ Giang (CA150108) Nguyễn Thị Thu Huyền (CB140170) Môn học : Chuyên đề 2 Mã học phần : IT6190 Chuyên ngành : Công nghệ thông tin
Conservative Synchronization of LargeScale Network Simulations Hà Nội: 8/2015 2
Conservative Synchronization of LargeScale Network Simulations MỤC LỤC LỜI MỞ ĐẦU .............................................................................................................. 4 1. TỔNG QUAN ............................................................................................................ 5 2. GIỚI THIỆU BÀI BÁO ............................................................................................ 5 3. PHÂN TÍCH CÁC MÔ HÌNH CMB ......................................................................... 6 3.1. Null – message ..................................................................................................... 7 3.2. Thuật toán lazy CMB nullmessage: ................................................................... 8 3.3. Tối ưu hoá thuật toán lazy null – message .......................................................... 9 3.4. Đồng bộ hóa mô phỏng quy mô lớn ................................................................. 11 4. ÁP DỤNG MÔ HÌNH PHÂN TÍCH NULL MESSAGE ĐỂ DỰ ĐOÁN HIỆU SUẤT MÔ PHỎNG ..................................................................................................... 11 4.1. Mô hình đường cơ sở (Baseline) ....................................................................... 11 4.2. Những kịch bản khác nhau cho mô hình baseline ........................................... 12 4.3. Nền tảng phần cứng và phần mềm ................................................................. 13 4.4. Ước lượng Nullmessage .................................................................................. 13 4.5. Ước tính chỉ số Overhead ................................................................................. 14 4.6. Khả năng mở rộng của thuật toán CMB .......................................................... 15 5. PHẦN MỀM MÔ PHỎNG NETWORK SIMULATION (NS) ............................... 16 5.1. Giới thiệu phần mềm mô phỏng NS ............................................................... 16 5.2. Đối tượng được mô phỏng: ............................................................................. 17 5.3. Dùng C++ và Otcl để xây dựng NS: ............................................................... 18 5.4. Cấu trúc cây thư mục NS ................................................................................. 18 5.5. Môi trường làm của NS: ................................................................................... 18 6. KẾT LUẬN .............................................................................................................. 19 LỜI CẢM ƠN ............................................................................................................ 20 3
Conservative Synchronization of LargeScale Network Simulations TÀI LIỆU THAM KHẢO ........................................................................................... 21 LỜI MỞ ĐẦU Mô phỏng tin học (Computer simulation) là các chương trình máy tính, mạng máy tính để mô phỏng một mô hình trừu tượng của một hệ thống cụ thể thông qua các hiện tượng, các sự kiện trong thực tế hoặc số liệu đã có như các điều kiện thời tiết, các phản ứng hoá học, các quá trình sinh học và các số liệu kinh tế…. Quy mô của sự kiện được mô phỏng bằng mô phỏng tin học đã vượt xa bất cứ điều gì có thể (hoặc thậm chí có thể tưởng tượng) so với cách sử dụng mô hình toán học truyền thống giấy và bút. Đã có rất nhiều những bài báo, những cuộc hội thảo lớn trao đổi, nghiên cứu về mô phỏng song song và phân tán như Parallel and Distributed Simulation, Winter Simulation Conference, Computer Simulation Methods and Applications,… Các tác giả Alfred Park, Kalyan S. Perumalla và đặc biệt là Richard M. Fujimoto là những nhân tố tích cực, đóng góp rất nhiều kết quả nghiên cứu trong lĩnh vực này. Trong đó có bài báo “Conservative Synchronization of LargeScale Network Simulations” (Đồng bộ thận trọng trong mô phỏng mạng truyền thông quy mô lớn) được in trong Kỷ yếu của Hội thảo lần thứ 18 về mô phỏng song song và phân tán (PADS'04), tạp chí IEEE năm 2004. Trong phạm vi bài tập lớn môn học, tiểu luận sẽ trình bày các nội dung được đề cập đến trong bài báo, trên cơ sở của chuyên đề về các thuật toán mô phỏng song song thận trọng. 4
Conservative Synchronization of LargeScale Network Simulations 1. TỔNG QUAN Kỹ thuật mô phỏng song song theo sự kiện rời rạc hiện nay đã cho phép ứng dụng với các mô hình mạng truyền thông quy mô lớn (chứa tới hàng triệu thiết bị đầu cuối và thiết bị chuyển mạch). Tuy nhiên, hiệu suất mô phỏng song song có thể bị giảm xuống đáng kể nếu không sử dụng những thuật toán đồng bộ thích hợp. Nội dung bài báo đã đưa ra những nét so sánh về hiệu suất và khả năng mở rộng của 2 thuật toán synchronous (đồng bộ) và asynchronous (không đồng bộ) trong mô phỏng mạng song song thận trọng. Nhóm nghiên cứu cũng phát triển một mô hình phân tích để đánh giá hiệu quả và tính khả mở của các tham số xác định trong một thuật toán khá nổi tiếng có tên là Nullmessage. Bài báo cũng chỉ rõ rằng dữ liệu thực nghiệm đã chứng minh tính chính xác của mô hình này. Việc phân tích và đo lường trên hệ thống song song với hàng trăm bộ vi xử lý cho thấy rằng đối với các kịch bản mô phỏng mô hình mạng thu nhỏ có số lượng kênh vào / ra xác định thì thuật toán nullmessage có khả năng mở rộng tốt hơn khả năng giảm số lượng tính toán giá trị toàn cục tối thiểu (global reduction) dựa trên các giao thức đồng bộ. 2. GIỚI THIỆU BÀI BÁO Mô phỏng song song ngầm định sự thực hiện chỉ một chương trình mô phỏng trên một tập các processors kết nối chặt chẽ (máy tính song song). Các tiến trình logic (LPs) trong mô phỏng song song bởi các thuật toán thận trọng sẽ luôn đảm bảo được nguyên tắc causality, điều đó có nghĩa là các message nhận được bởi tiến trình này được xử lý theo trật tự không giảm của nhãn thời gian. Tuy nhiên, không có gì đảm bảo rằng các đồng hồ cục bộ trong các tiến trình khác nhau đã “đồng giờ” với nhau. Vì vậy, đồng bộ hóa trong mô phỏng cũng là đề tài được đề cập đến trong nhiều nghiên cứu trước đây. Các thuật toán thận trọng được chia thành 2 loại, đó là đồng bộ và không đồng bộ. Các thuật toán không đồng bộ không yêu cầu đồng bộ hóa giá trị GVT (global vitua time). Thuật toán nullmessage (được phát triển từ thuật toán gốc ChandyMisraBryant) đã giải quyết được vấn đề hủy bỏ bế tắc là một ví dụ điển hình về thuật toán không đồng bộ. Bên cạnh đó, các thuật toán đồng bộ hóa sử 5
Conservative Synchronization of LargeScale Network Simulations dụng tính toán global redution để tìm ra biên độ thời gian tối thiểu (Lower Bound on Timestamp LBTS) của các thông điệp có thể được nhận bởi mỗi LP trong tương lai, điều đó giúp xác định rằng khi nào các sự kiện được an toàn để xử lý (ví dụ giao thức YAWNS). Một số thuật toán khác lại sử dụng các kỹ thuật phát hiện bế tắc và phục hồi (deadlock detection and recovery) hay kỹ thuật cửa sổ thời gian (simulation time windows). Mặc dù trước đây đã có nhiều nghiên cứu đánh giá hiệu suất của các thuật toán đồng bộ hoá thận trọng, nhưng hầu hết các nghiên cứu này đều mô phỏng trên quy mô nhỏ (ít hơn 100 bộ vi xử lý). Do vậy, kết luận dựa trên nghiên cứu mô phỏng đó không áp dụng đối với một kịch bản quy mô lớn. Trong bài báo này nhóm nghiên cứu đã giải quyết những vấn đề liên quan trong việc so sánh một thuật toán không đồng bộ CMB nullmessage với thuật toán đồng bộ barier trong mô phỏng mạng truyền thông quy mô lớn. Bài báo cũng đề cập đến thuật toán lazy nullmessage (trình bày trong phần 3). Phần 4 mô tả các kịch bản mô phỏng được sử dụng cho các nghiên cứu thực nghiệm, và trình bày so sánh giữa dự đoán mô hình phân tích và đo lường. Phần 5 trình bày các dữ liệu thực nghiệm được so sánh hiệu suất của thuật toán CMB và thuật toán global reduction. 3. PHÂN TÍCH CÁC MÔ HÌNH CMB Thuật toán CMB (Chandy – Misra – Briant) xây dựng dựa trên các giả thiết về tiến trình logic: Các LPs sử dụng một kênh vào riêng cho từng LP khác có trao đổi với nó. Mỗi kênh vào là FIFO, có một đồng hồ thời gian mà giá trị tương ứng với nhãn thời gian của: thông điệp ở đầu kênh vào (nếu có) hoặc thông điệp cuối cùng nhận được (nếu hàng đợi rỗng) LPs trao đổi các thông điệp có nhãn thời gian. Cấu hình mạng tĩnh, không tạo các LPs động. Các message được gửi trên mỗi link theo trật tự thời gian. Đường truyền là tin cậy, các thông điệp đến theo đúng thứ tự được gửi. Thuật toán với mục đích đảm bảo xử lý các sự kiện trong mỗi LP theo trật tự thời gian, tại mỗi tiến trình sẽ thực hiện như sau: 6
Conservative Synchronization of LargeScale Network Simulations WHILE (mô phỏng chưa kết thúc) { Đợi cho tới khi mỗi hàng đợi FIFO chứa ít nhất một msg Lấy sự kiện có nhãn thời gian nhỏ nhất ra khỏ hàng đợi Xử lý sự kiện này } ENDLOOP Thuật toán có thể dễ dàng cho thấy không vi phạm ràng buộc causality, các message sẽ luôn được xử lý đúng theo trật tự thời gian, tuy nhiên lại rất dễ rơi vào bế tắc khi mà trong một chu trình, mỗi tiến trình đều ở trong trạng thái đang chờ đợi một message từ tiến trình khác. Để giải quyết vấn đề thuật toán null – message được sử dụng. 3.1. Null – message Trước hết, có thể hiểu null – messge là một message chỉ chứa nhãn thời gian và mục tiêu khi sử dụng chính là gỡ sự bế tắc khi thực hiện thuật toán thận trọng cơ bản CMB bằng cách lan truyền thời gian nhân tạo. Cơ chế sử dụng null – message rất đơn giản: mỗi LP sẽ gửi một null message để chỉ ra nhãn thời gian thấp nhất của một messages mà nó sẽ gửi trong tương lai Thuật toán CMB cải tiến với null – message: WHILE (mô phỏng chưa kết thúc) { Đợi cho tới khi mỗi hàng đợi FIFO chứa ít nhất một msg Lấy sự kiện có nhãn thời gian nhỏ nhất ra khỏ hàng đợi Xử lý sự kiện này (null message không xử lý, chỉ gửi tiếp) Gửi tới những LPs lân cận các null messages mang nhãn thời gian thấp nhât của của một message sẽ được LP này gửi đến trong tương lai (Giá trị thời gian hiện thời cộng với giá trị lookahead) } ENDLOOP 7
Conservative Synchronization of LargeScale Network Simulations Có thể thấy ngay thuật toán nullmessage đã tháo gỡ thế bế tắc của thuật toán CMB, tuy nhiên thuật toán này lại phục thuộc vào giá trị lookahead và từ việc phục thuộc này sẽ phát sinh thêm nhiều vấn đề phải giải quyết như: giá trị lookahead = 0, giá trị lookahead quá nhỏ hay mức độ rẽ nhánh mạng quá lớn dẫn đến phát sinh quá nhiều null – message , điều đó cũng đồng nghĩa với việc hệ thống phải xử lý quá nhiều nullmessage, hiệu suất hệ thống mô phỏng không cao. Vậy phải làm như thế nào để dự đoán được giá trị lookahead phù hợp, một số thuật toán bổ sung khắc phục nhược điểm của nullmessage được ra đời. 3.2. Thuật toán lazy CMB nullmessage: Một phiên bản mới của thuật toán CMB lazy CMB được ra đời, lazy CMB nullmessage sẽ hạn chế số lượng null message gửi đi trong hệ thống bằng cách chỉ gửi chúng khi cần thiết. Cụ thể, các null message chỉ gửi khi LP đạt đến cuối thời gian xử lý an toàn của nó, tức là chỉ khi LP bị chặn. Trong trường hợp này, nếu không gửi null message thì hệ thống có thể dẫn đến bế tắc. Thuật toán lazy CMB nullmessage sẽ: • Đợi một thời gian trước khi gửi nullmessage • Chỉ gửi message khi cần thiết – Khi đã xử lý tất cả các msg an toàn, gửi nullmessage và chờ đợi – Khi nhận được nullmessage, sẽ tính được cận dưới nhãn thời gian của message tiếp. Hình 1: Runtimes của thuật toán Lazy CMB Hình 1 cho thấy quá trình mô phỏng sử dụng thuật toán Lazy CMB (giả sử các LP có cùng lookahead) với các giá trị "LBTS" như trên thì lazy null message thực 8
Conservative Synchronization of LargeScale Network Simulations hiện tương tự như của mô phỏng thời gian bước. Với một số lượng tối thiểu của các null message trao đổi giữa các LP, sơ đồ này tương tự như là mô phỏng đồng bộ. Người ta có thể tính toán số lượng null message Nɸ được gửi đi như sau: (1) Trong đó m là số lượng LP, n là số lượng các kênh đầu ra mỗi LP, và s là chiều dài của thời gian chạy trong mô phỏng. Số lượng các cửa sổ thực hiện (s được chia bởi lookahead), cho biết số vòng quay hoặc thời gian bước cho những null message được gửi đi. Vd với: m = 8, n = 2, s = 25, và lookahead = 0,2 giây. Bằng công thức 1, tổng số null message sẽ là 2.000. Khái quát hoá, chúng ta có thể tính toán gần đúng số lượng tin nhắn đồng bộ hóa (Nψ) khi thay đổi số lượng đầu vào bằng phương trình (giả sử m là một bội số của 2): (2) 3.3. Tối ưu hoá thuật toán lazy null – message Để tối ưu hoá thuật toán lazy nullmessage có thể sử dụng các phương pháp sau: Gửi nullmessage theo chu kỳ: mỗi LP sẽ gửi nullmessage mỗi f đơn vị thời gian trước khi mô phỏng (trong đó giá trị f nhỏ hơn giá trị lookahead của các LP, giả thiết rằng các LP có cùng lookahead). Với cách tăng tần suất gửi null message tới các LP kế cận sẽ tránh được tình trạng bế tắc của hệ thống. Loại bỏ bớt các nullmessage có cùng nhãn thời gian: Giả sử 1 LP vừa gửi đi 1 nullmessage có nhãn thời gian t, thì ngay sau đó nó không cần thiết phải gửi đi thêm 1 nullmessage nào khác có cùng nhãn thời gian t như vậy nữa (các nullmessage có cùng nhãn thời gian chỉ cần được gửi đi 1 lần từ 1 LP). Từ 2 biện pháp tối ưu trên, phương trình 1 có thể được sửa đổi như sau: 9
Conservative Synchronization of LargeScale Network Simulations (3) Trong đó c là tỷ lệ nullmessage bị hủy bỏ và f là tần suất các nullmessage được gửi đi. Ở đây, giá trị f được sử dụng ở vị trí của giá trị lookahead trong phương trình 1. Bây giờ chúng ta chuyển sang các trường hợp tổng quát hơn của lookahead không đồng đều trên các kênh đầu ra. Nó rất hữu ích để xây dựng một mô hình phân tích mà các mô hình mô phỏng là không thường xuyên. Ở đây, chúng ta giả định một giá trị lookahead được gán cho mỗi liên kết. Trong trường hợp của các giá trị lookahead là khác nhau trên mỗi LP, công thức 3 có thể được sửa đổi thành phương trình: (4) Phương trình 14 với các giá trị lookahead và tần suất gửi null message cho phép ước lượng được số null message sẽ gửi đi trong suốt quá trình mô phỏng. Tính toán được số lượng null message là rất quan trọng vì nó là một yếu tố quan trọng để tính toán giá trị overhead trong thuật toán null message. Phương trình 5 tính toán chỉ số overhead trong thuật toán lazy null messge. Ở đây a là số lượng kết nối từ xa, p là tỷ lệ phần trăm và w là số lượng từng loại kết nối cụ thể. Số lượng w này là yếu tố thông thường truyền thông. Ví dụ, nếu chúng ta có kết nối trên cả bộ nhớ dùng chung (w 1) và Ethernet (w2), có thể là w1 = 1 và w2 = 10. Bằng cách sử dụng những phương trình này, chúng ta không chỉ tính toán được số lượng null message được gửi qua tất cả LP, mà còn tính được giá trị overhead của thuật toán null message với từng kịch bản mô phỏng. Điều này rất hữu ích trong việc dự báo hiệu suất của một kịch bản baseline mới (ví dụ như các thí nghiệm nhỏ). 10
Conservative Synchronization of LargeScale Network Simulations 3.4. Đồng bộ hóa mô phỏng quy mô lớn Lưu ý rằng phương trình (1) và phương trình (2) ở trên chỉ khác nhau ở hệ số n trong (1) được thay bằng log2m trong (2). Đối với thuật toán quản lý thời gian đồng bộ, số lượng tin nhắn đồng bộ hóa tăng tỉ lệ thuận với mlog 2m, so với tỉ lệ của m trong thuật toán CMB. Hơn nữa, giá trị này không bao gồm thời gian ngắt và khởi động lại đồng thời toàn bộ các LP trong hệ thống (thời gian này sẽ tăng tuyến tính khi số lượng LP tăng), góp phần tăng giá trị overhead quản lý thời gian đối với mỗi phép tính LBTS. Vấn đề này sẽ được thảo luận thêm với kết quả hiệu suất trong phần 4.5 4. ÁP DỤNG MÔ HÌNH PHÂN TÍCH NULL MESSAGE ĐỂ DỰ ĐOÁN HIỆU SUẤT MÔ PHỎNG Các mô hình phân tích trên đây cho phép dự báo hoạt động của nullmessage và giá trị overhead. Những chỉ số này có thể được sử dụng để dự báo hiệu suất của các mô hình mô phỏng khác nhau. Đầu tiên chúng ta sẽ ước tính hoạt động của nullmessage và giá trị overhead trên hệ thống mô phỏng, sau đó so sánh với các chỉ số đo đạc thực nghiệm. Các phần sau đây liên quan đến kết quả thực nghiệm (mỗi LP tương ứng với một CPU vật lý). 4.1. Mô hình đường cơ sở (Baseline) Nhóm nghiên cứu đã sử dụng các tiêu chuẩn được phát triển tại Đại học Dartmouth như một tập hợp các mô hình baseline để mô hình hóa và mô phỏng mạng cộng đồng [22]. Cấu hình baseline này được tạo ra để chứng minh khả năng mở rộng mạng mô phỏng. Mỗi phần của mạng được gọi là một Campus Network (CN). Hình 4 cho thấy các cấu trúc liên kết cho CN. Mỗi CN bao gồm 4 máy chủ, 30 thiết bị định tuyến, và 504 máy chủ (tổng số là 538 nút). Mỗi CN bao gồm 4 mạng con (subnetwork) riêng biệt. Net 0 bao gồm 3 thiết bị định tuyến, có nút 0:0 là router gateway cho CN. Net 1 gồm 2 router và 4 máy chủ. Net 2 gồm 7 tuyến, 7 router LAN, và 294 khách hàng. Net 3 chứa 4 bộ định tuyến, 5 thiết bị định tuyến mạng LAN, và 210 khách hàng. 11
Conservative Synchronization of LargeScale Network Simulations To other CNs 0:2 1:0 1:2 1:3 0:0 0:1 Net 0 1:4 1:1 4 5 1:5 Net 1 2:0 2:1 3:0 3:1 2:2 2:3 2:4 2:5 3:2 3:3 2:6 Net 2 Net 3 Hình 4: Campus Network Tất cả các liên kết máy chủ không phải điểm cuối (nonend host) đều có băng thông là 2Gb/s và độ trễ truyền thông (delay) dưới 5ms (riêng truyền thông giữa Net 0 đến Net 1 có delay là 1ms). Host cuối được kết nối pointtopoint với router mạng LAN tương ứng có băng thông 100MB/s và delay là 1ms. Nhiều CN có thể được kết nối với nhau để tạo thành một cấu trúc liên kết vòng. Chính tính chất này của mạng cho phép các mô hình cơ sở để dễ dàng thay đổi kích thước (thu nhỏ hay mở rộng quy mô). 4.2. Những kịch bản khác nhau cho mô hình baseline Nhóm nghiên cứu đã đưa ra 5 kịch bản với 5 cấu hình tương phản. Việc lựa chọn máy chủ ngẫu nhiên, thay đổi độ trễ lan truyền trên mạng liên kết vòng và thay đổi các cụm liên kết sẽ tạo ra các kịch bản sử dụng trong nghiên cứu này. Kịch bản Lưu lượng Chord? Đặc tính khác Baseline Std. No None BaselineR Rand. No None Baseline2ms Rand. No Single 2ms ring link ChordR Rand. Yes None ChordAsym Rand. Yes Asym. Chord delays Bảng 1. Benchmark Scenarios 12
Conservative Synchronization of LargeScale Network Simulations 4.3. Nền tảng phần cứng và phần mềm Phần mềm mô phỏng song song / phân tán (PDNS) là phần mềm mô phỏng mạng trên nền tảng HLA RTI (High Level Architecture & using RunTime Infrastructure based). Các PDNS được nhắc đến trong nghiên cứu này gồm có: NS2, libSynk,.. NS2 (Network Simulator 2): là phần mềm mã nguồn mở mô phỏng mạng điều khiển sự kiện riêng rẽ hướng đối tượng, được phát triển tại UC Berkely, viết bằng ngôn ngữ C++ và Otcl chạy trên nền Windows 32 và Linux. NS rất hữu ích cho việc mô phỏng mạng diện rộng (WAN) và mạng local (LAN). Bốn lợi ích lớn nhất của NS2 phải kể đến là: Khả năng kiểm tra tính ổn định của các giao thức mạng đang tồn tại; Khả năng đánh giá các giao thức mạng mới trước khi đưa vào sử dụng; Khả năng thực thi những mô hình mạng lớn mà gần như ta không thể thực thi được trong thực tế; Khả năng mô phỏng nhiều loại mạng khác nhau. libSynk: là thư viện quản lý các kết nối và thời gian. libSynk được sử dụng để quản lý các tình huống trong mô phỏng song song và phân tán, nó cũng được sử dụng để phân chia bộ nhớ giữa các kết nối SMP và TCP/IP để truyền thông qua SMPS. 4.4. Ước lượng Nullmessage Sử dụng các mô hình phân tích cho thuật toán CMB có thể được ước tính được số lượng Nullmessage sẽ gửi đi trong hệ thống. Bảng 2 cho thấy số liệu ước tính cùng với số liệu đo đạc thực hiện trên các kịch bản baseline mô phỏng song song. Trong kịch bản này có s = 25; lookahead = 0,2; f = ( 0,2/3 ); n = 2; c = 0,5 . Số lượng Nullmessage ước lượng Nullmessage đo đạc CPUs 4 1,500 1,424 8 3,000 2,974 16 6,000 6,064 32 12,000 11,890 13
Conservative Synchronization of LargeScale Network Simulations 64 24,000 23,586 128 48,000 48,628 256 96,000 96,034 512 192,000 193,862 Bảng 2. Ước lượng số lượng Null message Số liệu trên Bảng 2 cho thấy rằng mô hình phân tích của nhóm nghiên cứu dự đoán khá chính xác số lượng nullmessage. Sự chênh lệch số liệu giữa ước lượng và số liệu mô phỏng phụ thuộc vào tỉ lệ giữa số lượng nullmessage được gửi đi và số lượng nullmessage bị hủy bỏ. Gần như không thể dự đoán chính xác được tỉ lệ này, nhưng số liệu ước lượng cũng đã khá gần với số liệu thực tế đo đạc được từ việc mô phỏng. 4.5. Ước tính chỉ số Overhead Từ các kết quả ước tính số lượng nullmessage được gửi đi như trên, cùng với phương trình 3 đã được thiết lập trong mục 3.3, chúng ta có thể để ước tính giá trị overhead cho mỗi kịch bản mô phỏng. Nhóm nghiên cứu cũng đã đưa ra một khái niệm mới “Packet Transmissions per Second of wallclock time” (PTS): là số lượng gói tin được xử lý trong 1 giây của wallclock hay số lượng gói tin được truyền đi từ nút này tới nút khác trong hệ thống mạng. Giá trị overhead và PTS trong trường hợp mô phỏng với 32 CPU được thể hiện trong Bảng 3. Số liệu thống kê cũng cho biết rằng 28 CPU (87,5%) đã gửi tin nullmessage thông qua bộ đệm bộ nhớ dùng chung và 4 CPU còn lại (12,5%) giao tiếp thông qua giao thức TCP / IP trên Ethernet. Sử dụng các giá trị m = 32, p1 = 0,875, p 2 = 0,125, W1 = 1, và w2 = 10, chỉ số overhead cho kịch bản cơ bản là 6,25. Kịch bản Chỉ số Overhead PTS Baseline 6.25 1,512,410 BaselineR 8.52 865,385 Baseline2ms 10.54 621,008 ChordR 9.43 699,848 14
Conservative Synchronization of LargeScale Network Simulations ChordAsym 12.21 684,630 Bảng 3. Ước lượng chỉ số Overhead 4.6. Khả năng mở rộng của thuật toán CMB Trong phần 3.3, chúng tôi đã chỉ ra rằng, thuật toán Nullmessage tương đối ổn định khi tăng kích thước mô hình mô phỏng. Chúng tôi cũng đã chứng minh bằng thực nghiệm với cùng kịch bản Baseline (đường cơ sở). Nhưng với các kịch bản khác, hiệu quả của thuật toán nullmessages phụ thuộc rất nhiều vào khả năng dự báo giá trị lookahead. Số lượng CPUs Null Messages Reductions 16 784 736 32 783 747 128 787 892 Bảng 4. Mô phỏng cho kịch bản Baseline Thời gian mô phỏng của thuật toán CMB gần như không đổi khi mô phỏng với quy mô từ 16128 VXL (xem Bảng 4), trong khi đó thời gian toàn cục (global redutions) lại đều đặn tăng theo số lượng CPU (từ 16 đến 128 CPU). Hình 5 cho thấy sự thay đổi của 2 giao thức đồng bộ với kịch bản Baseline Số lượng CPUs Null Messages Reductions 64 420 508 128 414 523 256 420 563 512 436 620 Bảng 5. Mô phỏng mô hình lớn với kịch bản Baseline Đây là kết quả mô phỏng trên máy Compaq Alpha Tru64 cluster. Giá trị PTS tương ứng được thể hiện trong hình 6. Kịch bản baseline sử dụng giá trị global reductions tăng theo hàm mũ tương ứng với quy mô mô phỏng. Ngược lại, thuật toán nullmessage lại tương đối ổn định trong thời gian chạy hiệu suất lên đến 512 CPU. 15
Conservative Synchronization of LargeScale Network Simulations Hình 5. Đánh giá PTS theo quy mô mô phỏng Hình 6. PTS trong mô hình lớn 5. PHẦN MỀM MÔ PHỎNG NETWORK SIMULATION (NS) 5.1. Giới thiệu phần mềm mô phỏng NS NS (Network Simulation) chương trình phần mềm dạng hướng đối tượng được sử dụng để mô phỏng lại các sự kiện xảy ra trong hệ thống mạng. NS được sử dụng để mô phỏng LAN và WAN, thực thi mô phỏng mạng lớn và nhiều loại mạng khác nhau Hệ mô phỏng NS2 được phát triển ở trường đại học Berkeylay từ năm 1989, là một phần trong dự án VINT (Virtual Internet Testbed) của phòng thí nghiệm quốc gia Lawrence Berkeley 16
Conservative Synchronization of LargeScale Network Simulations Hình ảnh: Tổng quan về NS dưới góc độ người dùng OTcl Script Kịch bản OTcl Simulation Program Chương trình Mô phòng OTcl Bộ biên dịch Tcl mở rộng hướng đối tượng NS Simulation Library Thư viện Mô phỏng NS Event Scheduler Objects Các đối tượng Bộ lập lịch Sự kiện Network Component Objects Các đối tượng Thành phần Mạng Network Setup Helping Modules Các mô đun Trợ giúp Thiết lập Mạng Plumbling Modules Các mô đun Plumbling Simulation Results Các kết quả Mô phỏng Analysis Phân tích NAM Network Animator Minh họa Mạng NAM 5.2. Đối tượng được mô phỏng: Wired, Wireless, Satellite TCP Agents, UDP Agents, multicast, unicast Thiết kế các cơ chế quản lý hàng đợi tại bộ định tuyến như DropTail, Fair Queueing, Red. Cài đặt thuật toán định đường động và tĩnh, Dijkstra, vector khoảng cách, thuật toán trạng thái liên kết, 17
Conservative Synchronization of LargeScale Network Simulations Hỗ trợ các ứng dụng WebCache, FTP, Telnet, CBR, Web, Real Audio. 5.3. Dùng C++ và Otcl để xây dựng NS: Hệ mô phỏng NS được viết trên C++ và Otcl, C++ dùng để xử lý dữ liệu, các thao tác về gói tin và Otcl được sử dụng để định dạng cấu hình mô phỏng, điều khiển mô phỏng. Đây là lí do để hệ mô phỏng NS đạt hiệu quả. Để giảm bớt thời gian xử lý gói tin và những sự kiện trong mô phỏng, tất cả đều được thực hiện trên C++. 5.4. Cấu trúc cây thư mục NS 5.5. Môi trường làm của NS: Để thực hiện mô phỏng một mô hình mạng trước hết ta phải khởi tạo các đối tượng, các liên kết, các Agent, các dịch vụ truyền tin... trên môi trường NS, và điều này khá đơn giản vì NS đã hỗ trợ cách khởi tạo ra các đối tượng này. Sau khi khởi tạo các đối tượng như nút(node), liên kết(link), các Agent, các dịch vụ truyền tin... thì đoạn mã lệnh tương ứng sẽ được phát sinh. Cấu trúc câu lệnh của NS cũng khá đơn giản chúng ta cũng có thể sử dụng nó để tạo ra một mô hình theo ý muốn. 18
Conservative Synchronization of LargeScale Network Simulations Sau khi thực hiện mô phỏng mô hình mạng trên NS, trình biên dịch sẽ dịch chương trình chúng ta đã mô phỏng, kết quả được lưu dưới dạng file NAM. NAM có một giao diện dễ sử dụng (có các nút điều khiển chương trình như: Play, Stop, FastForward, Rewind, Pause... ), chúng ta có thể thực hiện chương trình đã biên dịch dưới dạng file NAM trong môi trường NAM một cách dễ dàng. Trên màn hình luôn luôn hiển thị thời gian thực hiện chương trình, tốc độ truyền gói tin. Ngoài ra nó còn có màn hình quan sát lưu lượng gói tin truyền đi và số lượng gói tin rời khỏi đường truyền khi có độ trì hoãn cao hay nghẽn mạch xảy ra trên mạng. 6. KẾT LUẬN Bài báo trình bày một mô hình phân tích cho thuật toán lazy null message không đồng bộ để quản lý thời gian. Các phương trình được đề xuất trong bài báo có thể được sử dụng để tính toán số lượng nullmessage và giá trị overhead tương ứng. Cụ thể, chỉ số overhead cho phép dự đoán được việc tối ưu hóa thuật toán nullmessage, giá trị overhead hầu như tăng lên không đáng kể nếu như đầu vào/ra của các kênh ổn định (như mô phỏng với quy mô nhỏ). Thuật toán nullmessage cũng rất linh động cho các mô hình mạng biến động và không đối xứng. Thuật toán tối ưu hóa CMB có thể đồng bộ hóa các message theo giá trị lookahead gửi tới các kết nối cục bộ. Các tính chất này chứng minh được lợi thế trong mô phỏng mạng quy mô lớn của thuật toán CMB. 19
Conservative Synchronization of LargeScale Network Simulations LỜI CẢM ƠN Môn học các kỹ thuật hiện đại trong CNTT với chuyên đề Mô phỏng hiệu năng cao đã mang đến cho chúng em những kiến thức mới các phương pháp mô phỏng, đặc biệt là mô phỏng tin học hiệu năng cao. Qua quá trình thực hiện tiểu luận, phần nào chúng em cũng được hiểu thêm về các thuật toán thận trọng trong mô phỏng song song. Tuy nhiên, do chủ đề khá mới mẻ và kiến thức còn hạn chế nên tiểu luận của chúng em mới chỉ dừng lại ở mức tìm hiểu và thử nghiệm một vài ví dụ nhỏ trên phần mềm mô phỏng. Chúng em xin chân thành gửi tới Thầy, TS. Phạm Đăng Hải lời cảm ơn sâu sắc. Thầy đã tận tình giảng dạy và cung cấp cho chúng em những kiến thức và tài liệu cần thiết để chúng em hoàn thành tiểu luận này. 20