(12) United States Patent
`Tuttle et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,407,722 B2
`Mar. 26, 2013
`
`USOO8407722B2
`
`(54) ASYNCHRONOUS MESSAGING USINGA
`NODE SPECIALIZATION ARCHITECTURE
`IN THE DYNAMIC ROUTING NETWORK
`(75) Inventors: Timothy Tuttle, San Francisco, CA
`US): Karl E. Rumelhart, Palo Alt
`A ser
`umenart, Falo Allo,
`
`(*) Notice:
`
`(73) Assignee: Shaw Parsing L.L.C., Las Vegas, NV
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1127 days.
`(21) Appl. No.: 11/396,251
`
`(22) Filed:
`(65)
`
`Mar. 30, 2006
`Prior Publication Data
`
`Oct. 11, 2007
`US 2007/O239822 A1
`Related U.S. Application Data
`(63) Continuation of application No. 10/105,018, filed on
`Mar 21, 2002, now Pat. No. 7,051,070, which is a
`continuation-in-part of application No. 10/017,182,
`filed on Dec. 14, 2001, now Pat. No. 7.043.525.
`s
`s
`sw - s
`(Continued)
`
`(51) Int. Cl.
`(2006.01)
`G06F 3/00
`(2006.01)
`G06F 15/16
`(52) U.S. Cl. ........................................ 719/316; 709/206
`(58) Field of Classification Search .................. 709/203,
`709/219; 719/309
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,230,048 A * 7/1993 Moy ................................. 707/1
`5,535,335 A
`7, 1996 Cox et al.
`5,692, 193 A 11/1997 Jagannathan et al.
`
`Receive
`Message
`
`identify
`Message
`Category
`
`lock Up
`
`Nisodes of the as
`t
`lities
`
`Tansmit
`
`- 4
`
`ea.
`
`5,699,523. A 12/1997 Li et al.
`$295 s A
`f 3. R E.
`5,754,939 A
`5/1998 Herz et al.
`(Continued)
`FOREIGN PATENT DOCUMENTS
`O 733983 A2
`9, 1996
`0 749 081 A1 12, 1996
`(Continued)
`
`EP
`EP
`
`OTHER PUBLICATIONS
`Franklin et al., “Dissemination-Based Information Systems.” IEEE
`Data Engineering Bulletin, vol. 19, No. 3, Sep. 1996, 9 pages.
`(Continued)
`
`Primary Examiner — Andy Ho
`Assistant Examiner — Tuan Dao
`(74) Attorney, Agent, or Firm — Sterne, Kessler, Goldstein
`& Fox PL.L.C.
`
`ABSTRACT
`(57)
`A network routes update messages containing updates to
`properties of live objects from input sources to clients having
`the objects. When the clients receive live objects, the clients
`identify the objectIDs associated with the objects and register
`the objectIDs with the routing network. The routing network
`is adapted to selectively send update messages to nodes in the
`network and the nodes forward the messages to the clients.
`One implementation uses a hierarchy of registries to indicate
`which nodes and clients receive which update messages.
`Another implementation assigns update messages to one or
`more of N categories and nodes to one or more of M types,
`and the gateways maintain mapping between categories and
`types. To ensure that clients receive all of the update messages
`for which they register, the clients connect to client proxies
`that in turn connect to at least one node of each type.
`
`37 Claims, 12 Drawing Sheets
`
`-N
`010
`
`a
`
`a
`
`a
`
`Deterine Clients
`
`E.
`
`ansmit
`
`a
`
`s
`Traini
`E -
`
`Clients
`
`107
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 1 of 29
`
`

