(12) United States Patent
`Habusha et al.
`
`I 1111111111111111 11111 111111111111111 lllll lllll lllll 111111111111111 11111111
`US006205498Bl
`US 6,205,498 Bl
`Mar.20,2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54)
`
`METHOD AND SYSTEM FOR MESSAGE
`TRANSFER SESSION MANAGEMENT
`
`(75)
`
`Inventors: Uri Habusha, Mitzpe Hoshaya; Yoe)
`Amon, Haifa, both of (IL)
`
`(73) Assignee: Microsoft Corporation, Redmond, WA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`(21) Appl. No.: 09/053,415
`Apr. 1, 1998
`(22) Filed:
`
`Int. CI.7 ...................................................... G06F 13/14
`(51)
`(52) U.S. Cl. ............................ 710/29; 379/202; 379/229;
`340/825.5; 709/221; 709/228; 714/749;
`714/708
`(58) Field of Search ........................ 710/29, 15; 709/221,
`709/228; 379/202, 229; 340/825.5; 714/749,
`708
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`2/1985 Fraser ..................................... 370/60
`4,499,576
`4,584,679 * 4/1986 Livingston et al.
`................. 714/749
`4,623,886 * 11/1986 Livingston ........................ 340/825.5
`4,656,474
`4/1987 Mollier et al. ......................... 380/23
`4,736,369 * 4/1988 Barzilai et al. ...................... 370/231
`4,769,815 * 9/1988 Hinch et al. ......................... 370/236
`5,063,562 * 11/1991 Barzilai et al. ...................... 370/231
`5,163,131
`11/1992 Row et al. ........................... 395/200
`5,193,090
`3/1993 Filipiak et al.
`........................ 370/94
`5,247,676
`9/1993 Ozur et al. ........................... 709/328
`5,285,445
`2/1994 Lehnert et al.
`........................ 370/60
`5,287,103
`2/1994 Kasprzyk et al.
`.............. 340/825.52
`5,367,523 * 11/1994 Chang et al.
`........................ 370/235
`5,442,637 * 8/1995 Nguyen ................................ 714/708
`5,465,328
`11/1995 Dievendorff et al.
`................. 714/15
`5,526,358
`6/1996 Gregerson et al. ................. 370/94.3
`5,526,489
`6/1996 Nilakantan et al. ............ 395/200.02
`5,528,605 * 6/1996 Ywoskus et al. .................... 714/749
`5,546,391
`8/1996 Hochschild et al. ................... 370/60
`5,555,415
`9/1996 Allen .................................... 395/700
`5,557,748
`9/1996 Norris ............................... 395/200.1
`
`5,572,522
`5,572,582
`5,627,766
`5,758,184
`5,761,507
`
`11/1996
`* 11/1996
`5/1997
`5/1998
`6/1998
`
`Calamvokis et al. . ... ... ... ... ..... 370/60
`Riddle .................................. 379/202
`Beaven ............................ 364/551.01
`Lucovsky et al. ....................... 710/6
`Govett .................................. 709/101
`
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`
`Newton, Harry, Newton's Telecomm Dictionary, 8th Ed,
`Flatiron Publishing, 1994, pp. 333 and 870.
`Microsoft Message Queuing Services: A Guide to Reviewing
`Microsoft Message Queuing Service Release 1.0, Microsoft
`Corporation, Redmond, Washington, 1997.
`Comer, Douglas E., Internetworking With TCP/IP vol. 1:
`Principles, Protocols and Architecture, Chapter 6: Deter(cid:173)
`mining an Internet Address at Startup (RARP) and Chapter
`18: Client-Server Model of Interaction, pp. 83-88,
`293-309, Prentice-Hall, Englewood Cliffs, New Jersey,
`1991.
`
`(List continued on next page.)
`
`Primary Examiner-Thomas C. Lee
`Assistant Examiner---Abdelmoniem Elamin
`(74) Attorney, Agent, or Firm----Leydig, Voit & Mayer, Ltd.
`
`(57)
`
`ABSTRACT
`
`A method and system for managing the transfer of message
`packets between first and second nodes in a message queu(cid:173)
`ing system utilizes a session acknowledgment protocol to
`coordinate the two-way flow of packet transmission. In a
`session initiation phase, each node specifies a session
`acknowledgment timeout period and a transmission window
`size for transmission of message packets thereto. During the
`session, the first node transmits multiple message packets up
`to the window size set by the second node and stops to wait
`for a session acknowledgment from the second computer.
`The session acknowledgment may piggyback on a message
`packet sent to the first node. A window-size field in the
`session acknowledgment allows the receiving node to
`dynamically adjust the incoming data flow.
`
`17 Claims, 5 Drawing Sheets
`
`Page 1 of 14
`
`

