Lý thuyết mã mạng [2]
Ngô Quang Hưng | 27 tháng 02, 2006 | 
Bản để in
Tiếp theo bài trước, ta xét (và formalilze) một trong nhiều bài toán liên quan đến network coding.
Dùng một directed graph 
để mô hình một mạng máy tính. Để đơn giản hóa vấn đề, ta giả sử 
là acyclic graph. (Trong trường hợp cyclic, định nghĩa bài toán một cách cụ thể trở nên khó khăn hơn rất nhiều - và nói chung là người ta chưa biết nhiều về trường hợp này.) Trong đồ thị có một đỉnh 
là source và một số đỉnh 
là sinks. Ta muốn truyền dữ liệu từ source đến tất cả các sinks (multicast) trong thời gian ngắn nhất. Giả sử rằng ở mỗi đơn vị thời gian thì một đỉnh trong mạng truyền được một gói dữ liệu. (Trong trường hợp tổng quát, mỗi cạnh của mạng có thể có tốc độ truyền khác nhau, nhưng ta có thể thay một cạnh có tốc độ truyền lớn bằng nhiều cạnh đơn vị.)
Trong network coding, mỗi đỉnh trong mạng có quyền kết hợp các input packets theo cách tùy ý để gửi ra các output links. Để đơn giản, ta giả sử tất cả các packets đều có cùng kích thước là 
bits, nghĩa là mỗi packet có thể được xem như một phần tử của trường 
. Sự “kết hợp” của các inputs packets ra một output link nào đó chẳng qua là một hàm số. Ví dụ: giả sử đỉnh 
có 
input links và 
output links, thì tương ứng với mỗi output link 
sẽ có một hàm số 
chuyển input packets thành một output packet (cũng là một phần tử của trường ) để gửi ra link . Một bộ các hàm số như vậy gọi là một network code. Nếu network code cho phép các sinks giải mã các gói dữ liệu thì nó được gọi là network coding solution. Nếu tất cả các hàm đều là hàm tuyến tính (nghĩa là gói output trên cạnh là một tổ hợp tuyến tính của các gói inputs) thì ta có một linear network code.
Giả sử mỗi cạnh có thể dùng để truyền một gói dữ liệu trong một đơn vị thời gian. Định lý sau đây của R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung thật là tuyệt vời.
Tốc độ multicast tối đa từ source đến tất cả các sink bằng với capacity nhỏ nhất của các minimum-cuts giữa source và một sink.
Chú ý rằng: với mỗi một sink thì ta có một minimum cut capacity. Lấy capacity nhỏ nhất thì ra được tốc độ multicast tối đa. Định lý này là phiên bản information flow tương ứng của định lý max-flow min-cut lừng danh của Ford và Fulkerson
Tiếc rằng, định lý này (và chứng minh của nó) không xây dựng cho ta được một network coding solution. Nó chỉ cho biết là tồn tại một solution.
Ngoài ra, kể cả khi có solution, việc mô tả solution này cũng có thể cần exponential space, và như thế thì không thể dùng solution đó làm gì trên thực tế được. Để thấy điều này, giả sử đỉnh có 
input links. Mỗi hàm coding từ các input links ra một output link nào đó là một hàm số từ 
đến . Đặt 
thì tổng số các hàm như vậy là bằng 
, như vậy phải có ít nhất một hàm cần đến 
bits để miêu tả nó. Số bít này là hàm mũ của 
.
May thay, bài báo sau đây:
S.-Y. R. Li, R. W. Yeung, and N. Cai. “Linear network coding“. IEEE Transactions on Information Theory , Februray, 2003
cho ta biết là ta chỉ cần xét các hàm tuyến tính. Nghĩa là, nếu có một network coding solution thì có một solution tuyến tính với một giá trị nào đó của .
Anh Hưng vui lòng cho em xin lại link về cái định lý của Ahlswede at al. được không ạ? Link đã bị disable nên em không thể down được. Cám ơn anh Hưng.
Hải có thể download bài đó ở đây. Học kỳ này tôi có một seminar về đề tài này, các bạn có thể vào đây xem thêm tham khảo.
Cám ơn anh Hưng. Không ngờ là đề tài này lại đang hot với số lượng paper dầy đặc như thế. Em sẽ đọc và trao đổi riêng với anh Hưng, hy vọng tìm ra topic nào đó để làm.
Chào anh Hưng, em đang nghiên cứu về network coding cho mạng không dây (đặc biệt là mạng wireless mesh network - WMN). Em định sử dụng phương pháp Random linear network coding (do các tác giả Philip A. Chou, Yunnan Wu, … đề xuất) cho mô phỏng để nâng cao thông lượng (em sử dụng bộ mô phỏng Glomosim). Theo anh có những phương pháp nào là thích hợp cho mạng không dây? Em cũng gặp khó khăn trong việc cài đặt cho việc mô phỏng. Anh có thể chỉ cho em cách để tìm source code của các phương pháp này được không? Cảm ơn anh Hưng.
Tôi không bao giờ tự chạy simulations (để sinh viên làm), nên tìm simulation source code cho Glomosim thì tôi … chịu. Latdat_string có thể xem các bài network coding trên wireless networks gần đây (COPE, bài này, v.v.) xem họ setup cái simulation như thế nào.
BTW, random linear network coding chủ yếu là do nhóm MIT và Caltech làm (Tracy Ho and others).