`

`US 8,407,722 B2
`Page 2
`
`Related U.S. Application Data
`(60) Provisional application No. 60/256,613, filed on Dec.
`18, 2000, provisional application No. 60/276,847,
`filed on Mar. 16, 2001, provisional application No.
`60/278.303, filed on Mar. 21, 2001, provisional appli-
`cation No. 60/279,608, filed on Mar. 28, 2001, provi-
`sional application No. 60/280,627, filed on Mar. 29,
`2001.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,822,543 A 10, 1998 Dunn et al.
`5,845,324. A 12/1998 White et al.
`5,878.420 A
`3, 1999 de la Salle
`5,886,643 A
`3/1999 Diebboll et al.
`5.919,247 A
`7/1999 Van Hoffet al.
`5,933,429 A
`8, 1999 Bubenik et al.
`5,938,733 A
`8/1999 Heimsoth et al.
`5,964,839 A 10/1999 Johnson et al.
`5.974.457 A 10/1999 Waclawsky et al.
`6,018,619 A
`1/2000 Allard et al.
`6,029, 175 A
`2/2000 Chow et al.
`6,052,447 A
`4/2000 Golden et al.
`$95,493 A
`4.299 Ries et al.
`6,091,724. A * 7/2000 Chandra et al. ............... 370,390
`6,094,681. A
`7/2000 Shaffer et al.
`6,112,240 A
`8/2000 Pogue et al.
`6,138,158 A 10/2000 Boyle et al.
`6,173.406 B1
`1/2001 Wang et al.
`6,233,600 B1
`5/2001 Salas et al.
`6.253,167 B1
`6/2001 Matsuda et al.
`6.256,747 B1
`7/2001 Inohara et al.
`6.292,835 B1
`9/2001 Huang et al.
`$38,292 B 1929. Lecheler
`6,314.459 B1 * 1 1/2001 Freeman ....................... 709.220
`6,324,587 B1 * 1 1/2001 Trenbeath et al. ............ T19,310
`6,363,421 B2
`3/2002 Barker et al.
`6,366,926 B1* 4/2002 Pohlmann et al. ......... TO7 104.1
`6.405,245 B1
`6/2002 Burson et al.
`6,408,282 B1
`6/2002 Buist
`6,418.448 B1
`7/2002 Sarkar
`6,418.467 B1
`7/2002 Schweitzer et al.
`6,446,257 B1
`9/2002 Pradhan et al.
`6,449,638 B1
`9/2002 Wecker et al.
`6.460.036 B1
`10/2002 Herz
`6,484.143 B1
`11/2002 Swildens et al.
`6,502,131 B1
`12/2002 Vaid et al.
`6,510,323 B1* 1/2003 Stocker et al. ................ 455,466
`6,539.427 B1
`3/2003 Natarajan et al.
`6,553,413 B1
`4/2003 Leighton et al.
`6,560,611 B1
`5/2003 E.
`6,567,411 B2
`5/2003 Dahlen
`6,577.328 B2
`6/2003 Matsuda et al.
`6,606,596 B1
`8/2003 Zirngiblet al.
`6,606,643 B1
`8/2003 Emens et al.
`6,609,138 B1
`8/2003 Merriam
`6,654,804 B1
`1 1/2003 Fleming
`6,658,652 B1
`12/2003 Alexander et al.
`6,687,729 B1
`2/2004 Sievert et al.
`6,691, 165 B1
`2/2004 Bruck et al.
`6,725,446 B1
`4/2004 Hahn et al.
`6,728,747 B1
`4/2004 Jenkins et al.
`6,751,663 B1
`6, 2004 Farrell et al.
`6,760,324 B1
`7/2004 Scott et al.
`6,769,009 B1
`7/2004 Reisman
`6,789,115 B1
`9/2004 Singer et al.
`6,792.458 B1
`9, 2004 Muret et al.
`6,829,642 B1
`12/2004 Giroir et al.
`6.832.222 B1
`12/2004 Zimowski
`6836,886 B2 12/2004 Tuerke et al.
`6,871,346 B1
`3/2005 Kumbalimutt et al.
`6,918,084 B1
`7/2005 Slaughter et al.
`6,970,924 B1 1 1/2005 Chu et al.
`7,020,082 B2
`3/2006 Bhagavath et al.
`
`5, 2006 Tuttle et al.
`7,043,525 B2
`5/2006 Tuttle et al.
`7,051,070 B2
`9/2006 Fijolek et al.
`7,107,326 B1
`7,127,720 B2 10/2006 Canoet al.
`2:3: R
`1399; Sith et al.
`7207043 B2
`4/2007 Blythe et al.
`7.209.959 B1 * 4/2007 Campbell et al. ............. TO9,219
`232 R
`38 Estable et al.
`7,277.917 B2 10/2007 Tuttle et al.
`7,293,074 B1 * 1 1/2007 Jellinek et al. ................ TO9.218
`7.350,213 B2
`3/2008 Deutesfeld et al.
`7,412,518 B1
`8/2008 Duigou et al.
`7,426,721 B1
`339 Sarash et al.
`7.430,610 B2
`9/2008 Pace et al.
`7,516,177 B2
`4/2009 Knapp et al.
`7,565,359 B2
`7/2009 Nazem et al.
`2001/0012299 A1
`8, 2001 Dahlen
`2001/0047426 A1 11, 2001 Hunter
`2002/0010757 A1
`1/2002 Grank et al.
`2002fOO13852 A1
`1/2002 Janik
`2002/0024536 A1
`2/2002 Kahan et al.
`2002.0056004 A1
`5, 2002 Smith et al.
`2002/0073.165 A1
`6/2002 McNulty et al.
`2002fOO78251 A1
`6, 2002 Lewis
`2002fOO87630 A1* 7, 2002 Wu ............................... TO9,203
`2002fO095399 A1
`7, 2002 Devine et al.
`2002/0120717 A1* 8, 2002 Giotta ........................... TO9,219
`2002fO165977 A1* 11/2002 Novaes ......................... TO9,238
`2003, OO26254 A1
`2/2003 Sim
`2003/004111.0 A1
`2/2003 Wenocur et al.
`2003/O120817 A1
`6, 2003 Ott et al.
`2003. O1401 11 A1
`7, 2003 Pace et al.
`2004/0139433 A1
`7/2004 Blythe et al.
`2004/0199926 A1 10/2004 Gilgen et al.
`2004/0215493 A1 10/2004 Koppes et al.
`2005/0027815 A1
`2/2005 Christodoulou et al.
`2005/0033841 A1
`2/2005 McCarthy et al.
`2005/0125557. A
`6/2005 Vasudevanet al.
`2005/0278726 A1 12/2005 Cano et al.
`2006/0031282 A1
`2/2006 Tuttle et al.
`2006, OO31283 A1
`2/2006 Tuttle et al.
`2006/0041681 A1
`2/2006 Rumelhart
`2006/0075.279 A1
`4/2006 Cameros et al.
`2006/01 17318 A1
`6/2006 Rumelhart et al.
`2006/0265488 A1 11/2006 Tuttle et al.
`2007/0033293 A1
`2/2007 Rumelhart
`2007/0050519 A1
`3, 2007 Cano et al.
`2007/0061811 A1
`3/2007 Rumelhart et al.
`2009/0077173 A1
`3/2009 Lowery et al.
`FOREIGN PATENT DOCUMENTS
`O 889 421 A1
`1, 1999
`EP
`WO97, 16796 A1
`5, 1997
`WO
`WOO1,63837 A2
`8, 2001
`WO
`WO WO 2005/046184 A1
`5, 2005
`OTHER PUBLICATIONS
`Nagami et al., “Toshiba's Flow Attribute Notification Protocol
`(FANP) Specification.” Apr. 1997, RFC 2129, Internet RFC/STD/
`FYI/BCP Archives online), retrieved on May 16, 2002. Retrived
`from the Internet: <landfield.com/rfcs/rfc2129.html>, 16 pages.
`Strom et al., “Gryphon: An Information Flow Based Approach to
`Message Brokering.” International Symposium on Software Reli
`ability Engineering 98, 1998, 2 pages.
`Sturman et al., “Reflection in the Gryphon Message Brokering Sys
`tem.” Reflection Workshop of the 13. Sup,th ACM Conference on
`Object Oriented Program Systems, Languages and Applications
`(OOPSLA '98), 1998, 5 pages.
`International DOI Foundation, “Introduction to the Digital Object
`Identifier,” online). Apr. 1998 retrieved on May 16, 2002).
`Retrieved from the Internet: <doi.org/introduction.html>, 4 pages.
`Aksoy et al., “Research in Data Broadcast and Dissemination”. Proc.
`1st Int’l Conf. on Advanced Multimedia Content Processing, Osaka
`University, Osaka, Japan, Nov. 1998.
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 2 of 29
`
`

`

