`
`111111111111111111111111111!!),1!11111121,1111111111111111111111111
`
`(12) United States Patent
`Natchu
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,243,593 B2
`Aug. 14, 2012
`
`(54) MECHANISM FOR IDENTIFYING AND
`PENALIZING MISBEHAVING FLOWS IN A
`NETWORK
`
`(75)
`
`Inventor: Vishnu Natchu, Santa Clara, CA (US)
`
`(73)
`
`Assignee: Sable Networks, Inc., Santa Clara, CA
`(US)
`
`* )
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1098 days.
`
`(21) Appl. No.: 11/022,599
`
`(22) Filed:
`
`Dec. 22, 2004
`
`(65)
`
`Prior Publication Data
`
`US 2006/0133280 Al
`
`Jun. 22, 2006
`
`(51) Int. Cl.
`GO1R 31/08
`G06F 11/00
`GO8C 15/00
`H04J 1/16
`HO4J 3/14
`H04L 1/00
`H04L 12/26
` 370/229
`(52) U.S. Cl.
` 370/229-236
`Search
`(58) Field of Classification
`
`See application file for complete search history.
`
`(2006.01)
`(2006.01)
`(2006.01)
`(2006.01)
`(2006.01)
`(2006.01)
`(2006.01)
`
`(56)
`
`References Cited
`
`370/353
`370/229
`370/401
`370/229
`709/224
`709/105
`370/235
`370/229
`370/230
`
`U.S. PATENT DOCUMENTS
`6,167,041 A * 12/2000 Afanador
`6,252,848 Bl *
`6/2001 Skirmont
`6,310,881 Bl * 10/2001 Zikan et al.
`6,934,250 Bl *
`8/2005 Kejriwal et al.
`7,113,990 B2 * 9/2006 Scifres et al.
`2002/0032717 Al * 3/2002 Malan et al.
`2005/0141426 Al *
`6/2005 Hou
`2005/0226149 Al * 10/2005 Jacobson et al.
`2010/0110889 Al *
`5/2010 Yazaki et al.
`* cited by examiner
`Primary Examiner — Xavier Szewai Wong
`(74) Attorney, Agent, or Firm — West & Associates, A PC;
`Stuart J. West; Shaun N. Sluman
`(57)
`ABSTRACT
`A mechanism is disclosed for identifying and penalizing mis-
`behaving flows in a network. In one implementation, a set of
`behavioral statistics are maintained for each flow. These
`behavioral statistics are updated as information packets
`belonging to a flow are processed. Based upon these behav-
`ioral statistics, a determination is made as to whether a flow is
`exhibiting undesirable behavior. If so, a penalty is imposed on
`the flow. In one implementation, this penalty causes packets
`belonging to the flow to have a higher probability of being
`dropped than packets belonging to other flows that do not
`exhibit undesirable behavior. In one implementation, in addi-
`tion to penalizing the flow, this penalty also has the effect of
`correcting the flow's behavior such that the flow exhibits less
`undesirable behavior after the penalty than before. By cor-
`recting the flow's behavior, the penalty makes it possible for
`the flow to become a non-misbehaving flow.
`
`44 Claims, 5 Drawing Sheets
`
`TO/FROM
`OTHER
`ROUTER
`
`ROUTER
`202a
`► LINE
`CARD
`~MFMI
`
`
`
`210a
`
`TO/FROM
`OTHER
`ROUTER
`
`• 202b
`
`,
`/
`
`LINE 1
`CARD
`MFM
`
`210b
`
`204
`/
`SWITCHING
`FABRIC
`206a
`2
`FABRIC
`CARD
`
`: 206b
`•
`FABRIC
`CARD
`
`• 206c
`• 2
`FABRIC
`CARD
`
`208
`2
`APPLICATION
`PROCESSOR
`
`102
`/
`
`202c
`
`LINE
`CARD
`MFM
`
`210c
`
`• 202d
`
`LINE
`CARD
`MFM
`
`210d
`
`TO/FROM
` OTHER
`ROUTER
`
`TO/FROM
` OTHER
`ROUTER
`
`Cloudflare - Exhibit 1001, page 1
`
`Cloudflare - Exhibit 1001, page 1
`
`

