Peer-model support for virtual private networks with potentially overlapping addresses

Claim 2

A service-provider network comprising a plurality of interconnected provider edge routers and transit routers, wherein: A) each edge router includes circuitry for: i) receiving from a source not in the service-provider network packets that include destination-address fields that specify final destinations that also are not located in the service-provider network; ii) for each of a plurality of such received packets: a) making a routing decision based not only on the contents of that packet's destination-address field but also on the source from which it receives that packet; b) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to an interface on another of the provider edge routers; and c) forwarding the resultant packet to another router in the service-provider network in accordance with the routing decision; and iii) receiving, from other routers in the service provider network, packets that include internal-routing fields and forwarding them without their internal-routing fields to routers, that are not located in the service-provider network, that it selects in accordance with a routing decision based on the contents of the packets' internal-routing fields; and B) each transit router includes circuitry for: i) receiving, from other routers in the service provider network, packets that include internal-routing fields and destination-address fields; ii) making routing decisions based on the contents of those packets' internal-routing fields without reference to those of their destination-address fields; and iii) in accordance with those routing decisions, forwarding those packets to other routers in the service-provider network.

Claim 3

A service-provider network as defined in claim 1 wherein: A) a plurality of the provider edge routers make routing decisions based on the contents of reachability messages that they receive; B) the provider edge routers are together connected to at least first and second pluralities of customer routers, with which the service-provider network respectively associates first and second VPN IDs; C) when an provider edge router receives a reachability message concerning a given network-address range from a customer router with which it associates a given VPN ID, it sends a reachability message concerning the combination of that network-address range and the given VPN ID to each provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and D) when a provider edge router receives a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected, it sends that customer router a reachability message concerning that network-address range.

Claim 4

A service-provider network as defined in claim 2 wherein the provider edge routers use an external gateway protocol to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID.

Claim 5

A service-provider network as defined in claim 3 wherein the external gateway protocol that the provider edge routers use to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID is the Border Gateway Protocol.

Claim 6

A service-provider network as defined in claim 2 wherein: A) the internal-routing field includes both an egress-router field and an egress-channel field; B) the transit routers base their routing decisions concerning packets that include internal-routing fields on the internal-routing fields' egress-router fields without reference to their egress-channel fields; and C) the provider edge routers base their selections of the routers that are not located in the service-provider network on the internal-routing fields' egress-channel fields.

Claim 7

A service-provider network as defined in claim 5 wherein each transit router maintains an information base that associates internal-routing-field contents with routers to which it is connected in the service-provider network and forwards packets containing internal-routing fields to the routers with which that transit router's information base associates the contents of those internal-routing fields.

Claim 8

A service-provider network as defined in claim 6 wherein the information base of at least one transit router associates at least certain internal-routing-field contents with replacement internal-routing-field contents, and that transit router replaces the certain internal-routing-field contents with the replacement internal-routing-field contents in packets that it forwards.

Claim 9

A service-provider network as defined in claim 7 wherein the transit router that replaces internal-routing-field contents replaces the contents of the the egress-router field without replacing the contents of the egress-channel field.

Claim 10

A service-provider network comprising a plurality of interconnected routers including provider edge routers, wherein: A) the provider edge routers are together connected to at least first and second pluralities of customer routers, with which the service-provider network respectively associates first and second VPN IDs; B) each provider edge router includes circuitry for: i) responding to receipt of communications packets by forwarding them in accordance with routing decisions that it makes in accordance with the contents of reachability messages that it has received; ii) responding to receipt of a reachability message concerning a given network-address range from a customer router with which it associates a given VPN ID by sending a reachability message concerning the combination of that network-address range and the given VPN ID to each said provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and iii) responding to receipt of a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected by sending that customer router a reachability message concerning that network-address range.

Claim 11

A service-provider network comprising a plurality of interconnected routers including provider edge routers, wherein: A) the provider edge routers are together connected to at least first and second pluralities of customer routers, with which the service-provider network respectively associates first and second VPN IDs; B) each provider edge router includes circuitry for: i) responding to receipt of communications packets by forwarding them in accordance with routing decisions that it makes in accordance with the contents of reachability messages that it has received; ii) responding to receipt of a reachability message concerning a given network-address range from a customer router with which it associates a given VPN ID by sending a reachability message concerning the combination of that network-address range and the given VPN ID to each said provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and iii) responding to receipt of a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected by sending that customer router a reachability message concerning that network-address range.

Claim 12

