By default all assignments are to be submitted as text-only email or posted on
the web and submitted by email
containing the URL of the
assignment to:
with absolutely no attachments. All other modes of
submission are subject to prior approval by the instructor. Assignments will
in general not be accepted late.
You may use your Linux Accounts
to post assignments on the web as a means of submission.
An
assignment is late if the email is sent after the start of the class at
which it is due.
The grade for the assignment will be sent back to the email address from
which the
assignment email was sent. In the case of group assignments in which
multiple students
are involved, one student should be the sender of the email and the other
students should
be listed both in the email "CC:" list and in the body of the
message.
Students should check this page frequently for updates.
Assignments with an assignment date one week or more in the
future are subject to change.
Assignment #1, assigned Thursday, 3 February 2011, due Thursday, 10 February 2011.
Get your text books and bring them to class. You may share text books,
but you must be part of a study group with reliable access to the
text books no later than Thursday, 10 February 2011.
Read Chapter 1 (pp 1 -- 35) of
H. J. Bernstein, M. Goldstein, "Network Design and Implementation Lecture Notes
Spring 1984" Network_Design_and_Implementation_Spring_1984.pdf,
preparing detailed notes on queuing theory and graph theory.
Prepare a preliminary project proposal for the network design project that
you will do for this course.
Assignment #2, assigned Thursday, 10 February 2011, due Thursday, 24
February 2011.
Because of the difficulty people are having with some of the earlier
material, the due date of this assignment has been extended one week.
You should now have a copy of the Cook textbook. Read Chapters 1, 2 and 3, pages
1 -- 89 of Cook. Prepare detailed notes on the Max Flow, Min Cut Theorem. Be
prepared for the next quiz to explicitly compute the maximal flow through a network.
Be sure to get the Hwei Hsu text. You will need it for the readings for the
next assignment.
Note: There will be an in-class midterm on Thursday, 10 March 2011
Assignment #3, assigned Thursday, 3 March 2011, due Thursday 17 March 2011
Read Chapters 1, 2 and 9 of the Hwei Hsu text.
Read Chapter 2 (pp 37 --58) of
H. J. Bernstein, M. Goldstein, "Network Design and Implementation Lecture Notes
Spring 1984" Network_Design_and_Implementation_Spring_1984.pdf,
preparing detailed notes on communications network design.
Assignment #4, assigned Thursday, 17 March 2011, due Thursday 31 March 2011
Read Chapter 3 (pp 59 --96) of
H. J. Bernstein, M. Goldstein, "Network Design and Implementation Lecture Notes
Spring 1984" Network_Design_and_Implementation_Spring_1984.pdf,
preparing detailed notes on examples of networks.
Considering what you have read in Chapers 2 and 3, be prepared to propose a
practical series of steps you would use if you had been asked to design the
infrastructure of wires in some appropriate topology with appropriate capacities for a
real packet-switched network using TCP/IP. Be prepared to list the questions you
would ask and the approach you would take to coming up with a design.
Note: There will be no class on Thursday 24 March 2011.
Assignment #5, assigned Thursday, 31 March 2011, due Thursday 7 April 2011
Working with your classmates, write a program that will compute optimal
capacities for a network using the Kleinrock approximation. The program
must accept the following inputs:
A count, n, of the lines in the network;
A list of offered loads r[i] for each line in bits per second;
A distance d[i] along each edge;
The factor, mu, that gives the constant factor of proportionailty
between capacities, C[i] and service rates in bits per second, rs[i] = mu*C[i];
A target delay W[0];
The program should minmize total costs assuming costs if proportional to the
sume of the products of the costs and the distance.
The entire class may share one working program, but everybody is responsible
for being able to describe the design of the program in detail. You should
follow what you read in Chapter 3 (pp 59 --96) of
H. J. Bernstein, M. Goldstein, "Network Design and Implementation Lecture Notes
Spring 1984" Network_Design_and_Implementation_Spring_1984.pdf.
Be prepared to describe in detail how you can apply this program to
your project.
Assignment #6, assigned Thursday, 7 April 2011, due Thursday 14 April 2011
and Thursday 21 April 2011
Working with your classmates, write a program that will generate an
acceptable topology to provide redundant connections that will satisfy
a list of offered loads, and realistically allocate capacity to
minimize cost for a given delay. The required
inputs are:
A count, n, of the nodes in the network;
A list of offered loads load[i][j] for each pair of nodes in bits per
second;
A list of all distances dist[i][j] for each pair of nodes. Note that
it is not necessarily true that dist[i][j] == dist[j][i];
The required degrees, conn[i][j], of node-disjoint connectivity for each
pair of nodes. In all cases the program must force conn[i][j] >= 2
for any pair of nodes with any offered load. Note that it is not
necessarily true that conn[i][j] == conn[j][i];
A count, m, of available media;
Lists of capacity, cap[k], and cost per unit length, cost[k] for each
medium k, 0 < k < m;
The factor, mu, that gives the constant factor of proportionailty
between capacities, C[i] and service rates in bits per second, rs[i] = mu*C[i];
A target delay W[0];
This program should apply the graph theory you have learned to generate
a reasonable topology that satisfies the required offered loads and the
connectivity constraint, and the Kleinrock approximation to minimize the
cost. While a final working program would return to try alternate
topologies and then redo the capacities, for this exercise, just do
one forward pass.
The entire class may share one working program, but everybody is responsible
for being able to describe the design of the program in detail. You must
have a designated representative to present a first draft of this program
in class on 14 April and a final version of this program in class on
21 April.
Be prepared to describe in detail how you can apply this program to
your project.
Assignment #7, assigned Thursday, 21 April 2011, due Thursday 28 April 2011.
You must prepare your project as presentation as a web page and/or as a
PDF and/or as a PPT to submit on 28 April, and each group must do a 20 minute
(20 slide) first presentation of their project. For this first presentation, one
member of the group may handle the entire job.
Assignment #8, assigned Thursday, 28 April 2011, due Thursday 5 May 2011.
Based on discussion and comments in your first presentation, you must update
your project and a final presentation as a web page and/or as a
PDF and/or as a PPT to submit on 5 May, and each group must do a 40 minute
(40 slide) presentation of their project in which each member of the project
team handles some coherent aspect of the presentation.
Final: There will be an in-class open notes, closed book final on Thursday,
12 May 2011. This is the final meeting of the class. You must take the final
even if you are requesting an incomplete, so we will both have a clear idea
of what you still need to do to complete the course.