`

`US 6,205,498 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`5,764,625 *
`5,777,987 *
`5,778,384 *
`5,793,861
`5,812,819
`5,815,667 *
`5,819,042
`5,828,653
`5,835,727
`5,838,907
`5,845,081
`5,854,901
`5,864,669
`5,872,968
`5,875,301 *
`5,875,306
`5,878,056
`5,881,051 *
`5,901,138 *
`5,920,697
`5,922,049
`5,930,479
`5,956,340
`5,959,995 *
`
`Bournas ............................... 370/231
`Adams et al.
`....................... 370/336
`Provino et al. ... ... ... .... ... ... ... 707 /200
`Haigh ................................... 379/266
`Rodwin et al. ...................... 395/500
`Chien et al.
`......................... 709/232
`Hansen ................................. 709/223
`Goss ..................................... 370/230
`Wong et al.
`......................... 709/238
`Hansen ................................. 709/220
`Rangarajan et al. ................. 709/224
`Cole et al. ........................... 709/245
`Osterman et al.
`................... 395/600
`Knox et al. .............................. 713/2
`Duckwall et al.
`................... 395/828
`Bereiter . ... ... .... ... ... ... ... ... .... .. 709 /220
`... ... ... ... .... ... ... ... .. 371/32
`Black et al.
`Arrowood et al.
`.................. 370/248
`Bader et al.
`......................... 370/229
`Masters et al. ...................... 709/221
`Radia et al.
`......................... 709/220
`Hall ...................................... 709/238
`Afek et al. ........................... 370/412
`Wicki et al. ......................... 370/400
`
`6/1998
`7/1998
`7/1998
`8/1998
`9/1998
`9/1998
`10/1998
`10/1998
`11/1998
`11/1998
`12/1998
`12/1998
`1/1999
`2/1999
`2/1999
`2/1999
`3/1999
`3/1999
`5/1999
`7/1999
`7/1999
`7/1999
`9/1999
`9/1999
`
`OIBER PUBLICATIONS
`
`Benaloh, Josh et al, The Private Communication Technology
`(PCT) Protocol, Internet Draft, available from http://premi(cid:173)
`um.microsoft.com/msdn/library/bkgrnd/html/pct/hml., Oct.,
`1995.
`Marshall, Martin, "Microsoft Updates Falcon Beta", Inter(cid:173)
`netweek, Issue 653, Mar. 10, 1997.
`Bowen, Ted Smalley, "Asynchronous Messaging Pushes to
`the Fore", Infoworld, Feb. 23, 1998. Available from http://
`www.infoworld.com/cgi-bin/displayTC.pl?/
`980223sbl-async.htm.
`Biggs, Maggie, "Applications Released from Platform Con(cid:173)
`fines: Message Queuing Exchanges Data Between Apps
`Regardless of Platform", Infoworld, Feb. 23, 1998. Avail(cid:173)
`able
`from
`http://inforworld.com/cgi-bin/displayTC.pl? /
`980223analysis.htm.
`
`Using MSMQ as an RPC Transport, Microsoft Corporation,
`1997.
`Tarjan, Robert Endre, Data Structures and Network Algo(cid:173)
`rithms, Chapter 3: Heaps, pp. 33-43, Society for Industrial
`and Applied Mathematics, Philadelphia, Pennsylvania,
`1993.
`Microsoft Message Queue Server 1.0 Release Notes,
`Microsoft Corporation, Redmond Washington, 1997.
`Microsoft Message Queue Server: A Guide to Reviewing and
`Evaluation Microsoft Message Queue Server Beta 2
`Release, Microsoft Corporation, Redmond, Washington,
`1997.
`
`Richter, Jeffrey, Advanced Windows: The Professional
`Developers Guide to the Win32 API for Windows NT 4.0 and
`Windows 95, Chapter 11: Window Messages and Asynchro(cid:173)
`nous Input, pp. 461-528, Microsoft Press, Redmond, Wash(cid:173)
`ington, 1997.
`
`Sinha, Alok K., Network Programming in Windows NT,
`Chapter 5: Windows Sockets in Windows NT, pp. 199-299,
`Addison-Wesley Publishing Company, Reading, Massachu(cid:173)
`setts, 1996.
`
`Gilman, Len and Schreiber, Richard, Distributed Computing
`with IBM MQSeries, John Wiley & Sons, New York, New
`York, 1997.
`
`Blakeley,Burnie; Harris, Harry, and Lewis, Rhys,Messaging
`& Queuing Using the MQI, McGraw-Hill Inc., New York,
`New York, 1995.
`
`Blakeley et al., Messaging and Queuing Using the MQI,
`McGraw Hill, Inc.; New York, NY, 1995.
`Douglas E. Comer, Interneting with TCP/IP, vol. 1: Prin(cid:173)
`ciples, Protocols and Architecture, Second Edition, Chapter
`19, 1991.
`
`Andrew S. Tanenbaum, Computer Networks, Third Edition,
`Prentice Hall, New Jersey; pp. 577-622, 1996.
`
`* cited by examiner
`
`Page 2 of 14
`
`

