Lý thuyết tính toán trên mạng
Bản nháp báo cáo của một workshop do NSF tài trợ.
Bản nháp báo cáo của một workshop do NSF tài trợ.
Talk của Nick Harvey (MIT), talk của Baochun Li (Toronto), talk của Yunnan Wu (Princeton). Trong đó talk của Baochun Li hay nhất.
Tôi sẽ viết tiếp chuỗi bài về lý thuyết mã mạng trong vài tuần tới.
Matthias Grossglauser ghi lại một danh sách 10 bài báo về network models tốt nhất (theo Matthias) đến nay.
NY Times vừa có bài cho biết tổng số spam emails 6 tháng vừa qua đã tăng gấp đôi. Hiện nay hơn 90% emails là thư rác. Điều này hoàn toàn chính xác trong hộp thư của tôi.
Bài báo liệt kê nhiều “phương thức mới” mà bọn spammers dùng để gửi spam mails. Thật ra một số phương thức này cũ rồi, ví dụ chuyện dùng botnets để gửi. Một trong các phương thức mới mà tôi chú ý trong mailbox của mình gần đây là bọn nó dùng hình ảnh thay vì texts để tránh các loại bộ lọc từ khóa. Như vậy các spam filters sẽ từ từ phải dùng các kỹ thuật xử lý ảnh phức tạp và tốn tài nguyên, thay vì một dạng bayesian filter thô sơ dựa trên nội dung như Paul Graham đã đề nghị. Ví dụ này cho thấy không thể chống spam emails bằng cách thiết kế các filters tốt hơn được, vì như thế là không nhổ cỏ tận gốc.
Như thế nào là nhổ cỏ tận gốc? Có vài giải pháp:
Well, not anymore. Many of the messages in the latest spam wave promote penny stocks — part of a scheme that antispam researchers call the “pump and dump.” Spammers buy the inexpensive stock of an obscure company and send out messages hyping it. They sell their shares when the gullible masses respond and snap up the stock. No links to Web sites are needed in the messages. Though the scam sounds obvious, a joint study by researchers at Purdue University and Oxford University this summer found that spam stock cons work. Enough recipients buy the stock that spammers can make a 5 percent to 6 percent return in two days, the study concluded.
Tóm lại, nếu các bạn nghĩ ra một giao thức truyền thông người-đến-người tiện lợi và hiệu quả như emails, nhưng lại không hoặc ít bị spams, thì bạn nhiều khả năng sẽ thành Page/Brin mới.
Bandwidth-delay product là tích của bandwidth với delay trên một đường kết nối mạng. (Đôi khi người ta dùng round-trip-delay, nhưng cái đó không quan trọng cho thảo luận này.) Ví dụ: một đường DSL bình thường có delay khoảng 200ms, với bandwidth 1 Mbps sẽ có BDP = 25KB. (Ta có thể chạy traceroute từ máy ở nhà để tìm BDP của connection của mình.)
Như vậy, nếu ta gửi data liên tục thì sẽ luôn có 25KB dữ liệu nằm trên cái link từ máy của ta đến cái DSLAM của ISP. Trên Internet hiện nay có khoảng 440 triệu hosts. Nếu mỗi host đều dùng DSL với BDP như trên thì tại một thời điểm bất kỳ có đến 25KB x 440 triệu = 11 nghìn Giga-bytes dữ liệu có thể tồn tại trên các đường truyền. Đây là ước lượng rất bảo thủ, vì ta chỉ tính BDP từ các hosts đến máy gần nhất của ISP, chưa tính đến BDP của các liên kết giữa các routers/switches của các ISP. Bộ xương sống của Internet có capacity rất cao, và thường được over-provisioned. Ngoài ra ta còn chưa tính đến BDP của các liên kết không dây, cao hơn liên kết có dây rất nhiều (vì delay cao hơn).
Tưởng tượng nếu bạn có thể viết một chương trình gửi packets cho chạy lòng vòng trên Internet, khi nào cần thì “kéo” packets về máy mình. Và như thế nghiễm nhiên ta có một bộ nhớ 11 nghìn GB :-).
Ý tưởng dùng communication links làm bộ nhớ nghe thú vị nhưng có vẻ … vô dụng?
Không phải thế. Trong các mạng quang, để tránh quá trình rất chậm chạp của việc chuyển tín hiệu quang thành tín hiệu điện (O-E-O conversion), người ta dùng fiber delay lines làm buffer. Ý tưởng chính là dùng các cáp quang rất dài để “giữ” tín hiệu trong đó như là một buffer thật sự! Như thế, ta có thể thiết kế all-optical-networks mà lại có chức năng packet switching như mạng IP thông thường.
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
trong mạng có khả năng truyền
packets một giây. (Trong bài trước ta giả sử
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
bằng
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ỳ
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
của min-cut giữa
và
. 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à
. 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à 
Đị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:

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.
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
.
Báo cáo sau một workshop của NSF.
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.
Xin viết kỹ hơn về phương pháp giải mã của Bob cho bài toán đang xét. Về căn bản, Alice muốn gửi cho Bob con số
. Với chiến lược đã nêu, tỉ lệ q của số bit 1 trên tổng số bit nhận được sẽ gần với p nhưng không có gì đảm bảo nó sẽ bằng p. Hơn nữa, làm thế nào ta biết được là q sẽ gần với p?
Trước hết, ta xét vấn đề giải mã. Con số p Alice cần gửi là một bội số của
. Có tất cả
vị trí từ 0 đến 1 mà p có thể nằm. Các vị trí này cách đều nhau một khoảng bằng
, từ
đến
. Phương pháp giải mã của Bob rất đơn giản: tính tỉ lệ q như đã nêu, sau đó làm tròn nó về bội số gần nhất của
. Như vậy, miễn là
thì Bob sẽ giải mã đúng.
Cho trước một sai số
(ví dụ 0.001%), nếu
thì Bob sẽ giải mã sai với xác suất nhiều nhất là
. Để ước lượng xác suất này, ta dùng chặn Chernoff. Trong bài giảng ở đây, tôi có ghi lại chặn Chernoff ở một dạng tương đối mạnh. Với bài toán của chúng ta thì ta chỉ cần một dạng đơn giản của chặn này.
Giả sử ta có các biến ngẫu nhiên
trong đó
và
, với
là một xác suất cho trước. Dễ thấy rằng
![\[\mbox{E}\left[ \sum_{i=1}^t X_i \right] = tp.\] \[\mbox{E}\left[ \sum_{i=1}^t X_i \right] = tp.\]](/blog/latexrender/pictures/3db95e4fdfb684d81ece7a899c1810c3.gif)
nằm xa expected value
. Phân bố của tổng này có hai cái “đuôi” mỏng ở hai đầu, còn lại tập trung vào gần expected value (giống như hình ngọn núi), gọi là hiện tượng concentration.
Cho trước
, Chernoff’s bound cho đuôi trên (upper tail) có thể viết như sau:
![\mbox{Prob}\left[\sum_{i=1}^tX_i \geq (1+\delta)tp\right] \leq e^{-tp\delta^2/3} \mbox{Prob}\left[\sum_{i=1}^tX_i \geq (1+\delta)tp\right] \leq e^{-tp\delta^2/3}](/blog/latexrender/pictures/bf30cfe285ec1a78c14b4b296c8041b8.gif)
![\mbox{Prob}\left[\sum_{i=1}^tX_i \leq (1-\delta)tp\right] \leq e^{-tp\delta^2/2} \mbox{Prob}\left[\sum_{i=1}^tX_i \leq (1-\delta)tp\right] \leq e^{-tp\delta^2/2}](/blog/latexrender/pictures/f7f5748edc6f5113149329830ec86e13.gif)
tiến ra vô cùng, khả năng mà
nằm xa trung tâm tiến đến
theo hàm mũ (exponentially reduced).
Trở lại bài toán của chúng ta. Đặt
bằng giá trị của bit thứ
mà Bob nhận được. Như vậy, sau khi Alice gửi
bits, ta có
. Dùng chặn Chernoff, đặt
(bỏ qua trường hợp tầm thường khi
), ta có
![\mbox{Prob}\left[|q-p| \leq \epsilon\right] \geq 1 - 2e^{-t\epsilon^2/(3p)} \mbox{Prob}\left[|q-p| \leq \epsilon\right] \geq 1 - 2e^{-t\epsilon^2/(3p)}](/blog/latexrender/pictures/cacc090fa6302e4224d68114c277f60c.gif)
là Bob có sai số mong muốn.
Tiếp tục với câu hỏi cực kỳ thú vị lần trước.
Giả sử Bob biết n, và giả sử chuỗi nhị phân C có các bits
. Gọi c là số nguyên có biểu diễn nhị phân là C. Ví dụ, nếu C = 10110 thì c = 22. Chiến lược của Alice như sau: mỗi lần gửi, gửi bit 1 với xác suất
, và gửi bit 0 với xác suất 1-p. Với chiến lược này, Alice không cần phải nhớ xem mình đã gửi bit gì. Sau khi đã gửi thật nhiều bits, Bob tính tỉ lệ q của số bits 1 trên tổng số bits mà Bob đã nhận. Tỉ lệ này sẽ tiến đến p khi tổng số bits nhận được tiến đến vô cùng. Ta có thể dùng Chernoff bound để tính cụ thể xác suất mà p và q nằm trong vòng
của nhau là bao nhiêu. Hơn thế nữa, ta có thể ép xác suất
lớn tùy ý.
Thật ra thì ta không cần
nhỏ lắm, chỉ cần khoảng
là đủ. Tóm lại, khi tổng số bits Alice gửi tiến đến vô cùng, thì xác suất Bob giải mã được chuỗi C tiến đến 1. Đó là lời giải cho trường hợp Bob biết trước n.
Hiện nay, dịch cúm gà đã lan đến 10 tỉnh thành của Việt Nam và đã lan đến nhiều quốc gia trên thế giới. Chính phủ Mỹ đã thông qua kế hoạch 7.1 tỉ đô để chiến đấu với cúm gà. Cũng may mắn cho dân Mỹ là mùa Lễ Tạ Ơn này vẫn còn có thể ăn gà tây vì DƯỜNG NHƯ cúm gà vẫn chưa đến được Mỹ. Chắc là vì mùa đông sắp đến, bọn chim di cư chỉ có bay về gần đường xích đạo?! Ôi, tạ ơn Mùa Đông!
Liệu ta có thể trả lời câu hỏi: Tỉnh thành nào có nhiều khả năng phát cúm gà nhất trong thời gian sắp đến ? Cấp độ vĩ mô hơn là quốc gia nào có nhiều khả năng phát cúm gà nhất. Dĩ nhiên mọi địa phương, mọi quốc gia đều phải đề phòng, ngăn chặn thật cẩn thận, nhưng nếu biết được địa điểm tiềm năng mà cúm gà sẽ ghé đến, người ta có thể tập trung nguồn lực mạnh mẽ hơn để dập tắt cúm. Để tìm câu trả lời, ta thử liếc mắt sơ sơ qua lý thuyết đồ thị xem sao!
Nếu xem các tỉnh thành của nước Việt Nam chúng ta là các đỉnh, còn những đường lối mà cúm gà có thể đi qua (đường giao thông, chim di cư …) là các cạnh thì ta có một đồ thị. Trên đồ thị này, ta có thể ước lượng được khả năng nhiễm cúm của một đỉnh khi đỉnh lân cận của nó bị nhiễm là bao nhiêu. Vậy cho trước một số đỉnh đã bị nhiễm cúm, ta có thể tính được xác suất để một đỉnh khác sẽ nhiễm cúm sau một thời gian T hay không?
Đây cũng là một bài toán hay trong lý thuyết đồ thị và có ứng dụng trong an ninh mạng. Nếu thay cúm gà bằng mấy con worm, và nước Việt Nam bằng một hệ thống mạng thì ta có bài toán: Biết trước một số máy tính trong mạng bị dính sâu, sau một thời gian, ta có ước lượng được khả năng để một máy tính khác cũng bị dính đòn hay không. Hiện đã có một số cách để mô hình hóa bài toán này, kể cả dùng đến mô hình của sinh thái học, nhưng vẫn chưa có cái nào hiệu quả. Nguyên nhân chủ yếu là vì không xem xét được hình dạng của mạng, do đó chỉ có thể tính được số lượng bị nhiễm chứ không biết được cụ thể đỉnh nào bị nhiễm.
Nhìn vào tình hình dịch bệnh như hiện nay, nếu ta có thể giải quyết được triệt để bài toán trên thì thật là “công đức vô lượng”. Dĩ nhiên còn nhiều yếu tố khác nữa để có thể khống chế và tiêu diệt được một cơn dịch nguy hiểm, chỉ một bài toán đồ thị thôi thì không thể được gì. Nhưng thật ra, nếu giải được bài toán mấy con worm thì ta cũng có thể trở nên “nổi tiếng nhưng được ít người biết đến” rồi nhỉ ?!
___________________________________________
Xin cám ơn anh Hà Trần Đức vì mấy buổi nói chuyện về worm :-).
Đọc các bài báo về IP traceback, tôi vừa học được bài toán tuyệt đẹp sau đây:
Alice có một chuỗi C gồm n bits nhị phân cần gửi cho Bob. Tuy nhiên, mỗi lần Alice chỉ có thể gửi 1 bit và gửi xong thì Alice quên béng mất là mình đã gửi bit gì (hay bit nào). Thiết kế một protocol để Alice có thể gửi C cho Bob.
Chú thích: Alice có thể gửi bao nhiêu bits cho Bob tùy ý, miễn là trong giới hạn các ràng buộc trên. Giải bài toán trong hai trường hợp: (i) Bob biết trước n bằng bao nhiêu, và (ii) Bob không biết cả n luôn.
Impossible? Tựa đề của post đã có gợi ý.
Tuần rồi tòa đã chấp nhận cho SBC mua AT&T, và Verizon mua MCI. Tiếng Anh có câu “life goes full circle” quả là đúng, SBC hồi xưa là một công ty con bị tách ra từ chàng khổng lồ AT&T. Thế giới các telecom carriers mấy năm gần đây xẻ đôi, hợp lại, X mua Y, A mua B, loạn hết cả lên.
Trong một cuộc phỏng vấn Edward Whitacre, CEO của SBC, có một đoạn rất thú vị:
Anh chàng CEO này phát biểu linh tinh quá đáng. Tuy nhiên, một trong những đề tài nghiên cứu “nóng” hiện nay của mạng máy tính là cách tính cước phí của các ISP. Khi vấn đề tính cước được giải quyết sơ bộ thì các phát biểu như trên sẽ biến dần đi.
Hầu như năm nào ở SIGCOMM, INFOCOM cũng có các bài nghiên cứu về Internet pricing scheme. Giáo sư Andrew Odlyzko viết khá nhiều về “kinh tế mạng“. Nhưng đến nay thì một giải pháp đơn giản như tính tiền theo tổng số bytes gửi lên mạng cũng chưa được hiện thực hóa. Các ISPs vừa muốn làm bánh, vừa muốn ăn bánh. Đó là vấn đề chính. Dĩ nhiên đây cũng là một trong những vấn đề căn cốt khi thiết kế lại Internet.