(12) United States Patent
`Chiu et al.
`
`I 1111111111111111 11111 111111111111111 IIIII IIIII IIIII IIIII 1111111111 11111111
`US006385170Bl
`US 6,385,170 Bl
`May 7, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) METHOD AND SYSTEM FOR
`DYNAMICALLY TRIGGERING
`FLOW-BASED QUALITY OF SERVICE
`SHORTCUTS THROUGH A ROUTER
`
`(75)
`
`Inventors: Angela L. Chiu, Tinton Falls; Xiaowen
`Mang, Manalapan, both of NJ (US)
`
`(73) Assignee: AT&T Corp., New York, NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`(21) Appl. No.: 09/221,853
`
`(22) Filed:
`
`Dec. 29, 1998
`
`Int. Cl.7 .......................... G0lR 31/08; H04L 12/28
`(51)
`(52) U.S. Cl. ........................ 370/235; 370/351; 370/401
`(58) Field of Search ................................. 370/230, 231,
`370/232, 233, 235, 252, 254, 401, 402,
`412,413,466,474,351
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,412,654 A * 5/1995 Perkins ...................... 370/94.1
`6,009,077 A * 12/1999 Firoiu et al. ................ 370/230
`6,252,857 Bl * 6/2001 Fendick et al. ............. 370/254
`
`OTHER PUBLICATIONS
`
`Cell Switch Router (CSR) -label switching router support(cid:173)
`ing standard ATM interfaces, Hiroshi Esaki, Shigeo Mat(cid:173)
`suzawa, Akiyoshi Magi, Ken-ichi Ngami, Tatsuya Jimmei,
`Torn Kon'no, Yasuhiro Katsube, R&D Center, Toshiba
`Corporation, Japan, SPIE vol 3233, pp. 2 thru 10.*
`Reducing Overhead
`in Flow-Switched Networks: An
`Empirical Study of Web Traffic, Anja Feldman Jennifer
`Rexford, Ramon Cacere -AT&T Labs -Research, Florham
`Park, NJ, 1988 IEEE, pp. 1205 thru 1213.*
`
`Adaptive Resource Management for Flow-Based IP/ATM
`Hybrid Switching Systems* -Hao Che, San-qi Li, Depart(cid:173)
`ment of Electrical and Computer Engineering, University of
`Texas at Austin, Austin, Texas, Arthur Lin, Cisco Systems,
`Inc., CA IEEE, pp. 381 thru 389.*
`IP Switching -ATM Under IP, Peter Newman, Greg Min(cid:173)
`shall and Thomas L. Lyon, IEEE/ACM Transactions on
`Networking, vol. 6, No. 2, Apr. 1988, pp. 117 thru 129.*
`An Architecture for Differntiated Services, S. Blake, D.
`Black, M. Carlson, E. Davies, Z. Wang, W. Weiss, Lucent
`Technologies, Dec. 1998, The Internet Society (1998) pp. 1
`thru 33.*
`Specification of the Controlled-Load Netowrk Element
`Serivce, J. Wrocklawski, MIT LCS, Sep. 1997, pp. 1 thru
`17.*
`Specification of Guaranteed Quality of Service, S. Shenker,
`C. Partridge, R. Guerin, Sep. 1997, pp. 1 thru 18.*
`
`* cited by examiner
`
`Primary Examiner---Alpus H. Hsu
`Assistant Examiner-Due Ho
`
`(57)
`
`ABSTRACT
`
`A method and system for dynamically triggering flow-based
`quality of service shortcuts through a router is disclosed. The
`method further includes the steps of receiving a data packet
`at a router, determining whether a shortcut has been set up
`for a data flow to which said packet belongs, checking the
`status of an onset trigger counter when no shortcut exists,
`and when a current value of said onset trigger exceeds an
`onset trigger value, setting up a new shortcut for said data
`packet belonging to said data flow. The method of the
`present invention includes a dynamic system for adjusting
`state variable to control the number of shortcuts in existence
`and the adjusting the shortcut set up rate for optimal router
`switching efficiency.
`
`23 Claims, 7 Drawing Sheets
`
`100
`
`107
`
`ROUTE PACKET VIA
`EXISTING SHORTCUT
`
`102
`
`108
`
`RESET ONSET TRIGGER
`COUNTER TO ZERO
`
`109
`
`SEND PACKET VIA
`DEFAULT ROUTE
`
`I CREATE NEW SHORT CUT IN ROUTER r"- 105
`I
`106
`ROUTE All RELATED DATA
`PACKETS VIA NEW SHORTCUT
`
`Cloudflare - Exhibit 1028, page 1
`
`

`

