Thư viện bài, chuyên mục ‘Mạng máy tính’

Bài tập lập trình lớp mạng máy tính

Ngô Quang Hưng | 12 tháng 11, 2009 | Bản để in Bản để in

Thường là mỗi lần dạy lớp mạng máy tính tôi lại thiết kế một “bài tập lập trình mạng” khác nhau. Học kỳ này, bài tập là một phiên bản của BitTorrent protocol. Các sinh viên có 2 tháng để viết chương trình này. (Mấy lần trước thì là Gnutella và Kademlia, đều là các bài tập lập trình mạng tuyệt vời.)

1. Purpose and basic requirements

Project 1 hopefully have familiarized you with basic socket programming. Please check out my implementation (source) of project 1. I hope you can build on it or learn something from it. Project 2 is no longer “toyish.” You will implement a basic subset of the BitTorrent protocol, which is one of the (two) most popular P2P file sharing protocols on the Internet. BitTorrent traffic constitutes a large fraction of modern Internet traffic. If you implement the protocol correctly, your “client” should be able to download files from other BitTorrent clients “in the wild,” and there are millions of those peers.

The assignment is to be done in groups of size at most 2. You are responsible for finding your partner (if you need one), for finishing off the assignment in case your partner drops the class or backs out from completing the assignment for whatever reason. The program is to be written in C under a Unix platform such as Linux, SunOS, Solaris, or FreeBSD, or even Mac OS X. Under Windows, it is possible to develop your program with cygwin but you must make sure that:

  • Your submission compiles and runs under both Linux and Solaris/SunOS. We will test your submission on both Linux and Solaris/SunOS machines.
  • Except for C++ (which is still not at all recommended), no other language is allowed. I have good pedagogical reasons for this requirement.

For portability, please use the Makefile I provided in my Project 1 implementation, so that we can compile your program under these two platforms.


2. UBTorrent — overview of the protocol

Let’s refer to the subset of the BitTorrent protocol that we (i.e. you and I) will implement the UBTorrent protocol. It is BitTorrent with some advanced features stripped off. For simplicity, we will also name the program to be implemented ubtorrent, each instance of which is called a UBTorrent peer, or just a peer for short. For convenience, when we talk about the behavior of a particular peer, we will call it a (UBTorrent)client, to distinguish it from other peers.

The “official” BitTorrent protocol specification written by Bram Cohen is vague is some areas. Thus, I will copy materials from a more detailed specification of BitTorrent 1.0. You do not need to read the official specifications, because UBTorrent is (hopefully) simpler.

Peers collaborate to download files. Let’s say some client has a file to be shared named “Simon and Garfunkel – Sound of Silence.mp3“. Actually, let’s rename it “SS.mp3” for short. The client first needs to create a metainfo file containing information about SS.mp3. The metainfo file has the .torrent extension, and is often referred to as the “dot torrent” file of SS.mp3. The precise format of the metainfo file will be described below. Roughly, it contains the file name, keywords (if any), the URL of a program called a tracker, which is responsible for keeping track of all the peers who are collaborating in downloading SS.mp3.

Đọc tiếp toàn bài »

Chuyên mục: Mạng máy tính | Bình luận (5) »

Một bài tập lớp mạng máy tính

Ngô Quang Hưng | 21 tháng 10, 2009 | Bản để in Bản để in

Học kỳ này tôi dạy lớp mạng máy tính. Tôi thiết kế một bài tập mà cá nhân tôi rất thích vì nó chứa các thành tố của cả mạng lẫn thuật toán (quy hoạch động). Ý tưởng của bài tập này đến từ một bài báo mà anh Hà Trần Đức và tôi viết mấy năm trước. Chia sẻ bài tập này với các bạn ở đây cho vui. Do cut-and-paste, đoạn sau đây viết bằng tiếng Anh.

Problem 1. In this question, we explore how potentially a P2P design is more efficient than a central sever design for file distribution. However, to make it juicier, we will explore this issue from a computer worm propagation context.

The Slammer worm was a very famous computer worm, very destructive, infected 75000 victims within 10 minutes in January of 2003. Each instance of the worm has size 404 bytes. We will simplify the problem for the worm writer a little. Let’s assume that once an infected computer A transmitted the worm (404 bytes) to computer B, computer B is infected and thus can propagate the worm further on its own. If you were a worm writer wanting to design an infection strategy for your worm, you’ll have to do some back-of-the-envelop computation similar to this problem.

Suppose the worm writer wants to infect 1 million home computers, each of which has an ADSL connection whose upload speed is 400Kbps and whose download speed is 1.4Mbps. This population of 1 million computers is called the vulnerable population. Also suppose that the propagation delay from any machine to another machine on the Internet is 50ms.

