tcp ip links - Neal E. Young

neal young / tcp ip links

(as of 2000)

Related collections

Seminar on Algorithmic Aspects of Game Theory - cs294 at UC Berkeley by Christos Papadimitriou
~30 links in the reading list. "Algorithmic mechanism design, internet congestion & game theory/economics, `the price of anarchy', combinatorial auctions, multicast auctions, repeated games, power laws, game theory"
EECS 598-5 (broken link): Mathematical Modeling and Simulation Techniques in Networking, U.Michigan
~30 references. "Simulation and the Monte-Carlo methods; Medium Access Control (MAC); Performance of TCP; Congestion control, flow control, global optimization and fairness;
Internet traffic engineering and Self-similarity
ECSE-4670: Computer Communications Networks. Fall 2001. RPI
Sally Floyd's pointers to literature on optimization with end-to-end congestion control.
~20 references. "General references, modeling the Internet, proportional fairness, optimization flow control, delay-based optimization"
links by Frank Kelly on topics related to his paper "Mathematical modelling of the internet"
~40 refs: "Stability with propagation delays, admission control, priorities, multicast, marking strategies, pricing, groups, IETF activity, arguments for end-to-end as a design principle"
Papers on TCP/IP modelling and related topics - collected by Jitendra Padhye at ICSI center for internet research ~50 references
TCP/IP RESEARCH PAPERS collected by the Internet Engineering Task Force / TCP Over Satellite WG ~50 references, many on wireless and satellite
Congestion control literature - collected by Shivkumar Kalyanaraman at RPI
~150 references, lists of active researchers, by area. "End-to-end and edge-to-edge flow control, explicit rate/window feedback, DEC (classic papers) unicast architectures, multicast congestion control, QoS, rate-based, control-theoretic, pricing/economics, filtering/estimation/measurement".
collection of tcp-related links by Chyouhwa Chen at National Taiwan University of Sci. and Tech.
another such collection (broken link) at Complex Engineering System Lab, Tsinghua, China
end2end-interest mailing list - discussion of end-to-end aspects of networking protocols.
e.g. (Why) does rate-based AIMD lead to a stable network? by Frank Kelly, and related posts.

A few research groups/projects

ICSI center for internet research (Scott Shenker, Sally Floyd, Richard Karp, Christos Papadimitriou...)
Frank Kelly - University of Cambridge / Mathematics / Statistical Laboratory.
Steven Low - Cal. Tech.
Dah Ming Chiu - Sun
Microsoft networking group Cambridge, U.K. Follow "publications" link for publications database.
congestion manager project at MIT LCS Networks and Mobile Systems group
"an end-to-end framework for congestion control and management, bandwidth sharing, independent of specific transport protocols (like TCP) and applications". last meeting was in 2000?

Background

intro: Ramesh Johari's article Mathematical modeling and control of Internet congestion, in SIAM News, volume 33, March 2000. A short SIAM news article discussing congestion control.
intro: R.J. Gibbens, Control and pricing for communication networks, Phil. Trans. R. Soc. Lond. A (2000). Available from http://www.statslab.cam.ac.uk/cgi-bin/resreps.pl?term=1999-10.
brief survey of congestion control, segue into discussion of shadow prices
intro: J.K. Mackie-Mason and H. Varian, Pricing the Internet, in B. Kahin and J. Keller, eds., Public Access to the Internet, MIT Press, Cambridge, MA, 1995. Available from http://www-personal.umich.edu/~jmm/papers.html#pi.
http://citeseer.nj.nec.com/169035.html
nice overview of some economic issues in the internet, segue into "smart market" pricing
historical: V. Jacobson, Congestion avoidance and control, Proceedings of ACM SIG-COMM '88, 1988, 314329. Available from ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z.
http://citeseer.nj.nec.com/jacobson88congestion.html
documents first congestion-control features added to TCP/IP

Flow control as optimization

