Reducing switch state size in flow-based networks

Patent metadata

Field	Value
Publication number	US-9253035-B2
Application number	US-201313772800-A
Country	US
Kind code	B2
Filing date	Feb 21, 2013
Priority date	Feb 21, 2013
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

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.

First claim

What is claimed is:

1. A method 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, wherein the first hop switch is a virtual software switch that resides inside a hypervisor, 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; wherein at least one of the steps is carried out by a computer device.

2. The method of claim 1 , wherein said installing one or more forwarding rules comprises installing one or more forwarding rules on all switches except for the first hop switch, and wherein each of said one or more forwarding rules has a match which includes all fields as wildcards except for a known header field in the packet which is matched against the value of the outermost tag.

3. The method of claim 1 , wherein said forwarding comprises forwarding the given packet to the output port identified by the value of the removed outermost tag.

4. The method of claim 1 , wherein the first hop rule uniquely identifies a flow in the network.

5. The method of claim 1 , comprising: maintaining one or more counters at the first hop switch to be polled by a network controller, thereby enabling monitoring of each new flow that originates from the first hop switch.

6. The method of claim 1 , comprising: rerouting the given flow by installing a new first hop rule that adds a new group of one or more tags on each matching packet.

7. The method of claim 1 , wherein the one or more forwarding rules comprise a rule for confirming that all packets on a given switch that are to be forwarded to the same output port are tagged with an identical outermost tag for the given switch.

8. The method of claim 1 , comprising compressing the one or more forwarding rules for all flows at a given switch having the same output port into one wildcard flow rule, with the exception of flows at the first hop switch.

9. An article of manufacture comprising a non-transitory 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, wherein the first hop switch is a virtual software switch that resides inside a hypervisor, 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.

10. The article of manufacture of claim 9 , wherein said installing one or more forwarding rules comprises installing one or more forwarding rules on all switches except for the first hop switch, and wherein each of said one or more forwarding rules has a match which includes all fields as wildcards except for a known header field in the packet which is matched against the value of the outermost tag.

11. The article of manufacture of claim 9 , wherein said forwarding comprises forwarding the given packet to the output port identified by the value of the removed outermost tag.

12. The article of manufacture of claim 9 , wherein the first hop rule uniquely identifies a flow in the network.

13. The article of manufacture of claim 9 , wherein the method steps comprise: maintaining one or more counters at the first hop switch to be polled by a network controller, thereby enabling monitoring of each new flow that originates from the first hop switch.

14. The article of manufacture of claim 9 , wherein the method steps comprise: rerouting the given flow by installing a new first hop rule that adds a new group of one or more tags on each matching packet.

15. The article of manufacture of claim 9 , wherein the one or more forwarding rules comprise confirming that all packets on a given switch that are to be forwarded to the same output port are tagged with an identical outermost tag for the given switch.

16. The article of manufacture of claim 9 , wherein the method steps comprise: compressing the one or more forwarding rules for all flows at a given switch having the same output port into one wildcard flow rule, with the exception of flows at the first hop switch.

17. A system comprising: at least one distinct software module, each distinct software module being embodied on a non-transitory 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, wherein the first hop switch is a virtual software switch that resides inside a hypervisor, 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.

18. 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, wherein the first hop switch is a virtual software switch that resides inside a hypervisor, 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

Assignees

• IBM

Inventors

• Mann Vijay
• Iyer Aakash S

Classifications

• H04L45/64

  using an overlay routing layer · CPC title

• H04L45/38

  Flow based routing · CPC title

• H04L43/026

  using flow identification · CPC title

• H04L41/0806 Primary

  for initial configuration or provisioning, e.g. plug-and-play · CPC title

• H04L41/342

  between virtual entities, e.g. orchestrators, SDN or NFV entities · CPC title