Lý thuyết mã mạng (1)
Ngô Quang Hưng | 10 tháng 02, 2006 | 
Bản để in
Lý thuyết thông tin và mạng máy tính hiển nhiên là có phần giao rất lớn, tương hỗ, bổ túc cho nhau. Trong khoảng 5 năm trở lại đây, một nhánh nghiên cứu cực kỳ thú vị đang càng lúc càng thu hút nhiều nhà nghiên cứu từ cả lý thuyết thông tin (đặc biệt là lý thuyết mã - coding theory) và mạng máy tính. Tên gọi của nhánh nghiên cứu mới này là network coding (tạm dịch là mã mạng). Khởi đầu từ bài báo
R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network Information Flow“, (IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000),
đến nay network coding đã có ứng dụng ở rất nhiều nơi, từ wireless communications, content distribution, đến multicasting, vân vân.
Trong loạt bài này, ta sẽ duyệt qua các ý tưởng cơ bản của lý thuyết coding cổ điển (error-detecting, error-correcting codes), các routing algorithms trên Internet, và mối liên hệ của chúng đến network coding.
Để giới thiệu về network coding, hãy xét ví dụ đơn giản sau đây:
Nodes trên cùng muốn gửi 2 bits dữ liệu x và y đến cả hai nodes phía dưới (multicasting) trong thời gian nhanh nhất. Dễ thấy rằng phương pháp truyền trong hình là tối ưu, giả sử rằng tốc độ truyền trên các cạnh của đồ thị là bằng nhau. Ví dụ này dẫn đến ý tưởng sau đây:
Nếu ta cho phép các nodes ở giữa (các routers trên Internet chẳng hạn) tham gia thay đổi (xẻ đôi, trộn) các gói dữ liệu, thì có khả năng sẽ tiết kiệm được bandwidth, delay, và các tài nguyên khác trong mạng.
Khi làm nghiên cứu, sau khi phác thảo ý tưởng cơ bản, bước kế tiếp sẽ là formalize ý tưởng này. Quá trình formalization sẽ dẫn ta đến một vài bài toán tuyệt đẹp, liên quan đến đại số trừu tượng, đại số tuyến tính, các ma trận chưa hoàn tất, network flow, và nhiều nhánh khác.