  We consider multicommodity flow and cut problems in {\em polymatroidal}
networks where there are submodular capacity constraints on the edges incident
to a node. Polymatroidal networks were introduced by Lawler and Martel and
Hassin in the single-commodity setting and are closely related to the
submodular flow model of Edmonds and Giles; the well-known maxflow-mincut
theorem holds in this more general setting. Polymatroidal networks for the
multicommodity case have not, as far as the authors are aware, been previously
explored. Our work is primarily motivated by applications to information flow
in wireless networks. We also consider the notion of undirected polymatroidal
networks and observe that they provide a natural way to generalize flows and
cuts in edge and node capacitated undirected networks.
  We establish poly-logarithmic flow-cut gap results in several scenarios that
have been previously considered in the standard network flow models where
capacities are on the edges or nodes. Our results have already found
aplications in wireless network information flow and we anticipate more in the
future. On the technical side our key tools are the formulation and analysis of
the dual of the flow relaxations via continuous extensions of submodular
functions, in particular the Lov\'asz extension. For directed graphs we rely on
a simple yet useful reduction from polymatroidal networks to standard networks.
For undirected graphs we rely on the interplay between the Lov\'asz extension
of a submodular function and line embeddings with low average distortion
introduced by Matousek and Rabinovich; this connection is inspired by, and
generalizes, the work of Feige, Hajiaghayi and Lee on node-capacitated
multicommodity flows and cuts. The applicability of embeddings to polymatroidal
networks is of independent mathematical interest.
