Generalized butterfly graph and its application to video stream authentication

This paper presents the generalized butterfly graph (GBG) and its application to video stream authentication. Compared with the original butterfly graph, the proposed GBG provides significantly increased flexibility, which is necessary for streaming applications, including supporting arbitrary bit-rate budget for authentication and arbitrary number of video packets. Within the GBG design, the problem of constructing an authentication graph is defined as follows: given the total number of packets to protect, the expected packet loss rate for the network, and the available overhead budget, how should one design the authentication graph to maximize the probability that the received packets are verifiable? Furthermore, given the fact that media packets are typically of unequal importance, we explore two variants of the GBG authentication, packet sorting and unequal authentication protection, which apply unequal treatment to different packets based on their importance. Lastly, we examine how the proposed GBG authentication can be applied within the context of rate-distortion-authentication (R-D-A) optimized streaming: given a media stream protected by GBG authentication, the R-D-A optimized streaming technique computes an optimized transmission schedule by recognizing and accounting for the authentication dependencies in the GBG authentication graph. Index Terms--Butterfly, generalized butterfly graph (GBG), R-D-A optimization, stream authentication.