CN104811387B - The equal cost multipath explicitly replicated with position index - Google Patents

Abstract

Disclosed herein is the equal cost multipaths explicitly replicated with position index.The various system and method for (BIER) are explicitly replicated for performing position index.It is grouped as an example, a kind of method is related to receive in node.Grouping includes bit string.Node is based on flow valuve associated with grouping and selects forwarding information.Forwarding information includes forwarding bitmask.Node is then based on bit string and forwarding information to forward grouping.

Description

The equal cost multipath explicitly replicated with position index

Related application

Based on the 119th article of e money of United States patent law, the application is asked in the temporary patent application submitted on January 24th, 2014 Number for 61/931,473, the country of the patent application of entitled " the bitmask forwarding plane replicated for stateless multiple spot " is excellent It first weighs, the entire disclosure of which is incorporated herein by reference and for all purposes.

The application is still 14/488,790 in the number of patent application submitted on the 17th of September in 2014, entitled " to utilize more associations View label switching position index explicitly replicate " part continuation application, this application again transfer according to the 119th article of e of United States patent law Money request is 61/878,693 in the Provisional Patent Application No. submitted on the 17th of September in 2013, entitled " to have forwarding bitmask Multicast IPv6 " and on January 24th, 2014 Provisional Patent Application No. submitted be 61/931,473, it is entitled " for statelessly Multiple spot replicate bitmask forwarding structure " patent application domestic right.The application or number of patent application are 14/488, 761, the part continuation application of entitled " position index explicitly replicates ", this application is transferred please according to the 119th article of e money of United States patent law It is 61/878,693 to ask in the Provisional Patent Application No. submitted on the 17th of September in 2013, entitled " to have the multicast of forwarding bitmask IPv6 " and on January 24th, 2014 Provisional Patent Application No. submitted be 61/931,473, it is entitled " for stateless more The domestic right of the patent application of the bitmask forwarding structure that point replicates ".The application still submitted special on the 17th in September in 2014 Sharp Application No. 14/488,810, the part of entitled " explicitly being replicated using the position index of internet network agreement the 6th edition " after Continuous application, this application are transferred according to the 119th article of e moneys request of United States patent law in the SProvisional Patent Shen that September in 2013 is submitted on the 17th It entitled " the multicast IPv6 with forwarding bitmask " and please be submitted on January 24th, 2014 interim number for 61/878,693 Number of patent application is 61/931473, the patent application of entitled " the bitmask forwarding structure replicated for stateless multiple spot " Domestic right.For all purposes, every application of the two pieces provisional application of above-mentioned reference and three non-provisional applications is complete Portion's content is incorporated herein by reference and for all purposes, as they are herein by completely and as all proposing.

Technical field

Present application relates generally to network technology, and more particularly to the equal cost multipath explicitly replicated with position index.

Background technology

Target node data.The form of network node can be one or more routers, one or more bridges, One or more interchangers, one or more servers or any other applicable communication processing equipment.The data are typically adopted It is forwarded with the form and utilization forwarding table of grouping.The format unit of data is grouped into, generally include control information and is effectively carried Lotus data.Control information can include：Identify the information (for example, address) of source and destination, similar to the error detection for verifying sum Code, sequence information etc..Control information is usually located at head and the afterbody of grouping.Valid data are usually located at head and the tail of grouping Between portion.

Forwarding grouping is related to different processing, although it can be complicated that these processing concepts are simple.Forwarding grouping institute The processing being related to changes with the type of the retransmission method used.In many networks, be more likely to using multicast come Forward data.One of those is the reason is that multicast is a kind of by reducing the band of flow by distributing data to multiple receiving terminals Wide saving technique.However, in conventional multicast system, considerable control plane information has been used.Establish and safeguard this control Information by with becoming trend that is complicated and expending computing resource, and can become in overall performance of network main limitation because Element.Multicast another problem is that：Due to the use of packet distribution mechanism, sometimes grouping be forwarded to undesirable destination.Point These unnecessary distributions of group mean to cause network performance unwelcome burden.This is overcome by traditional approach Burden is related to generation and safeguards even more control plane information.

The content of the invention

In accordance with an embodiment of the present disclosure, it is proposed that a kind of method, including：It receives and is grouped in node, wherein grouping includes position String；First group of forwarding information is selected from multigroup forwarding information, wherein the selection is based on flow valuve, and first group of forward packets Include forwarding bitmask；And it is grouped based on bit string and first group of forwarding information to forward.

In accordance with an embodiment of the present disclosure, it is also proposed that a kind of network equipment, including：Memory, the memory storage are more Group forwarding information；Network interface, which is configured as receiving grouping, wherein wherein grouping includes bit string；And processing Device, the processor are configured as：First group of forwarding information is selected from multigroup forwarding information, wherein selecting first group of forwarding information It is to be carried out based on flow valuve, and first group of forwarding information includes forwarding bitmask；And based on bit string and first group of forwarding letter Breath is grouped to forward.

In accordance with an embodiment of the present disclosure, it is also proposed that a kind of system, including：Storage device, the storage device are used to store Multigroup forwarding information；Network Interface Unit, the Network Interface Unit are grouped for receiving, wherein grouping includes bit string；And place Device is managed, which is used for：First group of forwarding information is selected from multigroup forwarding information, wherein selecting first group of forwarding letter Breath is carried out based on flow valuve, and first group of forwarding information includes forwarding bitmask；And based on bit string and first group of forwarding Information is grouped to forward.

Description of the drawings

By reference to attached drawing, the disclosure can be better understood, and its numerous objects, features and advantages are to this field Technical staff becomes more apparent upon.

Fig. 1 is the simplified block diagram for some components for showing example network.

Fig. 2 is the simplified block diagram for some components for showing example network.

Fig. 3 A are the flow charts according to instantiation procedure used by present specification shows node.

Fig. 3 B are the flow charts according to instantiation procedure used by present specification shows node.

Fig. 4 is the simplified block diagram for some components for showing example network.

Fig. 5 A are the sample tables generated according to this specification by node.

Fig. 5 B are the sample tables generated according to this specification by node.

Fig. 6 is the sample table generated according to this specification by node.

Fig. 7 A are the sample tables generated according to this specification by node.

Fig. 7 B are the sample tables generated according to this specification by node.

Fig. 7 C are the sample tables generated according to this specification by node.

Fig. 7 D are the sample tables generated according to this specification by node.

Fig. 8 is the sample table generated according to this specification by node.

Fig. 9 is the flow chart according to instantiation procedure used by present specification shows node.

Figure 10 is the flow chart according to instantiation procedure used by present specification shows node.

Figure 11 is the flow chart according to instantiation procedure used by present specification shows node.

Figure 12 is the flow chart according to instantiation procedure used by present specification shows node.

Figure 13 A are the flow charts according to instantiation procedure used by present specification shows node.

Figure 13 B are the flow charts according to instantiation procedure used by present specification shows node.

Figure 14 is the flow chart according to instantiation procedure used by present specification shows node.

Figure 15 is the flow chart according to instantiation procedure used by present specification shows node.

Figure 16 A are the flow charts according to instantiation procedure used by present specification shows node.

Figure 16 B are the flow charts according to instantiation procedure used by present specification shows node.

Figure 17 is according to present specification shows the block diagrams of some components for the example endpoint that can be used.

Figure 18 is suitable for realizing the block diagram of the computer system of the embodiment of system described here.

Figure 19 applies to realize the block diagram of the network equipment of the embodiment of system as described herein.

Specific embodiment

General introduction

There has been described explicitly replicated for performing position index (bit indexed explicit replication, BIER various system and method).For example, a kind of method, which is included at node, receives grouping.The grouping includes bit string (bit string).The node selects forwarding information based on flow valuve associated with the grouping (flow value).Forwarding information includes Forward bitmask.Then, which forwards grouping based on bit string and forwarding information.

Multicast

Multi-case data is grouped and (generally includes the data point of the information (for example, Multicast group address) of mark multicast group by multicast Group) from source multiple receiving terminals are distributed to, the burden without excessively aggravating source.Term " receiving terminal " used herein represents to subscribe to more Broadcast the host (for example, computer equipment or application) of group.It is not to be replicated multi-case data grouping by source and be grouped the multi-case data Copy be sent to each receiving terminal, but the single copy of multi-case data grouping is sent by source, and the routing that multicast enables Device (abbreviated here as node) replicates the grouping at (one or more) point to diverge towards the path of each receiving terminal.Multicast road By agreement by enabling multicast transmission (that is, one being located in the grouping of the duplication multi-case data close to the purpose that multi-case data is grouped To multi-link and multipair multi-link), it avoids and is connected using multiple unicasts of similary purposes.Which save network bandwidth and Improve handling capacity.

Fig. 1 is the simplified block diagram for the network 100 for performing multicast data transmission.Multicast enables node 110,120,130 and 140 It is coupled by network link 150,160 and 170.Multicast enables node 110 and is also coupled to source 111 and receiving terminal (receiver)112；Multicast enables node 120 and is coupled to receiving terminal 121；Multicast enables node 130 and is coupled to receiving terminal 131 and receiving terminal 132；And multicast enables node 140 and is coupled to receiving terminal 141.Multicast enables node and source and/or reception It can also be directly indirect (for example, by the L2 network equipments or another node) that such coupling, which can be, between end.

For the example, source 111 is host, be configured as to including as receiving terminal host 112,121,131, 132 and 141 multicast group sends multi-case data grouping.Source 111 enables node 110 and send to multicast includes having common multicast group The Multicast Flows of one or more multi-case datas grouping of address (as shown in the arrow from 111 to 110).Multicast enables node 110 Including multicast forwarding, multicast enables node 110 using the table to determine where to forwarding multicast associated with the Multicast Flows Packet.The multicast that multicast forwarding is connected to multicast distribution tree (MDT) including identifying enables node 110 to multicast group One or more receiving terminals (for example, have sent add in message host, as described above) each interface information.Then, Multicast enables the multi-case data that node 110 is replicated in Multicast Flows and is grouped, and the multi-case data of duplication is grouped from identified Interface is sent to receiving terminal 112, multicast enables node 120 and multicast enables node 130.

Multicast enables node 120 and 130 using message (for example, Protocol Independent Multicast (PIM) adds in message) is added in accuse Knowing node 110, they are coupled to one or more receiving terminals.In response to receiving addition message, multicast enables node 110 more Its new multicast forwarding is grouped which interface should be forwarded to identify multi-case data.Multi-case data grouping can be 110 by node According to being replicated, so that other multicasts on the receiving terminal of multicast group (for example, receiving terminal 131 and 132) and MDT make Energy node (for example, multicast enables node 140) provides multi-case data grouping.In this way, the Multicast Flows from source 111 Multiple receiving terminals can be transferred to by multicast network.

