Virtual private network

• US 5,768,271 A
• Filed: 04/12/1996
• Issued: 06/16/1998
• Est. Priority Date: 04/12/1996
• Status: Expired due to Term

• Current Assignee: NCR Corporation (NCR Voyix Corporation), Alcatel Data Networks Inc. (Nokia Corporation)
• Original Assignee: Alcatel Data Networks Inc. (Nokia Corporation)
• Inventors: Lespagnol, Albert, Seid, Howard A.
• Primary Examiner(s): TON, DANG T
• Application Number:
  US08/632,168
• Time in Patent Office: 795 Days
• Field of Search: 370/389, 370/390, 370/392, 370/393, 370/394, 370/395, 370/396-400, 370/352, 370/356, 370/357, 370/355, 370/402, 370/409, 370/428
• US Class Current: 370/389
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 12/4604 LAN interconnection over a backbone network, e.g. Internet, Frame Relay
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 2012/5614 User Network Interface
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5645 Connectionless

Abstract

In a packet switching (packet-based) network, such as a frame relay (FR) network, which includes network resources made up of networked elements and customer premises equipment interconnected by one or more physical paths, a Virtual Private Network (VPN) is built above the underlying packet-based network and includes selected portions of the packet-based network resources. The VPN is a collection of logical nodes and virtual paths (VPs) and includes one or more virtual circuits (VCs), each VC being a logical connection between VC terminators including network elements and customer premises equipment. Segments of the VCs are carried by VPs, each VP being a logical connection established between two VP terminators which are located in either network elements or customer premises equipment. One or more VPs are multiplexed on a physical path (PP). Each VP is allocated a positive guaranteed bandwidth (VP-CIR), and each VC on a VP is also allocated a bandwidth (VC-CIR) greater than or equal to zero. Packets of information to be transmitted over a VC are provided with a unique address field to thereby identify the VCs and VPs associated with the VPN over which the packet of information will travel. Congestion control of the network is provided such that congestion control and management are carried out on a per VPN basis, and congestion outside of a VPN'"'"'s logical domain does not affect the performance of the VPN.

Claims

1. A packet-based network for providing virtual private networks, each virtual private network carrying traffic associated with a particular customer of the packet-based network, the traffic including packets for transmission via the packet-based network, the packet-based network comprising:

a plurality of network elements, each being interconnected to at least one other network element by a physical path;

a plurality of customer premises equipment, each being interconnected to a network element by a physical path;

at least one virtual path, each being a logical connection between two virtual path terminators;

at least one virtual circuit, each being a logical connection established between two virtual circuit terminators, wherein packets are transmitted by said virtual circuits between the virtual circuit terminators;

wherein the virtual private network includes a collection of packet-based network resources including respective network elements, customer premises equipment, virtual paths and corresponding virtual circuits, the collection of packet-based network resources making up the virtual private network providing a level of service to the traffic associated with the particular customer of the packet-based network which is independent of all other traffic on the packet-based network which is outside of the virtual private network'"'"'s logical domain; and

identification means contained in the packets of a respective customer having a virtual private network for identifying the respective virtual circuits and virtual paths used by the virtual private network to which the packets are associated.

2. A packet-based network according to claim 1, wherein said identification means is a local identifier of the respective virtual circuits and virtual paths used by the virtual private network, and wherein the packet-based network further includes means for updating said identification means during transmission of the packet of a respective customer within the packet-based network.

3. A packet-based network according to claim 1, wherein:

each virtual path is made up of at least one virtual path segment which is a portion of a virtual path using a particular physical path; and

each virtual circuit is made up of at least one virtual circuit segment which is a portion of the virtual circuit carried by a virtual path between two adjacent network elements, between two adjacent customer premises equipment, or between adjacent network elements and customer premises equipment.

4. A packet-based network according to claim 3, wherein virtual circuit and virtual path terminators include both network elements and customer premises equipment.

