Herbert J. Bernstein Professor of Computer Science Dept. of Mathematics and Computer Science, 1300 William Floyd Parkway, B111B Shirley, NY 11967
22238 CSC 2281A Network Design & Queuing Theory Spring 2012 On Line Course Assignments

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC2281S12/CSC2281_Assignments.html
Copyright © 2011, 2012 Herbert J. Bernstein and other parties. All rights reserved.

This is an online course. 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. No assignments will be accepted late. No assignments will be accepted on paper. No assignments will be accepted on computer media, CDs, or thumb drives. 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.

General Process for Doing this Course

You will have assignments that require you to do readings, view web sites, take quizzes and exams on line, and prepare materials on the web. There are no formal class meetings for this course, but we will try to schedule both individual and groups Skype sessions. It is very important that you keep up with the work, or you will find yourself at the end of the semeter with an entire semester of work still to do.

You will have a quiz to do every week of this course. You will find the quiz links on this page as the course progresses.

• Assignment #1, assigned Friday, 27 January 2012, due Friday, 3 February 2012.
  • If you have not already done so, download Skype and create a Skype account for yourself.
  • Email your Skype ID to the instructor:
  • The instructor will then send you a contact request, which you should accept.
     
    
  • Start reading the syllabus and get your text books.
  • 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. You may work solo or in a team. If you are willing to work in a team, be certain to say so in your project proposal.
  • Schedule your first Skype meeting with the instructor.
  • Do Quiz 1. This quiz only asks question through the material on queuing theory, but please do the graph theory readong now. You will have more reading to do on the next assignment that will build on the graph theory part.

• Assignment #2, assigned Friday, 3 February 2012, revised Sunday, 5 February 2012, due Friday, 10 February 2012.
  • 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.
  • Carefully read Wikipedia Queuing Theory Article and take notes.
  • Carefully read Wkipedia M/M/1 Queue Article and Wikipedia M/M/c Queue Article and take notes.
  • Carefully read Wikipedia Erlang Article and take notes.
  • Carefully read Wikipedia Little's Law Article and take notes.
  • Carefully watch Stay in Queue
  • Carefully listen to Graph Implementations, Graphs: Dijkstra's Algorithm and UC Davis Dijkstra's shortest path algorithm and take notes.
  • Carefully read Wikipedia Ford-Fulkerson Algorithm Article and take notes.
  • Carefully watch IIT Madras Lec-21 Successive Shortest Path Problem and IIT Madras Lec-22 Maximum Flow Problem and take notes.
  • Redo all of Quiz 1.
  • Do Quiz 2. This is a very difficult quiz. You will do much better is you take the time to have a Skype session with the instructor before trying to do it and if you form a study group, but do not put off doing the reading and trying the quiz.

• Assignment #3, assigned Friday, 10 February 2012, due Friday, 17 February 2012.
  • 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.
  • Do Quiz 3.

• Assignment #4, assigned Friday, 17 February 2012, due Friday, 24 February 2012.
  • Your goal for the week is to become proficient in working with the Ford-Fulkerson Max Flow Min Cut algorithm. You will find working implementations of an API and test program in MaxFlow.java and MaxFlowTest3.java This package implements Dijkstra's algorithm and uses it to implement Max Flow Min Cut. In working with this package you may consult with anybody you wish, but it is important the you learn to work with it. Be warned -- converting it to work in the undirected case is not as easy as it look.
  • Install and run the package on some computer that has a java compiler. Note that you can install a java compiler on you own laptop or you can use arcib.dowling.edu or you can you any of the many laboratory computers as Dowling.
  • Try the built in test case and change it to do the questions in the following quiz.
  • Do Quiz 4.
  • Go back and redo the earlier quizzes.

• Assignment #5, assigned Friday, 24 February 2012, due Friday, 2 March 2012.
  • Read Chapter 3 (pp 59 --96) of H. J. Bernstein, M. Goldstein, "Network Design and Implementation Lecture Notes Spring 1984" 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.
  • Working either by yourself, or with your classmates, prepare a program that implements the Kleinrock approximation.
  • Do Quiz 5.
  • Go back and redo the earlier quizzes.