`US. Patent
`
`May 7, 2002
`
`Sheet 1 0f 7
`
`US 6,385,170 B1
`
`FIG.
`
`1
`
`DATA PACKET ARRIVES AT ROUTER
`
`100
`
`PACKET
`
`101
`
`107
`
`BELONGS TO AN
`
`EXISTING SHORTCUT
`
`ROUTE PACKET VIA
`
`EXISTING SHORTCUT
`
`
`
`
`?
`
`NO
`
`CHECK STATUS OF ONSET TRIGGER
`
`COUNTER ASSOCIATED WITH THE FLOW
`
`
`
`108
`
`HAS
`
`
`
`
`
`
`COUNTER BEEN
`
`REACHED
`9
`
`
`TIME FOR
`
`
`RESET ONSET TRIGGER
`RESETTING ONSET TRIGGER
`COUNTER TO ZERO
`
`
`
`
`104
`
`
`
`ONSET TRIGGER
`
`
`COUNTER EXCEED OR EQUAL
`
`ONSET TRIGGER
`
`VALUE
`
`9
`YES
`'
`CREATE NEW SHORT CUT IN ROUTER
`
`
`
`ROUTE ALL RELATED DATA
`PACKETS VIA NEW SHORTCUT
`
`
`
`109
`
`
`
`/
`SEND PACKET VIA
`
`DEFAULT RDUTE
`
`105
`
`‘05
`
`Cloudflare - Exhibit 1028, page 2
`
`Cloudflare - Exhibit 1028, page 2
`
`

`

`US. Patent
`
`May 7, 2002
`
`Sheet 2 0f 7
`
`US 6,385,170 B1
`
`FIG. 1a
`
`
`
`Cloudflare - Exhibit 1028, page 3
`
`Cloudflare - Exhibit 1028, page 3
`
`

`

`US. Patent
`
`May 7, 2002
`
`Sheet 3 0f 7
`
`US 6,385,170 B1
`
`FIG. 2
`
`CHECK ABATEMENT STATUS
`
`200
`
`
`
`OF EXISTING SHORTCUT AT THE
`
`END OF THE ABATEMENT PERIOD
`
`
`
`
`
`HAS
`
`ANY PACKET
`
`
`TEAR DOWN
`START A NEw
`ARRIVED BY THE END OF
`EXISTING IDLE
`ABATEMENT
`
`
`
`THE ABATEMENT
`PERIOD
`SHORTCUT
`
`PERIOD
`
`
`
`
`
`202
`
`YES
`
`9 '
`
`THE SHORTCUT IS
`
`NOT TORN DOWN
`
`Cloudflare - Exhibit 1028, page 4
`
`Cloudflare - Exhibit 1028, page 4
`
`

`

`US. Patent
`
`May 7, 2002
`
`Sheet 4 0f 7
`
`US 6,385,170 B1
`
`mo
`
`
`mwAmcatofiVz.m€28VmV_AwesotofiVz.NQ23:momEsotofiV2;3=smeV_INrIIWmIIIIIIIIIIINmIIIIImVIVIIII..IIII..IImIIIIIIIIesotofiEE:
`manN9.
`
`
`
`
`
`
`
`
`
`.
`
`m,QNK
`
`
`
`
`
`SzoomeSoEozm.._o$9..an8:2nsmmSuzozmmo<E><
`
`
`
`
`
` Seize:aaqztammrfi53222935
`
`an_O_O0
`
`
`anr-11mmllllllrlllllmmlllllLlllllllllllfilmlllllll:£293:ng
`
`
`\vAmaze—VofiVszaanV“monotofiVszEmemVESQtOfiVZREEomeV
`
`an...55m:
`
`8m0OO28an
`
`
`LJSEEmVZQQEomeVAocaotofiVzbaemmeVAwesotofiVz.w€E$VmV3om_882%szm
`
`Iuliwmlllllllllllomllllllllllllllllmlmllllllls2%:tLV5$32
`
`2
`
`Cloudflare - Exhibit 1028, page 5
`
`Cloudflare - Exhibit 1028, page 5
`
`

`

