WO2013019434A1

WO2013019434A1 - Reverse path forwarding lookup with link bundles

Info

Publication number: WO2013019434A1
Application number: PCT/US2012/047667
Authority: WO
Inventors: Sarang Dharmapurikar; Mahesh Maddury; Francisco Matus
Original assignee: Cisco Technology Inc
Current assignee: Cisco Technology Inc
Priority date: 2011-08-03
Filing date: 2012-07-20
Publication date: 2013-02-07
Anticipated expiration: 2014-02-03
Also published as: US8873558B2; EP2740048B1; CN103703455B; EP2740048A4; EP2740048A1; CN103703455A; US20130034097A1

Abstract

In one embodiment, a method includes receiving a packet at an interface at a network device having a plurality of interfaces connected to a plurality of links forming a bundle, performing a Reverse Path Forwarding (RPF) check on the received packet, and forwarding the packet if it passes the RPF check. The RPF check includes a lookup in an RPF table having a plurality of entries for the bundle, each of the entries including the bundle and one of the links in the bundle, and verification that the interface receiving the packet is connected to one of the links in the bundle identified in the lookup. An apparatus is also disclosed.

Description

REVERSE PATH FORWARDING LOOKUP WITH LINK

BUNDLES

TECHNICAL FIELD

{0001 { The present disclosure relates generally to communication networks, and more particularly, to reverse path forwarding cheeks.

BACKGROUND

{0002| A -network device may include a plurality of interfaces connected to links forming a link bundle. The links may comprise, for example, ECM.P (Equal Cost Multi-Path) members or other links forming a link bundle. A large number of links may cause problems when implementing a Reverse Path Forwarding (RPF) check. Conventional networks limit the number of links in a bundle, perform a loose RPF check (do not check the incoming interface), or compieteiy skip the RPF cheek. This results in a number of drawbacks.

BRIEF DESCRIPTION OF THE FIGURES

{0003] Figure 1 illustrates an example of a network in which embodiments described herein may be implemented.

0004] Figure 2 illustrates another example of a network in which embodiments described herein may be implemented.

{0005 { Figure 3 depic ts an example of a network device that may be used to implement the embodiments.

{0006} Figure 4 is a flowchart illustrating an overview of a process for performing a reverse path, forwarding check, in. accordance with one embodiment.

|¾007] Figure 5 depicts an example of a re verse path forwarding table, in accordance with one embodiment.

[0008] Figure 6 illustrates an example of a network device in communication with a plurality of links associated with link bundles corresponding to the table of Figure 5,

[00O9| Corresponding reference characters indicate corresponding parts throughout the several views of the drawm.es. DESCRIPTION OF EXAMPLE EMBODIMENTS

OOvveerrvviieeww

{{00001100)) IInn oonnee e emmbbooddiimmeenntt,, a a mmeetthhoodd g geenneerraallllyy ccoommpprriisseess r reecceeiiviinngg a a ppaacckkeett aatt aann iinntteerrffaaccee aatt. a a. nneettwwoorrkk ddeevviiccee c coommppririssiinngg aa p plluuraralliittyy o off i inntteerrffaacceess ccoonnnneecctteedd ttoo aa pplluurraalliittyy ooff l liinnkkss f foorrmmiinngg a a b buunnddllee,, p peerrffoorrmmiinngg aa RReevveerrssee P Paatthh FFoorrwwaarrddiinngg ((RRPPFF)) cchheeeekk oonn tthhee rreecceeiivveedd ppaacckkeett,, aanndd foforrwwaarrddiinngg tthhee ppaacckkeett iiff iitt ppaasssseess t thhee RRPPFF cchheecckk.. TThhee RRPPFF cchheecckk ccoommpprriisseess aa llooookkuupp i inn a ann RRPPFF t taabbllee ccoommpprriissiinngg aa pplluurraalliittyy o off e ennttririeess ffoorr t thhee bbuunnddllee,, eeaacchh ooff t thhee eennttrriieess ccoommppririssiinngg tthhee bbuunnddllee aanndd oonnee ooff t thhee lliinnkkss iinn t thhee bbuunnddllee,, a anndd v veeririffiiccaattiioonn tthhaatt tthhee iinntteerrffaaccee ..rreecceeiivviinngg tthhee ppaacckkeett iiss c coonnnneecctteedd ttoo o onnee ooff tthhee lliinnkkss iinn tthhee bbuunnddllee iiddeennttiiffiieedd iinn tthhee llooookkuupp,,

((00001111 jj I inn aannootthheerr eemmbbooddiimmeenntt,, aann aappppaararattuuss g geenneerraallllyy c coommpprriisseess aa pplluurraalliittyy ooff iinntteerrffaacceess ffoorr c coonnnneeccttiioonn ttoo aa pplluurraalliittyy ooff lliinnkkss ffoorrmmiinngg aa bbuunnddllee,, aa pprroocceessssoorr foforr rreecceeiivviinngg aa ppaacckkeett,, ppeerrfoforrmmiinngg aa RReevveerrssee PPaatthh F Foorrwwaarrddiinngg ((RRPPFF)) cchheeeekk oonn t thhee rreecceeiivveedd-- ppaacckkeett,, aanndd ffoorrwwaarrddiinngg t thhee ppaacckkeett iiff iitt ppaasssseess tthhee RRPPFF cchheeeekk,, aanndd m meemmoorryy ffoorr ssttoorriinngg aann R RPPFF ttaabbllee ccoommpprriissiinngg a a p plluurraalliittyy ooff e ennttrriieess ffoorr tthhee bbuunnddllee,, eeaacchh ooff tthhee e ennttrriieess ccoommpprriissiinngg t thhee bbuunnddllee aanndd oonnee ooff tthhee lliinnkkss iinn tthhee bbuunnddllee.. T Thhee RRPPFF cchheeeekk ccoommpprriisseess aa llooookkuupp iinn t thhee RRPPFF ttaabbllee aanndd vveerriiffiiccaattiioonn tthhaatt tthhee iinntteerrffaaccee rreecceeiivviinngg tthhee ppaacckkeett iiss ccoonnnneecctteedd ttoo oonnee ooff tthhee lliinnkkss iinn tthhee bbuunnddllee i iddeennttiififieedd iinn t thhee llooookkuupp..

fOOI l] The following description is presented to enable one of ordinary skill m the art to make and use the embodiments. Descriptions of specific embodiments and applications are provided only as examples, and various modifications will be readily apparent to those skilled in the art. The general principles described herein may be applied to other applications without departing from the scope of the embodiments. Thus, the embodiments are not to be limited to those shown, but are to be accorded the widest scope consistent, with the principles and features described herein. For clarity, details relating to technical material that is known in the technical fields related to the embodiments have not been described in. detail.

{0013] For purposes of illustrating example techniques of network communication, it is important to understand the types of communications that may be traversing a network. The following provides foundational information from which the present disclosure may be explained.

|0 14f in unicast routing, traffic is forwarded through the network along a single path from a source to a destination host according to pre-computed routes. A unicast network device does not typically consider the source address; it considers only the destination address and how it would forward the traffic toward that destination. The network device scans through a routing or forwarding table for a match to the

destination address and then forwards a single copy of the unicast packet out the correct interface in the direction of the destination.

Θ015] By contrast, in multicast forwarding the source is sending traffic to an arbitrary group of hosts that are represented by a multicast group address. Multicast packets are replicated in a network at a point where paths diverge to achieve efficient data delivery to multiple receivers. In IP multicasting, the source may specify a destination IP address that may comprise a multicast group address for any number of receivers to receive the data flow. Multicast packets are sent from a source (S) address to a group (G) address, A multicast group is an arbitrary group (G) of receivers that express an interest in receiving a particular data stream from a source (S). A receiver seeking to receive data sent to a multicast group can. join the group using, for example, Internet Management Group Protocol (IG P). Join messages are typically sent from the receiver to the source and the data flow propagates in the opposite direction.

Receivers that are members of a given rnuiiicast group can recei ve data sent to that multicast group.

|¾016| Multicast-capable network devices create distribution trees that control the path that IP rnuiiicast traffic takes through the network in order to deli ver traffic to all receivers. The two basic types of multicast distribution trees are source trees and shared trees. In a source tree, the multicast traffic source is the root and the branches form a spanning tree through the network to the recei vers. This is also referred to as a shortest path tree (SPT) because the tree typically uses the shortest paths between the source and receiver through the network. Unlike source trees that have their root at the source, shared trees use a single common root placed at some chosen point in the network. This shared root is called a Rendezvous Point (RP.S. [0017] The multicast network device must determine which direction is the upstfeam direction (towards the root of the tree), and which is the downstream direction (or directions), if t here are multiple downstream paths, the net work de vice replicates the packet and forwards if down the appropriate downstream: path based on receiver interest. The concept of identifying the path to reach the source, in order to get the traffic from the source via the same path, is known as Reverse Path Forwarding (RPF). RPF enables network devices to correctly forward multicast traffic down the distribution tree.

[0018] RPF check is an important concept in forwarding operations. Unicast routing techniques are used to determine a path from a receiver or intermediate node back to the tree root. Packets received via this path from the tree root are eligible for further forwarding downstream:. Packets received on other interfaces not connected to this path will not be forwarded and their receipt is referred to as RPF failure.

Distinguishing upstream and downstream traffic in this way is referred to as an RPF check arte! helps to ensure loop-free forwardin of multicast packets and maintain securit (e.g., prevent IP address spoofing or other malicious traffic) in luiicast routing.

[6 19] Multicast RPF may be used in connection with a multicast routing protocol such as Protocol independent Multicast (PIM). PIM is used to dynamically create a multicast distribution tree to ensure distribution to intended receivers while limiting distribution so that network segments that are not in the path between the source and receivers are not burdened with unnecessary traffic. PIM can. leverage the unicast routing protocols used to populate a unicast routing table. PIM uses this unicast routing information to perform the multicast forwarding function. Bidirectional- PIM (Bidir- PIM) is an enhancement of the PIM protocol developed to facilitate efficient many-to- many communications. With Bidir-PFM, for each RP, a router on each link is elected as a designated .forwarder (DF). Using bidirectional mode, multicast groups can scale to an arbitrary number of sources with only a minimal amount of additional overhead.

[0020] The embodiments described herein allow for RPF cheeks across a large number of links grouped together to form a link bundle. As described below, the links may be, for example. Equal Cost Multi-Path (ECMP) members, links connected to designated forwarders, or other members (e.g. , ports, interfaces, bridge domain interfaces) grouped together in a bundle. The embodiments ma be used, for example. for unicast security binding checks to ensure that a packet has arrived on the correct port, or with multicast to ensure that a packet is recei ved on a port in cornmumcation with a designated forwarder associated with a given multicast group. It is to be understood that these are onl examples and that the embodiments described herein may he used in other applications, without departing from the scope of the

embodiments,

(002 Ij Referring now to the drawings, and firs to Figure 1 , an example of a network in which the embodiments described herein may be implemented is shown. The embodiments operate in the context of a data communication network including multiple network devices (nodes) interconnecting c mmunication, paths for receiving and transmitting packets of information that propagate through the network. The example shown in Figure 1 includes network devices 1.0 (A, B, C, D) in communication with hosts 12 (X, Y). Network device A is in communication with host X, and network devices B, C, and D are in communication with host Y. The network device 10 may be a switch, router, or any other network device configured to perform switching, routing, or forwarding operations. The hosts 12 may be an end point server, client device, or any other device configured to transmit, receive, or transmit and -receive traffic. The hosts 1.2 may operate as a source (sender), destination (receiver), or ^'both source and receiver. The traffic transmitted over the network may include data, video, audio, or any combination thereof.

[ΘΘ22] Network device A in Figure 1 includes a plurality of ports (interfaces) connected to links 14 in communication with network devices B, C, and D, and link 15 in communication with host X. n one embodiment, links 14 interconnecting network- device A with network devices B, C, and D are members of an equal cost multi-path bundle 1.6. For simplification, only three links 14 are shown, however, there may be anv number of links (e,s., 10, 100, 1000, more than eisht, more than 100, etc.) in link bundle 1.6, connecting network de vice A to any number of network devices. The link bundle 16 allows the network devices B, C, and D to appear as a single logical device to network device A. The network may also be configured for Layer 2 Multi-Path (L2MP) or TRILL (Transparent Interconnect of Lots of Links), for example.

f0023^"| As described in detail below, the network device 1 is configured to perform reverse path forwarding cheeks to provide a unicast security binding cheek and ensure that a packet has arrived on the correct post. As previously described, RPF checks are used to verify that the reverse path for the source address matches the input port. With a link bundle there can be multiple valid source links and the network device needs to verify that the incoming link for the packet is one of the valid source links. A multi-way RPF check is performed in which the input port may be an of the input ports connected to one of the links 14 within the bundle 16. If the packet arrives on a port connected to a link within a bundle associated wit reverse path route, the packet is accepted and forwarded. If there is no reverse pat route in the bundle from which the packet was received, the source address may have been modified or forged, if the RPF check does not find a reverse path for the packet, the packet is dropped (discarded).

|0024{ Another example of a network in which the embodiments described herein may he implemented is shown in Figure 2. Network devices 20 and 22 are configured to transmit multicast traffic. For simplification, only a small number of nodes and links are shown. Network device 20 (E) is in communication with plurality of network devices 22, The network devices 20, 22 ma be, for example, PIM routers or any other network device configured to perform routing, switching, or forwarding operations. In one embodiment, the network device 20 is configured for Bidir-PIM and can receive packets from multiple sources through designated forwarders 22. in Bidir-PIM, the network device 20 can receive packets on a given multicast group from multiple sources subscribed to this group on different interfaces from different designated forwarders 22. An RPF check is performed to verify that the interface of an arri ving packet is connected to a link that belongs to this set of interfaces (bundle 26) on which a router can expect the Bidir-PIM packets for a given multicast group

[0025] it is to be understood that the networks shown in Figures i and 2 and described herein are onl examples and that the embodiments may be implemented in networks having different network topologies and network devices, without departing from the scope of the embodiments.

[0026] Figure 3 illustrates an example of a network device (e.g., switch, router) 30 that may be used to implement the embodiments described herein. In one embodiment, the network device 30 is a programmable machine that may be implemented in hardware, software, or any combination thereof The network device 30 includes one or more processors 32, memory 34, and -network interfaces 36. Memory 34 ma be a volatile memory or non-volatile storage, which stores various applications, operating systems, modules, and data for execution and use b the processor 32, For example, the memory 34 may store tables, entries, network configurations,, policies, forwarding frees, etc. In one embodiment, memory 34 includes a forwarding table 38 and RPF table 40 (described further below with respect to Figure 5), The RPF tabic 40 may be stored, for example, in associative storage (e.g., content-addressable memory (CAM)). ^'T e forwarding table 38 may be any data structure including one or more tables (e.g., -forwarding table, routing table) or information base (e.g., forwarding information base (FIB), routing information base (RIB)) etc. The FIB may include ECMP information, for example.

f0027{ Logic may be encoded in one or more tangible media for execution by the processor 32. For example, the processor 32 may execute codes stored in a computer- readable medium such as memory 34. The computer-readable medium may be, for example, electronic (e.g., RAM^" (random access memory), ROM (read-only memory), EPROM (erasable programmable read-only metaory)), magnetic, optical (e.g., CD, DVD), electromagnetic, semiconductor technology, or any oilier suitable medium. |¾ 28^"j Art operating system, portions of which may be resident in memory 34 and executed by the processor 32, may functionally organize the network node by invoking network operations in support of software processes executing on the processor. These software processes may include, for example, a PTM module, which relies on an underlying topology-gathering protocol to populate the forwarding table 38 to establish and maintain paths or routes.

|¾i)29{ The network interfaces 36 may comprise any number of interfaces

(Imecards, ports) for receiving data or transmitting data to other devices. The interfaces 6 may include, tor example, an Ethernet interface for connection to a computer or network.

{ΘΘ3Θ] it is to be understood that the network, device 30 shown in Figure 3 and described above is only one example and that different configurations of network devices may be used.

j^'8931| Figure 4 is a flowchart illustrating an overview of a process for performing- a reverse path forwarding check, in accordance with one embodiment At step 42, the network device receives a packet. The network device performs a forwarding lookup (e.g., lookup in forwarding or routing table 38) based on a destination address in the packet (step 44). The network device also performs a reverse path fonvarding check (step 46). The RPF check may be based on a source address in a itnicast packet or ma be based on a destination address (multicast group) in a multicast packet. A described in detail below, the RPF check -includes a lookup in an associati ve data structure (e.g., RPF table 40) configured to allow for RPF checks across a large number of links i a bundle. The lookup identifies a bundle and link associated with the source address or multicast group in the packet. The RPF check verifies that the interface on which the packet was received is connected to one of the Units in the bundle identified in the lookup. If the packet passes the RPF cheek (step 48), the packet is forwarded based on the results of its forwarding iookop at step 44 (step 50). If the packet does not pass the RPF check, it is dropped (step 52). The RPF check fails if the lookup fails (no entry found in RPF table) or if the link (interface) on which the packet was received belongs to a different bundle than identified in the source address lookup in the RPF table.

[6032] It is to be understood that the process shown in Figure 4 and described above is only one example and that steps may be added, removed, reordered, or combined without departing from the scope of the embodiments.

jO033{ The following describes one example for RPF check operations (step 46 in Figure 4):

RPF_eheek (packet)

if (packet is unicast)

SAjinfo - FiB.iookop(packet.SA)

if (SA. infb.rnulttpath enabled) //This address is reached through a bundl e of mul tiple equal, cost paths/interfaces

//Check to see if the interface packet was recei ved on is a member of this bundle using an associati ve lookup.

rpfjpass - Rpfrabie.LookuD(SAJ«fo.BUNDLE J^'D,

paket.incomingjnterfece)

else // his SA is reached through a single path/interface end if G _...info ^::: FiB.!ookup(pac.ket .DA) //Lookup the Destination Address

(DA) also known as Multicast Group (G.S

//In BIDI -PIM, packets can be received on a given Multicast- Group from different sources subscribed to this group on different interfaces from different designated forwarders (DFs) //Check to see if the interface packet was received on is one on which packets are received for given Multicast Group using an associative lookup,

rpf ass ~ RpfTab!e.Lookup{Gjnfo.BU DLEJ.D, packet. mcomingjeterface)

else

//^'no associative lookup

end if

end

[0034 Figure 5 sho ws an example of EPF table 40, in accordance wi th one embodiment The RPF table 40 includes a plurality of entries 54, each entry comprising a (bundle, link) pair. The bundles and links may be identified using any appropriate identifier (e.g., bundle ID, interface ID, bridge domain, adjacency, etc.). The entries 54 in the RPF table 40 shown in Figure 5 correspond to network device 60 shown in Figure 6. Figure 6 illustrates network device 60 comprising a plurality of ports (interfaces) connected to a plurality of links. Links LI , L2, and L3 belong to bundle B , links L4, L5, 1,6, and L7 belong to bundle B2, and links L8 and L9 belong to bundle B3. The link may be, for example, ECMP members or link connected to multicast sources and recipients in PIM-Bidir, as described above with respect to Figures 1 and 2.

[0035] in one embodiment, table 40 is a hash table and the lookup is performed using the source or destination address in the received packet, as previously described. The lookup is preferably performed in hardware to speed up packet forwarding operations, it is to be understood that the table shown in Figure 5 and descri ed herein is only an example and that other data structures may be used, without departing from the scope of the embodiments. For example, the table 40 may be any type of

associative arra configured for use with a lookup or indexing operation to find a value (e.g., bundle/link pair) associated with a key (e.g., source address, destination address), wherein the array maps (binds) the key to the value.

j0 36{ Although the method and apparatus have been described in accordance with tiie embodiments shown , one of ordinary skili in the art wi!i readily recognize that there could be variations made without departing from the scope of the embodiments.

Accordingly, it is intended that all matter contained in the above description and shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

Claims

1 . A method comprising:

receiving a packet at an interface at a network device comprising a plurality of interfaces connected to a plurality of links forming a bundle;

performing a Reverse Path Forwarding (RPF) check on the received packet; and

forwarding the packet if the packet passes said RPF check;

wherein said RPF check comprises;

a lookup in an RPF table comprising a plurality of entries for said bundle, each of said entries comprising said bundle and one of the links in said bundle; and

verification that the interface receiving the packet is connected to one of the iinks in said bundle identified in said lookup.

2. The method of claim. .1 wherein said bundle comprises an equal cost multi- path bundle and the lookup is based on a source address in the packet,

3. The method of claim 1 wherein performing said RPF check comprises performing a security binding check for unicast.

4. The method of claim .5 wherein said plurality of links are connected to Protocol independent Multicast (MM) routers and said lookup is based on a multicast group address in the packet,

5. The method of claim 4 wherein the network device is configured for bidirectional-PlM operation and said plurality of links are in communication with designated forwarders.

6, The method of claim I wherein the RPF table comprises a hash table.

7. The method of claim 1 wherein the RPF table comprises a pluralit of entries for at least one other bundle.

8. T e^ method of claim .1 wherein said bundle comprises more than eight- links.

9. The method of claim 1 wherein said bundle comprises more than one hundred links.

10. An apparatus comprising:

a plurality of interfaces for connection to a plurality of links forming a bundle a processor for receiving a packet, performing a Reverse Path Forwarding

(RPF) check on the recei ved packet, and forwarding the packet if the packet passes said RPF check; and

memory for storing an RPF table comprising a plurality of entries for said bundle, each of said entries comprising said bundle and one of the links in said bundle;

wherein said RPF check comprises a lookup in the RPF table and verification that the interface receiving the packet is connected to one of the Sinks in said bundle identified in said lookup.

1 1 . The apparatus of claim 10 wherein said bundle comprises an equal cost multi-path bundle and said lookup is based on a source address contained in the packet,

12. The appara tus of claim 10 wherein performing said RPF check comprises performing a security binding check for uuicasl

13. The apparatus of claim. 10 wherein said plurality of links are connected to Protocol Independent ulticast (PIM) routers and said lookup is based on a multicast group address in the packet.

14. The apparatus of claim 13 wherein the processor is configured for bidtrectional-PlM operation and said pluralit of Sinks are in communication with designated forwarders.

15. The apparatus of claim 10 wherein the RPF tab e comprises a ash table. 1 {>. An apparatus comprising:

means for performing a Reverse Path Forwarding (RPF) check on a packet received at an interface, the apparatus comprising a plurality of interfaces for connection to a plurality of links forming a bundle; and

means for forwarding the packet if the packet passes said RPF check;

wherein said RPF cheek comprises:

verification that the interface receiving the packet is connected to o»e of the links in said bundle identified in said lookup.

17. The apparatus of claim 16 wherein said bundle comprises an equal cost multi-path bundle and said lookup is based on a source address in the packet.

1 8. The apparatus of claim 16 wherein performing said RPF check comprises performing a security binding check for tmicast.

19. The apparatus of claim 16 wherein said plurality of links are connected to Protocol Independent Multicast (ΡΪΜ) routers and said lookup is based on a multicast- group address in the packet,

20. The apparatus of claim 16 wherein the apparatus is configured to perform the lookup in hardware.