`US 8,407,722 B2
`Page 3
`
`Banavar et al., “An Efficient Multicast Protocol for Content-Based
`Publish-Subscribe Systems.” Proc. of the 19th International Confer
`ence on Distributed Computing Systems, 1999, 9 pages.
`Banavar et al., “Information Flow Based Event Distribution
`Middleware.” Proceedings of the 1999 ICDCS Workshop on Elec
`tronic Commerce and Web-Based Applications, 1999, 8 pages.
`Aguilera et al., “Matching Events in a Content-based Subscription
`System.” Eighteenth ACM Symposium on Principles of Distributed
`Computing (PODC 99), Atlanta, GA. May 4-6, 1999, 9 pages.
`Banavar et al., “A Case for Message Oriented Middleware.” Distrib
`uted Computing, 13. Sup,th International Symposium, Bratislava,
`Slavak Republic, Sep. 27-29, 1999, 18 pages.
`Aguilera et al., “Efficient Atomic Broadcast Using Deterministic
`Merge.” Symposium on Principles of Distributed Computing, 2000,
`10 pages.
`Opyrchal et al., “Exploiting IP Multicast in Content-Based Publish
`Subscribe Systems.” Proceedings of the IFIP ACM International
`Conference on Distributed Systems Platforms (Middleware 2000),
`Apr. 2000, 23 pages.
`Caplin Systems Ltd., White Paper “Real Time Text Protocol
`(RTTP).” Version 1.1, Sep. 2000, 11 pages.
`Reuters, "Reuters Market Data Systems and the Trading Solutions
`Architecture.” Version 1.0, Jan. 12, 2001, 51 pages.
`Ramamrithan et al., “Dissemination of Dynamic Data on the
`Internet,” online). Powerpoint Presentation, Spring 2001, retrieved
`on Feb. 6, 2002), 5 pages. Retrieved from the Internet <.cs.umbc.edu/
`courses graduate/CMSC691T/spring. Sub-2001/rlist amit.ppt).
`ComputerLetter, vol. 17. No. 23, Jul. 16, 2001, pp. 1-8.
`ComputerLetter, vol. 17. No. 31, Sep. 24, 2001, pp. 1-6.
`ComputerLetter, vol. 17. No. 35, Nov. 5, 2001, pp. 1-6.
`Tuttle et al., “Upstream Delivery of Information in a Digital Net
`work”, U.S. Appl. No. 09/901,582, filed Jul. 9, 2001.
`“Repackaging the Net'. ComputerLetter, vol. 17, No. 35, Nov. 5,
`2001, pp. 1-5.
`"Reckoning with IP, ComputerLetter, vol. 17. No. 37, Nov. 19.
`2001, pp. 1-6.
`“Persistence Counts”. ComputerLetter, vol. 17, No. 23, Jul. 16, 2001,
`pp. 1, 5-7.
`Zhao et al.; "A Workflow-centric Study of Organizational Knowledge
`Distribution.” Proceedings of the 33rd Hawaii International Confer
`ence on System Sciences; 2000; pp. 1-10; IEEE.
`Gribble, et al.; "The Ninja Architecture for Robust Internet-scale
`Systems and Services.” ComputerNetworks; 2001; pp. 473-497; vol.
`35; Elsevier Science B.V.
`Carmona, David; “Programming the Thread Pool in the .NET Frame
`work'; 'Online Jun. 2002, pp. 1-17, XP002357234; retrieved on
`Dec. 1, 2005 from the Internet: URL:http://msdn.microsoft.com/
`library/default.asp?url=/library/en-us/dndotnet/hmtl/progthrepool.
`asp>, pp. 1-17.
`Welsh, Matthew D.; "An Architecture for Highly Concurrent, Well
`Conditioned Internet Services': URL: http://www.eecs.harvard.edu/
`{mdw?papers/mdw-phdthesis/pdf>, 2005, pp. 48-54, 101, and 113
`114.
`Written Opinion of the International Searching Authority for Inter
`national Application No. PCT/US2005/029162, recorded Jan. 17,
`2006, 7 pages.
`Written Opinion of the International Searching Authority for Inter
`national Application No. PCT/US2005/029021, recorded Dec. 14,
`2005, 10 pages.
`
`Written Opinion of the International Searching Authority for Inter
`national Application No. PCT/US2005/029158, recorded Jan. 25,
`2006, 7 pages.
`Non-Final Office Action dated Oct. 26, 2009, U.S. Appl. No.
`1 1/205.263, Rumelhart et al., filed Aug. 15, 2005.
`Final Office Action dated Nov. 24, 2009, U.S. Appl. No. 1 1/205.237,
`Rumelhart et al., filed Aug. 15, 2005.
`Non-Final Office Action dated May 3, 2005, 8 pages in U.S. Appl.
`No. 10/017,182, Tuttle et al., filed Dec. 14, 2001.
`Notice of Allowance dated Jan. 3, 2006, U.S. Appl. No. 10/105,018,
`Tuttle et al., filed Mar. 21, 2002.
`Notice of Allowance dated Jul. 5, 2006, U.S. Appl. No. 10/105,018,
`Tuttle et al., filed Mar. 21, 2002.
`Non-Final Office Action dated Aug. 9, 2005, U.S. Appl. No.
`10/213,269, Cano et al., filed Aug. 5, 2002.
`Final Office Action dated Jan. 26, 2006, U.S. Appl. No. 10/213,269,
`Cano et al., filed Aug. 5, 2002.
`Notice of Allowance dated Jun. 6, 2006, U.S. Appl. No. 10/213.269,
`Cano et al., filed Aug. 5, 2002.
`Non-Final Office Action dated Feb. 3, 2009, U.S. Appl. No.
`1 1/205,233, Rumelhart et al., filed Aug. 15, 2005.
`Non-Final Office Action dated Aug. 6, 2009, U.S. Appl. No.
`1 1/205,233, Rumelhart et al., filed Aug. 15, 2005.
`Non-Final Office Action dated Apr. 22, 2008, U.S. Appl. No.
`1 1/205.237, Cameros et al., filed Aug. 15, 2005.
`Non-Final Office Action dated Apr. 29, 2009, U.S. Appl. No.
`1 1/205.237, Cameros et al., filed Aug. 15, 2005.
`Final Office Action dated Nov. 25, 2008, U.S. Appl. No. 1 1/205.237,
`Cameros et al., filed Aug. 15, 2005.
`Notice of Allowance dated May 22, 2007, U.S. Appl. No. 1 1/347,802,
`Tuttle et al., filed Feb. 3, 2006.
`Non-Final Office Action dated Jan. 26, 2007, U.S. Appl. No.
`1 1/347,802, Tuttle et al., filed Feb. 3, 2006.
`Non-Final Office Action dated Mar. 6, 2009, U.S. Appl. No.
`1 1/515,233, Rumelhart et al., filed Aug. 31, 2006.
`Final Office Action dated Oct. 7, 2009, U.S. Appl. No. 1 1/515,233,
`Rumelhart et al., filed Aug. 31, 2006.
`Non-Final Office Action dated Jan. 7, 2010, U.S. Appl. No.
`1 1/205,233, Rumelhart et al., filed Aug. 15, 2005.
`Non-Final Office Action dated Feb. 22, 2010, U.S. Appl. No.
`1 1/515,233, Rumelhart et al., filed Aug. 31, 2006.
`Final Office Action dated Mar. 23, 2010, U.S. Appl. No. 1 1/205.263,
`Rumelhart et al., filed Aug. 15, 2005.
`U.S. Appl. No. 13/617,168, Tuttle et al., “Asynchronous Messaging
`Using A Node Specialization Architecture in the Dynamic Routing
`Network.” filed Sep. 14, 2012.
`Non-Final Rejection mailed Aug. 9, 2005 for U.S. Appl. No.
`10/213,269, filed Aug. 5, 2002; 11 pages.
`Final Rejection mailed Jan. 26, 2006 for U.S. Appl. No. 10/213,269,
`filed Aug. 5, 2002; 8 pages.
`Notice of Allowance mailed Jun. 6, 2006 for U.S. Appl. No.
`10/213,269, filed Aug. 5, 2002; 4 pages.
`Non-Final Rejection mailed Aug. 26, 2010 for U.S. Appl. No.
`11/515.366, filed Aug. 31, 2006; 16 pages.
`Final Rejection mailed Feb. 17, 2011 for U.S. Appl. No. 1 1/515.366,
`filed Aug. 31, 2006; 30 pages.
`Notice of Allowance mailed Nov. 10, 2005 for U.S. Appl. No.
`10/017,182, filed Dec. 14, 2001; 6 pages.
`* cited by examiner
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 3 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 1 of 12
`
`US 8,407,722 B2
`
`0 || ||
`
`
`
`
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 4 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 2 of 12
`
`US 8,407,722 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`?senbax|| 36ed qÐNA
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 5 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 3 of 12
`
`US 8,407,722 B2
`
`$ (61-)
`
`
`
`
`
`GOES GEES GEG) GEG? GÐ) GE? G? G?)} v\!
`
`
`
`
`
`
`
`0 || ||
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 6 of 29
`
`

`

