When theory meets practice (in networking research)

**Kev** · 08-11-2009

Là người làm research trong lình vực theory, chắc ai cũng thắc mắc và tự hỏi (và chắc là tự trả lời luôn lol) là không biết cái mình làm ứng dụng thế nào.

Gần đây mình tình cờ đọc vnexpress thì thấy một article về kết quả của thầy (cũ) mình làm, thấy cũng vui vui. Dĩ nhiên là kết quả này đã được đănng khắp nơi trên báo nước ngoài, CNN, Nature, Science....đủ cả nhưng thấy báo Việt thì cảm giác lạ lạ.

[Only registered and activated users can see links. ]

Kết quả này bắt nguồn từ việc nghiên cứu thuần túy lý thuyết mà ra. Đây là bài báo FAST TCP: motivation, architecture, algorithms, performance
David X. Wei, Cheng Jin, Steven H. Low and Sanjay Hegde.
IEEE/ACM Transactions on Networking, 14(6):1246-1259, Dec 2006 (1.4MB)

Sau đó, Caltech implemented algorithm developed rối mang ra thi đua thì nó là 5 consecutive years world record fastest data transfer trans Atlantic.

Mình muốn nói là anh em làm theory thì nên giữ vửng hi vọng một ngày nào đó kết quả của mình cũng như vậy. Haha. No joking ví thấy mình làm mấy cái đó cũng là với PhD students thôi mà.

Side info: Bac No-Pe Khó nhà mình cũng có một số báo TON. Báo TON thì Viet students có vẻ ít ra, không biết được khoảng 10 bài trước giờ chưa.

Nếu có ai interested in topic này thì mình sẽ tiếp tục bàn nữa, nhiều ví dụ trực quan...

Nhưng ngành khác thi sao nhi? Có ai có cases nào thì đưa lên, nói chuyện chơi.

**SpringerCV** · #2 (**permalink**) 08-11-2009

Kết quả khủng khiếp nhỉ, chẳng hiểu các bác ấy cải tiến TCP kiểu mà ghê thế? Mình không hiểu lắm cái paper Kev giới thiệu vì cũng chỉ là dân amateur trong mảng này thôi. Trước có đọc ở blog KHMT bài của bác Nờ Pê Khó giới thiệu về network coding, đại khái là một big innovation cho internet. Mấy cái paper của MIT này đã thấy kết quả ác chiến lắm rồi:

[Only registered and activated users can see links. ]
[Only registered and activated users can see links. ]

Cũng là một dạng theory meets practice với thử nghiệm double TCP throughput trên một testbed khá lớn và có tiềm năng hơn thế rất nhiều. Thế nhưng kết quả của mấy bác ở Caltech này đã vượt hơn hẳn, kể cả khi áp dụng trên thực tế.

**Kev** · #3 (**permalink**) 08-11-2009

Đây là giải thích ngắn gọc trên wiki, có lẽ mình không giải thích rõ ràng hơn được nữa. Haha.

FAST TCP (also written "FastTCP") is a TCP congestion avoidance algorithm especially targeted at long-distance, high latency links, developed at the Netlab, California Institute of Technology and now being commercialized by FastSoft. It is compatible with existing TCP algorithms, requiring modification only to the computer which is sending data.

Name

The name FAST is a recursive acronym for FAST AQM Scalable TCP, where AQM stands for Active Queue Management, and TCP stands for Transmission Control Protocol.

[edit] Principles of operation

The role of congestion control is to moderate the rate at which data is transmitted, according to the capacity of the network and the rate at which other users are transmitting. Like TCP Vegas, FAST TCP[1] [2] uses queueing delay instead of loss probability as a congestion signal.

Most current congestion control algorithms detect congestion and slow down when they discover that packets are being dropped, so that the average sending rate depends on the loss probability. This has two drawbacks. First, low loss probabilities are required to sustain high data rates; in the case of TCP Reno, very low loss probabilities are required, but even new congestion avoidance algorithms such as H-TCP, BIC TCP and HSTCP require loss rates lower than those provided by most wireless wide area networks. Moreover, packet loss only provides a single bit of information about the congestion level, whereas delay is a continuous quantity and in principle provides more information about the network.

