`
`
`
`
`a2, United States Patent
`
`
`
`
`
`US 6,385,170 B1
`(10) Patent No.:
`
`
`
`
`
`
`
`May7, 2002
`(45) Date of Patent:
`Chiu et al.
`
`US006385170B1
`
`
`
`
`
`
`Adaptive Resource Management for Flow—Based IP/ATM
`
`
`
`
`
`
`
`
`Hybrid Switching Systems* —Hao Che, San—qi Li, Depart-
`
`
`
`
`
`
`mentof 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 UnderIP, Peter Newman, Greg Min-
`
`
`
`
`
`
`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—Duc Ho
`
`
`
`
`
`
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`
`
`Amethod 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 numberof shortcuts in existence
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and the adjusting the shortcut set up rate for optimal router
`
`
`switching efficiency.
`
`
`
`
`23 Claims, 7 Drawing Sheets
`
`
`
`107
`
`f
`
`
`
`
`YES
`
`
`
`
`
`
`
`
`(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 ofthis
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`US.C. 154(b) by 0 days.
`
`
`
`(22)
`
`
`
`
`
`(21) Appl. No.: 09/221,853
`
`
`
`
`
`Filed:
`Dec. 29, 1998
`
`
`
`
`
`
`
`
`(51)
`Int. C17 vee GOIR 31/08; HO4L 12/28
`
`
`
`
`
`
`
`
`(52) U.S. Ch on.
`. 370/235; 370/351; 370/401
`
`
`
`
`
`
`(58) Field of Search oo... eee 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 o..cccseeeeeee 370/94.1
`
`
`
`
`
`6,009,077 A * 12/1999 Firoiu etal. ......
`... 370/230
`
`
`
`
`
`
`6,252,857 B1 *
`6/2001 Fendick et al.
`............. 370/254
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SEND PACKET VIA
`
`
`DEFAULT ROUTE
`
`
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit 1028
`
`Page 1
`
`
`
`
`
`
`
`
`
`Cell Switch Router (CSR) —label switching router support-
`
`
`
`
`
`
`
`ing standard ATM interfaces, Hiroshi Esaki, Shigeo Mat-
`
`
`
`
`
`
`suzawa, Akiyoshi Mogi, Ken-ichi Ngami, Tatsuya Jimmei,
`
`
`
`
`
`
`Toru 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.*
`
`
`DATA PACKET ARRIVES AT ROUTER 100
`
`
`
`
`
`
`
`
`
`
`101
`PACKET
`a
`
`
`BELONGS 0 AN
`
`
`ROUTE PACKET VIA
`? NO
`
`
`EXISTING SHORTCUT
`EXISTING SHORTCUT
`
`
`
`
`
`
`
`
`7 102
`CHECK STATUS OF ONSET TRIGGER
`
`
`
`
`
`COUNTER ASSOCIATED WITH THE FLOW
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ONSET TRIGGER
`
`VALUE2
`
`
`
`
`
`CREATE NEW SHORT CUT IN ROUTER 105
`
`
`
`
`
`
`
`ROUTE ALL RELATED DATA
`L= (06
`
`PACKETS VIA NEW SHORTCUT
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1028 Page 1
`
`

`

`U.S. Patent
`
`
`
`
`May 7, 2002
`
`
`
`
`Sheet 1 of 7
`
`
`
`US 6,385,170 B1
`
`
`
`FIG.
`
`
`1
`
`DATA PACKET ARRIVES AT ROUTER
`
`
`
`
`
`
`
`190
`
`
`
`
`
`
`
`107
`
`
`
`
`
`101
`
`PACKET
`
`
`
`
`
`
`
`BELONGS TO AN
`
`
`
`
`
`EXISTING SHORTCUT
`?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`108
`HAS
`
`
`
`
`TIME FOR
`
`
`
`
`
`
`RESETTING ONSET TRIGGER
`
`
`
`
`COUNTER BEEN
`
`REACHED
`
`
`
`
`
`
`9
`
` ONSET TRIGGER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`COUNTER EXCEED OR EQUAL
`
`
`
`
`ONSET TRIGGER
`
`
`VALUE
`
`?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1028
`
`Page 2
`
`Splunk Inc. Exhibit 1028 Page 2
`
`

