Efficient Routing Protection Algorithm Based on Optimized Network Topology

Network failures are unavoidable and occur frequently. When the network fails, intra-domain routing protocols deploying on the Internet need to undergo a long convergence process. During this period, a large number of messages are discarded, which results in a decline in the user experience and severely affects the quality of service of Internet Service Providers (ISP). Therefore, improving the availability of intra-domain routing is a trending research question to be solved. Industry usually employs routing protection algorithms to improve intra-domain routing availability. However, existing routing protection schemes compute as many backup paths as possible to reduce message loss due to network failures, which increases the cost of the network and impedes the methods deployed in practice. To address the issues, this study proposes an efficient routing protection algorithm based on optimized network topology (ERPBONT). ERPBONT adopts the optimized network topology to calculate a backup path with the minimum path coincidence degree with the shortest path for all source purposes. Firstly, the backup path with the minimum path coincidence with the shortest path is described as an integer programming problem. Then the simulated annealing algorithm ERPBONT is used to find the optimal solution. Finally, the algorithm is tested on the simulated topology and the real topology. The experimental results show that ERPBONT effectively reduces the path coincidence between the shortest path and the backup path, and significantly improves the routing availability.     

A Genetic Algorithm to Solve Capacity Assignment Problem in a Flow Network

Computer networks and power transmission networks are treated as capacitated flow networks. A capacitated flow network may partially fail due to maintenance. Therefore, the capacity of each edge should be optimally assigned to face critical situations—i.e., to keep the network functioning normally in the case of failure at one or more edges. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. The RDP is known as NP-hard. Thus, capacity assignment problem subject to system reliability and total capacity constraints is studied in this paper. The problem is formulated mathematically, and a genetic algorithm is proposed to determine the optimal solution. The optimal solution found by the proposed algorithm is characterized by maximum reliability and minimum total capacity. Some numerical examples are presented to illustrate the efficiency of the proposed approach.     

一种基于多播路由图的最小子树图搜索算法

提出了一种基于网络编码的新的多播路由算法,该算法在搜索信源节点到各接收者路径族的过程中,考虑了不同路径族之间链路的共享,以降低带宽资源消耗,提高网络性能.基于得到的多播路由图,提出了一种最小子树图搜索算法,并利用最小子树图的性质,对相应于多播路由图的子树图进行化简.最后,在最小子树图上进行有效的网络编码,所有的网络编码问题可以简化为搜索多播网络的最小子树图问题.     

Energy-efficient cluster-based scheme for failure management in sensor networks

Wireless sensor networks are characterised by dense deployment of energy constrained nodes. Owing to the deployment of large number of sensor nodes in uncontrolled hostile environments and unmonitored operation, it is common for the nodes to exhaust its energy and become inactive. The failing nodes create holes in the network topology causing connectivity loss, which may lead to critical information loss. To avoid degradation of performance, it is necessary that the failures are detected well in advance and appropriate measures are taken to sustain the network operation. An energy-efficient cluster-based technique is proposed to detect failures and recover the cluster structure. The proposed technique relies on the cluster members to detect the failures in the cluster and recover the connectivity. The proposed failure detection and recovery technique recovers the cluster structure in less than one-fourth of the time taken by the Gupta algorithm and is also proven to be 70% more energy-efficient than the same. The proposed cluster-based failure detection and recovery scheme proves to be an efficient and quick solution to robust and scalable sensor network for long and sustained operation.     

A simple MC-based algorithm for evaluating reliability of stochastic-flow network with unreliable nodes

A MP/minimal cutset (MC) is a path/cut set such that if any edge is removed from this path/cut set, then the remaining set is no longer a path/cut set. An intuitive method is proposed to evaluate the reliability in terms of MCs in a stochastic-flow network subject to both edge and node failures under the condition that all of the MCs are given in advance. This is an extension of the best of known algorithms for solving the d-MC (a special MC but formatted in a system-state vector, where d is the lower bound points of the system capacity level) problem from the stochastic-flow network without unreliable nodes to with unreliable nodes by introducing some simple concepts. These concepts were first developed in the literature to implement the proposed algorithm to reduce the number of d-MC candidates. This method is more efficient than the best of known existing algorithms regardless if the network has or does not have unreliable nodes. Two examples are illustrated to show how the reliability is determined using the proposed algorithm in the network with or without unreliable nodes. The computational complexity of the proposed algorithm is analyzed and compared with the existing methods.     

Robust Cluster-Based Routing Protocol for IoT-Assisted Smart Devices in WSN