5. A packet-based network according to claim 1, wherein said identification means includes an address field having a fixed length virtual circuit identifier field and a fixed length virtual path identifier field to uniquely identify the virtual circuit and virtual path over which the packet of information will travel.

6. A packet-based network according to claim 1, wherein said identification means includes an address field made up of variable length subfields including a class type field, a virtual path identifier field and a virtual circuit identifier field to uniquely identify the virtual circuit and virtual path over which the packet of information will travel, said class type field identifying the length of the virtual path identifier field and virtual circuit identifier field.

7. A packet-based network according to claim 1, wherein said identification means includes an address field in said packets, said address field being an integrated field which identifies virtual paths and virtual circuits over which the packet of information will travel, said integrated field being encoded to uniquely identify how a frame of information is switched within said network elements.

8. A packet-based network according to claim 7, wherein each network element includes a connection table which identifies how a packet is routed within the network element based on the value of the integrated address field.

9. A packet-based network for providing virtual private networks, each virtual private network carrying traffic associated with a particular customer of the packet-based network, the traffic including packets for transmission via the packet-based network, the packet-based network comprising:

a plurality of network elements, each being interconnected to at least one other network element by a physical path;

a plurality of customer premises equipment, each being interconnected to a network element by a physical path;

at least one virtual path, each being a logical connection between two virtual path terminators;

at least one virtual circuit, each being a logical connection established between two virtual circuit terminators, wherein packets are transmitted by said virtual circuits between the virtual circuit terminators;

wherein the virtual private network includes a collection of packet-based network resources including respective network elements, customer premises equipment, virtual paths and corresponding virtual circuits;

identification means contained in the packets of a respective customer having a virtual private network for identifying the respective virtual circuits and virtual paths used by the virtual private network to which the packets are associated; and

wherein each virtual path on a physical path of the network is allocated a respective positive guaranteed bandwidth, and wherein when congestion occurs on a physical path, only a virtual path using bandwidth greater than the respective positive guaranteed bandwidth is required to reduce submission rate of packets onto the network.

10. A packet-based network according to claim 9, wherein the bandwidth utilization of each virtual path within the virtual private network is monitored, and wherein when one virtual path is utilizing less than its respective positive guaranteed bandwidth, any excess bandwidth is equally shared among the remaining virtu paths on a respective physical path in proportion to the respective positive guaranteed bandwidth of the remaining virtual paths with respect to a total bandwidth of the respective physical path.

11. A packet-based network according to claim 9, wherein each virtual circuit is provided with a virtual circuit bandwidth on a respective virtual path, and wherein even if the physical path utilized by a virtual circuit is congested, if the respective virtual path is lightly loaded, the virtual circuit can utilize bandwidth at least equal to or greater than its virtual circuit bandwidth.

12. A packet-based network for providing virtual private networks, each virtual private network carrying traffic associated with a particular customer of the packet-based network, the traffic including packets for transmission via the packet-based network, the packet-based network comprising:

a plurality of network elements, each being interconnected to at least one other network element by a physical path;

a plurality of customer premises equipment, each being interconnected to a network element by a physical path;

at least one virtual path, each being a logical connection between two virtual path terminators;

at least one virtual circuit, each being a logical connection established between two virtual circuit terminators, wherein packets are transmitted by said virtual circuits between the virtual circuit terminators;

wherein the virtual private network includes a collection of packet-based network resources including respective network elements, customer premises equipment, virtual paths and corresponding virtual circuits;

identification means contained in the packets of a respective customer having a virtual private network for identifying the respective virtual circuits and virtual paths used by the virtual private network to which the packets are associated; and

means for establishing a virtual path within the packet-based network locally at each network element traversed by the virtual path, said means for establishing a virtual path including;

means for identifying an outgoing physical path from a network element with available bandwidth to support a guaranteed bandwidth of the virtual path and able to support a number of virtual circuits carried by the virtual path;

