計算機網路特論 Special Topics on Computer Networks
- 課程目標: 精選十篇於計算機網路發展歷史中具有特殊意義的十篇文章，讓學生於閱讀經典中開拓視野。
- 評量方式: 口頭報告(55%) 課堂表現(15%) 期中考(15%) 期末考(15%)
- 主要教科書: 無
- 課程網頁 http://Course.ipv6.club.tw/NetworkHistory/
- Students enrolled to this class.
Three papers in a session
- Original paper
- Protocol Spec
- Follow-up Research
- "A Minimum Delay Routing Algorithm Using Distributed
Computation," [Gallagher 1977]. In this paper, the multipath
routing problem (of determining at each node, the fraction of
traffic destined for a given destination that should be routed
over each of the node’s outgoing links) is formulated as an
optimization problem. An iterative, distributed algorithm in
which marginal delay information is passed to upstream
nodes, which then readjust their routing fractions, is shown to
converge to minimize the overall average cost (e.g., delay) in
the network. This paper (as well as [Kelly 1998] below) are
nice examples of how network protocols (e.g., routing, ratecontrol)
can be naturally derived from well-posed
- "The Design Philosophy of the DARPA Internet Protocols,"
[Clark 1988]. This paper provides a thoughtful retrospective
view of the goals and design principles of the Internet
architecture and its protocols. It has been a favorite among
students in my networking classes, and paired with
[Molinero-Fernandez 2003] has made for many lively and
interesting class discussions.
- "A Calculus for Network Delay, Part I: Network Elements in
Isolation; Part II: Network Analysis," [Cruz 1991]. During
the 1990’s, there was considerable foundational research on
providing quality of service guarantees for flows that are
multiplexed within the network. This paper describes an
elegant "calculus" that provides provable worst-case
performance (delay) bounds on per-session, end-end
performance. Many important works followed this seminal
work; a nice survey is [LeBoudec 2001].
- "A generalized processor sharing approach to flow control
in integrated services networks," [Parekh 1993]. In many
ways a companion paper to [Cruz 1991], this two-part paper
demonstrates how provable per-node and end-end persession
performance bounds can be guaranteed, given a
weighted fair-queueing discipline at each node.
- "Equivalent capacity and its application to bandwidth
allocation in high speed networks," [Guerin 1991]. The
notion of effective bandwidth, an approximate
characterization of the queueing behavior of a session when
multiplexed with others, was developed by numerous
researchers (see, e.g., [Kelly 1996]) throughout the 1990’s.
This early paper introduced me to the idea, and sparked my
interest in the area.
- "On the self-similar nature of Ethernet traffic (extended
version)," [Leland 1994]. While the notion of long-range
dependency, self-similarity, and heavy-tailed distributions
are now a standard part of the lexicon of those interested in
traffic characterization and descriptive network models, this
paper introduced these ideas widely, launching many
subsequent research efforts that have taken such an approach
- "Sharing the cost of multicast trees: an axiomatic analysis,"
[Herzog 1997]. Axiomatic methods, in which one poses a
desired set of system properties or behaviors, and then
develops a protocol that meets these properties (or proves an
impossibility result – that there is no protocol that meets the
requirements) is a well-known technique in fields such as
mathematical economics and social welfare theory. This
paper was an elegant application of this set of tools in the
- "Rate control in communication networks: shadow prices,
proportional fairness and stability," [Kelly 1998]. This
paper formulates the rate control (congestion control)
problem as a problem of allocating bandwidth to flows so as
to optimize overall system "utility," showing that Jacobson’s
TCP congestion control protocol (developed 10 years earlier
using tremendous engineering insight) can be naturally
interpreted as a distributed algorithm that iteratively solves
this global optimization problem.
- "Multicast-based Inference of Network-Internal Loss
Characteristics," [Caceres 1999]. Many research efforts in
network measurement through the mid-to-late 1990’s were
descriptive in nature – taking active or passive measurements
at various points in the network, and interpreting the
observed performance (e.g., packet delay, packet loss,
aggregate traffic mix, or throughput). This paper elegantly
used statistical methods (maximum likelihood estimation)
together with end-to-end measurement data to infer the
(unseen) topology of the network between the measurement
endpoints. Inference techniques have since become an
important and widely-used part of the measurement toolkit.
- "Internet indirection infrastructure," [Stoica 2004]. It’s
said (in a quote often attributed to Butler Lampson) that
nearly every problem in computer science can be solved by
adding another level of indirection. I had always thought that
this quote applied to data structures and algorithms. This
paper, however, opened my eyes to how indirection can be
used in an elegant and clean distributed network architecture
for providing a variety of overlay services
- "Editorial zone: 10 networking
ACM SIGCOMM Computer Communication Review, Volume 36 Issue 1
- Search "10 papers for network"
PowerCam 4.1; PowerCam
- Visit the XMS Server and
register an account to upload your presentatations and reports.
- 2/20 Introduction
- 2/27 William F. Slater, "Internet History and Growth"
, Internet Society 2002.
- 3/5 Vint Cerf, "The Next 50 Years of Networking"
, ACM 1997. (Please turn on the speakers.)
V. Cerf, R. Kahn,
"A Protocol for Packet Network Intercommunication"
IEEE Transactions on Communications,
pp.637-648, Volume 22, Issue 5, May 1974.
- 4/2 Exhaustion
of IPv4 Address in 2010
- 4/9 IPv6 Promotion Status
- 4/16 R. M. Metcalfe, D. R. Boggs, "Ethernet: Distributed Packet Switching for Local Computer
, Communications of the ACM, Vol. 19, No. 5, pp 395-404.
- 4/23 Vint Cerf, "Internet in the 21st Century"
, ISOC 2002.
- 4/30 The Design Philosophy of the DARPA Internet Protocols (蔡政霖)
- 5/7-5/14 Internet indirection infrastructure (王嘉裕)
- 5/21 Equivalent capacity and its application to bandwidth allocation in
high speed networks (顏汎嘉)
- 5/21 Sharing the cost of multicast trees: an axiomatic analysis (林文仁)
- 5/28 On the self-similar nature of Ethernet traffic (王筱婷)
- 6/4 "Multicast-based Inference of Network-Internal Loss
- 6/4 A generalized processor sharing approach to flow control in
integrated services networks
- 6/11 Final Exam
- Rate control in communication networks: shadow prices, proportional
fairness and stability (王筱婷)
- D. Walden,
"A system for interprocess communication in a resource sharing computer
Communications of the ACM,
Volume 15 , Issue 4 (April 1972)
Pages: 221 - 230.