The value pointer leads to the TCP node, where the destination port value in the packet is hashed to lead to the final matching filter. The pointer of this value leads to the IP node, where the IP protocol type field is hashed to find a matching value corresponding to TCP. Search starts at the root, and the Ethernet type field is hashed to find a matching value corresponding to IP. When a TCP packet arrives, demultiplexing proceeds as follows. In the TCP node, there are three values pointing to the three possible destination port values of 2 and 5 (recall that the 17 has not been inserted yet). In the IP protocol field node, one of the values corresponding to TCP (which has value 6) will point to the TCP node. Finally, the Ethernet type field corresponding to IP points to a node corresponding to the IP protocol field. Thus the ARP entry points to nodes that further specify what type of ARP packets must be received the OSI entry does likewise. Each node entry has a value and a pointer. The root node corresponds to the Ethernet type field the hash table contains values for each possible Ethernet type field value used in the filters. Besides the TCP filters, there are one or more filters that specify ARP packets and one or more filters that specify packets that use the OSI protocol. Rather than search these values linearly, the header field values are placed in a hash table.įigure 8.6 shows an example with at least four filters, two of which specify TCP packets with destination port numbers 2 and 5 for now ignore the dashed line to TCP port 17, which will be used as an example of filter insertion in a moment. In the composite structure all the different field values specified in different filters for a given header field are placed in a single node. The Pathfinder data structure integrates several versions of the BPF control flow graph integrated into a composite structure. Specifically, this can be done using hashing ( P15, using efficient data structures) to perform exact search this can replace 500 comparisons with just a few comparisons.įigure 8.6. This suggests that integrating all the individual filters into a single composite filter can considerably reduce unnecessary comparisons when the number of individual filters is large. However, this is exactly analogous to a linear search for exact matching. Next, comparing the TCP port numbers in the packet to each of the 500 port pairs specified in each of the 500 filters is not obvious waste. Doing each filter sequentially would require comparing the Ethernet type of the packet 500 times against the (same) IP Ethernet type field and comparing the IP protocol field 500 times against the (same) TCP protocol value. To motivate the Pathfinder solution, imagine there are 500 filters, each of which is exactly the same (Ethernet type field is IP, IP protocol type is TCP) except that each specifies a different TCP port pair. This allows scaling to a large number of users. The need to deal with this change in environment (user-level networking) led to another successful mutation, called Pathfinder, Pathfinder goes beyond BPF by providing composability. In particular, each TCP connection may provide a filter, and the number of concurrent TCP connections in a busy server can be large. However, this is not true if early demultiplexing is used to discriminate between a large number of packet streams or paths. For example, a typical Tcpdump application may provide only a few filters to BPF. Fortunately, this is not a problem for typical BPF usage. Thus the processing time grows with the number of filters. However, every packet must still be compared with each filter in turn. George Varghese, in Network Algorithmics, 2005 8.5 PATHFINDER: FACTORING OUT COMMON CHECKSīPF is a more refined adaptation than CSPF becauses it increases speed for a single filter.
0 kommentar(er)
