A hierarchical approach to establish an efficient upgrade plan

Undesirable information such as the computer virus, route flap, always origins in one area of the network and spreads to others, thus causes far-reaching instability of the network. Upgrading network nodes with new software and/or hardware will help suppress such instability. This paper presents a hierarchical solution to establish an efficient upgrade plan, determining which nodes should be upgraded firstly. The easy-spread of undesirable information is analyzed. Different types of nodes are distinguished according to their abilities to deal with undesirable information. Simulations are performed to acquire a quantitative evaluation of the spread and identify related factors. Based on the theories of the graph, algorithms are given to acquire an efficient upgrading plan. These algorithms work in a hierarchical way taking advantage of the hierarchical structure of the Internet. With complexity analysis, these algorithms are shown to be feasible.