MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEEdge-partitioning regular graphs (with traffic grooming as an excuse)
par Ignasi Sau
| Date : | 02/07/09 | | Time : | 14h | | Location : | Salle Lagrange gris |
Traffic grooming is a major issue in optical networks. It refers to grouping low rate signals into higher speed streams, in order to reduce the equipment cost. In SONET WDM networks, this cost is mostly given by the number of electronic terminations, namely Add-Drop Multiplexers (ADMs for short). We consider the unidirectional ring topology with a generic grooming factor C, and in this case, in graph-theoretical terms, the traffic grooming problem consists in partitioning the edges of a request graph into subgraphs with at most C edges, while minimizing the total number of vertices of the decomposition. We introduce the pseudo-dynamic case when the request graph has bounded degree $\Delta$, and our aim is to design a network (namely, place the ADMs at each node) being able to support ANY} request graph with maximum degree at most $\Delta$. The existing theoretical models in the literature are much more rigid, and do not allow such adaptability. We show that the problem is essentially equivalent to finding the least integer $M(C,\Delta)$ such that the edges of any graph with maximum degree at most $\Delta$ can be partitioned into subgraphs with at most $C$ edges and each vertex appears in at most $M(C,\Delta)$ subgraphs. We establish the value of $M(C,\Delta)$ for almost all values of $C$ and $\Delta$, leaving open only the case where $\Delta \geq 5$ is odd, $\Delta \pmod{2C}$ is between $3$ and $C-1$, $C\geq 4$, and the request graph does not contain a perfect matching. For these open cases, we provide upper bounds that differ from the optimal value by at most one.
This is joint work with Zenthao Li and Xavier Muñoz.
Page des séminaires
| 
