CN100433731C - Method for realizing VPN multicast - Google Patents

Abstract

The invention relates to a matching method of a public network multicast distribution tree, comprising: a group management router calculates each coverage value of the current private network multicast group in each existing public network multicast distribution tree; Whether there is a public network multicast distribution tree whose coverage value is greater than the coverage threshold in the distribution tree, if yes, then judge whether there is a unique distribution tree with the largest coverage, if yes, select the public network multicast distribution tree with the largest coverage If not, then judge whether there is a unique static distribution tree, if yes, then select the static public network multicast distribution tree; if not, then judge whether there is a distribution tree with the largest number of unique references, if yes , select the public network multicast distribution tree; if not, select the public network multicast distribution tree with the earliest creation time. The invention also relates to a method for realizing VPN multicast, selecting a matching tree or creating a new tree. The invention reduces the waste of bandwidth.

Description

A Method of Realizing VPN Multicast

technical field

The invention relates to a matching method of public network multicast distribution tree, and also relates to a method for realizing VPN multicast. It belongs to the field of communication.

Background technique

In the network, each user access point is called a site (Site). The VPN (Virtual Private Network) network includes the following entities: Provider Edge Router (PE for short) is used to provide users with network interfaces in the backbone network of operators, store virtual routing (VirtualRouting Forwarding Instance, VRF) forwarding , process VPN-IPv4 routing, and access VPN subnets located at various sites, which are the main implementation parts of VPN; Customer Edge Router (CE for short), the network interface that accesses the backbone network of the operator in the user VPN site, Converge the private network routes of this site, publish and receive user network routes; the core router of the operator network (referred to as P router), undertakes the task of forwarding all data packets in the backbone network; the VPN users of each site pass through the user border router The CE is connected to the PE of the local operator's border router, and corresponds to a specific storage virtual router VRF on the PE. Some policies are configured on the VRF to specify the routing information of which sites the router of this site can receive and which routing information can be advertised to the outside. Each PE performs routing calculation according to the extended information of BGP (Border Gateway Protocol), and generates a routing table for each relevant VPN. The carrier border router PE equipment maintains multiple routing tables and supports multiple instances of dynamic routing protocols.

The carrier network is a public network used to transmit multicast data packets from different sites. It includes a public network multicast group (referred to as P-Group) and a public network multicast distribution tree (abbreviated as P-Tree).

The user's private network is an independent and autonomous IPv4 network system. It includes a private network multicast group (C-Group for short), and a private network multicast distribution tree (C-Tree for short).

Multicast VPN can be implemented in various forms, such as unicast scheme, which has a serious efficiency problem. Every time one CE is changed, all other CEs need to be reconfigured, so the expansion performance of the system is very poor. Multicast domain scheme (Multicast-Domain, referred to as MD), multicast data is transmitted in the way of flooding in the multicast domain router of the backbone network, the data forwarding is not optimal forwarding, it will reach the router without private network receivers, and then be This wastes the network bandwidth in the backbone network to a certain extent, and also increases the processing load of the router.

At present, the better scheme is the multicast domain (MD) improvement scheme. When the data transmission volume of a certain multicast group of a certain VPN in the multicast domain exceeds a certain threshold, the VPN-IP PIM scheme will be used for the multicast group Establish a dynamic MDT (Multicast Distribution Tree, multicast distribution tree), and multicast traffic can flow along this dynamic MDT optimization path. This can not only reduce the burden on operators to manage multicast routes in the public network, but also provide guarantee for high-speed multicast data transmission. In fact, this scheme of establishing dynamic MDT for VPN still has certain limitations, because there are many VPNs that need to be supported in the operational network, and there are many dynamic MDTs in each VPN, so the improved multicast In the domain method, there are still many multicast routing entries in the public network; at the same time, in this solution, only the large traffic in the public network multicast group can be detected, but the shortcomings caused by the sparse distribution of sites cannot be well handled .

The improved multicast domain scheme has been recognized by most researchers because of its fully controllable routing table items and the advantages of optimizing transmission for specific data sources. However, the improved multicast domain scheme only considers the problem of high sending rate of a certain source, but does not consider the problem of sparse station distribution, and the waste of bandwidth at this time is still very large.

Contents of the invention

The technical problem to be solved by the present invention lies in addressing the deficiencies in the prior art, through coverage calculation, using the existing public network multicast distribution tree matching method, reducing the waste of network bandwidth in the public network, while reducing the public network The amount of multicast tree information maintained by the routers reduces the burden on the server and enables the network to support more virtual private network multicast services.