A FAST TCP flow seeks to maintain a constant number of packets in queues throughout the network. The number of packets in queues is estimated by measuring the difference between the observed round trip time (RTT) and the base RTT, defined as the round trip time when there is no queueing. The base RTT is estimated as the minimum observed RTT for the connection. If too few packets are queued, the sending rate is increased, while if too many are queued, the rate is decreased. In this respect, it is a direct descendant of TCP Vegas.

The difference between TCP Vegas and FAST TCP lies in the way in which the rate is adjusted when the number of packets stored is too small or large. TCP Vegas makes fixed size adjustments to the rate, independent of how far the current rate is from the target rate. FAST TCP makes larger steps when the system is further from equilibrium and smaller steps near equilibrium. This improves the speed of convergence and the stability.

[edit] Strengths and weaknesses

Delay-based algorithms can, in principle, maintain a constant window size, avoiding the oscillations inherent in loss-based algorithms. However, they also detect congestion earlier than loss-based algorithms, since delay corresponds to partially filled buffers, while loss results from totally filled buffers. This can be either a strength or a weakness. If the only protocol used in a network is delay-based, then the inefficiency of loss can be avoided; however, if loss-based and delay-based protocols share the network[3], then delay-based algorithms tend to be less aggressive. This can be overcome by suitable choice of parameters, leading to complex interactions studied by Tang et al.

Delay measurements are also subject to jitter as a result of operating system scheduling, or bus contention.

Whether the strengths or weaknesses prevail is not clear, and depends in large part on the particular scenario.

**Kev** · #4 (**permalink**) 08-11-2009

Cái network coding thì mình nghĩ nó là hype là chính. Nhưng hội MIT toàn dân có khả năng biến theoretical results thành practical applications nên hi vọng cũng ra được sản phẩm gì đấy để còn push network coding lên. Với lại MIT cũng là một trong những nơi khai sinh ra network coding + 2,3 ông già bên Đức của Springer (lol) nên họ cũng muốn đẩy coding lên. Bài này best paper cùa SIGCOMM, hình như tay first author có job luôn ở Stanford.

Một trong những kết quả gần đây nhất ở MIT mà ra ứng dụng là về cái Chord hashing và look-up algorithm cho P2P networks. Cái này đặc biệt là ngon vì hiện giờ P2P và content delivery networks (CDNs) đang rất nóng trong thực tế.

[Only registered and activated users can see links. ]

**Mister** · #5 (**permalink**) 08-11-2009

	Trích:	SpringerCV
	Kết quả cống bố khủng khiếp nhỉ, chẳng hiểu các bác ấy cải tiến TCP kiểu mà ghê thế? Mình không hiểu lắm cái paper Kev giới thiệu vì cũng chỉ là dân amateur trong mảng này thôi. Trước có đọc ở blog KHMT bài của bác Nờ Pê Khó giới thiệu về network coding, đại khái là một big innovation cho internet. Mấy cái paper của MIT này đã thấy kết quả ác chiến lắm rồi: [Only registered and activated users can see links. ] [Only registered and activated users can see links. ] Cũng là một dạng theory meets practice với thử nghiệm double TCP throughput trên một testbed khá lớn và có tiềm năng hơn thế rất nhiều. Thế nhưng kết quả của mấy bác ở Caltech này đã vượt hơn hẳn, kể cả khi áp dụng trên thực tế.

Thật ra tụi Dina Katabi là dân làm system nên toán tủng mình nghĩ là dỏm thôi. Cái paper mà bác đưa ra thật ra chẳng có gì deep về theory cả. Nó chỉ apply được trong trường họp rất đơn giản. Làm thế nào đánh giá và thu được performance gain due to network coding in wireless ad hoc networks mới là bài toán rất khó và chưa có câu trả lới.

(Note cái; chú Katti làm bài báo đó cũng ăn may được tui Profs nó đẩy lên nên được best paper award cho journal version của paper đó trên IEEE/ACM TON và đã lấy được job ở stanford)

**SpringerCV** · #6 (**permalink**) 08-11-2009

	Trích:	Mister
	Thật ra tụi Dina Katabi là dân làm system nên toán tủng mình nghĩ là dỏm thôi. Cái paper mà bác đưa ra thật ra chẳng có gì deep về theory cả. Nó chỉ apply được trong trường họp rất đơn giản. Làm thế nào đánh giá và thu được performance gain due to network coding in wireless ad hoc networks mới là bài toán rất khó và chưa có câu trả lới. (Note cái; chú Katti làm bài báo đó cũng ăn may được tui Profs nó đẩy lên nên được best paper award cho journal version của paper đó trên IEEE/ACM TON và đã lấy được job ở stanford)

