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 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>

\forall (a,b) \in E, a \in I \text{ or } b \in I \text{ or } a,b \in I </math>

• <math>

type : C \to \mathbb{N} \text{ and } \forall x,y \in C, x \neq y, x \equiv y \iff type(x) = type(y) </math>

Note that we specifically allow multigraphs here.

A reservation is represented as a set of components, a set of edges, and a time interval during which the components and edges will be assigned to this reservation. Time is discretized into slots. All active reservations during any one time slot must be non-overlapping i.e., no component or edge is assigned to more than 1 reservation.

Accepted reservations <math>R = \lbrace r_{1},r_{2},\dots,r_{m} \rbrace</math> where <math>r_{i} = ( C_{i},E_{i},b_{i},e_{i} )</math>, <math>C_{i}</math> is the set of components for reservation <math>i</math>, <math>E_{i}</math> is the set of edges for reservation <math>i</math>, <math>b_{i}</math> is the time slot when reservation <math>i</math> becomes active, <math>e_{i}</math> is the time slot when reservation <math>i</math> ends, and

• <math>

\forall i, C_{i} \subseteq C, E_{i} \subseteq E </math>

• <math>

\forall \text{ time slots } k \text{ and } \forall \text{ reservations } i,j, b_{i} \le k \le e_{i}, b_{j} \le k \le e_{j} \Rightarrow C_{i} \cap C_{j} = \empty, E_{i} \cap E_{j} = \empty </math>

A reservation request is similar to a reservation except that the components have not yet been mapped onto components in the physical topology, and edges connect components directly instead of indirectly through the infrastructure nodes. Additionally, the request specifies an interval of starting time slots and length of time for the reservation to last.