`US. Patent
`
`May 7, 2002
`
`Sheet 5 0f 7
`
`US 6,385,170 B1
`
` 1
`
`7
`
`13
`
`19
`
`25
`
`FI G. 5
`
`7. BYTES
`
`0N
`
`SHORTCUTS
`
`DYNAMIC
`
`
`
`I
`
`7
`
`13
`
`19
`
`25
`
`INITIAL SETTING SCENARIO
`
`FIG. 6
`90 .
`
`DYNAMIC
`
`80
`
`70
`
`A SEES
`
`SHORTCUTS
`
`
`
`A
`
`STATIC
`
`50 __
`
`____ ____________
`
`
`
`1
`
`7
`
`13
`
`I9
`
`25
`
`INITIAL SETTING SCENARIO
`
`Cloudflare - Exhibit 1028, page 6
`
`Cloudflare - Exhibit 1028, page 6
`
`

`

`US. Patent
`
`May 7, 2002
`
`Sheet 6 0f 7
`
`US 6,385,170 B1
`
`FIG. 7
`
`100.0
`
`90.0 \
`80.0 '
`
`\
`
`DYNAMIC WITH INITIAL(5.60)
`
`
`
`%BYTES
`
`70.0 a,
`
`V
`
`3“.
`
`ON SHORTCUTS 600 ,_
`500
`.
`
`.IASIATLC WITH |N|T|AL(560
`‘
`STATIC WITH INITIAL(5.30)
`
`40.0
`
`30.0
`
`0.0
`
`1000.0
`
`2000.0
`
`3000.0
`
`4000.0
`
`5000.0
`
`TIME (sec)
`
`PERCENTAGE
`
`VALUE OF n
`
`Cloudflare - Exhibit 1028, page 7
`
`Cloudflare - Exhibit 1028, page 7
`
`

`

`US. Patent
`
`May 7, 2002
`
`Sheet 7 0f 7
`
`US 6,385,170 B1
`
`FIG. 9
`
`80
`
`% BYTES 0N SHORTCUTS
`
`78
`
`PERCENTAGE 76
`
`74
`
`72 70
`
`0
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`UPDATE_PERIOD
`
`FIG.
`
`10
`
`80
`
`DIST=0.6
`
`78
`
`75
`
`% BYTES
`ON
`
`SHORTCUTS
`
`0.3
`
`0.4
`
`0.5
`
`0.6
`
`0.7
`
`0.8
`
`0.9
`
`MID_THRESHOLD
`
`Cloudflare - Exhibit 1028, page 8
`
`Cloudflare - Exhibit 1028, page 8
`
`

`

