I 1111111111111111 11111 111111111111111 IIIII IIIII IIIII IIIII 1111111111 11111111
`US006546425Bl
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,546,425 Bl
`Apr. 8, 2003
`
`OTHER PUBLICATIONS
`Montenegro, G., Sun Microsystems, Inc., Internet Draft,
`"Reverse Tunneling for Mobile IP," Jan. 12, 1997.
`Bakre, A; Badrinath, B.R., "I-TCP: Indirect TCP for
`Mobile Hosts," Department of Computer Science, Rutgers
`University, Piscataway, NJ 08855, DCS-TR-314, Oct.
`1994.
`Internet Draft Piscitello, D., Phifer, L. Core Competence,
`Wang, Y., Hovey, R. Bellcore: "Mobile Network Computing
`Protocol (MNCP)," Sep. 3, 1997.
`Maltz, David A Bhagwat, Pravin, "MSOCKS: An Archi(cid:173)
`tecture
`for Transport Layer Mobility," 1998
`IEEE,
`0-7803-4386-7/98.
`(List continued on next page.)
`Primary Examiner---Mehmet B. Geckil
`(74) Attorney, Agent, or Firm-Nixon & Vanderhye P.C.
`ABSTRACT
`(57)
`
`A seamless solution transparently addresses the character(cid:173)
`istics of nomadic systems, and enables existing network
`applications to run reliably in mobile environments. The
`solution extends the enterprise network, letting network
`managers provide mobile users with easy access to the same
`applications as stationary users without sacrificing reliability
`or centralized management. The solution combines advan(cid:173)
`tages of existing wire-line network standards with emerging
`mobile standards to create a solution that works with exist(cid:173)
`ing network applications. A Mobility Management Server
`coupled to the mobile network maintains the state of each of
`any number of Mobile End Systems and handles the com(cid:173)
`plex session management required to maintain persistent
`connections to the network and to other peer processes. If a
`Mobile End System becomes unreachable, suspends, or
`changes network address (e.g., due to roaming from one
`network interconnect to another), the Mobility Management
`Server maintains the connection to the associated peer
`task-allowing the Mobile End System to maintain a con(cid:173)
`tinuous connection even though it may temporarily lose
`contact with its network medium. In one example, Mobility
`Management Server communicates with Mobile End Sys(cid:173)
`tems using Remote Procedure Call and Internet Mobility
`Protocols.
`
`76 Claims, 32 Drawing Sheets
`
`(12) United States Patent
`Hanson et al.
`
`(54) METHOD AND APPARATUS FOR
`PROVIDING MOBILE AND OTHER
`INTERMITTENT CONNECTIVITY IN A
`COMPUTING ENVIRONMENT
`
`(75)
`
`Inventors: Aaron D. Hanson, Seattle, WA (US);
`Emil A. Sturniolo, Medina, OH (US);
`Anatoly Menn, Seattle, WA (US); Erik
`D. Olson, Seattle, WA (US); Joseph T.
`Savarese, Edmonds, WA (US)
`
`(73) Assignee: Netmotion Wireless, Inc., Seattle, 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/330,310
`Jun. 11, 1999
`
`Filed:
`
`(22)
`
`(60)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Related U.S. Application Data
`Provisional application No. 60/103,598, filed on Oct. 9,
`1998.
`Int. Cl.7 . ... ... .. ... ... ... ... .. ... ... ... ... ... .. ... ... .. G06F 15/16
`U.S. Cl. ........................ 709/227; 709/228; 709/330
`Field of Search ................................. 709/245, 250,
`709/330, 229, 228, 227, 230, 203, 220,
`221, 202
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`Freeburg et al.
`4,837,800 A
`6/1989
`Hop
`4,912,756 A
`3/1990
`Perkins
`5,159,592 A
`10/1992
`Harrison
`5,181,200 A
`1/1993
`Natarajan
`5,212,806 A
`5/1993
`Bird et al.
`5,224,098 A
`6/1993
`Messenger
`5,276,680 A
`1/1994
`Davidson et al.
`5,307,490 A
`4/1994
`5,325,361 A *
`Lederer et al.
`............. 370/401
`6/1994
`Morris et al.
`9/1994
`5,349,678 A
`Seitz et al.
`4/1995
`5,410,543 A
`(List continued on next page.)
`
`104
`
`101
`
`208
`
`104
`
`'
`
`,
`ronsport
`:
`------ ------\::108-----"
`
`110
`
`Instacart, Ex. 1037
`
`1
`
`

`

`US 6,546,425 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,426,637 A
`5,442,791 A
`5,446,736 A
`5,475,819 A
`5,481,535 A
`5,490,139 A
`5,491,800 A
`5,499,343 A
`5,515,508 A
`5,548,723 A
`5,559,800 A
`5,564,070 A
`5,566,225 A
`5,568,645 A
`5,572,528 A
`5,574,774 A
`5,602,916 A
`5,610,595 A
`5,623,601 A
`5,633,868 A
`5,657,390 A
`5,664,007 A
`5,673,322 A
`5,682,534 A
`5,717,737 A
`5,721,818 A
`5,724,346 A
`5,732,074 A
`5,748,897 A
`5,752,185 A
`5,754,774 A
`5,758,186 A
`5,768,525 A
`5,771,459 A
`5,784,643 A
`5,796,727 A
`5,848,064 A
`5,856,974 A
`5,889,816 A
`5,909,431 A *
`5,935,212 A
`5,968,176 A
`6,006,090 A
`6,091,951 A
`6,112,085 A *
`6,147,986 A
`6,154,461 A
`6,161,123 A
`6,167,513 A
`6,170,057 Bl
`6,336,135 Bl *
`6,201,962 Bl *
`6,230,004 Bl
`6,233,617 Bl *
`6,233,619 Bl *
`6,236,652 Bl *
`6,243,753 Bl *
`6,249,818 Bl
`6,256,739 Bl *
`6,308,281 Bl
`
`6/1995
`8/1995
`8/1995
`12/1995
`1/1996
`2/1996
`2/1996
`3/1996
`5/1996
`8/1996
`9/1996
`10/1996
`* 10/1996
`10/1996
`11/1996
`11/1996
`2/1997
`3/1997
`4/1997
`5/1997
`8/1997
`9/1997
`9/1997
`10/1997
`2/1998
`2/1998
`3/1998
`3/1998
`5/1998
`5/1998
`5/1998
`5/1998
`6/1998
`6/1998
`7/1998
`8/1998
`12/1998
`1/1999
`3/1999
`6/1999
`8/1999
`10/1999
`12/1999
`7/2000
`8/2000
`11/2000
`11/2000
`12/2000
`12/2000
`1/2001
`1/2001
`3/2001
`5/2001
`5/2001
`5/2001
`5/2001
`6/2001
`6/2001
`7/2001
`10/2001
`
`Derby et al.
`Wrabetz et al.
`Gleeson et al.
`Miller et al.
`Hershey
`Baker et al.
`Goldsmith et al.
`Pettus
`Pettus et al.
`Pettus
`Mousseau et al.
`Want et al.
`Haas .......................... 455/423
`Morris et al.
`Shuen
`Alhberg et al.
`Grube et al.
`Garrabrant et al.
`Vu
`Baldwin et al.
`Elgamal et al.
`Samadi et al.
`Pepe et al.
`Kapoor et al.
`Doviak et al.
`Hanif et al.
`Kobayashi et al.
`Spaur et al.
`Katiyar
`Ahuja
`Bittinger et al.
`Hamilton et al.
`Kralowetz et al.
`Demery et al.
`Shields
`Harrison et al.
`Cowan
`Gervais et al.
`Agrawal et al.
`Kuthyar et al. ............. 370/260
`Kalajan et al.
`Nessett et al.
`Coleman et al.
`Sturniolo et al.
`Garner et al. ............... 455/428
`Orsic
`Sturniolo et al.
`Renouard et al.
`Inoue et al.
`Inoue et al.
`Niblett et al. ............... 709/215
`Sturniolo et al.
`........... 455/432
`Hall et al.
`Rothwein et al. ........... 709/227
`Narisi et al. ................ 709/227
`Preston et al. .............. 370/349
`Machin et al. .............. 709/227
`Sharma
`............... 709/229
`Skopp et al.
`Hall, Jr. et al.
`
`OIBER PUBLICATIONS
`
`Teknique, Data Sheet, TransNet II Wireless Gateway, Wire(cid:173)
`less-A Wide Area Viewpoint, Shaumburg, IL, 3 pages.
`Teknique, Data Sheet, TransRMail, Schaumburg, IL, 2
`pages.
`Teknique, Data Sheet, TXS000 High Performance Commu(cid:173)
`nication Processor, Schaumburg, IL, 2 pages (1994).
`
`Teknique, Data Sheet, Optimized TCP/IP over Wireless,
`Schaumburg, IL, 5 pages.
`Teknique, Data Sheet, TXlO00 High Performance Commu(cid:173)
`nication Processor, Schaumburg, IL, 2 pages (1994).
`Teknique, Data Sheet, TX2000 High Performance Commu(cid:173)
`nication Processor, Schaumburg, IL, 2 pages.
`Teknique, Data Sheet, TransNet II Wireless Gateway Ser(cid:173)
`vices, Schaumburg, IL, 2 pages.
`IBM, Leading the Way for wireless data communication,
`ARTour, Research Triangle Park, NC 4 pages (Sep. 1995).
`M3i RadioLink, Overview, Management through instant
`interactive information, 7 pages (Jun. 1995).
`Web site information, WRQ AtGuard, www.atguard,com
`(copyright 1999).
`Press release, "WRQ Licenses AtGuard to Symantec and
`ASCII Network Technology" (copyright 1999).
`Datability Software Systems Inc., New York, NY "Proposal
`Presented to Digital Equipment Corporation Large System
`Group, Marlboro, Massachusetts" (Jul. 7, 1983).
`Datability Software Systems Inc., New York, NY, Con(cid:173)
`trol-PC, Information Management System, System Builder
`Manual, Draft Version (Apr. 1986).
`Datability Software Systems Inc., New York, NY, "Remote
`Access Facility, User's Guide" (copyright 1985, 1986, 1987,
`1988).
`NetMotion Wireless Product Documentation on CD; with 2
`page printout of contents.
`Kojo, M., Raatikainen, K., Alanko, T: Connecting Mobile
`Workstations to the Internet over a Digital Cellular Tele(cid:173)
`phone Network. University of Helsinki, Department of
`Computer Science, Series of Publications C, No.
`C-1994--39. Sep. 1994. Published also in Proceedings of the
`Mobidata Workshop, Rutgers University, NJ, Nov. 1994.
`Alanko, T., Kojo, M., Laamanen, H., Liljeberg, M., Moil(cid:173)
`anen, M., Raatikainen, K: Measured Performance of Data
`Transmission Over Cellular Telephone Networks. Computer
`Communications Review, 24(1994)5. Published also as
`Technical Report: University of Helsinki, Department of
`Computer Science, Series of Publications C, No.
`C-1994--53.
`Kojo, M., Alanko, T., Liljeberg, M., Raatikainen, K:
`Enhanced Communication Services for Mobile TCP/IP Net(cid:173)
`working. University of Helsinki, Department of Computer
`Science, Series of Publications C, No. C-1995-15. Apr.
`1995.
`Liljeberg, M., Alanko, T., Kojo, M., Laamanen, H., Raati(cid:173)
`kainen, K: Optimizing World-Wide Web for Weakly Con(cid:173)
`nected Mobile Workstations: An Indirect Approach. In Proc.
`2nd International Workshop on Services in Distributed and
`Networked Environments (SDNE'95) Jun. 5th-6th, 1995,
`Whistler, Canada.
`Laamanen, H: An Experiment of Dependability and Perfor(cid:173)
`mance of GSM Access to Fixed Data Network. University of
`Helsinki, Department of Computer Science, Series of Pub(cid:173)
`lications C, No. C-1995-41. Sep. 1995.
`Kiiskinen J., Kojo, M., Liljeberg, M., Raatikainen, K: Data
`Channel Service for Wireless Telephone Links. University
`of Helsinki, Department of Computer Science, Series of
`Publications C, No. C-1996-1. Jan. 1996. Published also in
`Proceedings of the 2nd International Mobile Computing
`Conference, Hsinchu, Taiwan, ROC, Mar. 25-27, 1996.
`
`2
`
`

