(12) United States Patent
`US 6,401,127 B1
`(10) Patent N0.:
`Lei et al.
`(45) Date of Patent:
`Jun. 4, 2002
`
`US006401127B1
`
`(54) ADAPTIVE TIMER FOR LLC TYPE 2
`RELIABLE TRANSPORT IN A COMPUTER
`NETWORK
`
`(75)
`
`Inventors: Alan Lei, Fremont; Nitin Karkhanis,
`San Francisco; Richard Livingston,
`Hollister; Uwe Sellentin, San Jose‘, all
`of CA (US)
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/304,395
`
`(22)
`
`Filed:
`
`May 4, 1999
`
`Int. Cl.7 ................................................ G06F 13/00
`(51)
`(52) US. Cl.
`........................................ 709/235; 709/232
`(58) Field of Search .................................. 709/200—253
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`7/1994 Francis et al.
`................ 370/54
`5,331,637 A
`10/1994 Tsuchiya ........
`370/60
`5,353,283 A
`
`........ 370/94.1
`8/1995 Perkins et al.
`..
`5,442,633 A
`12/1996 Tsuchiya ............... 395/200.15
`5,583,996 A
`......... 370/404
`2/1997 Chang et al.
`5,600,644 A
`
`5/1997 Callon ..................... 370/397
`5,633,866 A
`
`............. 370/397
`10/1998 Burwell et al.
`5,818,842 A
`10/1998 Civanlar et al.
`....... 395/200.58
`5,828,844 A
`4/1999 Virgile ....................... 370/381
`5,898,686 A
`6/1999 Alexander, Jr. et al.
`370/395
`5,909,441 A
`6/1999 Shankar et al.
`........ 395/200.57
`5,909,550 A
`6/2000 Wesley ....................... 709/235
`6,076,114 A *
`OTHER PUBLICATIONS
`
`Pearlman, Radia, Interconnections, Bridges and Routers,
`Addison Wesley, 1992, pp. 34—35.
`Tanenbaum, Andrew, Computer Networks, Second Edition,
`1988, PGS. 253—257.
`
`Comer, Douglas, E., Internetworking With TCP/IR 3rd Edi-
`tion, vol. I, Prentice Hall, 1995, pp. 208—216.
`
`Tanenbaum, Andrew 8., “Computer Networks, 3rd edition”,
`Prentice Hall, PTR, 1996, pp. 28—54.
`RFC 1795 “IETF”, Request For Comments, Informational
`RFC, RFC 1795, dated Apr., 1995, (www.ietf.org)., Section
`2.
`
`(List continued on next page.)
`
`Primary Examiner—David Wiley
`(74) Attorney, Agent, or Firm—Cesari and McKenna, LLP;
`A. Sidney Johnston
`
`(57)
`
`ABSTRACT
`
`Amethod for computing an ACK timing interval for an ACK
`timer in a protocol layer LLC type 2 session first measures
`a time interval between transmission of a frame by a source
`computer joined to a to a destination computer by an
`intermediate link, and receipt of a corresponding acknowl-
`edgment frame by the source computer from the destination
`computer. The two events at the source computer, starting a
`timer upon commencement of transmission of a frame or
`sequence of frames and the later reception of an acknowl-
`edge message indicating receipt of those frames, permits
`calculation of a measured time interval. The measured time
`
`interval is used to compute the bandwidth of the interme-
`diate link. The required ACK timing interval for the ACK
`timer is then computed in response to the bandwidth, the
`number of bytes transmitted after starting the ACK timer,
`and the return time for an acknowledgment message. The
`ACK timing interval may be recomputed after every trans-
`mission of frames and receipt of a corresponding ACK
`message. The ACK timing interval is thereby dynamically
`adjusted to conditions on the intermediate link, including
`natural bandwidth for either a slow or fast link, congestion
`due to other traffic on the link, etc. The dynamic adjustment
`of the ACK timing interval prevents inadvertent timeouts of
`the ACK timer, and so prevents inadvertent breaking of the
`LLC type 2 reliable transport connection.
`
`15 Claims, 9 Drawing Sheets
`
`100
`
`102
`
`ROUTER
`
`ROUTER
`
`114
`
`E82
`116/
`
`120
`
`E81
`\112
`
`LLC TYPE 2 RELIABLE
`COMMUNICATION SESSION
`
`INTEL EX. 1257.001
`
`INTEL Ex. 1257.001
`
`

`