`US 6,385,170 B1
`
`1
`METHOD AND SYSTEM FOR
`DYNAMICALLY TRIGGERING
`FLOW-BASED QUALITY OF SERVICE
`SHORTCUTS THROUGH A ROUTER
`
`TECHNICAL FIELD
`
`This invention relates generally to processing data traffic
`and more particularly a technique for providing quality of
`service (QoS) for individual Internet Protocol (IP) data flows
`transferred via a router or other such suitable switch. The
`
`present invention describes a state dependent dynamic trig-
`gering scheme (SDDTS) for flow based QoS shortcuts.
`BACKGROUND OFT THE INVENTION
`
`The Internet has grown rapidly in the last several years. In
`order to support increasing demands for real-time and mul-
`timedia applications as well as mission critical applications,
`Internet Protocol (IP) need to support quality of service
`(QoS). QoS is a networking term that specifies a level of
`service based on,
`for example,
`throughput, delay, jitter
`and/or loss through a network. In general, QoS approaches
`can be divided into two main categories: flow-based and
`class-based. Flow-based QoS is designed to provide QoS
`assurance for each individual IP flow. IP specifies the format
`of data packets or datagrams and the addressing scheme to
`route the data packets or data grams to the desired destina-
`tion in a network. An IP flow is defined as a set of packets
`matching a particular profile. A profile can be defined, for
`example,
`in terms of source/destination IP addresses, IP
`protocol, source/destination port numbers, and Type of Ser-
`vice (ToS) requirements. A typical example of flow based
`QoS is the Integrated Service model proposed by the Intserv
`working group of the Internet Engineering Taskforce
`(IETF). The QoS Integrated Service model is further dis-
`cussed by J. Wroclawski
`in: “Specification of the
`Controlled-Load Network Element Service,” in IETF
`RFC2211, September, 1997, incorporated herein by refer-
`ence. S. Shenker, C. Partridge, and R. Guerin discuss
`another example of QoS in: “Specification of Guaranteed
`Quality of Service,” in IETF RFC2212, September, 1997,
`incorporated herein by reference. The Integrated Service
`model provides fine granularity and flexibility in specifying
`flows. However, the service model requires storing states on
`a per-flow basis at each network node and an end-to-end
`signaling protocol such as Resource ReServation Protocol
`(RSVP). Using RSVP, an application must reserve resources
`along a route from source to destination. This procedure is
`problematic in that the reserved resources may be unavail-
`able for additional processing needs and may result
`in
`decreased throughput. Further, RSVP raises concerns
`regarding the scalability of the approach due to the fact that
`the number of active flows can be quite large. In order to
`avoid the scalability problem with flow-based QoS, class-
`based QoS, which is also referred as Class of Service (CoS),
`is proposed to provide differentiated service for each class.
`For example, the Differentiated Service model is proposed
`by the Diffserv working group of IETF. The Differential
`Service Model
`is discussed by S. Blake, D. Black, M.
`Carlson, E. Davies, Z. Wang and W. Weiss in: “An Archi-
`tecture for Differentiated Services,” in IETF RFC2475,
`December, 1998,
`incorporated herein by reference.
`Generally, in a class-based QoS model, packets are marked
`as different classes and get served accordingly. Although
`class-based QoS may be more scalable, but it does not have
`the fine granularity of the flow-based approach. Thus there
`exists no assurance in class-based QoS for each individual
`flow within a class.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`Since each approach has its own pros and cons, a network
`may need both models in order to provide adequate service
`for different types of applications. For example, class-based
`QoS may be enough for the majority of the Internet traffic
`that may not need fine granularity of service levels or require
`QoS assurance on a per-flow basis. Class-based QoS can be
`realized by preferential treatment for different classes of data
`traffic at each router in the network or by mapping different
`classes of data traffic onto different label switching paths
`(LSPs). LSPs may include, for example, Cisco Corpora-
`tion’s Tag switching paths, Multipoint-to-Point Tree (MPTs)
`IP switching paths in Ascend Corporation’s IP Navigator
`and LSPs in MPLS (Multiprotocol Label Switching).
`On the other hand, some mission critical applications may
`require tight control on packet
`loss and delay on each
`individual flow. In addition, some voice or video traffic may
`require minimum jitter which may cause degradation of the
`data signal for each individual flow. Class-based QoS may
`not be suitable for such applications, and thus flow-based
`QoS may be necessary for those types of applications.
`Flow-based QoS can be achieved by using explicit routes in
`MPLS, or with NHRP (Next Hop Resolution Protocol)
`shortcuts as proposed in MPOA (Multiprotocol Over ATM
`with Asynchronous Transfer Mode (ATM) underneath IP.
`MPOA enables ATM services to be integrated with existing
`local area networks (LANs) that use Ethernet, token ring or
`TCP/IP protocols. IP switching, as one of the key advances
`in IP technology, is designed to improve the performance
`and scalability of IP as well as providing QoS. Two of the
`main IP switching products, IP switch by Nokia, Corp. and
`Cell Switch Router by Toshiba, Corp., use flow-based short-
`cuts for long-lived flows and hop-by-hop routing for the rest
`of the traffic. A shortcut may be defined as a directed
`forwarding path associated with some label, for example,
`link layer address, such that data packets are efficiently
`routed without requiring the need for an IP routing table
`lookup at each hop.
`there is
`In all
`those flow-based shortcut approaches,
`certain overhead associated with each shortcut setup. Since
`existing routers have limited resources in processing power
`and memory space, there are upper bounds on shortcut setup
`rates and number of simultaneous shortcut connections.
`
`Hence, it is important to investigate how to, most efficiently,
`trigger shortcut setup and tear down where the above
`physical limits are taken into account.
`In previous work, researchers have studied the effect of
`the two triggering parameters, for example, onset trigger and
`abatement period, on the resource usage measured by aver-
`age shortcut setup rate and average number of simultaneous
`shortcuts. Studies have concluded that a larger onset trigger
`may reduce both shortcut setup rate and number of simul-
`taneous shortcuts, however, at the expense of forcing more
`packets to follow the default path. Further studies have
`indicated, that a larger abatement period may increase the
`number of simultaneous shortcuts, but decreases the shortcut
`setup rate.
`Work in this area is limited. In particular, most of the prior
`art systems have focused on evaluating the performance of
`some static schemes. Generally, researchers have studied a
`static scheme where two parameters, the onset trigger and
`the timeout or some variations thereof, are used. Onset
`trigger may be defined as the number of packets that must be
`received, from the same flow, before triggering a shortcut to
`be setup. Timeout, also referred as the abatement period, is
`the preset idle time period before shortcut tearing down is
`triggered. The parameter setting is statically assigned based
`on some predefined IP traffic statistics. However, the static
`
`Cloudflare - Exhibit 1028, page 9
`
`Cloudflare - Exhibit 1028, page 9
`
`