`

`wawa •sn
`
`noz `171 tnv
`
`S Jo 1 WIN
`
`Zll £6C'Ett8 Sfl
`
`/102b
`
`ROUTER
`
`102c
`/
`ROUTER
`
`7
`
`-100
`
`102a
`/
`ROUTER
`
`102d
`/
`ROUTER
`
`ROUTER
`
`102e
`
`ROUTER
`
`102f
`
`Fig. 1
`
`Cloudflare - Exhibit 1001, page 2
`
`Cloudflare - Exhibit 1001, page 2
`
`

`

`wawa •sn
`
`noz `171 tnv
`
`S Jo Z WIN
`
`Zll £6C'Ett8 Sfl
`
`102
`
` TO/FROM
`• OTHER
`ROUTER
`
`TO/FROM
`OTHER
`ROUTER
`
`202c
`2
`
`LINE 14
`CARD
`MFM
`
`210c
`
`• 202d
`2
`
`LINE
`CARD
`MFM
`
`210d
`
`204
`/
`
`206a
`2
`
`SWITCHING
`FABRIC
`FABRIC
`CARD
`FABRIC
`CARD
`FABRIC
`CARD
`
`• • 206b
`• 2
`
`.
`• 206c
`• 2
`
`20
`2
`
`APPLICATION
`PROCESSOR
`
`TO/FROM
`OTHER
`ROUTER
`
`ROUTER
` LINE 1
` CARD I
`
`202a
`
`[4_11/1
`
`210a
`
`•
`
`•
`
`• 202b
`
`LINE I
`CARD i
`LIMFM
`
`210b
`
`TO/FROM
`OTHER
`ROUTER
`
`Fig. 2
`
`Cloudflare - Exhibit 1001, page 3
`
`Cloudflare - Exhibit 1001, page 3
`
`

`

`U.S. Patent
`
`Aug. 14, 2012
`
`Sheet 3 of 5
`
`[ MAINTAIN BEHAVIORAL
`
`STATISTICS FOR FLOW
`
`DETERMINE WHETHER
`FLOW IS EXHIBITING
`UNDESIRABLE BEHAVIOR
`
`ENFORCE PENALTY ON
`FLOW IF FLOW IS
`EXHIBITING UNDESIRABLE
`BEHAVIOR
`
`US 8,243,593 B2
`
`302
`
`304
`
`306
`
`Fig. 3
`
`Cloudflare - Exhibit 1001, page 4
`
`Cloudflare - Exhibit 1001, page 4
`
`

`

`U.S. Patent
`
`Aug. 14, 2012
`
`Sheet 4 of 5
`
`US 8,243,593 B2
`
`402
`/
`
`FLOW ID
`
`BEHAVIORAL STATISTICS
`
`• TOTAL (T) BYTE COUNT
`• LIFE (L) DURATION SINCE INCEPTION
`• RATE (R) OF INFORMATION FLOW
`• NUMBER (N) OF PACKETS PROCESSED
`• AVERAGE (A) PACKET SIZE
`• BADNESS FACTOR (B)
`• TIMESTAMP
`• OTHER
`
`OTHER FLOW INFORMATION
`
`'-•
`
`Eig. 4
`
`Cloudflare - Exhibit 1001, page 5
`
`Cloudflare - Exhibit 1001, page 5
`
`

`

`wawa •sn
`
`noz `171 tnv
`
`S Jo S WIN
`
`Zll £6C'Ett8 Sfl
`
`r
`
`16 MAXIMUM BADNESS FACTOR
`
`1 DEFAULT BADNESS FACTOR
`
`T
`TTHRESHOLD
`
`L
`LTHRESHOLD
`
`R
`R THRESHOLD
`
`TOTAL BYTE COUNT COMPONENT
`
`DURATION COMPONENT
`
`RATE COMPONENT
`
`A-A THRESHOLD
`AVERAGE PACKET
`MTU-A THRESHOLD SIZE COMPONENT
`
`BADNESS FACTOR = MIN <
`
`Eig. 5
`
`Cloudflare - Exhibit 1001, page 6
`
`Cloudflare - Exhibit 1001, page 6
`
`

`

`US 8,243,593 B2
`US 8,243,593 B2
`
`1
`1
`MECHANISM FOR IDENTIFYING AND
`MECHANISM FOR IDENTIFYING AND
`PENALIZING MISBEHAVING FLOWS IN A
`PENALIZING MISBEHAVING FLOWS IN A
`NETWORK
`NETWORK
`
`BACKGROUND
`BACKGROUND
`
`2
`2
`In one embodiment, a flow is processed as follows. One or
`In one embodiment, a flow is processed as follows. One or
`more information packets belonging to the flow are received
`more information packets belonging to the flow are received
`and processed. As the information packets are processed, a set
`and processed. As the information packets are processed, a set
`of behavioral statistics are maintained for the flow. These
`of behavioral statistics are maintained for the flow. These
`5 behavioral statistics reflect the empirical behavior of the flow.
`5 behavioral statistics reflect the empirical behavior of the flow.
`In one embodiment, the behavioral statistics include a total
`In one embodiment, the behavioral statistics include a total
`With the advent of file sharing applications such as KaZaA,
`With the advent of file sharing applications such as KaZaA,
`byte count (sum of all of the bytes in all of the packets of the
`byte count (sum of all of the bytes in all of the packets of the
`Gnutella, BearShare, and Winny, the amount of peer-to-peer
`Gnutella, BearShare, and Winny, the amount of peer-to-peer
`flow that have been processed up to the current time), a life
`flow that have been processed up to the current time), a life
`(P2P) traffic on the Internet has grown immensely in recent
`(P2P) traffic on the Internet has grown immensely in recent
`duration (how long the flow has been in existence since incep-
`duration (how long the flow has been in existence since incep-
`years. In fact, it has been estimated that P2P traffic now
`years. In fact, it has been estimated that P2P traffic now
`10 tion), a flow rate (derived by dividing the total byte count by
`lO tion), a flow rate ( derived by dividing the total byte count by
`represents about 50-70 percent of the total traffic on the
`represents about 50-70 percent of the total traffic on the
`the life duration of the flow), and an average packet size
`the life duration of the flow), and an average packet size
`Internet. This is so despite the fact that the number of P2P
`Internet. This is so despite the fact that the number of P2P
`( derived by dividing the total byte count by the total number
`(derived by dividing the total byte count by the total number
`users is quite small compared to the number of non P2P users.
`users is quite small compared to the number of non P2P users.
`of packets in the flow that have been processed). These behav-
`of packets in the flow that have been processed). These behav-
`Thus, it appears that most of the bandwidth on the Internet is
`Thus, it appears that most of the bandwidth on the Internet is
`15 ioral statistics are updated as information packets belonging
`15 ioral statistics are updated as information packets belonging
`being consumed by just a minority of the users. For this and
`being consumed by just a minority of the users. For this and
`to the flow are processed; thus, they provide an up to date
`to the flow are processed; thus, they provide an up to date
`other reasons, P2P traffic is viewed by ISP' s (Internet service
`other reasons, P2P traffic is viewed by ISP' s (Internet service
`reflection of the flaw's behavior.
`reflection of the flow's behavior.
`providers) and others as being abusive/misbehaving traffic
`providers) and others as being abusive/misbehaving traffic
`Based at least partially upon the behavioral statistics, a
`Based at least partially upon the behavioral statistics, a
`that should be controlled and penalized.
`that should be controlled and penalized.
`determination is made as to whether the flow is exhibiting
`determination is made as to whether the flow is exhibiting
`In order to control P2P traffic, however, it first needs to be
`In order to control P2P traffic, however, it first needs to be
`undesirable behavior. In one embodiment, this determination
`20 undesirable behavior. In one embodiment, this determination
`identified. Earlier generations of P2P protocols used fixed 20
`identified. Earlier generations of P2P protocols used fixed
`may be made by computing a badness factor for the flow. This
`may be made by computing a badness factor for the flow. This
`TCP port numbers for their transmissions. For example, Fast(cid:173)
`TCP port numbers for their transmissions. For example, Fast-
`badness factor is computed based, at least partially, upon the
`badness factor is computed based, at least partially, upon the
`Track used TCP port 1214. This made P2P traffic easy to
`Track used TCP port 1214. This made P2P traffic easy to
`behavioral statistics, and this badness factor provides an indi(cid:173)
`behavioral statistics, and this badness factor provides an indi-
`identify. Current P2P protocols, however, no longer have to
`identify. Current P2P protocols, however, no longer have to
`cation as to whether the flow is exhibiting undesirable behav-
`use fixed port numbers. Rather, they can be configured to use
`use fixed port numbers. Rather, they can be configured to use
`cation as to whether the flow is exhibiting undesirable behav-
`random dynamic port numbers so that P2P traffic can now be 25
`random dynamic port numbers so that P2P traffic can now be
`ior. In one embodiment, the badness factor also provides an
`25 ior. In one embodiment, the badness factor also provides an
`masqueraded as other types of traffic, such as HTTP web
`masqueraded as other types of traffic, such as HTTP web
`indication of the degree to which the flow is misbehaving.
`indication of the degree to which the flow is misbehaving.
`browsing and unspecified TCP traffic. As a result, the current
`browsing and unspecified TCP traffic. As a result, the current
`If the flow is exhibiting undesirable behavior, then a pen(cid:173)
`If the flow is exhibiting undesirable behavior, then a pen-
`P2P protocols have rendered the port-based identification
`P2P protocols have rendered the port-based identification
`alty may be enforced on the flow. In one embodiment, the
`alty may be enforced on the flow. In one embodiment, the
`techniques ineffective.
`techniques ineffective.
`penalty to be enforced is determined based, at least partially,
`penalty to be enforced is determined based, at least partially,
`Another technique that has been used to identify P2P traffic 30
`Another technique that has been used to identify P2P traffic
`30 upon the badness factor. This penalty may be an increased
`upon the badness factor. This penalty may be an increased
`involves the use of signatures. Specifically, it was observed
`involves the use of signatures. Specifically, it was observed
`drop rate. When enforced on the flow, this increased drop rate
`drop rate. When enforced on the flow, this increased drop rate
`that some P2P protocols inserted distinct information into
`that some P2P protocols inserted distinct information into
`causes the information packets belonging to the flow to have
`causes the information packets belonging to the flow to have
`their data packets. Using this distinct information as a signa(cid:173)
`their data packets. Using this distinct information as a signa-
`a higher probability of being dropped than information pack-
`a higher probability of being dropped than information pack-
`ture, it was possible to identify packets that were assembled
`ture, it was possible to identify packets that were assembled
`ets belonging to other flows that do not exhibit undesirable
`35 ets belonging to other flows that do not exhibit undesirable
`using those P2P protocols. This technique has several prob- 35
`using those P2P protocols. This technique has several prob-
`behavior. Thus, more packets may be dropped from the flow
`behavior. Thus, more packets may be dropped from the flow
`!ems. First, it usually is effective for only a relatively short
`lems. First, it usually is effective for only a relatively short
`than from other non-misbehaving flows. In one embodiment,
`than from other non-misbehaving flows. In one embodiment,
`period of time. As the P2P protocols evolve and mutate
`period of time. As the P2P protocols evolve and mutate
`this penalty is enforced on the flow only if a congestion
`this penalty is enforced on the flow only if a congestion
`(which they do on a fairly constant basis), their signatures
`(which they do on a fairly constant basis), their signatures
`condition is encountered. Thus, if there is no congestion, the
`condition is encountered. Thus, if there is no congestion, the
`change. Once that happens, the previous signatures are no
`change. Once that happens, the previous signatures are no
`flow (even if it is exhibiting undesirable behavior) is not
`40 flow (even if it is exhibiting undesirable behavior) is not
`longer valid, and the technique will have to be changed to 40
`longer valid, and the technique will have to be changed to
`penalized.
`penalized.
`recognize the new signatures. Another and more serious prob(cid:173)
`recognize the new signatures. Another and more serious prob-
`In one embodiment, enforcing the penalty on the flow has
`In one embodiment, enforcing the penalty on the flow has
`lem is that the P2P protocols are now evolving to the point that
`lem is that the P2P protocols are now evolving to the point that
`the effect of correcting the flaw's behavior. That is, enforcing
`the effect of correcting the flow's behavior. That is, enforcing
`they either leave no signature or they obfuscate their signa(cid:173)
`they either leave no signature or they obfuscate their signa-
`the penalty causes the badness factor of the flow to improve
`the penalty causes the badness factor of the flow to improve
`tures ( e.g. by encryption). This makes it extremely difficult if
`tures (e.g. by encryption). This makes it extremely difficult if
`45 (e.g. decrease). As a result, by application of the penalty, a
`not impossible to identify P2P traffic using signatures.
`( e.g. decrease). As a result, by application of the penalty, a
`not impossible to identify P2P traffic using signatures.
`45
`Overall, P2P protocols have gotten quite sophisticated, and
`Overall, P2P protocols have gotten quite sophisticated, and
`currently misbehaving flow can be turned into a non-misbe(cid:173)
`currently misbehaving flow can be turned into a non-misbe-
`the more sophisticated they become, the more difficult it is to
`the more sophisticated they become, the more difficult it is to
`having flow in the future. Once the flow is no longer misbe(cid:173)
`having flow in the future. Once the flow is no longer misbe-
`identify P2P traffic. Unless P2P traffic can be identified, it
`identify P2P traffic. Unless P2P traffic can be identified, it
`having, it is no longer subject to penalty. In this manner, a
`having, it is no longer subject to penalty. In this manner, a
`cannot be effectively controlled.
`cannot be effectively controlled.
`mis behaving flow can be identified, penalized, and even reha-
`misbehaving flow can be identified, penalized, and even reha-
`50 bilitated in accordance with one embodiment of the present
`50 bilitated in accordance with one embodiment of the present
`invention.
`invention.
`
`SUMMARY
`SUMMARY
`
`In accordance with one embodiment of the present inven(cid:173)
`In accordance with one embodiment of the present inven-
`tion, there is provided a mechanism for effectively identifying
`tion, there is provided a mechanism for effectively identifying
`and penalizing misbehaving information packet flows in a 55
`and penalizing misbehaving information packet flows in a
`55
`network. This mechanism may be applied to any type of
`network. This mechanism may be applied to any type of
`network traffic including, but certainly not limited to, P2P
`network traffic including, but certainly not limited to, P2P
`traffic. In one embodiment, misbehaving flows are identified
`traffic. In one embodiment, misbehaving flows are identified
`based upon their observed behavior. Unlike the prior
`based upon their observed behavior. Unlike the prior
`approaches, they are not identified based upon ancillary fac-
`approaches, they are not identified based upon ancillary fac-
`tors, such as port numbers and signatures. Because misbehav(cid:173)
`tors, such as port numbers and signatures. Because misbehav-
`ing flows are identified based upon their observed behavior,
`ing flows are identified based upon their observed behavior,
`and because their behavior cannot be hidden, misbehaving
`and because their behavior cannot be hidden, misbehaving
`flows cannot avoid detection. Thus, regardless of which pro(cid:173)
`flows cannot avoid detection. Thus, regardless of which pro-
`tocols they use, or how those protocols try to hide/obfuscate 65
`tocols they use, or how those protocols try to hide/obfuscate
`65
`their nature, misbehaving flows can be identified. Once iden(cid:173)
`their nature, misbehaving flows can be identified. Once iden-
`tified/detected, they can be controlled and/or penalized.
`tified/detected, they can be controlled and/or penalized.
`
`60
`60
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows an overview of a network in which one
`FIG. 1 shows an overview of a network in which one
`embodiment of the present invention may be implemented.
`embodiment of the present invention may be implemented.
`FIG. 2 is a blockdiagramofarouterin which one embodi(cid:173)
`FIG. 2 is a block diagram of a router in which one embodi-
`ment of the present invention may be implemented.
`ment of the present invention may be implemented.
`FIG. 3 is an operational flow diagram showing the opera(cid:173)
`FIG. 3 is an operational flow diagram showing the opera-
`tion of a misbehaving flow manager (MFM) in accordance
`tion of a misbehaving flow manager (MFM) in accordance
`with one embodiment of the present invention.
`with one embodiment of the present invention.
`FIG. 4 is a diagram of a sample flow block in accordance
`FIG. 4 is a diagram of a sample flow block in accordance
`with one embodiment of the present invention.
`with one embodiment of the present invention.
`FIG. 5 shows one possible function for computing a bad(cid:173)
`FIG. 5 shows one possible function for computing a bad-
`ness factor for a flow in accordance with one embodiment of
`ness factor for a flow in accordance with one embodiment of
`the present invention.
`the present invention.
`Cloudflare - Exhibit 1001, page 7
`
`Cloudflare - Exhibit 1001, page 7
`
`

`

`US 8,243,593 B2
`US 8,243,593 B2
`
`5
`5
`
`Information Routing
`Information Routing
`
`3
`3
`DETAILED DESCRIPTION OF
`DETAILED DESCRIPTION OF
`EMBODIMENT(S)
`EMBODIMENT(S)
`
`Network Overview
`Network Overview
`
`Router Overview
`Router Overview
`
`With reference to FIG. 1, there is shown an overview of a
`With reference to FIG. 1, there is shown an overview of a
`network 100 in which one embodiment of the present inven(cid:173)
`network 100 in which one embodiment of the present inven-
`tion may be implemented. As shown, the network 100 com(cid:173)
`tion may be implemented. As shown, the network 100 com-
`prises a plurality of routers 102 interconnected to each other
`prises a plurality of routers 102 interconnected to each other
`by trunks or links in such a way that each router 102 has
`by trunks or links in such a way that each router 102 has
`multiple possible paths to every other router 102. For
`multiple possible paths to every other router 102. For
`example, information from router 102a may reach router
`example, information from router 102a may reach router
`102d by going through routers 102b and 102c, or routers 102e
`102d by going through routers 102b and 102c, or routers 102e
`and 102/, and information from router 102c may reach router
`and 102f, and information from router 102c may reach router
`102a by going through router 102b or router 102e. Intercon(cid:173)
`102a by going through router 102b or router 102e. Intercon-
`necting the routers 102 in this way provides flexibility in
`necting the routers 102 in this way provides flexibility in
`determining how information from one router 102 is deliv(cid:173)
`determining how information from one router 102 is deliv-
`ered to another, and makes it possible to route around any
`ered to another, and makes it possible to route around any
`failures that might arise. For the sake of simplicity, only a few
`failures that might arise. For the sake of simplicity, only a few
`routers 102 are shown in FIG. 1; however, it should be noted
`routers 102 are shown in FIG. 1; however, it should be noted
`that network 100 may be much more complex if so desired,
`that network 100 may be much more complex if so desired,
`comprising more routers 102, more connections between the
`comprising more routers 102, more connections between the
`routers 102, and other components.
`routers 102, and other components.
`In addition to being coupled to each other, each router 102
`In addition to being coupled to each other, each router 102
`may further be coupled to various machines (not shown), such
`may further be coupled to various machines (not shown), such
`as clients and servers, from which information originates and
`as clients and servers, from which information originates and
`to which information is destined. By going through the rout(cid:173)
`to which information is destined. By going through the rout-
`ers 102, each of these machines may send information to any
`ers 102, each of these machines may send information to any
`of the other machines in the network 100.
`of the other machines in the network 100.
`Information is conveyed from one router 102 to another via
`Information is conveyed from one router 102 to another via
`a physical link or trunk. Depending on the type of network,
`a physical link or trunk. Depending on the type of network,
`this link or trunk may be an optical medium ( e.g. an optical
`this link or trunk may be an optical medium (e.g. an optical
`fiber), a coaxial cable, or some other type of medium. For
`fiber), a coaxial cable, or some other type of medium. For
`purposes of the present invention, network 100 may use any
`purposes of the present invention, network 100 may use any
`type of transport medium.
`type of transport medium.
`
`4
`4
`ing fabric 204 routes information through the router 102 and
`ing fabric 204 routes information through the router 102 and
`sends it on its way to the next hop (i.e. the next router).
`sends it on its way to the next hop (i.e. the next router).
`Information is thus received and routed by the router 102.
`Information is thus received and routed by the router 102.
`To increase the flexibility of the router 102 and to facilitate
`To increase the flexibility of the router 102 and to facilitate
`the process of failure recovery, each line card 202, in one
`the process of failure recovery, each line card 202, in one
`embodiment, has multiple connections to the switching fabric
`embodiment, has multiple connections to the switching fabric
`204. In addition, the switching fabric 204 provides multiple
`204. In addition, the switching fabric 204 provides multiple
`routes for connecting each line card connection to every other
`routes for connecting each line card connection to every other
`line card connection. With such a setup, each line card 202 has
`line card connection. With such a setup, each line card 202 has
`10 multiple routes to every other line card 202 in the router 102.
`10 multiple routes to every other line card 202 in the router 102.
`For example, one possible route from line card 202d to line
`For example, one possible route from line card 202d to line
`card 202a may pass through fabric card 206c, while another
`card 202a may pass through fabric card 206c, while another
`route may pass through fabric card 206b. By providing mul(cid:173)
`route may pass through fabric card 206b. By providing mul-
`tiple routes between the various line cards 202, the switching
`tiple routes between the various line cards 202, the switching
`15 fabric 204 makes it possible to route around any internal
`15 fabric 204 makes it possible to route around any internal
`failures that may arise.
`failures that may arise.
`In addition to the line cards 202 and the switching fabric
`In addition to the line cards 202 and the switching fabric
`204, the router 102 further comprises an application proces(cid:173)
`204, the router 102 further comprises an application proces-
`sor 208. In one embodiment, the application processor 208
`sor 208. In one embodiment, the application processor 208
`20 determines the forwarding paths, and hence, the egress line
`20 determines the forwarding paths, and hence, the egress line
`cards, that can be used to forward information to any particu(cid:173)
`cards, that can be used to forward information to any particu-
`lar destination address. Put another way, given a destination
`lar destination address. Put another way, given a destination
`address, the application processor 208 determines which line
`address, the application processor 208 determines which line
`card 202 or line cards are most suitable to act as the egress line
`card 202 or line cards are most suitable to act as the egress line
`25 card to forward information to that destination address. For
`25 card to forward information to that destination address. For
`example, suppose that the router 102 in FIG. 2 is router 102b
`example, suppose that the router 102 in FIG. 2 is router 102b
`in network 100, and that the destination is a machine coupled
`in network 100, and that the destination is a machine coupled
`to router 102d. Suppose further that line card 202c is coupled
`to router 102d. Suppose further that line card 202c is coupled
`to router 102c and line card 202d is coupled to router 102/ In
`to router 102c and line card 202d is coupled to router 102f. In
`30 such a case, because the most direct routes to router 102d are
`30 such a case, because the most direct routes to router 102d are
`through either router 102c or 102/, the most suitable egress
`through either router 102c or 102f the most suitable egress
`line cards for forwarding information to the destination router
`line cards for forwarding information to the destination router
`102d are probably line cards 202c and 202d. Accordingly, the
`102d are probably line cards 202c and 202d. Accordingly, the
`application processor 208 designates these line cards 202c,
`application processor 208 designates these line cards 202c,
`35 202d as potential egress line cards for destination router 102d,
`35 202d as potential egress line cards for destination router 102d,
`with one being designated as the primary egress line card and
`with one being designated as the primary egress line card and
`the other being the alternate.
`the other being the alternate.
`Once the egress line card determinations are made by the
`Once the egress line card determinations are made by the
`FIG. 2 shows a block diagram of a sample router 102 that
`FIG. 2 shows a block diagram of a sample router 102 that
`application processor 208 for each destination address, they
`application processor 208 for each destination address, they
`may be used to implement one or more of the routers 102 in
`may be used to implement one or more of the routers 102 in
`40 are communicated to each of the line cards 202 in the router
`40 are communicated to each of the line cards 202 in the router
`network 100. As shown in FIG. 2, the router 102 comprises a
`network 100. As shown in FIG. 2, the router 102 comprises a
`102. In turn, each line card 202 stores the information into a
`102. In turn, each line card 202 stores the information into a
`plurality ofline cards 202 for coupling the router 102 to one
`plurality of line cards 202 for coupling the router 102 to one
`forwarding table residing on the line card 202. Thereafter,
`forwarding table residing on the line card 202. Thereafter,
`or more of the other routers 102 in the network 100. For
`or more of the other routers 102 in the network 100. For
`when a line card 202 acts as an ingress line card and receives
`when a line card 202 acts as an ingress line card and receives
`example, assuming that the router 102 in FIG. 2 is router 102b
`example, assuming that the router 102 in FIG. 2 is router 102b
`a set of information, it can use the forwarding table to deter(cid:173)
`a set of information, it can use the forwarding table to deter-
`in network 100, line card 202d may couple router 102b to 45
`in network 100, line card 202d may couple router 102b to
`mine the appropriate egress line card 202 to which to forward
`45 mine the appropriate egress line card 202 to which to forward
`router 102/, line card 202c may couple router 102b to router
`router 102f, line card 202c may couple router 102b to router
`the information. Because the egress line card information is
`the information. Because the egress line card information is
`102c, line card 202b may couple router 102b to router 102e,
`102c, line card 202b may couple router 102b to router 102e,
`predetermined and stored in the forwarding table, the ingress
`predetermined and stored in the forwarding table, the ingress
`and line card 202a may couple router 102b to router 102a.
`and line card 202a may couple router 102b to router 102a.
`line card simply has to perform a table lookup to determine
`line card simply has to perform a table lookup to determine
`Overall, the line cards 202 act as the router's 102 interfaces to
`Overall, the line cards 202 act as the router' s 102 interfaces to
`the proper egress line card. No on-the-fly calculation needs to
`the proper egress line card. No on-the-fly calculation needs to
`the rest of the network 100. In one embodiment, the trunks 50
`the rest of the network 100. In one embodiment, the trunks
`50 be performed. Since table lookup operations can be carried
`be performed. Since table lookup operations can be carried
`coupled to the line cards 202 are bi-directional; thus, each line
`coupled to the line cards 202 are bi-directional; thus, each line
`out very quickly, the process of determining the proper egress
`out very quickly, the process of determining the proper egress
`card 202 may receive information from another router, or
`card 202 may receive information from another router, or
`line card requires relatively little time.
`line card requires relatively little time.
`send information to another router. Put another way, each line
`send information to another router. Put another way, each line
`card 202 is capable of acting as an ingress line card (to receive
`card 202 is capable of acting as an ingress line card (to receive
`information from another router) or an egress line card (to 55
`information from another router) or an egress line card (to 55
`In one embodiment, information is routed from router to
`send information to another router). Whether a particular line
`In one embodiment, information is routed from router to
`send information to another router). Whether a particular line
`router, and from line card 202 to line card 202, in the form of
`card 202 is acting as an ingress or an egress line card at any
`router, and from line card 202 to line card 202, in the form of
`card 202 is acting as an ingress or an egress line card at any
`information packets. Each packet represents a set ofinforma(cid:173)
`particular time depends upon the flow of network traffic.
`information packets. Each packet represents a set of informa-
`particular time depends upon the flow of network traffic.
`To couple the line cards 202 to each other within the router
`tion that is sent by a source to