A communications system comprising: A) a set of customer nodes so divided into at least first and second customer-node subsets that no node of any given subset is a routing adjacency of any other subset's node; and B) a service-provider network forming a virtual private network with the set of customer communications nodes and comprising a plurality of provider nodes including provider transit routers that form no routing adjacencies with any node of the set of customer communications nodes and further including provider edge routers associated with the set of customer communications nodes, which provider edge routers together form routing adjacencies with at least one node in every one of the customer node subsets, each provider edge router associated with the set of customer communications nodes forming a routing adjacency with at least one customer node, denominated a customer edge router, to which it is linked by at least one provider-customer channel, wherein: i) each provider edge router associated with the set of customer communications nodes includes circuitry for: a) receiving by way of a customer-provider channel that links it to a customer edge router in one of the customer node subsets data packets that include destination-address fields that specify nodes in another of the customer node subsets; b) for each of a plurality of Such received packets: (1) making a routing decision based not only on the contents of that packet's destination-address field but also on the source from which it receives that packet; (2) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to a channel that links another of the provider edge routers; and (3) forwarding the resultant packet to another router in the service-provider network in accordance with the routing decision; and c) receiving, from other routers in the service-provider network, packets that include internal-routing fields and forwarding them without their internal-routing fields by way of a provider-customer channel that it selects in accordance with the contents of the packets' internal-routing fields; and ii) each provider transit router includes circuitry for: a) receiving, from other routers in the service provider network, packets that include internal-routing fields and destination-address fields; b) making routing decisions based on the contents of those packets' internal-routing fields without reference to those of their destination-address fields; and c) in accordance with those routing decisions, forwarding those packets to other routers in the service-provider network.

Claim 13

A communications system comprising: A) a set of customer nodes so divided into at least first and second customer-node subsets that no node of any given subset is a routing adjacency of any other subset's node; and B) a service-provider network forming a virtual private network with the set of customer communications nodes and comprising a plurality of provider nodes including provider transit routers that form no routing adjacencies with any node of the set of customer communications nodes and further including provider edge routers associated with the set of customer communications nodes, which provider edge routers together form routing adjacencies with at least one node in every one of the customer node subsets, each provider edge router associated with the set of customer communications nodes forming a routing adjacency with at least one customer node, denominated a customer edge router, to which it is linked by at least one provider-customer channel, wherein: i) each provider edge router associated with the set of customer communications nodes includes circuitry for: a) receiving by way of a customer-provider channel that links it to a customer edge router in one of the customer node subsets data packets that include destination-address fields that specify nodes in another of the customer node subsets; b) for each of a plurality of Such received packets: (1) making a routing decision based not only on the contents of that packet's destination-address field but also on the source from which it receives that packet; (2) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to a channel that links another of the provider edge routers; and (3) forwarding the resultant packet to another router in the service-provider network in accordance with the routing decision; and c) receiving, from other routers in the service-provider network, packets that include internal-routing fields and forwarding them without their internal-routing fields by way of a provider-customer channel that it selects in accordance with the contents of the packets' internal-routing fields; and ii) each provider transit router includes circuitry for: a) receiving, from other routers in the service provider network, packets that include internal-routing fields and destination-address fields; b) making routing decisions based on the contents of those packets' internal-routing fields without reference to those of their destination-address fields; and c) in accordance with those routing decisions, forwarding those packets to other routers in the service-provider network.

Claim 14

A communications system as defined in claim 10 wherein: A) the communications system further includes a set of outside nodes not included in the virtual private network, at least one of the outside nodes being an outside edge router; B) at least one of the nodes of the provider network is a provider edge router associated with the set of outside nodes and forming a provider-exterior channel with the outside edge router; C) the provider edge routers associated with the set of customer nodes and the set of outside nodes make routing decisions based on the contents of reachability messages that they have received; D) the provider network associates internal and external VPN IDs with the set of customer nodes; E) one of the customer node subsets, denominated the target customer node subset, includes a target node associated with a target network address; F) at least first and second ones of the provider-customer channels are formed between the target customer node subset and the provider network and provide access to the target node; G) the customer edge router of the target customer node subset sends through the first provider-customer channel to a provider edge router reachability messages that advertise a network-address range that includes the target network address; H) the provider edge router that receives such a reachability message through the first provider-customer channel sends a reachability message that advertises the combination of the internal VPN ID and that network-address range only to each other provider edge router that forms a provider-customer channel with the set of customer communications nodes; I) a customer edge router of the target customer node subset also sends through the second provider-customer channel to a provider edge router reachability messages that advertise a network-address range that includes the target network address; J) the provider edge router that receives such a reachability message through the second provider-customer channel sends a reachability message that advertises the combination of the second VPN ID and that network-address range at least to the provider edge router associated with the set of outside nodes; K) when a provider edge router associated with the set of customer nodes receives a reachability message that advertises the combination of a network-address range and the internal VPN ID associated with the virtual private network, it sends to one said customer router with which it forms a customer-provider channel a reachability message that advertises that network-address range; L) when a provider edge router associated with the set of customer nodes receives therefrom a data packet whose destination-address field contains the target network address, it inserts into the packet an internal-routing field that specifies a route to the first provider-customer channel that provides access to the target node; M) when a provider edge router associated with the set of outside nodes receives a reachability message that advertises the combination of a network-address range and the external VPN ID associated with the virtual private network, it sends to one said customer router with which it forms a provider-exterior channel a reachability message that advertises that network-address range; and N) when a provider edge router associated with a set of outside nodes receives therefrom a data packet whose destination-address field contains the target network address, it inserts into the packet an internal-routing field that spedifies a route to the second provider-customer channel that provides access to the target node.