`

`US 6,546,425 Bl
`Page 3
`
`Liljeberg, M., Helin, H., Kojo, M., Raatikainen, K:
`Enhanced Service for World-Wide Web in Mobile WAN
`Environment. University of Helsinki, Department of Com(cid:173)
`puter Science, Series of Publications C, No. C-1996-28.
`Apr. 1996. (Revised version published in Proceedings of the
`IEEE Global Internet 1996 Conference, London, England,
`Nov. 20---21, 1996.)
`Alanko T., Kojo M., Liljeberg M., Raatikainen K.: Mowgli:
`Improvements for Internet Applications Using Slow Wire(cid:173)
`less Links. Proc. 8th IEEE International Symposium on
`Personal, Indoor and Mobile Radio Communications, Hel(cid:173)
`sinki, Finland, Sep. 1997.
`Kojo M., Raatikainen K., Liljeberg M., Kiiskinen J., Alanko
`T.: An Efficient Transport Service for Slow Wireless Tele(cid:173)
`phone Links. IEEE Journal on Selected Areas in Commu(cid:173)
`nications, vol. 15, No. 7, Sep. 1997.
`"MOWGLI, Mobile Office Workstations using GSM Links,"
`University of Helsinki Dept. of Computer Science, Helsinki,
`Finland (Feb. 2000).
`Information Sciences Institute, "Transmission Control Pro(cid:173)
`tocol-DARPA Internet Program Protocol Specification,"
`Sep.
`1981;
`http://www.csl.sony.co.jp/cgi-bin/
`hyperrfc?rfc793.txt.
`Berners-Lee et al., "Hypertext Transfer Protocol-HTTP/
`1.0"; May 1996; http://www.cis.ohio-state.edu/htbin/rfc/
`rfc1945.html.
`Microsoft Support Online Knowledge Base Search Results,
`"DHCP (Dynamic Host Configuration Protocol) Basics,"
`Article ID: Q120829, (Revision Date Sep. 24, 1996).
`O'Reilly Online Catalog, "Windows NT TCP/IP Network
`Administration," Chapter 6, 25 pages( undated).
`WRQ White Paper, "TCP/IP: The Best Protocol for Remote
`Computing," 13 pages (Nov. 14, 1996).
`WRQ White Paper, "Reducing the Cost of PC Connectiv(cid:173)
`ity," 7 pages (Nov. 25, 1996).
`
`WRQ White Paper, "TCP Kernel Architecture-The Silent
`TCP/IP Issue," 4 pages (Nov. 14, 1996).
`WRQ White Paper, "How WRQ's TCP/IP Reduces Costs
`and Improves Reliability in Remote and Mobile Comput(cid:173)
`ing," 5 pages (Nov. 14, 1996).
`Zenel, Bruce, Thesis Proposal, "A Proxy Based Filtering
`Mechanism for The Mobile Environment," Dept. of Com(cid:173)
`puter Science, Columbia University, New York, NY, 52
`pages (undated).
`Badrinath, B.R., et al., "Handling Mobile Clients: A Case for
`Indirect Inteaction," Department of Computer Science, Rut(cid:173)
`gers University, 7 pages (Oct. 1993).
`Brown, Kevin, et al., "M-UDP: UDP for Mobile Cellular
`Networks," Department of Computer Science, University of
`South Carolina, 19 pages (Sep. 4, 1996).
`Brown, Kevin, et al., "M-TCP: TCP for Mobile Cellular
`Networks," Department of Computer Science, University of
`South Carolina, 25 pages (Jul. 29, 1997).
`Zenel, Bruce et al., "A General Purpose Proxy Filtering
`Mechanism Applied to the Mobile Environment," 12 pages
`(undated).
`Piscitello, D., Internet Draft, "Mobile Network Computing
`Protocol (MNCP)," 55 pages (Aug. 28, 1997).
`Bakre, Ajay et al., "M-RPC: A Remote Procedure Call
`Service for Mobile Clients," ACM Presents MobiCom '95,
`Proceedings of The First Annual International Conference
`on Mobile Computing and Networking, pp. 97-110 (Nov.
`13-15, 1995).
`Drams, R., Network Working Group, Request for Com(cid:173)
`ments memo, "Dynamic Host Configuration Protocol,"
`Bucknell University, 39 pages (Oct. 1993).
`
`* cited by examiner
`
`3
`
`

`

