A common theme used by the comedy crew Monty Python was to emphasize and exaggerate ridiculousnesses that their target had imposed upon themselves. Few things could be considered as humorous as making a redundancy protocol... redundant; e.g. being forced to replace it by Cisco lawyers and IETF policy.
We've been working a few years now on our packet filtering software pf(4) and it became time to add failover. We want to be able to set up pf firewalls side by side, and exchange the stateful information between them, so that in case of failure another could take over 'keep state' sessions. Our pfsync(4) protocol solves this problem. However, on both sides of the firewall, it is also necessary to have all the regular hosts not see a network failure. The only reliable way to do this is for both firewall machines to have and use the same IP and MAC addresses. But the only real way to do that is to use multicast protocols.
The IETF community proposed work in this direction in the late 90's, however in 1997 Cisco informed them that they believed some of Cisco's patents covered the proposed IETF VRRP (Virtual Router Redundancy Protocol); on March 20, 1998 they went further and specifically named their HSRP "Hot Standby Router Protocol" patent. Reputedly, they were upset that IETF had not simply adopted the flawed HSRP protocol as the standard solution for this problem. Despite this legal pressure, the IETF community forged ahead and published VRRP as a standard even though there was a patent in the space. Why? There was much deliberation at all levels of the IETF, and unfortunately for all of us the politicians within eventually decided to allow patented technology in standards -- as long as the patented technology is licensed under RAND (Reasonable And Non Discriminatory) terms. As free software programmers, we therefore find ourselves in the position that these RAND standards must not be implemented by us, and we must deviate from the standard. We find all this rather Unreasonable and Discriminatory and we will design competing protocols. Some standards organization, eh?
Due to some HSRP flaws fixed by VRRP and for compatibility with the (HSRP-licensed) VRRP implementations of their competitors, Cisco in recent times has largely abandoned HSRP and now relies on VRRP instead -- a protocol designed for and by the community, but for which they claim patent rights.
On August 7 2002, after many communications, Robert Barr (Cisco's lawyer) firmly informed the OpenBSD community that Cisco would defend its patents for VRRP implementations -- meaning basically that it was impossible for a free software group to produce a truly free implementation of the IETF standard protocol. Perhaps this is because Cisco and Alcatel are currently engaged in a pair of patent lawsuits; a small piece of which is Cisco attempting to use the HSRP patent against Alcatel for their use of VRRP. Some IETF working group members took note of our complaints, however an attempt in April 2003 to have the IETF abandon the use of patented technology failed to "reach consensus" in the IETF.
A few years ago, the W3C, who designs our web protocols, tried to move to a RAND policy as well (primarily because of pressure from Microsoft and Apple), but the community outrage was so overpowering that they backed down. Some standards groups use this policy, while others avoid it -- the one differentiation being the amount of corporate participation. In the IETF, the pro-RAND agents work for AT&T, Alcatel, IBM, Cisco, Microsoft, and other large companies. Since IETF is an open forum, they can blend in as the populace, and vote just like all others, except against the community.
Translation: In failing to "reach consensus", the companies who benefit from RAND won, and the community lost again.
Left with little choice, we proceeded to reinvent the wheel or, more correctly, abandon the wheel entirely and go for a "hovercraft". We designed CARP (Common Address Redundancy Protocol) to solve the same problem that these other protocols are designed for, but without the same technological basis as HSRP and VRRP. We read the patent document carefully and ensured that CARP was fundamentally different. We also avoided many of the flaws in HSRP and VRRP (such as an inherent lack of security). And since we are OpenBSD developers, we designed it to use cryptography.
The combination of pf(4), pfsync(4), and carp(4) has permitted us to build highly redundant firewalls. To date, we have built a few networks that include as many as 4 firewalls, all running random reboot cycles. As long as one firewall is alive in a group, traffic through them moves smoothly and correctly for all of our packet filter functionality. Cisco's low end products are unable to do this reliably, and if they have high end products which can do this, you most certainly cannot afford them.
As a final note of course, when we petitioned IANA, the IETF body regulating "official" internet protocol numbers, to give us numbers for CARP and pfsync our request was denied. Apparently we had failed to go through an official standards organization. Consequently we were forced to choose a protocol number which would not conflict with anything else of value, and decided to place CARP at IP protocol 112. We also placed pfsync at an open and unused number. We informed IANA of these decisions, but they declined to reply.
If you want know more info about this case, search the mails related to CARP and patents in the "misc" mailing list of OpenBSD. I think that this case was the first big one case related to this situation (a open protocol with patents).
Probably you can also found information related to SCO lawsuits of the last decade. The clause about patents in the GPLv3 license exists due to the SCO lawsuits.
A lot of projects (and lawyers) have learned very much of the lawsuits of the last decade.
Best Answer
The short answer
In order to license something to others, you have to hold the rights to it. So your ability to license your code covered by the patent may depend on what you can work out with the patent holder.
The long answer
There are a number of ways this can go. You can get a release from the patent holder. You can release your code and hope the patent holder doesn't care; they might not. You can come up with an algorithm that is unencumbered by the patent. You can pay a negotiated patent royalty.
Whether anyone makes money from the GPL'd code may not matter, if public dissemination of the code hinders their ability to profit from the invention. The choice of license may not matter either; it's still a patent issue whether the source code is "copyleft" or not (though your vendor might have a preference as to which license you actually use).
The actual answer
This is one of those times where it might be useful to consult an attorney that specializes in patent and licensing law. They can not only advise you how far you can go with your source code without invoking the patent, but also how an agreement can be correctly crafted between you and the vendor.