a2, United States Patent
`US 6,401,127 B1
`(10) Patent No.:
`Jun.4, 2002
`(45) Date of Patent:
`Lei et al.
`
`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 ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/304,395
`
`(22)
`
`Filed:
`
`May4, 1999
`
`Int. C1.) occcecccccccsecccscscssssesesesscseseseseess G06F 13/00
`(51)
`(52) US. C1. cece cneeeneeecscteneseneenees 709/235; 709/232
`(58) Field of Search oo... eee 709/200-253
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`7/1994 Francis et al. oe 370/54
`5,331,637 A
`10/1994 Tsuchiya ........
`... 370/60
`5,353,283 A
`8/1995 Perkins et al.
`............. 370/94.1
`5,442,633 A
`12/1996 Tsuchiya ........00... 395/200.15
`5,583,996 A
`2/1997 Chang et al. oo... 370/404
`5,600,644 A
`
`5/1997 Callon .......e ce eeeeeeeeeeeeee 370/397
`5,633,866 A
`
`10/1998 Burwell et al. 0... 370/397
`5,818,842 A
`10/1998 Civanlar et al.
`....... 395/200.58
`5,828,844 A
`4/1999 Virgile .....c eee 370/381
`5,898,686 A
`6/1999 Alexander, Jr. et al.
`..... 370/395
`5,909,441 A
`6/1999 Shankaret al.
`........ 395/200.57
`5,909,550 A
`6/2000 Wesley «0.0.0... 709/235
`6,076,114 A *
`OTHER PUBLICATIONS
`
`Pearlman, Radia, Jnterconnections, 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/IP. 3"¢ Edi-
`tion, vol. 1, Prentice Hall, 1995, pp. 208-216.
`Tanenbaum, Andrew S., “Computer Networks, 3" 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 timinginterval 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
`ACKtiming 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 othertraffic on the link, etc. The dynamic adjustment
`of the ACK timinginterval prevents inadvertent timeouts of
`the ACKtimer, and so prevents inadvertent breaking of the
`LLC type 2 reliable transport connection.
`
`15 Claims, 9 Drawing Sheets
`
`100
`
`
`
`120
`
`ES‘
`\442
`
`LLC TYPE 2 RELIABLE
`COMMUNICATION SESSION
`
`INTEL Ex. 1257.001
`
`INTEL Ex. 1257.001
`
`

