Posts Tagged ‘VoD
For graph-based authentication, the main challenge is how to design a Directed Acyclic Graph (DAG) with lowest overhead, highest verification probability and lowest sender and receiver delay. However, there are trade-offs between these performance criteria, which are summarized below.
- Computation complexity: The number of hash operations and signature operations required at the sender and receiver. Note that computing a signature is much more complex than computing a hash.
- Overhead size: The extra bytes introduced by stream authentication, including the hashes and signatures appended to the packets. The overhead size is determined by the number of edges in the authentication graph. Note that a signature is much bigger in size than a hash.
- Verification percentage (or verification probability): The percentage of verifiable packets among all the received packets. Intuitively, the more redundant paths a packet has to the signature packet, the higher the probability of being verified.
- Sender delay: The delay at the sender (in number of packets) from the time when the packet is produced by the encoder to the time that all authentication data appended to this packet is ready. Real-time communication scenario requires low sender delay. For non-real-time scenario, e.g., pre-encoded content for VOD applications, it is not important because the sender has prior knowledge of all packets.
- Receiver delay: The delay at the receiver (in number of packets) from the time a packet is received to the time that it can be verified. For authenticated video, each packet must be received and pass the verification before its play out deadline.
A new heuristic algorithm is proposed for constructing multicast tree for multimedia and real-time applications. The tree is used to concurrently transmit packets from source to multiple destinations such that exactly one copy of any packet traverses the links of the multicast tree. Since multimedia applications require some Quality of Service, QoS, a multicast tree is needed to satisfy two main goals, the minimum path cost from source to each destination (Shortest Path Tree) and a certain end-to-end delay constraint from source to each destination. This problem is known to be NP-Complete. The proposed heuristic algorithm solves this problem in polynomial time and gives near optimal tree. We first mention some related work in this area then we formalize the problem and introduce the new algorithm with its pseudo code and the proof of its complexity and its correctness by showing that it always finds a feasible tree if one exists. Other heuristic algorithms are examined and compared with the proposed algorithm via simulation.
Shortest path tree or source-based trees tends to minimize the cost of each path from source to any destination, this can be achieved in polynomial time by using one of the two famous algorithms of Bellman and Dijkstra and pruning the undesired links. Recently, with the rapid evolution of multimedia and real-time applications like audio / video conferencing, interactive distributed games and real-time remote control system, certain QoS need to be guaranteed in the resulted tree. One such QoS, and the most important one, is the end-to-end delay between source and each destination, where the information must be sent within a certain delay constraint D. By adding this constraint to the original problem of multicast routing, the problem is reformulated and the multicast tree should be either delayconstrained Steiner tree, or delay-constrained shortest path tree. Delay constrained Steiner tree is an NP-Complete problem, several heuristics are introduced for this problem each trying to get near optimal tree cost, without regarding to the cost of each individual path for each destination. Delay-constrained shortest path tree is also an NP-Complete problem. An optimal algorithm for this problem is presented at, but its execution time is exponential and used only for comparison with other algorithms. Heuristic for this problem is presented in, which tries to get a near optimal tree from the point of view of each destination without regarding the total cost of the tree. An exhaustive comparison between the previous heuristics for the two problems can be found in. We investigate the problem of delay constrained shortest path tree since it is appropriate in some applications like Video on Demand (VoD), where the multicast group has a frequent change, and every user wants to get his information in the lowest possible cost for him without regarding the total cost of the routing tree. Also shortest path tree always gives average cost per destination less than Steiner tree.