Dev:onl reservation algorithm

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.