The Internet of Things (IoT) is gaining attention because of its broad applicability, especially by integrating smart devices for massive communication during sensing tasks. IoT-assisted Wireless Sensor Networks (WSN) are suitable for various applications like industrial monitoring, agriculture, and transportation. In this regard, routing is challenging to find an efficient path using smart devices for transmitting the packets towards big data repositories while ensuring efficient energy utilization. This paper presents the Robust Cluster Based Routing Protocol (RCBRP) to identify the routing paths where less energy is consumed to enhances the network lifespan. The scheme is presented in six phases to explore flow and communication. We propose the two algorithms: i) energy-efficient clustering and routing algorithm and ii) distance and energy consumption calculation algorithm. The scheme consumes less energy and balances the load by clustering the smart devices. Our work is validated through extensive simulation using Matlab. Results elucidate the dominance of the proposed scheme is compared to counterparts in terms of energy consumption, the number of packets received at BS and the number of active and dead nodes. In the future, we shall consider edge computing to analyze the performance of robust clustering.     

Robust end-to-end loss differentiation scheme for transport control protocol over wired/wireless networks

The authors propose a robust end-to-end loss differentiation scheme to identify the packet losses because of congestion for transport control protocol (TCP) connections over wired/wireless networks. The authors use the measured round trip time (RTT) values to determine whether the cause of packet loss is because of the congestion over wired path or regular bit errors over wireless paths. The classification should be as accurate as possible to achieve high throughput and maximum fairness for the TCP connections sharing the wired/wireless paths. The accuracies of previous schemes in the literature depends on varying network parameters such as RTT, buffer size, amount of cross traffic, wireless loss rate and congestion loss rate. The proposed scheme is robust in that the accuracy remains rather stable under varying network parameters. The basic idea behind the scheme is to set the threshold for the classification to be a function of the minimum RTT and the current sample RTT, so that it may automatically adapt itself to the current congestion level. When the congestion level of the path is estimated to be low, the threshold for a packet loss to be classified as a congestion loss is increased. This avoids unnecessary halving of the congestion window on packet loss because of the regular bit errors over the wireless path and hence improves the TCP throughput. When the congestion level of the path is estimated to be high, the threshold for a packet loss to be classified as the congestion loss not to miss any congestion loss is decreased and hence improves the TCP fairness. In ns 2 simulations, the proposed scheme correctly classifies the congestion losses under varying network parameters whereas the previous schemes show some dependency on subsets of parameters.     

基于网络传输特性的链路重要性评价方法

提出了一种基于网络传输特性的链路重要性评价方法,根据链路在网络所有节点相互通信的最短路径中的使用频度来评价链路重要性,最重要链路的使用频度最高.该方法不需要像目前的链路重要性评价方法那样进行链路收缩和删除,直接反映了链路对整个网络通信的贡献大小,可以判断通信网中任意两条链路的相对重要性.算法分析和实验仿真表明,文章算法克服了目前的评价方法存在的问题,给出了更直观合理的通信网链路重要性评价准则.     

基于动态代理选择的移动网络组播

针对移动网络组播面临的接入点间切换造成组播树频繁重构的问题,提出了一种新的移动网络组播方法DMA(Dynamic Multicast Agent)。DMA在远程加入的基础上,使用动态选择组播代理和局部隧道的方法,为移动网络内的节点提供组播服务。分析与仿真结果表明,DMA不但减少了因移动网络附着点改变而造成的组播树重构次数,在一定程度上屏蔽了移动网络的移动性对组播树造成的影响,而且使得组播数据总是能够以“接近最优”的路径进行转发。     

Reliable cross-layer multicast with local backtracking for improving transmission control protocol performance in ad hoc networks

The conventional layered protocols in ad hoc networks tend to suffer from the inability to distinguish between losses due to route failures and congestion because of the inflexible structure. Recently, in efforts to overcome the challenges of dynamic environment, there have been increased interests in protocols that rely on interactions between different layers. The authors propose a cross-layer multicasting scheme based on the concept of local backtracking groups and adequate buffer equipped within nodes to avoid undesired retransmission from the source and further to improve the efficiency of source-to-receivers delivery with the aid of buffer. While encountering route failure, a node can quickly restore its routing paths to multicast subscribers by exploiting the precise notification from the MAC layer and the parent group then opportunely provides it with an unacknowledged packets conserved in the buffer. It is obviously benefic that retransmission packets are issued from the parent group rather than from the source. The authors present both analytic models and simulation results that substantiate the efficiency and robust of our approach based on realistic mobility scenarios.     

Edge detection using Chebyshev's orthogonal polynomial and brain extraction from magnetic resonance images of human head