As can be seen that commonly used in being often to set up MDT and update the process of multicast forwarding to result in net in multicast Substantial amounts of status information in network.Particularly, the multicast forwarding for node maintenance being enabled by each multicast can become quite big.It safeguards Such multicast forwarding shows the limitation of network scalability.

Position index explicitly replicates

As described below, some technologies be used to reception client information being attached to grouping in the form of position (bit), and be based on connecing Receiving end information is grouped to forward.It is " Wu Zhuantai more this considerably reduce the amount of state information being stored at node, therefore also referred to as It broadcasts ".More formally, term position index explicitly replicates (BIER) and be used to describe these technologies.As showing as the term implies, Position position (bit position) is used as the index into forwarding table, and is grouped and is only copied to specified node.BIER makes It must can be incited somebody to action in the case of without using the multicast distribution tree at each node between source and receiving terminal and every group of status information Grouping is forwarded to multiple receiving terminals from source.

Fig. 2 shows example network 200.Network 200 enables node 206-218 including BIER.BIER enable node by with It is set to using BIER to forward grouping, and sometimes referred to as position forwarding router (BFR).BIER enables node 206-218 shapes Into provider network or provide the quotient field.Such provider network can be interconnected net service provider and be used for user's transmission point Group.The domain includes transmission node 208 and 210 and provider's boundary node 206,214,216 and 218.Provider's boundary node It is coupled to user's boundary node 211,213,215 and 217.Host 201,203,205 and 207 is coupled to user's boundary node Computing device.

Each BIER, which enables node 206-218, has the interface identified as shown.For example, BIER enables node 208 With three interfaces for being respectively designated as 1-3.Each BIER enables node and is allocated unique identifier or routable address, is claimed For router identifier (RID).RID can for example be implemented as Internet protocol (IP) address, prefix or loopback address (loopback address).Each BIER enables every other BIER of the node into network 200 and enables node notice or flood The general routable address.Each BIER enables node to be made using the routable address being advertised to establish the BIER in network 200 The unicast topologies of energy node.In one embodiment, router identifier, which can be mathematically converted into, is assigned to BIER and makes It can the set identifier (SI) of node and position position (BP).Length of the conversion based on used bit string.For example, in order to by road Set identifier and position position are converted to by device identifier " N ", set identifier is the integer portion of the business of (N-1)/bit string length Point.Position position is ((N-1) modulo BitStringLength (mould of fetch bit string length))+1.In the above examples, if N Equal to 257 and bit string length is 256, then SI is 1 and BP is 1.BIER networks 200, which further include, is configured as operation as multicast The node of recording controller (MDC) 230.MDC performs configuration and management role, as described below.

BIER enables the position forwarding entry router (BFIR) that node 206 is configured as multi-case data grouping.BIER is enabled Node 206 is coupled to source 201 by user's boundary node 211.By BFIR, (BIER makes for multi-case data grouping from source 201 Energy node 206) enter BIER networks.Each BIER enables node 214,216 and 218 and is configured as position forwarding egress router (BFER).BFER can be connected to host (for example, receiving terminal) or other networks (directly or by user's border router).BFER It is that last BIER on the path between source and receiving terminal enables node.BFER can be directly or indirectly (for example, by non- BIER enables CE nodes) it is coupled to provider border (PE) node of receiving terminal.

Distribute the position position in bit string

Each BFER in BIER networks divides co-ordination positions (BP) from the array of the set of position or position.The array of position (array of bit) can be carried in grouping or other internet messages.Position array be also stored in forwarding table and/or In routing table.For clarity, term used herein be " bit string " (when position array in a packet when) and " bitmask " (when When the array of position is stored in table).Furthermore, it is noted that BFIR can be used as BFER, vice versa.BFIR is also allocated position position.

Bit string (or bitmask) can have regular length or variable-length.It can quilt for the length of the bit string in BIER networks Static configuration or dynamically distributes, and be distributed in BIER networks.In one embodiment, the length of bit string is in 256 and 1024 Between position, but shorter or longer bit string can also be used.In one embodiment, the maximum length of bit string value is by BIER networks In BIER enable the hardware of node or software limitation determines.In one embodiment, the different BIER in BIER networks make For its, each bit string uses different length to energy node.For example, a BIER enable node can be long with the maximum bit string of 128 Degree, and another BIER enables node can have the maximum bit string length of 256.Bit string is a type of multitransmission entry, Each position position in plurality of position position is the element that can be used to represent independent node or interface.With other types The other types multitransmission entry of element can be used.

Position position (BP) is statically or dynamically assigned to each BFER.Each BFER should have from at least one of bit string Unique position position.In one embodiment, BP can be distributed to BFER by central office (for example, multicast domain controller).At one In embodiment, multiple BP are distributed to single BFER by multicast domain controller, for example, being connect to one or more of BFER is included in The unique BP of each interface assignment in mouthful.Other mechanism for distributing BP can be also implemented, for example, making from BIER is distributed to BP can be derived in the router identifier of node, the wherein derivation uses mapping algorithm.In some embodiments, in bit string Position position is assigned to single BFER.In other embodiments, single BP can be assigned to more than one BFER.When multiple When BFER is allocated same BP, the ownership that the BP can be exercised in given time in the plurality of BFER, and ownership It can be shifted between the plurality of BFER.It is more that the ownership of the BP can be transferred to this any one of due to several Another in a BFER, for example, in response to the transfer of the failure of node or link failure or if in the plurality of BFER one It is a otherwise to become unavailable, in response to changing network condition, the considerations of being shared due to timesharing etc..One BP is distributed Contribute to the operation similar to Anycast (anycast) to multiple BFER, wherein grouping is forwarded to one in one group of receiving terminal Each receiving terminal in receiving terminal, wherein this group of receiving terminal uses common address.

BIER only in BIER networks enables boundary node (for example, BFER and BFIR) and is allocated BP.In the network Every other BIER enables node (for example, transmission node) and BP is not required to participate in BIER.This helps to reduce distributes in network Position number.As shown in the example of figure 2, network 200 uses the bit string of four bit lengths.In network 200 four BFER (including BFIR nodes 206) in each be allocated BP：Node 206 is allocated BP { 1000 }；Node 214 is allocated BP { 0001 }；Section Point 216 is allocated BP { 0100 }；Node 218 is allocated BP { 0010 }.

Set

The size for the bit string that the quantity for the BFER that can be addressed and (distribute BP) is included in multi-case data grouping is limited. If bit string is four bit lengths, the quantity for the BFER that can be addressed is four.The concept of set allows for be allocated the BFER of BP Quantity increase.Set identifier (SI) is, for example, the number between 0 and 255.SI allows BP to be only in the context of set One.For example, each BP can be reused in each set.In the implementation gathered with 256 and bit string length is 256 In example, 65536 (256x256) a BFER can be supported.In one embodiment, the BIER in BIER networks enables node for every A SI generates respective forwarding information.If for example, made in BIER networks using two different set identifiers, BIER Energy node generates two position index forwarding tables (BIFT), each corresponds to each SI.In response to receiving the multicast number with SI According to grouping, BIER enables node using SI to select to carry out retransmitting multi-casting packet using which forwarding information (for example, BIFT).

Signaling

When receiving terminal (for example, host, such as the host 203 of Fig. 2) wishes to add in multicast group, the receiving terminal is (straight to it Connecing or indirectly) BFER that is coupled to sends information about firms (for example, using Internet Group Management Protocol (IGMP)).Information about firms mark Know host and wish the multicast group added in, and optionally identify source associated with the multicast group.In the figure 2 example, host 203 can send IGMP message to CE nodes 213, and then the IGMP message can be transmitted to BIER and enable node by CE nodes 213 214.Wish to add in the message of multicast group in response to receiving instruction receiving terminal, BFER sends it in the message being identified The signal of the interest of multicast group.In one embodiment, this includes：Arbitrary BFIRs of the BFER into network is sent to controller Member's message, instruction BFER is for the interest of the multicast group.In one embodiment, member's message includes the BP of BFER.Alternatively, The information (for example, information in the BIRT of BFIR) that BFIR uses the address for the BFER for initiating member's message and passes through IGP advertisement Lookup is performed, to determine BP associated with the BFER of initiation member message.In one embodiment, BFER uses border net Agreement (BGP) is closed to send member's message.

The borderline some or all of BIER that member's message can be only sent to BIER networks by BFER enable node (BFIR and BFER) or signaling message can be flooded to all nodes in network.If for example, network be used it is specific Source multicast (SSM), then BFER knows the source (for example, according to the IGMP message received from receiving terminal) of multicast group, and can search Signaling message is sent to the path of the specific BFIR and only to the BFIR.If the multicast type that SSM is not used, BFER can flood signaling message to all candidate BFIR.Only BIER enables boundary node and parses the message to determine group and BP Information, every other node can drop the message.The receiving terminal for adding in multicast group and being quit the subscription of from multicast group will not be caused by core BIER enables the disturbance of the status information (for example, position index forwarding table) of node maintenance or need in the status information any changes Become, unlike conventional multicast.On the contrary, addition or unsubscribe message are associated with given multicast group to update to BFIR signallings Bit string.This includes only BFIR more new state informations (for example, update group membership's table associated with the group) rather than core section Point.This indicates significantly improving on conventional multicast, in conventional multicast, multicast distribution tree be based on add in and unsubscribe message and It is established and removes throughout network.

BFIR (for example, the BIER of Fig. 2 enables node 206) maintenances include each multicast that the BFIR receives member's message The status information of the entry of group.In one embodiment, BFIR by state-maintenance in group membership's table (GMT), such as the 224 of Fig. 2 Shown in.In one embodiment, each entry in GMT includes：Identify multicast group information (for example, multicast group name and/ Or the address in the source of multicast group), it is interested (for example, passing through member in the multicast group identified in group field corresponding to expressing Message) BFER BP lists and identity expression all BFERs interested to the multicast group (for example, by correspondence Position be equipped in the position position of interested each BFER gather in expressing to the multicast group) bit string.In response to being connect from BFER It receives and indicates the BFER to the interested member's message of multicast group, which, which is set in the bit string corresponding to the multicast group, corresponds to The position of the BP of BFER.When the BFER is no longer grouped interested to the multi-case data for receiving the multicast group, which sends out to BFIR The number of delivering letters (for example, using unsubscribe message), and BFIR removes the corresponding positions in bit string.