`U.S. Patent
`
`Mar.26, 2013
`
`Sheet 4 of 12
`
`US 8,407,722 B2
`
`
`
`€seyeqL\ius\V4!vepue|yeOoy\dsLeNoy
`Z=XeL0616FO9ds
`
`$dlO9$|J2Q}004
`§=6syods=|e007
`
`OLY
`
`cL?
`
`OLY
`
`$2100S
`leqeseg
`
`seio9g
`
`OP
`
`
`
`siapleyPUeLYeEO
`
`
`
`sAoqmoysejeg
`
`siaBpogv7
`
`SJUBEID4S
`
`
`
`siaBueysexes
`
`SVPUe|HeO
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1001
`Page 7 of 29
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 7 of 29
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 5 of 12
`
`US 8,407,722 B2
`
`
`
`O)
`O
`h
`
`O
`CO
`
`-
`
`O.
`C
`
`.
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 8 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 6 of 12
`
`US 8,407,722 B2
`
`
`
`
`
`
`
`Terminate
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`61O
`
`612
`
`Parse Page
`and identify
`Object IDs
`
`Connect to
`Routing
`Network
`
`Register
`Object IDs
`With
`Network
`
`Message
`Received
`from Network
`?
`
`
`
`Update
`ldentified
`Object
`
`Fig. 6
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 9 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 7 of 12
`
`US 8,407,722 B2
`
`710A
`
`71OB
`
`71OC
`
`71 OD
`
`Information
`ProVider
`
`
`
`
`
`Dynamic
`Content
`Provider
`
`O O.
`
`O.
`
`Global Load Balancer
`
`16
`
`Cluster Load Balancer
`
`- - - - - - -
`Cluster Load
`Balancer 720A
`
`|
`
`724A
`
`I
`
`Cluster Load
`Balancer 722A
`
`Cluster Load Balancer
`
`
`
`Global Load Balancer
`
`71
`
`712A
`
`712B
`
`712C
`Fig. 7
`
`712D
`
`712E
`
`712F
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 10 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 8 of 12
`
`US 8,407,722 B2
`
`
`
`Receive
`Message
`
`Extract DS
`
`Look up
`Registered
`Nodes
`
`Transmit
`Message to
`Registered Nodes
`if any
`
`Look up
`Registered
`Clients
`
`Transmit
`Message to
`Registered
`Clients
`
`Fig. 8
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 11 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 9 of 12
`
`US 8,407,722 B2
`
`
`
`Node of Type 1
`732
`
`Node of Type 2
`732
`
`Client Proxy
`
`Client 1
`
`Client 2
`
`110
`
`Fig. 9
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 12 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 10 of 12
`
`US 8,407,722 B2
`
`
`
`Receive
`Message
`
`identify
`Message
`Category
`
`Look Up
`Nodes of the
`Message
`Category
`
`Transmit
`Message to
`ldentified Nodes
`
`Determine Clients
`Registered for the
`Message and Client
`Proxies Connected
`to the Clients
`
`Transmit
`Message to
`Client Proxy
`
`Transmit
`Message to
`Registered
`Clients
`
`Fig. 10
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 13 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 11 of 12
`
`US 8,407,722 B2
`
`
`
`Node of Type 1
`
`Node of Type 2
`
`Client 1
`
`110
`
`Client Proxy
`736
`
`Fig. 11
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 14 of 29
`
`

