Candidate Path Selection Method for TCP Performance Improvement in Fixed Robust Routing

Yukinobu Fukushima,Takashi Matsumura,Kazutaka Urushibara,Tokumi Yokohira 대한전자공학회 2016 IEIE Transactions on Smart Processing & Computing Vol.5 No.6

Fixed robust routing is attracting attention as routing that achieves high robustness against changes in traffic patterns without conducting traffic measurement and performing dynamic route changes. Fixed robust routing minimizes the worst-case maximum link load by distributing traffic of every source-destination (s-d) router pair onto multiple candidate paths (multipath routing). Multipath routing, however, can result in performance degradation of Transmission Control Protocol (TCP) because of frequent out-of-order packet arrivals. In this paper, we first investigate the influence of multipath routing on TCP performance under fixed robust routing with a simulation using ns-2. The simulation results clarify that TCP throughput greatly degrades with multipath routing. We next propose a candidate path selection method to improve TCP throughput while suppressing the worst-case maximum link load to less than the allowed level under fixed robust routing. The method selects a single candidate path for each of a predetermined ratio of s-d router pairs in order to avoid TCP performance degradation, and it selects multiple candidate paths for each of the other router pairs in order to suppress the worst-case maximum link load. Numerical examples show that, provided the worst-case maximum link load is less than 1.0, our proposed method achieves about six times the TCP throughput as the original fixed robust routing.

Muskingum 홍수 추적방법의 매개변수 최적화에 관한 연구

조현경(Hyeon-Kyeong Cho) 한국산업융합학회 2008 한국산업융합학회 논문집 Vol.11 No.1

This study presents techniques for the estimation of parameters in flood routing method of natural channel.. The Muskingum routing method is the most widely used method of hydrologic stream channel routing. In this paper, Genetic Algorithm and Fletcher-Powell method is applied to determine parameters(K and x) of the Muskingum routing method. The results of the approach shows that Genetic Algorithm method can be one of methods to determine parameters of the Muskingum routing method. Based on the analysis for estimated parameters and the comparison with the results from observed data, the applicability of Genetic Algorithm is verified.

Muskingum-Cunge방법을 이용한 상태공간모형의 홍수추적 적용성 평가

박영기 ( Young-ki Park ),정재성 ( Jae-seong Jeong ),이동주 ( Dong-joo Lee ) 한국환경기술학회 2012 한국환경기술학회지 Vol.13 No.1

본 연구의 목적은 인공하천의 하도 추적에서 Georgakakos A.P.가 개발한 상태공간 모형을 자연하도 추적에 적용하는 것이다. 상태공간 모형은 실시간으로 유량측정에 이용할 수 있는데, 관측값과 모델링값의 오차를 설명할 수 있다. 또한, 칼만필터의 추정치를 통하여 실시간으로 계산할 수 있다. 본 모형의 대상으로 대청댐 유역을 적용하였다. 하천 추적모형의 매개변수는 자연하천의 수문학적 특성인자(수로길이, 수로폭, 수로경사 등)에 의하여 결정되어졌다. 평가된 결과로서 수문곡선의 첨두시간이 관측수문곡선과 동일하였고, 첨두 유출량과 총 유출량은 각각 실제 관측치의 90~92%, 92~93%를 보였다. 상대평균제곱근오차, 표준화된 첨두유량오차는 0.79와 0.25로 나타났다. 이는 모델의 오차와 효율성 및 적용성을 나타내어 본 모델이 홍수추적모델에 유용하게 이용될 수 있을 것으로 판단된다. 또한 본 연구를 통하여 Muskingum-Cunge의 방법은 실시간으로 자연하천 하도의 홍수추적 모형에 적용할 수 있다는 것을 보였다. The purpose of this paper is to investigate the utility of state space model for natural river routing which is developed by Georgakakos, A.P. for the lined river routing. The state space model utilizes real-time discharge measurements, accounts for modeling and observation errors, and allows real-time updating through Kalman filter estimator. The model is tested in Daecheong Dam basin. The parameters of the channel routing model are determined by hydrologic characteristics(channel length, channel width, channel slope, etc)of Natural channel. The results show that peak time of hydrograph is same as the observed hydrograph, and the estimated peak discharge of runoff and total volume of runoff are 90~92%, 92~93% of real measurements, respectively. Errors and efficiency of the state space model shows that cofficients of RRMSE, NPE were 0.79 and 0.25. Applicability of the state space model appeared to be good. The this model might be useful for modeling flood routing. Through this study it is confirmed that Muskingum -cunge method can utilize real time flood routing for natural channels.

An Application of Pareto Solution with Adapted ACO for Searching Optimal Route of a Mobile Robot in Rough Terrain Environment