- S. H. Low, F. Paganini and J. C. Doyle. "Internet Congestion Control: An Analytical Perspective". IEEE Control Systems Magazine, Feb. 2002
  http://www.ee.ucla.edu/~paganini/PS/csm2001.ps
  http://citeseer.nj.nec.com/494567.html
  "This article reviews the current TCP congestion control protocols and overviews recent advances that have brought analytical tools to this problem. We describe an optimization-based framework that provides an interpretation of various flow control mechanisms, in particular, the utility being optimized by the protocol's equilibrium structure. We also look at the dynamics of TCP and employ linear models to exhibit stability limitations in the predominant TCP versions, despite certain built-in compensations for delay. Finally, we present a new protocol that overcomes these limitations and provides stability in a way that is scalable to arbitrary networks, link capacities, and delays."
- F.P. Kelly, Mathematical modelling of the Internet, Proceedings of the Fourth International Congress on Industrial and Applied Mathematics, 1999. Available from http://www.statslab.cam.ac.uk/~frank/mmi.html.
  http://citeseer.nj.nec.com/kelly99mathematical.html
  some results from the 1998 paper, plus more similar results, with more of an overview
- S. Shenker, D. Clark, D. Estrin and S. Herzog. Pricing in Computer Networks: Reshaping the Research Agenda. Communications Policy. Vol. 20(1), 1996.
  ftp://parcftp.xerox.com/pub/net-research/picn.ps
  http://citeseer.nj.nec.com/shenker95pricing.html
  a critique of optimality-based analysis
- R.J. Gibbens and F.P. Kelly, Resource pricing and the evolution of congestion control, Automatica, 35 (1999), 19691985.
  http://www.statslab.cam.ac.uk/~frank/evol.html.
  http://citeseer.nj.nec.com/gibbens98resource.html
  discussion of existing research, simulations of congestion control based on shadow prices
- D. Chiu and R. Jain, "Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks," Journal of Computer Networks and ISDN, Vol. 17, No. 1, June 1989, pp. 1-14.
  http://www.cse.wustl.edu/~jain/papers/cong_av.htm
  http://citeseer.nj.nec.com/context/197931/0
  "It is shown that a simple additive increase and multiplicative decrease algorithm satisfies the sufficient conditions for convergence to an efficient and fair state... We concentrate on one bottleneck resource and the users that share it."
- S. Shenker. "A Theoretical Analysis of Feedback Flow Control". SIGCOMM'90 , pp. 156-165.
  http://citeseer.nj.nec.com/context/4966/0
  http://www.eecs.umich.edu/~mingyan/598W02/cc/Shenker.pdf
  "We introduce a simple model of feedback flow control, in which sources make synchronous rate adjustments based on the congestion signals and other local information, and apply it to a network of Poisson sources and exponential servers."
- F. P. Kelly. "Charging and rate control for elastic traffic". European Transactions on Telecommunications, volume 8 (1997) pages 33-37.
  http://www.statslab.cam.ac.uk/~frank/elastic.html
  http://citeseer.nj.nec.com/kelly97charging.html
  "We have shown that if each user is able choose a charge per unit time that it is prepared to pay, and if the network determines allocated rates so that the rates per unit charge are proportionally fair, then a system optimum is achieved when users' choice of charges and the network's choice of allocated rates are in equilibirum. We have not discussed convergence to equlibrium and an interesting and challenging question concerns whether rate control algorithms such as those described in [2], [3], and [4] may be adapted to implement the proportional fairness criterion described in this paper."
- F.P. Kelly, A.K. Maulloo, and D.H.K. Tan, Rate control in communication networks: Shadow prices, proportional fairness, and stability, J. Oper. Res. Soc., 49 (1998), 237252. Available from http://www.statslab.cam.ac.uk/~frank/rate.html.
  http://citeseer.nj.nec.com/context/16262/0
  important technical paper on optimizing proportional fairness with end-to-end protocols
- J. Golestani and S. Bhattacharyya, ``A Class of End-to-End Congestion Control Algorithms for the Internet'', Proceedings of the International Conference on Network Protocols, 1998
  http://www.bell-labs.com/user/golestani/
  http://citeseer.nj.nec.com/91517.html
  end-to-end congestion control as global optimization via "minimum cost flow control"
