CSL374: Computer Networks


Class timings

Monday and Tuesday, 12:00-13:30 in Seminar Hall IIA-501

Slides

  • 7,8,14 August (Data Link Layer, Tanenbaum Chapter 3).

    • References

  • S. M. Ross, Introduction to Probability Models, Academic Press.
  • Bertsekas and Gallager, Data Networks, Prentice Hall of India.
  • A. S. Tanenbaum, Computer Networks, Prentice Hall of India.
  • Eytan Modiano's course on Communication Networks.
  • Rate control in communication networks: shadow prices, proportional fairness and stability. (F.P.Kelly,A.K.Maulloo and D.K.H.Tan, Journal of operations research society, 49, 1998.).
  • Ramesh Johari, and John N. Tsitsiklis. (2004). Efficiency loss in a network resource allocation game.
  • S. H. Low, Larry Peterson and Limin Wang, Understanding Vegas: A Duality Model, Journal of ACM, 49(2):207-235, March 2002.
  • Eva Tardos' course on Algorithmic Game Theory.
  • Johari/Mannor/Tsitsiklis, "Efficiency loss in a network resource allocation game: the case of elastic supply", 2004.
  • Koutsoupias/Papadimitriou, "Worst-case Equilibria", STACS 1999
  • S. Yang and B.Hajek, "Revenue and stability of a mechanism for efficient allocation of a divisible good," Preprint, March 2005, Revised, December 2005. (Also presented at the NBER/NSF Decentralization Conference , Urbana, April 2005.)
  • S. Yang and B. Hajek, "VCG-Kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals," Fortieth Annual Conference on Information Sciences and Systems , Princeton, New Jersey, March 22-24, 2006.
  • B. Hajek and S. Yang, "Strategic buyers in a sum bid game for flat networks" Preprint. March 2004.
  • S. Sanghavi and B. Hajek, "A new mechanism for the free-rider problem. Proc. Third ACM Workshop on the Economics of Peer-to-Peer Systems, Philadelphia, August 22, 2005.
  • B. Hajek, "On the value of a well chosen bit to the seller in an auction," Proceedings IEEE International Symposium on Information Theory, September 2005.
  • S. Sanghavi and B. Hajek, "Optimal allocation of a divisible good to strategic buyers," Preprint, March 2005. Full version of paper presented at the IEEE Conference on Decision and Control, December 2004.
  • J. Alvarez and B. Hajek, "On the use of packet classes in communication networks to enhance congestion pricing based on marks," IEEE Trans. Automatic Control, Vol. 47, June 2002, pp. 1020 - 1026.
  • T. Roughgarden, Selfish Routing and the Price of Anarchy. Limited preview.
  • T. Roughgarden, The Price of Anarchy is independent of the network topology, Journal of Computer and System Sciences, 67(2):341--364, 2003
  • Optimization Flow Control, I: Basic Algorithm and convergence. (S.H.Low and D.Lapsley, IEEE/ACM trans. on networking, 1999.).
  • Dynamic Cesaro-Wardrop Equilibration in Networks. (V.S.Borkar and P.R.Kumar, IEEE Trans. on Aut. Con., 48, 3, 2003.).

    • Miscellaneous Reading

  • Interesting (hi)story of computer scientists getting into networking games.

    • Assignments

  • 8 August: Simulate M/M/1, M/M/m and M/M/m/m queues using ns network simulator (Can use Eitan Altman's course on ns available at http://www-sop.inria.fr/mistral/personnel/Eitan.Altman/ns.htm). Objective is to make a comparative study of these systems. Performance measure of interest would be the expected customer delays (Use of any other performance measure that makes the comparison more insightful will fetch you extra marks). This comparison should be "fair" (use appropriate parameters for these systems, for example, same total arrival rate). The submission date for this assignment is 30 August 2006.
  • 14 August: Simulate an M/M/m/m queue using ns and check if the PASTA property holds. Also check the effect of the service requirement distribution of customers on the stationary distribution of the number of customers in the system. The submission date for this assignment is 30 August 2006. Hint: Create m links and keep track of which link is being used by a connection. At any point of time, only make sure that at most one customer is using a given link. Please contact Karan Mangla, Varun Gulshan or Rahul Garg for details.
  • 21 August: Characterize the customer functions that can be used as an extension of Little's law to relate customer averages and time averages. A non-trivial example of a function that does not give desired results will also do. The submission date for this assignment is 15 September 2006.
  • Propose an algorithm in which sender adapts to the available bandwidth-delay product while transmitting over a single link which is shared by random number of other transmissions. Assume no packet loss (due to data corruption or buffer overflow). Assume that the propagation delay is randomly varying with some given mean. Study the effect of distribution of propagation delay on performance of your algorithm. Verify related equations from the reference book. The submission date for this assignment is 5 October 2006.
  • 14 Sept: a) Check using discrete event simulations the validity of Poisson approximation used in analysis of slotted Aloha system. b) Study the variation of success probability as a function of arrival probability (lambda) and retransmission probability (q_r). c) Assume q_r(n) = (g-lambda)/n. Let the throughput under this adaptive scheme be T(g). Study the function T(g) and find the optimizer of T(g). The submission date for this assignment is 5 October 2006.

    • Students' Presentations

  • List of references for Hari Balakrishnan's course on Computer Networks (available at http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-829Computer-NetworksFall2002/CourseHome/index.htm). Form groups (consisting of two students each); each group presents two papers selected from the above list. Please send your group details and choice of papers to me. Each group is requested to send me a list of 10 papers that it can present; I will then try to come up with a final list. Please make sure that the subject of the email reads "CSL374 Preferences".