(12) United States Patent
`Subramanian et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,860,999 B1
`9
`*Dec. 28 2010
`
`US007860999Bl
`
`................. .. 709/235
`5,377,327 A * 12/1994 Jain etal.
`5,495,426 A *
`2/1996 Waclawsky et al.
`709/226
`5,845,091 A * 12/1998 Dunne et al.
`709/240
`
`
`
`Ea1I13°n:Ita1'
`2 :
`709;238
`1.
`e Ou ec et
`,
`,
`370 351
`6/2000 Vaid etal.
`..... ..
`6,078,953 A *
`709/223
`6,151,633 A * 11/2000 H t
`t
`1.
`709/235
`6,226,267 B1*
`5/2001 S15ii1Sn:y:tal.
`............ .. 370/235
`6,286,052 B1*
`9/2001 McCl0ghrie t
`1.
`709/238
`6,289,389 B1*
`9/2001 Kikinis ....
`709/239
`6,421,734 B1*
`7/2002 Nessettetal. ............. .. 709/247
`6,424,621 B1 *
`7/2002 Ramaswamy et al.
`..... .. 370/230
`6,570,867 B1*
`5/2003 Robinson et al.
`.... ..
`370/351
`6,611,872 131*
`8/2003 MCC/anne ........ ..
`709/238
`6,611,874 B1 *
`8/2003 Denecheau et al.
`....... .. 709/239
`6,701,363 B1*
`3/2004 Chiu et al.
`................ .. 709/224
`6,792,461 Bl*
`9/2004 Hericourt
`6,868,061 B1*
`3/2005 Kilkkiet al.
`........... .. 370/230.1
`
`(54) DISTRIBUTED COMPUTATION IN
`NETWORK DEVICES
`
`(75)
`
`Inventors: Siva Subramanian, Cary, NC (US); Tal
`.
`I'La"“"‘= S“‘my"a1e>CA(US)
`.
`.
`.
`(733 Asslgnee Amy“ 1"“-s Baskmg Rldges NJ (US)
`.
`I
`I
`I
`I
`(*1 N0t1CeI
`SuhJeCt t0 any dlselalmeri the term Ofthls
`patent is extended or adjusted under 35
`U.S.C. 154(1)) by 1839 days.
`
`atent is sub'ect to a terminal dis-
`This
`P
`J
`clajmer.
`
`(21) APPIINOII 09/736,678
`
`(22)
`
`Filed:
`
`Dec. 13, 2000
`
`=I< Cited by examiner
`
`60
`
`)
`
`51
`
`(
`
`(
`
`Related U.S. Application Data
`0
`I
`I.
`I. N 60/239 484 fil d
`.
`.
`P
`rovlslona app lcalon 0‘
`’
`’
`e on Ct‘
`11, 2000.
`I t. Cl.
`(2006.01)
`) Gn06F 15/16
`(2006.01)
`G06F 15/173
`(52) U.S. Cl.
`..................... .. 709/238; 709/235; 370/229;
`370/230. 1; 370/23 1; 370/234
`(58) Field of Classification Search ............... .. 709/235,
`709/238; 370/229, 230.15 231, 235, 234
`See apphcatjon me for c0mp1eIe Search history.
`_
`Referenees Clted
`U.S. PATENT DOCUMENTS
`
`(56)
`
`Primal?’ Ex‘1mi”@7’”A1‘i0 Etienne
`Assistant Examiner—Avi Gold
`(74) Attorney, Agent, or Firm—Winthrow & Terranova,
`PLLC
`
`ABSTRACT
`(57)
`The present invention facilitates routing trafiic overanetwork
`and distributing application level support among multiple
`routing devices during routing. Routing nodes are configured
`to Process the Content of the traffie to provide the requisite
`application level support. The traffic is routed, in part, based
`on the resources available for providing the processing. The
`processing of the traffic may be distributed throughout the
`network based on processing capacity of the routing nodes at
`any given time and given the amount of network congestion.
`
`5,167,033 A *
`
`ll/1992 Bryant et al.
`
`............. .. 709/235
`
`50 Claims, 9 Drawing Sheets
`
`CONTROL PLANE
`12
`
`CONTROL
`
`RECEIVE PACKET
`
`212
`
`214
`
`1
`-
`-
`.EP1:18fi%SI§1§fi8E$1;s
`SE CONFIGURATIONS FOR
`COMPUTE OR
`FORWARD PLANES
`
`216
`PREPARE PACKET OR RESPONSE
`FOR SENDING TO A DESTINATION
`IF NECESSARY
`
`I
`I
`
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`
`FORWARD PLANE
`16
`START
`
`2°‘)
`
`202
`
`RECEIVE PACKET
`
`FILTER PACKET BASED
`ON FORWARDING RULES
`
`204
`
`
`206
`
`TO coNTI§8iMe'bRIv'1PuTE OR
`NEXT—HOP/DESTINATION
`
`
`
`NEXIHOPI
`DESTINATION
`
`PROCESS PACKET IF NECESSARY
`
`1'-E HEADER MAN'PULAT‘0"'>
`
`FORWARD PACKET TO NEXT—HOP/
`
`I
`
`DESTINATION
`
`,:-210
`
`COMPUTE PLANE
`14
`
`COMPUTE
`
`RECEIVE PACKET
`
`E§£?§EfioP0%§EES%‘1
`COMPUTE FUNCTIONS
`(TYPICALLY DATA/PAYLOAD
`MANIPULATION)
`
`SEND PROCESSED PACKET
`TO FORWARD PLANE
`IF NECESSARY
`
`218
`
`220
`
`222
`
`1
`I
`I
`1
`
`|
`
`I
`
`1
`
`ARISTA 1110
`
`1
`
`ARISTA 1110
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 1 of9
`
`Us 7,860,999 B1
`
`FIG.1A
`
`2
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 2 of9
`
`Us 7,860,999 B1
`
`FIG.1B
`
`3
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 3 of9
`
`Us 7,860,999 B1
`
`FIG.1C
`
`4
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 4 of9
`
`Us 7,860,999 B1
`
`FIG.1D
`
`5
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 5 of9
`
`Us 7,860,999 B1
`
`I00
`
`102
`
`104
`
`106
`
`108
`
`110
`
`112
`
`IDENTIFY PROCESSING RESOURCES
`REQUIRED FOR TRAFFIC DELIVERY
`FROM SOURCE TO DESTINATION
`
`
`
`IDENTIFY POSSIBLE PATH(S) BETWEEN
`SOURCE AND DESTINATION WITH
`PROCESSING CAPABILITY
`
`IDENTIFY PROCESSING RESOURCES
`AVAILABLE FOR PATH(S)
`
`SELECT PATH FOR
`TRAFFIC DELIVERY
`
`DETERMINE RESOURCE ALLOCATION
`ALONG SELECTED PATH
`
`RESERVE RESOURCES
`FOR SELECTED PATH
`
`TRANSPORT TRAFFIC FROM SOURCE
`TO DESTINATION ALONG SELECTED PATH
`
`FIG. 2
`
`6
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 6 of9
`
`Us 7,860,999 B1
`
`/0
`
`CONTROL PLANE
`
`1.2
`
`COMPUTE SERVICES
`
`NETWORK SERVICES
`
`E
`
`2.9
`
`COMPUTE API
`
`NETWORK ARI
`
`22
`
`gg
`
`
`
`
`
`
`
`
`
`COMPUTE PLANE
`14
`
`FORWARD PLANE
`
`l§
`
`FIG. 3
`
`/10
`
`CONTROL PLANE
`
`E
`
`COMPUTE SERVICES
`
`NETWORK SERVICES
`
`E
`
`.22
`
`COMPUTE API
`
`NET ORK ARI
`
`2
`
`E
`
`COMPUTE PLANE
`14
`
`FORWARD PLANE
`16
`
`F0 RWARDED
`PACKETS
`
`FIG. 4
`
`7
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 7 of9
`
`Us 7,860,999 B1
`
`/-10
`
`CONTROL PLANE
`
`E
`
`S
`
`COMPUTE SERVICES
`
`NETWORK SERVICES
`
`1_s
`
`20
`
`COMPUTE API
`
`NE
`
`ORK API
`
`2
`
`E
`
`COMPUTE PLANE
`
`FORWARD PLANE
`16
`
`PACKETS
`MANIPULATED BY
`COMPUTE PLANE
`
`FIG. 5
`
`CONTROL PLANE
`
`CONFIGURATION
`INSTRUCTIONS
`
`1_2
`
`6
`
`COMPUTE SERVICES
`
`NETWORK SERVICES
`
`E
`
`E
`
`COMPUTE API
`
`'
`
`NETWORK API
`
`.23
`
`_4
`
`COMPUTE PLANE
`
`FORWARD PLANE
`
`E
`
`1
`
`PACKETS DIRECTED
`TO CONTROL PLANE
`
`FIG. 6
`
`8
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 8 of9
`
`Us 7,860,999 B1
`
`qr_mr_NF
`
`«om
`
`
`
`520$m_>_m_om_m
`
`._.m<._.w
`
`mom
`
`
`
`
`
`om_m<m_._.mv_0<n_mm5_u_
`
`
`
`mm_._:moz_om<>>mon_ZO
`
`ma
`
`ONN
`
`
`
`Exoim_>_momE
`
`
`
`mom_.m_xo<n_mmmooma
`
`
`
`zonm_m<mZO_._.<O_u_n_n_<
`
`
`
`mzoiozimEE_>_oo
`
`n_<o4><n_>fi<a>j<o_n:E
`AZO_._.<:_Dn__Z<_>_
`
`
`
`
`
`
`
`._.m_xO<n_ommmmoommozmm
`
`
`
`mz<._n_nE<>>mouO._.
`
`>m<mmm_om_zn__
`
`
`
`m:E_>_oo._oEzoo
`
`Qn_o:.cmz
`SE289
`
`
`
`>m<mmmom_zm.Exoimwmooma
`
`
`
`Azo:<.5n__z<_>_mm_o<m:ma
`
`NGE
`
`
`
`\n_O_.E.XmZOHEv_o<n_nE<>>mo¢
`
`ZO_._.<Z_._.wm_n_
`
`
`
`._.m_v_O<n_m_>_m_om_m
`
`
`
`Ev_o<n_mwmoomm
`
`
`momwzo:<m:o:zo.o¢m_m
`mofimozoso23¢m._
`
`mom_Sn__>_oo
`
`
`
`mmzfimom<>>mou_
`
`ma
`
`im
`
`
`
`mmzonammmom_v_o<n_mm<n_mmn_
`
`
`
`ZO_._.<z_._.wm_n_<O._.ozazmmmom
`
`>m<mmmomzn:
`
`
`
`
`
`mz<._n_.u._._.Dn__>_O0mz<._n_nE<2Eon_mz<._n_._oEzoo
`
`
`
`
`
`
`
`9
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Dec. 28,2010
`
`Sheet 9 of9
`
`Us 7,860,999 B1
`
`om<>>mon_
`
`momwmoomm
`
`mm
`
`oZoms§mom
`
`mmEI\mm_.Sm
`
`
`
` HmZ<.Eom<>>m_on_
`
`—Zl—LIJD’ZLL<OUJ
`
`m<oxm4<zm*
`
`e\
`
`m<oxa4<Zm
`
`m§—POI—Z0 N
`
`—z+mmu<om¢
`m<0xm4<zm”
`
`m_o<u_mm+z_ow
`
`mz<.Exo<m_
`
`m_o<u_mm»z_
`
`am
`
`:_Om._.ZOO
`
`mommmoomu
`
`mm
`
`»GE
`
`
`
`m_z<._n_Aomkzoo
`
`fl
`
`>mo_>_m_2
`
`Q.
`
`
`
`vEo>>Ezmommmooma
`
`
`
` Smz<._n_m_._.3a_>_OO
`
`>mo_>m__>_
`
`mm
`
`
`
`m_.5oo_>_>m<mm:
`
`$azofiozigov
`
`_.wOI
`
`10
`
`10
`
`
`
`
`
`
`
`
`

`
`1
`DISTRIBUTED COMPUTATION IN
`NETWORK DEVICES
`
`US 7,860,999 B1
`
`2
`
`This application claims the benefit of provisional applica-
`tion No. 60/239,484, filed Oct. 11, 2000, entitled COMPU-
`TATION IN NETWORK DEVICES, and is related to appli-
`cation Ser. No. 09/736,692, filed Dec. 13, 2000, entitled
`HIGH-SPEED COMPUTATION IN NETWORK DEVICES
`and Ser. No. 09/736,674, filed Dec. 13, 2000 entitled SER-
`VICE BASED ROUTING,
`the disclosures of which are
`incorporated herein by reference in their entirety.
`
`FIELD OF THE INVENTION
`
`The present invention relates to processing and routing
`packets in a network, and in particular, to distributing appli-
`cation level processing among one or more routing devices
`during high-speed routing.
`
`BACKGROUND OF THE INVENTION
`
`Existing routers have limited computation capacity and
`offer little or no application layer support during routing.
`These routers are typically divided into a control plane and a
`forward plane. The control plane is used for basic setup and
`control of the router. For example, the control plane is gen-
`erally used to establish routing tables used by the forward
`plane. The forward plane receives packets, processes the
`packets based on the routing tables set up by the control plane,
`and delivers the packets to the next-hop address or the final
`destination, depending on the termination point for each
`packet.
`The forward plane in existing routers is typically limited to
`packet delivery based on basic header analysis and manipu-
`lation. Historically, application layer support, such as that
`requiring analysis or manipulation of the packet’s payload,
`has been avoided. Those specially configured devices capable
`of providing application processing, such as firewalls, are
`uniquely configured for the special application wherein the
`routing speeds for normal routing in the forward plane are
`significantly impacted or the control plane is uniquely
`adapted to handle such processing. In either case, basic rout-
`ing capability of the forward plane is inhibited. Thus, tradi-
`tional network routers typically do not provide application
`level processing, and routing devices providing such support
`are only used in limited applications.
`Nortel Networks Limited is developing routing devices
`capable of providing application level processing without
`significantly impacting forwarding performance for the pack-
`ets being processed at an application level or for those requir-
`ing only basic routing. These routing devices are capable of
`providing various types of application level support to facili-
`tate any number of functions or network services.
`Although these routing devices provide application level
`support during routing, for any given traffic flow, a single
`device may not have the computational capacity to provide all
`ofthe processing for a given traffic flow. The capacity may be
`limited based on the routing device’s capability or the pro-
`cessing required for concurrent trafiic flows. Further, con-
`gested networks incorporating routing devices capable of
`providing application level support would be more efiicient if
`processing could be distributed to less congested devices,
`which are comparably capable.
`Thus, there is a need to distribute processing for applica-
`tion level support among routing devices capable ofproviding
`such support. There is a further need to be able to detect
`congested routing devices and direct traffic to routing devices
`
`with capacity for application level support without signifi-
`cantly impacting routing efficiency and speeds.
`
`SUMMARY OF THE INVENTION
`
`The present invention facilitates routing trafiic over a net-
`work and distributing application level support among mul-
`tiple routing devices during routing. Routing nodes are con-
`figured to process the content of the traffic to provide the
`requisite application level support. The trafiic is routed, in
`part, based on the resources available for providing the pro-
`cessing. The processing of the trafiic may be distributed
`throughout the network based on processing capacity of the
`routing nodes at any given time and given the amount of
`network congestion.
`When trafiic is routed, processing resources required for
`delivery of the trafiic from a source to the destination are
`determined. Since multiple routing paths may exist, one or
`more paths between the source and destination capable of
`providing the requisite application level support during rout-
`ing are identified. Next, the available processing resources in
`the possible paths are compared with the resources required
`for routing. One or more paths are then selected to optimize
`routing and minimize congestion. Upon selection of the one
`or more paths, the trafiic may be routed and processed accord-
`ingly.
`The requisite application level processing may be distrib-
`uted among multiple routing nodes and paths to make sure
`that suflicient resources are available and delivery does not
`negatively affect other traffic. The distribution ofthe process-
`ing is preferably based on available resources and perhaps on
`other network conditions bearing on the processing and rout-
`ing performance for the particular traffic flow, the network in
`general, or a combination thereof.
`Those skilled in the art will appreciate the scope of the
`present invention and realize additional aspects thereof after
`reading the following detailed description of the preferred
`embodiments in association with the accompanying drawing
`figures.
`
`BRIEF DESCRIPTION OF THE DRAWING
`FIGURES
`
`The accompanying drawing figures incorporated in and
`forming a part ofthe specification illustrate several aspects of
`the invention, and together with the description serve to
`explain the principles of the invention.
`FIG. 1A depicts a network including routing devices
`capable of providing application level support according to a
`preferred embodiment of the present invention.
`FIG. 1B depicts a first exemplary trafiic flow in the network
`of FIG. 1A wherein the trafiic flow receives application level
`support during routing.
`FIG. 1C depicts a second exemplary trafiic flow in the
`network of FIG. 1A wherein the trafiic flow receives applica-
`tion level support during routing.
`FIG. 1D depicts multiple exemplary traffic flows in the
`network of FIG. 1A wherein the trafiic flows receive applica-
`tion level support during routing.
`FIG. 2 is a flow diagram outlining the basic flow for dis-
`tributing application level processing for trafiic flow during
`routing according to a preferred embodiment of the present
`invention.
`
`FIG. 3 depicts a preferred architecture for a routing node
`constructed according to a preferred embodiment of the
`present invention.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`11
`
`11
`
`