`

`US 6,385,170 B1
`
`3
`scheme does not take into account, for example, system
`resource limitations and/or the variability of network data
`traffic characteristics. To solve this problem an “Adaptive
`Resource Management
`for Flow-Based IP/ATM Hybrid
`Switching Systems,” in IEEE INFOCOM, March 1998, by
`H. Che and S. Li, incorporated herein by reference, illus-
`trates an adaptive flow identification/classification scheme
`for resource balancing in flow-based IP switching. The
`objective of the adaptive flow identification/classification
`scheme is to minimize the relative differences of utilization
`
`among the following three constrained resources: hop-by-
`hop routing, shortcut connection setup, and active shortcut
`connections. Based on the relative utilization order among
`the three resources, a learning algorithm is designed to
`adjust the probability of taking different actions, i.e., adjust-
`ing two control parameters in different directions. Simula-
`tion results have shown some advantages of this adaptive
`approach over the static one. However, due to its increased
`complexity, the practicality of the proposed adaptive scheme
`remains an open issue.
`Moreover, none of the existing schemes or proposals
`addresses shortcut setup for QoS flows. Since each QoS flow
`requires certain level of service assurance, a shortcut that
`provides adequate service for each QoS flow through, for
`example, a router is required. As stated earlier, the traffic
`received by a router is generally quite dynamic and its
`characteristics are unknown in most cases. Thus a robust
`
`dynamic scheme for setting up and tearing down shortcuts,
`that can adjust itself to data traffic dynamics without being
`unnecessarily complex, is also required.
`SUMMARY OF THE INVENTION
`
`The present invention is directed to a State Dependent
`Dynamic Triggering Scheme (SDDTS) that addresses the
`above mentioned problems of the prior art. In particular the
`present invention illustrates a practical shortcut triggering
`scheme for QoS flows. The present invention illustrates a
`system and method for maximizing the percentage of QoS
`traffic switched through shortcuts given certain resource
`limitations, i.e., maximum shortcut setup rate and maximum
`number of simultaneous shortcut connections. Unlike prior
`art approaches, the present invention discloses a relatively
`uncomplicated and practical method based on arithmetic
`calculations to dynamically adjust
`two parameters,
`for
`example, onset trigger and abatement period. In embodi-
`ments of the present invention, the two parameters may be
`adjusted according to average shortcut setup rate and aver-
`age number of simultaneous shortcut connections. Thus the
`present invention is fundamentally different from the “Adap-
`tive Resource Management for Flow-Based IP/ATM Hybrid
`Switching Systems,” approach, discussed earlier,
`that
`involves a more complex and unpractical optimization algo-
`rithm for probability estimation of actions where the objec-
`tive is load balancing among three limited resources.
`The present invention discloses a practical and robust
`dynamic scheme for efficiently creating and tearing down
`shortcuts for QoS data flows through, for example, a data
`router. One key aspect of such a scheme is to decide, for
`example, when to setup a shortcut and when to tear down a
`shortcut, which in turn is governed, for example, by the
`onset
`trigger and abatement period trigger values. The
`dynamic scheme, as disclosed in one embodiment of the
`present invention, updates those trigger values in an on-line
`manner so as to achieve a higher and consistent switching
`efficiency.
`One object of the present invention, is to achieve near-
`optimal switching efficiency in terms of the percentage of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`bytes and packets that are routed over shortcuts. Because
`there is a direct relationship between number of shortcuts
`and the performance target, the more shortcuts, the better
`performance if there is no physical limit in terms of short-
`cuts. However, the number of shortcuts a router can support
`simultaneously does have its physical limits. In addition, a
`router may also have a limited set up rate, i.e. how fast a
`shortcut may be set up by the router.
`Generally, when the number of simultaneous shortcuts
`hits its physical limit, a request for setting up a new shortcut
`must be queued and waits for some existing shortcuts to be
`torn down. Even though some existing shortcuts may not
`have any future traffic, they may still stay active until the end
`of the abatement period. While setup requests wait in the
`queue,
`the packets may be sent over the default route,
`reducing, for example, router efficiency. To avoid applying
`abatement criterion to the flows with requests queued, the
`unsatisfied requests are removed from the request queue at
`the end of each onset period. The flows may be subject to the
`onset trigger again. Thus there exists a natural bias towards
`flows with existing shortcuts over flows with unsatisfied
`requests, even where the existing shortcuts remain idle.
`Hence, the fewer the number of shortcut setup requests
`granted, the less the percentage of QoS traffic that is routed
`through shortcuts. Thus another objective of the present
`invention is to keep the average shortcut number close to its
`limit and at the same time to reduce the chances that shortcut
`
`reaches its limit. Embodiments of the present
`number
`invention, describe an upper threshold and a lower threshold
`level of the number of shortcuts, and denote the region
`between the two as the desired stable region. As a result,
`there is a better chance for future long-lived flows being
`routed through shortcuts. Thus, it is an object of the present
`invention to achieve a higher switching efficiency. Since a
`higher setup rate results in more shortcuts, the same design
`philosophy applies to the setup rate.
`Thus, embodiments of the present invention disclose a
`dynamic scheme to adjust a plurality of control parameters
`to set-up and tear down shortcuts for most efficient routing
`of QoS flows in a network.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention will be disclosed in detail herein with
`
`reference to the following figures in which like reference
`numbers refer to the elements, and wherein:
`FIG. 1a is block diagram of a router in accordance with
`an exemplary embodiment of the present invention.
`FIG. 1 is a flow diagram illustrating how new shortcuts
`may be created in accordance with an exemplary embodi-
`ment of the present invention.
`FIG. 2 is a flow chart illustrating how existing shortcuts
`may be torn down in accordance with an exemplary embodi-
`ment of the present invention.
`FIG. 3 is an graph illustrating possible states of the two
`state variables in embodiments of the present invention.
`FIGS. 4—10 illustrate simulation results of embodiments
`
`of the present invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`FIG. 1a illustrates a block diagram according to an
`exemplary embodiment of the present invention. A router I
`is shown with a plurality of inputs 2—6 to the router. These
`may be via plurality of ports located on the router or via a
`single port having the capability to multiplex a plurality of
`
`Cloudflare - Exhibit 1028, page 10
`
`Cloudflare - Exhibit 1028, page 10
`
`

