  Motivated by the desire to utilize a limited number of configurable optical
switches by recent advances in Software Defined Networks (SDNs), we define an
online problem which we call the Caching in Matchings problem. This problem has
a natural combinatorial structure and therefore may find additional
applications in theory and practice.
  In the Caching in Matchings problem our cache consists of $k$ matchings of
connections between servers that form a bipartite graph. To cache a connection
we insert it into one of the $k$ matchings possibly evicting at most two other
connections from this matching. This problem resembles the problem known as
Connection Caching, where we also cache connections but our only restriction is
that they form a graph with bounded degree $k$. Our results show a somewhat
surprising qualitative separation between the problems: The competitive ratio
of any online algorithm for caching in matchings must depend on the size of the
graph.
  Specifically, we give a deterministic $O(nk)$ competitive and randomized $O(n
\log k)$ competitive algorithms for caching in matchings, where $n$ is the
number of servers and $k$ is the number of matchings. We also show that the
competitive ratio of any deterministic algorithm is
$\Omega(\max(\frac{n}{k},k))$ and of any randomized algorithm is $\Omega(\log
\frac{n}{k^2 \log k} \cdot \log k)$. In particular, the lower bound for
randomized algorithms is $\Omega(\log n)$ regardless of $k$, and can be as high
as $\Omega(\log^2 n)$ if $k=n^{1/3}$, for example. We also show that if we
allow the algorithm to use at least $2k-1$ matchings compared to $k$ used by
the optimum then we match the competitive ratios of connection catching which
are independent of $n$. Interestingly, we also show that even a single extra
matching for the algorithm allows to get substantially better bounds.