`US 6,401,127 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`’
`’
`’
`’
`Tanenbaurn Andrew ComputerNetworks 3rd edition Pren-
`tice Hall, 1996, pp. 28—35, 35—39.
`Tanenbaurn, Andrew 8., Computer Networks, Second Edi-
`tion, Prentice Hall, 1998, pp. 253—268.
`
`Corner, Douglas E., Computer Networks and Internets,
`Prentice Hall, 1997, pp. 239—249.
`th TCPIP
`C
`D
`l
`E. It
`t
`kl
`-
`-
`’ ”6W war ”g WI
`Dug as
`/
`’ V0
`omer’
`. 89—107.
`Th. dEd't'
`t. H ll 1995
`P
`W
`1 ton,
`ren 1ce
`a ’
`’ pp
`* cited by examiner
`
`l. I
`
`’
`
`INTEL EX. 1257.002
`
`INTEL Ex. 1257.002
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 1 0f 9
`
`US 6,401,127 B1
`
`100
`
`106
`
`102
`
`104
`
`ROUTER
`
`
`
`
`
`ROUTER
`
`110
`
`114
`
`E82
`116/
`
`120
`
`E81
`\112
`
`LLC TYPE 2 RELIABLE
`COMMUNICATION SESSION
`
`FIG. 1
`
`INTEL EX. 1257.003
`
`INTEL Ex. 1257.003
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 2 0f 9
`
`US 6,401,127 B1
`
`204
`f———TMT—\
`
`202
`f—L—fi
`
`254
`
`250
`
`APPLICATION
`
`APPLICATION
`
`252
`
`PRESENTATION
`AND
`
`
`
`SESSION
`
`TRANSPORT
`
`TCP
`
`206
`r———*-—fi
`INTERCONNECTION
`DEVICE
`
`LEVEL 3 SWITCH
`(ROUTER)
`
`BASED ON
`IP ADDRESS
`
`MAC BASED ON
`
`246
`240
`\
`244
`PACKETS
`
`(RELIABLE
`COMMUNICATION)
`
`
` 236
`
`234
`\
`230
`
`
`
`INTERNET
`
`
`PACKETS
`
`NETWORK
`
`IP
`
`(LEVEL 3)
`
`(DATAGRAMS)
`(LEVEL 3)
`
`
`
`BEST EFFORT
`
`
`COMMUNICATION
`
`
`(UNRELIABLE)
`
`
`
`
`DATA LINK
`DATA LINK
`
`
`FRAMES
`(LEVEL 2)
`(LEVEL 2)
`
`
`
`LLC LEVEL 2 SWITCH
`LLC
` MAC
`
`
`(BRIDGE)
`
`
`
`
`
`PHYSICAL
`
`219 BUS 215
`
`217
`
`PHYSICAL
`
`PHYSICAL
`(MAC)
`ADDRESS
`
`ISO, OR IEEE
`7 LEVEL
`COMMUNICATIONS
`MODEL
`
`INTERNET
`COMMUNICATIONS
`MODEL
`
`FIG. 2
`
`INTEL EX. 1257.004
`
`INTEL Ex. 1257.004
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 3 0f 9
`
`US 6,401,127 B1
`
`302
`
`304
`
`306
`
`@
`
`308
`
`320
`
`322
`
`MAC
`
`MAC
`LEADING
`
`
`
`MAC
`
`RIF
`
`802.2 LLC
`
`MAC
`TRAINING
`
`MULTICAST BIT SET
`\310
`
`
`
`IEEE 802.5: LEVEL 2 MAC FRAME FIELDS
`
`FIG. 3
`
`402
`
`404
`
`4gp
`
`406
`
`408
`
`DSAP
`
`SSAP
`
`CTRL
`
`DATA
`
`IEEE 802.2 LLC FIELDS
`
`FIG. 4
`
`INTEL EX. 1257.005
`
`INTEL Ex. 1257.005
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 4 0f 9
`
`US 6,401,127 B1
`
`
`
`INTEL EX. 1257.006
`
`INTEL Ex. 1257.006
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 5 0f 9
`
`US 6,401,127 B1
`
`BITS
`
`/602
`
`8{604
`
`fig
`
`>6608
`
`8{612
`
`IEEE 802. 2 LLC FIELDS
`
`FIG. 6
`
`700
`
`
`
`722
`
`708
`
`724
`
`720 In TYPE
`
`P/F
`
`NEXT
`
`FIG TB
`
`708
`
`INTEL EX. 1257.007
`
`INTEL Ex. 1257.007
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 6 0f 9
`
`US 6,401,127 B1
`
`@
`
`802
`
`804
`
`806
`
`808
`
`810
`
`812
`
`IEEE 802.2 LLC FIELDS USING SNAP SAP OPTION
`
`FIG. 8
`
`INTEL EX. 1257.008
`
`INTEL Ex. 1257.008
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 7 0f 9
`
`US 6,401,127 B1
`
`
`
`904
`4
`
`906
`8
`
`924
`
`908
`
`902-0
`
`
`
`299
`
`934
`16
`
`910
`
`19
`
`24
`
`31
`
`922
`
`932
`
`942
`
`952
`
`962
`
`972
`
`
`
`
`
`
`SERVICE
`
`TOTAL LENGTH
`TYPE I
`VERS HLEN I
`IDENTIFICATION-I FRAGMENT OFFSET
`
`T'ME
`TO LIVE
`
`PROTOCOL
`
`HEADER CHECKSUM
`
`SOURCEIPADDRESS
`
`DESHNAHONIPADDRESS
`
`IPOPHONSUFANY)
`
`PADDWG
`
`DATA
`
`FIG. 9
`
`926
`
`936
`
`964
`
`
`
`
`
`
`
`
`INTEL EX. 1257.009
`
`INTEL Ex. 1257.009
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 8 0f 9
`
`US 6,401,127 B1
`
`10,000——
`
`10,004
`
`SNRM
`(SABME)
`
`10,010
`1(0, P/F = "0")
`
`10,008 TRT
`
`TOUT
`
`10,022
`
`
`10,012
`
`I(LAST, P/F = "1")
`
`
`
`10,006
`UA (ACK)
`
`10,015
`
`l/RR/RNR/REJ
`
`FIG. 10
`
`10,002
`
`TIME
`
`INTEL EX. 1257.010
`
`INTEL Ex. 1257.010
`
`