`--- -
`107a ~~/ ,--ii)))) ---,,,
`
`100
`
`',,',r-107k
`
`l
`-----
`.,~/,--))))))
`,· D
`
`I
`
`I
`
`O
`
`104k
`
`\
`\
`
`,
`
`\
`
`I
`I
`~~~~(
`_,
`i_ Mobile End
`( 1
`,
`,_ System
`' , ~ . , '
`• ' . 106k
`• .... -. _______ .
`
`•
`
`•
`
`•
`
`'-
`
`\
`\
`I
`\
`!
`i
`I
`~~~~(
`j
`i_ Mobile End
`,_ System ~ ( _,
`✓-/
`
`I
`
`/ D
`O
`
`104a
`
`\
`
`\
`
`I
`
`· \ ,
`
`\,
`
`• , . 1 06a
`- ✓-
`,,
`...
`• ..... __________ .-· •
`
`108
`
`Router
`
`Host
`
`l= r-,.....
`
`110
`
`112
`
`\ ~ Mobility Management System
`
`102
`
`-~ -
`Mobile End
`I
`System
`1091 __......L.J
`
`FIG. 1
`
`104m
`
`Mobile End
`System
`
`109m
`
`• • •
`
`d •
`r:JJ.
`•
`~
`~ .....
`~ = .....
`
`~
`:;
`~CIO
`N
`0
`0
`~
`
`rF.J. =-~
`~ ....
`'"""' 0 ....,
`
`~
`~ e
`
`Network 111
`
`104n
`
`Mobile End
`System
`
`~
`N
`
`rJ'J.
`_,.a-...
`(It
`,I;;..
`_,.a-...
`,I;;..
`N
`(It
`~
`i,-
`
`4
`
`

`

`104
`
`102
`
`Mobile End System (MES)
`
`236
`
`Network
`Applications
`
`Socket API
`
`Control, User Interface
`
`Network/Security
`Provider
`210
`Network File and
`Print Services
`
`Transport Driver lnterf ace (TOI)
`
`208
`
`206
`
`204
`
`212
`
`Mobile Interceptor 1 - - - - - - - -
`
`202
`
`TCP.UDP Transports
`
`FIG. 2
`
`238
`- - - - - - -
`--200•
`-N-et-wo-rk-ln-te-rf o-ce~Dr~iv-er-s "'i.(N~D:t:IS~}
`-, -Fix_ed_----En-d--=S:-ys7te_m_s -;;(F~ES::-r) 71
`I I
`Network lnterf ace Drivers ~~I~)_• ____ ~• I !~~~~the~ ~~~~o_rt__ _ J
`i
`Network
`\: 108
`7
`Applications
`200 _.,
`L - - - - -
`File/Print
`
`208'
`~•· 1
`
`1
`
`!. •
`
`Socket API
`
`Mobile Management System (MMS)
`232
`224
`230
`!Monitor I l Control, User Interface
`
`210'
`Network File and] jProxy Server
`Print Services
`
`Configuration
`Manager
`
`Transport Driver Interface (TDI)
`
`TCP, UDP Trans_eorls
`
`Windows NT
`User /Security
`Database
`
`228
`
`206'
`,
`204'
`202'
`
`220
`
`Address Translation - - -
`(Intermediate Driver)
`
`i
`i
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`1 LAN or WAN
`L ______ _ _____ _v
`
`d •
`r:JJ.
`•
`~
`~ ......
`
`~ = ......
`
`> "Cl :;
`
`~
`
`00
`N
`0
`
`8
`
`'JJ. =(cid:173)~
`
`~
`N
`0 ....,
`~
`N
`
`e
`rJ'l
`O'I
`11.
`,I;;..
`O'I
`~
`N
`(It
`
`~ .....
`
`110
`
`5
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 3 of 32
`
`US 6,546,425 Bl
`
`Call to TOI Via Sockets
`or directly is intercepted
`
`Mobile Interceptor packages
`TD\ cell in an RPC
`datagram and sends to
`Mobile Management Server
`
`250
`
`252
`
`Mobile Management Server
`unpackages RPC datagram
`
`254
`
`FIG. 2A
`
`Mobile Management Server
`provides requested service
`
`256
`
`Applications
`
`Configuration API
`
`I Socket AP\
`
`TDI
`
`i---208
`
`i - - - 206
`
`i - - - 204
`
`RPC Protocol Engine 240
`
`i - - - 212
`
`Internet Mobility
`(Interceptor Virtual Circuit)
`Protocol
`Engine 244
`
`FIG. 3
`
`6
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 4 of 32
`
`US 6,546,425 Bl
`
`RCV TOI CALL
`
`Post RPC call
`to IMP queue
`
`Delay for
`coalesce time
`
`Flush queue. coalesce the RPC __ 308
`coils into single f rogment
`and toward to Server
`
`END
`
`FIG. 3A
`
`7
`
`

`

`244'
`
`352
`
`Work Request 1 ~354
`
`Receive lnd'J
`
`1
`
`IMP
`.-; Reconstructs
`Fragments
`& Formulates
`Work
`Request
`
`I RPC Receive Request I
`
`356(3)
`
`• •
`•
`
`FIG. 3B
`
`358
`
`Global Queue
`
`Association Work
`Queue
`
`•
`•
`•
`
`356(1)
`
`356(2)
`
`d •
`r:JJ. •
`~
`~ ......
`~ = ......
`
`~ :;
`
`~CIO
`N
`0
`
`8
`
`'JJ. =(cid:173)~
`~ ....
`Ul
`0 ....,
`~
`N
`
`e
`rJ'J.
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`i,-
`
`8
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 6 of 32
`
`US 6,546,425 Bl
`
`362
`
`Determine Association
`> - - - - - - . i and Get Association ---(cid:173)
`Control Block
`
`372
`Start Association
`>------1~ Create New Association
`Control Block
`
`Stop Association
`Destroy Association
`Control Block
`
`376
`
`382
`
`386
`
`Shut Down
`Ping Association
`
`FIG. 4
`
`No
`
`Yes
`
`368
`
`Schedule Association
`to Run Again
`
`9
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 7 of 32
`
`US 6,546,425 Bl
`
`De-Queue
`Work Request
`
`390
`
`364
`
`I
`
`398
`
`Start
`Receiving
`
`402
`Issue TCP
`>--__.,. Connect 1 - - - - - - -1
`
`410
`
`Yes
`Set State To Association
`~ - - - . i Scheduled again
`
`FIG. 5 Process Association Work
`
`10
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 8 of 32
`
`US 6,546,425 Bl
`
`START
`
`/372
`
`allocate and association control block
`
`372A
`
`initialize system wide resources with defaults
`
`3728
`
`get configuration overrides
`with current configuration settings
`
`372C
`
`initialize flags
`
`372D
`
`initialize the association-specific work queue
`
`372E
`
`initialize association object hash table
`
`372F
`
`initialize the coalesce timer
`
`372G
`
`insert association control block into session table
`
`372H
`
`END
`
`FIG. 5A
`
`11
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 9 of 32
`
`US 6,546,425 Bl
`
`START
`
`376,
`
`mark the association as deleted to prevent any further
`processing of work that may be outstanding
`
`close all associated association objects including
`process, connection and address objects
`
`376A
`
`3768
`
`free all elements on work queue
`
`376C
`
`stop coalesce timer if running
`
`376D
`
`decrement association control block reference count
`
`N
`
`376F
`
`'--- 376E
`
`destroy association specific work queue
`destroy object hash table
`
`376G
`
`destroy coalesce timer
`remove association control block
`from association table
`free control block
`
`END
`
`FIG. 5B
`
`12
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 10 of 32
`
`US 6,546,425 Bl
`
`( Credit INT )
`=0
`,,
`mark association as "low mark pending" by setting the i--- 379A
`RPC_ LMPQ_SEND_ FLAG.
`
`,,
`
`discard all received datagrams
`
`r---3798
`
`11
`
`throttle all received stream events by
`refusing to accept the data
`
`i--379C
`
`I refuse all received connect events for passive connections
`
`1 I
`
`379D
`
`11
`
`END
`
`(
`
`)
`
`FIG. SC
`
`13
`
`

`

`RPC Receive Work Request
`Main Fragment
`-,
`
`502( 1)
`
`503
`
`Work
`
`pUserDota
`
`-
`
`Request I pNextF rag
`Header
`Receive l--- 504
`Overlay
`.i RPC 4-- 506( 1 )
`
`500
`
`502(2)
`
`Second J
`Fragment
`'1
`
`Third
`Fragment/
`pNextFrag .
`
`506(6)
`
`502(3)
`
`RPC 4 r
`
`506(4)
`
`I RPC 61
`~506(7)
`1 RPC 7
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`> "Cl :-;
`
`~
`
`00
`N
`0
`0
`~
`
`'JJ. =-~
`~ ....
`'"""'
`'"""' 0 ....,
`
`~
`N
`
`e
`rJ'J.
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`i,-
`
`RPC 2 -
`
`506(2)
`
`RPC 5~
`
`RPC 3
`
`506(3)
`
`FB1···
`
`506(5)
`
`506(8)
`
`FIG. 6
`
`14
`
`

`

`RPC Receive
`Work Request
`
`500
`
`506(1)
`
`Receive
`Overlay
`RPC 1
`
`RPC 2
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`• • •
`RPC N
`
`FIG. 7
`
`Priority N
`2
`1
`
`\
`
`\
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`Priority 0
`(Highest)
`Open Address
`Open Connection
`
`Execute Call
`
`510(1)
`
`510(2)
`
`51 O(N)
`
`Open Address Object
`Open Connection Object
`Associate Address
`Connect
`Stream Send
`Stream Rev
`Datagram Send
`Datagram Rev
`Setlnfo
`SetEvent
`CleorEvent
`Disconnect
`Disassociate Address
`Close Connection Object
`Close Address Object
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`t :;
`
`~CIO
`N
`0
`
`8
`
`'JJ. =(cid:173)~
`~ ....
`'"""' N
`0 ....,
`~
`N
`
`e
`rJ'J.
`_,.a-...
`(It
`,I;;..
`a-...
`~
`N
`(It
`~
`i,-
`
`15
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 13 of 32
`
`US 6,546,425 Bl
`
`/ 4 0 6
`
`queue=
`PRIORITY _HIGH
`
`Weight=queue
`Weight
`
`408
`
`410
`
`~ - - - - - - - ,
`
`412
`No
`
`395
`
`414
`
`418
`
`420
`
`No
`
`No
`
`Mark Queue Eligible
`To Run Again
`
`Queue--
`
`No
`
`Fig. 8
`Process Priority
`Dispatch Queues
`
`16
`
`

`

`Connect Event
`Receive Response
`Receive Datagram Event
`Disconnect Event
`
`High
`Priority
`
`~ ""' ~
`""' ~ ~ I Global Queue
`""'
`~
`""' .. ~ ~
`
`358'
`
`Priority 1
`
`Priority 2 Queue
`
`Priority N Queu
`
`510'(1)
`
`510'(2)
`
`51 O'(N)
`
`IMP Send Request
`
`IMP
`244
`
`FIG. 9
`Proxy Generated
`RPC Calls
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`~ :;
`
`~CIO
`N
`0
`
`8
`
`'JJ. =(cid:173)~
`~ ....
`'"""'
`,i;;..
`0 ....,
`~
`N
`
`e
`rJ'J.
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`i,-
`
`17
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 15 of 32
`
`US 6,546,425 Bl
`
`No
`
`604
`
`603A
`
`-Error-
`Out of resources
`
`Queue connect or send request and signal global event -
`
`return to calling application
`
`Dispatch connect or send request
`from IMP global request queue
`
`605A
`
`No
`
`Wait for application to
`queue work for
`connection. Go to step 625
`
`606A
`
`Go to step 615
`
`607A
`
`No Wait for peer address.
`>-----1~ Continue queuing work.
`Go to step 625
`
`608A
`Wait for security context.
`Continue queuing work.
`Go to step 625
`
`Internet Mobility Protocol
`Connection Decision Tree.
`FIG. 10A Connect and Send request logic
`
`18
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 16 of 32
`
`US 6,546,425 Bl
`
`State Pending
`
`6088
`
`609
`
`610
`
`Send IMP Sync Fromet--------------
`
`Start IMP retransmit timer
`
`611
`
`613
`
`Wait
`Go to
`step 625
`
`611A
`
`Yes
`
`Yes
`
`State Established
`
`614
`
`No
`
`616
`Wait
`Go to
`step 625
`
`No
`
`Yes
`
`Yes
`
`No
`
`Yes
`
`614A
`
`Abort Connection
`Go to step #999
`
`FIG. 10B
`
`19
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 17 of 32
`
`US 6,546,425 Bl
`
`B
`
`619
`Wait for
`Yes
`acknowledgement.
`, ;L - - - - - - - -1~
`Go to step 625
`
`620
`
`621
`
`Create IMP data frame
`
`Send IMP data frame
`
`No
`
`623
`Start IMP
`retransmit
`timer
`
`624
`
`Yes
`
`Yes
`
`625
`
`No
`Sleep waiting for more work.
`Return to global dispatcher
`
`FIG. 10C
`
`20
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 18 of 32
`
`US 6,546,425 Bl
`
`626
`
`Terminate Connection
`
`Queue request to global work queue
`and return to calling application
`
`626A
`
`627
`
`Dispatched terminate request from
`IMP process globol work queue
`
`628
`
`629
`">-A_b_o_rt_--...i Abort Connection
`Go to step f 999
`
`State Closing
`
`628A
`
`630
`
`631
`
`632A
`
`636
`
`637
`
`Send IMP Mortis Frame1---------------~
`
`State Mortis
`
`630A
`
`Start retransmit timer
`
`634
`
`No
`
`Wait
`Go to
`step 637
`
`State Post Mortem
`
`Release connection Resources
`
`No
`
`Sleep waiting for more work.
`Return to global dispatcher
`
`FIG. 11
`Terminate Connection request logic
`
`635A
`
`Abort Connection
`Go to step #999
`
`21
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 19 of 32
`
`US 6,546,425 Bl
`
`650
`
`651
`
`-Event(cid:173)
`Retransmit timer
`expired!
`
`No
`
`Any
`frames
`outstanding
`?
`
`Yes
`
`652
`
`Dismiss timer.
`
`654
`
`Has
`entire retransmit >--N_o __ - j~ Sleep for difference
`in time
`period
`expired?
`
`t - - - -~
`
`Yes
`
`6 5 5 ~
`Has
`Total retransmit
`period
`expired?
`
`Yes
`
`656A
`
`Yes
`
`State
`Dormant
`
`657
`
`658
`
`659
`
`No
`
`No
`
`Reprocess frame to remove
`any expired data
`
`Abort Connection
`Go to step #999
`
`6568
`
`Retransmit Frame
`
`retransmit timer
`
`660
`
`Fig. 12
`Retransmit Event Logic
`
`22
`
`

`

`506(1)-.__ I POU #1
`: Expiry 0
`
`I
`
`506(2)
`
`506(n)-......__
`
`POU #2
`Expiry=2 sec
`•
`•
`•
`POU #n
`Expiry x
`
`►I
`
`I Time To I
`I Time T1 I
`•
`•
`•
`jT2Time=T1 + 2.5sec I
`
`POU #1
`Expiry 0
`
`j I IMP Work Queue I
`
`PDU #2
`Expiry=2 sec
`•
`•
`PDU #n
`Expiry x
`
`I I
`
`I Expired at Time T 2 I
`r - - - - - - - - 7
`1 POU #2
`1
`I
`.
`Exp1ry=2 sec 1
`i
`
`L - - - - - - - - . J
`
`FIG. 12A
`
`I IMP Work Queue I
`- - - - - - - , ------------- - - •
`506(1)"
`... PDU #1
`Retry Count=O
`
`PDU #2
`... Retry Count= 1
`
`506(2)'-
`•
`•
`•
`POU #n
`506(n)-...._
`... Retry Count=x
`
`.... ....
`
`.... ,_
`
`IMP Frame Payload
`
`I
`
`: Ret~y Id #O
`:
`Size n
`
`FIG. 128
`
`1_
`w
`PDU # 1
`PDU #2
`PDU #n
`Retry Count=x • • Retry Count=1 Retry Count=O
`
`1
`
`1r
`
`500
`
`\
`
`:
`
`IMP
`Header
`: Sequence #x
`
`1
`
`d •
`r:JJ.
`•
`~
`~ ......
`......
`
`~ =
`
`~ :;
`
`~CIO
`N
`0
`
`8
`
`'JJ. =(cid:173)~
`~ ....
`
`N
`0
`0 ....,
`~
`N
`
`e rJ"]_
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`I■-
`
`23
`
`

`

`PDU #2
`Removed due
`to retry count
`going to zero 14
`
`1
`
`PDU #n
`Retry Count=x
`
`---
`PDU #1
`•• PDU #2
`Retry Count= 1 Retry Count=O
`---------
`IMP Frame Payload
`
`503
`
`~500
`IMP
`I
`: Header
`1 Sequence #x
`I i Retry Id #1
`i
`Size n
`
`\
`
`j
`~
`"
`PDU #1
`PDU #n
`I Retry Count=x • • Retry Count=O
`IMP Frame Payload
`
`IMP Header
`i
`: Sequence #x
`Id # 1
`: R t
`e ry
`I
`I Size n - PDU #2
`
`I
`
`500'
`
`I--- 503
`
`FIG. 12C
`Retransmission of IMP Frame
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`~ :;
`
`~CIO
`N
`0
`
`8
`
`'JJ. =(cid:173)~
`~ ....
`'"""' 0 ....,
`
`N
`
`~
`N
`
`e
`rJ'J.
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`i-,,.
`
`24
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 22 of 32
`
`US 6,546,425 Bl
`
`-Event(cid:173)
`ceive IMP fr
`nt from net
`
`670
`
`Pre-validate IMP Frame
`
`671
`
`672
`
`'>-N_o __ ----.1~ Discard
`frame
`
`Sleep
`
`Yes
`
`Yes
`
`No
`
`674
`
`677
`
`Place on connection receive queue
`
`Place on global receive queue
`
`675
`
`678
`
`Mark connection eligible to receive
`
`Place receive queue on global work queue
`
`676
`
`Place connection on global work queue
`
`679
`
`Signal global work event
`
`FIG. 13A
`Receive Event Logic
`
`25
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 23 of 32
`
`US 6,546,425 Bl
`
`Dispatch receive eligible
`from global work queue
`
`680
`
`Dequeue frame from receive queue ~ - - - - - - - - - -
`
`681
`
`683 \
`
`682
`
`No
`
`Sleep waiting
`for more work.
`Go to step #1012
`
`Validate IMP received frame
`
`685
`
`Yes
`
`Process Passive Connection
`request. Go to step #720
`
`688
`
`Parse IMP frame
`
`690
`
`691
`
`691A
`
`an IMP abort _Ye_s ____ Abort Connection
`Go to step #999
`
`Fig. 13B
`
`26
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 24 of 32
`
`US 6,546,425 Bl
`
`692
`
`Process acknowledgement info and release
`any outstanding send frames
`
`FIG. 13C
`
`693
`
`Post frame to security subsystem
`for possible decryption
`
`694
`
`Process any control data
`
`695
`
`698
`
`696
`
`Queue data to
`application layer
`
`697A
`
`Change state
`>---.....,. back to
`Established
`
`699
`
`Yes
`
`Indicate disconnect to
`application layer
`
`699A
`
`State Mortis
`
`700
`
`Send IMP Post Mortum F rome
`
`Yes
`
`700A
`
`State Post Mortum
`
`701
`
`Release connection resources
`
`No
`
`704 --.... Go to step 680
`
`702
`
`Sleep waiting for more work.
`Return to global work dispatcher
`
`27
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 25 of 32
`
`US 6,546,425 Bl
`
`721
`
`Abort Connection
`Call step #999
`
`No
`
`No
`
`724
`
`725
`
`Duplicate frame
`Discard
`
`Go to step 680 1 - - - - - J
`
`-Error(cid:173)
`> - - - - - - -4 - Out of resources
`
`727
`
`Abort connection request
`Call step #999
`
`728
`
`Go to step 680 1------J
`
`729
`
`FIG. 14A
`Passive Connection request logic
`
`726
`
`726A
`
`State Configure
`
`730
`
`Acquire security context
`
`731
`
`28
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 26 of 32
`
`US 6,546,425 Bl
`
`732
`
`Send IMP establish Frame
`
`State Established
`
`732A
`
`733
`
`Start retronsmitter
`
`734
`
`Wait
`For authentication process to
`conclude. Return to global dispatcher
`
`736
`
`Abort Connection
`~ - - Go to step #999
`
`737
`
`Indicate connection to
`listening application
`
`738
`
`Get configuration
`
`740
`
`Abort Connection
`>------1..i Go to step #999
`
`741
`
`Yes
`
`Sleep waiting for more work
`Return to global dispatcher
`
`FIG. 148
`
`29
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 27 of 32
`
`US 6,546,425 Bl
`
`999
`
`1000
`
`Abort Connection request
`
`Dispatched
`rt Connection req
`
`Yes
`1002 ~ - - - . J I . - - -~
`Save original state
`
`State Abort
`
`1002A
`
`1004
`
`Yes
`
`Indicate disconnection to
`listening application
`
`No
`
`State Post Mortem ..,.. ____ ___,
`
`1003A
`
`1005
`
`Release connection resources
`
`1007
`
`No
`
`Go to step f 1012
`
`FIG. 15A
`Abort Connection request logic
`
`30
`
`

`

`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 28 of 32
`
`US 6,546,425 Bl
`
`1009
`
`Yes
`
`Yes
`
`Yes
`
`No
`
`1011
`
`1010
`
`Send IMP Abort Frame
`
`Discard Frame
`
`1012
`
`Return to calling routine
`
`FIG. 158
`
`31
`
`

`

`Socket .
`servers
`
`xid . ping
`
`✓ 902
`
`linked list of server
`integer transaction ID number
`counter
`
`timeout
`
`time-out value that can be backed off
`
`s erver:
`next
`serverlD
`giaddr
`.
`ping
`
`e___904
`
`pointer to next server
`IP Address of a DHCP server
`B00TP Relay agent recently associated with this server
`c.f. socket ->ping
`
`new
`
`flag
`
`FIG. 16
`DHCP Listener Data Structures
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`~ :;
`
`~CIO
`N
`0
`
`8
`
`'JJ. =(cid:173)~
`~ ....
`
`N
`\0
`0 ....,
`
`~
`N
`
`e
`rJ'J.
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`i,-
`
`32
`
`

`

`8
`
`►I s.:0" ; " I
`
`802 _/'--------'
`Receive "Server" Packet
`
`/4 - )C I I
`
`806
`
`N
`
`N
`
`N
`
`.. ,
`
`804 _,,, ~
`
`Exit Signal
`
`cleanup
`
`Receive "Client" Packet
`
`Timeout
`
`Call PingCheck
`
`838
`
`Set socket->xid = random,
`Send DHCP Discover
`Set Timer to T
`
`N
`
`N
`
`814
`
`816
`
`Signal
`"Hard Roam"
`
`match
`
`822
`Add server to list.
`set server->"new"
`( unless first in list)
`
`Reset "new" flags
`tor all known server
`in list.
`
`818
`
`server- >ping=socket->ping
`
`820
`
`Set socket->xid = packet->xid
`++socket->ping
`
`Call PingCheck
`
`834
`
`Set Timer
`to R
`
`836
`
`Fig. 17
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`> "Cl :;
`
`~
`
`00
`N
`
`0 8
`
`'JJ. =(cid:173)~
`
`~
`~
`0
`0 ....,
`
`~
`N
`
`e
`rJ'J.
`O'I
`11.
`,I;;..
`O'I
`~
`N
`(It
`~
`I■-
`
`33
`
`

`

`Set SubnetRoam= TRUE
`J1-----t.-.i- Set Out Of Range= TRUE
`
`840
`
`842
`
`848
`Set ~
`SubnetRoam
`FALSE
`I
`
`852
`
`Set
`OutofRange
`FALSE
`I
`
`N
`
`N
`
`854
`
`N
`
`•
`
`FIG. 17A
`
`858
`
`Signal
`Subnet Roam
`
`862
`
`866
`
`Signal
`No Server
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`> "Cl :;
`
`~
`
`00
`N
`0
`0
`~
`
`'JJ. =-~
`~ ....
`'"""' 0 ....,
`
`~
`
`~
`N
`
`e
`rJ'J.
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`i,-
`
`34
`
`

`

`Enable
`
`OS lnterf ace Change Signal
`
`Listener Signal
`
`662
`
`876
`
`Zero list of known addresses L-- 650
`
`852 --..J Enable OS Interface
`Chanae Notification
`
`854 -..... I Call OS to get list of current
`addresses that use DHCP
`
`856 --...I
`
`Close listeners on all known
`addresses no longer in current list
`
`858 --...I Open listeners on all current but
`not known
`interfaces; add to
`known list.
`
`Close all Listeners
`
`860
`
`Disable OS
`lnterf oce Change
`I Notification
`
`882
`
`I
`
`Close listener
`
`866
`
`Call OS to Release and
`renew DHCP lease
`
`y
`
`868
`
`y
`
`t
`Signal DOR to registrants
`
`-H
`
`y
`
`DONE-Wait for Next Signal
`
`FIG. 18
`ROAMING CONTROL CENTER(cid:173)
`Mobile End System
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`~ :;
`
`~CIO
`N
`0
`0
`~
`
`'JJ. =(cid:173)~
`~ ....
`
`~
`N
`0 ....,
`~
`N
`
`e
`rJ'J.
`O'I
`1J.
`,I;;..
`O'I
`~
`N
`(It
`~
`I■-
`
`35
`
`

`

`US 6,546,425 Bl
`
`1
`METHOD AND APPARATUS FOR
`PROVIDING MOBILE AND OTHER
`INTERMITTENT CONNECTIVITY IN A
`COMPUTING ENVIRONMENT
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application claims priority from provisional appli(cid:173)
`cation No. 60/103,598 filed Oct. 9, 1998 entitled "Method
`and Apparatus For Providing Wireless Connectivity In A
`Computing Environment" (which provisional application is
`incorporated by reference herein in its entirety).
`
`FIELD OF THE INVENTION
`
`The present invention relates to connectivity between
`networked computing devices. More particularly, the
`present invention relates to methods and systems that trans(cid:173)
`parently address the characteristics of nomadic systems, and
`enable existing network applications to run reliably in the
`associated mobile environments. Still more particularly, the
`invention relates to techniques and systems for providing a
`continuous data stream connection between intermittently(cid:173)
`connected devices such as handheld data units and personal
`computing devices.
`
`BACKGROUND AND SUMMARY OF THE
`INVENTION
`
`Increasingly, companies are seeing rapid access to key
`information as the way to maintaining a competitive advan(cid:173)
`tage. To provide immediate access to this information,
`mobile and other intermittently-connected computing
`devices are quietly and swiftly becoming an essential part of
`corporate networks----especially with the proliferation of
`inexpensive laptops and hand-held computing devices.
`However, integrating these nomadic devices into existing
`network infrastructures has created a challenge for the
`information manager.
`Many problems in mobile networking parallel the diffi-
`culties in early local area networks (LANs) before the
`adoption of Ethernet. There are a variety of mobile protocols
`and int