A system and method for supporting network isolation in a multi-tenant cluster environment. An exemplary method can support one or more tenants, and can associate each of the one or more tenants with a partition of a plurality of partitions, and can also associate each of the plurality of partitions with one or more nodes of a plurality of nodes, each of the plurality of nodes being associated with a leaf switch of a plurality of switches. The method can mark each of the plurality of partitions with a policy parameter. The method can assign each node of the plurality of nodes a partitioning order based on the marked on the partition associated with each node. Finally, the method can, based at least upon the marking of the partition of the plurality of partitions, generate one or more linear forwarding tables for use in the multi-tenant cluster environment.