For this reason, the present invention provides a kind of matching method of public network multicast distribution tree, comprises the following steps:

Step 1. The group management router calculates the coverage values of the current private network multicast group in each existing public network multicast distribution tree according to the following coverage formula,

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{tree})$

Among them, PEs is the operator's border router, C-Group is the private network multicast group, P-Tree is the public network multicast distribution tree, and the coverage refers to that when the receivers of the private network multicast group are all members of the operator's border router When the public network multicast distribution tree is a member of the operator's border router, the coverage degree of the private network multicast group to the public network multicast distribution tree;

Step 2, the group management router judges whether there is a public network multicast distribution tree whose coverage value is greater than the preset coverage threshold in the public network multicast distribution tree, if yes, then perform step 3; if not, then match fails, and ends;

Step 3, the group management router judges whether there is only one public network multicast distribution tree with the largest coverage in the public network multicast distribution tree greater than the coverage threshold, and if so, the public network group with the largest coverage The broadcast distribution tree matches the distribution tree of the private network multicast group; if not, go to step 4;

Step 4, the group management router judges whether there is only one static public network multicast distribution tree in the public network multicast distribution tree greater than the coverage threshold, and if so, then matches the static public network multicast distribution tree is the distribution tree of the private network multicast group; if not, go to step 5;

Step 5. The group management router judges whether there is only one public network multicast distribution tree with the largest number of references by each private network multicast group, and if so, then matches the public network multicast distribution tree to the private network multicast group distribution tree; if not, go to step 6;

Step 6. Match the public network multicast distribution tree with the earliest creation time as the distribution tree of the private network multicast group.

The present invention also provides a method for realizing VPN multicast, comprising the following steps:

Step 1. The group management router judges whether there is a private network multicast group that can cover the current private network multicast group in the existing public network multicast distribution tree according to the private network multicast group signal that changes the state of the bearer tree, and according to the public network multicast group The matching method of the network multicast distribution tree selects the public network multicast distribution tree that matches the private network multicast group; if yes, then perform step 3; if not, then perform step 2;

Step 2, establish a new public network multicast distribution tree for the private network multicast group, and then end;

Step 3. Select the public network multicast distribution tree as the distribution tree of the private network multicast group.

The present invention uses the existing public network multicast distribution tree matching method through coverage calculation to reduce the amount of multicast routing table information maintained in the public network; the present invention also uses the public network multicast distribution tree matching method to establish A distribution tree that meets the coverage requirements reduces the bandwidth waste caused by the sparse distribution of receiving member sites in the prior art. The coverage requirement avoids the sparse distribution of receiving member sites, reduces the waste of bandwidth, and reduces the amount of information maintained by the multicast routing table in the public network.

The technical solutions of the present invention will be described in further detail below with reference to the accompanying drawings and embodiments.

Description of drawings

Fig. 1 is the flowchart of the first embodiment of the present invention;

Fig. 2 is a flow chart of the second embodiment of the present invention.

Detailed ways

Firstly, the relevant terms involved in the present invention will be introduced below.

Group management router: a router for management and maintenance and for mapping functions. The group management router is relative to each C-Group. For example, to switch to a private network multicast group (C-Group) in the public network, a public network multicast distribution tree (P-Tree) needs to be selected as its distribution tree. The group management router supervises and manages the C-Group, establishes a distribution tree P-Tree for it, and notifies other recipients of the C-Group, the operator's border router PE, to switch to the P-Tree. A router entity may contain many group management routers, and these group management routers can share the router's distribution tree, or apply to the router to create a new distribution tree. We also use group-managed router to denote a router entity that contains group-managed routers.

Coverage: It means that when the receiver PE members of the private network multicast group (C-Group) are all PE members of the P-Tree (that is to say, the two are the relationship between the subset and the original set), the C-Group The degree of coverage of the P-Tree. Its value is a real value between [0, 1]. If a certain P-Tree is used to distribute the data packets of the C-Group, the smaller the coverage, the greater the bandwidth waste. Its formula is as follows:

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{tree})$

Among them, PEs is the border router of the operator, C-Group is the private network multicast group, and P-Tree is the public network multicast distribution tree.

Multicast domain: a distribution tree configured for each VPN, it is a static shared tree, including all PE members of the VPN, all C-Groups use this tree to distribute data by default, some VPN control Messages are also distributed in this tree.

Switching: When the data packets in the private network are transmitted in the public network, we need to select a P-Tree as the distribution tree for it, and in order to optimize the transmission, the public network distribution tree used is also dynamically changed. The tree process is called the "switching" process. According to different types of distribution trees and different preconditions for switching, switching is also divided into multiple types.