Ừm, mình cũng thấy nó đẹp vì lần đầu tiên network coding thu được kết quả trong thực tế thôi, còn implementation trong đó còn nhiều vấn đề lắm. Ngay cái paper nó publish có một vài faults khá chối chẳng hạn như phần biểu diễn các opportunistic coding options còn thiếu hẳn 1 critical cases có thể dẫn xuất ra nhiều vấn đề khác.

----
@Kev: So great invention!!! [r2)]

Đọc lại thì thấy cũng đơn giản nhỉ, quan trọng là lại đánh trúng vào điểm yếu cố hữu của congestion control algorithm. Sửa lại quan điểm cố hữu về congestion từ "loss based" sang "queued based", từ bỏ quan điểm phiến diện để đánh giá toàn diện hơn. Nhưng đúng là research luôn như vậy, nhìn người ta làm xong rồi thì hiểu và thấy nó đơn giản (dù đôi khi muốn hiểu được cũng phải hỏi lại, he he

) rồi nghĩ bụng "sao mình không phát hiện ra nhỉ" nhưng bắt tay vào làm thì mới biết tay nhau.

Mấy ông già bên này thì một ông big inventor đã ra đi rồi, đúng lúc mình email hỏi để xin qua chỗ ông đó ở TU Munich mới đau. Bác Nờ Pê Khó có viết về vụ này hồi ấy trên blog KHMT. Mấy ông già còn lại nhìn chung tầm còn thấp hơn nhiều. Dân Đức thực dụng nên mấy ông "to đầu" cũng vẫn hay nhắm những project nào ra tiền thôi (industries fund và thường thấy ứng dụng cụ thể), những thứ "xa xôi, bất trắc" thì họ không xông xáo bằng dân Mỹ.

**Kev** · #7 (**permalink**) 08-11-2009

Thì Ralf đã ra đi rối vẫn còn trụ cột và là inventor của network coding bên Đức mà. Bác thích thì lao vào chơi thôi.

[Only registered and activated users can see links. ]

Thật ra thì research đỉnh cao không hẳn chỉ là những lý thuyết khô cứng, khó đọc, khó hiểu, giải quyết những vấn đề phức tạp, khó khăn. Có thể trong Maths/ Physics...thì đúng nhưng những ngành khác, đặc biệt là Engineering thì những gì có big impact đôi khi rất thực tế. Một ví dụ là 10 năm trước, không ai biết equiblirium state của Internet là cái gì, như thế nào mặc dù ai cũng biết là nó tồn tại (nếu không thỉ giờ anh em đâu có vào forum chửi nhau thế này haha). Thậm chí Internet chỉ có 3 computers thôi cũng không ai biết. Lúc đó Internet chì là hueristic, chẳng ai biết nó chạy thế nào. Thế là thầy mình viết 1 bài báo mathematically model cai Internet dùng mấy cái basic functions, toán tủng nếu mấy bác Maths nhìn vào thì cấp 3 chuyên toán VN cũng biết (integral, fixed point theorem...). Sau kết quả đó, characterizing equilibrium state của Internet thật đơn giản, bao nhiêu nodes cũng như nhau. Từ đó bất cứ new algorithms nào cuả Internet, chỉ cần tìm được cái function đó là chacterie được equilibrium state của Internet nếu tât cả các nodes (6 billions!!!) dùng algorithms đó. Maths miếc rất quan trong nhưng làm Engineering research, có lẽ Engineering mind vẫn quan trọng hơn. Dấy là lý do mà trước đây cãi nhau việc cứ Mathematicians chuyển qua EE/CS sẽ dễ dàng thành công.

Liên quan đến ở trên, Scott Shenker ở Berkeley từng nói “The Internet is an equilibrium, we just have to identify the game”.

Trong đây có ai làm game không nhỉ?