Anuntapat Anuntachai,Arit Thammano,Olarn Wongwirat 제어로봇시스템학회 2016 제어로봇시스템학회 국제학술대회 논문집 Vol.2016 No.10

A challenge in searching an optimal route of a mobile robot involves finding the route that has the shortest distance and consumes the least energy. To solve this problem, an ant colony optimization (ACO) algorithm can be used, but only on a flat terrain, since the energy depends directly on the distance. In a rough terrain, the least energy route might not be the shortest distance. Also, the shortest distance route might not be the least energy. This is due to a factor of slope in the route. Although our adapted ACO can be used for searching energy-efficient routes in the rough terrain, it is difficult to achieve the shortest distance simultaneously. This paper proposes a novel method to find an optimal route of a mobile robot in rough terrain environment by using a Pareto solution with adapted ACO. In the proposed method, the adapted ACO is used to search two sets of route, i.e., one contains the least energy and another one contains the shortest distance. Then, the Pareto solution is deployed to find the optimal route in terms of energy and distance by adopting a distance vector for selection. The experiment was performed by simulation to verify the proposed searching method. The experimental results show that the proposed searching method can prescribe the optimal value for choosing the route provided by adapted ACO.

Heuristics for Rich Vehicle Routing Problem : A Case of a Korean Mixed Feed Company

손동훈(Dong Hoon Son),․,김화중(Hwa-Joong Kim) 한국산업경영시스템학회 2019 한국산업경영시스템학회지 Vol.42 No.1

The vehicle routing problem is one of the vibrant research problems for half a century. Many studies have extensively studied the vehicle routing problem in order to deal with practical decision-making issues in logistics. However, developments of new logistics strategies have inevitably required investigations on solution methods for solving the problem because of computational complexity and inherent constraints in the problem. For this reason, this paper suggests a simulated annealing (SA) algorithm for a variant of vehicle routing problem introduced by a previous study. The vehicle routing problem is a multi-depot and multi-trip vehicle routing problem with multiple heterogeneous vehicles restricted by the maximum permitted weight and the number of compartments. The SA algorithm generates an initial solution through a greedy-type algorithm and improves it using an enhanced SA procedure with three local search methods. A series of computational experiments are performed to evaluate the performance of the heuristic and several managerial findings are further discussed through scenario analyses. Experiment results show that he proposed SA algorithm can obtain good solutions within a reasonable computation time and scenario analyses show that a transportation system visiting non-dedicated factories shows better performance in truck management in terms of the numbers of vehicles used and trips for serving customer orders than another system visiting only dedicated factories.

A provably tight delay-driven concurrently congestion mitigating global routing algorithm

Samanta, R.,Erzin, A.I.,Raha, S.,Shamardin, Y.V.,Takhonov, I.I.,Zalyubovskiy, V.V. Elsevier [etc.] 2015 Applied mathematics and computation Vol.255 No.-

Routing is a very important step in VLSI physical design. A set of nets are routed under delay and resource constraints in multi-net global routing. In this paper a delay-driven congestion-aware global routing algorithm is developed, which is a heuristic based method to solve a multi-objective NP-hard optimization problem. The proposed delay-driven Steiner tree construction method is of O(n<SUP>2</SUP>logn) complexity, where n is the number of terminal points and it provides n-approximation solution of the critical time minimization problem for a certain class of grid graphs. The existing timing-driven method (Hu and Sapatnekar, 2002) has a complexity O(n<SUP>4</SUP>) and is implemented on nets with small number of sinks. Next we propose a FPTAS Gradient algorithm for minimizing the total overflow. This is a concurrent approach considering all the nets simultaneously contrary to the existing approaches of sequential rip-up and reroute. The algorithms are implemented on ISPD98 derived benchmarks and the drastic reduction of overflow is observed.

Design of a set of One-to-Many Node-Disjoint and Nearly Shortest Paths on Recursive Circulant Networks

정일용 한국멀티미디어학회 2013 멀티미디어학회논문지 Vol.16 No.7

The recursive circulant network G(N,d) can be widely used in the design and implementation of parallel processing architectures. It consists of N identical nodes, each node is connected through bidirectional, point-to-point communication channels to different neighbors by jumping di, where 0≤i≤⌈logdN⌉−1. In this paper, we investigate the routing of a message on G(2m,4), a special kind of RCN, that is key to the performance of this network. On G(2m,4) we would like to transmit k packets from a source node to k destination nodes simultaneously along paths on this network, the ith packet will be transmitted along the ith path, where 1≤k≤m−1, 0≤i<m−1. In order for all packets to arrive at a destination node quickly and securely, we present an O(m4) routing algorithm on G(2m,4) for generating a set of one-to-many node-disjoint and nearly shortest paths, where each path is either shortest or nearly shortest and the total length of these paths is nearly minimum since the path is mainly determined by employing the Hungarian method.

