如何提供不同的服务质量(quality of service,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-service routing,简称QoSR)则是其中的核心技术和热点问题.QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的...如何提供不同的服务质量(quality of service,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-service routing,简称QoSR)则是其中的核心技术和热点问题.QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的两个目标:(1) 满足业务QoS需求;(2) 最大限度地提高网络利用率.由于QoSR是NP完全问题,研究者们设计了很多启发式算法进行了广泛深入的研究.在有权图和QoS度量的基础上介绍了QoSR的基本概念,详细分析了面向单播应用的QoSR算法中的热点问题,并按照所求解的问题类型和求解方法,将这些算法分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.在分析每类中典型算法的基础上,总结和对比了各类的特点,进而详细剖析了算法的有效性,并基于此总结了基于概率模型求解QoSR问题的方法.最后指出了该领域中需要进一步研究的热点问题.展开更多
The exchanged hypercube EH（s, t） （where s ≥ 1 and t ≥ 1） is obtained by systematically reducing links from a regular hypercube Q,＋t＋l. One-step diagnosis of exchanged hypercubes which involves only one testi...The exchanged hypercube EH（s, t） （where s ≥ 1 and t ≥ 1） is obtained by systematically reducing links from a regular hypercube Q,＋t＋l. One-step diagnosis of exchanged hypercubes which involves only one testing phase during which processors test each other is discussed. The diagnosabilities of exchanged hypercubes are studied by using the pessimistic one-step diagno- sis strategy under two kinds of diagnosis models： the PMC model and the MM model. The main results presented here are the two proofs that the degree of diagnosability of the EH（s, t） under pessimistic one-step tl/tl fault diagnosis strategy is 2s where I ≤ s ≤ t （respectively, 2t, where 1 ≤ t ≤ s） based on the PMC model and that it is also 2s where 1 ≤ s ≤ t （respectively, 2t, where 1 ≤ t ≤ s） based on the MM＊ model.展开更多
Connectivity is a vital metric to explore fault tolerance and reliability of network structure based on a graph model. Let be a connected graph. A connected graph G is called supper-κ (resp. supper-λ) if every minim...Connectivity is a vital metric to explore fault tolerance and reliability of network structure based on a graph model. Let be a connected graph. A connected graph G is called supper-κ (resp. supper-λ) if every minimum vertex cut (edge cut) of G is the set of neighbors of some vertex in G. The g-component connectivity of a graph G, denoted by , is the minimum number of vertices whose removal from G results in a disconnected graph with at least g components or a graph with fewer than g vertices. The g-component edge connectivity can be defined similarly. In this paper, we determine the g-component (edge) connectivity of varietal hypercube for small g.展开更多
基金supported by the National Natural Science Fundation of China(61363002)
文摘The exchanged hypercube EH（s, t） （where s ≥ 1 and t ≥ 1） is obtained by systematically reducing links from a regular hypercube Q,＋t＋l. One-step diagnosis of exchanged hypercubes which involves only one testing phase during which processors test each other is discussed. The diagnosabilities of exchanged hypercubes are studied by using the pessimistic one-step diagno- sis strategy under two kinds of diagnosis models： the PMC model and the MM model. The main results presented here are the two proofs that the degree of diagnosability of the EH（s, t） under pessimistic one-step tl/tl fault diagnosis strategy is 2s where I ≤ s ≤ t （respectively, 2t, where 1 ≤ t ≤ s） based on the PMC model and that it is also 2s where 1 ≤ s ≤ t （respectively, 2t, where 1 ≤ t ≤ s） based on the MM＊ model.
文摘Connectivity is a vital metric to explore fault tolerance and reliability of network structure based on a graph model. Let be a connected graph. A connected graph G is called supper-κ (resp. supper-λ) if every minimum vertex cut (edge cut) of G is the set of neighbors of some vertex in G. The g-component connectivity of a graph G, denoted by , is the minimum number of vertices whose removal from G results in a disconnected graph with at least g components or a graph with fewer than g vertices. The g-component edge connectivity can be defined similarly. In this paper, we determine the g-component (edge) connectivity of varietal hypercube for small g.
