1-3hit |
Ken TANAKA Kenji MIKAWA Manabu HIKIN
Network devices, such as routers or L3 switches, have a feature called packet-filtering for network security. They determine whether or not to pass arriving packets by applying filtering rules to them. If the number of comparisons of packets with rules increases, the time required for a determination will increase, which will result in greater communication delay. Various algorithms for optimizing filtering tables to minimize the load of packet filtering, which directly impacts the communication delay, have been proposed. In this paper, first we introduce an adaptive packet filter based on an algorithm that reconstructs the filtering table according to the frequency distribution of arrival packets. Next, we propose a new reconstruction algorithm based on grouping of dependent rules. Grouping dependent rules makes it possible to sort the rules in the table by the frequency of matching. Finally, we show the effectiveness of our algorithm by comparing it against previously reported algorithms.
In differentiated services, packet classification is used to categorize incoming packets into multiple forwarding classes based on pre-defined filters and make information accessible for quality of service. Although numerous algorithms have presented novel data structures to improve the search performance of packet classification, the performance of these algorithms are usually limited by the characteristics of filter databases. In this paper, we use a different approach of filter preprocessing to enhance the search performance of packet classification. Before generating the searchable data structures, we cluster filters in a bottom-up manner. The procedure of the filter clustering merges filters with high degrees of similarity. The experimental results show that the technique of filter clustering could significantly improve the search performance of Pruned Tuple Space Search, a notable hash-based algorithm. As compared to the prominent existing algorithms, our enhanced Pruned Tuple Space Search also has superior performance in terms of speed and space.
In this paper, a new multicast routing method for layered streams is proposed. This method is an extension of the weighted greedy algorithm (WGA) and uses two kinds of weight values to refine the link distance. It can cope with dynamic change in the group members without multicast tree re-construction. The method is compatible with the RSVP and can be utilized in existing shared tree type routing protocols such as CBT and PIM sparse mode. The network resources can be utilized efficiently; furthermore, the loss rate of member's requests to receive more layers can be reduced by this routing method when a sufficient number of nodes have the packet filtering function and a sufficient number of hops is permitted.