Dev:onl reservation algorithm

The Open Network Lab now uses multiple 52 port gigabit switches to interconnect the hosts, routers, and other hardware (collectively referred to as components) that users can allocate to build their own topologies. The switches are currently connected in a backbone-line topology. They could be connected in a ring topology, but then we can not control which way packets flow around the ring. So we broke the ring be removing the last connection. Each of the inter-switch connections is 12 Gbps.

Users make reservations ahead of time for the topology that they intend to use in their experiments. The reservation algorithm attempts to map the topology onto the physical resources of the testbed if possible, and then records which resources were used so that future reservation requests can not user those specific resources.

Problem Statement

Before giving the actual problem statement, the various pieces and abstractions are described.

The physical topology is represented by a set of ``infrastructure nodes which are not directly visible to the user, ``components which are visible to the user, and edges which connect the infrastructure nodes and components together. Every component only has edges to infrastructure nodes, never other components. Every component also has a ``type which is an abstract label representing the component's physical characteristics ({\it e.g.}, a standard end host, an IXP platform, an NSP). Two components are treated as equivalent if their types are the same.

Physical topology <math>P = (I,C,E)</math> where <math>I</math> is the set of infrastructure nodes, <math>C</math> is the set of components, and <math>E</math> is the set of edges, where

<math> \begin{align} &\forall (a,b) \in E, a \in I \text{ or } b \in I \text{ or } a,b \in I &type : C \to \mathbb{N} \text{ where } \forall x,y \in C, x \neq y, x \equiv y \iff type(x) = type(y) \end{align} </math>