In this article, we propose a new edge detecting method based on the transform coefficients obtained by a point spread function constructed out of Chebyshev's orthogonal polynomials. This edge detector finds edges similar to that of Prewitt and Roberts but is robust against additive and multiplicative noises. We also propose a new scheme to extract brain portion from the magnetic resonance images (MRI) of human head scan by making use of the of the new edge detector. The proposed scheme involves edge detection, morphological operations, and largest connected component analysis. Experiments conducted by applying the proposed scheme on 19 volumes of MRI collected from Internet Brain Segmentation Repository (IBSR) show that the proposed brain extraction scheme performed better than the popular Brain Extraction Tool (BET). The performance of the proposed scheme is measured by computing the Dice coefficient (D) and Jaccard similarity index (J). The proposed method produced a value of 0.9068 for D and 0.8321 for J.     

An Efficient Algorithm for Global Path Optimization in MPLS Networks

This paper proposes an algorithm to solve the optimization of label switched paths (LSPs) in multiprotocol label switching (MPLS) networks. The underlying optimization problem in this task is the well-known unsplittable multicommodity flow problem equipped with practically relevant objective functions and specialized with hard technical requirements.The proposed heuristic algorithm is based on network flow theory. It incorporates iterative shortest path search and performs adaptive edge weight adjustments in order to successfully satisfy all the required traffic demands and to maximize user-defined objectives. The robust algorithm facilitates the incorporation of several strategic and optimization objectives and the fulfillment of certain hard technical requirements of the target problem domain as well. Novel features of the approach include a new adaptive path allocation/deallocation strategy based on the identification of bottleneck links, demand ordering and preprocessing phases, and a systematic path allocation control method.The efficiency of the method is empirically shown on randomly generated networks with practical sizes and topologies, and on a real-world IP (Internet Protocol) backbone network. The algorithm is able to successfully solve difficult problem instances comprising very large instances with 1000 nodes, 3500 edges and 999000 traffic demands. The computational tests demonstrate that the proposed approach can be efficiently applied to solve problem instances that embed MPLS specific hard technical requirements. Furthermore, it is shown that our algorithm offers significantly better performance than the straightforward adaptations of existing methods that were developed for related network optimization problems. Namely, our algorithm produces acceptable results quicker, it can solve problems that were not previously solvable, and it yields better results than the alternative methods. The extensive empirical tests demonstrate the combinatorial properties of the target problem and the performance aspects of the algorithm and its components as well.     

Cross-layer distributed approach for optimal rate allocation for homogeneous wireless multicast

Multicast-based data communication is an efficient communication scheme especially in multihop ad hoc networks where the MAC layer is based on one-hop broadcast from one source to multiple receivers. The problem of resource allocation for a set of homogeneous multicast sessions over multihop wireless network is addressed. An iterative algorithm is proposed that achieves the optimal rates for a set of multicast sessions such that the aggregate utility for all sessions is maximised. The authors demonstrate analytically and through simulations that the algorithm achieves optimal resource utilisation while guaranteeing fairness among multicast sessions. The algorithm in network environments with asynchronous distributed computations has been further analysed. Two implementations for the algorithm based on different network settings are presented and show that the algorithm not only converges to the optimal rates in all network settings but it also tracks network changing conditions, including mobility and dynamic channel capacity.     

Geometric approaches to enhancing edge quality in planar milling

Experimental studies show that the in-plane exit angle is a crucial factor affecting edge quality in milling operations. Serious edge defects start to form at tool exits with an exit angle larger than a threshold value determined by the depth of cut, feed rate and material ductility, regardless of other cutting parameters. By adjusting the tool path, the exit angle can be used as a handle for changing the defect formation on the machined edges. A computational framework that minimizes the primary edge defect in planar milling by appropriate selection of the orientation for parallel tool paths is presented. Algorithms are developed to predict defect locations on linear and circular edges while the tool is moving along a given tool path. Process-planning software implemented with these algorithms demonstrates the feasibility of enhancing edge quality with geometric approaches in an automatic manner. The paper provides an effective solution to the edge defect problem in circumstances such as micro-milling and precision manufacturing where edge finishing is difficult to perform.     

Reliability assessment for a stochastic manufacturing system with reworking actions

This article evaluates the system reliability of a manufacturing system with reworking actions, where the system reliability is an essential indicator to determine whether the manufacturing system is capable or not. Based on the path concept, we transformed the manufacturing system into a stochastic-flow network in which the capacity of each machine is stochastic (i.e., multistate) due to failure, partial failure, and maintenance. In such a manufacturing network, the input flow (raw materials/WIP; work-in-process) processed by each machine might be defective and thus the output flow (WIP/products) would be less than the input amount. To analyze the different sources processed by the manufacturing network, we decomposed the network into one general processing path and several reworking paths by a graphical technique. Subsequently, an algorithm for the manufacturing network was proposed to generate the lower boundary vector which allows sufficient products to satisfy the demand. In terms of such a vector, the system reliability can be derived easily.     