Claim 15

For performing packet-based communication though a service-provider network comprising a plurality of interconnected provider edge routers and transit routers, a method comprising: A) receiving at one said edge router, denominated an ingress router, from a source not in the service-provider network, packets that include destination-address fields that specify final destinations that also are not located in the service-provider network; and B) for each of a plurality of such received packets: i) making a routing decision at said ingress router based not only on the contents of that packet's destination-address field but also on the source from which the ingress router received that packet; ii) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the ingress router received the packet, that specifies a route to an interface on another of the provider edge routers, denominated an egress router; iii) forwarding the resultant packet from said edge router to a chain of at least one transit router in the service-provider network in accordance with the routing decision; iv) making routing decisions in the chain of at least one transit router based on the contents of the packet's internal-routing field without reference to those of its destination-address field; v) in accordance with those routing decisions, forwarding that packet through the chain of at least one transit touter to the egress router; and vi) employing the egress router to forward that packet without its internal-routing field to a router, not located in the service-provider network, that the egress router selects in accordance with a routing decision based on the contents of the packet's internal-routing field.

Claim 16

For performing packet-based communication though a service-provider network comprising a plurality of interconnected provider edge routers and transit routers, a method comprising: A) receiving at one said edge router, denominated an ingress router, from a source not in the service-provider network, packets that include destination-address fields that specify final destinations that also are not located in the service-provider network; and B) for each of a plurality of such received packets: i) making a routing decision at said ingress router based not only on the contents of that packet's destination-address field but also on the source from which the ingress router received that packet; ii) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the ingress router received the packet, that specifies a route to an interface on another of the provider edge routers, denominated an egress router; iii) forwarding the resultant packet from said edge router to a chain of at least one transit router in the service-provider network in accordance with the routing decision; iv) making routing decisions in the chain of at least one transit router based on the contents of the packet's internal-routing field without reference to those of its destination-address field; v) in accordance with those routing decisions, forwarding that packet through the chain of at least one transit touter to the egress router; and vi) employing the egress router to forward that packet without its internal-routing field to a router, not located in the service-provider network, that the egress router selects in accordance with a routing decision based on the contents of the packet's internal-routing field.

Claim 17

A method as defined in claim 12 wherein: A) the routing decisions made at a plurality of the provider edge routers, including the ingress and egress routers, are based on the contents of reachability messages that those routers receive; B) the provider edge routers are together connected to at least first and second pluralities of customer routers, with which the service-provider network respectively associates first and second VPN IDs; C) when an provider edge router receives a reachability message concerning a given network-address range from a customer router with which it associates a given VPN ID, it sends a reachability message concerning the combination of that network-address range and the given VPN ID to each provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and D) when a provider edge router receives a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected, it sends that customer router a reachability message concerning that network-address range.

Claim 18

A method as defined in claim 13 wherein the provider edge routers use an external gateway protocol to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID.

Claim 19

A method as defined in claim 14 wherein the external gateway protocol that the provider edge routers use to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID is the Border Gateway Protocol.

Claim 20

A method as defined in claim 13 wherein: A) the internal-routing field includes both an egress-router field and an egress-channel field; B) the transit routers base their routing decisions concerning packets that include internal-routing fields on the internal-routing fields' egress-router fields without reference to their egress-channel fields; and C) the egress routers bases its selections of the routers that are not located in the service-provider network on the internal-routing fields' egress-channel fields.

Claim 21

A method as defined in claim 16 wherein each transit router maintains an information base that associates internal-routing-field contents with routers to which it is connected in the service-provider network and forwards packets containing internal-routing fields to the routers with which that transit router's information base associates the contents of those internal-routing fields.

Claim 22

A method as defined in claim 17 wherein the information base of at least one transit router associates at least certain internal-routing-field contents with replacement internal-routing-field contents, and that transit router replaces the certain internal-routing-field contents with the replacement internal-routing-field contents in packets that it forwards.

Claim 23

A method as defined in claim 18 wherein the transit router that replaces internal-routing-field contents replaces the contents of the egress-router field without replacing the contents of the egress-channel field.