- Optimization Flow Control, I: Basic Algorithm and Convergence. S. H. Low and D. E. Lapsley. IEEE/ACM Transactions on Networking, 7(6):861-75, Dec. 1999
  http://netlab.caltech.edu/pub/papers/ofc1_ToN.ps
  http://citeseer.nj.nec.com/199010.html
  analysis and simulation of an aggregate-utility-maximizing distributed algorithm
- L. Massoulie and J. Roberts. "Bandwidth Sharing: Objectives and Algorithms". INFOCOM'99.
  http://research.microsoft.com/users/lmassoul/infocom9.ps&pub=IEEE
  http://citeseer.nj.nec.com/259384.html
  max-min fairness, proportional fairness, overall delay minimization via fixed window flow control
- J. Mo and J. Walrand. "Fair End-to-End Window-based Congestion Control". IEEE Trans. Networking, Vol. 8, No. 5, October 2000.
  http://buffy.eecs.berkeley.edu/IRO/Summary/99abstracts/jhmo.1.html
  http://www.ecse.rpi.edu/Homepages/shivkuma/teaching/sp2001/readings/mo-walrand.pdf
  http://citeseer.nj.nec.com/337047.html
  http://citeseer.nj.nec.com/181366.html
  "we demonstrate the existence of fair end-to-end window-based congestion control protocols for packetswitched networks with FCFS routers. Our definition of fairness generalizes proportional fairness and includes arbitrarily close approximations of max-min fairness. The protocols use only information that is available to end hosts and are designed to converge reasonably fast."
- S. Athuraliya, S. Low, "Optimization Flow Control with Newton-Like Algorithm", Journal of Telecommunication Systems, 2000
  http://citeseer.nj.nec.com/athuraliya99optimization.html
  analysis and simulation of another aggregate-utility-maximizing distributed algorithm, with an improved update step
- "Additive Increase Appears Inferior", S. Gorinsky and H. Vin, Technical Report TR2000-18, Department of Computer Sciences, The University of Texas at Austin, May 2000.
  http://www.cs.utexas.edu/users/gorinsky/tr2000-18.ps
  interesting: counters the oft-stated claim that Additive-Increase algorithms are necessary for stability, also discusses convergence rates for the single bottleneck case.
- F. Paganini, "On the stability of optimization-based flow control", in the 2001 American Control Conference. http://www.ee.ucla.edu/~paganini/
  http://citeseer.nj.nec.com/paganini01stability.html
  further analysis of algorithm proposed by Low et al
- Understanding Vegas: A Duality Model. S. H. Low, Larry Peterson and Limin Wang. Journal of ACM, 49(2):207-235, March 2002
  http://netlab.caltech.edu/pub/papers/vegas.ps
  http://citeseer.nj.nec.com/490101.html
  "we now interpret the Vegas algorithm as approximately carrying out the scaled gradient projection algorithm"
Stability (extending the network model to allow round-trip times)
- Floyd, S., and Jacobson, V., On Traffic Phase Effects in Packet-Switched Gateways. Internetworking: Research and Experience, V.3 N.3, September 1992, p.115-156.
  http://citeseer.nj.nec.com/floyd92traffic.html
  discusses instability due to unintended synchronization of end-to-end loss-based controls
- R. Johari & D. Tan, "End-to-End Congestion Control for the Internet: Delays and Stability". IEEE/ACM Transactions on Networking 9(2001) 818-832.
  http://www.statslab.cam.ac.uk/cgi-bin/resreps.pl?term=2000-2&field=number
  http://citeseer.nj.nec.com/context/1737214/0
  analyzes stability of end-to-end protocols when different connections have different round-trip times, including a convergence-rate proof for a single-resource, single-route case
