Chinese Journal of Computers   Full Text
Title	A Study of Algorithm for Testing Route Oscillation Based on Algebraic Method
Authors	ZHAO Hui-Qun SUN Jing
Address	(School of Information and Engineering, North China University of Technology, Beijing 100041)
Year	2007
Issue	No.10(1763—1769)
Abstract &   Background	Abstract Based on the RNA(Route network algebra) a new method for testing route oscillation is proposed. By modeling a route system in RNA expression it translates route analysis work into algebraic deduction. By introducing concept of linear relation of network elements it proves that route oscillation if and only if network elements have linear relativity. Following the ideal an O(H×L+N2) time algorithm for testing route oscillation is proposed. To support the new ideal an experiment is design with proposed algorithm, which work on real route table of AS, its feasibility had been further demonstrated. keywords oscillation of routing; routing network algebra; protocol test; BGP background The research is supported by the National Natural Science Foundation of China under grant No. 60473032, Advanced the National High Technology Research and Development Program (863 Program) under grant No.2006AA09Z139, and National Science Foundation of Beijing under grant No. 4062012. All above projects study some problems of network routing protocol consistence, which appear with network quickly development. The main research work focuses on probing new methodology for testing protocol policy consistency. This paper offers a new way to testing route oscillation. By modeling a route system in RNA expression it translates route analysis work into algebraic deduction, and an O(H×L+N2) time algorithm for testing route oscillation is proposed.