Topology và Định tuyến trong Mạng Overlay: Nghiên cứu của Kishore Kothapalli

Luận án tiến sĩ nghiên cứu topology and routing in overlay networks, phân tích chuyên sâu, xây dựng mô hình lý thuyết, đề xuất giải pháp khoa học cho vấn đề thực tiễn.

• Tác giả: Kishore Kothapalli
• Người hướng dẫn: Professor Christian Scheideler
• Trường học: The Johns Hopkins University
• Chuyên ngành: Doctor of Philosophy
• Đề tài: Topology and Routing in Overlay Networks
• Loại tài liệu: dissertation
• Năm xuất bản: 2006
• Địa điểm: Baltimore

Mục lục chi tiết

• Abstract
• Acknowledgements
• 1. CHƯƠNG 1: INTRODUCTION
• 1.1. Models of Computing
• 1.2. Client-server computing
• 1.3. Peer-to-peer computing
• 1.4. Why Logical Networks?
• 1.4.1. Provisioning Special Features
• 1.4.2. Virtual Private Networks (VPNs)
• 1.4.3. Internet Transparency and Symmetry
• 2. CHƯƠNG 2: TERMINOLOGY AND NOTATION
• 2.1. Basic Probability
• 2.2. Basic Graph Theory
• 2.3. Basic Network Topologies
• 2.4. Basic Routing Theory
• 3. CHƯƠNG 3: OUR CONTRIBUTIONS
• 3.1. Key Questions
• 3.2. Vertex Coloring
• 4. CHƯƠNG 4: MODEL AND DEFINITIONS
• 4.1. Summary of our approach
• 4.2. Organization of the Chapter
• 4.3. Upper Bound for Constant Degree Oriented Graphs
• 4.4. Upper Bound for Arbitrary Oriented Graphs
• 4.5. Chapter Summary and Acknowledgements
• 5. CHƯƠNG 5: P2P NETWORKS: DETERMINISTIC CONSTRUCTIONS
• 5.1. Overlay networks for uniform peers
• 5.2. Overlay networks for non-uniform peers
• 5.3. Overlay networks for multicasting
• 5.4. The static Pagoda network
• 5.5. The dynamic Pagoda network for uniform nodes
• 5.5.1. Isolated Join and Leave operations
• 5.5.2. Concurrent Join and Leave Operations
• 5.6. The dynamic Pagoda network for non-uniform nodes
• 5.6.1. Join and Leave operations
• 5.7. The concurrent multicast problem
• 5.8. Routing
• 5.9. Turning multicast flows into trees
• 5.10. Multicasting in a dynamic setting: virtual homes
• 5.11. Chapter summary and acknowledgements
• 6. CHƯƠNG 6: P2P NETWORKS: SUPERVISED P2P SYSTEMS
• 6.1. A general framework for supervised peer-to-peer systems
• 6.1.1. The hierarchical decomposition technique
• 6.1.2. The continuous-discrete technique
• 6.1.3. The recursive labeling technique
• 6.2. Putting all pieces together
• 6.3. Dynamic Hypercube Network
• 6.4. Dynamic de Bruijn Network
• 6.5. Concurrent Join/Leave Operations
• 6.6. Robustness against Random Faults
• 6.6.1. The Random Fault Model
• 6.7. Robustness against Adaptive Adversarial Attacks
• 6.7.1. The Semi-adaptive Model
• 6.7.2. The Fully Adaptive Model
• 6.8. Massive Multi-player Online Gaming
• 7. CHƯƠNG 7: WIRELESS AD HOC NETWORKS: MODEL AND SPANNER
• 7.1. Unit Disk Graph (UDG) model
• 7.2. Packet Radio Network (PRN) model
• 7.3. A new model for wireless communication
• 7.4. Transmission range, interference range, and physical carrier sensing range
• 7.5. Constant density dominating set
• 7.6. Overview of spanner protocol
• 7.6.1. Phase I: dominating set
• 7.6.2. Phase II - Distributed Leader Coloring
• 7.6.3. Phase III - Gateway Discovery
• 7.7. Chapter Summary and Acknowledgements
• 8. CHƯƠNG 8: WIRELESS AD HOC NETWORKS: BROADCASTING AND GATHERING
• 8.1. Related work
• 8.2. Stage 1: Building Gathering Tree(s)
• 8.3. Stage 2: Gathering on Tree(s)
• 8.4. Self-stabilization
• 8.5. Broadcasting Multiple Messages
• 8.6. Chapter Summary and Acknowledgements
• 9. CHƯƠNG 9: CONCLUSIONS
• Bibliography
• Vita
• List of Figures

Tóm tắt

I. Tổng Quan Mạng Overlay Giải Pháp Ưu Việt Triển Vọng Mới

Trong kỷ nguyên thông tin, các mô hình trao đổi thông tin dựa trên mạng overlay đang ngày càng thu hút sự chú ý. Mạng overlay cung cấp một cấu trúc liên kết logic trên một mạng vật lý hiện có. Ưu điểm của mạng overlay bao gồm dễ triển khai, khả năng thích ứng và khả năng triển khai gia tăng. Do phạm vi ứng dụng và ưu điểm rộng rãi, việc nghiên cứu chính thức về mạng overlay là cần thiết để hiểu các thách thức nghiên cứu khác nhau trong bối cảnh này. Luận án này tập trung vào hai loại mạng overlay: mạng ngang hàng (P2P) và mạng ad hoc không dây. Trọng tâm sẽ là hai vấn đề chính trong mạng overlay: làm thế nào để tạo ra các topology hiệu quả và làm thế nào để cung cấp các chiến lược định tuyến hiệu quả.

1.1. Lịch Sử Phát Triển và Tầm Quan Trọng của Mạng Overlay

Do tầm quan trọng ngày càng tăng, việc nghiên cứu mạng overlay đang được coi là một lĩnh vực nghiên cứu độc lập từ thập kỷ qua. Hiện tại, nghiên cứu này tập trung vào hai loại mạng overlay chính: mạng P2P và mạng overlay cho các mạng ad hoc không dây. Mạng overlay P2P đã thu hút được sự chú ý lớn trong những năm gần đây do những ưu điểm vượt trội mà chúng mang lại. Mạng P2P cho phép cải thiện hiệu quả của các tài nguyên như tính toán và lưu trữ bằng cách chia sẻ tài nguyên liền mạch. Đồng thời, các hệ thống P2P không cần máy chủ trung tâm, điều này có nghĩa là các cá nhân có thể tìm kiếm thông tin hoặc hợp tác mà không phải trả phí hoặc đầu tư thêm phần cứng hiệu năng cao.

1.2. Ưu Điểm Vượt Trội của Mạng Overlay So Với Mạng Truyền Thống

Mạng overlay mang lại nhiều lợi ích so với các mạng truyền thống. Các lợi ích này bao gồm dễ triển khai, khả năng tùy biến dễ dàng và khả năng triển khai gia tăng. Những ưu điểm này làm cho mạng overlay trở thành một lựa chọn tốt cho một loạt các ứng dụng. Để cung cấp thêm thông tin chi tiết, chúng ta hãy xem xét các ví dụ như cung cấp các tính năng đặc biệt, Mạng riêng ảo (VPN) và điện toán lưới (grid computing), tất cả đều được hưởng lợi từ những ưu điểm trên. Mạng overlay cung cấp một mức độ trừu tượng và dễ dàng trong việc cung cấp đảm bảo chất lượng dịch vụ (QoS) , một chủ đề được tranh luận sôi nổi trong các diễn đàn nghiên cứu Internet như IETF (Internet Engineering Task Force).

II. Thách Thức Trong Thiết Kế Topology và Định Tuyến Overlay

Mặc dù mạng overlay mang lại nhiều lợi ích, nhưng việc thiết kế và triển khai chúng cũng đặt ra nhiều thách thức. Các thách thức này bao gồm việc xây dựng các topology hiệu quả, đảm bảo khả năng mở rộng, đối phó với tính động (tham gia và rời mạng của các nút) và đảm bảo an ninh. Các giải pháp cần phải cân bằng giữa hiệu suất, chi phí và độ phức tạp. Ngoài ra, các yêu cầu cụ thể của ứng dụng có thể ảnh hưởng lớn đến các quyết định thiết kế.