The tree types involved in the present invention are as follows:

The public network multicast distribution tree (P-Tree) adopts the source tree type. When the private network multicast group (C-Group) is the source tree, the P-Tree of the source tree type should be used to distribute data; when the C-Group is a shared tree, but the site includes an RP (Rendezvous Point, rendezvous point) point , and the data source is a unicast data packet to the RP point, when the data packets of this group traverse the public network, the source tree type P-Tree can also be used to achieve optimal forwarding.

The public network multicast distribution tree (P-Tree) adopts the shared tree type. When the private network multicast group (C-Group) is a shared tree, the shared tree type P-Tree should be used.

The public network multicast distribution tree (P-Tree) can also be divided into static tree and dynamic tree.

The static tree P-Tree is established by manual configuration. Any distribution tree with a stable topology in the public network can be configured statically, and any static tree cannot be automatically deleted by the router. For example, all multicast domains must be implemented using static trees, and the P-Tree that has appeared in the public network for a long time should also be configured as a static multicast tree, so as to stabilize the P-Tree routing items in the public network and reduce maintenance costs. Speed up the forwarding process.

In order to reduce the amount of information in the routing table in the public network, it is necessary to support the dynamic tree P-Tree. These P-Trees will only be established when needed, and will always exist when there is a C-Group reference, until the reference count reaches zero, the group management router will actively release the dynamic tree to reduce maintenance in the public network multicast routing entry. The number of dynamic trees that can be established should be controlled by the operator in some way, so as to ensure good scalability of the operator's network.

In order to maintain the established P-Tree and the mapping relationship between the C-Group and the P-Tree, the PE router needs to maintain the tree table and the group table to manage these basic information. The tree table and group table involved in the present invention are as follows:

The tree table stores the P-Tree information established by the group management router, and is the main basis for selecting the public network forwarding tree for the C-Group. Table 1 is the data items contained in the tree table, as shown in Table 1:

Table 1

IP Address Tree Label Tree-Type Ref-Count Dynamic PEs-List

in FIG. 1,

IP Address: IPv4 multicast address of P-Tree, that is, P-Group;

Tree Label: P-Tree mark;

Tree-Type: the type of P-Tree, source tree or shared tree;

Ref-Count: the number of C-Groups referencing the tree;

Dynamic: A dynamically created flag, identifying whether the P-Tree is dynamically created;

PEs-List: PE member list, which identifies the PE members covered by the P-Tree.

Table 2 is the member information of the C-Group switched to the P-Tree saved in the group table, as shown in Table 2:

Table 2

VPN-RD G PEs-List

Table 2,

VPN-RD: identifies the VPN to which the group belongs;

G: private network multicast address;

PEs-List: PE member list, which identifies the PE members covered by this group.

The C-Groups in the group table are those C-Groups that meet the switching conditions, leave the default multicast domain distribution tree, and perform optimized transmission in the public network. In order to indicate that the group has switched and maintain the information of the group in the public network, it is necessary for the group management router to periodically send the corresponding MDTJoin TLV (handover message) message to the multicast domain to notify other receivers PE that the C -Group is transmitted on the corresponding P-Tree outside the multicast domain.

Another alternative solution is: if the delay in the Join (joining a multicast group) process can be tolerated, the group table does not need to be maintained. When it is necessary to obtain the member list of the C-Group, all member PEs of the group are known by temporarily sending member PE query messages.

The definition constants involved in the present invention are as follows:

Traffic threshold: In order to prevent frequent switching on the boundary, it is necessary to define the upper and lower boundaries of the traffic threshold. During the traffic detection process, when the traffic of a certain C-Group is higher than the upper bound of the traffic, it will be switched to the public network, and when its traffic is lower than the lower bound of the traffic, it will be switched back to the multicast domain . However, there is a dead zone between the flow lower bound and the upper bound. When the flow value is in this area, the C-Group remains in its original state. Controlling the length of the dead zone can control the stability of the public network multicast group.

Example 1

Fig. 1 is a flowchart of the first embodiment of the present invention. As shown in Figure 1, it includes the following steps:

Step 1. The group management router calculates the coverage values of the current private network multicast group in each existing public network multicast distribution tree according to the following coverage formula,

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{tree})$

Among them, PEs is the operator's border router, C-Group is the private network multicast group, and P-Tree is the public network multicast distribution tree;

Step 2, the group management router judges whether there is a public network multicast distribution tree whose coverage value is greater than the preset coverage threshold in the public network multicast distribution tree, if yes, then perform step 3; if not, then match fails, and ends;