`

`U.S. Patent
`
`
`
`
`May 7, 2002
`
`
`
`
`Sheet 2 of 7
`
`
`US 6,385,170 B1
`
`
`
`FIG.
`
`
`fa
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ONSET TRIGGER
`COUNTER
`
`nanoo—&SWPo
`
` ROUTER
`
`INPUT Co
`
`Pp}INPUT
`
`| | CONTROLLER
`INPUT
`| |INPUT
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit 1028
`
`Page 3
`
`Splunk Inc. Exhibit 1028 Page 3
`
`

`

`U.S. Patent
`
`
`
`
`May7, 2002
`
`
`
`
`Sheet 3 of 7
`
`
`US 6,385,170 B1
`
`
`
`
`FIG. 2
`
`
`
`
`
`
`CHECK ABATEMENT STATUS
`
`
`
`
`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
`SHORTCUT
`PERIOD
`
`
`
`
`
`
`
`
`PERIOD
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`THE SHORTCUT IS
`
`
`
`NOT TORN DOWN
`
`
`
`Splunk Inc.
`
`Exhibit1028
`
`Page 4
`
`Splunk Inc. Exhibit 1028 Page 4
`
`

`

`US 6,385,170 B1
`
`U.S. Patent
`
`May7, 2002
`
`
`
`Mironene)((snoproys)y‘(dnjas)s)=e((ynopoys)y‘*
`
`
`
`
`
`
`
`
`
`(dnyas)s)|--*~~~¢SaDaeCee(inopoys}fIWI~~~—
`
` 80t708208&‘Ola
`
` (dnyas)
`
`tur]reddn(48S)J4Lremo(tS
`
`108@@@ER)EY
`
`Sheet 4 of 7
`
`Ste__8SsSs_sano}HONS)UL
`
`
`
`og?|e|@@Y((aqous)n"(dnes))({(inoioys)y‘9(dnjas)s)(Anopoys)y‘4(dnyas)s)
`
`ocee@SLNOLNOHSN|(%(jnapoys)y‘?(dnyas)s)
`
`
`
`
`any((inooys)y‘°(dnyas)s)(3(;noysoys)y‘2(dryas)s)nouous\soNoSSesg“|seddn(HO4S)UL
`
`
`
`
`
`
`
`
`
`(ANOO3S/SLNOLNOHS40YIGNNN)SALVEdNL3SLNOLYOHSJOVYIAV
`
`Splunk Inc.
`
`Exhibit 1028
`
`Page5
`
`Splunk Inc. Exhibit 1028 Page 5
`
`

`

`U.S. Patent
`
`
`
`
`May7, 2002
`
`
`
`
`Sheet 5 of 7
`
`
`US 6,385,170 B1
`
`
`
` 1
`
`7
`
`
`
`13
`
`
`
`19
`
`
`
`25
`
`
`
`
`
`
`
`
`
`1
`
`
`
`7
`
`
`
`
`
`
`
`
`% BYTES
`
`ON
`
`
`
`
`
`
`
`
`
`
`
`*% BYTES
`
`ON
`
`SHORTCUTS
`
`
`
`SHORTCUTS
`
`
`
`
`
`29
`
`
`
`
`
`
`13
`
`
`
`
`
`INITIAL SETTING SCENARIO
`
`19
`
`
`
`1
`
`7
`
`13
`
`
`
`
`
`INITIAL SETTING SCENARIO
`
`19
`
`25
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1028
`
`Page6
`
`Splunk Inc. Exhibit 1028 Page 6
`
`

`