2.1. Bài Toán Thiết Kế Topology Hiệu Quả trong Mạng Overlay

Một trong những thách thức chính là thiết kế một topology hiệu quả cho mạng overlay. Topology này cần phải đảm bảo khả năng kết nối tốt, độ trễ thấp và khả năng phục hồi cao. Việc xây dựng các topology hiệu quả một cách phi tập trung là một vấn đề khó khăn, đặc biệt là khi các nút có băng thông không đồng đều. Trong luận án này, tác giả trình bày một topology overlay xác định, Pagoda, có thể được sử dụng để định tuyến hiệu quả, quản lý dữ liệu và truyền đa phương tiện. Bên cạnh đó, tác giả cũng đề xuất một phương pháp thống nhất để tạo ra một lớp lớn các topology overlay thông qua một cách tiếp cận gọi là mạng overlay được giám sát.

2.2. Vấn Đề Định Tuyến Tối Ưu trong Mạng Overlay Động

Việc định tuyến hiệu quả trong một mạng overlay động cũng là một thách thức lớn. Các thuật toán định tuyến cần phải có khả năng thích ứng với các thay đổi trong topology, chẳng hạn như các nút tham gia hoặc rời mạng. Ngoài ra, các thuật toán định tuyến cần phải có khả năng tìm đường đi ngắn nhất giữa hai nút, đồng thời giảm thiểu độ trễ và tiêu thụ băng thông. Luận án này tập trung vào việc cung cấp các thuật toán hiệu quả để phát sóng và thu thập thông tin trong mạng ad hoc không dây, đồng thời đảm bảo rằng tất cả các thuật toán đều đơn giản, tự ổn định và chỉ yêu cầu một lượng lưu trữ không đổi tại bất kỳ nút nào.

III. Giải Pháp Pagoda Topology Overlay Xác Định Cho Mạng P2P

Pagoda là một topology overlay xác định được thiết kế cho mạng P2P. Nó cho phép định tuyến hiệu quả, quản lý dữ liệu và truyền đa phương tiện. Topology này được xây dựng dựa trên một cấu trúc phân cấp, trong đó các nút được tổ chức thành các cụm. Các nút trong cùng một cụm được kết nối trực tiếp với nhau, trong khi các cụm khác nhau được kết nối thông qua các nút cổng. Cấu trúc này cho phép định tuyến hiệu quả, vì các gói tin có thể được định tuyến đến đích bằng cách đi qua các cụm trung gian.

3.1. Cấu Trúc Phân Cấp và Thuật Toán Định Tuyến của Pagoda

Cấu trúc phân cấp của Pagoda cho phép định tuyến hiệu quả bằng cách chia mạng thành các cụm. Thuật toán định tuyến sử dụng thông tin về cấu trúc cụm để tìm đường đi ngắn nhất giữa hai nút. Các gói tin được định tuyến đến đích bằng cách đi qua các cụm trung gian. Điều này làm giảm độ trễ và tiêu thụ băng thông, đồng thời tăng cường khả năng mở rộng của mạng.

3.2. Ưu Điểm của Pagoda trong Quản Lý Dữ Liệu và Multicasting

Pagoda cũng có thể được sử dụng để quản lý dữ liệu và truyền đa phương tiện một cách hiệu quả. Cấu trúc phân cấp của Pagoda cho phép dữ liệu được lưu trữ và truy xuất một cách hiệu quả. Ngoài ra, topology này cũng hỗ trợ truyền đa phương tiện bằng cách cho phép các nút truyền dữ liệu đến nhiều đích cùng một lúc. Khả năng này rất quan trọng đối với các ứng dụng như video streaming và hội nghị trực tuyến.

IV. Mạng Overlay Được Giám Sát Phương Pháp Tạo Topology Linh Hoạt

Mạng overlay được giám sát (Supervised Overlay Networks) là một phương pháp tiếp cận để tạo ra các topology overlay linh hoạt. Phương pháp này sử dụng một nút giám sát để giúp các nút khác kết nối với nhau. Nút giám sát có thể cung cấp thông tin về topology mạng, cũng như giúp các nút tìm các nút lân cận phù hợp. Điều này cho phép tạo ra các topology overlay có thể thích ứng với các thay đổi trong mạng.

4.1. Tổng Quan Về Khung Mạng Overlay Được Giám Sát

Khung mạng overlay được giám sát bao gồm một nút giám sát và một tập hợp các nút ngang hàng. Nút giám sát có trách nhiệm duy trì thông tin về topology mạng và giúp các nút ngang hàng kết nối với nhau. Các nút ngang hàng sử dụng thông tin từ nút giám sát để tìm các nút lân cận phù hợp và xây dựng topology overlay.

4.2. Ưu Điểm và Ứng Dụng của Mạng Overlay Được Giám Sát

Mạng overlay được giám sát có nhiều ưu điểm, bao gồm khả năng thích ứng với các thay đổi trong mạng, khả năng mở rộng và khả năng bảo mật. Phương pháp này có thể được sử dụng trong nhiều ứng dụng khác nhau, chẳng hạn như điện toán lưới, trò chơi trực tuyến nhiều người chơi và truyền phát video.

4.3. Kỹ Thuật Phân Rã Phân Cấp Liên Tục Rời Rạc và Gán Nhãn Đệ Quy

Có một số kỹ thuật quan trọng để tạo mạng overlay được giám sát, bao gồm kỹ thuật phân rã phân cấp (hierarchical decomposition), kỹ thuật liên tục-rời rạc (continuous-discrete technique) và kỹ thuật gán nhãn đệ quy (recursive labeling). Mỗi kỹ thuật này đóng một vai trò quan trọng trong việc tạo ra một mạng overlay hiệu quả và có thể mở rộng.

V. Mô Hình Hóa Truyền Thông Không Dây và Spanner Thưa Thớt

Luận án này giới thiệu một mô hình mới cho truyền thông không dây thực tế hơn so với các mô hình thường được sử dụng trong cộng đồng lý thuyết. Mô hình này tính đến các yếu tố như phạm vi truyền dẫn, phạm vi nhiễu và phạm vi cảm biến vật lý. Sử dụng mô hình này, tác giả trình bày cách tạo ra một cấu trúc spanner thưa thớt dựa trên tập hợp các nút thống trị.

5.1. Mô Hình Đĩa Đơn Vị và Mô Hình Mạng Radio Gói Tin

Các mô hình phổ biến cho truyền thông không dây bao gồm mô hình đĩa đơn vị (UDG) và mô hình mạng radio gói tin (PRN). Tuy nhiên, các mô hình này có những hạn chế nhất định và không phải lúc nào cũng phản ánh chính xác các điều kiện thực tế. Do đó, luận án này giới thiệu một mô hình mới để truyền thông không dây.

5.2. Phạm Vi Truyền Dẫn Phạm Vi Nhiễu và Phạm Vi Cảm Biến Vật Lý

Mô hình mới cho truyền thông không dây tính đến các yếu tố như phạm vi truyền dẫn, phạm vi nhiễu và phạm vi cảm biến vật lý. Những yếu tố này có thể ảnh hưởng lớn đến hiệu suất của mạng không dây. Phạm vi truyền dẫn là khoảng cách tối đa mà một nút có thể truyền dữ liệu. Phạm vi nhiễu là khoảng cách mà một nút có thể gây nhiễu cho các nút khác. Phạm vi cảm biến vật lý là khoảng cách mà một nút có thể cảm nhận sự hiện diện của các nút khác.

5.3. Spanner Thưa Thớt Định Nghĩa và Ứng Dụng Trong Mạng Ad Hoc