- Stability of Distributed Congestion Control with Heterogeneous Feedback Delays. L. Massoulie, November 2000
  http://research.microsoft.com/scripts/pubs/view.asp?TR_ID=MSR-TR-2000-111
  http://citeseer.nj.nec.com/massoulie00stability.html
  proves asymptotic stability under heterogenous delays, similar to above
- G. Vinnicombe. On the stability of end-to-end congestion control for the Internet. University of Cambridge. Tech. Rep. CUED/F-INFENG/TR.398, December 2000.
  http://citeseer.nj.nec.com/context/1902794/0
  more on heterogenous delays
Bibliography from Mathematical modeling and control of Internet congestion (mentioned above)
- J. Crowcroft and P. Oechslin, Differentiated end-to-end Internet services using a weighted proportionally fair sharing TCP, ACM Comp. Commun. Rev., 28 (1998), 5367. Available from http://www.cs.ucl.ac.uk/staff/jon/hipparch/pricing.html.
  http://citeseer.nj.nec.com/crowcroft98differentiated.html
  implementation/simulation of a TCP modified to achieve proportional fairness
- S. Floyd, TCP and explicit congestion notification, ACM Comp. Commun. Rev., 24 (1994), 1023. Available from http://www-nrg.ee.lbl.gov/floyd/ecn.html.
  http://citeseer.nj.nec.com/71263.html
  http://citeseer.nj.nec.com/415830.html
  simulations of explicit congestion notification in TCP/IP
- R.J. Gibbens, Control and pricing for communication networks, to appear in Phil. Trans. R. Soc. Lond. A (2000). Available from http://www.statslab.cam.ac.uk/cgi-bin/resreps.pl?term=1999-10.
  brief survey of congestion control, segue into discussion of shadow prices
- R.J. Gibbens and F.P. Kelly, Resource pricing and the evolution of congestion control, Automatica, 35 (1999), 19691985. Available from http://www.statslab.cam.ac.uk/~frank/evol.html.
  http://citeseer.nj.nec.com/gibbens98resource.html
  discussion of existing research, simulations of congestion control based on shadow prices
- R.J. Gibbens, R. Mason, and R. Steinberg, Internet service classes under competition (1999). Available from http://www.soton.cam.ac.uk/~ram2/papers/pmp10.pdf.
  http://www.soton.ac.uk/~ram2/papers/gmsjsac2.html
  economic analysis of Paris-Metro-like pricing
- V. Jacobson, Congestion avoidance and control, Proceedings of ACM SIG-COMM '88, 1988, 314329. Available from ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z.
  http://citeseer.nj.nec.com/jacobson88congestion.html
  documents first congestion-control features added to TCP/IP
- F.P. Kelly, Mathematical modelling of the Internet, to appear in Proceedings of the Fourth International Congress on Industrial and Applied Mathematics, 1999. Available from http://www.statslab.cam.ac.uk/~frank/mmi.html.
  http://citeseer.nj.nec.com/kelly99mathematical.html
  results from the 1998 paper, plus other results, with more of an overview
- F.P. Kelly, A.K. Maulloo, and D.H.K. Tan, Rate control in communication networks: Shadow prices, proportional fairness, and stability, J. Oper. Res. Soc., 49 (1998), 237252. Available from http://www.statslab.cam.ac.uk/~frank/rate.html.
  http://citeseer.nj.nec.com/context/16262/0
  technical paper on optimizing proportional fairness with end-to-end protocols
- J.K. Mackie-Mason and H. Varian, Pricing the Internet, in B. Kahin and J. Keller, eds., Public Access to the Internet, MIT Press, Cambridge, MA, 1995. Available from http://www-personal.umich.edu/~jmm/papers.html#pi.
  http://citeseer.nj.nec.com/169035.html
  nice overview of some economic issues in the internet, segue into "smart market" pricing
- A. Odlyzko, A modest proposal for preventing Internet congestion, 1997. Available from http://www.research.att.com/~amo/doc/networks.html.
  http://citeseer.nj.nec.com/odlyzko97modest.html
  introduced the "paris metro" idea