`

`US. Patent
`
`Jun. 4, 2002
`
`Sheet 9 0f 9
`
`US 6,401,127 B1
`
`__——-
`11,000
`
`10,004
`
`SNRM
`(SABME)
`
`10,002
`
`10,008 TRT
`
`TOUT
`10,022
`
`10,015
`NO ACK ARRIVED
`AT SOURCE COMPUTER
`
`11 006
`
`|/RR/RNR/REJ RESPONSIVE TO
`(LAST, P/F—' "1")
`
`
`
`10,005
`10,010
`UA (ACK)
`
`Iw,WF="m)
`
`
`
`' 10012
`
`“LAST, P/F = 1')
`
`
`11,010
`
`
`S FORMAT PDU
`
`
`(RR,RELRNR)
`
`
`WITH P/F = "1"
`
`
`
`11,022
`I/RR/RNR/REJ RESPONSIVE TO
`SFORMATPDU
`P/F = "1|!
`APPEARS AS AN
`UNSOLICITED
`MESSAGE WITH
`P/F = "111
`
`11030
`DISK
`RESPONSIVE TO
`RECEIVING AN
`"UNSOLICITED"
`‘
`F = "1"
`
`
`
`TIME
`
`FIC3. 11
`
`INTEL EX. 1257.011
`
`INTEL Ex. 1257.011
`
`

`

`US 6,401,127 B1
`
`1
`ADAPTIVE TIMER FOR LLC TYPE 2
`RELIABLE TRANSPORT IN A COMPUTER
`NETWORK
`
`FIELD OF THE INVENTION
`
`This invention relates to communications over a computer
`network, and more particularly to the use of timing events to
`detect loss of a frame.
`
`BACKGROUND OF THE INVENTION
`
`When a frame is transmitted over a computer network
`there is a possibility that it will be lost. Loss of a frame can
`be due to a number of factors. The factors include: failure of
`
`an intermediate link; congestion in the network; failure of a
`bridge or router; aborted frames in the network; cyclic
`redundancy check (CRC) errors; etc. In order to compensate
`for lost frames during transmission from a source station to
`a destination station, over a computer network,
`it
`is a
`common practice to transmit an acknowledge message
`(ACK message) by the destination station upon receipt of an
`information frame, or a sequence of frames. The ACK
`message usually gives the sequence number of the last
`correctly received frame, and may be either a separate short
`frame or may be “piggybacked” on an information frame
`traveling upstream from the destination station to the source
`station.
`
`Also, an acknowledgment timer (ACK timer) is operated
`in the source station. The ACK timer is started when the
`
`frame is transmitted onto the network (usually at the begin-
`ning of the transmission). In the event that an ACK message
`is not received before the expiration of the ACK timer, then
`it is a common practice to have the source station either
`retransmit the information frame, or depending upon the
`protocol, transmit a poll frame to the destination station. The
`destination station, upon receipt of the poll frame,
`is
`required to transmit a response to the source station. The
`purpose of the poll frame and the response frame is for the
`source station to learn: whether or not the destination station
`
`is still operative on the network; if the route in a source route
`bridged (SRB) network is still operative; retrieving the
`sequence number of the last correctly received frame; etc.
`A problem with operating an ACK timer in the source
`station is that delays in the network can cause the ACK timer
`to expire before the source station receives an acknowledg-
`ment frame from the destination station.
`
`Logical Link Control Layer (LLC) reliable communica-
`tion was introduced; and sequence numbers for frames along
`with acknowledgment (ACK) messages permit establish-
`ment of reliable communication in layer 2 of the OSI
`communications reference model. LLC reliable communi-
`
`cation is referred to as “LLC type 2” reliable communica-
`tion. When introduced, LLC type 2 reliable communication
`was established between end stations on IEEE 802.5 token
`
`ring networks, and their extension with bridges to source
`route bridged (SRB) networks. A fixed time timing interval
`for ACK messages was appropriate for uncongested small
`SRB networks. Later, introduction of wide area network
`(WAN) links in SRB networks along with development of
`congestion problems at bridges in SRB networks lengthened
`the packet travel time in the networks, and lead to time-out
`problems in the ACK timer.
`In LLC type 2 reliable communication the source station
`inserts a sequence number in a field of the LLC type 2 header
`(in an exemplary version of the IEEE standard three (3) bits
`are designated for the sequence number, in another exem-
`plary version of the IEEE standard seven (7) bits are
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`designated for the sequence number). In some point-to-point
`protocols the LLC TYPE 2 function in the LLC layer can
`read the sequence numbers of received packets, and can
`request retransmission of packets which are missing. The
`LLC TYPE 2 fields of a frame are fully disclosed by Radia
`Perlman in her book Interconnections, Bridges and Routers,
`published by Addison Wesley Publishing Company, in 1992,
`all disclosures of which are incorporated herein by
`reference, particularly at pages 33—34. As explained by
`Perlman at page 34, LLC type 2 reliable communication
`makes use of four packet types: I packets; RR packets; RNR
`packets; and, RE] packets:
`“1. I (stands for “information”) is a data packet. In this
`case,
`the CTL [control] field is 2 bytes long and
`includes 7 bits of sequence number for the data packets
`being transmitted from source S to destination D, plus
`7 bits sequence number for the acknowledgment for
`packets being received from D by S.
`2. RR (“receive ready”) is an acknowledgment. It contains
`a sequence number and indicates that all packets with
`sequence numbers lower than that have been received.
`It also indicates that the receiver is prepared to receive
`more data.
`
`3. RNR (“receive not ready”) is an acknowledgment for
`previously transmitted packets (with numbers lower
`than the sequence number in the receive sequence
`number field in the RNR), just like the RR. However,
`it also indicates that the receiver is temporarily busy
`and that further packets should not be transmitted until
`the receiver indicates it can accept new packets, by
`transmitting an RR.
`4. RE] (“reject”) indicates that the receiver is requesting
`retransmission of packets starting with the number in
`the receive sequence number field.”
`An ACK timer in the source station is started each time
`
`transmission of a sequence of packets is begun by the source
`station, and the ACK timer expires after an “ACK timing
`interval”. The source station anticipates receiving a response
`frame (that is, an ACK message), for example a Receive/
`Ready (RR) frame, acknowledging that the destination sta-
`tion received the preceding sequence of frames.
`In the
`absence of receipt of an RR frame during the ACK timing
`interval,
`the ACK timer expires and the source station
`transmits a “poll” frame in order to seek a response from the
`destination station to indicate whether or not the destination
`station is still active on the network. Reliable communica-
`
`tion of LLC type 2 is described by Andrew Tanenbaum in his
`book Computer Networks, Second Edition, published in
`1988, all disclosures of which are incorporated herein by
`reference, especially at pages 253—257.
`However a problem arises when the link round trip time
`is substantially equal to, or longer than, the ACK timing
`interval of the ACK timer. The ACK timer may expire before
`the response, for example the RR frame, is received by the
`source station. Factors delaying the response frame com-
`prise:
`the response frame is still on its way from the
`destination station back to the source station;
`the frame
`transmitted by the source station has not reached the desti-
`nation station because it is stuck in a queue of an interme-
`diate router experiencing congestion; the outgoing frame is
`still stuck in a queue in the source station and has not been
`transmitted because the network connected to the source
`
`station is congested; etc.
`Historically, LLC type 2 reliable communication was
`introduced to operate over a SRB network where the delays
`are small and predictable. However, further developments
`introduced wide area network links into SRB networks
`
`INTEL EX. 1257.012
`
`INTEL Ex. 1257.012
`
`

`