Cấu trúc spanner thưa thớt được sử dụng để giảm số lượng liên kết trong mạng, đồng thời vẫn đảm bảo khả năng kết nối tốt. Spanner thưa thớt có thể được sử dụng để cải thiện hiệu suất của các thuật toán định tuyến và phát sóng trong mạng ad hoc không dây. Cấu trúc spanner thường được xây dựng dựa trên một tập hợp các nút thống trị. Tập hợp các nút thống trị là một tập hợp con của các nút trong mạng sao cho mỗi nút trong mạng hoặc thuộc về tập hợp thống trị hoặc là nút lân cận của một nút trong tập hợp thống trị.

VI. Thuật Toán Phát Sóng và Thu Thập Thông Tin Hiệu Quả Trong Mạng Ad Hoc

Luận án này trình bày các thuật toán hiệu quả để phát sóng và thu thập thông tin trong mạng ad hoc không dây. Tất cả các thuật toán đều đơn giản, tự ổn định và chỉ yêu cầu một lượng lưu trữ không đổi tại bất kỳ nút nào. Do đó, các thuật toán này cũng có thể áp dụng được trong nhiều tình huống khác nhau, chẳng hạn như các thiết bị cảm biến đơn giản.

6.1. Phát Sóng Đa Tin Nhắn Giảm Thiểu Sự Chồng Chéo Gói Tin

Phát sóng đa tin nhắn (broadcasting multiple messages) là một vấn đề quan trọng trong mạng ad hoc không dây. Các thuật toán phát sóng cần phải có khả năng phân phối tin nhắn đến tất cả các nút trong mạng một cách hiệu quả, đồng thời giảm thiểu sự chồng chéo gói tin. Sự chồng chéo gói tin có thể làm giảm hiệu suất của mạng và gây ra mất mát dữ liệu.

6.2. Thu Thập Thông Tin Hiệu Quả Từ Các Nút Bị Cô Lập

Trong một số trường hợp, một số nút trong mạng có thể bị cô lập và không thể giao tiếp trực tiếp với các nút khác. Việc thu thập thông tin từ các nút bị cô lập này là một thách thức. Luận án này trình bày các thuật toán có thể thu thập thông tin từ các nút bị cô lập bằng cách sử dụng các nút trung gian.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ với nhan đề "Topology and Routing in Overlay Networks" (Tô-pô và định tuyến trong mạng phủ) được nghiên cứu sinh Kishore Kothapalli thực hiện tại Khoa Khoa học Máy tính thuộc Đại học Johns Hopkins (The Johns Hopkins University, Baltimore, Maryland, Hoa Kỳ), hoàn thành vào tháng 6 năm 2006. Công trình được hướng dẫn bởi Giáo sư Christian Scheideler, cùng sự tham gia đánh giá của các thành viên trong hội đồng gồm Giáo sư Rao Kosaraju, Giáo sư Andreas Terzis, Giáo sư James Fill và Giáo sư Jin Kung.

+-------------------------------------------------------------------------------+
| THÔNG TIN TỔNG QUAN VỀ LUẬN ÁN                                                |
+----------------------+--------------------------------------------------------+
| Tác giả              | Kishore Kothapalli                                     |
| Cơ sở đào tạo        | The Johns Hopkins University                           |
| Thời gian công bố    | Tháng 6 năm 2006                                       |
| Giáo sư hướng dẫn    | Prof. Christian Scheideler                             |
| Thành viên hội đồng  | Prof. Rao Kosaraju, Prof. Andreas Terzis,              |
|                      | Prof. James Fill, Prof. Jin Kung                       |
| Lĩnh vực nghiên cứu  | Khoa học máy tính / Mạng phân tán và Thuật toán        |
+----------------------+--------------------------------------------------------+

Tính cấp thiết và khoảng trống nghiên cứu

Mạng phủ (overlay network) là mạng liên kết logic được thiết lập phía trên một mạng vật lý sẵn có. Mô hình này sở hữu nhiều ưu điểm như tính linh hoạt, tính thích ứng, dễ triển khai thực tế và khả năng triển khai gia tăng (incremental deployability). Trong bối cảnh hạ tầng Internet truyền thống gặp phải các rào cản lớn về việc đảm bảo chất lượng dịch vụ (QoS), sự cạn kiệt không gian địa chỉ IPv4, sự suy giảm tính minh bạch đầu cuối do thiết bị NAT (Network Address Translator) và giao thức DHCP gây ra, cùng sự bất đối xứng băng thông của hạ tầng ADSL/cáp, mạng phủ nổi lên như một mô hình truyền thông quan trọng. Hai phân lớp mạng phủ nhận được nhiều sự quan tâm là mạng ngang hàng (peer-to-peer - P2P) và mạng ad hoc không dây (wireless ad hoc networks).

Tuy nhiên, nghiên cứu lý thuyết về mạng phủ khi đó đối mặt với các khoảng trống cơ bản:

1. Trong mạng P2P, phần lớn các công trình tập trung vào cấu trúc ngẫu nhiên hóa; các câu hỏi nền tảng về cách thiết kế topo tiền định (deterministic constructions) và cách tổ chức các nút mạng có băng thông không đồng đều (heterogeneous/non-uniform bandwidth peers) vẫn chưa có lời giải hoàn chỉnh.
2. Việc tạo lập các topo tiền định tốt hoàn toàn phi tập trung là bài toán phức tạp, đòi hỏi một phương pháp luận thống nhất thông qua mô hình mạng P2P có giám sát (supervised overlay networks) nhằm hỗ trợ các thao tác gia nhập/rời mạng nhanh và khả năng tự phục hồi.
3. Trong mạng ad hoc không dây, các mô hình truyền thông lý thuyết phổ biến thời điểm đó (như Unit Disk Graph - UDG, Packet Radio Network - PRN) còn quá đơn giản hóa, chưa phản ánh đúng can nhiễu vật lý thực tế, dải truyền và dải cảm nhận sóng mang. Hơn nữa, việc xây dựng khung xương thưa (spanner), thuật toán phát thanh (broadcasting) và thu thập thông tin (gathering) tự ổn định với dung lượng lưu trữ hằng số tại mỗi nút vẫn là thách thức lớn.

Mục tiêu và câu hỏi nghiên cứu

Mục tiêu bao trùm của luận án là giải quyết hai bài toán trung tâm trong mạng phủ: thiết kế topo hiệu quả và xây dựng chiến lược định tuyến hiệu quả cho mạng P2P và mạng ad hoc không dây.

Ba câu hỏi nghiên cứu cốt lõi được tác giả xác định và đánh số tại Mục 3.1 bao gồm:

1. Tính liên thông (Connectivity): Làm thế nào để đảm bảo mạng phủ luôn duy trì một thành phần liên thông duy nhất (hoặc một thành phần liên thông khổng lồ - giant connected component kích thước $n(1-o(1))$ trong các mô hình ngẫu nhiên)?
2. Tính duy trì (Maintenance): Làm thế nào để duy trì cấu trúc mạng phủ khi các nút liên tục gia nhập và rời khỏi mạng ở tốc độ cao (churn), thông qua số lượng thao tác kiểm soát cục bộ tối thiểu?
3. Định tuyến (Routing): Làm thế nào để giải quyết hiệu quả các bài toán định tuyến trong mạng phủ nhằm tối ưu hóa độ tắc nghẽn (congestion), độ trễ/độ giãn nở (dilation) và dung lượng bộ đệm tại các nút?

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Cấu trúc topo logic và các thuật toán định tuyến phân tán trong mạng P2P (topo tiền định Pagoda, hệ thống P2P có giám sát trên nền Hypercube và de Bruijn) và mạng ad hoc không dây (mô hình can nhiễu thực tế, spanner mật độ hằng số, cây thu thập dữ liệu, phát thanh dữ liệu); thuật toán tô màu đỉnh phân tán trên đồ thị có hướng.
• Phạm vi không gian và thời gian: Nghiên cứu lý thuyết tính toán phân tán, đánh giá độ phức tạp thuật toán và mô hình hóa toán học, hoàn thành tại Baltimore, Hoa Kỳ năm 2006.

---

Tổng quan tài liệu và vị trí của luận án