Color‐edge detection based on discrimination of noticeable color contrasts

Color‐edge detection is an important research task in the field of image processing. Efficient and accurate edge detection will lead to higher performance of subsequent image processing techniques, including image segmentation, object‐based image coding, and image retrieval. To improve the performance of color‐edge detection while considering that human eyes are ultimate receiver of color images, the perceptually insignificant edges should avoid being over‐detected. In this article, a color‐edge detection scheme based on the perceptual color contrast is proposed. The perceptual color contrast is defined as the visible color difference across an edge in the CIE‐Lab color space. A perceptual metric for measuring the visible color difference of a target color pixel is defined by utilizing the associated perceptually indistinguishable region. The perceptually indistinguishable region for each color pixel in the CIE‐Lab color space is estimated by the design of an experiment that considers the local property due to local changes in luminance. Simulation results show that the perceptual color contrast is effectively defined and the color edges in color images are detected while most of the perceptually insignificant edges are successfully suppressed through the proposed color‐edge detection scheme. © 2009 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 19, 332–339, 2009     

网络拓扑结构对IP组播效率影响的研究

研究了不同网络拓扑结构对IP组播效率的影响,给出了一种度量组播效率的方法,并进行了分析与仿真.结果表明:在随机选择组播树根节点的情况下,平均节点度越大的网络,组播效率越低;限制组播路由的通过性和适当选择组播根节点的位置能够有效提高组播效率;有源最短路径树在不同网络拓扑下的性能差异较大,并且不是一种能够适合于各种网络结构的高效组播树构建算法.     

Cutset enumeration of network systems with link and node failures

Network reliability analysis has received considerable attention and is thus widely studied to predict and prevent any network failure. However, most of such works presume perfectly reliable nodes. Although a few studies have considered both link and node failures, none of these methods has utilized the minimal paths or cuts, which are considered as fundamental approaches in the network reliability evaluation. An efficient method for deducing the minimal cutsets of a system subject to both link and node failures from the minimal cutsets of the system, which assumes perfect node reliability, is presented. The proposed method does not require re-enumeration of minimal cutsets for the additional consideration of the node failures. For a simple extension of such a method, the proposed approach can be embedded in any exact or approximate algorithm to account for link failures as well as node failures. As a result, the application of this method would be more realistic and valuable in practice for the reliability evaluation of networks with unreliable nodes.     

Dynamic resource sharing protection using label stacking and burst multiplexing in optical burst switched networks

A protection and restoration mechanism is essential to provide reliable traffic transmission in networks, but it is not easy to apply existing protection mechanisms to optical burst-switching (OBS) networks, because of the unique properties of OBS. The authors introduce a 1:1 link-based protection that minimises burst losses by deflecting bursts until a source ingress router arbitrates a working path to a backup path when a link failure occurs. The authors also propose a genuine dynamic resource sharing (DRS) link protection in order to achieve high efficiency in network resource allocation and reliable protection simultaneously in OBS networks. DRS employs burst-multiplexing and label-stacking techniques in backup channel selection and always reserves an optimal number of backup channels according to the changes in traffic load in a working link and the quality of service (QoS) requirements of bursts. Simulation results show that the DRS can provide the same protection reliability with just half of the backup channels needed in a normal 1:1 protection in a light-load case, while guaranteeing the QoS requirements of class bursts. The authors show that this property also makes backup link sharing among a number of working links possible.     

Single Failure Routing Protection Algorithm in the Hybrid SDN Network

Loop free alternate (LFA) is a routing protection scheme that is currently deployed in commercial routers. However, LFA cannot handle all single network component failure scenarios in traditional networks. As Internet service providers have begun to deploy software defined network (SDN) technology, the Internet will be in a hybrid SDN network where traditional and SDN devices coexist for a long time. Therefore, this study aims to deploy the LFA scheme in hybrid SDN network architecture to handle all possible single network component failure scenarios. First, the deployment of LFA scheme in a hybrid SDN network is described as a 0-1 integer linear programming (ILP) problem. Then, two greedy algorithms, namely, greedy algorithm for LFA based on hybrid SDN (GALFAHSDN) and improved greedy algorithm for LFA based on hybrid SDN (IGALFAHSDN), are proposed to solve the proposed problem. Finally, both algorithms are tested in the simulation environment and the real platform. Experiment results show that GALFAHSDN and IGALFAHSDN can cope with all single network component failure scenarios when only a small number of nodes are upgraded to SDN nodes. The path stretch of the two algorithms is less than 1.36.