A Course on Network Optimization and Design
Recently I was asked to teach a ten week graduate course on network optimization and design. Below you will find course lecture slides and a large assortment of sample code used for solving network design problems and creating and solving the examples given in the lecture slides.
This was a survey course on network analysis and design and takes a hands on approach via the simulation, formulation, and/or solution of a number of interesting networking problems via the Python programming language, several open source Python libraries, and open source Linear Programming/MIP solvers. A major thrust of the course was to get students to understand how the various data and control plane networking technologies lead to constraints in various network design problems.
This course made use of the excellent textbook/reference: Michal Pioro and Deepankar Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004. In addition to the course text many freely available supplementary materials were also used.
If you have comments, questions, suggestions, or would like to collaborate on further developing course materials send an email to Dr. Greg Bernstein.
- Course Intro
Who we are, what the course is about and such...
- Network Technologies from a
Design Point of View
Here we review common networking technologies from the point of view of design and optimization. In particular how do data plane and control plane technologies enhance or limit our ability to design efficient networks. We consider IP, Ethernet, MPLS, TDM, WDM, and accompanying control planes such as OSPF, learning bridges, WSON, SDN/Openflow.
- Introduction to Python
A quick introduction to Python and why we will be using it for network design.
- Random Variable Review
Written to even the playing field and jog my memory. Of additional note contains some nice free references on random variables and hints on using random variables in Python.
- Queueing Theory Overview
A quick overview of queueing theory aimed at packet/circuit switches and data centers; A great free reference from arxiv on queueing theory for data/tele communications; An introduction to reviewing the literature for results with a particularly current article on ISP traffic from access to core.
- Discrete Event Simulation
Introduction to discrete event simulation. Overview of some popular simulators. Simulation of queueing models with SimPy.
- Basic Network Design
Networks, graphs, nodes, links, and paths. Introduction to link-path and node-link formulations of network design problems and their resulting linear programming problems. Using Python to automate the formulation and solution process.
- Network Visualization and Information Sharing
Illustrates how to work with network topologies, demands, and paths via Python and JSON.
- Capacitated Network Design in Depth
Design problems for networks with fixed capacity links. Issues include "path splitting" and inverse multiplexing. Computational complexity of different problem variants. Both link-path and node-link formulations are used.
- Flows to Paths
Hits the somewhat subtle issue of recovering paths from "flow solutions" in node-link formulated problems. Optional.
- Network Dimensioning Design Problems
Network link sizing problems. Both continuous and modular link sizes. Discussion of complexity of problem variants.
- Linear and Mixed Integer Programming
A whirlwind tour of linear and mixed integer programming. References to free tutorials and software. A bit of a taste of how the algorithms work and a branch and bound example walk through.
- Shortest Paths and Such...
A quick review of Bellman-Ford and Dijkstra algorithms with simple Python implementations for reinforcement. The concept of a "widest path" and the modification of Dijkstra code to compute them. An overview of k-shortest loopless paths.
- Topology Design -- Access
An access network design problem and formulation with examples. Fun stuff!
- Topology Design -- Link Placement
Link placement design problems with OpEx and CapEx included via constraints and objectives. Fun stuff!
- Multi Layer Design Part I
Review of multi-layer networks. Multi-layer network modeling including a simple JSON format. Capacitated design in multi-layer network. Full walk through of a link-path example.
- Multi Layer Design Part II
Deals with path splitting in multi-layer networks and single path allocation constraints; Modular dimensioning of multi-layer networks; Example walk throughs. Fun stuff!
- Shortest Path Networking Design
Introduction to optimization of shortest path networks, i.e., IP and Ethernet networks utilizing shortest path protocols to compute packet routes based on "shortest paths". Ran out of time to implement a MIP problem formulation. But will revisit this for the next time!