Reducing Switch State Size in Flow-Based Networks

An article of manufacture comprising a computer readable storage medium having computer readable instructions tangibly embodied thereon which, when implemented, cause a computer to carry out a plurality of method steps comprising:

• 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 first hop rule adds one or more tags onto a given packet that matches a description of the given flow, and wherein the one or more tags correspond to one or more output ports to be used for forwarding the given packet on each of one or more subsequent switches in the network on the path of the given flow such that all packets to be forwarded to the same output port on each switch have an to identical outermost tag for that switch;
• installing and analyzing one or more forwarding rules at each of the subsequent switches in the network on the path of the given flow to confirm a match with the given packet at each of the subsequent switches 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.

A system comprising:

• at least one distinct software module, each distinct software module being embodied on a tangible computer-readable medium;
• a memory;
• and
• at least one processor coupled to the memory and operative for:
• 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 first hop rule adds one or more tags onto a given packet that matches a description of the given flow, and wherein the one or more tags correspond to one or more output ports to be used for forwarding the given packet on each of one or more subsequent switches in the network on the path of the given flow such that all packets to be forwarded to the same output port on each switch have an identical outermost tag for that switch;
• installing and analyzing one or more forwarding rules at each of the subsequent switches in the network on the path of the given flow to confirm a match with the given packet at each of the subsequent switches 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.

A method comprising:

• proactively 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 first hop rule adds one or more tags onto a given packet that matches a description of the given flow, and wherein the one or more tags correspond to one or more output ports to be used for forwarding the given packet on each of one or more subsequent switches in the network on the path of the given flow such that all packets to be forwarded to the same output port on each switch have an identical outermost tag for that switch;
• proactively installing one or more forwarding rules at each of the subsequent switches in the network on the path of the given flow, wherein the one or more forwarding rules determine a match of the given packet at each of the subsequent switches based on the outermost tag on the given packet;
• analyzing one or more forwarding rules at each of the subsequent switches in the network on the path of the given flow to confirm a match with the given packet at each of the subsequent switches 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;
• wherein at least one of the steps is carried out by a computer device.