Đề tài Thuật toán điều khiển tắc nghẽn wlda+

Trang 1 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Hồng Đoàn THUẬT TOÁN ĐIỀU KHIỂN TẮC NGHẼN WLDA+ Ngành: Công nghệ thông tin Chuyên ngành: Mạng và truyền thông Mã số: 1.01.10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS, TS. Nguyễn Đình Việt Hà nội – 2007 Lời cảm ơn Trang 2 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 Mục lục Bảng thuật ngữ viết tắt .................... Error! Bookmark not defined. Danh mục các hình vẽ ...................... Error! Bookmark not defined. Mở đầu ............................................................................................ 4 Chương 1 Giới thiệu ...................................................................... 7 I. Internet và các mô hình tham chiếu ............................................................................. 7 1. Lịch sử phát triển mạng Internet và bộ giao thức TCP/IP ................................. 7 2. Các mô hình tham chiếu .................................................................................... 8 II. Một số giao thức phổ biến ......................................... Error! Bookmark not defined. 1. Giao thức TCP ................................................. Error! Bookmark not defined. 2. Giao thức UDP: ................................................ Error! Bookmark not defined. 3. Giao thức RTP ................................................. Error! Bookmark not defined. Chương 2 Cơ chế điều khiển lưu lượngError! Bookmark not defined. I. Phát hiện lỗi và điều khiển khắc phục lỗi ................... Error! Bookmark not defined. 1.Tổng quan ......................................................... Error! Bookmark not defined. 2. Cơ chế bảo vệ, phát hiện và khắc phục lỗi....... Error! Bookmark not defined. II. Điều khiển lưu lượng, tránh tắc nghẽn ...................... Error! Bookmark not defined. 1. Cơ chế điều khiển lưu lượng ............................ Error! Bookmark not defined. 2. Thuật toán điều khiển lưu lượng ...................... Error! Bookmark not defined. 3. Điều khiển tắc nghẽn trong mạng hỗn hợp có dây và không dây .............Error! Bookmark not defined. 4. Kỹ thuật TCP-friendly ..................................... Error! Bookmark not defined. 5. Lược đồ WLDA+ ............................................. Error! Bookmark not defined. Chương 3 Đánh giá hiệu suất giao thức và việc đảm bảo QoS cho truyền thông đa phương tiện ... Error! Bookmark not defined. I. Các phương pháp đánh giá hiệu suất giao thức .......... Error! Bookmark not defined. 1. Giới thiệu chung............................................... Error! Bookmark not defined. 2. Đánh giá hiệu suất bằng mô hình toán học ...... Error! Bookmark not defined. 3. Đánh giá hiệu suất bằng đo thực tế .................. Error! Bookmark not defined. 4. Đánh giá hiệu suất bằng mô phỏng .................. Error! Bookmark not defined. II. Truyền thông Multimedia và vấn đề đảm bảo QoS .. Error! Bookmark not defined. 1.Truyền thông đa phương tiện ............................ Error! Bookmark not defined. 2. Một số mô hình QoS: ....................................... Error! Bookmark not defined. III. Một số kỹ thuật xử lý hàng đợi ................................ Error! Bookmark not defined. Chương 4: Đánh giá hiệu suất WLDA+ bằng mô phỏngError! Bookmark not defined. I. Cơ bản về NS .............................................................. Error! Bookmark not defined. II. Mô phỏng thuật toán WLDA+ bằng NS ................... Error! Bookmark not defined. 1. Cấu hình mô phỏng WLDA+ ........................... Error! Bookmark not defined. 2. Đánh giá độ chính xác của các lược đồ lỗi. ..... Error! Bookmark not defined. 3. Đánh giá hiệu suất của các kỹ thuật. ................ Error! Bookmark not defined. Trang 3 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 4. Đánh giá ảnh hưởng của những tỷ lệ lỗi khác nhau trong mạng không dây: .............................................................................. Error! Bookmark not defined. 5. Tính khả triển của WLDA+ ............................. Error! Bookmark not defined. Kết luận và phương hướng nghiên cứuError! Bookmark not defined. Kết luận .......................................................................... Error! Bookmark not defined. Phương hướng nghiên cứu ............................................. Error! Bookmark not defined. Tài liệu tham khảo ....................................................................... 11 Trang 4 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 Mở đầu Các giao thức truyền thông chủ yếu trên Internet được áp dụng ngày nay vẫn là các giao thức truyền thống như TCP, UDP, IPNhững giao thức này vẫn đang đáp ứng được yêu cầu thực tế ở một mức độ nhất định. Ứng dụng phổ biến chạy trên giao thức TCP là File Tranfer Protocol, World Wide Web, Telnet, HyperText Tranfer Protocol, Simple Mail Tranfer Protocol v.v. Một số ứng dụng đặc biệt như truyền thông Multimedia, hội thảo truyền hình trực tuyến, Telephony, xem phim qua mạng thì triển khai trên giao thức UDP. Tuy nhiên, hiệu suất các ứng dụng này cũng chưa có được kết quả như mong đợi, nhất là trong môi trường mạng hỗn hợp giữa mạng có dây và mạng không dây đang dần trở nên phổ biến. Trong môi trường hỗn hợp, cơ chế điều khiển luồng, điều khiển tắc nghẽn truyền thống của TCP khó phát huy hết tác dụng do tình trạng mất dữ liệu, độ trễ các gói tin tăng đột biến không hẳn là dấu hiệu của tình trạng tắc nghẽn mạng mà còn có thể là do nguyên nhân đường truyền không dây có tỷ lệ lỗi bit cao, việc triển khai QoS vẫn chưa rộng rãi. Ngoài ra, với TCP là một giao thức không hỗ trợ truyền Multicast nên khi truyền tin theo nhóm hay Multicast thì vấn đề quản lý các phiên làm việc đan xen sẽ rất phức tạp. Giao thức UDP trong các ứng dụng multimedia thì không có cơ chế phát lại các gói tin dẫn đến không đảm bảo toàn vẹn dữ liệu, không đảm bảo tính công bằng về đường truyền cho các giao thức khác khi cùng tham gia truyền tin trên một tuyến đường mạng, có thể dẫn đến tình trạng các luồng thông tin chạy trên các giao thức khác mất dần cơ hội truyền cho đến lúc thông lượng trở về 0. Vậy nên giải pháp cho mạng Internet ngày nay có xu hướng là: một mặt vẫn tiếp tục nghiên cứu chính sách ưu tiên dịch vụ, đảm bảo chất lượng và Trang 5 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 triển khai các chính sách này trên các thiết bị mạng mới. Những thiết bị mạng mới đó vẫn tương thích với các giao thức, thiết bị cũ đang còn tồn tại. Sau đó, sẽ thay thế dần các thiết bị cũ trên đường truyền Internet bằng các thiết bị mới hơn, có các kỹ thuật quản lý QoS tốt hơn và tính mở rộng cao hơn để có được một mạng Internet chất lượng cao. Mặt khác, cải tiến giao thức với kỹ thuật điều khiển luồng, tránh tắc nghẽn tốt hơn để phục vụ các ứng dụng multimedia trong môi trường mạng hỗn hợp được hiệu quả hơn. Một ví dụ: với kỹ thuật WLDA+ được giới thiệu bởi V.Dorgham Sisalem vào tháng 2 năm 2004 [4] là một thuật toán kiểu TCP-friendly chạy trong môi trường mạng hỗn hợp. Kỹ thuật này dựa trên cơ chế điều khiển luồng của giao thức RTP [13] để phân tích các thông tin về độ trễ, sự mất dữ liệu, băng thông nơi cổ chai của đường truyền phục vụ cho việc điều khiển tắc nghẽn, đồng thời sử dụng thêm một số kỹ thuật khác để bóc tách nguyên nhân mất dữ liệu là do đường truyền hay do tắc nghẽn và có cách xử lý thích hợp nhằm tăng hiệu suất sử dụng băng thông đồng thời đảm bảo tính công bằng cho các giao thức khác trên cùng một đường truyền. Việc nghiên cứu tìm hiểu rõ kỹ thuật này chính là mục tiêu của luận văn. Ngoài ra, để làm sáng tỏ vấn đề luận văn cũng tìm hiểu, trình bày một số nội dung liên quan như các cơ chế áp dụng cho việc truyền tải dữ liệu trong mạng hỗn hợp I-TCP, Snoop- TCP, giới thiệu giao thức RTP cùng các khái niệm cơ bản khác như cơ chế điều khiển tắc nghẽn của TCP, đảm bảo chất lượng dịch vụ trong ứng dụng multimedia và các phương pháp đánh giá hiệu suất mạng, mô phỏng mạng dựa trên bộ mô phỏng mạng (Network Simulator) NS-2. Việc nghiên cứu giao thức WLDA+ nhằm khẳng định tính công bằng đối với việc chia sẻ đường truyền, tính chính xác của dữ liệu được truyền đi khi áp dụng cơ chế này và đặc biệt là tính ưu việt khi tách bạch được hai nguyên nhân gây mất gói tin là do tắc nghẽn hay do đường truyền lỗi Trang 6 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 trong môi trường mạng hỗn hợp, từ đó có cách đối xử hợp lý với tốc độ truyền dữ liệu vào mạng giúp cải thiện hiệu suất của mạng tốt hơn. Với mục tiêu đó, chúng tôi bố trí luận văn thành 4 phần Chương 1: Giới thiệu Chương này hệ thống lại lịch sử phát triển của Internet và bộ giao thức TCP/IP, các ưu, nhược điểm của bộ giao thức này như tự thích ứng với đường truyền, chia sẻ công bằng hay không đảm bảo chất lượng dịch vụ QoS, hiện tượng đồng bộ toàn cầu. Sau đó so sánh với một số giao thức phổ biến khác như UDP, RTP và trình bày giải pháp cải thiện hiệu suất của ứng dụng Multimedia trong đường truyền có dây và đường truyền không dây. Chương 2: Cơ chế điều khiển lưu lượng trong giao thức WLDA+ Chương này trình bày về các cơ chế, kỹ thuật điều khiển lưu lượng và tránh tắc nghẽn của giao thức TCP truyền thống, những đặc trưng lỗi của đường truyền không dây và các cải tiến cho mạng hỗn hợp như I- TCP, snoop-TCP và cải tiến cho mạng hỗn hợp có các ứng dụng Multimedia như giao thức WLDA+. Chương 3: Đánh giá hiệu suất giao thức mạng Chương này giới thiệu một vài phương pháp đánh giá hiệu suất giao thức mạng như phương pháp đánh giá bằng mô hình toán học (lý thuyết hàng đợi) hay phương pháp đánh giá dựa trên việc đo trên mạng thực và lựa chọn phương pháp đánh giá hiệu suất cho giao thức WLDA+. Trong chương này, chúng tôi cũng đề cập đến vấn đề đảm bảo chất lượng dịch vụ QoS, đặc biệt là với các ứng dụng Multimedia. Chương 4: Đánh giá hiệu suất WLDA+ bằng mô phỏng Chương này tập trung vào việc sử dụng phần mềm mô phỏng mạng NS2, xây dựng mô hình mô phỏng phục vụ cho luận văn, thực hiện một số mô phỏng để đánh giá giao thức nhằm thấy được hiệu quả sử dụng Trang 7 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 mạng, phân biệt lỗi đường truyền và tính cân bằng trong giao thức WLDA+. Kết luận và Phương hướng nghiên cứu tiếp theo. Chương 1 Giới thiệu I. Internet và các mô hình tham chiếu 1. Lịch sử phát triển mạng Internet và bộ giao thức TCP/IP Mạng công cộng toàn cầu Internet đã trở nên một thành phần không thể thiếu trong đời sống xã hội ở thế kỷ này. Xuất phát từ nhu cầu thực tế, khi các ngành công nghiệp phát triển nhanh chóng, các máy móc trở nên hiện đại phục vụ rất hữu ích cho đời sống của con người và việc điều khiển những chiếc máy, dây chuyền hiện đại với kích thước khổng lồ như thế không còn đơn giản với những thao tác bằng tay của con người, và máy với nhiệm vụ tính toán hay gọi tắt là máy tính, máy điều khiển lần đầu tiên xuất hiện trong những công xưởng lớn hay trong những môi trường quan trọng của các Quốc gia. Kế theo là sự đòi hỏi của việc chia sẻ thông tin giữa các máy tính đó đã dẫn tới sự hình thành mạng máy tính, liên mạng máy tính trong phạm vi toàn cầu để trở thành một mạng thông tin lớn nhất: Internet. Ban đầu, vào những năm 60 mạng được hình thành trong phòng thí nghiệm được Robert LG đề xuất, cơ quan quản lý dự án nghiên cứu phát triển ARPA thuộc Bộ Quốc phòng Mỹ đã liên kết các mạng tại 4 địa điểm đầu tiên tạo thành mạng WAN có tên là ARPANET. Năm 1983 giao thức TCP/IP được coi như một chuẩn đối với ngành quân sự Mỹ và các máy của mạng Arpanet phải tuân thủ chuẩn này. Với những ưu điểm nổi bật của bộ giao thức này, đặc biệt là khả năng liên kết các mạng khác nhau một cách dễ dàng nó đã trở thành bộ giao thức phổ biến cho mạng Internet ngày nay. Trang 8 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 Internet có thể hiểu theo một nghĩa nào đó như là tập hợp của nhiều mạng con, tạo thành một liên mạng sử dụng bộ giao thức TCP/IP, với mỗi một thực thể tham gia vào mạng được cấp một địa chỉ IP duy nhất được công bố trên toàn thế giới mạng. Mọi lĩnh vực như chính trị, xã hội, thể thao, văn hóa, học tập, nghiên cứu v.v. đều có thể xuất hiện trên Internet và trở thành một phần tất yếu của cuộc sống con người hiện đại ngày nay, đồng thời làm cho nhu cầu ứng dụng truyền thông đa phương tiện tăng lên không ngừng với một tốc độ chóng mặt. 2. Các mô hình tham chiếu Để thuận tiện trong việc lập trình giao thức, xử lý thông tin và giảm độ phức tạp khi thiết kế hay trong quá trình xử lý lỗi, mô hình mạng máy tính nói chung được chia thành nhiều tầng (layer) hay còn gọi là các mức hoặc các lớp. Mỗi tầng được xây dựng dựa trên tầng ngay bên dưới, còn tầng bên dưới thì thực hiện các chức năng riêng của nó rồi chuyển kết quả thực hiện lên tầng trên. Tầng trên lại dựa vào những kết quả này để thực hiện chức năng của chúng mà không cần quan tâm đến chi tiết tại sao lại có những kết quả mà nó đã nhận được. Mặt khác, để có sự thống nhất của tất cả các nhà sản xuất thiết bị mạng trên toàn thế giới, hay nói đúng hơn để cho các sản phẩm mạng của các hãng khác nhau có thể liên lạc, làm việc một cách đơn giản với nhau cần có các chuẩn truyền thông chung nhất hay gọi là các mô hình tham chiếu. Có hai mô hình phổ biến là ISO OSI và TCP/IP. 2.1 Mô hình OSI: Mô hình OSI (Open system interconnection – Mô hình kết nối các hệ thống mở) là một cơ sở dành cho việc chuẩn hoá các hệ thống truyền thông, nó được nghiên cứu và xây dựng bởi ISO. Vào những năm 70, việc nghiên cứu về mô hình OSI đã được bắt đầu. Đến năm 1984, mô hình tham chiếu OSI chính thức được đưa ra giới thiệu. Trang 9 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 Đúng như tên gọi, mô hình 7 lớp OSI chỉ là mô hình tham chiếu chứ không phải là một mạng cụ thể nào. Theo mô hình này, hai thực thể thuộc hai tầng đồng mức khi liên kết với nhau phải sử dụng một giao thức chung. Giao thức ở đây tạm hiểu đơn giản là quy định, phương tiện để các tầng có thể giao tiếp được với nhau, tương tự như hai người thuộc hai Quốc gia sử dụng ngôn ngữ khác nhau muốn hiểu nhau thì cần có một ngôn ngữ chung vậy. Trong mô hình OSI có hai loại giao thức chính được áp dụng là: giao thức có liên kết (connection - oriented) và giao thức không liên kết (connectionless). Giao thức có liên kết: là trước khi truyền số liệu, hai thực thể trên hai tầng đồng mức cần thiết lập một liên kết logic và các gói tin được trao đổi thông qua liên kết này. Giao thức không liên kết: không cần thiết lập liên kết logic trước khi truyền số liệu và mỗi gói tin được truyền độc lập với các gói tin trước hoặc sau nó. Mô hình OSI Hình 1.1 Mô hình OSI Các tầng được xây dựng dựa trên một số nguyên tắc chung: Trang 10 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007  Mỗi tầng được tạo ra khi có nhu cầu phải có một sự trừu tượng mới.  Mỗi tầng tương ứng với một chức năng nhất định  Số lượng tầng phải đủ lớn để các chức năng riêng biệt trong các tầng không quá xa nhau.  Các ranh giới của mỗi tầng có thể chọn để giảm tối thiểu lưu lượng thông tin trao đổi trực tiếp. Nhiệm vụ của các tầng trong mô hình OSI có thể được tóm tắt như sau: Tầng ứng dụng (Application layer – lớp 7): Là tầng trên cùng trong mô hình 7 lớp, quy định giao diện giữa người sử dụng và môi trường OSI, cung cấp các phương tiện cho người sử dụng truy cập và sử dụng các dịch vụ của mô hình OSI, Giao thức được ứng dụng nhiều nhất là giao thức HTTP, là cơ sở của WWW, ngoài ra còn một số giao thức phổ biến khác như SMTP, Telnet, FTP . Phục vụ các ứng dụng truyền tệp, đăng nhập từ xa, hay Email. Tầng trình diễn (Presentation layer – lớp 6): Là tầng có chức năng chuyển đổi các thông tin từ cú pháp người sử dụng sang cú pháp để truyền dữ liệu, đồng thời tầng này giải quyết các vấn đề liên quan đến ngữ nghĩa, cú pháp, ngoài ra nó có thể nén dữ liệu truyền và mã hóa chúng trước khi truyền để bảo mật, tăng hiệu suất. Một số chuẩn định dạng dữ liệu của lớp trình diễn dữ liệu là GIF, JPEG, MP3, MPEG Tầng phiên (Session layer – lớp 5): Là tầng thực hiện việc thiết lập, duy trì và hủy bỏ các phiên làm việc giữa hai hệ thống, hai máy tính khác nhau. Tầng phiên cũng quy định một giao diện ứng dụng cho tầng vận chuyển sử dụng. Các giao thức trong lớp 5 sử dụng là NFS, X- Window System, ASP. Tầng vận chuyển (Transport layer – lớp 4): Là tầng có chức năng xác định địa chỉ trên mạng, cách thức chuyển giao gói tin trên cơ sở trực Trang 11 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 tiếp giữa hai đầu cuối, đảm bảo truyền dữ liệu tin cậy (end-to-end). Tầng vận chuyển còn có các chức năng như điều khiển luồng, khắc phục lỗi và Tài liệu tham khảo Tài liệu tiếng Việt 1. Nguyễn Đình Việt, đánh giá hiệu suất mạng máy tính (2003), luận án tiến sỹ Toán học, Khoa Công nghệ, Đại học Quốc Gia Hà Nội 2. Vũ Duy Lợi, Mạng thông tin máy tính (2002), Nhà xuất bản thế giới, Hà Nội 3. Báo cáo khoa học “So sánh hiệu suất của các kế hoạch kiểm soát lỗi link-by-link và end-to-end trong mạng tốc độ cao” của PGS.TS Nguyễn Đình Việt trong báo cáo tại Hội thảo Quốc Gia năm 2001 Tài liệu tiếng Anh 4. TCP- Friendly Congestion Control over Wireless NetWork Vicente E.Mujica V.,Dorgham Sisalam (2004) 5. TCP- Friendly Congestion schema in the Internet 6. Congestion Avoidance and Control – Van Jacobson, Michael J.Karels 7. The loss delay Based Adjustment Algorithm – Dorgham Sisalem, Henning Schulzrinne 8. TCP- friendly for Multimedia Communication in the Internet – Dorgham Sisalem 9. LDA+: A TCP-friendly Adaptation Scheme for multimedia communication - Dorgham Sisalem, Adam Wolisz 10. The multimedia Transport Protocol RTP – Kevil jecffay 1999 11. RAP: end-to-end Rate-base Congestion Control Machenism for Realtime Streams in the Internet – Reza Rejaie, Mark handley, Deborah Estrin Trang 12 Luận văn cao học – Nghiên cứu thuật toán WLDA+ 2007 12. Discriminating Congestion Losses From Wireless Losses using Inter-Arrival at the Receiver. 13. RFC 1889 – RTP a Transport Protocol for Real-Time Applications 14. TCP Westwood: End-to-end bandwidth Estimation for Enhanced Trasport over Wireless links – Claudio casetti, Mario gerla, Saverio Mascolo, M.Yahya Sanadidi and Ren wang 15. S.Biaz and N.Vaidya, “Discriminating congesstion losses from wireless losses using inter-arival times at the receiver,” 1999 16. End-to-end differentiation of congesstion and wireless lossess Song Cen, Pamela C.Cosman, and Geoffrey, M. Voelker. 17. Y.Tobe, Y. Tamura, A. Molano, S. Ghosh, and H. Tokuda, “Achieving moderate fairness for UDP flows by path-status classification,” 2000 18. The multimedia transport Protocol RTP, Kevin Jeffay 1999 19. NS –by – Example, NS-for –beginer. NS – Tutorial 20. 21. 22. 23. Và một số tài liệu tham khảo khác.