Difference between revisions of "Dev:onl reservation algorithm"

From ARL Wiki
Jump to navigationJump to search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
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 ==
 
== 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 ``infrastructure nodes'' which are not directly
+
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
+
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 ``type'' which is an abstract label
+
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
+
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.
  
Line 25: Line 13:
 
components, and <math>E</math> is the set of edges, where
 
components, and <math>E</math> is the set of edges, where
  
−
<math>
+
*:<math>
−
\begin{align}
+
\forall (a,b) \in E, a \in I \text{ or } b \in I \text{ or } a,b \in I
−
&\forall (a,b) \in E, a \in I \text{ or } b \in I \text{ or } a,b \in I
+
</math>
−
&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>
 +
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>
 
</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.

Retrieved from "http://wiki.arl.wustl.edu/index.php?title=Dev:onl_reservation_algorithm&oldid=222"