Previous research on SDN traffic engineering mostly focuses on statictraffic, whereas dynamic traffic, though more practical, has drawn much lessattention. Especially, online SDN multicast that supports IETF dynamic groupmembership (i.e., any user can join or leave at any time) has not beenexplored. Different from traditional shortest-path trees (SPT) and graphtheoretical Steiner trees (ST), which concentrate on routing one tree at anyinstant, online SDN multicast traffic engineering is more challenging becauseit needs to support dynamic group membership and optimize a sequence ofcorrelated trees without the knowledge of future join and leave, whereas thescalability of SDN due to limited TCAM is also crucial. In this paper,therefore, we formulate a new optimization problem, named Online Branch-awareSteiner Tree (OBST), to jointly consider the bandwidth consumption, SDNmulticast scalability, and rerouting overhead. We prove that OBST is NP-hardand does not have a $|D_{max}|^{1-epsilon}$-competitive algorithm for any$epsilon >0$, where $|D_{max}|$ is the largest group size at any time. Wedesign a $|D_{max}|$-competitive algorithm equipped with the notion of thebudget, the deposit, and Reference Tree to achieve the tightest bound. Thesimulations and implementation on real SDNs with YouTube traffic manifest thatthe total cost can be reduced by at least 25% compared with SPT and ST, and thecomputation time is small for massive SDN.
展开▼