BIER networks forward multi-case data grouping based on bit string in BIER networks.BFIR is by bit string and multi-case data Grouping is transferred in BIER networks.In the presence of many different technologies that can be used for transmission bit string.It is more that this illustrates that bit string is encapsulated by finger In multicast data grouping.The term, which not only covers, is merged into BM in multi-case data grouping (for example, as head or payload Information), it also covers to add or be pre-applied to multi-case data grouping by some or all of bit strings.

Fig. 3 A are the flow charts for showing aforesaid operations.In one embodiment, this method by BFER (for example, Fig. 2 BFER 214) it performs.BIER information is asked in 302, BFER, for example, position position and set identifier.In one embodiment In, request BIER information includes BFER and sends message to multicast domain controller (for example, multicast domain controller 230 of Fig. 2).One In a embodiment, network has been added in or in response to some other conditions in response to detection BFER, BIER information is automatically presented with the video To BFER.Administrator can use BP and set identifier manual configuration BFER.

BIER information is received in 304, BFER, the BIER information is not as management configuration as a result, being exactly for example to respond It is included in the request for BIER information in the message from MDC.306, BIER information is received in response to BFER, Other some or all of nodes of BFER into BIER networks notice its BIER information and its router identifier.In an implementation In example, BFER notices its BP and SI by Interior Gateway Protocol (IGP).For example, Intermediate System-to-Intermediate System (ISIS) and/ Or ospf (OSPF) can be modified to auxiliary and distribute this by BIER Web vector graphics link state update Information.Other flooding mechanisms can also be used to distribute information.All BIER in BIER networks enable node BFER its router identifier) is also flooded, is used to set up network topology and unicast forwarding table.In one embodiment, BIER enables node and also notices additional information, for example, BIER enables the bit string size that node is configured such that.With conventional multicast In the status information based on every group maintenance compare, it is relative small amount of attached that such BIER information is added to noticed information Add information.

Fig. 3 B show using covering signaling (overlay signaling) to distribute information about firms in BIER networks Exemplary method.In one embodiment, the method for Fig. 3 B is performed by BFER (for example, the BIER of Fig. 2 enables node 214).