`U.S. Patent
`
`
`
`
`May7, 2002
`
`
`
`
`Sheet 6 of 7
`
`
`US 6,385,170 B1
`
`
`
`
`FIG. 7
`
`
`100.0
`DYNAMIC WITH INITIAL(5.60)
`90.0
`
`
`
`DYNAMIC’ WITH INITIAL(5.30)
`AX
`80.0 #
`
`
`
`f
`NLL ee
`
`
`
`
`
`% BYTES 70.0WfAN. ae
`
`
`
`
`ON SHORTCUTSli)
`=~~ STATIC WITH INITIAL(5.60
`
`
`
`
`STATIC WITH INITIAL(5.30)
`50.0
`
`
`0.0
`
`
`
`——.Y
`
`He
`
`40.0
`
`30.0
`PERCENTAGE
`
`
`
`1000.0
`
`
`
`
`3000.0
`2000.0
`
`TIME (sec)
`
`
`
`
`4000.0
`
`
`
`5000.0
`
`
`
`
`
`
`
`
`
`VALUE OF n
`
`Splunk Inc.
`
`Exhibit1028
`
`Page 7
`
`Splunk Inc. Exhibit 1028 Page 7
`
`

`

`U.S. Patent
`
`
`
`
`May7, 2002
`
`
`
`
`Sheet 7 of 7
`
`
`US 6,385,170 B1
`
`
`
`
`FIG. 9
`
`
`
`
`
`BYTES ON SHORTCUTS
`
`
`
`80
`
`
`
`78
`
`
`
`
`PERCENTAGE 7¢
`
`74
`
`
`
`72
`
`
`
`
`
`70
`
`
`
`
`
`
`
`
`
`UPDATE_PERIOD
`
`
`
`
`
`
`
`
`
`
`
`
`
`78
`
`76
`
`SHORTCUTS
`
`
`
`
`% BYTES
`
`ON
`
`
`
`0.5
`
`
`
`0.4
`
`
`
`0.5
`
`0.6
`
`
`
`
`MID_THRESHOLD
`
`0.7
`
`
`
`0.8
`
`
`
`0.9
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1028
`
`Page8
`
`Splunk Inc. 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 QoSshortcuts.
`BACKGROUND OFT THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`The Internet has grownrapidly in the last several years. In
`
`
`
`
`
`
`
`order to support increasing demandsfor real-time and mul-
`
`
`
`
`
`
`timedia applications as well as missioncritical 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 gramsto 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
`
`
`
`
`
`
`
`QoSis 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 dueto 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, whichis 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 morescalable, 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 needfine granularity of service levels or require
`
`
`
`
`
`
`QoSassurance on a per-flow basis. Class-based QoS can be
`
`
`
`
`
`
`
`realized by preferential treatmentfordifferent 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).
`
`
`
`
`
`
`
`
`Onthe other hand, some missioncritical applications may
`
`
`
`
`
`
`
`
`
`
`require tight control on packet
`loss and delay on each
`
`
`
`
`
`
`
`
`individual flow. In addition, some voice or videotraffic 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 QoScan 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.
`
`
`
`
`
`
`
`MPOAenables AIMservicesto be integrated with existing
`
`
`
`
`
`
`
`
`
`local area networks (LANs)that use Ethernet, token ring or
`
`
`
`
`
`
`
`TCP/IPprotocols. 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, mostefficiently,
`
`
`
`
`
`
`
`
`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 numberof 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
`
`
`
`
`
`
`numberof simultaneous shortcuts, but decreases the shortcut
`
`
`setup rate.
`
`
`
`
`
`
`
`Workin this areais 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 numberof 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 parametersetting is statically assigned based
`
`
`
`
`
`
`
`
`on somepredefined IP traffic statistics. However, the static
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1028
`
`Page9
`
`Splunk Inc. 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
`schemeis 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, 1.¢., adjust-
`
`
`
`
`
`
`
`ing two control parameters in different directions. Simula-
`
`
`
`
`
`
`
`
`tion results have shown some advantages of this adaptive
`
`
`
`
`
`
`
`
`
`approach overthe static one. However, dueto 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 schemefor setting up and tearing downshortcuts,
`
`
`
`
`
`
`
`
`
`that can adjust itself to data traffic dynamics without being
`
`
`
`
`unnecessarily complex, is also required.
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`The present invention is directed to a State Dependent
`
`
`
`
`
`
`
`Dynamic Triggering Scheme (SDDTS)that addresses the
`
`
`
`
`
`
`
`
`above mentioned problemsofthe 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, 1.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
`
`
`
`
`
`
`
`for
`calculations to dynamically adjust
`two parameters,
`
`
`
`
`
`
`
`
`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 schemeis 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
`
`
`
`
`
`
`
`
`trigger and abatement period trigger values. The
`onset
`
`
`
`
`
`
`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 numberof shortcuts
`
`
`
`
`
`
`
`
`
`and the performance target, the more shortcuts, the better
`
`
`
`
`
`
`
`performance if there is no physical limit in terms of short-
`
`
`
`
`
`
`
`cuts. However, the numberof 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 anyfuture traffic, they maystill 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
`
`
`
`
`
`
`
`
`
`abatementcriterion 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 subjectto 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 QoStraffic that is routed
`
`
`
`
`
`
`
`
`through shortcuts. Thus another objective of the present
`
`
`
`
`
`
`
`
`invention is to keep the average shortcut numbercloseto its
`limit and at the same time to reduce the chances that shortcut
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`number
`reaches its limit. Embodiments of the present
`
`
`
`
`
`
`
`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 mostefficient 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 downin accordance with an exemplary embodi-
`
`
`
`
`ment of the present invention.
`
`
`
`
`
`
`
`FIG. 3 is an graphillustrating 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 1
`
`
`
`
`
`
`
`
`
`is shown with a plurality of inputs 2-6 to the router. These
`
`
`
`
`
`
`
`
`
`may bevia plurality of ports located on the router or via a
`
`
`
`
`
`
`
`single port having the capability to multiplex a plurality of
`
`Splunk Inc.
`
`Exhibit1028
`
`Page 10
`
`Splunk Inc. Exhibit 1028 Page 10
`
`