`

`US 6,385,170 B1
`
`5
`input signals into the router. The router may further com-
`prise a controller 7 for various processing functions of the
`router,
`for example, monitoring the inputs, creating
`shortcuts, adjusting parameters, and any other such suitable
`functions that may be required by the router. The controller
`7 may include, for example, an onset trigger counter 7a for
`counting the plurality of data packets of a flow received by
`the router, as will be discussed in more detail below. In
`addition the controller 7 may receive a timing signal from a
`clock 8 for controlling the various timing functions, includ-
`ing for example, monitoring the idle periods and/or abate-
`ment periods as described below in detail. The clock 8 may
`be a stratum 1 clock from an external timing source, or a
`stratum 2 clock or even an internal oscillator having a
`stratum 3 accuracy or any other such suitable timing source.
`The controller, based on the received input data packets and
`timing values, may determine, in accordance with embodi-
`ments of the present
`invention,
`that a new shortcut
`is
`required for routing a particular incoming data flow. If a new
`shortcut is required, the controller may create, for example,
`new shortcuts 14—15 for outputs 11—12. In embodiments of
`the present invention, the router may most efficiently route
`the data packets of a flow to the appropriate route via the
`shortcuts, without checking a lookup table for IP routing
`purposes which can decrease router efficiency. In addition,
`the router may determine that, for example, an existing
`shortcut 16 may have been idle longer than an abatement
`period and thus the controller may determine that
`the
`shortcut is no longer needed. In that case, the controller may
`tear down, for example, the existing shortcut 16. The various
`features of the present
`invention will be discussed and
`described in far greater details below.
`FIG. 1 is a flow diagram illustrating a shortcut setup
`procedure in accordance with an exemplary embodiment of
`the present invention. In step 100, a data packet arrives at,
`for example, a router or other such suitable switch for
`routing data traffic. The router and/or switch may determine
`whether the data packet belongs to or is associated with a
`flow having an existing shortcut as shown in step 101. If the
`packet belongs to a flow having an existing shortcut, the data
`packet may be routed via the existing shortcut as shown in
`step 107. If, however, the data packet does not belong to an
`existing flow, then, for example, a controller may implement
`a process, in accordance with one embodiment of the present
`invention, to determine whether a new shortcut should be
`created. This process and/or program to determine whether
`a new shortcut should be created, may be a software
`program downloaded to the controller and/or may be stored
`in an EPROM or any such suitable device. As shown in step
`102, the controller, for example, may check the status of an
`onset trigger counter associated with the flow. The onset
`trigger counter may keep count of data packets belonging to
`a particular flow and/or a set of packets matching a particular
`profile. Thus, in essence, the onset trigger counter may keep
`a running record of the number of packets of each flow that
`has visited the router. The trigger counter may keep a
`separate count for data packets having a similar profiles. As
`shown in step 103, the trigger counter, may include a clock
`for determining whether the time, known as the onset period,
`for resetting the onset trigger to zero been reached. If, for
`example, the number of data packets received, of a particular
`flow, does not equal at
`least
`the number of packets as
`specified by the onset trigger value, received during a period
`of time that is equal to the onset period, then the trigger
`counter for that flow may be reset to zero as shown in step
`108. This onset period may be based, for example, on a
`predetermined value or may be alternatively determined by
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`any suitable technique known in the art. If the onset trigger
`counter is reset to zero, as shown in step 108, then this
`information may be provided back to the controller so that
`counting may restart as packets related to that flow are again
`received by the router or switch. On the other hand, if data
`packets fitting a particular profile are constantly being
`received at the router, such that the time for resetting the
`onset period has not been reached, then there may be no need
`to reset the trigger counter. Thus, as the counter accumulates
`counts for the current flow profile,
`the controller may
`determine whether the onset trigger counter exceed or equal
`an onset trigger value as shown in step 104. The onset trigger
`value may be determined dynamically, in accordance with
`the present
`invention, based on,
`for example, resource
`availability and/or data traffic flow through the router and/or
`network. If the trigger counter for the particular flow profile
`does not exceed or equal, for example,
`the dynamically
`determined onset trigger value, then the data packet may be
`sent to a default route as shown in step 109. However, if the
`trigger counter for the particular flow profile does exceed or
`is equal to, for example, the dynamically determined onset
`trigger value, then a new shortcut may be created within the
`router as shown in step 105. Once the new shortcut
`is
`created, all data packets matching the particular flow profile
`may be routed via the newly created shortcut as shown in
`step 106.
`Under embodiments of the present invention, for routing
`QoS flows efficiently, new shortcuts may be created dynami-
`cally as existing idle shortcuts may be torn down. Thus,
`effectively tearing down an idle shortcut at the appropriate
`time may permit the creation of new functional shortcuts
`permitting the router to achieve higher and consistent
`switching efficiencies while staying within its physical limi-
`tations. FIG. 2 illustrates the tearing down of the existing
`shortcuts in accordance with an embodiment of the present
`invention. An existing shortcut may be torn down if it is
`determined that there are no data packet arrivals fitting the
`profile of those flows with active shortcuts for a given period
`of time. As shown in step 200, the controller may check the
`abatement status at the end of each abatement period whose
`length is equal to the value of the parameter of the abatement
`period. The abatement status may be determined based on
`the arrival of any packets that belongs to the flow by the end
`of the current abatement period as shown in step 201. The
`abatement period, for tearing down an existing shortcut, may
`also be a dynamically determined period of time. The
`abatement period may be determined dynamically, in accor-
`dance with the present invention, based on, for example,
`resource availability and/or data traffic flow through the
`router or network. An idle shortcut may be defined as a
`shortcut that has been in existence, without receiving a data
`packet of the flow for which the shortcut was created, by the
`end of the abatement period. Where such an idle shortcut is
`determined to exist, such shortcut may be torn down as
`shown in step 203. At the end of an abatement period, the
`router may start a new abatement period as shown in step
`204. Accordingly, the abatement period may be updated at
`the end of the previous abatement period and/or may be
`updated periodically. The new abatement period may also be
`dynamically determined based on, for example, varying
`traffic conditions and/or available system resources. Where
`traffic conditions require, the abatement period may become
`smaller and smaller causing shortcuts to be torn down
`sooner. Accordingly, new shortcuts may be created, under
`embodiments of the present invention, as idle shortcuts are
`torn down. If, however, the shortcut continuously receives
`data packets of the particular flow profile for which the
`
`Cloudflare - Exhibit 1028, page 11
`
`Cloudflare - Exhibit 1028, page 11
`
`

`