Consider the following two scenarios:

  • Suppose initially a really fast server is infected. The server’s up-link (i.e. the link to send data to the Internet) is an OC12 link, whose speed is roughly 622 Mbps. Let the server infect each of the vulnerable hosts one by one. How long does it take until all vulnerable hosts are infected?
  • Now, suppose initially a computer with an ADSL connection as above is infected. The worm writer decides to use a P2P-type of strategy for infection. The infection strategy can be visualized as a tree, whose root is the originally infected host. A parent node, upon infected, will infect each of its children one-by-one in some order. This tree has a million and one nodes. Let T(n) denote the minimum infection time of a tree with n nodes whose root is infected. We are interested in computing T(1000001).

    – Write a recursive formula for computing T(n).

    – What is T(1000001), according to your recursive formula? (You may need to write a very short piece of code to compute this. If the code is recursive, it might never terminate. Think of a way [very simple] to write an iterative one, with a for loop.)

Problem 2. Repeat the above question with a 4 GB file instead of the 404 worm bytes.

Chuyên mục: Mạng máy tính & Thuật Toán | Bình luận »

Giao trứng cho ác

Ngô Quang Hưng | 18 tháng 05, 2009 | Bản để in Bản để in

Cập nhật 18 tháng 5:

Cuối cùng thì có vẻ như các tin tức về chủ quyền trên server đã được/bị hủy bỏ. Ví dụ như

http://211.88.5.96/cvweb/vcc/info/Article.jsp?a_no=180804&col_no=550

không còn chứa các tuyên bố chủ quyền này nọ nữa.

Chắc là domain name www.vietnamchina.gov.vn sẽ được hồi phục nay mai. Còn thiếu mỗi việc … quy trách nhiệm là đóng sổ vụ này.

Cập nhật 15 tháng 5:

Có vẻ như giải pháp bỏ DNS entry đã được thực hiện.

 > server vdc-hn01.vnn.vn
Default Server:  vdc-hn01.vnn.vn
Address:  203.162.0.11

> www.vietnamchina.gov.vn.
Server:  vdc-hn01.vnn.vn
Address:  203.162.0.11

*** vdc-hn01.vnn.vn can't find www.vietnamchina.gov.vn.: Non-existent host/domain

Nếu vào thẳng IP thì có vẻ như các công văn yêu cầu đội bạn bỏ tài liệu không có tác dụng:

http://211.88.5.96/cvweb/vcc/index.jsp

http://211.88.5.96/cvweb/vcc/info/Article.jsp?a_no=180804&col_no=550

Cũng đáng chú ý là một bình luận (số 113) của bác Trương Thái Du bên blog Osin:

Tôi tò mò vào trang web nói trên. Bất ngờ với cách dùng hai hình ảnh tượng trưng cho VN (khuê văn các) và TQ (thiên đàn). Chắc chắn người TQ đã chọn ảnh. Ý tưởng rất rõ ràng THIÊN TRIỀU và HỌC TRÒ. Chơi với TQ mà lơ tơ mơ về lịch sử và văn hóa thì hậu quả tự đồng hóa luôn nhãn tiền.

14 tháng 5
Bác Lê Tuấn Huy có công rất lớn với đất nước, phát hiên ra vụ “nằm vùng” của vietnamchina.gov.vn. Nhiều blogs khác cũng đã đăng lại tin này (Ô Sin, Linh, NVP, v.v.), cùng với một bài trên BBC Việt Ngữ.

Là dân kỹ thuật, có cái cần thử ngay:

[NQH] MFM:~$ nslookup
> set type=a
> www.vietnamchina.gov.vn
...
Non-authoritative answer:
Name:   www.vietnamchina.gov.vn
Address: 211.88.5.96
> set type=ns
> gov.vn.
Server:         24.92.226.40
Address:        24.92.226.40#53

Non-authoritative answer:
gov.vn  nameserver = d.dns-servers.vn.
gov.vn  nameserver = a.dns-servers.vn.
gov.vn  nameserver = f.dns-servers.vn.
...
> server d.dns-servers.vn
Default server: d.dns-servers.vn
Address: 203.119.44.105#53
> vietnamchina.gov.vn.
Server:         d.dns-servers.vn
Address:        203.119.44.105#53

Non-authoritative answer:
*** Can't find vietnamchina.gov.vn.: No answer

Authoritative answers can be found from:
vietnamchina.gov.vn     nameserver = hcm-server1.vnn.vn.
vietnamchina.gov.vn     nameserver = vdc-hn01.vnn.vn.

> set type=a
> server vdc-hn01.vnn.vn
Default server: vdc-hn01.vnn.vn
Address: 203.162.0.11#53
> www.vietnamchina.gov.vn.
Server:         vdc-hn01.vnn.vn
Address:        203.162.0.11#53