`

`N = (It
`
`_.,
`0'I
`rJ'J.
`e
`
`o=
`Q0
`\0
`,l;;i,.
`_.,
`
`i,-
`
`•
`r:JJ.
`d •
`
`30
`
`28
`
`27
`
`DRIVE
`DISK
`HARD
`
`51
`
`52
`
`INTERFACE
`SERIAL PORT 1-----------m~
`
`INTERFACE INTERFACE INTERFACE
`DISK DRIVE
`
`DRIVE
`
`DRIVE
`
`OPTICAL
`
`HARD DISK MAG DISK
`
`46
`
`34
`
`33
`
`32
`
`23
`
`INTERFACE r-4~----,
`NETWORK
`
`ADAPTER
`
`VIDEO
`
`UNIT
`
`PROCESSING
`
`PERSONAL COMPUTER ~----------j-1--,D
`
`47
`
`53
`
`48
`
`21
`
`---
`
`-·-----------------------■-----
`
`36
`
`PROGRAMS
`APPLICATION
`
`50
`49
`
`COMPUTER
`
`REMOTE
`
`42
`
`------
`
`------
`
`38
`
`37
`
`36
`
`35
`
`DATA
`
`PROGRAMS MODULES
`
`SYSTEM
`
`OPERATING APPLICATION PROGRAM PROGRAM
`
`OTHER
`
`FIG. 1
`
`DATA
`
`PROGRAM
`
`MODULES
`PROGRAM
`
`OTHER
`
`PROGRAM
`
`APPLICATION
`
`SYSTEM
`
`OPERATING
`
`BIOS
`
`! (ROM)
`f~YSTEM MEMORY
`
`I
`
`38
`
`37
`
`36
`
`35
`
`22
`
`Page 3 of 14
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar.20,2001
`Mar.20, 2001
`
`Sheet 2 of 5
`Sheet 2 of 5
`
`US 6,205,498 Bl
`US 6,205,498 B1
`
`,q-
`c.o
`
`N
`z
`0
`I-
`<(
`()
`
`/
`
`I
`
`I
`I
`
`N
`0)
`
`,q-
`co
`
`0
`co
`
`en
`0
`a
`:'2
`
`0
`0)
`
`e::::
`i-..: w
`w
`> ~ ::J
`en w
`e::::
`w
`e:::: ::J
`en wo
`a..
`0
`:'2
`
`
`
`AnNsNoanand
`
`0::
`w
`i-..'.w
`en ::J
`>
`0:: enw
`w
`e:::: ::J
`en wo
`a..
`0
`:'2
`
`YSaANASOW
`
`&NOILLWOMddV¥bNOILVOMddV
`‘LSISYSd“LSISdsdSeW
`
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`\
`\
`\
`\
`\
`\ N
`\ co
`\
`\
`'
`'
`'
`'
`'
`o,
`r--
`..... --
`
`e::::
`w
`LADYVL
`C)
`I- w
`<( w ::J
`z
`(!) w
`<(
`0:: ::J
`:'2 ~o
`---
`
`ANAND
`
`.....
`
`.....
`
`a..
`<(
`
`-
`
`,,,,.
`
`,,,,.
`
`/
`
`/
`
`/
`
`co
`co
`
`c.o
`' 'r--
`'
`'
`'
`
`\
`
`\
`
`c.o
`co
`
`N
`w
`0
`0
`z
`
`......
`w
`0
`0
`z
`
`c.o
`co
`
`,q-
`r--
`
`N
`\
`r--
`\
`\
`I
`\
`I
`L,,,
`\
`\
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`4éSls
`
`N
`
`C)
`LL
`
`Page 4 of 14
`
`I
`
`I
`
`I
`
`I
`
`/
`
`/
`
`/
`
`/
`
`/
`
`-.,,,
`
`co
`c.o
`
`e::::
`w
`>
`e::::
`w
`en
`0
`:'2
`
`N
`c.o
`
`z
`0
`I-
`<(
`()
`
`__idv_|
`
`e::::
`w
`a.. 0 C)
`:'2 ~
`<(
`<(
`:'2
`
`Page 4 of 14
`
`

`

`i,-
`~
`'° ~
`~
`(It
`Q
`N
`O'I
`rJ'J.
`e
`
`•
`r:JJ.
`d •
`
`160
`
`SESSION ACK.
`PACKETS WITH
`
`MESSAGE
`
`OR
`
`FIG. 3
`
`PACKET
`
`ACK.
`
`SESSION
`
`142
`
`PACKETS
`MESSAGE
`
`NODE
`
`SECOND
`
`PACKET
`
`PARAMETER
`CONNECTION
`
`PACKET
`
`PARAMETER
`CONNECTION
`
`PACKET
`
`RESPONSE
`
`PACKET
`
`CONNECTION
`
`ESTABLISH
`
`100
`
`NODE
`FIRST
`
`82
`
`Page 5 of 14
`
`

`

`U.S. Patent
`
`Mar.20,2001
`
`Sheet 4 of 5
`
`US 6,205,498 Bl
`
`HEADER
`102
`
`VERSION
`FLAGS
`I 1 IO IO I
`I 1 I O I 1 I
`TimeToReachQueue
`
`100
`~
`~
`104
`BODY
`
`FIG.4
`
`ClientlD
`ServerlD
`TimeStamp
`Flags
`Data
`
`106
`
`108
`
`112
`114
`116
`118
`120
`
`FIG. 5
`
`HEADER
`ACK. TIMEOUT
`PERSISTENT ACK. TIMEOUT
`WINDOW SIZE
`
`FIG. 6
`
`HEADER
`ACK. SEQ. NUMBER
`
`142
`~ Io Io I 1 I
`
`PERSISTENT MESSAGE
`STORAGE NUMBER
`STORAGE FLAGS
`I 1 Io I 1 I
`......
`SYNC. SESSION ACK.
`SYNC. PERSIST. SESSION ACK.
`WINDOW SIZE
`
`160
`
`HEADER
`
`FIG. 7 ~ MESSAGE DATA
`
`SESSION
`ACKNOWLEDGMENT
`
`128
`.-..-'
`
`140
`
`1 32
`1 34
`__..,
`- 136
`.)
`146 -
`
`-1
`44
`-
`
`8
`,........-14
`
`v---1
`50
`152
`154
`
`v -
`
`1 68
`_../
`
`----...
`
`1 62
`
`Page 6 of 14
`
`

`

`U.S. Patent
`
`Mar.20,2001
`
`Sheet 5 of 5
`
`US 6,205,498 Bl
`
`194
`
`192
`
`FIG. 8
`
`ADMIN.
`APPLICATION
`
`MQSERVER
`
`ECHO
`RESPOSE
`QUEUE
`
`PING
`ORIGINATOR
`
`180
`
`182
`
`\
`\
`\
`\
`
`\
`
`ECHO
`REQUEST
`
`' ' '
`
`MQSERVER
`
`ADMIN
`REQUEST
`QUEUE
`
`' ' ' ........
`
`202
`
`-------
`
`ECHO
`RESPONSE
`
`200
`
`FIG. 9
`
`204
`
`CD D
`YARNON4
`0Q
`RAPHIR8
`CDQ
`CDQ
`CDQ
`
`CLIOO
`
`BART3
`
`URl2
`
`Page 7 of 14
`
`

`

`US 6,205,498 Bl
`
`1
`METHOD AND SYSTEM FOR MESSAGE
`TRANSFER SESSION MANAGEMENT
`
`FIELD OF THE INVENTION
`
`This invention relates generally to message queuing
`systems, and more particularly to the management of a
`session between two nodes in a message queuing system for
`transferring messages.
`
`5
`
`2
`called "ping" to detect whether a remote computer is in
`operation. The ping program takes the address of a remote
`computer as a parameter and sends an echo request. It then
`waits for an echo response from that remote computer, and
`reports whether the response is received within a predefined
`timeout period. The lack of a response within the timeout
`period suggests that the remote computer may be out or
`service.
`While the conventional ping approach works well with
`10 one computer, it does not allow the administrator to check a
`large group of computers at one time. Conventional ping
`applications support communications with a single com(cid:173)
`puter per session. Expanding them to deal with multiple
`computers is difficult. In addition, the computer that initiates
`the ping request must also handle the echo response. It
`cannot redirect the response to another computer or process
`the response off-line. Moreover, the conventional ping
`operation only works when both computers are directly
`connected using a communication protocol. The ping opera(cid:173)
`tion will not work if the computers use different communi-
`20 cation protocols or belong to separate networks.
`
`15
`
`BACKGROUND OF THE INVENTION
`A message queuing system enables applications in a
`distributed processing network to send messages to, and
`receive messages from, other applications. A message may
`contain data in any format that is understood by both the
`sending and receiving applications. When the receiving
`application receives a request message, it processes the
`request according to the content of the message and, if
`required, sends a response message back to the original
`sending application. The sending and receiving applications
`may be on the same machine or on separate machines
`connected by a network. While in transit between the
`sending and receiving applications, the message queuing
`system keeps messages in holding areas called message
`queues. The message queues protect messages from being
`lost in transit and provide a place for an application to look 25
`for messages sent to it when it is ready.
`When one application in the message queuing system
`sends a message to a receiving application on a remote
`computer, the message is often routed through a network of
`intermediate nodes in the message queuing system. Each
`node in the message route passes the message on to the next
`node by establishing a session therewith using a standard
`communication protocol. In some cases, the connection
`between the two nodes can fail, but the underlying commu(cid:173)
`nication protocol does not detect the connection failure and
`therefore cannot inform the message queuing system of the 35
`lost connection. To overcome this problem, an acknowledg(cid:173)
`ment mechanism at the message queue (MQ) server level
`has to be developed for indicating whether the message
`transfer has been successful.
`A conventional acknowledgment mechanism which sends
`an acknowledgment for each message or based on a maxi(cid:173)
`mum segment size is not adequate for managing the message
`transfer session for several reasons. The message queuing
`system is an asynchronous system in which the sending of
`a message or an acknowledgment does not coincide with the 45
`establishment of the session connection. As a result, the
`sending node in the session does not know when the
`acknowledgment may be received. Moreover, the same
`session between the two nodes is to be used for both sending
`and receiving messages by either node. The conventional 50
`acknowledgment mechanism is not adequate to prevent
`messages sent by one node from colliding with messages
`sent by the other node. Also, in terms of performance, the
`acknowledgment mechanism is unsatisfactory because the
`sending node cannot afford to stop and wait for an acknowl(cid:173)
`edgment every time it sends a message using the session 55
`connection.
`A message queuing system may include a large number of
`networked computers, which may go on and off at random
`intervals. To manage a large network, an administrator often
`needs a report of the operating status of the different 60
`computers in the network. This report does not have to be
`completely accurate, as it only has to provide a general
`indication of potential problems which will lead to a more
`in-depth examination of the possibly problematic comput(cid:173)
`ers.
`In networks using a connection-based communication
`protocol, it is common to use a program which is commonly
`
`SUMMARY OF THE INVENTION
`
`30
`
`In accordance with the invention, there is provided a
`method and system for managing transfer of message pack(cid:173)
`ets in a session between first and second nodes in a message
`queuing system that utilizes a session acknowledgment
`protocol to coordinate the two-way flow of message packet
`transmission. When a session is initiated, each of the two
`nodes specifies a session acknowledgment timeout period
`and a transmission window size. During the session, the first
`node transmits multiple message packets up to the window
`size set by the second node and stops to wait for a session
`acknowledgment from the second node. The second node
`sends a session acknowledgment when the session acknowl(cid:173)
`edgment timeout period set by the first node has expired, or
`when the number of packets received but not yet acknowl(cid:173)
`edged has reached the window size. The session acknowl(cid:173)
`edgment may either be sent as a separate message packet or
`piggyback on a message packet sent by the second node to
`the first node. A window-size field in the session acknowl-
`40 edgment allows the receiving node to set a new window size
`to dynamically adjust the incoming data flow.
`In accordance with another aspect of the invention, a
`"multi-ping" mechanism implemented with asynchronous
`message delivery allows an administrator to check the
`operating status of multiple computers in the message queu(cid:173)
`ing system. A ping-originator application sends echo request
`messages to a plurality of remote computers at one time. The
`echo response messages from the remote computers are sent
`to a response queue. An administration application reads the
`echo response messages and displays the operating status of
`the remote computers for viewing by the administrator.
`The advantages of the invention will become apparent
`with reference to the following detailed description when
`taken in conjunction with the drawings in which:
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a computer system that may
`be used to implement a method and system for managing a
`message transfer session according to the invention;
`FIG. 2 is a schematic diagram showing a message queuing
`system in which two computers exchanging messages are
`connected by a message route with intermediate nodes;
`FIG. 3 is a schematic diagram showing two nodes in a
`message route communicating with each other during a
`65 message transfer session by passing packets;
`FIG. 4 is a schematic diagram showing the format of a
`message packet for initiating a message transfer session;
`
`Page 8 of 14
`
`

`

`US 6,205,498 Bl
`
`3
`FIG. 5 is a schematic diagram showing the format of a
`message packet for passing parameters for managing a
`message transfer session;
`FIG. 6 is a schematic diagram showing the format of a
`message packet for session acknowledgment;
`FIG. 7 is a schematic diagram showing the format of a
`message packet which includes a session acknowledgment
`section;
`FIG. 8 is a schematic diagram showing a system for
`implementing a multi-ping mechanism based on asynchro(cid:173)
`nous message delivery; and
`FIG. 9 is a schematic diagram showing a graphic display
`of the operating states of computers in a message queuing
`system according to the results of a multi-ping operation.
`While the invention is susceptible of various modifica- 15
`tions and alternative constructions, certain illustrated
`embodiments hereof have been shown in the drawings and
`will be described below. It should be understood, however,
`that there is no intention to limit the invention to the specific
`forms disclosed, but, on the contrary, the invention is to
`cover all modifications, alternative constructions and
`equivalents falling within the spirit and scope of the inven(cid:173)
`tion as defined by the appended claims.
`
`10
`
`4
`disk drive interface 32, a magnetic disk drive interface 33,
`and an optical drive interface 34, respectively. The drives
`and their associated computer-readable media provide non(cid:173)
`volatile storage of computer readable instructions, data
`5 structures, program modules and other data for the personal
`computer 20. Although the exemplary environment
`described herein employs a hard disk, a removable magnetic
`disk 29 and a removable optical disk 31, it should be
`appreciated by those skilled in the art that other types of
`computer readable media which can store data that is
`accessible by a computer, such as magnetic cassettes, flash
`memory cards, digital video disks, Bernoulli cartridges,
`random access memories (RAMs), read only memories
`(ROM), and the like, may also be used in the exemplary
`operating environment.
`A number of program modules may be stored on the hard
`disk, magnetic disk 29, optical disk 31, ROM 24 or RAM 25,
`including an operating system 35, one or more application
`programs 36, other program modules 37, and program data
`38. A user may enter commands and information into the
`20 personal computer 20 through input devices such as a
`keyboard 40 and pointing device 42. Other input devices
`(not shown) may include a microphone, joystick, game pad,
`satellite dish, scanner, or the like. These and other input
`devices are often connected to the processing unit 21
`2s through a serial port interface 46 that is coupled to the
`system bus, but may be collected by other interfaces, such as
`a parallel port, game port or a universal serial bus (USE). A
`monitor 47 or other type of display device is also connected
`to the system bus 23 via an interface, such as a video adapter
`30 48. In addition to the monitor, personal computers typically
`include other peripheral output devices (not shown), such as
`speakers and printers.
`The personal computer 20 may operate in a networked
`environment using logical connections to one or more
`remote computers, such as a remote computer 49. The
`remote computer 49 may be another personal computer, a
`server, a router, a network PC, a peer device or other
`common network node, and typically includes many or all of
`the elements described above relative to the personal com(cid:173)
`puter 20, although only a memory storage device 50 has
`40 been illustrated in FIG. 1. The logical connections depicted
`in FIG. 1 include a local area network (LAN) 51 and a wide
`area network (WAN) 52. Such networking environments are
`commonplace in offices, enterprise-wide computer
`networks, intranets and the Internet.
`When used in a LAN networking environment, the per-
`sonal computer 20 is connected to the local network 51
`through a network interface or adapter 53. When used in a
`WAN networking environment, the personal computer 20
`typically includes a modem 54 or other means for establish-
`so ing communications over the wide area network 52, such as
`the Internet. The modem 54, which may be internal or
`external, is connected to the system bus 23 via the serial port
`interface 46. In a networked environment, program modules
`depicted relative to the personal computer 20, or portions
`thereof, may be stored in the remote memory storage device.
`It will be appreciated that the network connections shown
`are exemplary and other means of establishing a communi(cid:173)
`cations link between the computers may be used.
`The present invention is directed to the coordination of
`message transfer in a session established between two nodes
`60 in a message queuing system. Referring to FIG. 2, an
`application 60 running on a computer 62 sends a message to
`a second application 64 on a remote computer 66 which is
`connected to the first computer by a network 72 of inter(cid:173)
`mediate nodes. The source and destination computers and
`65 the intermediate nodes each has a message queue (MQ)
`server. The application 60 on the source computer 62
`interacts with the MQ server 68 through an application
`
`35
`
`DETAILED DESCRIPTION OF IBE
`PREFERRED EMBODIMENT
`Turning now to the drawings, FIG. 1 and the following
`discussion are intended to provide a brief, general, descrip(cid:173)
`tion of a suitable computing environment in which the
`invention may be implemented. Although not required, the
`invention will be described in the general context of
`computer-executable instructions, such as program modules,
`being executed by a personal computer. Generally, program
`modules include routines, programs, objects, components,
`data structures, etc. that perform particular tasks or imple(cid:173)
`ment particular abstract data types. Moreover, those skilled
`in the art will appreciate that the invention may be practiced
`with other computer system configurations, including hand(cid:173)
`held devices, multiprocessor systems, microprocessor-based
`or programmable consumer electronics, network PCs,
`minicomputers, mainframe computers, and the like. The
`invention may also be practiced in distributed computing
`environments where tasks are performed by remote process(cid:173)
`ing devices that are linked through a communications net(cid:173)
`work. In a distributed computing environment, program
`modules may be located in both local and remote memory 45
`storage devices.
`With reference to FIG. 1, an exemplary system for imple(cid:173)
`menting the invention includes a general purpose computing
`device in the form of a conventional personal computer 20,
`including a processing unit 21, a system memory 22, and a
`system bus 23 that couples various system components
`including the system memory to the processing unit 21. The
`system bus 23 may be any of several types of bus structures
`including a memory bus or memory controller, a peripheral
`bus, and a local bus using any of a variety of bus architec(cid:173)
`tures. The system memory includes read only memory
`(ROM) 24 and random access memory (RAM) 25. A basic
`input/output system 26 (BIOS) containing the basic routines
`that helps to transfer information between elements within
`the personal computer 20, such as during start-up, is stored
`in ROM 24. The personal computer 20 further includes a
`hard disk drive 27 for reading from and writing to a hard
`disk, not shown, a magnetic disk drive 28 for reading from
`or writing to a removable magnetic disk 29, and an optical
`disk drive 30 for reading from or writing to a removable
`optical disk 31 such as a CD ROM or other optical media.
`The hard disk drive 27, magnetic disk drive 28, and optical
`disk drive 30 are connected to the system bus 23 by a hard
`
`55
`
`Page 9 of 14
`
`

`

`US 6,205,498 Bl
`
`10
`
`35
`
`5
`programming Interface (API) layer 70 to send the message.
`The message queuing system routes the message through the
`network 72 of intermediate nodes to the MQ server 74 of the
`destination computer. The message routing is performed
`according to routing information provided by a message 5
`queue directory service (MQDS) 80 of the message queuing
`system. The message is received by the MQ server 74 of the
`destination computer and placed in a target queue 76 for
`retrieval by the destination application 64. While in transit,
`the message is transferred (or "hops") from one node (e.g.,
`the node 82) within the network 72 to the next node (e.g.,
`node 84) in the message route via a direct communication
`session established between the two nodes. This direct
`communication session is established for each node speci(cid:173)
`fied in the routing information so that the message can be
`received by the destination computer. As noted above, each
`node in the network 72 includes an MQ server, although for
`purposes of simplicity FIG. 2 only shows nodes 82 and 84
`as having MQ servers. It will also be appreciated that the
`session for message transfer may be between the source and
`destination computers if the two can directly access each
`other. The message transfer session may be formed using
`one of several commonly used communication protocols,
`such as TCP/SPX.
`The message queuing system may support multiple types
`of messages which are different in the ways they are
`delivered across the network 72. In a preferred embodiment,
`the message queuing system supports three types of mes(cid:173)
`sages: express, persistent, and transaction. An express mes(cid:173)
`sage is delivered by simply forwarding it from one node to
`the next node in the message route without provision for
`recovery from crash. Thus, there is no guarantee that an
`express message will ultimately reach the destination node.
`Nevertheless, because of the lower overhead involved in the
`delivery operation, the express message delivery may be the
`fastest way to send a message. A persistent message is
`delivered in a way that allows recovery if the message
`hopping operation crashes. The recoverability guarantees
`that the message will ultimately make its way to the desti(cid:173)
`nation node. A persistent message, however, may be deliv(cid:173)
`ered out of order with respect to other messages from the
`same sending node, and the destination node may receive
`duplicated copies of the message. In contrast, a transaction
`message is delivered in a way that guarantees exactly-once
`and in-order delivery of the message.
`The persistence of the delivery of a persistent message is
`achieved using a "store-and-forward" approach. In this
`approach, a copy of a persistent message in transit is stored
`in a persistent queue 86 on a disk ( or another type of
`non-volatile memory) of a sending node 84 before the
`message is forwarded to the next node 88. The stored copy
`is deleted only after the message has been successfully
`forwarded to the next node in a message transfer session. As
`used herein, the term "persistent message" means a message
`which is delivered using the store-and-forward approach.
`In an embodiment of the invention, to support the persis(cid:173)
`tent message delivery, each persistent message is given a
`sequence number for identification and tracking. When a
`session is established between the two nodes 82 and 84, for
`example, both sides initialize a "Persistence Packet Sent
`Number" and a "Persistence Packet Received Number" to
`zero. When the first node sends a persistent message packet,
`it increments its Persistence Packet Sent Number by one and
`virtually assigns this number to the packet as the packet
`sequence number. The sequence number is not sent with the
`packet. When the second node receives the packet, it incre(cid:173)
`ments its Persistence Packet Received Number and assigns
`the number to the received packet. Since the underlying
`communication protocol for the session between the two
`nodes ensures that the packets transmitted by the sending
`
`6
`node 82 are received in order and only once by the receiving
`node 84, both nodes in the session are expected to assign the
`same sequence number to the same persistent message
`packet.
`When the packet reaches the second node 84, it is stored
`in the persistence queue 86 on the disk. When the storage is
`completed, the node 84 sends a storage acknowledgment to
`the first node 82. After receiving the storage
`acknowledgment, the first node either stops its storage
`operation or removes the stored copy of the packet from its
`persistence queue on the disk.
`In accordance with an aspect of the invention, the suc(cid:173)
`cessful transfer of messages between two nodes 82, 84 is
`facilitated by the use of a session acknowledgment protocol
`handled by the MQ servers 90, 92 of the two nodes. The
`15 session acknowledgment protocol allows each node to estab(cid:173)
`lish session parameters for coordinating the data flow in both
`directions, such as timeout periods for sending acknowledg(cid:173)
`ments and the window size for data transmission. As will be
`described in greater detail below, the timeout periods are
`20 used by each node to require the other node in the session to
`respond to message transfer in a timely fashion. The window
`sizes allow a node to set an upper limit for incoming
`message transmission according to its available resources.
`Referring to FIG. 3, according to the session protocol, a
`25