A method for a computing device serving as a host computer (1100, 311) for operating virtual machines, VMs (1111-1114, VM A, VM B, VM C), executed by a set of processing units of the host computer (1100, 311), the method comprising: at a hypervisor of the host computer (1100, 311): receiving a firewall rule from a network manager that provides firewall rules to a plurality of host computers (311, 312, 319); inserting a node that corresponds to the received firewall rule into a search tree structure constructed by the hypervisor; using a filter for a particular VM (1111, VM A) to identify a set of firewall rules (601, 602, 605, 607) that are relevant to the particular VM (1111, VM A) from the search tree structure based on the IP address of the particular VM,, wherein each respective VM of a set of VMs (VM A, VM B, VM C) operating on the host computer (1100, 311) has a respective filter used to identify a respective set of firewall rules relevant to the respective VM, wherein the filters are included in the hypervisor; at the filter for the particular VM, caching the identified relevant rules (601, 602, 605, 607) and only using the search tree structure to update the cached rules when the hypervisor receives a firewall configuration message from the network manager; and at the hypervisor, performing firewall operations for the particular VM (1111, VM A) by applying the identified relevant rules (601, 602, 605, 607). at a hypervisor of the host computer (1100, 311): receiving a firewall rule from a network manager that provides firewall rules to a plurality of host computers (311, 312, 319); inserting a node that corresponds to the received firewall rule into a search tree structure constructed by the hypervisor; using a filter for a particular VM (1111, VM A) to identify a set of firewall rules (601, 602, 605, 607) that are relevant to the particular VM (1111, VM A) from the search tree structure based on the IP address of the particular VM,, wherein each respective VM of a set of VMs (VM A, VM B, VM C) operating on the host computer (1100, 311) has a respective filter used to identify a respective set of firewall rules relevant to the respective VM, wherein the filters are included in the hypervisor; receiving a firewall rule from a network manager that provides firewall rules to a plurality of host computers (311, 312, 319); inserting a node that corresponds to the received firewall rule into a search tree structure constructed by the hypervisor; using a filter for a particular VM (1111, VM A) to identify a set of firewall rules (601, 602, 605, 607) that are relevant to the particular VM (1111, VM A) from the search tree structure based on the IP address of the particular VM,, wherein each respective VM of a set of VMs (VM A, VM B, VM C) operating on the host computer (1100, 311) has a respective filter used to identify a respective set of firewall rules relevant to the respective VM, wherein the filters are included in the hypervisor; at the filter for the particular VM, caching the identified relevant rules (601, 602, 605, 607) and only using the search tree structure to update the cached rules when the hypervisor receives a firewall configuration message from the network manager; and at the hypervisor, performing firewall operations for the particular VM (1111, VM A) by applying the identified relevant rules (601, 602, 605, 607).