means for reserving resources on the physical paths, the reserved resources being indicative of the virtual path bandwidth and number of virtual circuits carried by the virtual path; and

means for updating a connection table in the network element by mapping incoming virtual circuits and virtual paths to respective outgoing virtual circuits and virtual paths.

13. A packet-based network according to claim 12 further including means for establishing a virtual circuit within a virtual private network including:

means for identifying a respective virtual path towards a destination having at least the available bandwidth required by the virtual circuit and an unused virtual circuit segment;

means for reserving resources for the virtual circuit on the respective virtual path, the reserved resources for the virtual circuit being indicative of the virtual circuit bandwidth and the virtual circuit segment on the respective virtual path; and

means for updating the connection table within the network element.

14. A packet-based network according to claim 12, further including means for establishing a signalling virtual circuit on each virtual path.

15. A packet-based network for providing virtual private networks, each virtual private network carrying traffic associated with a particular customer of the packet-based network, the traffic including packets for transmission via the packet-based network, the packet-based network comprising:

a plurality of network elements, each being interconnected to at least one other network element by a physical path;

a plurality of customer premises equipment, each being interconnected to a network element by a physical path;

at least one virtual path, each being a logical connection between two virtual path terminators;

at least one virtual circuit, each being a logical connection established between two virtual circuit terminators, wherein packets are transmitted by said virtual circuits between the virtual circuit terminators;

wherein the virtual private network includes a collection of packet-based network resources including respective network elements, customer premises equipment, virtual paths and corresponding virtual circuits;

identification means contained in the packets of a respective customer having a virtual private network for identifying the respective virtual circuits and virtual paths used by the virtual private network to which the packets are associated, and

a physical service access point for each respective physical path which multiplexes all packets to be transmitted on the respective physical path, the physical service access point including a physical path queue which is served at a physical path rate, the physical path queue being shared by all virtual paths multiplexed on to the respective physical path.

16. A packet-based network according to claim 15 wherein a physical path congestion threshold is determined based on the maximum amount of packets stored in the physical path queue and waiting for transmission on to the respective physical path, and wherein a congestion notification is provided to each of the virtual paths multiplexed onto the respective physical path in response to the length of the physical path queue exceeding the physical path congestion threshold.

17. A packet-based network according to claim 16 wherein said congestion notification includes an additional bit in each packet.

18. A packet-based network according to claim 16 wherein said congestion notification includes a signaling frame transmitted from the physical service access point to each of the virtual paths multiplexed on the physical service access point.

19. A packet-based network according to claim 16 wherein:

each of the virtual paths multiplexed onto the respective physical path is allocated a corresponding positive guaranteed bandwidth;

the sum of the positive guaranteed bandwidth for all of the virtual paths multiplexed onto the respective physical path is less than a total bandwidth of the respective physical path, and

in response to said physical path congestion notification, each virtual path multiplexed onto the respective physical path reduces the submission rate of packets to the physical path queue to a level no greater than the corresponding positive guaranteed bandwidth.

20. A packet-based network according to claim 16 further including a virtual path service access point for each respective virtual path which multiplexes all packets to be transmitted on the respective virtual path from virtual circuits, the virtual path service access point including a virtual path queue which is served at a virtual path rate, the virtual path queue having a congestion threshold indicative of a maximum allowed virtual path queue length, the virtual path service access point providing a virtual path congestion notification to the virtual circuits carried by the respective virtual path in response to the length of the virtual path queue exceeding the virtual path queue threshold.

21. A packet-based network according to claim 20 wherein:

each of the virtual circuits multiplexed onto the respective virtual path is allocated a corresponding virtual circuit bandwidth;

the sum of the virtual circuit bandwidth for all of the virtual circuits multiplexed onto the respective virtual path is less than a guaranteed bandwidth of the respective virtual path, and

in response to the virtual path congestion notification, each respective virtual circuit multiplexed onto the respective virtual path reduces the submission rate of packets to the virtual path queue.