- D. Wischik, How to mark fairly, Workshop on Internet Service Quality Economics, MIT. Available from http://www.statslab.cam.ac.uk/~djw1005/Stats/Research/marking.html.
  discussion of fairness in packet marking schemes
Explicit Congestion Notification (ECN)
- S. Floyd, TCP and explicit congestion notification, ACM Comp. Commun. Rev., 24 (1994), 1023. Available from http://www-nrg.ee.lbl.gov/floyd/ecn.html.
  http://citeseer.nj.nec.com/71263.html
  http://citeseer.nj.nec.com/415830.html
  documents first congestion-control features added to TCP/IP
- S. Floyd and V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance," IEEE/ACM Transactions on Networking, 1(4), August 1993
  http://citeseer.nj.nec.com/floyd93random.html
- RFC: "The Addition of Explicit Congestion Notification (ECN) to IP": http://www.icir.org/floyd/papers/rfc3168.txt
- S. Kunniyur and R. Srikant, End-to-end Congestion Control Schemes: Utility Functions, Random Losses and ECN marks. Proceedings of IEEE Infocom 2000.
  http://citeseer.nj.nec.com/kunniyur00endtoend.html
  http://citeseer.nj.nec.com/280819.html
TCP compatibility
- S. Floyd and K. Fall, "Promoting the Use of End-to-End Congestion Control in the Internet," IEEE/ACM Transactions on Networking, August 1999
  http://www.icir.org/floyd/end2end-paper.html
  http://citeseer.nj.nec.com/floyd99promoting.html
  argues that routers need to enforce TCP friendliness / compatability
- Dynamic Behavior of Slowly-Responsive Congestion Control Algorithms.
  Deepak Bansal, Hari Balakrishnan, Sally Floyd and Scott Shenker.
  Sigcomm 2001, August 27-31, San Diego, CA.
  http://nms.lcs.mit.edu/papers/slowcc-sigcomm01.html
  simulation of tcp-compatible protocols in a changing network
- The TCP-Friendly Website - how congestion-control mechanisms can play nicely with TCP/IP.

Related works from Theoretical Computer Science

