多信道广播组总延误端到端延迟变化路由问题

摘要

在高速分组交换环境中,提出了构造多信道广播树,且满足实时交互性应用端到端变化要求的总延误问题.多信道广播路由将寻找从源到包括所有多信道广播终端的一棵有根树.在多媒体应用中,关于路由问题有两种要求:最小总延误和延迟变化.在实践中链路延迟和终端延迟的概念是有区别的.重新定义延迟的概念,也就是端到端的路径延迟定义为截止延迟或界定延迟,延误成员数的延迟定义为松驰延迟.终端的松驰延迟具有的特征是沿着一棵树从源到任何一个终端的累积延迟可以超过松驰延迟的值.确定这样一棵约束树的问题是NP-完全的.由时间的复杂性和动态成员的灵活性,提出了一个有效的启发式算法.%The problem of multicast group total tardiness of constructing multicast trees to meet end-to-end variation requirements of real-time interactive applications operating in high-speed packet-switched environments is presented. There may be two requirements of multicast routing in many multimedia applications: minimum total tardiness and minimum delay variation. In particular, a distinction can be made between the concept of the delay of the link and concept of the delay of destination. The new concept of the delay is redefined, that is, routine end-to-end delay is defined as "deadline delay" or "bounded delay" and the delay of number of tardy member in this paper is defined as "slack delay". The problem of determining such a constrained tree is NP-complete. A heuristic algorithm which this paper presents is very efficient in terms of the time complexity and flexible in dynamic membership changes.