Name:   www.vietnamchina.gov.vn
Address: 211.88.5.96

Theo http://www.ip2location.com/free.asp thì 211.88.5.96 nằm ở Bắc Kinh. Như vậy là web server nằm ở Bắc Kinh, còn nameservers là của bọ (dĩ nhiên rồi! tên miền .vn mà).

Nếu chúng đã “muốn làm gì thì làm” với webserver thì bọ cũng phải được “muốn làm gì thì làm” với nameserver của bọ chứ: đừng trả lời DNS query cho www.vietnamchina.gov.vn là xong. Dĩ nhiên vấn đề phức tạp hơn như thế. Chẳng biết hai bên ký kết cái gì khi thành lập website này. Nhỡ khi ký rằng: “Iem bỏ entry vào name server, anh cung cấp nội dung website, chúng ta cân bằng cán cân thương mại nhé, … Nếu mà cắt hợp đồng này thì anh kiện iem” thì sao?

Do đó, bỏ cái entry này ra khỏi DNS RR, chỉ dễ dàng về mặt kỹ thuật mà thôi.

Chuyên mục: Mạng máy tính & Tin tức đó đây & Ảnh hưởng của CNTT | Bình luận (1) »

Phiên tòa P2P của thập kỷ

Ngô Quang Hưng | 04 tháng 03, 2009 | Bản để in Bản để in

17 tháng 4 này sẽ tuyên án. Trích từ một editorial của Wired:

When Swedish authorities raided The Pirate Bay and its servers in 2006 — paving the way for ongoing criminal trial that ended Tuesday — the pirates were unbowed, quickly resurrecting the site and setting their reverse-DNS to read: “hey.mpaa.and.apb.bite.my.shiny.metal.ass.thepiratebay.org.”

“Even though no one spreads more culture than we do, it is the film and music-mob that are trying to close us down,” co-founder Fredrik Neij said, in a speech outside Swedish Parliament after the raid. “This time we’re firing with the big cannons and saying, ‘In your face, Hollywood!’”

But all that swagger evaporated like salt water on a beached schooner once The Pirate Bay landed on the witness stand in Stockholm, Sweden, where the three admitted founders — and a fourth man accused of financing them — face up to two years in prison each on allegations of facilitating copyright infringement. The trial wrapped up Tuesday, and a verdict is expected in April.

In the courtroom, the defendants quickly abandoned their revolutionary, free-culture ideals in favor of the simpler philosophy embraced by criminal defendants since time immemorial: I’m Not Responsible.

Một tin khác liên quan mật thiết: Obama picks Net neutrality backer as FCC chief

Chuyên mục: Mạng máy tính & Nhân vật và sự kiện | Bình luận »

Lý thuyết tính toán trên mạng

Ngô Quang Hưng | 22 tháng 01, 2007 | Bản để in Bản để in

Bản nháp báo cáo của một workshop do NSF tài trợ.

Chuyên mục: Lý thuyết tính toán & Mạng máy tính | Bình luận (7) »

Vài bài tổng quan về cấu trúc các mạng phức tạp

Ngô Quang Hưng | 19 tháng 01, 2007 | Bản để in Bản để in

  • M. E. J. Newman, The structure and function of complex networks, SIAM Review, vol. 45, no. 2, pp. 167–256, 2003. [pdf]
  • J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845. [pdf]
  • J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006. [pdf]

Chuyên mục: Mạng máy tính & Thuật Toán | Bình luận »

Vài talks về lý thuyết mã mạng

Ngô Quang Hưng | 11 tháng 01, 2007 | Bản để in Bản để in

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.

Chuyên mục: Lý thuyết thông tin & Lý thuyết tính toán & Mạng máy tính & Thuật Toán | Bình luận (4) »

Mười bài báo về Network Models

Ngô Quang Hưng | 08 tháng 01, 2007 | Bản để in Bản để in

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.

Chuyên mục: Mạng máy tính | Bình luận »

Xì pam

Ngô Quang Hưng | 12 tháng 12, 2006 | Bản để in Bản để in

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:

  • Tử hình bọn spammers. Bắt được chú nào xử chú nấy. Bọn ACLU sẽ lồng lộn lên. Không được :-) .
  • Tử hình bọn kiếm lợi từ spam emails. Cũng có lý, nhưng cũng không xong.
  • Làm sao cho người ta không kiếm lời được từ spam emails nữa. Như thế thì phải giáo dục người dùng đừng click bậy click bạ. Chuyện này lịch sử cho thấy là không thể được trong thời gian trước mắt. Nói chung là users hoặc là rất tham, hoặc là rất ngốc, cho nên bọn nó vẫn kiếm lợi từ spam được:

    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.

  • Không dùng emails nữa. Thật ra không phải là không có lý. Ta đã bỏ telnet, ftp, thì không có lý do gì lại không bỏ cái protocol smtp rất là phiền toái và cổ lỗ sĩ này. Khổ ở chỗ, không dùng emails nữa thì dùng gì để liên lạc với nhau? Spams không chỉ có ở emails, spim chẳng hạn. Chuyển sang dùng cái gì cũng có khả năng bị spam.

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.