`

`
`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-
`
`
`
`
`
`
`
`
`mentperiods 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 incomingdata 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 embodimentof
`
`
`
`
`
`
`
`
`
`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 shownin step 101. If the
`
`
`
`
`
`
`
`
`packet belongsto 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 embodimentofthe 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 downloadedto the controller and/or may be stored
`
`
`
`
`
`
`
`
`in an EPROMoranysuch suitable device. As shownin 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 countof data packets belonging to
`
`
`
`
`
`
`
`
`a particular flow and/ora set of packets matching a particular
`
`
`
`
`
`
`
`
`
`profile. Thus, in essence, the onset trigger counter may keep
`
`
`
`
`
`
`
`
`
`a running record of the numberof 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 whetherthe time, knownasthe onset period,
`
`
`
`
`
`
`
`
`
`
`for resetting the onset trigger to zero been reached.If, for
`
`
`
`
`
`
`
`example, the numberof data packets received,of a particular
`
`
`
`
`
`
`
`
`
`flow, does not equal at
`least
`the number of packets as
`
`
`
`
`
`
`
`
`specified by the onsettrigger 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 shownin step
`
`
`
`
`
`
`
`
`108. This onset period may be based, for example, on a
`
`
`
`
`
`predetermined value or may bealternatively determined by
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`US 6,385,170 B1
`
`
`6
`
`
`
`
`
`
`
`
`
`
`any suitable technique knownin theart. If the onset trigger
`
`
`
`
`
`
`
`
`
`
`counter 1s reset to zero, as shown in step 108, then this
`
`
`
`
`
`
`
`information may be provided back to the controller so that
`
`
`
`
`
`
`
`
`
`counting mayrestart as packets related to that flow are again
`
`
`
`
`
`
`received by the router or switch. On the other hand, if data
`
`
`
`
`
`
`
`packets fitting a particula