`Packer
`
`54 METHOD FOR EXPLICIT DATA RATE
`CONTROL IN A PACKET COMMUNICATION
`ENVIRONMENT WITHOUT DATA RATE
`SUPERVISION
`
`75 Inventor: Robert L. Packer, Los Gatos, Calif.
`73 Assignee: Packeteer, Inc., Cupertino, Calif.
`*
`Notice:
`This patent issued on a continued pros
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`
`21 Appl. No.: 08/742,994
`22 Filed:
`Nov. 1, 1996
`(51) Int. Cl." ..................................................... H04L 12/26
`52 U.S. Cl. ........................... 370/231; 370/232; 370/235
`58 Field of Search ...................................... 370/229-238
`56)
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,042,029 8/1991 Hayakawa ................................. 370/60
`5,193,151
`3/1993 Jain.
`5,359,593 10/1994 Derby et al..
`5,426,635
`6/1995 Mitra et al..
`5,455.826 10/1995 OZveren et al..
`OTHER PUBLICATIONS
`Balakrishnan, H., et al., “Improving TCP/IP Performance
`Over Wireless Networks', Proc. of 1st ACM Conf. on
`Mobile Computing and Networking, Berkeley, CA, Nov.
`1995, 10 pages.
`RFC 793, “Transmission Control Protocol-DARPA Inter
`net Program Protocol Specification”, Postel, ed., 1981, 87
`pageS.
`
`O
`
`SERVER-TCPEND SYSTEM
`
`12
`
`US00603821.6A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,038,216
`*Mar. 14, 2000
`
`RFC 1122, “Requirements for Internet Hosts”, Branden, ed.,
`1989, 116 pages.
`20.3 Sliding Windows, TCP/IP Illustrated, vol. I, pp.
`280-284.
`10 Protocol Layering, TCP/IP, vol. I, pp. 139-144.
`2.5 The Idea Behind Sliding Windows, TCP/IP, vol. I, pp.
`175-177.
`12.10 Variable Window Size and Flow Control, TCP/IP, vol.
`I, pp. 182-194.
`14 TCP: Flow Control and Adaptive Retransmission, TCP/
`IP, vol. II, pp. 261–283.
`Thomas, Stephen A., “IPng and the TCP/IP Protocols”, John
`Wiley & Sons, Inc., pp. 239-240, 1996.
`Fengmin Gong et al., “Study of a two-level flow control
`scheme and buffering strategies”, INFOCOM'94. Network
`ing for Global Communications., 13th Proceedings IEEE
`(94CH3401-7), vol. 3, pp. 1224-1233, Jun. 1994.
`Roberts, Lawrence G. “Explicit Rate Flow Control.” Apr.
`1997, IrobertsGaziplink.net; http://www.ziplink.net/~lrob
`erts/Ex . . . ate/Explicit-Rate-Flow-Control.htm; pp. 1-14.
`
`Primary Examiner Melvin Marcelo
`Attorney, Agent, or Firm Townsend and Townsend and
`Crew LLP; Kenneth R. Allen
`57
`ABSTRACT
`A method for explicit data rate control is introduced into a
`packet communication environment (10) which does not
`have data rate Supervision by adding latency to the acknowl
`edgment (ACK) packet and by adjusting the size of the flow
`control window associated with the packet in order to
`directly control the data rate of the Source data at the Station
`(12 or 14) originating the packet.
`
`19 Claims, 10 Drawing Sheets
`
`CLEN CPEND SYSTEM
`
`14
`
`
`
`
`
`
`
`ACCESS LINK
`/
`18
`
`NETWORK
`COUD
`
`
`
`
`
`
`
`
`
`24
`
`ROUTER
`
`
`
`22
`ACCESS LINK
`
`26
`
`RATE CONTROL
`
`DEVICE i
`
`
`
`Splunk Inc. Exhibit 1059 Page 1
`
`
`
`Mar. 14, 2000
`
`Sheet 1 of 10
`
`6,038,216
`
`U.S. Patent
`
`
`
`WALSASGN3dOL-LNAINoU
`
`Y3.LNOY
`
`gaogapeapae
`
`eocesoseoce
`
`MYOMLAN
`
`gnoto
`
`
`
`aanvlWALSASGNAdOL-YaAuasS
`
`
`
`
`
`INISS300¥TOWLNOOSve
`
`7feoscoecose
`
`bOld
`
`
`
`YNITSSsa00V
`
`—zz
`
`gooopo0000nOD
`
`jessovecees
`
`Y3LNOW
`
`Splunk Inc.
`
`Exhibit 1059
`
`Page 2
`
`301g92
`
`Splunk Inc. Exhibit 1059 Page 2
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 2 of 10
`
`6,038,216
`
`top Schedule
`
`MT 2O1
`
`204
`
`208
`
`212
`
`216
`
`
`
`
`
`
`
`
`
`Update Data Rate
`ReCW'd for this
`Connection
`
`Find the CR/ER
`Policy for this
`Connection and
`Direction
`
`Schedule an
`Immediate
`Transmission
`
`Dispose of
`Retransmission
`Data in
`Packer Buffer
`
`
`
`
`
`
`
`2O2
`
`Yes
`
`TCP Data
`Present?
`
`
`
`No
`
`2O6
`
`Yes
`
`Start of a
`New Burst?
`
`No
`
`21 O
`
`ls there a
`Target Rate?
`
`No
`
`Yes
`
`
`
`
`
`
`
`214
`
`Holding a
`Retransmission
`of Data for which We
`are Delaying a
`
`Yes
`
`NO
`
`
`
`218
`
`
`
`This ACK seq.>
`
`Yes
`
`
`
`No
`
`22O
`
`
`
`
`
`
`
`Data Rate
`on the Other Half
`Connection Exceeds
`its Target
`Rate?
`
`Yes
`
`No
`
`Splunk Inc. Exhibit 1059 Page 3
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 3 of 10
`
`6,038,216
`
`()
`
`
`
`Set lastAckFor Warded
`for this Half Connection
`to tcpHar->ack
`
`
`
`3.22.
`
`TCP Data to
`Schedule?
`
`
`
`
`
`22
`-
`
`
`
`Set timeLastFresh AckForwarded on
`this Half Connection to Current Time to
`Cause an Immediate Transmit
`
`Yes
`
`- Change ACK on the
`Data Packet and
`Forward it immediately
`(See Fig. 2C)
`
`
`
`Schedule Packet for
`Immediate
`Transmission
`
`4-Yes
`
`Was an ACK
`Created?
`
`
`
`
`
`2-32
`
`Invoke tcpDownShift to
`Handle CPACK
`Packets
`(See Fig. 2D)
`
`Fig. 2B
`
`Splunk Inc. Exhibit 1059 Page 4
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 4 of 10
`
`6,038,216
`
`topSeparate Data
`
`M 205
`
`240
`
`
`
`is there Already
`an ACK Packet for this
`Connection?
`
`No
`
`
`
`
`
`
`
`
`
`Yes
`
`
`
`246
`
`Set Flag on this Half
`Connection to Reuse the
`ackPacket When it is
`Eventually Recycled at
`Transmit Complete
`
`
`
`248
`
`
`
`
`
`Change ACK and
`Checksum in Original
`Packet and Sent It
`
`250
`
`New ack Packet?
`
`No
`
`Return (ackPacket)
`
`Copy Front of
`Packet ( ip and top
`header ) into new
`ackPacket
`
`242
`
`Update the Length
`in the ackPacket
`to exclude data
`
`244
`
`Yes
`
`Compute and Set
`Checksum for the
`ackPacket
`
`252
`
`Fig. 2C
`(Step 228 of Fig. 2B)
`
`Splunk Inc. Exhibit 1059 Page 5
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 5 of 10
`
`6,038,216
`
`256 topDownShift
`
`Set up new Ack packet:
`1. Set this half Connections
`ack packet to point to this
`packet
`2. Set the appropriate
`recycle function and
`argument to capture the
`transmit complete
`A.
`confirmation from the driver
`
`
`
`
`
`
`
`
`
`- 255
`
`
`
`257
`
`Return
`
`Mark Ack
`packet
`for reuse
`and recycle
`
`- 260
`amount of
`data > tWO
`MSS2
`
`
`
`
`
`
`
`
`
`NO
`Compute:
`1. Time since last ack
`2. Target rate
`3. Actual rate
`4. Time until ack req'd
`
`262
`
`Clamp the
`neWAck at the
`lastAckForwarded
`H
`2 . MSS
`
`263
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`268
`
`264
`
`266
`
`Set Other Half
`Connection Actual
`Rate to Ratio of
`Data Rate
`/ RTO Time
`
`Data
`Rate Reduction
`Achievable in One
`Step? (See
`Fig.2F)
`
`Set Other Half
`Connection Actual
`Rate to Target Rate
`
`
`
`
`
`
`
`
`
`Late
`in Sending
`an Ack?
`
`270
`
`272
`
`ls. There
`Unack'd Data? YES
`
`Apply Existing
`Late CarryOver
`to Reduce
`Delay Here
`
`
`
`Existing Late
`CarryOver for this
`Connection?
`
`
`
`
`
`
`
`FIG. 2D
`(Step 232 of Fig. 2B)
`
`274
`
`Recover Time by
`Acking More Data
`
`279
`Set Flag indicating a
`Late Carryover
`
`28O
`
`Check Window Size
`is Not Causing Ack
`to be Late
`(See Fig. 2G)
`
`Splunk Inc. Exhibit 1059 Page 6
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 6 of 10
`
`6,038,216
`
`
`
`
`
`
`
`
`
`
`
`Compute:
`A Transmission Time Delay =
`Time until next ACK must be
`sent to maintain the target
`data rate - Time since last ACK
`was sent (Computed in Fig. 2D,
`step 263)
`
`281
`
`284
`
`
`
`Scale DOWn
`Advertised
`Receive WindoW
`
`
`
`
`
`ls the
`Advertised Receive
`Window Too Large?
`(See Fig.2H)
`
`
`
`
`
`
`
`Update
`Checksum in
`Packet Header
`
`
`
`
`
`
`
`Schedule Packet
`for Transmission at
`Time = Present
`Time + Delay
`Computed
`in step 281
`
`
`
`
`
`288
`
`FIG. 2E
`
`Splunk Inc. Exhibit 1059 Page 7
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 7 of 10
`
`6,038,216
`
`209
`
`M
`
`290
`
`292
`
`294
`
`topRtoTime
`
`
`
`Determine Time
`to RTO
`
`Reduce Time to
`RTO by Time to
`Send an ACK
`
`Further Reduce
`RTO by a
`Safety Factor
`
`Return (Rto )
`
`Fig. 2F
`(Step 264 of Fig. 2D )
`
`Splunk Inc. Exhibit 1059 Page 8
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 8 of 10
`
`6,038,216
`
`2
`
`topCheckMinWinSize
`
`Bete
`
`Determine the Time
`Since Last increase in
`Window Size
`
`!--
`
`Determine the
`Minimum Window
`increase Time" the
`Maximum Window
`Adjustment
`
`
`
`
`
`
`
`Determine the Lesser
`of the Quantities
`Computed in Steps
`300 and 302
`
`Scale Quantity
`Computed in Step 304
`by the Minimum
`Window Size
`
`Reduce the Maximum
`Window Adjustment
`Segments by the
`Quantity Computed in
`Step 306
`
`3 ed
`
`increase the Minimum
`Number of MSS Sized
`Segments in Window
`by the Quantity
`Computed in Step 308
`
`Fig. 2G
`(Step 280 of Fig. 2D )
`
`Splunk Inc. Exhibit 1059 Page 9
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 9 of 10
`
`6,038,216
`
`topUpdateAckRxWindow
`
`2.
`
`/
`
`
`
`
`
`Reset Closing Flag
`
`Return (False)
`
`Original Amt
`Ack'd > 2 " MSS AND
`No CarryOver?
`
`Yes
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`32
`
`Win Closing
`Flag Not Set?
`
`Set Window Size to -
`Allow the Specified
`Rate Given the Current
`RTT and the Detected
`Speed
`
`
`
`Clamp Receive
`WindoW to at Least
`2 * MSS
`
`so
`w)
`
`MOWe Revised WindoW
`into Packet
`
`Return (True)
`
`J.
`
`Set Win Closing Flag
`(Adjustment Will
`Occur in Next Ack)
`
`Return (False)
`
`Fig. 2H
`(Step 282 of Fig. 2E)
`
`Splunk Inc. Exhibit 1059 Page 10
`
`
`
`U.S. Patent
`
`Mar. 14, 2000
`
`Sheet 10 of 10
`
`6,038,216
`
`top Sched AckEmitted
`
`215
`
`M
`
`
`
`
`
`
`
`330
`
`No
`
`ls the
`Connection Still
`Valid?
`
`332
`
`Set
`lastAckForwarded
`for this Half
`Connection
`
`
`
`Set
`time Last FreshAckForwarded
`for this Half Connection
`to the Current Time
`
`334
`
`336
`
`ls the
`lastAckForwarded F
`lastAckRCvd?
`
`Yes
`
`
`
`
`
`
`
`338
`
`340
`
`Set New Ack to
`Equal lastAckRCvd
`
`
`
`Invoke tcpDownshift
`in Order to Compute
`New Ack Time and
`to Reschedule Packet
`(See Fig. 2D )
`
`Fig. 2
`
`Splunk Inc. Exhibit 1059 Page 11
`
`
`
`1
`METHOD FOR EXPLCIT DATA RATE
`CONTROL IN A PACKET COMMUNICATION
`ENVIRONMENT WITHOUT DATA RATE
`SUPERVISION
`
`COPYRIGHT NOTICE
`A portion of the disclosure of this patent document
`contains material which is Subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`This invention relate S to digital packet
`telecommunications, and particularly to data flow rate con
`trol at a particular layer of a digitally-Switched packet
`telecommunications environment normally not Subject to
`data flow rate control wherein data packets are communi
`cated at a variety of rates without Supervision as to rate of
`data transfer, such as under the TCP/IP protocol Suite.
`The widely-used TCP/IP protocol Suite, which imple
`ments the World-wide data communication network envi
`ronment called the Internet and is employed in local net
`works also (Intranets), intentionally omits any explicit
`Supervisory function over the rate of data transport over the
`various media which comprise the network. While there are
`certain perceived advantages, this characteristic has the
`consequence of juxtaposing very high-Speed packets and
`very low-Speed packets in potential conflict and the resultant
`inefficiencies. Certain loading conditions can even cause
`instabilities which could lead to overloads that could stop
`data transfer temporarily. It is therefore considered desirable
`to provide Some mechanism to optimize efficiency of data
`transfer while minimizing the risk of data loSS.
`In order to understand the exact context of the invention,
`an explanation of technical aspects of the Internet/Intranet
`telecommunications environment may prove helpful.
`Internet/Intranet technology is based largely on the TCP/
`IP protocol suite, where IP is the network level Internet
`Protocol and TCP is the transport level Transmission Control
`Protocol. At the network level, IP provides a “datagram”
`delivery service. By contrast, TCP builds a transport level
`Service on top of the datagram Service to provide guaranteed,
`sequential delivery of a byte stream between two IP hosts.
`TCP has flow control mechanisms operative at the end
`stations only to limit the rate at which a TCP endpoint will
`emit data, but it does not employ explicit data rate control.
`The basic flow control mechanism is a sliding window, a
`time slot within an allowable window which by its sliding
`operation essentially limits the amount of unacknowledged
`transmit data that a transmitter can emit.
`Another flow control mechanism is a congestion window,
`which is a refinement of the sliding window scheme involv
`ing a conservative expansion to make use of the full,
`allowable window. A component of this mechanism is
`Sometimes referred to as slow start.
`The sliding window flow control mechanism works in
`conjunction with the Retransmit Timeout Mechanism
`(RTO), which is a timeout to prompt a retransmission of
`unacknowledged data. The timeout length is based on a
`running average of the Round Trip Time (RTT) for acknowl
`edgment receipt, i.e. if an acknowledgment is not received
`within (typically) the smoothed RTT+4* mean deviation,
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,038,216
`
`2
`then packet loSS is inferred and the data pending acknowl
`edgment is retransmitted.
`Data rate flow control mechanisms which are operative
`end-to-end without explicit data rate control draw a Strong
`inference of congestion from packet loss (inferred, typically,
`by RTO). TCP end systems, for example, will back-off,
`i.e., inhibit transmission in increasing multiples of the base
`RTT average as a reaction to consecutive packet loSS.
`Bandwidth Management in TCP/IP Networks
`Bandwidth management in TCP/IP networks is accom
`plished by a combination of TCP end systems and routers
`which queue packets and discard packets when Some con
`gestion threshold is exceeded. The discarded and therefore
`unacknowledged packet Serves as a feedback mechanism to
`the TCP transmitter. (TCP end systems are clients or servers
`running the TCP transport protocol, typically as part of their
`operating System.)
`The term “bandwidth management is often used to refer
`to link level bandwidth management, e.g. multiple line
`support for Point to Point Protocol (PPP). Link level band
`width management is essentially the process of keeping
`track of all traffic and deciding whether an additional dial
`line or ISDN channel should be opened or an extraneous one
`closed. The field of this invention is concerned with network
`level bandwidth management, i.e. policies to assign avail
`able bandwidth from a single logical link to network flows.
`RouterS Support various queuing options. These options
`are generally intended to promote fairneSS and to provide a
`rough ability to partition and prioritize Separate classes of
`traffic. Configuring these queuing options with any precision
`or without side effects is in fact very difficult, and in some
`cases, not possible. Seemingly simple things, Such as the
`length of the queue, have a profound effect on traffic
`characteristics. Discarding packets as a feedback mechanism
`to TCP end Systems may cause large, uneven delays per
`ceptible to interactive users.
`Routers can only control outbound traffic. A 5% load or
`less on outbound traffic can correspond to a 100% load on
`inbound traffic, due to the typical imbalance between an
`outbound Stream of acknowledgments and an inbound
`Stream of data.
`A mechanism is needed to control traffic which is more
`efficient in that it is more tolerant of and responsive to traffic
`loading.
`As background, further information about TCP/IP and the
`state of the art of flow control may be had in the following
`publications:
`Comer, Douglas. Internetworking with TCP/IP Vol. I.
`Prentice Hall, 1991.
`Comer, Douglas and Stevens, David. Internetworking
`with TCP/IP Vol. II. Design, Implementation, and Internals.
`Prentice Hall, 1991.
`W. Richard Stevens, TCP/IP Illustrated. Vol. I-The Pro
`tocols. Addison-Wesley. 1994.
`RFC 793. Transmission Control Protocol. Postel, 1981.
`RFC 1122. Host Requirements. Braden 1989.
`A particularly relevant reference to the present work is:
`Hari Balakrishnan, Srinivasan Seshan, Elan Amir, Randy
`H. Katz. Improving TCP/IP Performance over Wireless
`Networks. Proc. 1st ACM Conf. on Mobile Computing and
`Networking, Berkeley, Calif., November 1995.
`The above document reports efforts of a research group at
`the University of California at Berkeley to implement TCP
`interior spoofing to mitigate the effects of Single packet
`
`Splunk Inc. Exhibit 1059 Page 12
`
`
`
`6,038,216
`
`3
`loSS in micro-cellular wireleSS networks. Its mechanism is
`the buffering of data and performing retransmissions to
`preempt end to end RTO. It is a Software mechanism at a
`wireleSS network based Station which will aggressively retry
`transmission a Single time when it inferS that a single packet
`loSS has occurred. This is a more aggressive retransmission
`than the normal TCP RTO mechanism or the quick recov
`ery mechanism, whereby a transmitter retransmits after
`receiving N consecutive identical acknowledgments when
`there is a window of data pending acknowledgment.
`Sliding window protocols are known, as in Comer, Vol. I.
`page 175. Known sliding window protocols are not time
`based. Rate is a byproduct of the characteristics of the
`network and the end Systems.
`
`SUMMARY OF THE INVENTION
`According to the invention, a method for explicit network
`level data rate control is introduced into a level of a packet
`communication environment at which there is a lack of data
`rate Supervision to control assignment of available band
`width from a single logical link to network flows. The
`method includes adding latency to the acknowledgment
`(ACK) packet of the network level and adjusting the
`reported size of the existing flow control window associated
`with the packet in order to directly control the data rate of
`the Source data at the Station originating the packet.
`Called direct feedback rate control, the method comprises
`a mechanism that mitigates TCP packet level traffic through
`a given link in order to manage the bandwidth of that link.
`A Software mechanism to implement the function may be a
`Software driver, part of a kernel of an operating System or a
`management function implemented on a separate dedicated
`machine in the communication path.
`The invention has the advantage of being transparent to
`all other protocol entities in a TCP/IP network environment,
`For example, in the connections controlled according to the
`invention, it is transparent to TCP end Systems (i.e., end
`systems using the TCP protocol).
`The invention will be better understood upon reference to
`the following detailed description in connection with the
`accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a System according to the
`invention.
`FIGS. 2A-2I depict flowcharts of a particular embodi
`ment according to the invention.
`DETAILED DESCRIPTION OF SPECIFIC
`EMBODIMENTS
`Referring to FIG. 1, a system 10 which uses the invention
`comprises a first TCP end System 12, Such as a Server device,
`a second TCP end system 14, such as a client device, which
`is connected through a first router 16 and thence via a first
`access link 18 into a network cloud 20 of a character as
`hereinafter explained, which in turn provides a logical
`connection via a Second access link 22 to a Second router 24.
`According to the invention, there is provided between at
`least one of the end Systems 12 and one of the routerS 24 a
`rate control device 26 which is operative to control the rate
`at which a TCP transmitter can emit packets. In this
`invention, rate control is accomplished by (1) delaying the
`transmission of an acknowledgment, which may be a special
`packet, (known as an ACK) issued by the end System 12 or
`14; and/or by (2) modifying the report of the length of the
`
`4
`receive window in those same packets, and/or by (2) gen
`erating acknowledgments Substantially independently of the
`acknowledgments generated by the end receiving Station.
`The rate control device 26 is preferably placed at the end
`System acting as the Server, but a rate control device may be
`placed adjacent any System in a path for data. At the Server,
`it is most effective in controlling flow rate because it
`typically receives and relays the bulk of the traffic of interest.
`Several factors are employed to weight the length of the
`added acknowledgment delay: the amount of data being
`acknowledged, the measured and Smoothed round trip time,
`the targeted transmission rate, and the mean of the deviation
`between the measured and Smoothed roundtrip time.
`The direct feedback rate control mechanism may be
`incorporated conveniently into computer-executable code,
`assuming the end System or the router is programmable. It
`can be used in an open loop environment or it can be used
`with a rate monitoring mechanism that provides an indica
`tion of flow rate.
`The following is a detailed description of a specific
`embodiment of a direct feedback rate control mechanism
`expressed in pseudocode. For example, the pseudo-code
`explains a mechanism of generating acknowledgments,
`including Substituting acknowledgments. This pseudo-code
`also addresses specifics of the TCP environment. It should
`be noted that latency and the sliding window flow control
`can be implemented anywhere in the data path.
`According to an embodiment of the present invention, a
`method for controlling data rate of data packets in a digital
`data packet communication environment is provided. This
`environment employs TCP/IP protocols and has a plurality
`of interconnected digital packet transmission Stations. TCP/
`IP data packet communication environments lack explicit
`end-to-end data rate Supervision, Such as that found in ATM
`or Frame Relay Systems. In this invention, a first digital
`packet transmission Station Sends at least one Source packet
`to a Second digital packet transmission Station over the
`network. The first digital packet transmission Station waits
`for typically one acknowledgment packet before Sending
`additional Source packets. The Second digital packet trans
`mission Station sends an acknowledgment packet toward the
`first digital packet transmission Station after receipt of the at
`least one Source packet.
`The Second digital packet transmission Station can thus
`establish a limit on explicit rate of emission of packets from
`the first transmission Station to the Second transmission
`Station. It invokes this limit by the timing of transmission of
`the acknowledgment packet from the Second digital packet
`transmission Station to the first digital packet transmission
`Station. Specifically, the Second digital packet transmission
`Station will insert a latency or delay in issuance of the
`acknowledgment packet. The latency will be based upon the
`Selected limit. The latency can be invoked at any point
`traversed by the acknowledgment packet by delaying propa
`gation of the acknowledgment packet through that point.
`One way this is done is by intercepting the acknowledgment
`packet at an intermediate point, and rescheduling it and
`reusing it, i.e., Substituting a duplicate acknowledgment
`packet at a delay from normal propagation. An alternative to
`the duplicate Substitution is the Substitution of a Sequence of
`values which include the acknowledgment Sequence indica
`tors. The Substitution Sequence might also include other
`indicia, for example, an indication of a Suitable window Size
`to be communicated to the first transmission Station. These
`indicators Serve to signal to the first transmission Station the
`information needed to repackage groupings of packets,
`which also imposes an upper limit and explicit transmission
`rate.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Splunk Inc. Exhibit 1059 Page 13
`
`
`
`S
`Substitute acknowledgment packets can be generated at
`any point of latency in response to groupings of packets
`from the first digital packet transmission Station. The
`acknowledgments and the groupings can be generated with
`out correlation to time, range of data being acknowledged,
`window Size being advertised to the first transmission Station
`and number of acknowledgments. The Selection of the
`latency time in theory can be a manually preset value.
`Alternatively it can be Selected based on a simple formula
`relating latency to explicit maximum rate of transmission.
`Since the rate of emission of packets from a Source or first
`transmission Station to the Second transmission Station is a
`limited by the fact that acknowledgments must be received
`before the next emission of a packet or grouping of packets,
`the latency of acknowledgment imposes an upper bound on
`explicit transmission rate.
`FIG. 2A depicts a flow chart 201 of processing steps in the
`subroutine tcpschedule. This routine is invoked for every
`TCP Segment to Schedule its emission. In a decisional Step
`202, a check is made whether there is TCP data present. If
`this is so, then in a step 204 the data rate received for this
`connection is updated and processed. Otherwise, or in any
`event, processing continues with a decisional Step 206
`wherein a check is made whether the packets being tested
`are the start of a new burst. If this is so, then in a step 208,
`an appropriate policy for this connection and this direction
`of traffic flow is found. This yields a combination of CIR
`(committed information rate) and EIR (excess information
`rate). Otherwise, or in any event, processing continues with
`a decisional Step 210 wherein a check is performed to See if
`there is a target rate associated with this flow. If there is no
`target rate, then in a step 212, the packet is Scheduled for an
`immediate transmission after which processing returns.
`Otherwise, if there is a target rate for this particular flow,
`then in a decisional Step 214, a check is performed to See if
`an acknowledgment packet or Sequence (ACK) for the
`outbound retransmission of TCP data is being retained. This
`check determines whether: 1) there is TCP data AND 2) it is
`a retransmitted data packet and 3) an ACK is being retained
`for this data. If all these conditions are true, the retransmitted
`data packet is discarded in a step 216. Abuffer containing the
`packet is cleared and processing returns. This Step ensures
`that there is no retransmission caused by our own acknowl
`edgment delay. If this is not So, then in a step 218, a check
`is made to see if this acknowledgment (ACK) sequence is
`greater than the last forwarded acknowledgment Sequence.
`If this is So, then in a decisional Step 220, a check is made
`to see if the data rate on the other half connection (data
`flowing in the other direction along this connection) exceeds
`its target rate.
`FIG. 2B depicts a continuation flow chart 203. If the test
`in step 218 in FIG. 2A of whether this ACK sequence is
`greater than the last forwarded ACK Sequence fails, then
`processing continues with a step 234 in FIG.2B, wherein the
`packet is Scheduled for immediate transmission and then
`processing returns. If the test of decisional step 220 in FIG.
`2A, of whether the data rate on the other half connection
`exceeds its target rate, fails, then processing continues with
`a step 222 in FIG. 2B, wherein a lastACKforwarded (last
`acknowledgment forwarded) variable is set for this particu
`lar half connection to tcphdr pointing on ACK. Then in a
`step 224, variable timeLastFresh AckForwarded for this half
`connection is set to the current time in order to cause an
`immediate transmit. Then in Step 234, the packet is Sched
`uled for immediate transmission and processing returns.
`Finally, if the test of step 220 in FIG. 2A, whether the data
`rate on the other half connection exceeds its target rate, is
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,038,216
`
`6
`true, then processing continues with a decisional Step 226 in
`FIG.2B, in which a check is made whether there is TCP data
`to Schedule. If this is not So, then in a Step 228, a procedure
`tcpSeparateData is invoked in order to change the ACK
`value on the data packet and forward it immediately. Then
`in a decisional Step 230, a test is performed to determine
`whether a new ACK was created. If step 230 is not true, then
`the processing returns. Otherwise a new ACK was created,
`So processing continues with a step 232, in which routine
`tcpDownShift is invoked to handle TCPACK packets. After
`Step 232, processing returns. If the test in decisional Step 226
`fails because there is no TCP data to schedule, then pro
`cessing continues directly with Step 232 to invoke tcpDown
`Shift to handle TCP packets. After step 232, processing
`returns.
`FIG. 2C depicts a flow chart 205 of the process steps of
`routine tcpSeparateData which is step 228 of FIG. 2B. This
`Subroutine is invoked by routine tcpSchedule to Separate
`data from IP and TCP headers, assign it an older (i.e., prior)
`ACK and Schedule the transmission, or to create a new
`ACK-only packet with Specified ACK Sequence and to
`return it. In a decisional Step 240, a determination is made
`whether an ACK packet for this connection already exists. If
`this is not So, then a new ACK packet is created. In a step
`242, the front of the packet, i.e. the IP and TCP headers, is
`copied into the newly created ACK packet. Then in a step
`244, the length in the newly created ACK packet is updated
`in order to exclude the length of the data.
`If the test in step 240 is true, then in a step 246, a flag for
`this half connection is Set to cause a reuse of the existing
`ACK packet when it is eventually recycled at transmit
`complete time. Subsequently, in a step 248, the ACK and
`checksum in the original packet are altered and it is sent.
`Then in a decisional step 250, a determination is made
`whether a new ACK packet was created. If this is So, then in
`a step 252 the checksum is computed and Set for the newly
`created packet. Otherwise, or in any event, the ACK packet
`is returned.
`FIG. 2D depicts a flow chart 207 of the processing steps
`of Subroutine tcpDownShift. This subroutine is called from
`function topSchedule and from a recycle routine to Schedule
`an acknowledgment for a half connection which is exceed
`ing its target rate based on information Supplied to it.
`TcpDownShift is the function to choose a latency time to
`establish a limit on explicit rate of emission of packets from
`the first transmission Station to the Second transmission
`Station. One technique for establishing the limit on rate is to
`generate Substitute acknowledgment packets at a point of
`latency in response to groupings of packets received from
`the first digital packet transmission Station. In a first deci
`sional step 255, a determination is made whether there is
`already an acknowledgment outstanding for this half con
`nection. If this is So, then in a step 257, that outstanding
`acknowledgment packet is marked for reuse at the appro
`priate time after its Scheduled transmission and the routine
`returns to its caller. Otherwise, in a step 256, a new acknowl
`edgment packet is prepared. An indicator for this half
`connection's acknowledgment packet is Set to point to the
`new acknowledgment packet. A recycle function and argu
`ment to capture the transmit complete confirmation from the
`driver is also associated with the new acknowledgment
`packet. Then, in a first decisional Step 260, a determination
`is made whether the amount of data to be acknowledged is
`greater than two times the MSS (Maximum Segment Size).
`If this is the case, then in a step 262, processing “clamps' the
`new acknowledgment at the last AcknowledgementFor
`warded added to the amount of two times the MSS. This has
`
`Splunk Inc. Exhibit 1059 Page 14
`
`
`
`6,038,216
`
`15
`
`25
`
`7
`the effect of limiting the acknowledgment to the position
`where the last acknowledgment occurred, plus a number of
`bytes equal to two times the MSS. Otherwise, or in any
`event, in a step 263, values are computed for: 1) a time since
`the last acknowledgment was Sent for the particular
`connection, 2) a target data rate for the connection, 3) an
`actual rate for the connection and 4) an amount of time until
`the acknowledgment must be sent back to achieve the target
`data rate. The time to Send an acknowledgment is computed
`from the amount of data Sent from the first transmission
`Station and the target rate for the connection. Thus, the
`timing of the acknowledgment is not dependent upon time,
`range of data being acknowledged, advertised window Size
`and number of acknowledgments. In a decisional Step 264,
`a determination is made whether data rate reduction can be
`achieved in a single Step without incurring an RTO at the
`Sender. In other words, the q