Luận án hệ thống hóa các giai đoạn phát triển của mạng P2P và mạng ad hoc không dây, phân loại chi tiết các công trình tiền nhiệm:

+-------------------------------------------------------------------------------+
| PHÂN LOẠI CÁC THẾ HỆ MẠNG PHỦ TRONG TỔNG QUAN TÀI LIỆU                         |
+---------------------+-------------------+-------------------------------------+
| Phân lớp mạng       | Thế hệ            | Các hệ thống / Công trình tiêu biểu |
+---------------------+-------------------+-------------------------------------+
| Mạng P2P            | Thế hệ thứ nhất   | Napster, Gnutella [50]              |
|                     | Thế hệ thứ hai    | Tapestry [155], Pastry [129],       |
|                     | (DHT có cấu trúc) | Chord [142], CAN [125]              |
|                     | Thế hệ thứ ba     | Chịu lỗi, bảo mật, kháng tấn công  |
|                     |                   | [42, 6, 132]                        |
+---------------------+-------------------+-------------------------------------+
| Mạng ad hoc         | Thế hệ thứ nhất   | Cấu hình hình sao qua Base Station  |
| không dây           | Thế hệ thứ hai    | Multi-hop: IETF MANET, Archipelago  |
|                     | Thế hệ thứ ba     | Mạng phi hạ tầng hoàn toàn          |
+---------------------+-------------------+-------------------------------------+

Các hướng nghiên cứu trước được điểm lại

• Mạng P2P:
  • Thế hệ 1: Napster (sử dụng máy chủ chỉ mục tập trung, gây điểm nghẽn cổ chai) và Gnutella [50] (phi tập trung nhưng dùng kỹ thuật ngập lụt không kiểm soát - naive flooding, làm tăng tải khi quy mô đạt hàng triệu nút).
  • Thế hệ 2: Bảng băm phân tán (Distributed Hash Table - DHT) với cấu trúc topo định trước nhằm đảm bảo thời gian tìm kiếm $O(\log n)$, tiêu biểu là Chord [142] (dựa trên băm nhất quán của Karger et al. [69]), Pastry [129] và Tapestry [155] (dựa trên mô hình Plaxton-Rajaraman-Richa [121]), CAN [125] (dựa trên phân rã phân cấp không gian $d$ chiều).
  • Thế hệ 3: Các đề xuất bổ sung cơ chế chịu lỗi ngẫu nhiên và kháng lại các mô hình tấn công đối nghịch [42, 6, 132].
• Mạng ad hoc không dây:
  • Thế hệ 1 & 2: Mô hình tập trung qua trạm gốc (Base Station/Access Point) và mô hình chuyển tiếp đa chặng (multi-hop) của nhóm IETF MANET và dự án Archipelago [1, 7].
  • Mạng phủ hình học và topo: Đồ thị Gabriel [46], Đồ thị Yao [152], đồ thị lân cận tương đối (RNG) [47], cùng các thuật toán định tuyến hình học như Face Routing [86] và các biến thể [85, 47, 17, 18, 19].
• Lĩnh vực liên quan:
  • Hệ thống phân tán: Khái niệm tự ổn định (self-stabilization) khởi xướng bởi Dijkstra [32]; các mô hình máy truy cập ngẫu nhiên song song PRAM (CREW, CRCW, EREW).
  • Mạng phân phối nội dung (CDN): Cơ chế sử dụng máy chủ đại diện (surrogate servers) và bộ chuyển hướng (redirectors) của Akamai và Digital Island [120].
  • Tô màu đỉnh phân tán: Các giải pháp tô $(\Delta+1)$ màu trên đồ thị có bậc cực đại $\Delta$ trong số vòng giao tiếp logarit.

Khoảng trống luận án lựa chọn giải quyết

Luận án định vị trọng tâm vào việc khắc phục tính ngẫu nhiên thiếu kiểm soát của mạng P2P thế hệ 2 bằng cấu trúc tiền định Pagoda có hỗ trợ nút không đồng nhất về băng thông; xây dựng cơ chế quản lý cho mạng P2P có giám sát nhằm đối phó với kẻ tấn công đối nghịch thích ứng toàn diện (fully adaptive adversary); và khắc phục sự phi thực tế của các mô hình mạng không dây UDG/PRN bằng một mô hình can nhiễu mở rộng đi kèm giao thức xây dựng spanner và định tuyến tự ổn định có bộ nhớ $O(1)$.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

Luận án vận dụng hệ thống lý thuyết giải tích tiệm cận, xác suất học và lý thuyết đồ thị:

