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

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 denote the minimum infection time of a tree with n nodes whose root is infected. We are interested in computing .

  – Write a recursive formula for computing .

  – What is , 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.