`

`U.S. Patent
`
`Mar. 26, 2013
`
`Sheet 12 of 12
`
`US 8,407,722 B2
`
`
`
`Node of Type 1
`
`Node of Type 2
`
`Node of Type 3
`
`Client 1
`
`Client 1
`
`110
`
`Fig. 12
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 15 of 29
`
`

`

`US 8,407,722 B2
`
`1.
`ASYNCHRONOUS MESSAGING USINGA
`NODE SPECIALIZATION ARCHITECTURE
`IN THE DYNAMIC ROUTING NETWORK
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation of U.S. application Ser.
`No. 10/105,018 filed Mar. 21, 2002 (now U.S. Pat. No. 7,051,
`070), which is a continuation-in-part of U.S. application Ser.
`No. 10/017,182 filed Dec. 14, 2001 now U.S. Pat. No. 7,043,
`525, which claims the benefit of U.S. Provisional Application
`No. 60/256,613, filed Dec. 18, 2000, U.S. Provisional Appli
`cation No. 60/276,847, filed Mar. 16, 2001, U.S. Provisional
`Application No. 60/278.303, filed Mar. 21, 2001, U.S. Pro
`visional Application No. 60/279,608, filed Mar. 28, 2001, and
`U.S. Provisional Application No. 60/280,627, filed Mar. 29,
`2001, all of which are hereby incorporated by reference
`herein.
`
`10
`
`15
`
`BACKGROUND
`
`2
`sions, cellular telephones, personal digital assistants and
`other handheld devices, and special-purpose web-browsing
`appliances. Client devices typically employ a program called
`a “web browser' for interpreting the HTML or other display
`instructions in the web page and displaying the content
`accordingly. Most web browsers include special functional
`ity, such as a Java Virtual Machine, for executing JAVAR)
`applets and/or other applets or scripts embedded in the web
`pageS.
`A client device specifies a web page or other document on
`the web using a Uniform Resource Locator (URL). A URL
`has the form “service://server/path/file.” Here “service'
`refers to the protocol to be used, such as the file transfer
`protocol (FTP) or the hypertext transport protocol (HTTP).
`“Server' is the IP address of the server containing the page,
`and “path/file’specifies the particular web page on the server.
`The Web suffers from a substantial limitation with respect
`to dynamically updating content in a web page at a client
`device. The Web’s only mode of operation is for a client
`device to first request a page from a server and then for the
`server to send the requested page to the client device. Once
`the server delivers the page to the client, it typically termi
`nates its connection to the client, and does not retain any
`information about the client or the page that was sent. For this
`reason, servers are typically “stateless. As a result, client
`devices drive and control the flow of information around the
`Web. While client-side control is appropriate in some situa
`tions, it does not permit efficient updating of data at the client
`devices. For example, ifa web page contains information that
`may change, such as the score of a baseball game or a stock
`quote, the server has no way to inform the client devices that
`are viewing the page of the change. Instead, the client devices
`must ask the server for the updated information. However, the
`client devices do not know when the information on the web
`page has changed, and thus do not know to ask for the update.
`There are some simple web programming techniques that
`attempt to update content on client device-side web pages.
`One approach that web designers use is to rely on the client
`devices to periodically re-request web pages. This updating
`can be performed as the result of user action (such as pressing
`the “refresh' button) or can be automated to occur on a
`particular schedule (such as by using the HTML Meta
`Refreshtag to cause the client device to request the page every
`X seconds). Although this technique provides client devices
`with more up-to-date information, it is very wasteful of
`resources. In particular, the web server must resend the page
`even if nothing has changed, and, even when something has
`changed, it must resend the entire web page rather than just
`the updated information, which may be only a very small part
`of the page. Further, attempting to reduce unnecessary
`requests by decreasing the request rate results in decreasing
`the currency of the data. This is an unalterable trade off in a
`client-driven approach.
`The performance of automatic refreshing can be improved
`Somewhat by putting information that may change in a sepa
`rate frame from information that is less likely to change, and
`only refreshing the separate frame. A few web designers even
`write custom JAVA applets to limit refreshing to individual
`components on a page, such as the score of a Soccer game. A
`willingness to go to such effort illustrates the serious drain of
`resources caused by frequent refreshing. Nevertheless, even
`custom JAVA applets are not a meaningful attack on this
`problem. Custom applets require a large separate develop
`ment effort for each item on each page that might need to be
`updated. More importantly, most custom applets still update
`content based upon client-driven requests, although it is pos
`sible to design an applet that accepts “pushed' messages. This
`
`25
`
`30
`
`35
`
`40
`
`45
`
`1. Field of the Invention
`This invention pertains in general to transferring informa
`tion through digital networks and in particular to transferring
`information for remotely updating content at client devices
`through the digital networks.
`2. Background Art
`The Internet is a digital network of computers. An indi
`vidual computer on the Internet is typically identified by an
`internet protocol (IP) address. A computer on the Internet
`sends a packet of information to another computer by routing
`the packet to a logical port at the destination computer's IP
`address. The destination computer interprets the packet
`according to one of several possible protocols determined by
`the port to which the packet was sent.
`The World WideWeb (the “Web’) is a collection of tech
`nology and content available on the Internet that allows the
`content to be routed from server computers to particular des
`tination computers. The Web includes a large number of web
`pages residing on many different servers. Web pages contain
`one or more files, or references to one or more files, specify
`ing instructions for presenting the web page and content, Such
`as text, images, applets, video, and/or audio.
`Web pages use a variety of definitional and programming
`languages to control how information is presented. The most
`fundamental of these is the Hypertext Markup Language
`(HTML). HTML uses a system of “tags' to specify how
`content should be displayed. Recent advances in HTML
`introduce “style sheets” which help separate content infor
`50
`mation from display information. HTML has also been modi
`fied and extended to provide new capabilities. For example,
`Extensible Markup Language (XML) adds semantic content
`to web pages. In addition, Dynamic HTML (DHTML) adds
`Some dynamic content to web pages.
`A web page may also include one or more programs for
`controlling how the web page is displayed. For example,
`JAVAR) applets and JAVASCRIPTR) scripts may be used to
`control the display of a web page. In addition, DHTML uses
`Scripts to control the dynamic content. Thus, a web page
`designer can use applets and scripts to produce animation
`effects or modify the display based on user interaction. For
`example, the designer can write a script that changes the color
`of a piece of text when a user clicks on a button.
`Devices that display/execute web pages are often called
`“client devices” or simply "clients.” Client devices include
`personal computers, web-enabled set-top boxes and televi
`
`55
`
`60
`
`65
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1001
`Page 16 of 29
`
`

`

`US 8,407,722 B2
`
`3
`solution is not scalable to provide updated information for
`large numbers of client devices and for large numbers of web
`pageS.
`Therefore, there is a need in the art for an efficient way to
`provide dynamic content to a web page at a client device.
`
`DISCLOSURE OF THE INVENTION
`
`4
`client proxies. The client proxies, in turn, transmit the mes
`sages to the clients that have registered for the messages.
`The features and advantages described in this Summary and
`the following detailed description are not all-inclusive, and
`particularly, many additional features and advantages will be
`apparent to one of ordinary skill in the art in view of the
`drawings, specification, and claims hereof.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a high-level block diagram illustrating an envi
`ronment containing a dynamic content routing network;
`FIG. 2 is an interaction diagram illustrating interactions
`among a server, information provider, dynamic content pro
`vider, client, and routing network to update a property of a live
`object on a web page;
`FIG. 3 is a high-level diagram graphically indicating the
`many-to-many mapping performed by the routing network;
`FIG. 4 illustrates two different web pages containing sports
`Scores;
`FIG. 5 is a block diagram illustrating an input source and
`the tools available to it for generating the update messages;
`FIG. 6 is a flow chart illustrating the steps performed by an
`embodiment of an activation module:
`FIG. 7 is a block diagram illustrating a lower-level view of
`the routing network according to an embodiment of the
`present invention;
`FIG. 8 is a flow chart illustrating steps performed by a
`gateway and a node in a cluster to perform object-based
`routing of a message received from an input source in an
`embodiment using a hierarchy of registries;
`FIG. 9 is a block diagram illustrating a high-level view of
`the routing network in an embodiment adapted to use mes
`sage categories, node types, and client proxies;
`FIG. 10 is a flow chart illustrating steps performed by a
`gateway, a node that stores client registration information,
`and a pass-through client proxy to perform object-based rout
`ing of a message received from an input source:
`FIG. 11 is a block diagram illustrating a high-level view of
`the routing network for an embodiment in which the client
`proxy stores the client registration information; and
`FIG. 12 is a block diagram illustrating a high-level view of
`the routing network for an embodiment in which the nodes
`adopt client proxy functionality.
`The figures depict an embodiment of the present invention
`for purposes of illustration only. One skilled in the art will
`readily recognize from the following description that alterna
`tive embodiments of the structures and methods illustrated
`herein may be employed without departing from the prin
`ciples of the invention described herein.
`
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`FIG. 1 is a high-level block diagram illustrating an envi
`ronment 100 containing a dynamic content routing network
`110 (hereafter referred to as the “routing network”). The
`environment 100 also contains a server 112 in communica
`tion with a client 114, an information provider 108, and a
`dynamic content provider 116. Although a typical environ
`ment 100 will have hundreds of servers 112 and information
`providers 108, thousands (or even millions) of clients 114,
`and multiple dynamic content providers 116, FIG. 1 illus
`trates only one of each of these entities in order to enhance the
`clarity of this description.
`The server 112, client 114, information provider 108,
`dynamic content provider 116, and routing network 110 are
`
`The above need is met by a dynamic content routing net
`work that routes messages containing data for updating prop
`erties of live objects to clients displaying web pages or other
`representations of data containing the live objects. The web
`server that initially provides the web pages to the clients does
`not need to track which clients are currently displaying the
`live objects. Instead, the information provider or a dynamic
`content provider (generically referred to as an "input source”)
`that provided the live object simply sends an update message
`to the routing network. This routing utilizes bandwidth effi
`ciently because the update messages are provided to the cli
`ents only when the live objects change.
`The routing network is adapted to selectively send mes
`sages to the nodes in the network. In one embodiment, a
`hierarchy of registrations is used. Each gateway in the routing
`network maintains the mappings between the live: objects
`and the nodes that have registered for the live objects. Each
`node in the routing network, in turn, maintains the mappings
`between the live objects and the clients that display them. An
`input source provides a message to a gateway in each cluster
`in the routing network. Each gateway forwards to each node
`only messages that reference the objects for which it has
`registered. Each node forwards to each client only messages
`that reference the objects for which it has registered. Adding
`node functionality to the gateway and client functionality to
`the node advantageously allows the routing network to decide
`which nodes should receive an update message. As a result,
`messages are sent to only nodes that have registered for the
`messages. Furthermore, each node receives all the messages
`that the clients connected to that node are interested in.
`In another embodiment, all messages from an input source
`are assigned to one or more of N categories. Also, the nodes
`are assigned to one or more of M types, and mappings are
`created between message categories and node types. Each
`gateway keeps track of these mappings. When a gateway
`receives messages from input sources, the gateway identifies
`the categories of the messages and routes the messages to the
`nodes of the types to which the categories are mapped. To
`ensure that clients have access to the messages they need,
`clients are allowed to communicate with nodes of several
`types using client proxies connected between the clients and
`the nodes. There are at least two ways to implement the cl