Step 3, the group management router judges whether there is only one public network multicast distribution tree with the largest coverage among the public network multicast distribution trees greater than the coverage threshold, if yes, then execute step 7; if not, then execute Step 4;

Step 4, the group management router judges whether there is only one static public network multicast distribution tree in the public network multicast distribution tree greater than the coverage threshold, if yes, then perform step 8; if not, then perform step 5 ;

Step 5, the group management router judges whether there is only one public network multicast distribution tree with the largest number of references by each private network multicast group, if yes, then perform step 9; if not, then perform step 6;

Step 6, matching the public network multicast distribution tree with the earliest creation time as the distribution tree of the private network multicast group;

Step 7, matching the public network multicast distribution tree with the largest coverage as the distribution tree of the private network multicast group, and then ending;

Step 8, matching the static public network multicast distribution tree to the distribution tree of the private network multicast group, and then ending;

Step 9. Match the public network multicast distribution tree to the distribution tree of the private network multicast group, and then end.

The specific operation of the above steps is as follows:

Assuming that a tree needs to be allocated to a group R containing members {PE1, PE4, PE8}, Table 11 below is the tree table.

where coverage is calculated.

Table 11

serial number PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 Tree type Citations Coverage 1 √ √ √ × √ × × √ static 13 -

2 √ √ × √ × × √ √ static 12 0.6 3 × √ √ √ × × √ √ static 9 - 4 √ × × √ √ × × √ static 16 0.75 5 √ √ × √ × × × √ static 16 0.75 6 × √ √ √ √ √ √ × static 12 - 7 √ × √ √ × √ × √ static 8 0.6 8 √ √ √ × × √ × √ static 11 - 9 √ × √ √ √ × √ √ dynamic 3 0.5 10 √ √ × √ × √ √ × dynamic 6 - 11 × √ √ × × × × × dynamic 2 - 12 √ × √ √ × × × √ dynamic 1 0.75 13 × √ × √ × × √ √ dynamic 1 - 14 × × × × × × √ × dynamic 3 - 15 √ √ × √ √ × × √ dynamic 1 0.6 16 √ √ × √ √ × √ √ dynamic 2 0.5 17 × √ × √ √ × × √ dynamic 1 - 18 √ × × √ × √ × × dynamic 1 - 19 × × √ × × × × × dynamic 1 -

Step 101, assuming that we set the coverage threshold as 0.6, then we can see that the tree that meets the coverage requirements is shown in Table 12, which is:

Table 12

serial number PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 Tree type Citations Coverage 2 √ √ × √ × × √ √ static 12 0.6 4 √ × × √ √ × × √ static 16 0.75 5 √ √ × √ × × × √ static 16 0.75 7 √ × √ √ × √ × √ static 8 0.6 12 √ × √ √ × × × √ dynamic 1 0.75 15 √ √ × √ √ × × √ dynamic 1 0.6

Step 102, then select the only tree with the largest coverage, the result is as shown in Table 13:

Table 13

serial number PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 Tree type Citations Coverage 4 √ × × √ √ × × √ static 16 0.75 5 √ √ × √ × × × √ static 16 0.75 12 √ × √ √ × × × √ dynamic 1 0.75

If no unique tree is obtained in step 103 and step 102, a static tree is selected, and the result is as shown in table 14:

Table 14

serial number PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 Tree type Citations Coverage 4 √ × × √ √ × × √ static 16 0.75 5 √ √ × √ × × × √ static 16 0.75

If no unique tree is obtained in steps 104 and 103, the tree with the largest number of references is selected. As shown in Table 15, since the two trees selected now have the same number of references, the result has not changed:

Table 15

serial number PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 Tree type Citations Coverage 4 √ × × √ √ × × √ static 16 0.75 5 √ √ × √ × × × √ static 16 0.75

If no unique tree is obtained in step 105 and step 104, then select the tree with the earliest creation time, as shown in Table 16, the earliest time is first, and the results are as follows:

Table 16 serial number PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 tree type Citations Coverage 4 √ x x √ √ x x √ static 16 0.75

After the above steps, you can select the tree with the unique result number 4, match the tree to group R, add one to the reference number, and modify other information maintained in the tree table and group table. One tree selection and allocation process is Can be done.

Example 2

Fig. 2 is a flowchart of the second embodiment of the present invention. Embodiment 2 is a method for realizing VPN multicast

method, including the following steps:

Step 11, the group management router judges whether there is a private network multicast group that can cover the current private network multicast group in the existing public network multicast distribution tree according to the private network multicast group signal that changes the state of the bearer tree, and according to the public network multicast group The matching method of the network multicast distribution tree selects the public network multicast distribution tree that matches the private network multicast group; if yes, then perform step 13; if not, then perform step 12;