Christos H. Papadimitriou and Mihalis Yannakakis. Linear programming without the matrix. Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, 1993.
http://citeseer.nj.nec.com/context/460684/0
Y. Bartal, J. Byers, and D. Raz. Global Optimization Using Local Information with Applications to Flow Control. In 38th IEEE Symp. on Foundations of Computer Science, pages 303-312, 1997
http://citeseer.nj.nec.com/bartal97global.html
N. Garg and J. Konemann, "Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems", Proc. of the 39th Annual Symposium on Foundations of Computer Science (FOCS '98), November 1998
http://citeseer.nj.nec.com/garg97faster.html
J. Kleinberg, Y. Rabani, and E. Tardos. Fairness in routing and load balancing. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1999.
http://citeseer.nj.nec.com/371772.html
N. Nisan and A. Ronen. Algorithmic Mechanism Design. In Proc. of 31st Symposium on Theory of Computing, pages 129-140. ACM Press, New York, 1999.
http://citeseer.nj.nec.com/nisan99algorithmic.html
J. Feigenbaum, C. Papadimitriou, and S. Shenker. Sharing the Cost of Multicast Transmissions. In Proc. of 32nd Symposium Theory of Computing, pages 218-226. ACM Press, New York, 2000.
http://citeseer.nj.nec.com/319471.html
A. Goel, A. Meyerson, S. Plotkin, "Combining fairness with throughput: Online routing with multiple objectives," Proc. 32nd ACM STOC, 2000.
http://citeseer.nj.nec.com/goel00combining.html
"How Bad is Selfish Routing?" Tim Roughgarden and Eva Tardos. IEEE Symposium on Foundations of Computer Science (2000)
http://citeseer.nj.nec.com/471986.html
R. Karp, E. Koustosoupias, C.Papadamitriou, and S.Shenker. Optimization problems in congestion control. FOCS, 2000. 26
http://citeseer.nj.nec.com/karp00optimization.html
K. Jain and V. Vazirani. Applications of Approximation Algorithms to Cooperative Games. In ACM Symposium on Theory of Computing (STOC), 2001.
http://citeseer.nj.nec.com/496450.html
N. Young. Sequential and parallel algorithms for mixed packing and covering.
IEEE Symposium on Foundations of Computer Science, 2001.
http://citeseer.nj.nec.com/458229.html
Y. Afek, Y. Mansour and Z. Ostfeld. Convergence Complexity of Optimistic Rate Based Flow Control Algorithms. In Proc. of 28th ACM Symposium on Theory of Computing, pp. 89-98, 1996. http://citeseer.nj.nec.com/article/afek96convergence.html
Panagiota Fatourou, Marios Mavronicolas, and Paul Spirakis. Efficiency of oblivious versus non-oblivious schedulers for optimistic rate-based flow control. In PODC, August 1997. http://citeseer.nj.nec.com/fatourou00efficiency.html
B. Awerbuch and Y. Shavitt. Converging to Approximated Max-Min Flow Fairness in Logarithmic Time. In Proc. of the 17th IEEE INFOCOM, pp. 1350-57, March 1998.
http://citeseer.nj.nec.com/awerbuch97converging.html

Miscellany

H. Balakrishnan, S. Seshan, E. Amir, and R. H. Katz, "Improving TCP/IP performance over wireless networks," in Proceedings of the rst Annual International Conference on Mobile Computing and Networking (Mobicom '95), pp. 2-11, Nov. 1995.
http://citeseer.nj.nec.com/context/34969/0
The TCP-Friendly Website - how congestion-control mechanisms can play nicely with TCP/IP.
The Internet Traffic Report
"Where mathematics meets the Internet," W. Willinger and V. Paxson, in Notices of the AMS, 8/1998. (About modelling internet traffic.)
A Dartmouth link: Market-Based Resource Allocation in Mobile-Agent Systems
Economic Markets as a Means of Open Mobile-Agent Systems - Bredin, Kotz, Rus (1999)
Market-Based Mobile-Agent Planning: A Thesis Proposal - Bredin (1999)
A Game-Theoretic Formulation of Multi-Agent Resource.. - Dartmouth College..
A Game-Theoretic Formulation of Multi-Agent Resource.. - Bredin, Maheswaran.. (2000)
Trading Risk in Mobile-Agent Computational Markets - Bredin, Kotz, Rus
Rahul Garg, Abhinav Kamra, Varun Khurana (2001). Eliciting Cooperation from Selfish Users: A Game-Theoretic Approach Towards Congestion Control in Communication Networks
http://domino.watson.ibm.com/library/CyberDig.nsf/...
S. Shenker. Making Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines. In Proceedings of ACM SIGCOMM'94, pages 47--57, 1994. 20
http://citeseer.nj.nec.com/shenker94making.html
D.G.Luenberger, Optimization by vector space methods. Wiley, 1969.
http://citeseer.nj.nec.com/context/77736/0
A Course in Robust Control Theory: A Convex Approach
by G. E. Dullerud and F. Paganini
Texts in Applied Mathematics, Vol 36, Springer - New York, 2000.
http://www.springer-ny.com/detail.tpl?isbn=0387989455
Eduardo D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems.
Second Edition, Springer, New York, 1998. (531+xvi pages, ISBN 0-387-984895)
Series: Textbooks in Applied Mathematics, Number 6. Hardcover, approx $55.00
Order in USA from 1-800-SPRINGER or from amazon.com.
INTRODUCTION TO CONTROL OF OSCILLATIONS AND CHAOS
by A L Fradkov & A Yu Pogromsky
Routing and peering in a competitive Internet. Presentation by Ramesh Johari at IPAM workshop on large-scale communication networks, March 18-22, 2002. http://web.mit.edu/~rjohari/www/

Breadcrumbs

Search

neal young / tcp ip links

Main Navigation

Related collections

A few research groups/projects

Background

Flow control as optimization

Related works from Theoretical Computer Science

Miscellany