`

`US 6,401,127 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`Tanenbaum, Andrew, Computer Networks, 3”edition, Pren-
`tice Hall, 1996, pp. 28-35, 35-39.
`Tanenbaum, Andrew S., Computer Networks, Second Edi-
`tion, Prentice Hall, 1998, pp. 253-268.
`
`Comer, Douglas E., Computer Networks and Internets,
`Prentice Hall, 1997, pp. 239-249.
`Comer, Douglas E., Internetworking with TCPHP, vol. 1,
`Third Edition, Prentice Hall, 1995, pp. 89-107.
`
`* cited by examiner
`
`INTEL Ex. 1257.002
`
`INTEL Ex. 1257.002
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 1 of 9
`
`US 6,401,127 B1
`
`106
`=102
` ROUTER
`
`104 ROUTER
`
`110
`
`114
`
`ES2
`1167
`
`120
`
`ES1
`\442
`
`LLC TYPE 2 RELIABLE
`COMMUNICATION SESSION
`
`FIG. 1
`
`INTEL Ex. 1257.003
`
`INTEL Ex. 1257.003
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 2 of 9
`
`US 6,401,127 B1
`
`202
`204
`a o—-_
`254
`250
`
`APPLICATION
`
`APPLICATION
`
`252
`
`
`
`PRESENTATION
`AND
`SESSION
`
`6
`240
`944
`PACKETS
`TRANSPORT
`
`(RELIABLE
`
`
`
`TCP
`
`206
`—_—_
`INTERCONNECTION
`DEVICE
`
`COMMUNICATION)
`6
`LEVEL 3 SWITCH
`
`
`234
`230
`
`
`(ROUTER)
`INTERNET
`
`PACKETS
`
`
`NETWORK
`
`IP
`(LEVEL3) BASED ON
`(LEVEL3)
`
`
`
`(DATAGRAMS)
`BEST EFFORT
`
`
`COMMUNICATION
`(UNRELIABLE)
`
`
`
`
`DATA LINK
`DATA LINK
`
`
`(LEVEL 2)
`FRAMES
`(LEVEL 2)
`
`
`
`
`
`
`MAC
`222
`220
`MAC
`954
`
`
`IP ADDRESS
`
`LEVEL 2 SWITCH
`(BRIDGE)
`
`ag
`
`tp
`
`PHYSICAL
`
`PHYSICAL
`
`BASED ON
`PHYSICAL
`(MAC)
`ADDRESS
`
`ISO, OR IEEE
`7 LEVEL
`COMMUNICATIONS
`MODEL
`
`INTERNET
`COMMUNICATIONS
`MODEL
`
`FIG. 2
`
`INTEL Ex. 1257.004
`
`INTEL Ex. 1257.004
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 3 of 9
`
`US 6,401,127 B1
`
`300
`
`302
`
`304
`
`306
`
`308
`
`320
`
`322
`
`MAC
`LEADING
`
`MAC
`
`MAC
`
`RIF
`
`802.2 LLC
`
`MAC
`TRAINING
`
`
`
`MULTICASTBIT SET
`‘310
`
`IEEE 802.5: LEVEL 2 MAC FRAME FIELDS
`
`FIG. 3
`
`402
`
`404
`
`400
`
`406
`
`408
`
`DSAP
`
`SSAP
`
`CTRL
`
`DATA
`
`IEEE 802.2 LLC FIELDS
`
`FIG. 4
`
`INTEL Ex. 1257.005
`
`INTEL Ex. 1257.005
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 4 of 9
`
`US 6,401,127 B1
`
`
`
`INTEL Ex. 1257.006
`
`INTEL Ex. 1257.006
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 5 of 9
`
`US 6,401,127 B1
`
`ans (52
`
`co
`
`600
`
`me
`
`(or
`
`IEEE 802.2 LLC FIELDS
`
`FIG. 6
`
`700
`
`BITS
`
`9
`
`706
`702,
`omfoTse [ele FIG. 7A
`
`708710 oo coc
`
`6
`
`7
`
`8
`
`
`
`720 Ptfo TYPE|PIF NEXT FIG. 7B
`
`
`
`722
`
`~—_-708
`
`724
`
`708
`
`730 TYPE|PIF MODIFIER JFIG. 7C
`
`
`
`
`
`
`
`INTEL Ex. 1257.007
`
`INTEL Ex. 1257.007
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 6 of 9
`
`US 6,401,127 B1
`
`800
`
`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
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 7 of 9
`
`US 6,401,127 B1
`
`200
`
`906
`8
`
`924
`
`908
`
`934
`16
`
`19
`
`24
`
`910
`
`
`31
`
`904
`
`
`902~0
`
`
`reno|HE][omen
`
`
`DENTICATION FLAGS|
`
`
`
`
`
`
`
`TO LIVE
`
`922
`
`932
`
`942
`
`952
`
`962
`
`972
`
`IP OPTIONS(IF ANY)
`
`PADDING
`
`DATA
`
`
`
`FIG. 9
`
`INTEL Ex. 1257.009
`
`INTEL Ex. 1257.009
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 8 of 9
`
`US 6,401,127 B1
`
`10,000
`
`10,004
`SNRM
`(SABME)
`
`10,008-|TRT 10,006
`Bot
`UA (ACK)
`(0, PIF = "0")
`
`TOUT
`10,022
`
`
`”
`40.012
`
`\(LAST, P/F = "1")
`
`
`10,015
`VRR/RNRIREJ
`
`FIG. 10
`
`10,002
`
`TIME
`
`INTEL Ex. 1257.010
`
`INTEL Ex. 1257.010
`
`

`

`U.S. Patent
`
`Jun.4, 2002
`
`Sheet 9 of 9
`
`US 6,401,127 B1
`
`11,000
`
`10,002
`
`TOUT
`10,022
`
`10,004
`
`SNRM
`(SABME)
`
`
`10,008YTRT 10,006
`10,010
`UA (ACK)
`
`
`
`\(0, PIF = "0")
`
`
`*
`40,012
`(LAST, P/F = "1")
`
`
`11,010
`
`
`S FORMAT PDU
`(RR, REJ, RNR)
`WITH P/F = "1"
`
`
`
`
`
`11,030
`DISK
`NSIVE
`REECEWING AN
`"UNSOLICITED,
`
`10,015
`NO ACK ARRIVED
`AT SOURCE COMPUTER
`
`11,006
`I/RR/RNR/REJ RESPONSIVE TO
`(LA T,P/IF =—_ "{")
`11,022
`/RR/RNR/REJ RESPONSIVE TO
`§ FORMAT PDU
`=
`APPEARSAS AN
`UNSOLICITED
`MESSAGEWITH
`
`PIF = "1"
`
`TIME
`
`FIG. 11
`
`INTEL Ex. 1257.011
`
`INTEL Ex. 1257.011
`
`

`

`US 6,401,127 B1
`
`1
`ADAPTIVE TIMER FOR LLC TYPE2
`RELIABLE TRANSPORT IN A COMPUTER
`NETWORK
`
`FIELD OF THE INVENTION
`
`This invention relates to communications over a computer
`network, and moreparticularly 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 numberof 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 sourcestation 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 beeither 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 (ACKtimer) 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 commonpractice 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: whetheror not the destination station
`
`2
`designated for the sequence number). In somepoint-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 TYPE2 fields of a frame are fully disclosed by Radia
`Perlman in her book Jnterconnections, 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
`makesuse of four packet types: I packets; RR packets; RNR
`packets; and, REJ 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 numberfor 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 lowerthan that have been received.
`It also indicates that the receiver is prepared to receive
`more data.
`
`3. RNR (“receive not ready”) is an acknowledgmentfor
`previously transmitted packets (with numbers lower
`than the sequence number in the receive sequence
`numberfield 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. REJ (“reject”) indicates that the receiver is requesting
`retransmission of packets starting with the number in
`the receive sequence numberfield.”
`An ACKtimer in the source station is started each time
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`is still operative on the network;if the route in a source route
`bridged (SRB) network is still operative; retrieving the
`sequence numberof 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.
`
`40
`
`45
`
`Logical Link Control Layer (LLC) reliable communica-
`tion wasintroduced; and sequence numbersfor 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
`wasestablished between end stations on IEEE 802.5 token
`
`50
`
`55
`
`60
`
`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 Tanenbaumin 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 roundtrip time
`is substantially equal to, or longer than, the ACK timing
`interval of the ACK timer. The ACKtimer may expire before
`the response, for example the RR frame, is received by the
`ring networks, and their extension with bridges to source
`source station. Factors delaying the response frame com-
`route bridged (SRB) networks. A fixed time timing interval
`prise:
`the response frame is still on its way from the
`for ACK messages was appropriate for uncongested small
`destination station back to the source station;
`the frame
`SRB networks. Later, introduction of wide area network
`transmitted by the source station has not reached the desti-
`(WAN)links in SRB networks along with development of
`nation station because it is stuck in a queue of an interme-
`congestion problemsat bridges in SRB networks lengthened
`diate router experiencing congestion; the outgoing frameis
`the packet travel time in the networks, and lead to time-out
`still stuck in a queuein the source station and has not been
`transmitted because the network connected to the source
`problems in the ACK timer.
`In LLC type 2 reliable communication the source station
`station is congested; etc.
`
`inserts a sequence numberinafield of the LLC type 2 header Historically, LLC type 2 reliable communication was
`65
`(in an exemplary version of the IEEE standard three (3) bits
`introduced to operate over a SRB network where the delays
`are designated for the sequence number, in another exem-
`are small and predictable. However, further developments
`introduced wide area network links into SRB networks
`plary version of the TEEE standard seven (7) bits are
`
`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 packettravel times giverise to premature expiration
`of the ACKtimerin 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 timeris
`
`a great inconveniencefor 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 ISOMEC 8802-2:1988, ANSI/AIEEE 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 usedin 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
`PDUshall pass a DL-RESETindication 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
`connection, using the SABME(set asynchronousbal-
`anced mode extended) and DISC (disconnect) (the
`SABMEand DISC commandsend the session and a
`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 ACKtimerin 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 WANsis 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 variationsin 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
`
`4
`datagramstraveling across the global Internet; the trip trmes
`appearto 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 TCPAP 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
`TCPAP 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 NetBIOSare 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 networktransit 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 asa result, the link may
`be eventually taken downif 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 framesinto
`TCPAP. 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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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.
`SUMMARYOF THE INVENTION
`
`A method for computing an ACK timing interval for an
`ACK timer in a protocol layer LLC type 2 session first
`measuresa 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-
`edgmentframe by the source computer from the destination
`computer. The two events at
`the source computer: Le.,
`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 othertraffic 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
`becomeapparent 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 JEEE 802.2 LLCfields
`having a one byte control field.
`FIG. 7A-FIG. 7C are block diagramsof 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 showsa 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 thenceto 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
`accordancewith 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/controlfield 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 thatis
`abovethe data link layer and upon whichthe performance of
`the data link layer functions are dependent; for example,
`device control, buffer allocation, LLC station management,
`etc.” Andfurther,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 ofdata flow;(3) Interpretation
`of received command PDUsand 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.
`ALLC 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. A packet 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 mayrefer to a single frame, for example a
`
`INTEL Ex. 1257.014
`
`INTEL Ex. 1257.014
`
`

`

`US 6,401,127 B1
`
`10
`
`15
`
`20
`
`25
`
`30
`
`8
`7
`corresponding layer of the ISO/JIEEE modelis the “trans-
`single frame carrying flow control information upstream to
`a source station.
`port” layer, represented by block 244. Arrow 246 indicates
`that reliable packet communication is established by the
`The distinction between a frame and a packet has the
`TCPprotocol. ACK messagesare usedto tell the IP layer to
`following addressing characteristics. A frame has the MAC
`(layer 2) destination address and the IP (layer 3) destination
`re-transmit lost packets.
`address of the sameendstation, the intended destination end
`In the Internet communication model 202, the reliably
`station. The destination end station is either on the same
`received packets are passed up to the application layer as
`represented by box 250. In the ISO/IEEE model 204, the
`local area network, or the same subnet formed by bridges
`between local area networks, as the source end station.
`reliably received packets from the transport layer at block
`244 are passed through two additional layers, the session
`However, in contrast, a packet has the MAC address of a
`router and the IP address of an endstation on a distant subnet
`layer and the presentation layer, and then finally to the
`application layer 254. Application layer 254 of the ISO/
`or other network, and the router routes the packet on its
`IEEE modelcorrespondsto the application layer 250 of the
`journey to the intended destination end station.
`Internet model. For example,
`the application layer may
`Turning now to FIG. 2,
`the Internet communications
`represent an e-mail computer program, or may represent a
`model 202 is shown, along with a comparison with the ISO,
`or IEEE, seven (7) layer communications model 204, and
`file transfer computer program, or may represent transfer by
`
`with a representation of the interconnection devices 206 a browser computer program of a web page fromaserverto
`a client, etc.
`used as a layer 2 switch 208 (also knownas a bridge) and as
`a layer 3 switch 210 (also knownasa router). At the physical
`The various higher layers of the Open System Intercon-
`nect (OSI) reference model are described by Andrew S.
`layer, box 215 of the Internet communications model, bits
`are exchanged by a source station (not shown) and a
`Tanenbaum in above-mentioned book, “Computer
`destination station (not shown). Arrow 217 shows the cor-
`Networks, 3rd edition”, particularly at pages 28-35. The
`Internet reference model, or the TCP/IP reference model, is
`respondence between the physical layers of the two models,
`box 215 and box 219, and also showsthat the physical layers
`also discussed by Tanenbaum at pages 35-39.
`exchange bits over the connection medium (for example,
`Turning nowto FIG. 3, layer 2 fields for a token ring local
`electrical, fiber optics, optical, etc.).
`area network as defined by IEEE standard 802.2 are shown.
`Fields of the frame whichare transmitted first and arrive first
`The data link layer (DLL layer) of the Internet model of
`at the destination station are shown in block 302 as “MAC
`communications is represented by block 220. The corre-
`sponding DLL layer of the ISOMEEE model is box 222.
`leading fields”. The layer 2 or MAC destination address is
`Arrow 224 indicates that frames are exchanged by two
`given in field 304. The layer 2 or MACsource station
`stations at
`layer 2 of both the Internet communications
`addressis given in field 306. The receiving station knowsto
`model and the ISOMEEE model. The data link layer has a
`look for the Route Information Field, RIF field, 308 by
`lower MACsublayer (medium access control) and an upper
`determining that the “multicast bit” in the MAC source
`LLC sublayer (logicallink control). The LLC layer is more
`address field, MAC SAfield 306, is “set”. Alternatively, in
`fully disclosed in IEEE standard 802.2, all disclosures of
`the event that the frame 300 is a transparently routed frame,
`the multicast bit in the MAC SAfield 306 is “clear”.
`which are incorporated herein by reference. Fields which are
`recognized and acted upon byareceiving station, as the Fields to which the LLC sublayer of the DLL layer 220
`
`frame is re