Chuyên mục: Mạng máy tính | Bình luận (8) »

Dùng Internet làm bộ nhớ?

Ngô Quang Hưng | 29 tháng 11, 2006 | Bản để in Bản để in

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.

Chuyên mục: Mạng máy tính | Bình luận (6) »

Lý thuyết mã mạng [3]

Ngô Quang Hưng | 02 tháng 03, 2006 | Bản để in Bản để in

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 st_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.

Chuyên mục: Lý thuyết thông tin & Mạng máy tính | Bình luận (9) »

Lý thuyết mã mạng [2]

Ngô Quang Hưng | 27 tháng 02, 2006 | Bản để in 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 G=(V,E) để mô hình một mạng máy tính. Để đơn giản hóa vấn đề, ta giả sử G 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ị G có một đỉnh s là source và một số đỉnh t_1, \dots, t_d 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à k bits, nghĩa là mỗi packet có thể được xem như một phần tử của trường \mathbb{F}_{2^k}. 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 vp input links và q output links, thì tương ứng với mỗi output link e sẽ có một hàm số f_e chuyển p input packets thành một output packet (cũng là một phần tử của trường \mathbb{F}_{2^k}) để gửi ra link e. 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 f_e đều là hàm tuyến tính (nghĩa là gói output trên cạnh e 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 v\Theta(n) 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ừ \mathbb{F}_{2^k}^{n} đến \mathbb{F}_{2^k}. Đặt N = 2^{kn} thì tổng số các hàm như vậy là bằng 2^{kN}, như vậy phải có ít nhất một hàm cần đến kN bits để miêu tả nó. Số bít kN này là hàm mũ của n.

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 k.

Chuyên mục: Lý thuyết thông tin & Mạng máy tính | Bình luận (5) »

Tương lai của mạng quang

Ngô Quang Hưng | 16 tháng 02, 2006 | Bản để in Bản để in

Báo cáo sau một workshop của NSF.

Chuyên mục: Mạng máy tính | Bình luận »

Lý thuyết mã mạng (1)

Ngô Quang Hưng | 10 tháng 02, 2006 | Bản để in 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:

Network Coding Example

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.

Chuyên mục: Lý thuyết thông tin & Mạng máy tính | Bình luận »

Sức mạnh của xác suất [3]

Ngô Quang Hưng | 17 tháng 11, 2005 | Bản để in Bản để in

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ố p = c/2^n. 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 1/2^n. Có tất cả 2^n 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 1/2^n, từ 0 đến (2^n-1)/(2^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 1/2^n. Như vậy, miễn là |p-q| \leq \epsilon \approx 1/2^{n+1} thì Bob sẽ giải mã đúng.

Cho trước một sai số \theta (ví dụ 0.001%), nếu \mbox{Prob}[|p-q|\leq \epsilon] \geq 1-\theta thì Bob sẽ giải mã sai với xác suất nhiều nhất là \theta. Để ướ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 X_1, \dots, X_t trong đó \mbox{Prob}[X_i = 1] = p\mbox{Prob}[X_i = 0] = 1-p, với p 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.\]

Các chặn Chernoff cho ta ước lượng xác suất mà \sum_{i=1}^tX_i nằm xa expected value tp. 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 \delta \in (0,1), 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}

và cho lower tail ta có
\mbox{Prob}\left[\sum_{i=1}^tX_i \leq (1-\delta)tp\right] \leq e^{-tp\delta^2/2}

Nói theo ngôn ngữ bình thường: khi t tiến ra vô cùng, khả năng mà \sum_{i=1}^tX_i nằm xa trung tâm tiến đến 0 theo hàm mũ (exponentially reduced).

Trở lại bài toán của chúng ta. Đặt X_i bằng giá trị của bit thứ i mà Bob nhận được. Như vậy, sau khi Alice gửi t bits, ta có q = \frac{\sum_{i=1}^tX_i}{t}. Dùng chặn Chernoff, đặt \delta = \epsilon/p (bỏ qua trường hợp tầm thường khi p=0), ta có

\mbox{Prob}\left[|q-p| \leq \epsilon\right] \geq 1 – 2e^{-t\epsilon^2/(3p)}

Như vậy, chỉ cần t \geq 12p \ln(2/\theta) 2^{2n} là Bob có sai số mong muốn.

Chuyên mục: Lý thuyết thông tin & Mạng máy tính & Xác suất & thống kê | Bình luận »