  Content Delivery Networks (CDN) are witnessing the outburst of video
streaming (e.g., personal live streaming or Video-on-Demand) where the video
content, produced or accessed by mobile phones, must be quickly transferred
from a point to another of the network. Whenever a user requests a video not
directly available at the edge server, the CDN network must 1) identify the
best location in the network where the content is stored, 2) set up a
connection and 3) deliver the video as quickly as possible. For this reason,
existing CDNs are adopting an overlay structure to reduce latency, leveraging
the flexibility introduced by the Software Defined Networking (SDN) paradigm.
In order to guarantee a satisfactory Quality of Experience (QoE) to users, the
connection must respect several Quality of Service (QoS) constraints. In this
paper, we focus on the sub-problem 2), by presenting an approach to efficiently
compute and maintain paths in the overlay network. Our approach allows to speed
up the transfer of video segments by finding minimum delay overlay paths under
constraints on hop count, jitter, packet loss and relay processing capacity.
The proposed algorithm provides a near-optimal solution, while drastically
reducing the execution time. We show on traces collected in a real CDN that our
solution allows to maximize the number of fast video transfers.