**SpringerCV** · #8 (**permalink**) 08-11-2009

	Trích:	Kev
	Maths miếc rất quan trong nhưng làm Engineering research, có lẽ Engineering mind vẫn quan trọng hơn. Dấy là lý do mà trước đây cãi nhau việc cứ Mathematicians chuyển qua EE/CS sẽ dễ dàng thành công.

Hi hi, lại đụng đến vấn đề nhạy cảm rồi. Về chuyện này thì có lẽ kết luận chỉ chính xác cho nhóm đối tượng người Việt thôi. Đơn giản là vì ở Việt Nam trong một thời gian dài, ông nào giỏi cũng đi làm Toán hết cho nên dân Toán thường có tư duy tốt, chuyển sang ngành nào cũng giỏi cả. Chứ nếu cứ lập luận theo cái đà trên thì ngay cả học nhạc cũng chỉ cần giỏi Toán là được, bằng chứng là nhạc sĩ Phó Đức Phương, bỏ Toán SP ra sáng tác thì thành nhạc sĩ nổi tiếng ngay, ha ha ...

Về network coding thì đúng là không có duyên. Giờ đã yên ổn nơi khác rồi nên cũng không còn băn khoăn gì nữa cả.

TKP · #9 (**permalink**) 08-12-2009

	Trích:	Kev
	Là người làm research trong lình vực theory, chắc ai cũng thắc mắc và tự hỏi (và chắc là tự trả lời luôn lol) là không biết cái mình làm ứng dụng thế nào. Gần đây mình tình cờ đọc vnexpress thì thấy một article về kết quả của thầy (cũ) mình làm, thấy cũng vui vui. Dĩ nhiên là kết quả này đã được đănng khắp nơi trên báo nước ngoài, CNN, Nature, Science....đủ cả nhưng thấy báo Việt thì cảm giác lạ lạ. [Only registered and activated users can see links. ] Kết quả này bắt nguồn từ việc nghiên cứu thuần túy lý thuyết mà ra. Đây là bài báo FAST TCP: motivation, architecture, algorithms, performance David X. Wei, Cheng Jin, Steven H. Low and Sanjay Hegde. IEEE/ACM Transactions on Networking, 14(6):1246-1259, Dec 2006 (1.4MB) Sau đó, Caltech implemented algorithm developed rối mang ra thi đua thì nó là 5 consecutive years world record fastest data transfer trans Atlantic. Mình muốn nói là anh em làm theory thì nên giữ vửng hi vọng một ngày nào đó kết quả của mình cũng như vậy. Haha. No joking ví thấy mình làm mấy cái đó cũng là với PhD students thôi mà. Side info: Bac No-Pe Khó nhà mình cũng có một số báo TON. Báo TON thì Viet students có vẻ ít ra, không biết được khoảng 10 bài trước giờ chưa. Nếu có ai interested in topic này thì mình sẽ tiếp tục bàn nữa, nhiều ví dụ trực quan... Nhưng ngành khác thi sao nhi? Có ai có cases nào thì đưa lên, nói chuyện chơi.

Hồi trước em có chơi với cái FAST TCP này, setup trong mạng LAN thì thấy good. Hứng chí, em deploy thực lên lên vòng Ring của DHQG (mấy bác trên đó bảo bw của Ring này 1-2Gbps) thì thấy chẳng hơn gì thằng TCP Reno. Chắc là do code lúc đó chưa hoàn chỉnh hay sao, vì thấy rõ ràng nó chạy theo mode FAST, tức là ko còn AIMD của Reno, nhưng mà có cái gì đó chặn ở ngưỡng trên nên throughput nó cứ đều đều, ko tăng lên được. Sau đó thì chán quá, bỏ FAST chuyển sang hướng khác.

**Kev** · #10 (**permalink**) 08-12-2009

Có phải là lý do này không bác?

"FAST TCP (also written "FastTCP") is a TCP congestion avoidance algorithm especially targeted at long-distance, high latency links"

Cái test scenarios cùa bác chắc đâu long-distance hay high latency links, rite? Netlab có một cái gói là WAN in LAB dùng cáp fiber cuộn tròn từng ống dài khoảng 7-8000 Km, mô phỏng trans Atlantic links. Mục đích WAN in Lab là để cho Internet research groups khắp nơi test algorithms mới trong môi trường thật. Có khi lúc đó bác book cái WAN in Lab này để test cái implementation của bác thì ngon. Hehe.