A Nearly Optimal One-to-Many Routing Algorithm on k-ary n-cube Networks

Choi, Dongmin,Chung, Ilyong THE KOREAN INSTITUTE OF SMART MEDIA 2018 스마트미디어저널 Vol.7 No.2

The k-ary n-cube $Q^k_n$ is widely used in the design and implementation of parallel and distributed processing architectures. It consists of $k^n$ identical nodes, each node having degree 2n is connected through bidirectional, point-to-point communication channels to different neighbors. On $Q^k_n$ we would like to transmit packets from a source node to 2n destination nodes simultaneously along paths on this network, the $i^{th}$ packet will be transmitted along the $i^{th}$ path, where $0{\leq}i{\leq}2n-1$. In order for all packets to arrive at a destination node quickly and securely, we present an $O(n^3)$ routing algorithm on $Q^k_n$ for generating a set of one-to-many node-disjoint and nearly shortest paths, where each path is either shortest or nearly shortest and the total length of these paths is nearly minimum since the path is mainly determined by employing the Hungarian method.

OSPF Protocol 표준 및 구현의 대수 정형적 명세 및 정형적 검증

박재현 한국통신학회 2004 韓國通信學會論文誌 Vol.29 No.3B

The OSPF protocol is the most widely used Interior Gateway Routing Protocol. Therefore, for the reliability of behavior of gigabit swiching routers, it is essential to guarantee the interoperability and the safety of the OSPF protocol. In this paper, we analyze the standard document of the OSPF protocol, so that we provide a formal specification that specifies the protocol behaviors by detailed design level using the algebraic formal method. By referring available source codes of the OSPF protocol, we supplement the formal specification to express more detailed behaviors that is not specified definitely in the standard. We also formally verify the interoperability and the safety of the protocol state machine of the specification. By showing that the formal specification specify all of the states and the transition events that appear in the standard document of the OSPF protocol, we prove that the state machine has the completeness, and prove it has the interoperability. To prove that the specification of the protocol has the safety, we formally verify the reachability, the liveness, the livelock-free property, and the deadlock-free property. As a result, we prove the protocol has the consistency. The specification and the validation are also effective to the OSPF Version 3 that inherit the protocol mechanism of the OSPF Version 2. OSPF 프로토콜은 가장 보편적으로 사용되고 있는 Interior Gateway Routing Protocol 이다. 그러므로, 초고속 라우터의 동작의 신뢰성 확보를 위해, OSPF 프로토콜의 상호운용성과 안전성의 보장은 중요하다. 본 논문에서는 OSPF 라우팅 프로토콜의 표준 문서를 분석하여, 프로토콜 동작들을 대수 정형 방법을 사용하여 상세 설계 수준으로 명세하고, OSPF 프로토콜의 가용한 원천코드를 참조하여, 표준에 명확하게 명세되지 않은 좀더 상세한 동작까지 표현하도록 이 명세를 보완하였다. 그리고 명세된 프로토콜 상태 기계의 상호운용성과 안전성을 정형적으로 증명하였다. 우리는 먼저 제시한 정형적 명세가 OSPF 프로토콜의 표준 문서에 나타난 모든 상태들과 모든 천이 이벤트들을 표현하고 있어, 명세된 프로토콜 상태기계가 완전성을 가지고 있다는 사실을 보이고, 또한 상호운용성을 가짐을 증명하였다. 그리고 프로토콜의 동작의 안전성을 증명하기 위해, 생존성, 그리고 라이브락 부재를 정형적으로 증명하고, 교착상태 부재 역시 정형적으로 증명하였다. 결과적으로 OSPF 프로토콜이 일관성을 가진다는 사실을 보인다. 본 명세와 검증은 기존외 OSPF Version 2의 프로토콜 메커니즘을 그대로 계승한 OSPF Version 3에서도 유효하다.

A Nearly Optimal One-to-Many Routing Algorithm on k-ary n-cube Networks

Dongmin Choi,Ilyong Chung 한국스마트미디어학회 2018 스마트미디어저널 Vol.7 No.2

The k-ary n-cube is widely used in the design and implementation of parallel and distributed processing architectures. It consists of identical nodes, each node having degree is connected through bidirectional, point-to-point communication channels to different neighbors. On we would like to transmit packets from a source node to destination nodes simultaneously along paths on this network, the packet will be transmitted along the path, where . In order for all packets to arrive at a destination node quickly and securely, we present an O( ) routing algorithm on for generating a set of one-to-many node-disjoint and nearly shortest paths, where each path is either shortest or nearly shortest and the total length of these paths is nearly minimum since the path is mainly determined by employing the Hungarian method.