Difference between revisions of "Dev:onl reservation algorithm"
(New page: 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 b...) |
|||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Problem Statement == | == Problem Statement == | ||
Before giving the actual problem statement, the various pieces and abstractions are described. | Before giving the actual problem statement, the various pieces and abstractions are described. | ||
| − | The physical topology is represented by a set of | + | The physical topology is represented by a set of ''infrastructure nodes'' which are not directly |
| − | visible to the user, | + | 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 | infrastructure nodes and components together. Every component only has edges to infrastructure | ||
| − | nodes, never other components. Every component also has a | + | nodes, never other components. Every component also has a ''type'' which is an abstract label |
| − | representing the component's physical characteristics ( | + | 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. | 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 | 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, | + | 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. | ||
Latest revision as of 12:52, 12 August 2008
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.
