Nói thêm một chút về định lý của Ahlswede-Cai-Li-Yeung giới thiệu trong bài trước. Ta xét trường hợp tổng quát hơn một chút: mỗi cạnh
e
trong mạng có khả năng truyền
C(e)
packets một giây. (Trong bài trước ta giả sử
C(e)
bằng 1, thật ra chẳng khác nhau gì vì có thể thay một cạnh với băng thông
C(e)
bằng
C(e)
cạnh mỗi cạnh có băng thông bằng 1.) Định lý phát biểu như sau:
Tốc độ multicast tối đa từ source đến tất cả các sinks bằng với capacity nhỏ nhất của các minimum-cuts giữa source và một sink bất kỳ.
Xét một sink bất kỳ
t_i
nào đó. Định lý max-flow min-cut nói rằng flow lớn nhất từ source đến sink này bằng với capacity
Cap(s, t_i)
của min-cut giữa
s
và
t_i
. Nghĩa là nếu nguồn chỉ truyền dữ liệu đến một mình sink này, thì tốc độ tối đa là
Cap(s,t_i)
. Như vậy, khi multicast đến tất cả các sinks cùng một lúc, tốc độ lớn nhất có thể có là
\min_i Cap(s, t_i)
Định lý trên nói rằng ta có thể đạt tới cận trên này dùng network coding. Xem ví dụ (ảnh) trong bài đầu tiên, dễ thấy rằng nếu không cho dùng network coding thì ta không thể nào đạt tới cận trên này được:
Với network coding, ta nhận 2 bits x và y sau 2 đơn vị thời gian. Nếu không dùng network coding, tốc độ truyền chỉ có thể tối đa là 2 bits trong 3 đơn vị thời gian.
Tốc độ truyền tối đa trong mạng máy tính thường được gọi là throughput. Điểm cực kỳ thú vị là: network coding cho phép ta đạt đến throughput lớn nhất cho bài multicast và có thể giải bài toán tìm cách truyền tốt nhất trong polynomial time, trong khi đó nếu không dùng network coding thì bài toán tìm các multicast trees cho throughputs lớn nhất là NP-hard. Khi không dùng network coding, bài toán này có thể được formulated như bài toán Steiner Tree Packing, được chứng minh NP-hard trong bài báo Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour, Packing Steiner Trees, SODA 2003.
Một bài báo khác gần đây so sánh throughput của network coding và Steiner Tree Packing: Y. Wu, P. A. Chou, and K. Jain. A comparison of network coding and tree packing. ISIT, 2004. Kết quả cho thấy, trong 6 cấu hình mạng khác nhau của 6 ISPs, thuật toán xấp xỉ Tree Packing của họ có performance khá gần với network coding. Tuy nhiên network coding vẫn có lợi ở việc tận dụng tài nguyên tốt hơn.
9 Comments
Hinh nhu Steiner tree packing duoc biet la NP hard tu lau lam roi. Lap Chi Lau moi FOCS 05, moi dua ra mot constant approximation cho bai toan’ nay`. Va hinh nhu duoc best student paper thi phai.
Co conjecture la` network coding trong bai toan single source nhu cua Ahlswede-Cai-Li-Yeung thi lam tang throughput, nhung trong bai toan multi source multi sink thi through put hoan toan giong voi truong hop khong dung throughput.
Viet nhan chu cuoi cung la` coding, ma ko sao sua lai duoc. Bu’t sa ga chet’:)
Cảm ơn bạn Thanh. Đúng là tôi viết ẩu, bài Steiner Tree packing đã có từ lâu trong ngữ cảnh VLSI design. Sẽ sửa lại post cho đúng.
Bạn có thể cho biết ai đã conjecture (vụ multi-source multi-sink) không? Tôi đang đọc các bài báo về đề tài này. Thanks!
Hinh nhu la paper cua Bobby Kleinberg SODA 06
http://theory.lcs.mit.edu/~rdk/pubs_chron.html
La` cap nha^.t nhat, khong ro~ ho^.i do’ co viet conjecture o trong paper do’ khong, co the la paper truoc’ do’. Khong nho ro~ lam’.
Loạt bài này rất tuyệt. Sao không thấy anh HƯNG post tiếp nhỉ.
ANh Hưng có demo các bài liên quan đến network coding này kô ?
Trong ns-2 không hỗ trợ phần này .
Thanks
Tôi sẽ viết tiếp chứ, khi rảnh rỗi hơn một chút (Thanksgiving chẳng hạn). Demo nghĩa là sao? Nếu bạn tìm danh sách các papers liên quan đến network coding thì xem phần 1 của chuỗi bài này, có link đến một paper collection.
OK, cám ơn anh. Em đã xem một số Link đó rồi, cám ơn anh Hưng nhiều.
À quên, ý em nói ở đây là mô phỏng đó mà.
Network Coding dung la hot topic, loat bai nay rat hay, cam on tac gia nhieu.