`
`US 7,860,999 B1
`
`3
`FIG. 4 illustrates the forwarding path of packets processed
`within the forward plane of the architecture shown in FIG. 3.
`FIG. 5 illustrates the forwarding path of packets processed
`by the compute plane of the architecture shown in FIG. 3.
`FIG. 6 illustrates the forwarding path ofpackets directed to
`the control plane and the path of instructions for configuring
`the compute plane and forward plane from the control plane
`according to a preferred embodiment ofthe present invention.
`FIG. 7 is a flow diagram outlining the basic flow for pro-
`cessing packets in the control plane, compute plane, and/or
`the forward plane according to a preferred embodiment ofthe
`present invention.
`FIG. 8 is a block schematic of a preferred configuration of
`a routing node according to the present invention.
`
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`The present invention provides for distributing application
`level support among multiple routing devices during routing.
`The application layer support may include any type of pro-
`cessing or network service on packet content. The embodi-
`ments set forth below represent the necessary information to
`enable those skilled in the art to practice the invention and
`illustrate the best mode of practicing the invention. Upon
`reading the following description in light of the accompany-
`ing drawing figures, those skilled in the art will understand
`the concepts of the invention and will recognize applications
`of these concepts not particularly addressed herein. It should
`be understood that these concepts and applications fall within
`the scope of this disclosure and the accompanying claims.
`With reference to FIG. 1A, a network 2 is illustrated pro-
`viding for communications between an application server 4
`and a computing device 6, such as a personal computer. A
`communication server 8 may be provided to facilitate distri-
`bution of application level support among routing nodes 10
`that are capable of providing the application level support
`while routing trafiic between the application server 4 and the
`computing device 6. As will be discussed in greater detail
`below, the routing nodes 10 are capable of providing high-
`speed routing services in conjunction with processing content
`carried in the packets between the application server 4 and the
`computing device 6 during routing.
`The routing nodes 1 0 may take on any type of configuration
`capable of providing application level support on packet con-
`tent during routing. However, the preferred embodiment of
`the invention provides for configuring the routing nodes 10 to
`include three primary processing planes: a control plane 12, a
`compute plane 14, and a forward plane 16. Preferably, all
`incoming packets are received by the forward plane 16
`through various ports interacting with a network, such as a
`packet-switched network. The forward plane 16 is configured
`to analyze each ofthe incoming packets and determine where
`to send each packet. In general, the incoming packets need to
`be forwarded on toward their final destination, to the control
`plane 12, or to the compute plane 14.
`Preferably, any packet processing provided by the forward
`plane 16 is limited to manipulating information in one or
`more headers ofthe packet as necessary in traditional routing.
`Packets entering the forward plane 16 that require application
`level processing, which may entail manipulation of the pack-
`et’s payload, are directed to the compute plane 14 by the
`forward plane 16. After processing, the packets are returned
`to the forward plane 16 for further processing. Additional
`details of the configuration of the preferred routing node are
`outlined after a discussion of the concepts of the present
`invention.
`
`4
`
`An exemplary trafiic flow between the application server 4
`and a computing device 6 is shown in FIG. 1B. The routing
`nodes 10 are illustrated to depict the control plane 12, com-
`pute plane 14, and forward plane 16. In the present example,
`assume that the media flow is routed between the application
`server 4 and the computing device 6 through routing nodes
`10A, 10B and 10C. Further assume that each of the routing
`nodes 10A, 10B and 10C will provide application level pro-
`cessing on all or select packets constituting the trafiic flow.
`The traffic flow is illustrated by the solid line extending into
`the compute planes 14 through the forward planes 16 of each
`of the routing nodes 10A, 10B and 10C.
`With the trafiic flow depicted in FIG. 1B, application level
`processing provided by the routing nodes 10A, 10B and 10C
`may be distributed in a number ofways. For example, each of
`the routing nodes 10A, 10B and 10C may provide the same
`type of processing wherein each of the routing nodes 10A,
`10B and 10C provides processing for a certain portion of the
`traffic flow. As such, each of the routing nodes 10A, 10B and
`10C may process one third of the trafiic or routing node 10A
`may provide 80 percent of the processing wherein routing
`nodes 10B and 10C each provide 10 percent of the process-
`ing. Alternatively, each of the routing nodes 10A, 10B and
`10C may provide a different type of processing on the entire
`traffic flow. For example, routing node 10A may provide a
`compression application, routing node 10B may provide an
`encryption function and routing node 10C may provide an
`e-commerce related application on the compressed and
`encrypted traffic flow. Altematively, a network device or
`server along the way will be able to do all the computation.
`Actual distribution of the application layer support for the
`traffic flow may be facilitated by the communication server 8
`or by a protocol implemented between the routing nodes 10
`and perhaps the application server 4 or personal computer 6.
`If the communication server 8 is used to distribute processing
`throughout the network 2 among the compatible routing
`nodes 10, information is collected from each of the routing
`nodes 10 continuously or on a periodic basis to determine the
`resources available or the remaining processing capacity of
`the various routing nodes.
`An alternative traffic flow is depicted in FIG. 10 wherein
`the traffic flow is routed from the application server 4 to the
`personal computer 6 via routing devices 10A, 10D, and 10C.
`Notably, routing nodes 10A and 10C simply forward traffic
`while the routing node 10D provides application level pro-
`cessing. The solid line representing the trafiic flow extends
`into the compute plane 14 of routing node 10D, whereas the
`traffic fiow is solely handled by the forward plane 16 in
`routing nodes 10A and 10C. The trafiic flow may be config-
`ured in such a manner because routing nodes 1 0A and 1 0C are
`currently processing other trafiic to an extent that they lack
`sufficient capacity to handle all or any portion of the process-
`ing required for the trafiic flow depicted. Alternatively, rout-
`ing nodes 10A and 10C may not be configured to provide the
`same type ofprocessing as that provided in routing node 10D.
`FIG. 1D depicts three different traffic flows between the
`application server 4 and the computing device 6. The flows
`are represented by a solid line, a dotted line, and a dashed line.
`The traffic flow represented by the solid line is depicted as
`extending into the compute planes 14 ofeach ofrouting nodes
`10A, 10D, and 10C. As such, processing for application level
`support is distributed for that trafiic flow between each of the
`three routing nodes 10A, 10D, and 10C. The trafiic flows
`represented by the dotted and dashed lines are routed through
`routing nodes 10A, 10B, and 10C, respectively. For the traffic
`flow represented by the dotted line, application level support
`is only provided by routing nodes 10B and 10C, wherein
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`12
`
`12
`
`

`
`US 7,860,999 B1
`
`5
`routing node 10A operates to simply forward packets
`between the application server 4 and routing node 10B. The
`trafiic flow represented by the dashed line receives applica-
`tion level processing by routing nodes 10A and 10B, wherein
`routing node 10C merely forwards the packets between 10B
`and the computing device 6.
`Preferably, the routing and distribution of application level
`support for each trafiic flow is distributed to provide efiicient
`routing and processing. For example, if the trafiic flow rep-
`resented by the solid line was the first ofthe three trafiic flows
`initiated, the application level support was distributed evenly
`between routing nodes 10A, 10D, and 10C. If the trafiic flow
`represented by the dashed line was the second flow initiated,
`the application level support for the traffic flow may have
`been evenly distributed between routing nodes 10A and 10B.
`When the trafiic flow associated with the dotted line was
`
`initiated, a decision may have been made to avoid providing
`application level support by routing node 10A, due to its
`handling of the traffic flows represented by the solid and
`dasl1ed lines. Thus, for the trafiic flow represented by the
`dotted line, routing node 10A only forwards the traffic,
`wherein routing nodes 10B and 10C were less congested and
`had sufficient capacity to handle the application level support.
`Notably, distribution of the processing associated with
`application level support may be distributed based on avail-
`able resources or in an effort to maximize routing or process-
`ing speeds by distributing the processing among multiple
`routing nodes 10. The basic process of distributing applica-
`tion level support during routing is outlined in FIG. 2. Pref-
`erably, the process will begin by identifying the necessary
`processing resources required for delivery of trafiic from a
`source to the destination (block 100). As in the network 2
`depicted in FIGS. 1A through 1D, multiple routing paths will
`likely exist. Among these multiple paths, paths capable of
`providing the requisite application level support during rout-
`ing between the source and destination are identified (block
`102). Within the identified paths, available processing
`resources are identified to assist in distributing the application
`level support (block 104).
`A routing path for delivering trafiic between the source and
`destination is selected (block 106), preferably based on avail-
`able resources and perhaps based on other network conditions
`bearing on the processing and routing performance for the
`particular trafiic flow, for the network in general, or a combi-
`nation thereof. The ultimate goal is to provide the necessary
`application level support during routing and to route the traf-
`fic to meet quality and/or speed requirements. For example,
`streaming media traffic requiring application level support
`may need the traffic delivered with minimal packet loss and at
`a given rate. Other trafiic flows may require less speed and
`more accuracy. The distribution of the application level sup-
`port will
`facilitate meeting the routing and processing
`demands of the trafiic flows.
`Preferably, once the path is selected for trafiic delivery, the
`necessary resource allocation for providing the application
`level support along the selected path is determined (block
`108). In essence, the distribution of the application level
`support is determined. The routing nodes needed to provide
`the application level support are determined, and the amount
`of application level support provided by each of the routing
`nodes 10 is defined. Based on this distribution, resources may
`be reserved in the selected routing nodes 10 to ensure each of
`the routing nodes have the capacity and the ability to provide
`the application level support for the trafiic flow (block 110).
`Once the resources are reserved, traffic for the trafiic flow
`may be transported from the source to the destination along
`the selected path (block 112).
`
`6
`During transport, the selected routing nodes 10 will pro-
`vide the allocated application level support and routing func-
`tions necessary for delivery. The routing nodes 10 may coop-
`erate with one another alone or in combination with a
`
`communication server 8 to communicate capacity informa-
`tion using an acceptable protocol. The capacity information is
`used to determine whether a given flow may be processed in
`a node or nodes within the routing path. Processing is allo-
`cated and the capacity is reserved for the allocated processing
`prior to initiating traffic flow.
`With reference to FIG. 3, a routing node 10 is illustrated
`according to a preferred embodiment ofthe present invention.
`As noted above, the routing node 1 0 may be divided into three
`primary processing planes: a control plane 12, a compute
`plane 14, and a forward plane 16. Preferably, all incoming
`packets are received by the forward plane 16 through various
`ports interacting with a network, such as a packet-switched
`network. The forward plane 16 is configured to analyze each
`of the incoming packets and determine where to send each
`packet. In general, the incoming packets need to be forwarded
`on toward their final destination, to the control plane 12, or to
`the compute plane 14.
`Depending on the extent or nature of any necessary
`manipulation of the packet, the packet may be processed by
`the forward plane 16 and forwarded to the next-hop routing
`node or final destination. Preferably, any packet processing
`provided by the forward plane 16 is limited to manipulating
`information in one or more headers ofthe packet as necessary
`in traditional routing. As depicted in FIG. 4, packets requiring
`only traditional routing are maintained in the forward plane
`16 for processing and immediately forwarded to the next-hop
`routing node or destination.
`Packets entering the forward plane 16 that require applica-
`tion level processing, which may entail manipulation of the
`packet’s payload, are directed to the compute plane 14 by the
`forward plane 16. As depicted in FIG. 5, these packets are
`passed through the forward plane 16 to the compute plane 14
`for processing and then sent back to the forward plane 16,
`which will forward the processed packet to the next-hop
`routing node or final destination.
`Although additional detail is provided below, the compute
`plane 14 provides application level processing, and any nec-
`essary payload manipulation required by such processing.
`During processing by the compute plane 14, the payload may
`be reviewed, removed, modified, and repacked as directed by
`any number of applications. The routing node 10 preferably
`supports programming and unique configuration ofthe com-
`pute plane 14 and the forward plane 16.
`Any number of applications may be supported through the
`compute plane 14. For example, Internet Protocol (IP) secu-
`rity and secure socket layer (SSL) applications may be imple-
`mented in a routing node 10 using the compute plane 14.
`Various types of multimedia applications are made possible,
`alone or in combination with other applications. Further,
`incorporating a high-speed compute plane 14 for application
`specific packet processing enables streaming applications
`and minimizes or eliminates the need for buffering. The com-
`pute plane 14 is capable of implementing virtually any type of
`application, ranging from carrying out mathematical opera-
`tions on payloads to implementing compression and encryp-
`tion algorithms. The compute plane 14 may also help facili-
`tate high-speed firewalls acting as a single point of entry or
`distributed to provide multiple points of entry. Typically, the
`compute plane 14 operates on layer four and higher protocols
`that are typically application related.
`In addition to traditional forwarding of incoming packets
`and directing packets to the compute plane 14 for processing,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`13
`
`13
`
`

`
`US 7,860,999 B1
`
`7
`the forward plane 16 may direct selected incoming packets to
`the control plane 12 for basic communications with the rout-
`ing node 10 as shown in FIG. 6. In essence, the control plane
`12 provides overall control and configuration for the routing
`node 10, and in particular, for the compute plane 14 and the
`forward plane 16. This control may range from running diag-
`nostics to setting configurations for the compute plane 14 and
`the forward plane 16. These settings may dictate the type of
`processing to carry out on the incoming packets and which
`plane handles the processing.
`Returning now to FIG. 3, the routing node 10 may support
`various services, which are groups of code or objects that
`implement specific functionality. Preferably, these services
`use Java code and may be divided into compute services 18
`related to the compute plane 14, and network services 20
`related to the operation ofthe forward plane 16. Each ofthese
`services cooperates with the corresponding compute plane 14
`and forward plane 16 via a compute application program
`interface (API) 22 and network API 24, respectively. The
`network API can be CPIX, IEEE 1520, the IETF’s APIs, or
`other propriety APIs. Since the services are preferably Java
`compatible, the compute API 22 and network API 24 may
`specify interfaces for Java applications to control the respec-
`tive compute plane 14 and forward plane 16.
`Preferably, the network API 24 can be used to instruct the
`forward plane 1 6 to alter packet processing through the instal-
`lation ofhardware or software filters that facilitate forwarding
`rules. These filters execute actions specified by a defined filter
`policy. Typically, these filters can be based on combinations
`of fields in the machine address, IP address, and transport
`headers. The filters may also be configured to trigger on a
`payload as well. The filter policy can define where the match-
`ing packets are delivered and can also be used to alter the
`packet content as noted above.
`Typical packet delivery options include discarding match-
`ing packets and diverting matching packets to the control
`plane 12 or compute plane 14 based on the filter policy. With
`the present invention, a high-speed compute plane 14 is pro-
`vided to handle such processing. Additionally, packets may
`be “copied” to the control or compute planes 12, 14 or may be
`mirrored to a selected interface. Packets may also be identi-
`fied as being part of high-priority flow; these packets can be
`placed in a high-priority queue and delivered accordingly. For
`example, packets canbe marked differentially for DiffSery or
`MPLS marking. As noted, the filter policy can also cause
`packet and header content to be selectively altered for most of
`these operations. The particular plane handling the process-
`ing is capable of re-computing IP header check sums at high
`speeds when and if the IP header or payload is changed.
`In the present invention, all control plane computations,
`such as installing new routing tables, ARP cash tables, Filter
`tables, or parsing a new Internet Control Message Protocol
`(ICMP) message type, are easily accommodated through the
`network API 24. Through the network API 24, the forward
`plane 16 may provide a number of services. The applications
`are typically contained within the forward plane 16 and will
`not require additional processing by the compute plane 14 for
`traditional operation. The following list of services is merely
`exemplary and not intended to limit the scope of the present
`invention. The various functions provided by the forward
`plane 16 relate to analyzing incoming packets, manipulating
`packet headers, if necessary, and forwarding the packets to
`the next-hop or destination at high speeds.
`The present invention supplements these abilities with
`high-speed, preferably line rate, processing capabilities at an
`application level. As noted, the compute plane 14 is prefer-
`ably used to manipulate packet data or payloads beyond layer
`
`8
`three or four protocols that provide application l