• Midterm: The CSC2281 midterm will be given during a 2-hour supervised Skype session on or before Friday, 9 March 2012. The default time is Monday, 5 March 2012 from 8 pm to 10 pm. If you wish to propose an alternate time contact the instructor via Skype IM or email no later than Friday 2 March 2012.

• Assignment #6, assigned Friday, 9 March 2012, due Friday, 16 March 2012.
  • The rest of this semester will revolce around applying the tools you have learned to your project. You must see the instructor in person or via Skype to firmly settle the scope of your project no later than on Monday 12 March 2012.
  • Form this point on, you must post information on your project progress on your blog no less often than once per week. What you post should reflect both your specific contributions to the project and your own understanding of the progres of the project as a whole.
  • Working either by yourself or with your classmates you were to have writen a program that will compute optimal capacities for a network using the Kleinrock approximation. Make a version of the program will 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 minimize total costs assuming costs are proportional to the sum 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.

    You will need a running version of this program to answer the questions on the next quiz. The source of the program is to be posted on your Google Sites account and you must describe in detail how you can apply this program to your project on your web site and in summary form on your blog.

  • Gather as much data as you can on offered loads for your project and post them on your Google sites web site.
  • Do Quiz 6.

• Assignment #7, assigned Friday, 16 March 2012, due Friday, 23 March 2012, Friday 30 March 2012 and Friday 20 April 2012.

  This long assignment will have three quizzes to track your progress, but your real job is not the quizzes, but to assemble the software and data for your network design project and to do it.

  • First the tools: working with your classmates or any others yo can interest, 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. This program is just the sum of everything you should have put together to be able to do your project. You may do it as one big program, or several smaller ones, but you need it to do almost any network design. Post the working program to your web site and summarize its status in your blog. Everybody had to post it, even if only one person does the programming.

  • Be prepared to describe in detail how you can apply this program to your project.
  • Do Quiz 7 on or before 23 March 2012.
  • There will be a group video Skype conference on Monday, 26 March 2012 at 8pm for students to discuss this program and their projects. Any students who cannot join that discussion must schedule an alternate dicsussion to be held prior to 26 March 2012.
  • Based on whatever data you have collected and the program you have written, do a preliminary design for your network and post it to your website with a brief discussion in your blog.
  • Do Quiz 8 on or before 30 March 2012.
  • Take whatever network you end up with, an go through at least 2 more cycles of changing the topopogy and optimizing the capacities.
  • Complete your network design project and prepare a complete presentation as a web site. You have until after Spring Break to get it done, but you are not likely to finish it unless you work on it steadily.
  • There will be a group video Skype conference on Monday, 16 April 2012 at 8pm for students to discuss their projects. Any students who cannot join that discussion must schedule an alternate dicsussion to be held prior to 16 April 2012.
  • Do Quiz 9 on or before 20 April 2012 Your project must be complete before you take this quiz.

• Assignment #8, assigned Friday, 20 April 2012, due Friday, 4 May 2012.
  • In the prior assignment you should have submitted your project in answer to a quiz question. If you did so, then by early in this assignment period, you should have the instructor's feedback on what you have done. Using that feedback and whatever other feedback you can get, set up you Google sites website with best presentation you can put together of your project.
  • Add to your Google sites web site you best versions of software tools you used for your project, and all other assignments for the semester.
  • When you have your web site ready for final evaluation, email the URL to the instructor. Note -- even if several student participated in the work and have helped each other, each student must prepare a separate web site.
  • Do Quiz 10 on or before 4 May 2012.
  • The only items that will be accepted for grading within this semster after 4 May 2012 are: improvements to the project itself, no more than three redone quizzes and the final. Except for the final that work must be turned in no later than 5 pm on Friday, 11 May 2012.

• Final Exam: The final exam will be a 2 hour Skype-supervised session, from 8 to 10 pm on Monday 14 May 2012. For the final you will need a computer with a webcam, Skype installed and your Dowling student ID. If you cannot be available then, you must arrange an alternate date for the exam with the instructor. You must make the arrangements on or before 1 May 2012. All work other than the final to be considered for grading must have been completed and turned in no later than 5 pm on Friday, 11 May 2012.