`US 6,401,127 B1
`
`3
`having LLC type 2 reliable communication, and so intro-
`duced long and variable packet travel times. The long and
`variable packet travel times give rise to premature expiration
`of the ACK timer in the LLC type 2 reliable communication
`protocol.
`The premature expiration of the ACK timer causes the
`source station to transmit a poll frame requesting a response
`from the destination station. The destination station then
`
`receives the poll frame and transmits an acknowledgment
`response to the poll frame, for example another RR frame.
`Accordingly,
`the source station receives two (2) RR
`acknowledgment frames in succession from the destination
`station,
`the first from the properly received sequence of
`information frames and the second in response to the poll
`frame. Receipt of two (2) RR acknowledgment frames in
`succession by a source station is a violation of IEEE 802.2
`protocol rules. The violation of the protocol rules causes the
`source station to terminate the session. Termination of the
`session due to an inadvertent time-out of the ACK timer is
`
`a great inconvenience for users of the network. Presently, the
`ACK timing interval is manually configured in order to
`account for low bandwidth communication sessions in the
`network.
`
`The problem of termination of the session upon receipt by
`a station of two successive acknowledgment frames remains
`in the Standard ISO/IEC 8802-2:1988, ANSI/IEEE Std.
`802.2, 1998 Edition,
`(IEEE 802.2) at clause 5.4.2.3.5
`“Frame Reject (FRMR) Response”, as follows:
`“The FRMR (frame reject response) PDU (protocol data
`unit) shall be used by the LLC in the asynchronous
`balanced mode (two way communication) to report the
`observance of a condition, that is not correctable by
`re-sending the identical PDU, that resulted from the
`receipt of a PDU from the remote LLC .
`.
`. The FRMR
`response PDU may be used in the case of any or both
`of the following conditions: The receipt of an unsolic-
`ited F bit set to “1” (that is, two ACK messages in
`succession) .
`.
`. The LLC receiving the FRMR response
`PDU shall pass a DL-RESET indication primitive to
`the network layer, which is responsible itself for initi-
`ating the appropriate mode setting or resetting correc-
`tive action by instructing the LLC to initialize both
`directions of information transfer on the data link
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`connection, using the SABME (set asynchronous bal-
`anced mode extended) and DISC (disconnect) (the
`SABME and DISC commands end the session and a
`
`45
`
`new session must then be established) command PDUs,
`as applicable.”
`Also,
`the IEEE 802.2 Standard at clause 7.7 “FRMR
`Exception Conditions”, action of resetting the session upon
`receipt of a FRMR response PDU is defined as the LLC
`layer passing a message up the protocol stack to its super-
`visory mechanism in the network layer.
`The expiration of an ACK timer in the source station for
`long distance transmissions over Wide Area Networks
`(WANs) using the TCP/IP protocol has been addressed.
`Particularly, the use of a time out and retransmission timer
`using the TCP/IP protocol for WANs is described by Dou-
`glas E. Comer in his book “Internetworking with TCP/IP”,
`3rd edition, Vol. 1, published by Prentice-Hall in 1995, all
`disclosures of which are incorporated herein by reference,
`particularly at pages 208—216. The TCP/IP protocol
`is
`designed for communication over long distances of a Wide
`Area Network (WAN). There can be large variations in the
`time required for a packet to travel across a WAN, and
`Comer shows, at his page 210, sample measurements for
`Internet round trip times measured for 100 successive IP
`
`50
`
`55
`
`60
`
`65
`
`4
`datagrams traveling across the global Internet; the trip times
`appear to vary from less than two seconds to more than eight
`seconds for this particular set of 100 successive IP data-
`grams.
`layer of the
`is in the transport
`The TCP/IP protocol
`Internet model protocol, and also in the OSI communication
`reference model. The communications reference models are
`discussed by Andrew S. Tanenbaum in his book “Computer
`Networks, 3rd edition”, published by Prentice-Hall, PTR in
`1996, all disclosures of which are incorporated herein by
`reference, particularly at pages 28—54. In the Internet, or
`TCP/IP reference model, the layers of the communications
`reference model comprise:
`the physical layer at layer 1;
`above that is layer 2 including the MAC address and, for
`SRB networks, RIF information; next higher is layer 3 that
`is the Internet, or IP, layer which provides best effort packet
`(or datagram) communication; and above that the transport,
`or TCP, layer 4 which provides reliable communication.
`The problem of premature timeout in LLC type 2 reliable
`transport was addressed by development of the data link
`switching protocol, DLSw, as explained in RFC 1795
`(Internet Engineering Task Force, “IETF”, Request For
`Comments, Informational RFC, RFC 1795, dated April
`1995, www.ietf.org), which in Section 2, in relevant part
`states:
`
`“Data Link Switching was developed to provide support
`for SNA and NetBIOS in multi-protocol routers. Since
`SNA and NetBIOS are basically connection oriented
`protocols, the Data Link Control procedure that they
`use on the LAN is IEEE 802.2 Logical Link Control
`(LLC) Type 2. Data Link Switching also accommo-
`dates SNA protocols over WAN (Wide Area Network)
`links via the SDLC [Synchronous Data Link Control]
`protocol.
`IEEE 802.2 LLC Type 2 was designed with the assump-
`tion that the network transit delay would be predictable
`(i.e., a local LAN). Therefore the LLC Type 2 elements
`of procedure use a fixed timer for detecting lost frames.
`When remote bridging is used over wide area lines
`(especially at lower speeds), the network delay is larger
`and it can vary greatly based upon congestion. When
`the delay exceeds the time-out value LLC Type 2
`attempts to retransmit. If the frame is not actually lost,
`only delayed, it is possible for the LLC Type 2 proce-
`dures to become confused. And as a result, the link may
`be eventually taken down if the delay exceeds the T1
`timer times N2 retry count.”
`The solution offered by the DLSw protocol option in RFC
`1795 is to package the LLC type 2 frames into TCP/IP for
`transport across a wide area network, or across a slow link.
`RFC 1795 defines Switch to Switch Protocol (SSP) frame
`formats to accomplish encapsulating LLC type 2 frames into
`TCP/IP. Packaging the LLC type 2 frames into TCP/IP
`packets reduces the size of the network domain over which
`LLC type 2 reliable transport is implemented, and so short-
`ens the time interval which the source end station must wait
`
`before receiving an LLC type 2 acknowledgment message in
`a return frame. However, the fundamental problem of pre-
`mature timeout
`in LLC type 2 reliable transport
`is not
`addressed by the DLSw option, and in fact
`is simply
`avoided.
`
`Further, some network designs require LLC type 2 reli-
`able communication from end station to end station, without
`a DLSw link. In these designs the problem of premature
`expiration of the ACK timer remains a problem, especially
`where WAN links or congested intermediate routers or
`bridges are included within the span of the LLC type 2
`reliable communication.
`
`INTEL EX. 1257.013
`
`INTEL Ex. 1257.013
`
`

`

`US 6,401,127 B1
`
`5
`inadvertent
`There is needed a mechanism to prevent
`time-outs of the ACK timer in communications between a
`
`source station and destination station using LLC type 2
`reliable transport, especially when a slow link is employed
`for the connection, and also when the session bandwidth is
`subject to dynamic variations during day to day operations.
`SUMMARY OF THE INVENTION
`
`A method for computing an ACK timing interval for an
`ACK timer in a protocol layer LLC type 2 session first
`measures a time interval between transmission of a frame by
`a source computer joined to a destination computer by an
`intermediate link, and receipt of a corresponding acknowl-
`edgment frame by the source computer from the destination
`computer. The two events at
`the source computer:
`i.e.,
`starting a timer upon commencement of transmission of a
`frame or sequence of frames and the later reception of an
`acknowledge message indicating receipt of those frames,
`permits calculation of a measured time interval. The mea-
`sured time interval
`is used to dynamically compute the
`bandwidth of the intermediate link. The required ACK
`timing interval for the next ACK timer is then computed in
`response to the dynamically computed bandwidth and the
`number of bytes to be transmitted and subsequently
`acknowledged. The ACK timing interval may be recom-
`puted after every transmission of frames and receipt of a
`corresponding ACK message. The ACK timing interval is
`thereby dynamically adjusted to conditions on the interme-
`diate link, including natural bandwidth for either a slow or
`fast link, congestion due to other traffic on the link, etc. The
`dynamic adjustment of the ACK timing interval prevents
`inadvertent timeouts of the ACK timer, and so prevents
`inadvertent breaking of the LLC type 2 reliable transport
`connection.
`
`Other and further aspects of the present invention will
`become apparent during the course of the following descrip-
`tion and by reference to the accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Referring now to the drawings, in which like numerals
`represent like parts in the several views:
`FIG. 1 is a block diagram of a communication system
`using an LLC2 Type 2 reliable communication session.
`FIG. 2 is a block diagram of communications protocols,
`and showing interconnecting devices.
`FIG. 3 is a block diagram of a layer 2 MAC frame.
`FIG. 4 is a block diagram of IEEE 802.2 LLC fields.
`FIG. 5A—FIG. 5C are block diagrams of LLC control
`subfields for a packet having a two byte control field.
`FIG. 6 is a block diagram of an IEEE 802.2 LLC fields
`having a one byte control field.
`FIG. 7A—FIG. 7C are block diagrams of subfields of a one
`byte LLC control field.
`FIG. 8 is a block diagram of IEEE 802.2 LLC fields for
`the SNAP SAP option.
`FIG. 9 is a block diagram of a layer 3 IP header.
`FIG. 10 is a timing diagram for operation of a LLC type
`2. reliable transport in accordance with the invention.
`FIG. 11 is a timing diagram for operation of a LLC type
`2 reliable transport showing an inadvertent timeout.
`DETAILED DESCRIPTION OF AN
`ILLUSTRATIVE EMBODIMENT
`
`Turning now to FIG. 1, block diagram 100 shows a point
`to point link 102 between two routers 104 106, each of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`which serves end stations through local area networks
`(LANs). Router 104 connects to LAN 1 110 and thence to
`end station ES1 1112. Router 106 connects to LAN 2 114
`and thence to end station ES2 116. Communication between
`
`end station ES1 112 and end station ES2 114 passes through
`point to point link 102 between routers 104 106. Arrow 120
`indicates that point to point link 102 has established a layer
`2 LLC Type 2 reliable communication session. LAN 1 110
`may be an IEEE 802.5 token ring, an IEEE 802.3 Ethernet,
`etc. or a local area network of any convenient type.
`Protocols and Fields
`
`Source and destination stations joined by a link for
`example router 104 and router 106, are often referred to as
`“link stations”. In the present context, a “link” is used in
`accordance with the definition of a “data link” given in IEEE
`802.2, Clause 1.4.2.8 as: “An assembly of two or more
`terminal installations and the interconnecting communica-
`tions channel operating according to a particular method that
`permits information to be exchanged; in this context the
`term ‘terminal installation’ does not include the data source
`
`and the data sink.” Also in the present context, the “data link
`layer” (DLL) is defined at Clause 1.4.2.9 as: “The concep-
`tual layer of control or processing logic existing in the
`hierarchical structure of a station that is responsible for
`maintaining control of the data link. The data link layer
`functions provide an interface between the station higher
`layer logic and the data link. These functions include
`address/control field interpretation, channel access and com-
`mand PDU/response PDU generation, sending, and inter-
`pretation.” Further, the “higher layer” is defined at Clause
`1.4.2.14 as: “The conceptual layer of control or processing
`logic existing in the hierarchical structure of a station that is
`above the data link layer and upon which the performance of
`the data link layer functions are dependent; for example,
`device control, buffer allocation, LLC station management,
`etc.” And further, the “logic link control or “LLC” is defined
`at Clause 1.4.2.17 as: “That part of a data station that
`supports the logical link control functions of one or more
`logical
`links. The LLC generates command PDUs and
`response PDUs for sending and interprets received com-
`mand PDUs and response PDUs. Specific responsibilities
`assigned to an LLC include: (1) Initiation of control signal
`interchange; (2) Organization of data flow; (3) Interpretation
`of received command PDUs and generation of appropriate
`response PDUs, and; (4) Actions regarding error control and
`error recovery functions in the LLC sublayer.” The LLC is
`a sublayer of the DLL, as shown with reference to FIG. 2.
`A LLC Type 2 reliable communication session will now
`be further discussed with reference to FIGS. 2—9.
`
`terminology which will be used herein is as
`Further,
`follows. At the physical layer, bits are transmitted by a
`source station onto the network. A frame is forwarded in a
`
`subnet according to the layer 2 MAC address from a source
`station to a destination station, and may be forwarded by
`several bridges. Apacket is routed by a router according to
`a layer 3 address in an IP header, and may be routed from a
`subnet
`to,
`for example another subnet,
`to a wide area
`network, to a point to point link to another router, etc. This
`distinction between a frame and a packet is fully disclosed
`by Andrew Tanenbaum in his book Computer Network, 3rd
`edition, published by Prentice Hall Publishing Company in
`1996, all disclosures of which are incorporated herein by
`reference, especially at pages 28—34. Further,
`the term
`“message” will be used generally to indicate a transfer of
`information between computers, and may include a file
`transfer of many megabytes requiring many packets and
`many frames, or may refer to a single frame, for example a
`
`INTEL EX. 1257.014
`
`INTEL Ex. 1257.014
`
`

`

`US 6,401,127 B1
`
`7
`single frame carrying flow control information upstream to
`a source station.
`The distinction between a frame and a packet has the
`following addressing characteristics. A frame has the MAC
`(layer 2) destination address and the IP (layer 3) destination
`address of the same end station, the intended destination end
`station. The destination end station is either on the same
`local area network, or the same subnet formed by bridges
`between local area networks, as the source end station.
`However, in contrast, a packet has the MAC address of a
`router and the IP address of an end station on a distant subnet
`or other network, and the router routes the packet on its
`journey to the intended destination end station.
`Turning now to FIG. 2,
`the Internet communications
`model 202 is shown, along with a comparison with the ISO,
`or IEEE, seven (7) layer communications model 204, and
`with a representation of the interconnection devices 206
`used as a layer 2 switch 208 (also known as a bridge) and as
`a layer 3 switch 210 (also known as a router). At the physical
`layer, box 215 of the Internet communications model, bits
`are exchanged by a source station (not shown) and a
`destination station (not shown). Arrow 217 shows the cor-
`respondence between the physical layers of the two models,
`box 215 and box 219, and also shows that the physical layers
`exchange bits over the connection medium (for example,
`electrical, fiber optics, optical, etc.).
`The data link layer (DLL layer) of the Internet model of
`communications is represented by block 220. The corre-
`sponding DLL layer of the ISO/IEEE model is box 222.
`Arrow 224 indicates that frames are exchanged by two
`stations at
`layer 2 of both the Internet communications
`model and the ISO/IEEE model. The data link layer has a
`lower MAC sublayer (medium access control) and an upper
`LLC sublayer (logical link control). The LLC layer is more
`fully disclosed in IEEE standard 802.2, all disclosures of
`which are incorporated herein by reference. Fields which are
`recognized and acted upon by a receiving station, as the
`frame is received, are discussed hereinbelow. The layer 2
`MAC and layer 2 LLC sublayers respond to corresponding
`fields in frames, where the fields are designated MAC and
`LLC fields, respectively. Three (3) types of LLC frames are
`defined by the IEEE 802.2 standard. Type 1 is best effort, or
`unreliable, operation. Type 2 is acknowledged reliable
`operation, where ACK messages and packet sequence num-
`bers are used to cause re-transmission of lost frames. Type
`3 is an acknowledged connectionless operation.
`Layer 3 of the Internet communications model is repre-
`sented by block 230, the IP layer of the Internet protocol .
`The corresponding layer of the ISO/IEEE model, the “net-
`wor ” layer, is shown by block 234. Layer 3 devices respond
`to layer 3 fields in a frame.
`In the event
`that
`the IP
`destination address in the frame (a layer 3 field) is for an end
`station and the MAC destination address (a layer 2 field) is
`for an intermediate router,
`the frame is referred to as a
`“packet”. Arrow 236 indicates that packets are exchanged
`between layer 3 entities of the communications model, that
`is between layer 3 in the source station and the destination
`station. Alternatively, the term “datagram” is used to refer to
`packets exchanged between layer 3 entities in source and
`destination stations, as shown at arrow 236, however the
`term “packet” will be used herein.
`In communication
`between stations, either on a single local area network, or
`separated by half the circumference of the Earth with many
`hops between source and destination stations, packets are
`exchanged at layer 3 as a best effort communication, and so
`provide unreliable communication.
`Block 240 represents the TCP (transmission control
`protocol) layer