Techniques, systems, and articles of manufacture for reducing switch state size in flow-based networks. A method includes installing a first hop rule on a first hop switch in a network for a given flow that originates from the first hop switch, wherein the rule adds tags onto a given packet that matches a description of the given flow, wherein the tags correspond to output ports used for forwarding the given packet on each subsequent switch in the network on the path of the given flow; installing and analyzing forwarding rules at each subsequent switch in the network on the path of the given flow to confirm a match with the given packet at each subsequent switch based only on the outermost tag on the given packet; and removing the outermost tag from the given packet and forwarding said given packet to the output port corresponding to said removed outermost tag.