In 322, BFER membership request is received from host (for example, host 203 of Fig. 2).Membership request alternately through with Family boundary node (for example, user's boundary node 213 of Fig. 2) relays.In one embodiment, membership request disappears including IGMP Breath.Membership request includes the information of mark multicast group and identifies the host wishing to add in (for example, subscribe to) that the multicast group is still Leave the information of the multicast group (for example, being quit the subscription of from the multicast group).In response to receiving membership request, BFER update instruction multicast groups In host member forwarding information.For example, if membership request indicates that host wishes to add in multicast group G1, BFER update Forwarding entry so that the arbitrary multi-case data grouping for being received by the BFER and being addressed to multicast group G1 will be transmitted to this by the BFER Host.

Member's message is generated in 324, BFER.Member's message is demonstrated by interest of the BFER to multicast group.In one embodiment In, member's message is realized using BGP.Member's message carries the information of mark multicast group and identifies the information (example of BFER Such as, the set identifier of BFER and position position).

Member's message is sent in 326, BFER.In one embodiment, member's message is sent to be related to multicast domain controller (for example, MDC 230 of Fig. 2) forwards member's message.Then, some or all of border router (examples of the MDC into BIER domains Such as, BFER and BFIR) send member's message.

Position index is route and forwarding table

Each BIER in BIER networks enables node and enables BP and the router mark that node is noticed using other BIER Symbol is known to generate one or more position index routing tables (BIRT) and position index forwarding table (BIFT).BIER enables node and uses this A little tables carry out retransmitting multi-casting packet.As shown in the example BIRT 262 of Fig. 2, position index routing table is to store BP to router mark Know the table of the mapping (for example, being learnt by Interior Gateway Protocol (IGP)) of symbol.Each BIER enables node and receives BP to road By the mapping of device identifier, and store it in BIRT.Using router identifier, BIER enables node in unicast routing table It is middle to perform recursive lookup to identify from the shortest path that the BIER enables that node enables node towards BIER associated with BP The next-hop BIER being directly connected to enable node (referred to herein as neighbours (NBR)).In one embodiment, NBR is towards logical Accuse the next-hop on the shortest path (SPT) of the BFER of BP.In one embodiment, BIRT includes each mono- entry of BP.Such as It is lower further to inquire into, when to given BFER there are multiple equivalence path when, BIRT is more including BP associated with the BFER A entry.

Each BIER enables node and its BIRT is converted to one or more position index forwarding tables (BIFT).Fig. 2 is shown The example BIFT 264 that node B 208 generates is enabled by BIER.In one embodiment, generation BIFT is related to passes through neighbours first BIRT is ranked up.For having the entry of common NBR in BIRT, the bitmasks of these entries by or (OR) logic by simultaneously Together, so as to create bitmask, it is the combination of the BP from these entries.This is referred to as forwarding bitmask herein (FBM) or only it is known as bitmask (BM).Each instruction being arranged in FBM passes through neighbour associated with the FBM in BIFT Occupy reachable BFER.Multi-case data grouping is enabled node by BIER and is forwarded to using BIFT.For example, according to BIFT 264, such as The multi-case data grouping that fruit has the bit string of the BP gathered with { 0001 } reaches node 208, then multi-case data grouping should be turned Issue NBR C (BIER in the example of Fig. 2 enables node 210).If the multi-case data grouping of the BP with { 1000 } set Reach node 208, then multi-case data grouping should be forwarded to NBR A (BIER in the example of Fig. 2 enables node 206).Such as Fruit have { 1001 } bit string multi-case data grouping reach node 208, then the multi-case data grouping should be forwarded to NBR A and Both NBR C.

Packets forwarding

After bit string is encapsulated into multi-case data grouping, BFIR is turned multi-case data grouping using the BFTS of the BFIR It issues one or more BIER and enables node.The BIER of reception multi-case data grouping enables node and uses in multi-case data grouping Bit string and BIER enable the BFT of node oneself to determine whether to forward the packet multi-case data to one in its neighbour or more It is a, and if so, it is transmitted to which or which neighbours.For this purpose, BIER enable bit string during multi-case data is grouped by node with The FBM entries that BIER is enabled in the BFT of node are compared.In one embodiment, BIER enables node in multi-case data point The bit string and BIER of group perform logical AND operation between enabling the FBM in the BFT of node.As pointed out, at one In embodiment, the BFT that BIER enables node includes the entry that the BIER enables each neighbours of node, and each entry includes FBM domains, the domain indicate which BFER is reachable along shortest path by the neighbours identified in the entry.If for given neighbour Occupy, with result be true, then BIER, which enables node and forwards the packet multi-case data, gives the neighbours.As a result it is that true instruction BIER is enabled The FBM of neighbours is given in the BIFT of node has the position for being set to 1, and the corresponding positions in the bit string of multi-case data grouping It is arranged to 1.The position being set in the bit string of multi-case data grouping indicates which BFER expresses the interest to multicast group, and BIER enables the position being set in the BIFT entries of node and indicates that the BFER for expressing interest is by the neighbours indicated in entry Reachable.BIER enables node and forwards the packet the multi-case data comprising bit string to be made to the bit string in multi-case data grouping with BIER The step-by-step between FBM in the BIFT of energy node is with operating as really all neighbours.

In the figure 2 example, BIER enables node 214 (BFER) and enables node 206 (BFIR) transmission signal table to BIER It is interested for receiving grouping associated with given multicast group or stream that bright BIER enables node 214.BIER enables 216 He of node 218 equally enable node 206 (BFIR) transmission signal to BIER shows that BIER enables node 216 and 218 pairs of same multicast group senses Interest.The dotted line of signaling as shown in Figure 2 represents.BIER enable node 206 update the multicast group group membership's table 224 (if Be not present, then create one) in entry, and carried out by pair enabling the corresponding position in node 214,216 and 218 with BIER It sets to update the bit string in the entry.Bit string corresponding to the multicast group is { 0111 }.

BIER enable node 206 be configured as receive be addressed to the multicast group or stream (for example, being saved from source 201 via CE The multi-case data grouping of point 211).BIER enable node 206 using be included in multi-case data grouping in Multicast group address and/or Source address accesses its GMT and selects associated with multicast group bit string.Selection is corresponding to the bit string of the multicast group from GMT Afterwards, BIER enables node 206 and the bit string of the multicast group is encapsulated into multi-case data grouping, and identify the grouping will be by The neighbours (for example, using its BFT) being transmitted to.In one embodiment, this is included in bit string and BIER enables node 206 It performs and operates between each entry in BIFT.In this example, an entry, and the entry pair are only existed in BIFT Node 208 should be enabled in BIER.This means enable node 206 to the most short of all three BFER in network 200 from BIER Path all enables node 208 by BIER.Because for NBR B (BIER enables node 208), with result be it is true, therefore BIER enables node 206 and forwards the packet multi-case data enables node 208 to BIER.BIER enables node 206 and also changes its turn Bit string in the multi-case data grouping of hair, as described below.

In response to receiving multi-case data grouping, BIER enables bit string of the node 208 in multi-case data grouping It performs and operates between each entry in ({ 0111 }) and its BIFT (being shown in 264).Due to the result of NBR C be it is true, BIER enables node 208 and forwards the packet multi-case data enables node 210 to BIER.BIER enables node 208 and also passes through removing Corresponding to the inaccessible BFER's of shortest path that node is enabled via the BIER being just forwarded to by multi-case data grouping Position come change its forwarding multi-case data grouping in bit string.In this example, because node E is unreachable (from section via node C The shortest path of point B to node E is without C), so node B, which removes node B and is transmitted in the bit string of node C, corresponds to node E Position.Therefore, the multi-case data with bit string { 0011 } is forwarded the packet and gives node C by node B.The result of NBR E be also it is true, because This BIER enables the duplication multi-case data grouping of node 208 and forwards the packet the multi-case data enables node 216, BIER to BIER Enabled node 216 is BFER.Node B, which updates bit string and forwards the packet the multi-case data with bit string { 0110 }, gives node E.

In response to receiving multi-case data grouping, BIER enables bit string of the node 210 in multi-case data grouping It performs and operates between each entry in ({ 0011 }) and its BIFT, and multi-case data is forwarded the packet and enables node to BIER 214 (it is BFER) and BIER enable node 218.BIER enables node 216 and also forwards the packet the multi-case data to be made to BIER It can node 218.This causes BIER to enable the duplicate copies that node 218 receives multi-case data grouping.Such case is not It is desired, and be to be enabled from BIER caused by node 208 enables node 218 there are two paths of equal value to BIER 's.That is, such as show, it is reachable via the single-hop path of node C or node E that node F, which is used from node B,.It is more that this is referred to as equivalence Path (ECMP), and the technology for solving such case is described below.

ECMP

Forwarding grouping includes node and determines which neighbour the grouping should be sent to will pass through shortest path to the grouping Destination advance.Occasionally there are multiple neighbours that grouping can be forwarded.For example, from the node to destination, there may be a plurality of Shortest path or a plurality of equative route.The expense in path can be on the type of the link on hop count, path and/or node (and road The operating parameter of link and/or node on footpath, such as bandwidth and processing capacity) etc. assessed.Node by using Such as it dijkstra's algorithm and is calculated by the routing iinformation of IGP distributions to perform shortest path to generate route topological.

When the destination from node to grouping is there are during a plurality of equative route, the node should along one in these paths and Only one is grouped to forward, such as one into the neighbours in respective paths and only one forwarding grouping.Along more than one road Footpath (for example, to more than one nodes neighbors) forwarding grouping causes undesired repetition.It repeats to represent both to replicating and forwarding point The sending node of multiple copies of group causes to bear, also to receiving, buffering and handling the reception sections of (for example, discarding) multiple groupings Point (one of grouping is just enough) causes to bear.In addition, grouping is copied to the transmission medium usually with fixed-bandwidth capacity (for example, network link) causes to bear.It may be complex task that definite grouping should be forwarded on which paths.Logic is relevant Grouping (for example, grouping of the part as same Multicast Flows) should pass through same neighbourhood.Otherwise, if the relevant grouping quilt of logic Mulitpath is distributed to, then the additional attention of the sequence on these groupings is faced in destination.It pays close attention to when handling ECMP One problem is load balance.It is desirable to that every ECMP path is all used rather than over-burden in some paths, and other It is under utilized.

In typical multicast deployments, it is grouped and is forwarded to using multicast distribution tree.Node can perform ECMP calculating conducts and set A part for vertical multicast distribution tree.For example, the receiving terminal which upstream (towards source) neighbours should be chosen as adding in message can be used ECMP technologies determine.But ECMP is not used for retransmitting multi-casting packet to downstream node in typical multicast deployments Forwarding determines.

In general, ECMP jumps (hop-by-hop) come what is made decision based on a jumper connection one.That is, each node of grouping is received It determines or assesses some ECMP standards associated with the grouping, and correspondingly select path.ECMP is performed at each node It determines that negative influence can be generated to forwarding performance.So being done in the environment of BIER may include that node determines that there are a plurality of ECMP roads Footpath and given grouping should be sent to through the reachable node in ECMP paths.It is multiple to perform these calculating in the dataplane Miscellaneous.As an alternative, these operations are performed in control plane forwarding table with reference to used in setting BIER nodes.Once ECMP Path is identified, and the forwarding information of node is correspondingly configured for every ECMP path, then the node can be simple Ground selection uses which forwarding information (for example, forwarding the grouping on which ECMP paths).In one embodiment, node makes It is made choice with including information in a packet between ECMP paths.For example, grouping can include being associated based on grouping Multicast Flows value or field.Based on the value, node can select ECMP paths and by the grouping from same Multicast Flows along list A ECMP paths are forwarded to.

The ECMP paths of different neighbours are mainly concerned with herein.Another type of ECMP paths are related to the more of same neighbourhood Paths (for example, parallel interface).In the case of mulitpath to same neighbourhood, for the bit string and pin in every ECMP path It is identical to the bit string of every path candidate.On the other hand, if ECMP paths are to different neighbours, each ECMP paths Bit string is different for each neighbours.

Fig. 4 is the simplified block diagram for the specific components for showing example network 400.BIER enable node 410 to 416 be by with It is set to the BFR of transmission node.It is the BFR set as BFER that BIER, which enables node 420 to 428, wherein the position position distributed As shown in the figure.BIER enables node 406 as that can be transmission node or the BFR of BFIR.In one embodiment, which enables Node (for example, passing through one or more user's boundary node (not shown)) is coupled directly or indirectly to one or more masters Machine (not shown).Optionally, network 400 also includes multi-case data controller (not shown).

Network 400 includes many ECMP paths.For example, nodes X can pass through the shortest path by node C or node D Reach node L.The expense in path is equivalent.Nodes X can reach node P by any one in node A, B, C or D.Make To receive the response of multi-case data grouping, nodes X determines which neighbor node multi-case data grouping should be forwarded to.As Example, if multi-case data is grouped with node L as a purpose (for example, what position corresponding with BP { 10000 } was grouped in multi-case data Bit string is set), nodes X determines to forward the packet to node C or node D.

Fig. 5 A are by the example of the position index routing table (BIRT) 502 of BFR (for example, node 406 in Fig. 4) generations. BIRT 502 includes three row.First row includes to determine each that BIER networks (for example, network 400 of Fig. 4) include The position position of BFER and the information of (optional) set identifier.In one embodiment, the row are simultaneously comprising BFR-ID or void Intend position position.Virtual bit position can be implemented as the unique integral in the border router of BIER networks.Secondary series include pair Routable address for each in BFER, such as loopback or BFR prefixes.3rd row are included for the neighbours or multiple neighbours One or more entries, BFER corresponding with the BFR prefixes can be reached by the neighbours from the node along shortest path.As Example, the first row of BIRT502 show that there are two ECMP paths, node L from the nodes X in Fig. 4 to node L to have position Position { 10000 }.First paths pass through neighbours D by neighbours C, the second paths.Table 502 is also shown with position position { 00001 } BFER P, the BFER P can be reached from nodes X by neighbours A, B, C and D.Therefore, BIRT 502 is shown from section There are four ECMP paths by point X to node B.The process of more detail discussion generation BIRT in Fig. 10.

Fig. 5 B are the example position index forwarding tables (BIFT) 504 for example generated by the node 406 of Fig. 4.BIFT 504 is profit It is generated with the information in the BIRT 502 of Fig. 5 A.As shown in the figure, BIFT 504 includes to forward the row of bitmask (FBM). BIFT 504 also includes the row for neighbours.BIFT 504 show in the multiple positions set in FBM each can pass through Corresponding neighbours reach.As an example, considering the first entry in BIFT 504, BEFR corresponding with position position 1,2 and 3 passes through Neighbours A is accessibility.In Fig. 4, node P, M and N are accessibility by node A for reflection.Life is discussed in fig. 11 Into the subsidiary details of BIFT.

Fig. 6 is an example of the ECMP mapping tables 602 of generation, as an example, being generated by the node 406 of Fig. 4.Consider The BIFT 504 of Fig. 5 B, position position 1 in each entry (for example, for node A, node B, node C and node D) are set. Consider that wherein nodes X (the 406 of Fig. 4) receives the example that the multi-case data with bit string { 11111 } is grouped.As receiving this The response of multi-case data grouping, nodes X is by the bit string compared with the corresponding FBM of neighbours A.Since result is true ({ 11111 } AND { 00111 } is equal to { 00111 }), duplicate which is grouped by nodes X, having bit string { 00111 } is forwarded to neighbour Occupy A.Then, nodes X by bit string compared with the FBM of node B.Since result is true, which is grouped by nodes X Another duplicate is forwarded to node B, which has bit string { 01101 }, i.e. the FBM with bit string { 11111 } operate with (AND) Result.This process is also continued to node C and node D, nodes X forwards the duplicate that the multi-case data is grouped to these nodes Each.BP is set in multiple entries of BIFT and represents ECMP problems.Each from node A to D finally forwards this more The duplicate of multicast data grouping is to such as node P.These copies of multi-case data grouping are not needed.

Avoiding a kind of method that copy is not required that multi-case data is grouped is：In each FBM multicasts to entrance more afterwards Position in the bit string of packet is shielded.In other words, entrance grouping bit string compared with next FBM before, Those positions being set in the duplicate of outgoing multi-case data grouping can be cleared.It can be used to avoid in this technology While the copy of unwanted grouping, load balance is sacrificed.In the examples described above, it is being sent to the multi-case data of node A Set has been carried out to three relatively low positions in the duplicate of grouping.If nodes X is in the bit string that will enter grouping and the FBM of node B Those positions of the bit string into grouping are zeroed out before being compared, then outgoing bit string will not indicate that the grouping should When being sent to node P.In other words, nodes X and will be forwarded by { 11000 } compared with the entry of node B to node B The duplicate with bit string { 01000 } of multi-case data grouping.Multi-case data grouping with bit string { 01000 } will be only forwarded to Node N.Therefore, all groupings to node P will pass through node A.This causes load imbalance, and endangers network performance.

The another method for avoiding due to ECMP paths and reducing performance is the multiple BIFT of generation, wherein for each BIFT, Each position position is set at most one and only one FBM.In response to receiving multi-case data grouping, BFR choosings at BFR It selects one of BIFT and is forwarded the packet the multi-case data using selected BIFT.In one embodiment, the selection is based on The flow valuve (flow value) carried in each multi-case data grouping.BFR generations such as Fig. 7 A of the nodes X of such as Fig. 4 etc, The BIFT shown in 7B, 7C and 7D.In one embodiment, generation BIFT is related to generation and using ECMP mapping tables (such as Fig. 6 Shown ECMP mapping tables 602).

In one embodiment, the maximum number that ECMP mapping tables 602 are related to ECMP paths in definite BFR is generated.To every A position, BFR make the set of this position to how many FBM in BIFT.In the example of the BIFT 504 of Fig. 5 B, with position position 1 corresponding maximum number is 4.In other words, position position 1 is set to be located in each of 4 FBM shown in Fig. 5 B.The BFR is generated Include the row or the table of entry for each position.This is illustrated in the first row of ECMP mapping tables 602.BFR is also created For the row in every ECMP path.Since the maximum number in ECMP paths in BIFT is 4, nodes X generation is with 4 additional columns ECMP mapping tables 602.BFR (nodes X in this example) and then information is distributed, the corresponding position position of the message identification is arranging In the neighbours that are set.Can for example it be come by using Xun Huan (round-robin) algorithm or other a certain algorithms to the information It is distributed.

To each position, this position is at most set once in each given table.This position is set more The neighbours that should be forwarded to of multicast data grouping be input into in the corresponding row in this position.In 504 bit positions of BIFT 1 is set for 4 neighbours.Each neighbours are come across in the respective column of ECMP mapping tables 602.Neighbours A is come across in first row, Neighbours B is come across in secondary series, and neighbours C is come across in the 3rd row, and neighbours D is come across in the 4th row.This is reflected in the of table 602 In a line.This means when to each column-generation BIFT, BIFT corresponding with first row will have for neighbours A and only for The position position 1 that neighbours A is set.If the BIFT is selected for retransmitting multi-casting packet, multi-case data grouping will pass through Neighbours A and node P (corresponding to BP 1) is only forwarded to by neighbours A.BIFT corresponding with secondary series will have for neighbours B And only for the position position 1 that neighbours B is set.If the BIFT is selected for retransmitting multi-casting packet, the multi-case data point Group will be forwarded to node P (corresponding to BP 1) by node B and only by node B

In forwarding table 504 in place, position position 2 is respectively set once for neighbours A and neighbours D.This is reflected in ECMP mappings In the first two columns of second row of table 602.Due to presence and the ECMP paths of position position 2 relevant two, and deposited in the mapping table In 4 row, each ECMP neighbours are repeated twice.Position position 3 is respectively set once for node A and node B.It is similar with 2, these It is mapped in the third line of table 602 and is repeated.Position position 4 is only that neighbours B is set.Position position 5 is set for neighbours C and D. It is wherein directed in the embodiment not divided exactly to the number in the ECMP paths of position location by the maximum path number of the BIFT, performs The asymmetric distribution of neighbor information in ECMP mapping tables.

Then mapping table 602 is converted to 4 separated position forwarding tables by BFR.As shown in Figure 7A, position forwarding table 702 is right It should be arranged in the table 1 of mapping table 602.As shown in position forwarding table 702, it is set in FBM middle positions 1,2 and 3 corresponding with neighbours A, FBM middle positions 4 corresponding with neighbours B are set, and are set in FBM middle positions 5 corresponding with neighbours C.It, should in BIFT 702 Each in the position of five positions is only set once.As an example, position position 1 is only set in FBM corresponding with A.Cause This, multi-case data that is being forwarded using BIFT702 and being set with BP 1 is grouped is forwarded to node merely through neighbours A P.Fig. 7 B are shown arranges corresponding BIFT 704 with the table of mapping table 602 2.Fig. 7 C show arranged to the table of mapping table 602 3 it is corresponding BIFT 706.Fig. 7 D are shown arranges corresponding BIFT 708 with the table of mapping table 602 4.

Fig. 8 is the example BIFT generated by BFR (for example, nodes X (406) in Fig. 4).Fig. 8 shows optional BIFT 802.It is not that the bit string of entrance compares with each FBM entries in BIFT, optional forwarding mechanism is considered in the bit string Each (travels through the bit string rather than travels through the BIFT).One advantage of this mode is, by the FBM in bit string and the BIFT The maximum number being compared is restricted to the length of the bit string rather than the opposite number for being restricted to neighbours, the number may It is very big.In the example present, using only a forwarding table, and to each establishment for the corresponding item in each ECMP paths Mesh.For each the position position 1 being set being directed in 4 neighbours, 4 FBM entries are created in table.For being directed to 2 The position position 2 that neighbours and BIFT 504 are set creates 2 FBM entries.It is retouched no matter using for Fig. 6,7A, 7B, 7C and 7D The multilist mechanism stated or (or multiple in multiple tables using for the more entry methods of single BIFT described in Fig. 8, all employing Entry) between the selection mechanism that makes choice.As an example, flow valuve can be included in multi-case data grouping.To given stream For each packet, which is consistent (for example, identical value).Based on the calculating to flow valuve, BIFT (or items are selected Mesh).It ensure that the multi-case data grouping of phase cocurrent flow is forwarded to identical neighbours and cocurrent flow can not be distributed to ECMP paths In.Fig. 9 is provided into 16B on generation forwarding information, and the supplement for selecting forwarding information and retransmitting multi-casting packet is thin Section.

Fig. 9 is the flow chart for showing the instantiation procedure used according to this specification by node.Fig. 9 shows to generate The method of forwarding information.In one embodiment, turned by position forwarding router (BFR) generation of the BFR 406 of such as Fig. 4 etc Photos and sending messages.BFR generates BIER forwarding informations, it is then determined that with the presence or absence of ECMP paths.If in the presence of BFR generations avoid for example dividing The forwarding information of the ECMP problems of group copy.

In 902, BFR generations BIRT.In one embodiment, this is related to for example receives what is be advertised using IGP BIER information.It discusses in Fig. 10 and the generation relevant subsidiary details of BIRT.Using the BIRT generated in 902, BFR is 904 Middle generation BIFT.In one embodiment, generation BIFT, which is related to, determines which BFER is reachable by which neighbour, and generates and neighbour Occupy corresponding forwarding bitmask.The subsidiary details of generation BIFT are discussed in fig. 11.

In 906, BFT determines the maximum number in ECMP paths, as indicated in the BIFT generated in 904.In a reality It applies in example, this, which is related to, checks BIFT to be directed to the number for the FBM entries that this of each position location determination position is set wherein, And determine the maximum number with the FBM entries to position location being set.It is discussed in fig. 12 on definite ECMP The maximum number of subsidiary details in path.In 908, BFR determines whether the maximum number in ECMP paths is more than 1.If it is not, on The generation forwarding information unrelated with ECMP problems, need not take further action.However, if BFR determines that there are a plurality of ECMP Path, BFR generate non-ECMP forwarding informations in 910.In one embodiment, this is related to multiple forwarding tables of generation and/or more A forwarding entry will make choice multiple forwarding tables and/or multiple forwarding entries to provide load balancing and avoid grouping secondary This.It is discussed in Figure 13 A, 13B on the subsidiary details for generating non-ECMP forwarding informations.

Present specification shows the flow charts of the instantiation procedure used by node according to Figure 10.Figure 10 shows generation such as The subsidiary details of the 902 described position index routing tables (BIFT) of Fig. 9.In one embodiment, Figure 10 is by such as Fig. 4's The BFR of BFR 406 etc is performed.

In 1002, BFR receives the notice generated by BFER.In one embodiment, notice is received by IGP, and is wrapped Containing identifying routable address (for example, router identifier) associated with BFER and position associated with BFER position sum aggregate Close the information of the mapping between identifier.In response to receiving notice, BFR determines related to the BFER of generation notice in 1004 BP.BFR simultaneously determine set identifier, if its in notice by comprising.

In 1006, BFR accesses the topology information of its storage to determine the shortest path along the BFER towards generation notice Next hop neighbor.In 1008, BFR updates BIRT.In one embodiment, this, which includes addition, includes the entry of information, should The position position of message identification BFER and BFR ID and the neighbours of BFER can be reached via it.

Present specification shows the flow charts of instantiation procedure used by node, generation BIFT according to Figure 11.Figure 11 Show the subsidiary details of operation 904 in Fig. 9.In one embodiment, Figure 11 is held by the BFR of the BFR 406 of such as Fig. 4 etc Row.

In 1102, the first entry of the BIRT of BFR selections BFR.In 1104, BFR is determined and the relevant neighbours of entry With position position.In one embodiment, neighbours are identified by BFR ID or prefix or other information.In 1106, BFR determines BIFT Whether entry for neighbours is included.In the case of the first BIRT entries, there will be no the neighbours with identifying the BIRT entries Occupy corresponding BIFT entries.If there is no BIFT entries corresponding with neighbours, in 1108, BFT creates corresponding with neighbours BIFT entries.In 1110, BFR sets the relevant position in position position with being identified in BIRT entries in FBM.1112, BFR Determine whether BIRT includes other entry.If so, select next BIRT entries in 1114, BFR.

As an example, consider the BIRT 502 of Fig. 5 A, the first entry in 1102, BFR selects BIRT.In BIRT 502 Example in, first entry correspond to neighbours C.Then, determine that the entry corresponds to BP 5 in 1104, BFR.In other words, set Being set to the node L of BP 5 can reach from BFR by node C.Then, BFT creates entry in its BIFT for neighbours C, and in FBM In to the 5th progress set.Fig. 5 B show that entry corresponding with neighbours C has the position 5 being set.Then BFR repeat into Row, next selection is for neighbours D and position 5 corresponding entry etc..After the method shown in Figure 11 is performed, BFR will The BIFT of an entry with the neighbours including being directed to each BFR, and each entry will include forwarding bitmask, forward position Mask has the position being set for the accessibility each BFER of the neighbours.

Present specification shows the flow charts of the instantiation procedure used by node according to Figure 12.Figure 12 is shown in Fig. 9 Shown in 906, the subsidiary details of the maximum number of method in the ECMP paths presented in the forwarding information on BFR are determined. In one embodiment, the method for Figure 12 is performed by the BFR of the BFR 406 of such as Fig. 4 etc.

In 1202, BFR initializing variables (for example, being referred to as maxECMP).In one embodiment, initialize MaxECMP, which is related to, sets maxECMP to be equal to 0.First position in 1204, BFR selection bit strings.In one embodiment In, as shown in Figure 5 B, bit string corresponds to the forwarding bitmask in the forwarding table of position.In another embodiment, position position corresponds to First in BIER topology tables, topology table includes indicating each neighbours by BFR, which position is accessibility letter Breath.

In 1206, BFR initializes the variable for being for example referred to as COUNT.In one embodiment, initialization COUNT is related to And COUNT is set to be equal to 0.First entry in 1208, BFR selects BIFT or topology table.1210, as an example, BFR is true Whether determine the FBM of entry first is arranged to 1.If so, increase COUNT in 1212, BFR.

It determines to whether there is more entries in BIFT or topology table in 1216, BFR.If so, it is selected in 1214, BFR Next entry and return 1210, wherein BFR determines whether first of the FBM in entry is arranged to 1.If so, 1212, BFR increases COUNT.In this way, BFR determines how many entry has first position being set in BIFT, and Value is stored in counting variable (for example, COUNT).

Next, whether the value for determining COUNT in 1218, BFR is more than maxECMP.During first time operation method, speech is changed It, to first position, if in these positions any one be set, will be greater than since maxECMP is initially 0, COUNT maxECMP。

1220, the response of maxECMP is more than as definite COUNT, maxECMP is set as the value phase with COUNT by BFR Deng.Determine whether there are more position positions in bit string in 1222, BFR.It is if so, next in 1224, BFR selects bit string Position position.In the example present, next bit position is position 2.Method is then back to 1206, wherein COUNT is initialized as again 0。

Then, whether it is arranged to 1 in the first entry of 1208, BFR selections BIFT and the position 2 of definite first entry.Side Method is carried out along each iteration of bit string.At the end, the value of maxECMP will equal to the ECMP paths indicated by BIFT most Big figure.Corresponding to position position 1 using the example BIFT504 of Fig. 5 B, the maximum number in ECMP paths is 4.

Present specification shows the flow charts of the instantiation procedure used by node according to Figure 13 A.Figure 13 A are shown such as figure The subsidiary details of the non-ECMP forwarding informations of generation in 9 shown in 910.In one embodiment, Figure 13 A by such as Fig. 4 BFR 406 etc BFR is performed.Figure 13 A, which are shown, is converted to the BIFT comprising a plurality of ECMP paths not comprising a plurality of ECMP paths Multiple BIFT process.

ECMP mapping tables 602 in 1302, BFR generates mapping table, such as Fig. 6.Mapping table is included for every ECMP The row in path.In one embodiment, the number of row is equal to the value of the maxECMP calculated in Figure 12.Mapping table also includes pin The row of each position of bit strings.

First position of the FBM in the BIFT of BFR is contained in 1304, BFR selections.In 1306, BFR determines this position Occurrence number of the position in BIFT.In other words, BFR determines that how many neighbours' entries are arranged to 1 comprising wherein this position FBM.In one embodiment, it is 0 that BFR, which sets count value, and whenever BFR detects that wherein this position is arranged to 1 neighbour When occupying entry, increase count value.In one embodiment, it is multiplexed the count value calculated in Figure 12.

Corresponding neighbor information is pressed into column distribution in 1308, BFR.If in the mapping table, the position being set of BP goes out Occurrence number is equal with the number arranged in mapping table, then will go out with there are (position in other words, being set) corresponding each neighbours Now once.If the number that the position being set occurs is less than the maximum number arranged in mapping table, then corresponding with the position being set One or more neighbours will appear from repeatedly.As an example, if the true position locations of BFR are set in two entries, and ECMP The maximum number (i.e. the columns of mapping table) in path is 4, then each neighbours corresponding with the entry that its middle position is set will be Occur twice in mapping table entry.

It is determined in 1310, BFR in bit string or forwarding bitmask with the presence or absence of more multidigit position.If so, 1312, BFR selection selection next bits position.After entire bit string is processed, mapping table, which is done, to be filled in.

1314, to each row of mapping table, BFR generations BIFT.In one embodiment, each column-generation BIFT is related to And create entry corresponding with each neighbours.Each entry includes FBM.To every BP of mapping table, BFR determines that the BP should be Which it is set in the FBM of neighbours.Consider the example in Fig. 6, as shown in Figure 7 A, in the first BIFT, position position 1,2 and 3 exists It is set in FBM corresponding with neighbours A.To the BIFT shown in Fig. 7 B, position position is set in FBM corresponding with different neighbours Position.

Present specification shows the flow charts of the instantiation procedure used by node according to Figure 13 B.Figure 13 B are shown such as figure Another method of the non-ECMP forwarding informations of generation in 9 shown in 910.In one embodiment, method by such as Fig. 4 BFR 406 etc BFR is performed.

In 1320, BFR generations according to the optimization BIFT of bit position index.In one embodiment, this make use of BIFT, example BIFT 504 as shown in Figure 5 B.BFR determines the length of the FBM used in BIFT, and creates and be directed in the BIFT of optimization The entry of each BP.First position is selected in 1322, BFR.The first neighbours in 1324, BFR selects BIFT. In the example of BIFT504, BFR selection neighbours A.Determine whether position corresponding with this position is set in 1326, BFR.If It is to create entry corresponding with this position in 1328, BFR.In one embodiment, entry includes the forwarding for coming from BIFT Bitmask and the information for identifying neighbours.In the example of BIFR 504, first is set, therefore BFR is in the BIFT of optimization In to BP 1 create comprising neighbours A and neighbours A FBM { 00111 } entry.

It determines to whether there is more neighbours in BIFT in 1330, BFR.If so, next neighbours are selected in 1332, BFR, And 1326, determine whether position corresponding with position position is set.If so, BFR creates another entry corresponding with position position, The entry includes the FBM and neighbours for coming from BIFT.In the example of BIFT 504, the first BP is also set for neighbours B, because This BFR creates BP 1 in the BIFT of optimization the entry of the information of the FBM { 01101 } comprising mark neighbours B and neighbours B.

After all neighbours in traveling through BIFT, more multidigit position is determined whether there is in 1334, BFR.If so, 1336, BFR selection next bit positions, and return to 1324.Behind each position in traveling through bit string, BFR has generated all The optimization BIFT according to position name placement of BIFT 802 such as Fig. 8 etc, optimization BIFT are included for every ECMP paths Entry.

Present specification shows the flow charts of the instantiation procedure used by node according to Figure 14.The BFR 406 of such as Fig. 4 Etc BFR with non-ECMP forwarding informations (for example, forwarding table to every ECMP paths) select one group of forwarding information (example Such as, BIFT or BIFT entries) in response to receiving multi-case data grouping.In one embodiment, selection, which relates to the use of, is contained in The flow valuve of multi-case data grouping.Figure 14 shows to generate a kind of method of flow valuve.

Information about firms is received in 1402, BFIR.In one embodiment, information about firms is bgp information.1404, BFIR The multicast group that identification is identified by information about firms.In one embodiment, this is related to parsing member's message, identifies Multicast group address Domain, and extract Multicast group address.

Flow valuve is generated in 1406, BFIR.In one embodiment, generation flow valuve be related to create multicast source cryptographic Hash and/ Or the cryptographic Hash or identifier of group address.In an alternate embodiment of the invention, flow valuve can be implemented as digital value.As an example, BFIR Can be that each multicast group distributes numerical value, BFIR receives member's message for each multicast group.BFIR can be by using The mode of covering signaling (for example BGP) is assigned to the flow valuve of multicast group to notice, therefore each BFIR uses identical flow valuve. Optionally, to identical multicast group, different stream can be used in each BFIR.In one embodiment, received as transmission node The response of multi-case data grouping, transmission node calculate flow valuve.Transmission node can utilize multicast source and/or group address to be breathed out to calculate Uncommon value can add in side information to cryptographic Hash, which is, for example, to identify the information of the port on transmission node.

Group membership's table is updated in 1408, BFIR.In one embodiment, update group membership's table be related to BFIR with multicast group Flow valuve is stored in the corresponding entry of information about firms.In one embodiment, update group membership's table further relate to BFIR with multicast By position corresponding with the BP of BFER position in the corresponding bit string of group.In one embodiment, member's message includes the BP of BFER. Optionally, BFIR by using the address of the BFER that initiates member's message and by the information of IGP advertisement (for example, BFIR Information in BIRT) it searches to determine the relevant BP of BFER with initiating member's message to perform.

Present specification shows the flow charts of the instantiation procedure used by node according to Figure 15.Figure 15 is shown by BFIR A kind of method performed.Multi-case data grouping is received in 1502, BFIR (for example, from host).Multicast number is determined in 1504, BFIR According to the flow valuve of the multicast group of grouping.In one embodiment, multi-case data grouping includes the information for identifying multicast group.BFIR makes With the information to search flow valuve in the GMT of BFIR.

Flow valuve is packaged in multi-case data grouping in 1506, BFIR, for example, being packaged in the head of BIER.In a reality It applies in example, BFIR includes flow valuve in the entropy field (entropy field) of packet header.Entropy field is usually the field of 8. It is advantageous that：Entropy field is usually located at the head of grouping, therefore BFR can rapidly identify flow valuve, without parse into The main body of the multi-case data grouping entered.

The bit string of the multicast group for multi-case data grouping is determined in 1508, BFIR.In one embodiment, bit string includes In the GMT of BFIR.Bit string is encapsulated into multi-case data grouping in 1510, BFIR, such as is packaged in the head of BIER.BFIR Bit strings can be configured to by such as network administrator and use one in several different method for packing.This depends on network configuration, And such as IP, MPLS or some other tunnelings can be made.

In 1512, BFIR retransmitting multi-casting packets.In one embodiment, this be related to by bit string and BFIR BFIT into Row compares.In one embodiment, retransmitting multi-casting packet be related to access by IR safeguard BIFT, and based on bit string determine by Which neighbour multi-case data is forwarded the packet to.In one embodiment, BFIR is grouped in multi-case data bit string and its BIFT's It performs logical AND (AND) between entry to operate, and the result for forwarding the packet to AND is those genuine neighbours.

Figure 16 A are according to this specification, show that node is used and are grouped the example process being forwarded to multi-case data Flow chart.In one embodiment, which is performed by BFR (for example, BFR406 of Fig. 4).The processing of Figure 16 A is directed to use with BIFT (for example, BIFT504 of Fig. 5 B).

At 1602, BFR receives multi-case data grouping.BFR determines whether multi-case data grouping is BIER at 1604 Grouping, thus whether include bit string.In one embodiment, the head that BFR is grouped multi-case data is scanned, to be referred to Show that the multi-case data is grouped into the value of BIER groupings.BFR can detect that the transmitting terminal of multi-case data grouping is BFR, so as to Go out the conclusion that multi-case data is grouped into the grouping of BIER multi-case datas.If multi-case data grouping is not the grouping of BIER multi-case datas, Then BFR performs alternate process at 1630.In one embodiment, alternate process 1630 is related to multi-case data grouping flooding extremely Total interface or discarding multi-case data grouping on BFR.Alternatively, if traditional multicast forwarding information can use, BFR It can use the information to forwarding grouping.

At 1606, BFR determines whether multi-case data grouping includes flow valuve.In one embodiment, this is related to BFR to more Multicast data packet header is parsed, and determines whether head includes entropy field.If it is, the value in entropy field can be Flow valuve can indicate that there is no one of class values for flow valuve in multi-case data grouping.

In response to detecting that multi-case data grouping includes flow valuve, BFR determines the value of flow valuve at 1608.In one embodiment In, flow valuve is that BFR converts it to determine the encoded radio of actual flow valuve.Using flow valuve, BFR selects to be used for turning at 1610 Send out the forwarding information of multi-case data grouping.For example, in one embodiment, flow valuve and corresponding BIFT are associated by BFR maintenances Conversion table.One of the flow valuve received in being grouped based on multi-case data, BFR selections BIFT is for retransmitting multi-casting data point Group.

BFR accesses bit string at 1612.In one embodiment, bit string is accessed to be related to identification tunneling and be based on Tunneling type determines position of the bit string in multi-case data grouping.At 1614, BFR selects entry in the BIFT of BFR. In one example, the first entry in BIFT is chosen, and BFR travels through BIFT execution sequences.

BIFT determines whether multi-case data packets forwarding giving the selected associated neighbour of BIFT entries at 1616 It occupies.In one embodiment, this is related between the FBM in the bit string and selected BIFT entries in multi-case data grouping and holds Row AND operation.As determined by 1618, if the result of AND operation is true, this method marches to 1620, and BFR Update the bit string in multi-case data grouping.In one embodiment, this be related to multi-case data grouping in bit string with it is selected BIFT entries in bit string between perform AND operation, and by the bit string of the result write-in multi-case data grouping of AND operation In.This has following effect：The position that cannot be grouped the neighbours being forwarded in the position of position via multi-case data and reach is carried out It resets.The problem of so preventing repetition or loop.

At 1622, multi-case data packets forwarding is given the corresponding neighbours of BIFT entries by BFR.At 1624, BFR is true It whether there is other entries in determining in BIFT.If so, this method is back to 1614, and next entry in BIFT is chosen It selects.

Figure 16 B are according to this specification, show that node uses the example process being forwarded to multi-case data grouping Flow chart.In one embodiment, which is performed by BFR (for example, BFR 406 of Fig. 4).The processing of Figure 16 B is related to Use the BIFT (for example, BIFT 802 of the optimization of Fig. 8) of optimization.

At 1650, BFR receives multi-case data grouping.BFR determines whether multi-case data grouping is BIER at 1652 Grouping, thus whether include bit string.In one embodiment, the head that BFR is grouped multi-case data is scanned, to be referred to Show that the multi-case data is grouped into the value of BIER groupings.BFR can detect that the transmitting terminal of multi-case data grouping is BFR, so as to Go out the conclusion that multi-case data is grouped into the grouping of BIER multi-case datas.If multi-case data grouping is not the grouping of BIER multi-case datas, Then BFR performs alternate process at 1680.In one embodiment, alternate process 1680 is related to multi-case data grouping flooding extremely Total interface or discarding multi-case data grouping on BFR.Alternatively, if traditional multicast forwarding information can use, BFR It can use the information to forwarding grouping.

If multi-case data is grouped into the grouping of BIER multi-case datas, BFR knows that multi-case data grouping includes bit string. BFR determines position of the bit string in multi-case data grouping at 1654.Using bit string, BFR determines that multi-case data grouping should Which neighbour be forwarded to.In one embodiment, this is related to first (as shown in 1656) in selection bit string, and determines Whether first of bit string is set (as shown in 1658).If the position is not set, at 1676 BFR determine be in bit string It is no to there is more multidigit.If it is, BFR selects next bit at 1678, and this method is back to 1658.

In response to determining that the position in bit string is set, BFR determines whether multi-case data grouping includes flow valuve at 1660. In one embodiment, this is related to BFR and multi-case data packet header is parsed, and determines whether head includes entropy field. If it is, the value in entropy field can be flow valuve or can be indicate to be not present flow valuve in multi-case data grouping one group One of value.

In response to detecting that multi-case data grouping includes flow valuve, BFR determines the value of flow valuve at 1662.In one embodiment In, flow valuve is that BFR converts it to determine the encoded radio of actual flow valuve.At 1664, BFR determine optimization BIFT in The number of the selected corresponding entry in position position.Using flow valuve, BFR selects to be used for retransmitting multi-casting packet at 1664 Forwarding entry.In one embodiment, using flow valuve come select forwarding information be related to determine available forwarding information collection (for example, BIFT entries) number and/or ECMP paths associated with given position position number.Number based on ECMP paths with And the maximum number in ECMP paths, flow valuve can be changed (for example, divided by appropriate value).For example, if flow valuve offer is used for The selector in four ECMP paths, but given position position only has there are two entry, then flow valuve can by displacement to the right (divided by Two) selected to provide the possibility for the number that matches.

At 1670, BFR creates the duplicate of multi-case data grouping, and updates bit string.Update the position in the duplicate of grouping String is related in bit strings and the not accessibility corresponding position of neighbours, wherein, these neighbours cannot be via the duplicate quilt from grouping The shortest path for the interface being forwarded to and reach.This can be by the position position that the multi-case data from entrance is grouped and forwarding AND operation is performed to complete between the corresponding bitmask in selected position in table clause.End value is used as multi-case data The bit string of the duplicate of grouping.At 1672, multicast packet is forwarded to interface by BFR.

At 1674, BFR is set in being grouped by the multi-case data forwarded in the bit string that is grouped multi-case data with BFR Position it is corresponding those reset to update the bit string that reaches in multi-case data grouping.In one embodiment, this is related to It is performed in bit string and entry in the multi-case data grouping received between the anti-tree of the corresponding bitmask in selected position AND operation.This has following effect：Pair with the position position that is set in the bit string of outflow grouping it is corresponding those carry out it is clear Zero, this prevents from cycling and repeat.Then BFR determines to whether there is more multidigit in bit string at 1676.Then BFR continues by turn before The bit string of received multi-case data grouping is proceeded to, until reaching the end of bitmask.

Figure 17 is some add-on assembles and/or replacement for showing the node that can be used in network for example shown in Fig. 3 The block diagram of component.In the description, node 1700 includes multiple line cards (line card 1702 (1)-(N)), these line cards are via data Bus 1730 and result bus 1740 are communicatively coupled to forwarding engine or packets forwarding device 1710 and processor 1720.Line card 1702 (1)-(N) includes multiple porthandler 1750 (1,1)-(N, N), these porthandlers are by port processor controllers 1760 (1)-(N) is controlled.It shall also be noted that forwarding engine 1710 and processor 1720 are not only via data/address bus 1730 It intercouples with result bus 1740, but also it is communicatively coupled with one another by communication link 1770.

The processor 1750 and 1760 of each line card 1702 can be installed on single printed circuit board.When receiving point Group or grouping and during head, can be by router 1700 in the following manner to being grouped or being grouped and head is identified and divides Analysis.When received, grouping (or some control information or its whole control information) or grouping and head are handled from port One of device 1750 (1,1)-(N, N) (grouping or grouping and head are received at the porthandler), which is sent to, is coupled to number One or more of those equipment according to bus 1730 equipment is (for example, other in porthandler 1750 (1,1)-(N, N) Porthandler, forwarding engine 1710 and/or processor 1720).Can by for example forward engine 1710 determine to grouping or Grouping and the processing on head.For example, forwarding engine 1710 can determine to be grouped or be grouped and head should be forwarded at port Manage one or more of (1,1)-(N, N) of device 1750.This can pass through the phase into port processor controllers 1760 (1)-(N) One (or multiple) answered indicate herein below to complete：It is stored in one given in porthandler 1750 (1,1)-(N, N) Grouping in a (or multiple) or grouping and head should be forwarded to appropriate one in porthandler 1750 (1,1)-(N, N) It is a.In addition, alternatively, once grouping or grouping and head have been identified as handling, forward engine 1710, processor 1720 Etc. that can be used to handle the grouping or grouping and head or addition grouping security information in a certain manner to ensure grouping peace Entirely.It is being grouped or is being grouped on the node with head as initiation, which can be included for example：Information or grouping to grouping It is encrypted with some or all of the information on head, addition can ensure to be grouped or be grouped and the digital signature of head safety Or some other information or processing.On so processed grouping or the node on grouping and head is received, corresponding place is performed It manages to recover or verify the information of protected grouping or the information on grouping and head.

Figure 18 is the block diagram of computing device, shows how forwarding module is implemented in software, as described above.Calculate system System 1810 widely represent can run computer-readable instruction any single processor or multiple processor computing devices or System.The example of computing system 1810 includes and is not limited to various equipment (including work station, personal computer, calculating on knee Machine, client-side terminal, server, distributed computing system, handheld device (for example, personal digital assistant and mobile phone), Network appliance, interchanger, router, storage control are (for example, array control unit, magnetic tape drive controller or hard disk driver control Device) etc.) in it is any one or more.In its most basic configuration, computing system 1810 can include at least one place Manage device 1818 and system storage 1816.The software of forwarding module 1817 is realized by running, computing system 1810 becomes special Computing device, the dedicated computing equipment are configured as in the above described manner performing packets forwarding.

Processor 1818, which typicallys represent, can handle data or explanation and any type of operating instruction or the processing of form Unit.In certain embodiments, processor 1818 can receive instruction from software application or module.These instructions can to locate Reason device 1818 performs the function of one or more of embodiment that is described herein and/or showing embodiment.For example, processing Device 1818 can perform operate as described herein and/or can be performed for the device of operate as described herein.Processing Device 1818 can also carry out other arbitrary operations, method or processing described herein and/or show and/or can be used for Perform the device of arbitrary other operations, method or processing described herein and/or show.

System storage 1816 typically represent any type that can store data and/or other computer-readable instructions or The volatibility or non-volatile memory device or medium of form.The example of system storage 1816 includes and is not limited to arbitrary access Memory (RAM), read-only memory (ROM), flash memory or other arbitrary suitable memory devices.Although it is not required that, but at certain In a little embodiments, computing system 1810 can include volatile memory-elements (for example, system storage 1816) and non-volatile Property storage device both (for example, the main storage 1832 being described more fully below).In one example, can perform with reality The program instruction of existing forwarding module can be loaded into system storage 1816, wherein, it is more that forwarding module is configured as forwarding Multicast data is grouped.

In certain embodiments, in addition to processor 1818 and system storage 1816, computing system 1810 can also wrap Include one or more assemblies or element.For example, as shown in figure 18, computing system 1810 can include Memory Controller 1818, Input/output (I/O) controller 1820 and communication interface 1822, in these each can be via the communications infrastructure 1812 It is interconnected.The communications infrastructure 1812 typicallys represent the communication between the one or more assemblies that can promote computing device The infrastructure of any type or form.The example of the communications infrastructure 1812 includes and is not limited to communication bus (for example, industry Standard architecture (ISA), peripheral component interconnection (PCI), PCI express (PCIe) or similar bus) and network.

Memory Controller 1818, which typicallys represent, can handle the one of memory or data or control computing system 1810 Any type of communication or the equipment of form between a or multiple components.For example, in certain embodiments, Memory Controller 1818 can come control processor 1818, system storage 1816 and I/O controllers 1820 via the communications infrastructure 1812 Between communication.In certain embodiments, Memory Controller 1818 can be combined to hold individually or with other elements Row described herein and/or one or more of the feature shown or operation and/or Memory Controller 1818 can be used In one or more that individually or with other elements is combined to perform in feature that is described herein and/or showing or operation A device.

I/O controllers 1820 typically represent can coordinate and/or control computing device output and input the arbitrary of function The module of type or form.For example, in certain embodiments, I/O controllers 1820 can control or promote computing system 1810 One or more elements (for example, processor 1818, system storage 1816, communication interface 1822, display adapter 1826, Input interface 1830 and memory interface 1834) between carry out data transfer.

Communication interface 1822 widely represents to promote between computing system 1810 and one or more optional equipments Any type of communication or the communication equipment of form or adapter.For example, in certain embodiments, communication interface 1822 can promote Communication into computing system 1810 between private network or public network including additional computing systems.Communication interface 1822 Example includes and is not limited to wired network interface (network interface card), radio network interface (wireless network interface card), modulatedemodulate Adjust device and other arbitrary suitable interfaces.In at least one embodiment, communication interface 1822 can be via going to network (example Such as, internet) direct link go to being directly connected to for remote server to provide.Communication interface 1822 can also be for example, by LAN (for example, ethernet network), personal area network, phone or cable system, cellular phone connection, satellite data connection or arbitrary Other suitably connect to provide such connection indirectly.

In certain embodiments, communication interface 1822 also may indicate that host adapter, which is configured as Promote via external bus or communication port between computing system 1810 and one or more complementary networks or storage device Communication.The example of host adapter includes and is not limited to small computer system interface (SCSI) host adapter, general serial Bus (USB) host adapter, 11054 host adapter of Institute of Electrical and Electronics Engineers (IEEE), serial advanced technology attachment Part (SATA) and SATA (eSATA) host adapter of extension, Advanced Technology Attachment (ATA) and Parallel ATA (PATA) are main Machine adapter, Fibre Channel port adapters, Ethernet Adaptation Unit, etc..

Communication interface 1822 can also allow for computing system 1810 to participate in Distributed Calculation or remote computation.For example, communication Interface 1822 can receive instruction from remote equipment or send an instruction to remote equipment for operation.

As shown in figure 18, computing system 1810 can also include at least one display device 1824, the display device 1824 The communications infrastructure 1812 is coupled in via display adapter 1826.Display device 1824, which typicallys represent, visually to be shown Any type of information or the equipment of form forwarded by display adapter 1826.Similarly, 1826 general table of display adapter Show and be configured as being used for what is shown on display device 1824 from the communications infrastructure 1812 (or from frame buffer) forwarding The equipment of figure, any type of text and other data or form.

As shown in figure 18, computing system 1810 can also include at least one input equipment 1828, the input equipment 1828 The communications infrastructure 1812 is coupled in via input interface 1830.Input equipment 1828 typicallys represent can be to computing system 1810 provide (computer the is manually generated) any type of input or the input equipment of form.The example of input equipment 1828 Including and be not limited to keyboard, sensing equipment, speech recognition apparatus or other arbitrary input equipments.

As shown in figure 18, computing system 1810 can also include main storage 1832 and spare storage device 1833, 1832 and 1833 are coupled in the communications infrastructure 1812 via memory interface 1834.Storage device 1832 and 1833 typicallys represent Any type of data and/or other computer-readable instructions or the storage device of form or medium can be stored.For example, storage Equipment 1832 and 1833 can be disc driver (for example, so-called hard disk driver device), floppy disk, tape drive, CD Driver, flash drive etc..Memory interface 1834 is typicallyed represent in storage device 1832 and 1833 and computing system Any type of data or the interface or equipment of form are transferred between 1810 other assemblies.Class main storage 1832 is deposited Storage equipment can store the information of such as routing table and forwarding table etc.

In certain embodiments, storage device 1832 and 1833 can be configured as is read out from removable memory module And/or write to removable memory module, wherein, removable memory module is configured as storage computer software, data Or other computer-readable informations.The example of suitable removable memory module includes and is not limited to floppy disk, tape, CD, sudden strain of a muscle Deposit equipment etc..Storage device 1832 and 1833 can also include allowing computer software, data or other computer-readable instructions Other the similar structures or equipment being loaded into computing system 1810.For example, storage device 1832 and 1833 can by with It is set to reading or write-in software, data or other computer-readable informations.Storage device 1832 and 1833 can also be calculating system A part for system 1810 can be the autonomous device to be accessed by other interface systems.

Many other equipment or subsystem may be connected to computing system 1810.On the contrary, need not occur showing in Figure 18 The all components that go out and equipment implement embodiment that is described herein and/or showing.Above mentioned equipment and subsystem are also It can be interconnected in a manner of being different from shown in Figure 18.

Computing system 1810 can also use any number of software, firmware and/or hardware configuration.For example, institute is public herein The computer program that one or more of embodiment opened can be encoded as on computer readable storage medium (is also referred to as Computer software, software application, computer-readable instruction or computer control logic).The example of computer readable storage medium Including magnetic storage medium (for example, hard disk drive and floppy disk), optical storage media (for example, CD-ROM or DVD-ROM), electricity storage Medium (for example, solid state drive and quick flashing medium) etc..Such computer program can also be via network (for example, internet) Or computing system 1810 is transferred in carrier media to store in memory.

Computer-readable medium comprising computer program can be loaded into computing system 1810.It is stored in computer Then all parts of computer program on readable medium or a part can be stored in system storage 1816 and/or deposit In each several part for storing up equipment 1832 and 1833.When being performed by processor 1818, the computer that is loaded into computing system 1810 Program can cause processor 1818 to perform the function of one or more of embodiment described herein and/or shown And/or processor 1818 is caused to become to perform one or more of embodiment described herein and/or shown The device of function.Additionally or alternatively, one or more of embodiment described herein and/or shown can be by reality In present firmware and/or hardware.For example, computing system 1810 can be configured as application-specific integrated circuit (ASIC), which fits In one or more of realization presently disclosed embodiment.

Figure 19 be can exemplary network device associated with the node in the network 200 of Fig. 2 block diagram.For example, It is associated that the network equipment 1950 of Figure 19 can enable node 206 with the BIER in Fig. 2.In some cases, it is used herein " node " include one or more network equipments associated with the node." network equipment " used herein includes performing Routing function and/or forwarding capability and support one or more route and/or the various equipment of exchange agreement are (for example, routing Device, interchanger or network controller).Network equipment maintenance one or more routing table and/or forwarding table, these routing tables and/ Or forwarding table storage identifies the routing for going to each data source and/or data user and/or forwarding information.For example, in multicast In enabled node, the network equipment realizes that the QoS routing for being used for multi-case data grouping being conveyed to multicast reception end from multicast source is assisted View.

In the embodiment of Figure 19, the network equipment 1950 includes the storage device for information about firms 1952, for forwarding Storage device, forwarding module 1960 and the interface 1962 of information 1964.Interface 1962 be coupled as sending and receiving grouping and/ Or other internet messages.It should be noted that the network equipment 1950 can include additional interface, and each interface can be that logic connects Mouth or physical interface.In one embodiment, interface 1962 includes one or more ports.

Forwarding module 1960 is configured as performing forwarding based on the forwarding information 1964 stored.Forwarding module 1960 is also It is configured as updating stored information about firms 1952 and forwarding information 1964.Forwarding module 1960 can realize 3 layer protocols and/ Or 2 one or more of layer protocol example.

Entry 1970 provides the example for being stored in the information about firms in the memory of the network equipment.As shown in the figure, entry 1970 include the information of set identifier (SI) 1954, the information 1956 for identifying a position (BP) and mark multicast group 1958.Node associated by SI and BP identification entries 1970, and the multicast ordered by multicast group information mark respective nodes Group.In one embodiment, the storage device of information about firms 1952 is implemented as group member table.

Entry 1972 provides the example that can be stored in the forwarding information in the memory of the network equipment.As shown in the figure, Entry 1972 includes information 1966, bit string or the bit array 1968 of mark BP and identifies the information 1969 of neighbours.Forwarding module 1960 are forwarded the packet multi-case data to associated with the neighbours identified in the entry using the information in entry 1972 Interface.In one embodiment, the storage device of forwarding information 1964 is implemented as position index forwarding table (BIFT).

Although with reference to several embodiments, invention has been described, and the present invention is not intended to be limited to presented here Concrete form.On the contrary, its be intended to the replacement that covering is reasonably included in the scope of the present invention that appended claims define, It changes and equivalent.

Claims (9)

1. a kind of method, including：

Determine the maximum number in equal cost multipath ECMP paths identified in single group forwarding information；

Multigroup forwarding information is generated, the wherein generation includes the maximum number based on ECMP paths by the single group forwarding information turn It is changed to multigroup forwarding information；

Grouping is received at node, wherein the grouping includes bit string；

First group of forwarding information is selected from multigroup forwarding information, wherein the selection is based on flow valuve, and described first group Forwarding information includes forwarding bitmask；

The bit string and the forwarding bitmask are compare to determine if to forward the grouping；And

The matched position of position based on the specific position in the bit string and the specific position in the forwarding bitmask is to forward State grouping.

2. the method as described in claim 1 further includes：

The flow valuve is generated, the wherein generation includes calculating the cryptographic Hash of address associated with multicast group；

Include the flow valuve in the grouping.

3. the method as described in claim 1, wherein each group in multigroup forwarding information includes forwarding table.

4. the method as described in claim 1, wherein each group in multigroup forwarding information includes forwarding table clause.

5. a kind of network equipment, including：

Memory, the multigroup forwarding information of the memory storage；

Network interface；And

Processor,

Wherein described network interface and the processor are configured as：

Determine the maximum number in equal cost multipath ECMP paths identified in single group forwarding information；

Multigroup forwarding information is generated, the wherein generation includes the maximum number based on ECMP paths by the single group forwarding information turn It is changed to multigroup forwarding information；

Grouping is received at node, wherein the grouping includes bit string；

First group of forwarding information is selected from multigroup forwarding information, wherein the selection is based on flow valuve, and described first group Forwarding information includes forwarding bitmask；

The bit string and the forwarding bitmask are compare to determine if to forward the grouping；And

The matched position of position based on the specific position in the bit string and the specific position in the forwarding bitmask is to forward State grouping.

6. the network equipment as claimed in claim 5, wherein the processor is additionally configured to：

The flow valuve is generated, wherein generating the flow valuve includes the cryptographic Hash for calculating address associated with multicast group；

Include the flow valuve in the grouping.

7. the network equipment as claimed in claim 5, wherein each group in multigroup forwarding information includes forwarding table.

8. a kind of system, including：

Storage device, the storage device are used to store multigroup forwarding information；

Network Interface Unit；And

Processing unit,

Wherein described Network Interface Unit and the processing unit are used for：

Determine the maximum number in equal cost multipath ECMP paths identified in single group forwarding information；

Multigroup forwarding information is generated, the wherein generation includes the maximum number based on ECMP paths by the single group forwarding information turn It is changed to multigroup forwarding information；

Grouping is received at node, wherein the grouping includes bit string；

First group of forwarding information is selected from multigroup forwarding information, wherein the selection is based on flow valuve, and described first group Forwarding information includes forwarding bitmask；

The bit string and the forwarding bitmask are compare to determine if to forward the grouping；And

The matched position of position based on the specific position in the bit string and the specific position in the forwarding bitmask is to forward State grouping.

9. system as claimed in claim 8, wherein the processing unit is additionally configured to：

The flow valuve is generated, wherein generating the flow valuve includes the cryptographic Hash for calculating address associated with multicast group；

Include the flow valuve in the grouping.