22. A packet-based network according to claim 21, wherein in response to persistence of said virtual path congestion notification after the reduction of the submission rate by each respective virtual circuit, each respective virtual circuit incrementally reduces submission rate until said virtual path congestion notification is removed, the respective virtual circuit only reducing submission rate to a level no greater than the corresponding virtual circuit bandwidth.

23. A packet-based network for providing virtual private networks, each virtual private network carrying traffic associated with a particular customer of the packet-based network, the traffic including packets for transmission via the packet-based network, the packet-based network comprising:

a plurality of network elements, each being interconnected to at least one other network element by a physical path;

a plurality of customer premises equipment, each being interconnected to a network element by a physical path;

at least one virtual path, each being a logical connection between two virtual path terminators;

at least one virtual circuit, each being a logical connection established between two virtual circuit terminators, wherein packets are transmitted by said virtual circuits between the virtual circuit terminators;

wherein the virtual private network includes a collection of Racket-based network resources including respective network elements, customer premises equipment, virtual paths and corresponding virtual circuits;

identification means contained in the packets of a respective customer having a virtual private network for identifying the respective virtual circuits and virtual paths used by the virtual private network to which the packets are associated; and

wherein a pseudo virtual path is provided on each physical path to carry traffic not associated with a virtual private network.

24. A packet-based network according to claim 23, wherein each virtual path and the pseudo virtual path on a physical path of the network is allocated a respective positive guaranteed bandwidth, and wherein when congestion occurs on a physical path, only a virtual path or pseudo virtual path using bandwidth greater than the respective positive guaranteed bandwidth is required to reduce submission rate of packets onto the network.

25. A packet-based network according to claim 24, wherein the bandwidth utilization of each virtual path within the virtual private network is monitored, and wherein when one virtual path is utilizing less than its respective positive guaranteed bandwidth, any excess bandwidth is equally shared among the remaining virtual paths on a respective physical path in proportion to the respective positive guaranteed bandwidth of the remaining virtual paths with respect to a total bandwidth of the respective physical path.

26. A packet-based network according to claim 24, wherein each virtual circuit is provided with a virtual circuit bandwidth on a respective virtual path, and wherein even if the physical path utilized by a virtual circuit is congested, if the respective virtual path is lightly loaded, the virtual circuit can utilize bandwidth at least equal to or greater than its virtual circuit bandwidth.

27. A packet-based network for providing virtual private networks, each virtual private network carrying traffic associated with a particular customer of the packet-based network, the traffic including packets for transmission via the packet-based network, the packet-based network comprising:

a plurality of network elements, each being interconnected to at least one other network element by a physical path;

a plurality of customer premises equipment, each being interconnected to a network element by a physical path;

at least one virtual path, each being a logical connection between two virtual path terminators;

at least one virtual circuit, each being a logical connection established between two virtual circuit terminators, wherein packets are transmitted by said virtual circuits between the virtual circuit terminators;

wherein the virtual private network includes a collection of packet-based network resources including respective network elements, customer premises equipment, virtual paths and corresponding virtual circuits,

identification means contained in the packets of a respective customer having a virtual private network for identifying the respective virtual circuits and virtual paths used by the virtual private network to which the packets are associated;

a general network control center (GNCC) for controlling the packet-based network;

at least one virtual private network control center (VNCC), each respective VNCC being associated with a corresponding virtual private network; and

mediation means located between the GNCC and each respective VNCC for enabling communications therebetween;

wherein for communication from the GNCC to the respective VNCC said mediation means filters messages received from the packet-based network to ensure that GNCC messages are properly formatted for the respective VNCC and passes to the respective VNCC only those messages which pertain to traffic of the corresponding virtual private network; and

wherein for communication from the respective VNCC to the GNCC said mediation means screens VNCC messages to ensure the VNCC messages are properly formatted for the GNCC and to ensure that the VNCC messages are restricted to the packet-based network resources assigned to the corresponding virtual private network.