IE341 Spring 09

Click here to get a copy of the syllabus.

This course deals with the design and analysis of telecommunication networks. The students will learn how network models allow to create networks that satisfy various types of traffic demands and robustness constraints. Networks will also be simulated to assess the robustness and performance of the outcome of the design process. We will cover the design and analysis of:

  • local, metropolitan, and wide area networks;
  • wireless networks;
  • distributed computing networks.

The prerequisite for this course are IE220 and IE224. As the network design process is strongly optimization-dependent, notions of Operations Research will be used throughout the course.

Meeting:

  • Mohler 451, Mon/Wed, 1:10pm-2:25pm.
  • Mohler 444, Friday, 12:10pm-2:00pm

Lecture calendar

  1. 01/12/2009: Introduction (notes).
  2. 01/14/2009: Graphs, complexity, optimization (notes).
  3. 01/19/2009: The Network Design Problem (notes).
  4. 01/21/2009: Examples of network design problems. Branch&Bound (notes).
  5. 01/26/2009: Branch&Bound. The Flow Deviation algorithm (notes).
  6. 01/26/2009: Path models for the Linear MCF problem (notes).
  7. 02/01/2009: Column generation for the Linear MCF problem (notes).
  8. 02/04/2009: Branch&Price. Cut-set inequalities. Examples of path models (notes).
  9. 02/09/2009: Partition inequalities. IP routing and OSPF (notes).
  10. 02/11/2009: OSPF in IP networks (notes).
  11. 02/16/2009: Wireless networks: an introduction (notes).
  12. 02/18/2009: Antenna Configuration Optimization. Midterm practice (notes).
  13. 02/23/2009: Errata on the BS and ACO problems. Midterm practice (notes).
  14. 02/24/2009: Midterm exam, Mohler 451, 4pm-5pm. Closed book, closed notes.
  15. 02/25/2009: Frequency Assignment Problems (FAP) (notes).
  16. 03/09/2009: Minimum-Interference FAP (notes).
  17. 03/11/2009: Ad-hoc networks. Scheduling problems (notes).
  18. 03/16/2009: Ad-hoc networks. Broadcast and multicast problems (notes).
  19. 03/18/2009: Heuristics for broadcast and multicast problems. Protection and restoration in wired networks (notes).
  20. 03/23/2009: Protection and restoration. Uncertainty in the traffic demand (notes).
  21. 03/25/2009: Robust Network design: an example (notes).
  22. 03/30/2009: Simulation in networks. Queues (notes).
  23. 04/01/2009: Queues (notes).
  24. 04/06/2009: Queue networks. Simulation. Compartmental models (notes).
  25. 04/08/2009: Simulation with a compartmental model (notes).
  26. 04/13/2009: Simulation: techniques (notes).
  27. 04/15/2009: Case study #1: Shared protection (no notes).
  28. 04/20/2009: Final practice (notes).
  29. 04/22/2009: Final practice, cont’d (notes).
  30. 04/28/2009: Final, Mohler 355, 8am-11am. Closed book, closed notes.

Lab calendar

  1. 01/16/2009: AMPL, Neos (notes).
  2. 01/23/2009: Two problems in wired network design (notes).
  3. 01/30/2009: Path formulations for the LMCF (notes).
  4. 02/06/2009: Column generation and cutting planes for the LMCF (notes).
  5. 02/13/2009: OSPF routing (notes).
  6. 02/20/2009: Wireless networks: BS location and ACO (notes). A definition of the problem.
  7. 02/27/2009: The Frequency assignment problem (notes).
  8. 03/13/2009: Comparing MO-, MI, and MS-FAP. Ad-hoc network scheduling (notes).
  9. 03/20/2009: Multicast in ad-hoc networks (notes).
  10. 03/27/2009: Robust network design (notes).
  11. 04/03/2009: Node and link simulation (notes).
  12. 04/10/2009: Network design and simulation (notes).
  13. 04/17/2009: Simulation of a wireless network (notes).

Projects

A small project has to be developed as part of this course, and has an overall impact of 20% on the final grade. Every project consists of

  • modeling a network optimization problem arising in a practical (mainly Telecommunication) application;
  • solving the model on a set of real-world instances, provided with the project;
  • developing a simulation model and running simulations to assess the features of the solution obtained from the Optimization process;
  • presenting and interpreting results.

A short report should be provided in pdf format, within a zip file containing all model, data, and simulation files. The report should be no longer than 10 pages, and should describe the optimization model, the motivation for using variables and constraints, and a summary of the results obtained with the solver and simulation package.

All projects are due by the final exam, April 28 at 8:00am. Each project can be carried out by one or two students. However, for groups of two students an extra part of the work is required, to be discussed with the instructor. If you are interested in a project in particular, send me an email with your intent. Projects, in general, will not be assigned on a first-come, first-served basis, but will be briefly discussed beforehand.

Projects available

  1. A wireless network for a commuter train;
  2. Balanced routing in ad-hoc networks;
  3. Robust management of power grids (assigned);
  4. Shared protection network design: benefits and costs (assigned);
  5. Design of a supercomputing network infrastructure (assigned);
  6. Bit Torrent and multicast routing (assigned);
  7. Robust minimum congestion with dynamic demands (assigned);
  8. Sensor network simulation (assigned);
  9. Node capacity optimization and simulation (assigned).

Course material

  • (textbook) Michal Pioro, Deepankar Medhi. Routing, Flow, and Capacity Design in Communication and Computer Networks (Morgan Kaufmann).
  • (not required) Dimitri P. Bertsekas, Robert G. Gallager. Data Networks (Prentice Hall).
  • A short howto on graphs and Network Optimization models, with hints on how to implement them in AMPL.
  • Handouts on wireless networks and on robustness.

See also the page on Opportunities for students.

Accommodations for Students with Disabilities

If you have a disability for which you are or may be requesting accommodations, please contact both your instructor and the Office of Academic Support Services, University Center C212 (610-758-4152) as early as possible in the semester. You must have documentation from the Academic Support Services office before accommodations can be granted. For more information, please visit the student support services website: http://www.lehigh.edu/~inacsup/disabilities.