`US 6,385,170 B1
`
`7
`shortcut was created, the shortcut will not be torn down and
`will continue to route the appropriate data packets. Thus, as
`long as the time period between data packets of the same
`flow, received by the router, does not exceed the abatement
`period, the shortcut may remain in existence as shown in
`step 202.
`As discussed above, the onset trigger may control the
`process of setting up a new shortcut based on for example,
`the onset period. Meanwhile the abatement period may
`govern the process of tearing down, for example, an existing
`idle shortcut. The present invention discloses a system and
`method for determining and adjusting control parameters to
`regulate two state variables, for example,
`the number of
`simultaneous shortcuts and shortcut setup rate, for efficient
`traffic flow in a router or any other such suitable switch.
`Thus, embodiments of the present invention, may permit the
`automatic tuning of control parameters based on data traffic
`conditions and system limitations and/or available
`resources. The state dependent dynamic triggering scheme
`(SDDTS) is further described below in detail.
`The SDDTS technique may be based on regulating a
`plurality of control parameters,
`for example,
`the onset
`trigger and abatement period or any other such parameter
`that may impact the two state variables. As stated above, the
`two state variables that may have the maximum impact on
`the switch efficiencies comprise number of simultaneous
`shortcuts and shortcut setup rate. Thus,
`to achieve near-
`optimal switching efficiency based on at least these two state
`variables, the control parameter settings may vary based on
`the incoming traffic characteristics and system resource
`limitations. One embodiment of the present invention based
`on the SDDTS technique may utilize, for example, a dual
`threshold technique for
`the various control parameters.
`Thus, each of the control parameters may have an upper
`threshold and a lower threshold. Since the data traffic
`
`characteristics of, for example, a router or any other such
`switch, may be unknown and constantly changing,
`it is
`impossible to find an optimal predetermined set of control
`parameters. For example,
`it would impossible to find a
`single onset trigger value and/or abatement period that suits
`all data traffic patterns for a desirable switching efficiency. In
`embodiments of the present invention, the performance of a
`router or other switching device, may be kept at satisfactory
`levels by defining an upper threshold limit and a lower
`threshold limit for the desired parameters. Accordingly, by
`maintaining the parameters between the desired threshold
`values, may keep the state variables, for example,
`the
`number of simultaneous shortcuts and shortcut setup rate
`within the desired stable state region for optimal switch
`efficiency. Having upper and lower threshold limits of the
`control parameters may permit a certain degree of fluctua-
`tion within the stable state region for adjusting to the
`constantly changing incoming traffic data patterns. The
`criteria to determine performance of, for example, the router
`or other such switching equipment, may be measured in
`terms of percentage of bytes and/or percentage of packets on
`shortcuts. Thus, the more data being routed via shortcuts,
`may ultimately results in less