Step 12, set up a new public network multicast distribution tree for the private network multicast group, and then end;

Step 13. Select the public network multicast distribution tree as the distribution tree of the private network multicast group.

The establishment of a new tree mentioned in step 12 in this embodiment refers to the establishment of a new public network multicast distribution tree for members in the current private network multicast group.

Example 3

The difference between this embodiment and Embodiment 2 is that the group management router in step 11 receives the private network multicast group signal to change the state of the bearer tree from the newly added user multicast group or the existing multicast group sent from the network side. of new user join messages.

Example 4

The difference between this embodiment and Embodiment 2 is that the private network multicast group signal for changing the bearer tree state in step 11 comes from the group management router to determine whether the coverage value is less than the preset first coverage threshold, and the traffic Signal whether the value is less than the preset flow threshold.

Example 5

The difference between this embodiment and Embodiment 2 is that the private network multicast group signal to change the state of the bearer tree in step 11 comes from the group management router to determine whether the coverage value is less than or equal to the preset second coverage threshold, and the traffic A signal indicating whether the value is greater than or equal to a preset flow threshold.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention without limitation. Although the present invention has been described in detail with reference to the preferred embodiments, those of ordinary skill in the art should understand that the technical solutions of the present invention can be The scheme shall be modified or equivalently replaced without departing from the spirit and scope of the technical scheme of the present invention.

Claims (5)

1. a public network multicast issuing tree matching method is characterized in that, comprises the steps:

Step 1, group management router are calculated current private network multicast group each coverage numerical value in each existing public network multicast issuing tree according to following coverage formula,

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

Wherein, PEs is the operator edge router, C-Group is the private network multicast group, P-Tree is a public network multicast issuing tree, coverage is meant that the private network multicast group is to the level of coverage of public network multicast issuing tree when recipient's operator edge router member of private network multicast group is the operator edge router member of public network multicast issuing tree;

Step 2, group management router judge whether there be the public network multicast issuing tree of coverage numerical value greater than predefined coverage threshold value in the described public network multicast issuing tree, if then execution in step 3; If not, then it fails to match, finishes then;

Step 3, group management router judge whether to exist the public network multicast issuing tree of a unique coverage maximum in the public network multicast issuing tree greater than described coverage threshold value, if then the public network multicast issuing tree coupling with this coverage maximum is the distribution tree of this private network multicast group; If not, execution in step 4 then;

Step 4, group management router judge whether to exist the public network multicast issuing tree of unique static state in the public network multicast issuing tree greater than described coverage threshold value, if public network multicast issuing tree coupling that then should static state is the distribution tree of this private network multicast group; If not, execution in step 5 then;

Step 5, group management router judge whether to exist a unique maximum public network multicast issuing tree of being quoted by each private network multicast group of quantity, if then this public network multicast issuing tree coupling is the distribution tree of this private network multicast group; If not, execution in step 6 then;

Step 6, be the distribution tree of this private network multicast group with creation-time public network multicast issuing tree coupling the earliest.

2. an application rights requires 1 described public network multicast issuing tree matching method to realize the method for VPN multicast, it is characterized in that, comprises the steps:

Step 1, group management router are according to the private network multicast group signal that changes the carrying tree state, in existing public network multicast issuing tree, judge whether to exist one can cover current private network multicast group, and the public network multicast issuing tree of selecting according to described public network multicast issuing tree matching method that is complementary with this private network multicast group; If then execution in step 3; If not, execution in step 2 then;

Step 2, set up a new public network multicast issuing tree, finish then for this private network multicast group;

Step 3, select this public network multicast issuing tree to be the distribution tree of this private network multicast group.

3. the method for realization VPN multicast according to claim 2 is characterized in that, the new user that the private network multicast group signal of described change carrying tree state comes from the Add User multicast group or the existing multicast group of network side transmitted adds message.

4. the method for realization VPN multicast according to claim 2, it is characterized in that, whether the private network multicast group signal of change in the described step 1 carrying tree state comes from numerical value that the group management router judges coverage less than the predefined first coverage threshold value, and whether flow number is less than the signal of preset flow rate threshold value.

5. the method for realization VPN multicast according to claim 2, it is characterized in that, the private network multicast group signal of change in the described step 1 carrying tree state comes from the group management router and whether judges coverage numerical value smaller or equal to the predefined second coverage threshold value, and whether flow number is more than or equal to the signal of preset flow rate threshold value.

Images