#
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".