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
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.
denote the minimum infection time of a tree with n nodes whose root is infected. We are interested in computing 
.
.
trong mạng có khả năng truyền 
packets một giây. (Trong bài trước ta giả sử 
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à 
. 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à 
để 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ị 
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ị.)
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 
chuyể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ừ 
đến 
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 
.
. 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?
. 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 
đế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 
thì Bob sẽ giải mã đúng.
(ví dụ 0.001%), nếu ![\mbox{Prob}[|p-q|\leq \epsilon] \geq 1-\theta](/blog/latexrender/pictures/2bddce3a1ea0fb460dda00d97574df7e.gif "\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à 
trong đó ![\mbox{Prob}[X_i = 1] = p](/blog/latexrender/pictures/54d6f70e2be76a286cbbc7a93e6fb4f8.gif "\mbox{Prob}[X_i = 1] = p")
và ![\mbox{Prob}[X_i = 0] = 1-p](/blog/latexrender/pictures/ac4bd99f80df26c4d0d45f76891e76b8.gif "\mbox{Prob}[X_i = 0] = 1-p")
, với ![\[\mbox{E}\left[ \sum_{i=1}^t X_i \right] = tp.\]](/blog/latexrender/pictures/3db95e4fdfb684d81ece7a899c1810c3.gif "\[\mbox{E}\left[ \sum_{i=1}^t X_i \right] = tp.\]")
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.
, 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}](/blog/latexrender/pictures/bf30cfe285ec1a78c14b4b296c8041b8.gif "\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 \leq (1-\delta)tp\right] \leq e^{-tp\delta^2/2}](/blog/latexrender/pictures/f7f5748edc6f5113149329830ec86e13.gif "\mbox{Prob}\left[\sum_{i=1}^tX_i \leq (1-\delta)tp\right] \leq e^{-tp\delta^2/2}")
tiến ra vô cùng, khả năng mà 
bằng giá trị của bit thứ 
mà Bob nhận được. Như vậy, sau khi Alice gửi 
. 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)}](/blog/latexrender/pictures/86885b098e4a8448ce2202b46a5f826d.gif "\mbox{Prob}\left[|q-p| \leq \epsilon\right] \geq 1 – 2e^{-t\epsilon^2/(3p)}")
là Bob có sai số mong muốn.