Some embodiments provide a non-transitory machine readable medium of a first middlebox element of several middlebox elements to implement a middlebox instance in a distributed manner in several hosts. The non-transitory machine readable medium stores a set of instructions for receiving (1) configuration data for configuring the middlebox instance to implement a middlebox in a logical network and (2) a particular identifier associated with the middlebox in the logical network. The non-transitory machine readable medium stores a set of instructions for generating (1) a set of rules to process packets for the middlebox in the logical network and (2) an internal identifier associated with the set of rules. The non-transitory machine readable medium stores a set of instructions for associating the particular identifier with the internal identifier for later processing of packets having the particular identifier.