• Xác suất và cận đuôi: Luận án thiết lập không gian xác suất $(\Omega, \mathcal{F}, \Pr)$, bất đẳng thức Boole (Boole's inequality/union bound), bất đẳng thức Markov ($\Pr(X \ge t\mathbb{E}[X]) \le 1/t$) và hệ thống các cận Chernoff cho biến ngẫu nhiên tổng Bernoulli độc lập: $$\Pr(X > (1+\delta)\mu) < \left[ \frac{e^\delta}{(1+\delta)^{1+\delta}} \right]^\mu$$ Khái niệm "với xác suất cao" (with high probability - w.h.p.) được định nghĩa chuẩn tắc là xác suất đạt ít nhất $1 - 1/n^k$ với hằng số $k > 0$.
• Lý thuyết đồ thị và topo mạng: Khảo sát đồ thị $G=(V,E)$ với $n=|V|, m=|E|$, đường kính $D$, bậc cực đại $\Delta$. Định nghĩa dung lượng cạnh $c: E \to \mathbb{R}^+$, độ giãn nở cạnh (edge expansion) $\alpha = \min_{\emptyset \subset U \subset V} \frac{c(U,\bar{U})}{\min{c(U), c(\bar{U})}}$ và độ giãn nở nút. Khảo sát các họ đồ thị chuẩn gồm Lưới $M(m,d)$, Torus $T(m,d)$, Hypercube, Butterfly $BF(d)$ (gồm $(d+1)2^d$ nút, bậc 4) và de Bruijn $DB(b,d)$ với độ giãn nở $O(1/d)$.
• Lý thuyết định tuyến: Định nghĩa các mô hình Định tuyến đơn hướng (Unicasting), Hoán vị (Permutation Routing), Phát thanh (Broadcasting), Đa hướng (Multicasting) và Thu thập thông tin (Gathering). Hiệu năng được đo bằng hai thông số:
  • Độ tắc nghẽn (Congestion $C(S)$): Nghịch đảo giá trị luồng đồng thời cực đại.
  • Độ giãn nở (Dilation $D(S)$): Chiều dài đường đi luồng dài nhất trong nghiệm $S$.

Phương pháp nghiên cứu

Tác giả áp dụng phương pháp thiết kế và phân tích thuật toán phân tán tiền định kết hợp ngẫu nhiên hóa có chứng minh toán học hình thức:

• Kỹ thuật phá vỡ tính đối xứng (Symmetry Breaking): Khai thác hướng cạnh trong đồ thị có hướng để giảm số vòng giao tiếp trong bài toán tô màu đỉnh.
• Kỹ thuật phân cấp và nhãn đệ quy: Kỹ thuật phân rã phân cấp (hierarchical decomposition), kỹ thuật liên tục - rời rạc (continuous-discrete technique) và kỹ thuật gán nhãn đệ quy (recursive labeling) để ánh xạ các nút mạng P2P vào topo đại số.
• Mô hình hóa can nhiễu vật lý: Thiết lập mô hình mạng không dây dựa trên 3 thông số hình học: bán kính truyền ($R_t$), bán kính can nhiễu ($R_i$), và bán kính cảm nhận sóng mang vật lý ($R_s$), giải quyết hiện tượng nút ẩn (hidden node) và nút lộ (exposed node).

---

Nội dung chính theo từng chương

Chương 1: Introduction (Giới thiệu)

Chương 1 trình bày tổng quan về các mô hình tính toán: tính toán để bàn (desktop computing), tính toán khách - chủ (client-server computing) và tính toán ngang hàng (peer-to-peer computing). Phân tích lý do hình thành mạng logic (provisioning tính năng đặc biệt như QoS, IPv6; mạng riêng ảo VPNs; tính toán lưới Grid Computing như distributed.net, SETI@home). Phân tích hiện trạng mất tính minh bạch và bất đối xứng của Internet do NAT, DHCP và hạ tầng ADSL. Điểm lại lịch sử mạng P2P qua 3 thế hệ và mạng ad hoc không dây qua 3 thế hệ. Trình bày các thách thức nghiên cứu then chốt và mối liên hệ với hệ thống phân tán truyền thống cùng mạng phân phối nội dung (CDN).

Chương 2: Terminology and Notation (Thuật ngữ và Ký hiệu)

Chương này chuẩn hóa hệ thống ký hiệu toán học xuyên suốt luận án. Trình bày các bất đẳng thức đại số cơ bản, lý thuyết xác suất (không gian xác suất, biến ngẫu nhiên, kỳ vọng, bất đẳng thức Markov, cận Chernoff và định nghĩa xác suất cao w.h.p.). Thiết lập các khái niệm lý thuyết đồ thị (đường đi, chu trình, cây khung, khoảng cách, đường kính, bậc, độ giãn nở cạnh và nút). Định nghĩa toán học cho các topo mạng chuẩn: Lưới $M(m,d)$, Torus $T(m,d)$, Butterfly $BF(d)$, de Bruijn $DB(b,d)$. Cuối cùng là các định nghĩa hình thức về lý thuyết luồng và định tuyến (thu thập thông tin, đơn hướng, hoán vị, đa hướng, phát thanh, độ tắc nghẽn $C(S)$ và độ giãn nở $D(S)$).

Chương 3: Our Contributions (Các đóng góp của Luận án)

Chương 3 tóm lược cấu trúc kỹ thuật và các kết quả trọng tâm của luận án, xoay quanh 3 câu hỏi lớn về tính liên thông, tính duy trì và định tuyến. Trình bày khái quát kết quả đạt được trong 3 phần chính: thuật toán tô màu đỉnh phân tán trên đồ thị có hướng (Phần I); cấu trúc mạng P2P tiền định Pagoda, định tuyến đa hướng và khung P2P có giám sát kháng tấn công đối nghịch thích ứng (Phần II); mô hình truyền thông không dây mới, giao thức xây dựng spanner mật độ hằng số và các thuật toán phát thanh, thu thập dữ liệu tự ổn định (Phần III).

Chương 4: Vertex Coloring (Tô màu đỉnh đồ thị có hướng)

Chương 4 nghiên cứu bài toán tô $(\Delta+1)$ màu phân tán cho đồ thị có hướng $G=(V,E)$ với bậc cực đại $\Delta$. Tác giả chứng minh rằng việc sở hữu hướng cạnh đóng vai trò quyết định trong việc phá vỡ tính đối xứng giữa các nút lân cận. Chương này phát triển các thuật toán cục bộ:

• Đối với đồ thị có hướng bậc hằng số (Constant Degree Oriented Graphs), thuật toán đạt cận trên về thời gian thực thi nhanh hơn các thuật toán trên đồ thị vô hướng.
• Đối với đồ thị có hướng bậc tùy ý (Arbitrary Oriented Graphs), thuật toán chia làm các giai đoạn (Phase I và Phase II), sử dụng các lựa chọn ngẫu nhiên cục bộ để cô lập các thành phần liên thông của các nút chưa được tô màu, qua đó hoàn thành việc gán nhãn màu hợp lệ trong số vòng giao tiếp tối ưu.

+-------------------------------------------------------------------------------+
| CÁC GIAI ĐOẠN TRONG THUẬT TOÁN TÔ MÀU ĐỈNH ĐỒ THỊ CÓ HƯỚNG                   |
+-----------+-------------------------------------------------------------------+
| Giai đoạn | Cơ chế thực thi                                                   |
+-----------+-------------------------------------------------------------------+
| Phase I   | Các nút thực hiện chọn màu ngẫu nhiên dựa trên hướng cạnh để      |
|           | phá vỡ tính đối xứng; phần lớn các nút nhận màu hợp lệ.          |
| Phase II  | Xử lý các thành phần liên thông còn lại của các nút chưa có màu,  |
|           | gán nhãn hoàn tất việc tô (\Delta + 1) màu trong thời gian ngắn.  |
+-----------+-------------------------------------------------------------------+

Chương 5: P2P Networks: Deterministic Constructions (Mạng P2P: Cấu trúc tiền định)

Chương 5 giới thiệu mạng phủ tiền định mang tên Pagoda ($PG(d)$), giải quyết bài toán tổ chức các nút mạng có băng thông không đồng đều:

• Cấu trúc Pagoda tĩnh: $PG(d)$ được thiết kế dựa trên cấu trúc tích hợp từ các thành phần $DXN(i)$, sử dụng kết hợp cạnh dạng cây (tree edges) và cạnh tắt (shortcut edges).
• Mạng Pagoda động cho nút đồng nhất: Thiết lập các giao thức xử lý thao tác gia nhập (join) và rời mạng (leave) ở chế độ cô lập (isolated) và đồng thời (concurrent), đảm bảo đường kính và bậc nút luôn duy trì ở mức logarit mà không cần tái cấu trúc toàn cục.
• Mạng Pagoda cho nút không đồng nhất: Mở rộng cấu trúc để tích hợp các nút có năng lực băng thông khác nhau mà không làm nghẽn các nút yếu.
• Đa hướng đồng thời (Concurrent Multicasting): Giải quyết bài toán luồng đa hướng đồng thời, chuyển đổi luồng đa hướng thành các cây phát thanh (multicast trees) và quản lý nút động thông qua cơ chế "nhà ảo" (virtual homes).

Chương 6: P2P Networks: Supervised P2P Systems (Mạng P2P: Hệ thống P2P có giám sát)

Chương 6 đề xuất một khung lý thuyết tổng quát cho hệ thống P2P có giám sát (supervised peer-to-peer systems), trong đó máy chủ chỉ thực hiện một lượng nhỏ tác vụ điều phối nhãn, còn việc truyền dữ liệu diễn ra trực tiếp giữa các peer.

• Khung phương pháp luận hợp nhất: Kết hợp 3 kỹ thuật cốt lõi:
  1. Kỹ thuật phân rã phân cấp (hierarchical decomposition).
  2. Kỹ thuật liên tục - rời rạc (continuous-discrete).
  3. Kỹ thuật gán nhãn đệ quy (recursive labeling).
• Hiện thực hóa topo: Ứng dụng khung này để xây dựng Mạng Hypercube động và Mạng de Bruijn động.
• Độ bền vững: Chứng minh hệ thống duy trì tính liên thông và hiệu năng định tuyến trước:
  • Mô hình lỗi ngẫu nhiên (Random Fault Model).
  • Kẻ tấn công đối nghịch bán thích ứng (Semi-adaptive Model).
  • Kẻ tấn công đối nghịch thích ứng toàn diện (Fully Adaptive Model).
• Ứng dụng: Chứng minh tính khả thi trong trò chơi trực tuyến nhiều người chơi quy mô lớn (Massive Multi-player Online Gaming - MMOG).

+-------------------------------------------------------------------------------+
| KHUNG PHƯƠNG PHÁP LUẬN CHO MẠNG P2P CÓ GIÁM SÁT (CHƯƠNG 6)                   |
+--------------------------+----------------------------------------------------+
| Thành phần kỹ thuật      | Vai trò và chức năng                               |
+--------------------------+----------------------------------------------------+
| Phân rã phân cấp         | Chia nhỏ không gian địa chỉ logic thành cây phân cấp|
| Kỹ thuật liên tục-rời rạc| Ánh xạ không gian địa chỉ liên tục vào nút rời rạc |
| Gán nhãn đệ quy          | Cập nhật nhãn định tuyến khi nút gia nhập/rời mạng |
| Kháng tấn công thích ứng | Duy trì topo trước kẻ tấn công phá hoại nút chủ đích|
+--------------------------+----------------------------------------------------+

Chương 7: Wireless Ad Hoc Networks: Model and Spanner (Mạng Ad Hoc không dây: Mô hình và Cấu trúc Spanner)

Chương 7 chỉ ra các điểm yếu của mô hình đĩa đơn vị UDG và mô hình vô tuyến gói PRN, từ đó xây dựng một mô hình truyền thông không dây mới. Mô hình này phân tách rõ ràng giữa bán kính truyền tin, bán kính can nhiễu và bán kính cảm nhận sóng mang vật lý, đồng thời mô hình hóa chính xác hiện tượng nút ẩn và nút lộ.

• Dựa trên mô hình mới, tác giả đề xuất giao thức 3 giai đoạn để xây dựng đồ thị khung xương (spanner) có mật độ hằng số (constant density spanner) dựa trên tập thống trị (dominating set):
  • Phase I (Dominating Set): Thiết lập tập thống trị mật độ hằng số.
  • Phase II (Distributed Leader Coloring): Tô màu trưởng nhóm phân tán để tránh xung đột tần số/kênh.
  • Phase III (Gateway Discovery): Tìm kiếm các nút cổng (gateways) để liên kết các nút thống trị, tạo thành cấu trúc spanner hoàn chỉnh.

Chương 8: Wireless Ad Hoc Networks: Broadcasting and Gathering (Mạng Ad Hoc không dây: Phát thanh và Thu thập thông tin)

Chương 8 ứng dụng cấu trúc spanner mật độ hằng số đã xây dựng ở Chương 7 để phát triển các thuật toán giao tiếp cấp cao:

• Phát thanh (Broadcasting): Thiết kế thuật toán phát thanh một thông điệp và phát thanh nhiều thông điệp đồng thời (multiple messages broadcasting) tối ưu về thời gian và không gây tắc nghẽn can nhiễu.
• Thu thập thông tin (Information Gathering): Xây dựng quy trình 2 giai đoạn:
  • Stage 1: Xây dựng cây thu thập $T(s)$ hướng về nút đích (sink $s$).
  • Stage 2: Thu thập và nén luồng dữ liệu trên cây $T(s)$.
• Tính chất tự ổn định (Self-stabilization): Toàn bộ các thuật toán được chứng minh có khả năng tự ổn định từ bất kỳ trạng thái khởi tạo lỗi nào, đồng thời chỉ yêu cầu dung lượng bộ nhớ lưu trữ hằng số ($O(1)$) tại mỗi nút thiết bị.

Chương 9: Conclusions (Kết luận)

Chương 9 tổng kết toàn bộ các kết quả đạt được của luận án, khẳng định tính khả thi của việc kết hợp giữa phân tích lý thuyết thuật toán và thiết kế cấu trúc mạng phủ. Đồng thời, tác giả vạch ra các hướng nghiên cứu mở rộng trong tương lai về tối ưu hóa định tuyến và an ninh mạng phân tán.

---

Kết quả và những đóng góp mới

Đóng góp mới về mặt lý luận và khoa học

1. Thuật toán tô màu đỉnh trên đồ thị có hướng: Chứng minh trên phương diện lý thuyết rằng thông tin về hướng cạnh giúp phá vỡ tính đối xứng nhanh hơn, thiết lập cận trên mới về số vòng giao tiếp cho bài toán tô $(\Delta+1)$ màu phân tán.
2. Cấu trúc P2P tiền định cho nút không đồng nhất: Thiết kế thành công topo Pagoda ($PG(d)$), giải quyết câu hỏi mở về việc xây dựng mạng P2P tiền định có khả năng tích hợp các nút có băng thông không đồng đều mà vẫn đảm bảo chặn trên logarit cho bậc đỉnh và đường kính.
3. Khung lý thuyết cho mạng P2P có giám sát: Đề xuất mô hình kết hợp giữa phân rã phân cấp, kỹ thuật liên tục - rời rạc và gán nhãn đệ quy, chứng minh hệ thống đạt độ bền vững trước kẻ tấn công đối nghịch thích ứng toàn diện (fully adaptive adversary).
4. Mô hình truyền thông không dây thực tế: Xây dựng mô hình hình học mở rộng tính đến can nhiễu và cảm nhận sóng mang, khắc phục hạn chế phi thực tế của UDG và PRN.
5. Cấu trúc Spanner và Thuật toán truyền thông tự ổn định: Phát triển giao thức tạo spanner mật độ hằng số và các thuật toán phát thanh, thu thập dữ liệu tự ổn định chỉ đòi hỏi bộ nhớ lưu trữ $O(1)$ tại mỗi nút cảm biến.

+-------------------------------------------------------------------------------+
| BẢNG TỔNG HỢP CÁC ĐÓNG GÓP KỸ THUẬT CHÍNH CỦA LUẬN ÁN                         |
+---------------------+-------------------+-------------------------------------+
| Phân hệ / Chủ đề    | Tên đóng góp      | Đặc tính kỹ thuật cốt lõi           |
+---------------------+-------------------+-------------------------------------+
| Tô màu phân tán     | Oriented Coloring | Tô (\Delta + 1) màu, phá vỡ đối     |
|                     |                   | xứng bằng hướng cạnh                |
| Mạng P2P tiền định  | Pagoda Network    | Hỗ trợ băng thông không đồng đều,   |
|                     | (PG(d))           | tối ưu đa hướng đồng thời           |
| Mạng P2P giám sát   | Unified Framework | Kháng lỗi ngẫu nhiên và kẻ tấn công |
|                     | (Hypercube/deBr.) | đối nghịch thích ứng toàn diện      |
| Mạng Ad Hoc K.Dây   | New Radio Model & | Phân tách R_t, R_i, R_s; spanner    |
|                     | Constant Spanner  | mật độ hằng số qua 3 giai đoạn      |
| Định tuyến Ad Hoc   | Broadcast & Gather| Tự ổn định (self-stabilizing),      |
|                     | Algorithms        | bộ nhớ hằng số O(1) trên mỗi nút   |
+---------------------+-------------------+-------------------------------------+

Kiến nghị và giải pháp đề xuất

• Ứng dụng mô hình mạng P2P có giám sát cho các hệ thống ứng dụng quy mô lớn đòi hỏi kiểm soát định danh và phân phối tải như trò chơi trực tuyến nhiều người chơi (MMOG) và hệ thống phân giải tên miền thế hệ mới.
• Ứng dụng cấu trúc spanner mật độ hằng số và thuật toán thu thập thông tin tự ổn định vào việc thiết kế giao thức mạng cảm biến không dây (wireless sensor networks), nơi các nút có tài nguyên năng lượng và bộ nhớ cực kỳ hạn chế.

---

Hạn chế và hướng nghiên cứu tiếp

Hạn chế từ phạm vi nghiên cứu

• Các kết quả nghiên cứu chủ yếu được xây dựng trên mô hình lý thuyết tính toán phân tán và chứng minh toán học hình thức; việc triển khai trên môi trường mạng Internet thực nghiệm thực tế với độ trễ biến động cao và mất gói ngẫu nhiên chưa được trình bày chi tiết trong phạm vi văn bản.
• Mô hình mạng P2P có giám sát vẫn duy trì một mức độ can thiệp tối thiểu từ máy chủ điều phối, do đó chưa hoàn toàn loại bỏ hoàn toàn sự phụ thuộc vào thành phần tập trung như các mạng P2P thuần túy.

Hướng nghiên cứu tiếp

• Mở rộng các thuật toán định tuyến để xử lý các kịch bản nút di chuyển với vận tốc cao liên tục trong mạng ad hoc không dây.
• Nghiên cứu cơ chế khuyến khích kinh tế (incentives for cooperation) trong mạng P2P nhằm ngăn ngừa hành vi nút bất hợp tác (free-riding).

---

Giá trị tham khảo

Luận án mang lại giá trị tham khảo học thuật chuyên sâu cho nhiều đối tượng:

• Nghiên cứu sinh và Giảng viên ngành Khoa học Máy tính / Mạng máy tính: Cung cấp cơ sở lý thuyết chuẩn mực về cấu trúc đồ thị đại số (Hypercube, de Bruijn, Butterfly), lý thuyết luồng, cùng các kỹ thuật phân tích cận xác suất (Chernoff bounds, Markov) áp dụng trong thuật toán phân tán.
• Kỹ sư thiết kế giao thức mạng P2P và Hệ thống phân tán: Cung cấp giải pháp thiết kế topo tiền định Pagoda và khung P2P có giám sát kháng tấn công thích ứng.
• Kỹ sư và nhà nghiên cứu Mạng cảm biến không dây (WSN): Cung cấp mô hình can nhiễu thực tế cùng thuật toán phát thanh và thu thập dữ liệu tự ổn định với dung lượng bộ nhớ $O(1)$.

---

Câu hỏi thường gặp

1. Cấu trúc mạng Pagoda trong Chương 5 giải quyết vấn đề gì mà các mạng P2P trước đó chưa xử lý triệt để?

Mạng Pagoda ($PG(d)$) giải quyết hai vấn đề mở: thiết kế topo mạng P2P theo phương pháp tiền định (thay vì dựa vào cấu trúc ngẫu nhiên) và khả năng tổ chức hiệu quả các nút có năng lực băng thông không đồng đều (non-uniform/heterogeneous bandwidth), đồng thời hỗ trợ tối ưu hóa bài toán đa hướng đồng thời (concurrent multicasting).

2. Mô hình truyền thông không dây mới trong Chương 7 khác gì so với mô hình Unit Disk Graph (UDG)?

Mô hình UDG giả định bán kính truyền tin và nhận tin là một hình đĩa đơn vị hoàn hảo và không phân biệt rõ can nhiễu. Mô hình mới của luận án phân tách rõ ràng 3 phạm vi vật lý: bán kính truyền ($R_t$), bán kính can nhiễu ($R_i$) và bán kính cảm nhận sóng mang vật lý ($R_s$), từ đó mô hình hóa chính xác hiện tượng nút ẩn (hidden node) và nút lộ (exposed node).

3. Khung P2P có giám sát ở Chương 6 đạt được khả năng kháng tấn công ở cấp độ nào?

Khung P2P có giám sát của luận án được chứng minh có khả năng duy trì tính liên thông và hiệu năng định tuyến trước cả lỗi ngẫu nhiên (random faults), kẻ tấn công đối nghịch bán thích ứng (semi-adaptive adversary) và kẻ tấn công đối nghịch thích ứng toàn diện (fully adaptive adversary).

4. Yêu cầu về bộ nhớ của các thuật toán phát thanh và thu thập thông tin trong Chương 8 là bao nhiêu?

Các thuật toán phát thanh và thu thập thông tin trên cấu trúc spanner trong Chương 8 đều chỉ yêu cầu dung lượng bộ nhớ hằng số ($O(1)$ storage) tại mỗi nút mạng, giúp thuật toán tương thích với các thiết bị cảm biến phần cứng giới hạn.

5. Khái niệm "độ tắc nghẽn" (Congestion) của một chiến lược định tuyến được định nghĩa như thế nào trong luận án?

Theo Mục 2.5, trong bài toán luồng đồng thời cực đại, độ tắc nghẽn $C(S)$ của nghiệm định tuyến $S$ được định nghĩa là nghịch đảo của giá trị luồng đồng thời (reciprocal of the concurrent flow value), biểu thị hệ số mà dung lượng các cạnh cần phải nhân lên để đáp ứng đầy đủ nhu cầu của tất cả các luồng hàng hóa.

---

Kết luận

Luận án tiến sĩ của Kishore Kothapalli đã giải quyết một cách có hệ thống các bài toán nền tảng về cấu trúc topo và định tuyến trong hai phân lớp mạng phủ: mạng ngang hàng P2P và mạng ad hoc không dây. Bằng việc kết hợp chặt chẽ giữa lý thuyết đồ thị, giải tích tiệm cận và thiết kế thuật toán phân tán, công trình đã đề xuất nhiều cấu trúc quan trọng như mạng tiền định Pagoda, khung P2P có giám sát bền vững trước tấn công thích ứng, cùng mô hình can nhiễu không dây thực tế đi kèm các thuật toán tự ổn định có bộ nhớ $O(1)$. Đây là một tài liệu học thuật có giá trị tham khảo cao đối với lĩnh vực tính toán phân tán và thiết kế giao thức mạng.

Trích đoạn nội dung tài liệu

Topology and Routing in Overlay Networks by Kishore Kothapalli A dissertation submitted to The Johns Hopkins University in conformity with the requirements for the degree of Doctor of Philosophy. Baltimore, Maryland June, 2006 © Kishore Kothapalli 2006 All rights reserved UMI Number: 3240749 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3240749 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Abstract In this age of information, new models of information exchange methodologies based on overlay networks are gaining popular attention. Overlay networks provide a logical interconnection topology over an existing physical network. Overlay networks offer bene- fits such as ease of implementation, flexibility, adaptability, and incremental deployability.

Due to the wide range of applications and advantages, formal study of overlay networks is required to understand the various research challenges in this context. In this thesis, we study two classes of overlay networks namely peer-to-peer networks and wireless ad hoc networks. Our focus will be along two central issues in overlay net- works: how to arrive at efficient topologies and how to provide efficient routing strategies. Peer-to-peer networks have gaineda lot of research attention in recent years for various reasons.

Despite many advances however, fundamental questions such as how to design deterministic constructions, and how to organize peers of non-uniform bandwidth have remained open. In this thesis, we answer these questions by providing a deterministic overlay topology, Pagoda, that can be used for efficient routing, data management and multicasting. Given the difficulty of arriving at good deterministic topologies in a purely decentralized manner, we also propose a unified methodology to create a large class of H overlay topologies via an approach called the supervised overlay networks. We show that this approach also has other advantages such as support for rapid peer join/leave and rapid repair.

For the case of wireless ad hoc networks, we start by providing a model for wireless communication that is much more realistic than the models that are being used in the theo- retical community. Using this model, we show how to arrive a sparse spanner construction based on dominating sets. We then use the spanner construction to provide efficient algo- rithms for broadcasting and information gathering in wireless ad hoc networks. All our algorithms are simple, self-stabilizing and require only a constant amount of storage at any node.

Thus, our algorithms are also applicable in a wide variety of scenarios such as simple sensor devices. Advisor: Professor Christian Scheideler Readers: Professor Rao Kosaraju and Professor Andreas Terzis 1H Dedicated to the memory of my mother Acknowledgements First and foremost I express my gratitude to my advisor Dr. Christian Scheideler for supporting me, and sharing many of his insights. His clarity of thought and expression, timely and sound advice have been of immense help and a huge inspiration.

Thanks are also due to the members of my thesis committee, Prof. Rao Kosaraju, Prof. James Fill, Prof. Jin Kung, and Prof.

Andreas Terzis for their valuable feedback. I wish to take this opportunity to thank my teachers, Prof. Rao Kosaraju, Prof. James Fill, Prof.

Sanjeev Saxena, and many others from whom I have benefited immensely during the course of my education. It was a rewarding experience to work with Prof. Andrea Richa, Prof. Christian Schin- delhauer, Ankur Bhargava, Chris Riley, Mark Thober, and Melih Onus.

I wish to thank Prof. Hager for his advice while working towards a qualifier project. I was lucky to have made some good friends at the Johns Hopkins University Ankur Kapoor, Paritosh Shroff, Sandeep Sarat, Debraj Ghosh, and many others. For all the good times, thank you all.

Thanks also to friends from my earlier days at Warangal and Kanpur, especially Kiran Tati, Sriram Gorti, Sreekanth Bharatham, and Subbarao Denduluri. Last but not the least, thanks are also due to my family members whose constant sup- port and encouragement could always be counted upon even under difficult circumstances. VI Contents Abstract ii Acknowl edgements FUABKDWNHe List of Figures 1 Introduction 1.1 Models of Computing © 6. ee ee ha l.hà kh kia 1.2 Client-server computing.

ch hư hà ha 1.3 Peer-to-peercompUng.2 Why Logical Network§?. gi kh hư Ha. Provisioning Special Featife$S.2 Virtual Private Networks (VPNs). 6-0 he —¬oCŒ*`2xœ©) 1.4 Internet Transparency and Symmetry ee.

Overlay Networks - A Brief HistOrV.1 Peer-to-Peer Networks 2. kh hà ha 1.2 Wireless Ad Hoc Networks.5 Relation to other areas ww.2 Content Distribution Network (CDN) .6 Organization of the theSÌS. Q Q Q Q HH hở 2 Terminology and Notation 2.2 Basic Probability kh kh 2.3 Basic Graph Theory. 0 gi hà Kha 2.4 Basic Network Topologies 2.5 Basic Routing Theory.

gà gà kh ưa Vii 3 Our Contributions 35 3.1 Key Qu€eSULONS.2 Vertex COlOFÌNE. cuc Q HQ ee ko ta 37 3.1 Deterministic Construction for Heterogeneous Pees.2 Supervised Peer-to-peer Systems.4 Wireless Ad Hoc Networks «00. ee ee ee ơn kg 42 Vertex Coloring 45 Vertex Coloring 46 4. nh HH hà kg gà ki va 47 4.

Model and Defniions. ch Hà Hà kg kg va xa 52 4. Quà kh at 53 4.4 Summary of ourapproach .5 Organization of the Chapter. gà kg ga kia tia 56 4.3 Upper Bound for Constant Degree Oriented Graphs.4 Upper Bound for Arbitrary Oriented Graphs.3 FurtherImprovements hà kia kia .5 Chapter Summary and Acknowledgements.

ee ee ee es 74 II Peer-to-peer Overlay Networks P2P Networks: Deterministic Constructions 5.1 Overlay networks for uniform p€ETS.2 Overlay networks for non-uniform peerSs.3 Overlay networks for multicasting .5 ee Restofthe Chapter.2 kh kh kg The static Pagoda network 2.3 The dynamic Pagoda network for uniform nodes.1 Isolated Join and Leave operations. ee ee he 5.2 Concurrent Join and Leave OperalonS.4 The dynamic Pagoda network for non-uniform nodes.1 Join and Leave operations 2. cu eeki ki ha vii 5.1 The concurrent multicast problem. cv vu ee ee 5.2 Routing SHA[BY.

Q Q Q HQ HH ee 5.4 Tuming multicast flows into trees 2. ee ee ee 5.6 Multicasting in a dynamic setting: vitualhomes.6 Chapter summary and acknowledgem€nñtS. eee et eee ees P2P Networks: Supervised P2P Systems 115 6. cv kg Q kg k va 115 6.

cv ru ee 116 6. 0Q Q LH ng ee 118 6.2 A general framework for supervised peer-to-peer systems .1 The hierarchical decomposition technique.2 The continuous-discrete technique.3 The recursive labeling technique. ee ee ee ee ee 122 6.4 Putting all pieces together. cu gi kh k k kg 128 6.

Q Dynamic Hypercube NetwOorkK. ee he ee ee ee.2 Dynamic de Bruijn Network ©. gà kh kh ki k kg 131 6.1 Concurrent Join/Leave ÔperatOnS.5 Robustness against Random Faults.1 The Random FautModel.6 Robustness against Adaptive Adversarial Attaeks.1 The Semi-adaptive Model .2 The Fully Adaptive Model. ee ee ee 146 6.

ch ee ee 149 6. Massive Multi-player Online Gaming. kh hà kh ki ai Hi. ch 151 III Wireless Ad hoc Networks 7 Wireless Ad Hoc Networks: Model and Spanner 7.

c c c c c c vu gà kg gà VN k VN xà sa 7.2 Models of Wireless NetfWOTKS. 0L Q Q Q LH vn ng kg k kg va 7.1 Unit Disk Graph (UDG) model.2 Packet Radio Network (PRN) model.3 A new model for wireless communication. ee ee ix 7.2 Transmission range, interference range, and physical carrier sensing range. kg kh à kà Ha 163 7.

Constant density dominating S€L.2 Constant density SDAnDET. Q Q Q HQ ee ee 169 7.6 Overview of spanner protOCol.7 Phase I: dominating SeE. gà na 182 ra.8 Constant density SDARRET. uc Q Q ee ko 183 7.1 Phase II - Distributed Leader Coloing.2 Phase III - Gateway Discovery.9 Chapter Summary and Acknowledgements.

193 8 Wireless Ad Hoc Networks: Broadcasting and Gathering 195 8. kg cà kg cv kg kg ki kg RA 196 83 RelatedwOrK. cà kg kg xà kia ky va 199 1° 6. uc co cu gà k ki KT VY 204 8.

ee ee va 207 8.6 Broadcasting Multiple Messages. cà kh KV 209 8. co cu HH HQ hà gi. ch HH HH HQ ga kg 212 8.1 ee eee Stage 1: Building Gathering TreeT(s) .2 Stage 2: Gathering on T(s) 2.3 Self-stabilization HQ kg ©.8 Chapter Summary and Acknowledgements 222 9 Conclusions 223 Bibliography 225 Vita 244 List of Figures 1] A logical (overlay) netWOTK.2 Figure (a) shows a client-server model of computing where the server handles all the requests of the clients.

Figure (b) shows a supervised peer-to-peer system where the server has certain limited functionality and clients (peers) are allowed to com- municate with each other. The bold lines indicate the client-client communication links. Figure (c) shows a pure peer-to-peer system where there is no central server. The figure is based on Figure 2.

ee ee ees 1.3 A CDN in operation. The figure is based on [120, Figure 9. 21 The structure of atree, 2.2 The structure of M(m,1), T(4,2), and M(2,3).3 The structure of BF(3).4 The structure of DB(2,2) and DB(2,3).1 Figure shows that edge orientations can be provided naturally in many scenarios.2 Orientation helps in symmetry breaking. In Figure (a) both v and w choose the same color.

In (b), for existing algorithms both remain uncolored whereas in (c), when using orientation, node v may getcolored.3 Coloring constant degree oriented graphs by random choices.4 Connected component of uncolored nodes. The number at the uncolored nodes within the connected component gives the layer number they belongto.5 Algorithm for any node u.6 Improved algorithm for Phasel. es ee ee 70 5.1 kg ki va The structure of 2B(3).2 The structure of PG(2) consisting of DXN(0), DXN(1) and DXN(2). The tree edges are shown in dashed lines and the shortcut edges are shown in dotted lines.3 Figure (a) shows the operation of stage | and (b) shows the operation of stage 2.1 The decomposition tree ford = 2.2 Logical organization of nodes into five sets.

The number against node position indicates the set to which the node belongsto,.3 Physical organization of nodes into five SE. ee es 7Ì Neighborhood of node u according to UDG model.2 Neighborhood of node u according toPRN model.3 The general transmission, interference model.4 Figure in (a) shows the hidden node problem where nodes A and C cannot send to B at the same time and (b) shows the exposed node problem where C’ cannot sent packets to 2 while B is sending to A as Ở senses busy medium though A is out of the transmission rangeofC.5 Properties of the new model for wireless communication.6 Two consecutive rounds of the spanner protocol. ee ee es 77 The spanner of the original network, ©.1 An example network with node s the source of the broadcast.- Xii Chapter 1 Introduction As the age of information has dawned upon us, it has become imperative that efficient informa- tion exchange methodologies be studied. While traditional network models certainly broadened the knowledge and understanding of information exchange, new and emerging paradigms require a dif- ferent approach.

Overlay networks, which are logical networks over an existing network, are becom- ing more common. Overlay networks supporting a range of functionality such as grid computing, file sharing, sensor networks, and wireless ad hoc networks are being studied heavily. Evidenced by the success of early applications using overlay networks such as Gnutella [50], and distributed.