Claim 24

For performing packet-based communication though a service-provider network comprising a plurality of interconnected routers including provider edge routers together connected to at least first and second pluralities of customer routers, a method comprising: A) associating first and second VPN IDs with the first and second pluralities of customer routers, respectively; B) employing each said provider edge router to respond to receipt of communications packets by forwarding them in accordance with routing decisions that it makes in accordance with the contents of reachability messages that it receives; C) employing each said provider edge router to respond to receipt of a reachability message concerning a given network-address range from a customer router with which a given VPN ID is associated by sending a reachability message concerning the combination of that network-address range and the given VPN ID to each said provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and D) employing each said provider edge router to respond to receipt of a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected by sending that customer router a reachability message concerning that network-address range.

Claim 25

For performing packet-based communication though a service-provider network comprising a plurality of interconnected routers including provider edge routers together connected to at least first and second pluralities of customer routers, a method comprising: A) associating first and second VPN IDs with the first and second pluralities of customer routers, respectively; B) employing each said provider edge router to respond to receipt of communications packets by forwarding them in accordance with routing decisions that it makes in accordance with the contents of reachability messages that it receives; C) employing each said provider edge router to respond to receipt of a reachability message concerning a given network-address range from a customer router with which a given VPN ID is associated by sending a reachability message concerning the combination of that network-address range and the given VPN ID to each said provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and D) employing each said provider edge router to respond to receipt of a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected by sending that customer router a reachability message concerning that network-address range.

Claim 26

A communications method comprising: A) providing a set of customer nodes so divided into at least first and second customer-node subsets that no node of any given subset is a routing adjacency of any other subset's node; B) providing a service-provider network forming a virtual private network with the set of customer communications nodes and comprising a plurality of provider nodes including provider transit routers that form no routing adjacencies with any node of the set of customer communications nodes and further including provider edge routers associated with the set of customer communications nodes, which provider edge routers together form routing adjacencies with at least one node in every one of the customer node subsets, each provider edge router associated with the set of customer communications nodes forming a routing adjacency with at least one customer node, denominated a customer edge router, to which it is linked by at least one provider-customer channel; C) employing a provider edge router associated with the set of customer communications nodes to receive by way of a customer-provider channel that links that provider edge router to a customer edge router in one of the customer node subsets data packets that include destination-address fields that specify nodes in another of the customer node subsets; and D) for each of a plurality of such received packets: i) employing the provider edge router to: a) make a routing decision based not only on the contents of that packet's destination-address field but also on the source from which it receives that packet; b) insert into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to a channel that links another of the provider edge routers, denominated an egress router; and c) forward the resultant packet to a chain of at least one of the transit routers in the service-provider network in accordance with the routing decision; ii) making routing decisions in the chain of at least one transit router based on the contents of those packet's internal-routing field without reference to those of their destination-address field; iii) in accordance with those routing decisions, forwarding that packet through the chain of at least one transit router to the egress router; and iv) employing the egress router to forward that packet without its internal-routing field by way of a provider-customer channel that it selects in accordance with the contents of the packet's internal-routing field.

Claim 27

A communications method comprising: A) providing a set of customer nodes so divided into at least first and second customer-node subsets that no node of any given subset is a routing adjacency of any other subset's node; B) providing a service-provider network forming a virtual private network with the set of customer communications nodes and comprising a plurality of provider nodes including provider transit routers that form no routing adjacencies with any node of the set of customer communications nodes and further including provider edge routers associated with the set of customer communications nodes, which provider edge routers together form routing adjacencies with at least one node in every one of the customer node subsets, each provider edge router associated with the set of customer communications nodes forming a routing adjacency with at least one customer node, denominated a customer edge router, to which it is linked by at least one provider-customer channel; C) employing a provider edge router associated with the set of customer communications nodes to receive by way of a customer-provider channel that links that provider edge router to a customer edge router in one of the customer node subsets data packets that include destination-address fields that specify nodes in another of the customer node subsets; and D) for each of a plurality of such received packets: i) employing the provider edge router to: a) make a routing decision based not only on the contents of that packet's destination-address field but also on the source from which it receives that packet; b) insert into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to a channel that links another of the provider edge routers, denominated an egress router; and c) forward the resultant packet to a chain of at least one of the transit routers in the service-provider network in accordance with the routing decision; ii) making routing decisions in the chain of at least one transit router based on the contents of those packet's internal-routing field without reference to those of their destination-address field; iii) in accordance with those routing decisions, forwarding that packet through the chain of at least one transit router to the egress router; and iv) employing the egress router to forward that packet without its internal-routing field by way of a provider-customer channel that it selects in accordance with the contents of the packet's internal-routing field.