(12) United States Patent
`Goldszmidt et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006195680Bl
`US 6,195,680 Bl
`Feb.27,2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) CLIENT-BASED DYNAMIC SWITCHING OF
`STREAMING SERVERS FOR
`FAULT-TOLERANCE AND LOAD
`BALANCING
`
`(75)
`
`Inventors: German Sergio Goldszmidt, Dobbs
`Ferry; Marc Hubert
`Willebeek-LeMair, Yorktown Heights,
`both of NY (US); Kenneth Sau-yee
`Hon, Mid-Levels (HK)
`
`(73) Assignee: International Business Machines
`Corporation, Armonk, NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/121,379
`
`(22) Filed:
`
`Jul. 23, 1998
`
`Int. Cl? ...................................................... G06F 13/00
`(51)
`(52) U.S. Cl. .............................................................. 709/203
`(58) Field of Search ........................ 364/DIG. 1, DIG. 2;
`709/200, 202, 203, 105, 208, 209, 210,
`217, 218, 219, 231; 714/4, 2, 22, 3, 6
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`................... 395/200
`12/1994 Attanasio et a!.
`5,371,852
`5,815,663 * 9/1998 Vomini ................................. 709/219
`
`OTHER PUBLICATIONS
`
`"Overview: Bamba" http://www.alphaworks.ibm.com, Aug.
`26, 1996, 4 pages.
`IBM eNetwork Dispatcher, http://www.software.ibm.com,
`May 1998, 17 pages.
`"RTP Payload Format for H.263 Video Streams" ftp://
`ds.internic.net/rfc/ Request for Comments:2190, C. Zhu,
`Intel Corp, Sep. 1997, 13 pages.
`The "Internet Television", Understanding the Browser
`Basics,
`http://w3.ag.uiuc.edu/AIM/Discovery/Net/www/
`television/television.html, Jun. 2, 1998, 2 pages.
`
`1.8 .
`
`K. Bannan, "Philips Magnavox:Philips Magnavox Web TV",
`http://www.zdnet.com/products/content/pcmg/1604/
`pcmg0123.html, PC Magazine, Feb. 18, 1997, 2 pages.
`K. Bannan, "Sony Electronics Inc.:Sony WebTV Internet
`Terminal", http://www.zdnet, com/products/content/pcmg/
`1604/pcmg0125.html, PC Magazine, Feb. 18, 1997,2 pages.
`
`(List continued on next page.)
`
`Primary Examiner-Robert B. Harrell
`(74) Attorney, Agent, or Firm-Wayne L. Ellenbogen
`
`(57)
`
`ABSTRACT
`
`A client-based system for the fault tolerant delivery of
`real-time or continuous data streams, such as real-time
`multimedia streams, e.g., live audio and video clips. Mul(cid:173)
`timedia servers are grouped into two or more sets, for
`example wherein a first set includes one or more primary
`servers using odd-numbered ports and a second set includes
`one or more secondary servers using even-numbered ports.
`The client requests a multimedia stream through a control
`server or gateway which routes requests to the multimedia
`servers; and the client receives the stream directly from a
`selected (primary) server. The client automatically detects
`load imbalances and/or failures (complete or partial) and
`dynamically switches to a secondary server in order to
`continue receiving the real-time multimedia stream with
`minimal disruption and while maintaining a balanced load
`across multiple servers in a distributed network environ(cid:173)
`ment. The determination can be made based on: the received
`bit or frame rate (for video); a bit rate or sample rate (for
`audio); monitoring a delivery rate or for packets arriving out
`of order: for example using packet numbering mechanisms
`available in TCP; sequence numbering or time stamp capa(cid:173)
`bilities of RTP (in combination with the User Datagram
`Protocol (UDP)). In any case, the determination could be
`based on the rate measurement or monitoring mechanism
`falling below (or exceeding) some threshold. Alternately, the
`primary server or the control server could send an explicit
`distress or switch signal to the client. An explicit signal can
`be used for example to switch clients in phases with minimal
`disruption.
`
`46 Claims, 9 Drawing Sheets
`
`Samsung-LG-HTC Ex. 1109 p. 1
`
`

`

`US 6,195,680 Bl
`Page 2
`
`01HER PUBLICATIONS
`
`"desktop conferencing & collaboration", http://www.wpi(cid:173)
`ne.com/, May 26, 1998 White Pine Software, Inc., 17 pages.
`"CU-SeeMe Reflector", http://www.e92plus.co.uk/refiec(cid:173)
`tor.htm, Enhanced CU-SeeMe, Feb. 3, 1998, 2 pages.
`Michael Sattler, "Internet TV With Cu-Seeme", Published
`by Sams Sep. 1995, Abstract from: http://www.amazon(cid:173)
`.com/exec/obidos/ISBN=1575210061/
`6156-9453266-197205, Feb. 3, 1998, 2 pages.
`Vivo Software, Inc-Home Page, http://www.vivo.com/,
`1997 Vivo Software, Inc, May 27, 1998, 4 pages.
`Download RealPlayer Plus, http://www.real.com/products/
`playerplus/index.html?src=download, Copyright (c) Real(cid:173)
`Networks,Inc. and/or its licensors, 1995-1998, 4 pages.
`InterVu:Home, http://www.intervu.com/, May 26,1998,
`InterVu, Inc, 3 pages.
`Video and Audio: Organization and Retrieval in the WWW,
`http://www.vosaic.com/corp/papers/wwwS.html, Z. Chen et
`al., 17 pages, Jul. 12, 1997.
`VOSAIC Corp.Home Page, http://www.vosaic.com/, Copy(cid:173)
`right (c) 1997-98 Vosaic LLC, 11 pages.
`StorNet Texas Home Page, http://storl.stornet.com/Wel(cid:173)
`come.html, Mar. 24, 1998, 5 pages.
`Marathon Products, http://www.marathontechnologies.com/
`products.htm, "Continuous Uptime for Windows NT Appli(cid:173)
`cations", Mar. 24, 1998, 2 pages.
`Software Fault Tolerance, http://www.marathontechnologi(cid:173)
`es.com/software.htm, Marathon's Endurance™ Technology
`& Software Fault Tolerance, Mar. 24, 1998, 5 pages.
`
`Stardust IP Multicast Initiative-Release, http://www.ip(cid:173)
`multicast.com/press/pr980407.hmtl, Television and Internet
`Multicasting Differences Clarified, Apr. 7, 1998, 3 pages.
`MBone(or IP Multicast Information Web, http://www.m(cid:173)
`bone.com/®1994, 1995, 1996, 1997 Vinay Kumar, 26 pages.
`D. M. Dias et al., "A Scalable and Highly Available Web
`Server", COMPCON '96, 8 pages.
`T. Brisco, "DNS Support for Load Balancing", Rutgers
`University Apr. 1995, Network Working Group Request for
`Comments: 1794, Category: Informational, 6 pages.
`P. Mockapetris, Domain Names-Implementation and
`Specification, lSI, Nov. 1987, Network Working Group
`Request for Comments: 1035, 52 pages.
`C. R. Attanasio et al., "A Virtual Multiprocessor Imple(cid:173)
`mented by an Encapsulated Cluster of Loosly Coupled
`Computers", IBM Research Report, Oct. 26, 1992, 2 cover
`pages and pp. 1-13.
`VDOStore-VDOLive Player.Free video streaming client,
`http://www.clubvdo.net/store/Products/VDOnetNDOL(cid:173)
`ive_player.asp, May 26, 1998, 5 pages.
`H. Schulzrinne et al., "Real Time Streaming Protocol
`(RTSP)", Network Working Group, Request for Comments:
`2326, Category: Standards Track, Apr. 1998, pp. 1-92.
`SG15 Plenary May 28, 1966, "Draft Recommendation
`H.323: Visual Telephone Systems and Equipment for Local
`Area Networks which Provide a Non-Guaranteed Quality of
`Service", International Telecommunication Union, 69 pages.
`
`* cited by examiner
`
`Samsung-LG-HTC Ex. 1109 p. 2
`
`

`

`U.S. Patent
`
`Feb.27,2001
`
`Sheet 1 of 9
`
`US 6,195,680 Bl
`
`1.8~
`
`Client
`Agent
`
`1 .1
`
`-------------------1
`I
`I
`'I
`I
`I
`I
`I
`
`Control Server
`
`1. 7
`
`Server Architecture
`
`1.4~=++--
`
`1.92~~~
`
`1.5
`
`1.9~
`
`Cluster
`
`Fig.1a
`
`1 91 r·
`
`1 94
`
`r·
`
`1.6
`
`1 96 r·
`
`Client ID
`
`Primary ID
`
`Secondary I D
`
`Fig. 1 b
`
`Samsung-LG-HTC Ex. 1109 p. 3
`
`

`

`U.S. Patent
`
`Feb.27,2001
`
`Sheet 2 of 9
`
`US 6,195,680 Bl
`
`2.8
`
`Fig. 2(a)
`
`Fig. 2(b)
`
`Fig. 2(c)
`
`Samsung-LG-HTC Ex. 1109 p. 4
`
`

`

`U.S. Patent
`
`Feb.27,2001
`
`Sheet 3 of 9
`
`US 6,195,680 Bl
`
`3.8
`
`Fig. 3(a)
`
`Fig. 3(b)
`
`Fig. 3(c)
`
`Samsung-LG-HTC Ex. 1109 p. 5
`
`

`

`350'
`
`Client
`
`r--354
`
`Browser
`
`353 -"
`NSP Interface
`--- ---------------------1
`ks-355
`
`V Decode
`
`Video
`
`Video
`Render
`
`Server
`
`320'
`
`r321
`HTTP
`Server
`
`~
`,It
`
`~
`11t
`
`File
`Server
`
`j
`
`...l
`
`,...
`"""
`
`.......
`
`.........
`...,...,
`
`........
`
`Network
`Interface
`
`Network
`Interface
`
`Split~
`
`322
`
`HTTP
`
`j
`
`Audio
`Decode
`
`-~
`
`Audio
`Render
`
`Plug-in
`352~----------------------
`
`Fig. 3d
`
`d •
`\Jl
`•
`~
`~ ......
`~ = ......
`
`"'!"j
`~
`?'
`N
`~-..J
`
`N c c
`'"""'
`
`'JJ. =(cid:173)~
`~ .....
`
`~
`0 ......,
`'0
`
`e
`rJ'l
`-..a-..
`1--"
`\0
`(It
`0..,
`00
`Q
`~
`1--"
`
`Samsung-LG-HTC Ex. 1109 p. 6
`
`

`

`U.S. Patent
`
`Feb.27,2001
`
`Sheet 5 of 9
`
`US 6,195,680 Bl
`
`Client agent sends a request
`message to the control server for
`the multimedia stream.
`
`The control server determines which
`set of streaming servers the client
`agent should connect to.
`
`4.1
`
`4.2
`
`NO
`
`4.5
`
`The control server
`selects a streaming server
`among all that are using
`even-numbered ports based
`on some load-balancing
`heuristics.
`
`The control server
`selects a streaming server
`among all that are using
`odd-numbered ports based
`on some load-balancing
`heuristics.
`
`The selected streaming server starts
`to deliver the real-time multimedia
`data to the client agent.
`
`4.6
`
`Fig. 4
`
`Samsung-LG-HTC Ex. 1109 p. 7
`
`

`

`U.S. Patent
`
`Feb.27,2001
`
`Sheet 6 of 9
`
`US 6,195,680 Bl
`
`The client agent detects that the
`streaming server fails.
`
`The client agent request the control
`server to switch it to an alternate server
`
`The control server uses the primary
`and alternate entries from the client
`agent to determine its alternate set
`of streaming server.
`
`5.1
`
`5.2
`
`5.3
`
`NO
`
`5.5
`
`5.6
`
`The control server selects a
`streaming server among all that are
`using even-numbered ports based
`on some load-balancing heuristics.
`
`The control server selects a
`streaming server among all
`that are using odd-numbered
`ports based on some
`load-balancing heuristics.
`
`The selected streaming server starts to
`deliver the real-time multimedia data to the
`client agent, it now becomes the primary
`streaming server.
`
`5.7
`
`Fig. 5
`
`Samsung-LG-HTC Ex. 1109 p. 8
`
`

`

`U.S. Patent
`
`Feb.27,2001
`
`Sheet 7 of 9
`
`US 6,195,680 Bl
`
`640
`
`641
`
`642
`
`Controller
`
`Dispatcher
`
`656
`Primary
`
`@
`•
`•
`•
`@
`Clients
`L-~-
`620
`
`•
`•
`•
`@'
`Sources :
`L-----
`\__ 630
`
`I
`
`•
`•
`•
`
`Reflectors
`
`L_ __ \ __ _
`
`""---- 610
`
`Fig. 6
`
`Samsung-LG-HTC Ex. 1109 p. 9
`
`

`

`730
`
`735
`
`Buffers
`~
`0 0 ... o---s-112
`DO···
`•
`•
`•
`
`>-712
`
`)/
`
`Reflector
`
`__., / ~ 14~
`
`720
`
`Client Station
`~~o~ .--I U-n-pa_c___,k II D ecom press I ~----.
`
`/
`
`I Unpack II Decompress!
`
`Fig. 7
`
`d •
`\Jl
`•
`~
`~ ......
`~ = ......
`
`"'!"j
`~
`?'
`N
`~-..J
`
`N c c
`'"""'
`
`'JJ. =-~
`~ .....
`00
`0 ......,
`'0
`
`e
`rJ'l
`-..a-..
`1--"
`\0
`(It
`0..,
`00
`Q
`~
`1--"
`
`Samsung-LG-HTC Ex. 1109 p. 10
`
`

`

`U.S. Patent
`
`Feb.27,2001
`
`Sheet 9 of 9
`
`US 6,195,680 Bl
`
`u -Q)
`~ -s::::
`
`s::::
`C'O
`
`' -
`0 __.
`(..)
`Q)
`'+=
`Q)
`0::::
`
`Q)
`(.)
`' -
`::J
`0
`(f)
`
`__.
`c
`Q)
`
`()
`
`0
`C'0 co
`
`-Q)
`Q) -s::::
`
`s::::
`
`~
`
`CJ)
`
`co
`~
`Q)
`'-
`u..
`
`co .
`C)
`u.
`
`-Q)
`~ -s::::
`
`s::::
`C'O
`
`0 ...--
`co
`
`0
`N co
`
`Samsung-LG-HTC Ex. 1109 p. 11
`
`

`

`US 6,195,680 Bl
`
`1
`CLIENT-BASED DYNAMIC SWITCHING OF
`STREAMING SERVERS FOR
`FAULT-TOLERANCE AND LOAD
`BALANCING
`
`FIELD OF THE INVENTION
`This invention relates generally to providing fault toler(cid:173)
`ance and load balancing for real-time data streaming. More
`particularly, it relates to a client-based dynamic server
`switching method for use in a distributed system including
`multiple servers that are simultaneously transmitting one or
`more real-time multimedia streams.
`
`BACKGROUND
`The demand for real-time multimedia streaming is
`steadily increasing. In order to increase the scale of network
`broadcast using real-time multimedia streaming, multiple
`servers can be used to provide the same multimedia stream
`to a large number of clients. Clients are directed to one of a
`multiplicity of servers to obtain the multimedia stream in 20
`real-time.
`One method known in the art that seeks to increase the
`processing capacity at hot sites on the Internet is to create a
`cluster of computing nodes (also called a multi-node cluster)
`to handle the load. The Internet refers to the collection of 25
`networks and gateways that use the Transmission Control
`Protocol/Internet Protocol (TCP liP) suite of protocols. TCP I
`IP is a well known protocol that was developed by the
`Department of Defense for communications between com(cid:173)
`puters (see e.g., D. E. Comer, "Internetworking with TCP/IP,
`Principals, Protocols and Architecture,"Prentice Hall, which
`is hereby incorporated by reference herein in its entirety).
`The multi-node cluster is (encapsulated) made to appear as
`one entity to clients, so that the added capacity provided by
`the multi-node cluster is transparent to clients. Client
`requests are distributed among nodes in the multi-node
`cluster. Many load balancing techniques are known in the
`art; see for example, Dias et al., "A Scalable and Highly
`Available Web Server", Proc. 41st IEEE Computer Society
`Intl. Conf. (COMPCON) 1996, Technologies for the Infor(cid:173)
`mation Superhighway, pp. 85-92, February 1996; see also
`U.S. Pat. No. 5,371,852, issued Dec. 6, 1994 to Attanasio et
`al., entitled "Method and Apparatus for Making a Cluster of
`Computers Appear as a Single Host."
`Research and development has also been increasing in 45
`both the areas of audio/video streaming and video confer(cid:173)
`encing. Video conferencing differs from audio and video
`streaming in that the communication is bi-directional and
`end-to-end delays must be very low ( <200 ms) for interac(cid:173)
`tive communication. In fact, video conferencing standards 50
`are quite mature and have emerged from both the Interna(cid:173)
`tional Telecommunication Union (ITU), in the form of the
`H.3xx standards; and the Internet Engineering Task Force
`(IETF) in conjunction with the multicast backbone
`(MBONE). In general, the two camps use the same audio 55
`and video compression standards (defined by the ITU), but
`differ in their networking protocol specifications.
`Audio/video streaming differs technically from its video
`conferencing counterpart in that it can afford greater flex(cid:173)
`ibility in end-to-end delays when being transmitted across a 60
`network, and in the fact that stored content may be manipu(cid:173)
`lated off-line with additional processing. These begin to
`merge when one considers live audio and video streaming
`applications (e.g., Internet, radio, and TV). The most rel(cid:173)
`evant of the ITU standards is H.323, which defines audio/ 65
`visual services over LANs for which quality of service
`cannot be guaranteed (see e.g., "Draft Recommendation
`
`2
`H.323: Visual Telephone Systems and Equipment for Local
`Area Networks Which Provide A Non-Guaranteed Quality
`of Service," (May 28, 1996), which is hereby incorporated
`herein by reference in its entirety). This standard specifies a
`5 variety of audio and video coders and decoders (CODECs)
`as well as signaling protocols to negotiate capabilities and
`setup and manage connections. The underlying transport
`specified is the Real-time Transport Protocol (RTP). This
`protocol, defined by the IETF, is intended to provide a means
`10 of transporting real-time streams over Internet Protocol (IP)
`networks. A new protocol, Real Time Streaming Protocol
`(RTSP), more directly addresses the issues of delivering and
`managing multimedia streams, (see e.g., "Real Time Stream(cid:173)
`ing Protocol (RTSP)" IETF Request for Comments: 2326
`15 (April 1998), which is hereby incorporated herein by refer(cid:173)
`ence in its entirety). Clearly, this area is still evolving as new
`protocols are being defined and refined to satisfy a wide
`range of emerging networked multimedia applications.
`Streaming technology can be used to deliver live audio
`and video data, where the clips arrive in streams so that users
`can begin to view or hear the clip before the download is
`complete. Conventional Internet traffic is short-lived, with a
`duration ranging from milliseconds to seconds, and bursty.
`In contrast, real-time multimedia streaming is lengthy, with
`a duration ranging from minutes to even hours, with low
`continuous bandwidth requirements. Server and/or network
`failures will terminate the real-time streaming process, and
`the stream from a given server will be interrupted for a
`particular session. This interruption may, in many cases,
`30 only be detected at the client. Thus, a need exists for a
`client-based means to automatically switch to an alternate
`server in order to continue receiving a multimedia stream in
`an uninterrupted fashion in the event of a service
`degradation, load imbalance, or failure. The present inven-
`35 tion addresses such a need.
`One known method in the art for increasing scalability for
`real-time multimedia streaming is through the use of
`so-called "reflector" technology. The reflector technology is
`used in applications-such as IBM's BAMBA™, Vosaic's
`40 MEDlASERVERTM and White Pine Software's
`CU-SeeMe™-to provide real-time audio and video stream(cid:173)
`ing over the Internet. Reflectors are servers that manage the
`distribution of audio and video streams to their receivers.
`They can be cascaded and scaled to handle increased
`demand for a broadcast. Multimedia streams are replicated
`at each reflector and delivered to multiple receivers. By
`simply adding more reflectors, a broadcast is capable of
`supporting large numbers of clients.
`A key problem with the basic reflector technology is that
`the resulting workload across reflectors is poorly balanced
`and network bandwidth can be wasted. For example, some
`reflectors can have a large number of clients simultaneously
`connecting to it while others are serving only a few clients.
`This causes the workload across reflectors to be highly
`unbalanced and can cause performance degradation due to
`server and/or network overloads. Another problem with the
`basic reflector approach, is that in the event that a reflector
`(server) fails or is overloaded, there is no automatic mecha(cid:173)
`nism for redirecting a client to another server where they
`will continue receiving the multimedia stream. The present
`invention addresses these problems.
`
`SUMMARY
`
`Accordingly, it is an object of this invention to provide an
`improved client-based system for the fault-tolerant delivery
`of real-time or continuous data streams. In one embodiment,
`
`Samsung-LG-HTC Ex. 1109 p. 12
`
`

`

`US 6,195,680 Bl
`
`4
`FIGS. 2(a), 2(b), and 2(c) depict an example in block
`diagram form of a client agent requesting a multimedia
`stream from the streaming servers;
`FIGS. 3(a), 3(b), and 3(c) depict an example in block
`5 diagram form of the dynamic server switching process for
`the client agent when the primary server for the client agent
`fails;
`FIG. 3d depicts a more detailed example of the client(cid:173)
`server architecture of FIGS. 3(a)-(c), adaptable to the
`10 present invention;
`FIG. 4 depicts an example of a method having features of
`the present invention for streaming continuous real-time
`MM data to a client;
`FIG. 5 depicts an example of a method having features of
`the present invention for switching clients among multiple
`servers if a streaming server becomes overloaded or fails;
`FIG. 6 depicts another example of an architecture having
`features of the present invention;
`FIG. 7 depicts a more detailed example of the source,
`client and reflector depicted in FIG. 6; and
`FIG. 8 depicts an example of a hierarchical reflector
`configuration.
`
`DETAILED DESCRIPTION
`
`3
`real-time multimedia streams, e.g., live audio and video
`clips, are delivered in streams so that users can begin to view
`or hear the clip before the download is complete. The
`real-time multimedia streams can be lengthy, with durations
`ranging from minutes to even hours, with low continuous
`bandwidth requirements. According to the present invention,
`a receiver (also called a client) automatically detects load
`imbalances and/or failures (complete or partial) and dynami(cid:173)
`cally switches to an alternate server in order to continue
`receiving the real-time multimedia stream with minimal
`disruption.
`The present invention includes features for automatically
`and gracefully switching clients among multiple servers in
`the event that a server becomes overloaded or fails. A
`preferred embodiment addresses the case where clients are 15
`receiving a continuous multimedia stream and the switching
`must be transparent to the client and maintain uninterrupted
`playback of the multimedia streams. When a server fails, its
`respective client agents detect the failure and automatically
`switch to alternate servers that continue to provide the client 20
`agents with the real-time multimedia streams.
`The present invention also includes features for gracefully
`switching client agents to alternate servers in the case of a
`server failure or overload while maintaining a balanced load
`across multiple servers in a distributed network environ- 25
`ment.
`An example of a system having features of the present
`invention includes: a control server; two or more streaming
`servers, and a plurality of client agents. The control server
`is preferably a scalable server that is capable of handling a
`requests from a large number of incoming client agents and
`redirecting them to the streaming servers that are providing
`the multimedia data. The control server assigns different
`identifiers to the streaming servers for delivering the mul-
`timedia data, and uses these identifiers to group these
`streaming servers into two or more different sets. The
`streaming servers are used to deliver the real-time multime(cid:173)
`dia streams to the client agents. To receive a multimedia
`stream, client agents are given an identifier to connect to a
`server in one of the sets.
`Each client agent receives the multimedia stream from a
`streaming server, performs the appropriate processing (e.g.,
`decompression, scaling) on the stream and renders the
`multimedia output. Each client agent can be provided with 45
`a primary server identifier as well as a secondary server set
`identifier. The primary entry characterizes the primary
`streaming server in the set of servers the client agent is
`connecting to. The secondary entry characterizes the set
`containing an alternate server for the client agent. When a 50
`client detects a failure or overload, the client sends a switch
`request to the control server which then selects a server in
`the secondary set and redirects the client agents of the
`primary server to the selected alternate server. Thus, the
`client agents can continue to receive the multimedia streams 55
`with minimal or no interruption.
`
`30
`
`35
`
`40
`
`FIG. 1a illustrates an example of an environment includ-
`ing a server architecture 1. 7 and a client agent 1.8 having
`features of the present invention. The server architecture 1.8
`includes a control server 1.1 and at least two sets (1.5, 1.6
`) (also called clusters) of streaming servers (1.2, 1.3). Each
`set of streaming servers includes at least one streaming
`server (1.2, 1.3), each having a number of ports (1.92, 1.93).
`In one embodiment, the streaming servers (1.2, 1.3) are
`assigned to one of the sets (1.5, 1.6) based on a simple
`arithmetic test. For instance, the assignments may be based
`on connection port numbers, e.g., all streaming servers using
`even-numbered ports 1.92 are assigned to one set, and all
`streaming servers (1.2, 1.3) using odd-numbered ports 1.93
`are assigned to another set. The server set assignments could
`further include considerations including one or more of:
`size; capacity; location (locality/affinity); and network
`connectivity, so that a good balance of server availability can
`be maintained in the two sets. One method to achieve this is
`for the control server 1.1 to assign any new streaming server
`to the currently smaller set. Servers in the system are
`preferably divided into two disjoint non-empty sets-a set
`which is serving stream data through the odd-numbered port
`and another set which is serving stream data through the
`even-numbered port. Both of these sets (1.5, 1.6) contain at
`least one server (1.2, 1.3). The two sets of servers are
`preferably mutually exclusive, meaning that no servers in
`the system can be in these two groups at the same time.
`Those skilled in the art will appreciate that many alter(cid:173)
`natives are available. The control server 1.1 could be a
`gateway through which client requests must pass and which
`includes a routing function to distribute client requests
`among servers in the cluster. For example, a system adapt(cid:173)
`able to the present invention that provides load balancing in
`60 an encapsulated cluster of nodes is described in U.S. Pat. No.
`5,371,852, issued Dec. 6, 1994, entitled "Method and Appa(cid:173)
`ratus for Making a Cluster of Computers Appear as a Single
`Host", by Attanasio et al ('852 patent). The present invention
`has a common assignee with this U.S. patent, which is
`65 hereby incorporated by reference in its entirety. Here, only
`the address of a Transmission Control Protocol (TCP) router
`(control server 1.1) is given out to clients 1.8; the TCP router
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These, and further characteristics and features of the
`invention, will be more apparent from the following detailed
`description of a preferred embodiment and the appended
`drawings in which:
`FIG. 1a depicts an example in block diagram form of an
`environment having features of the present invention;
`FIG. 1b depicts an example of a data structure which can
`be used to record the relationship between a client and the
`streaming servers depicted in FIG. 1a;
`
`Samsung-LG-HTC Ex. 1109 p. 13
`
`

`

`US 6,195,680 Bl
`
`5
`distributes incoming requests among the nodes (streaming
`servers 1.2, 1.3) in the cluster, either in a round-robin
`manner, or based on the load on the nodes. In the '852
`patent, a Virtual Encapsulated Cluster routes TCP informa(cid:173)
`tion that crosses the boundary of a computer cluster. The 5
`information is in the form of port type messages. Incoming
`messages are routed and the servers respond so that each
`cluster appears as a single computer image to the external
`host. A cluster of servers with a single TCP-router node is
`divided into a number of virtual clusters (virtual encapsu- 10
`lated clusters). Each virtual encapsulated cluster appears as
`a single host to hosts on the network which are outside the
`cluster. The messages are routed to members of each virtual
`encapsulated cluster in a way that keeps the load balanced
`among the set of cluster nodes. The TCP router can also act 15
`as a proxy, where the requests are sent to a selected node,
`and the responses go back to the TCP router and then to the
`client. In a preferred mode of operation, called forwarding
`mode, client requests are sent to a selected node, and the
`responses are sent back to the client directly from the 20
`selected node, bypassing the router.
`Referring again to FIG. 1a, as is conventional, the client
`1.8 can be directly connected to the control server 1.1 or
`over a network (not shown) such as a cable network,
`telephone network, local area network (LAN), an intranet, or
`the Internet (or some combination of these). The client agent
`1.8 (also called simply client), can be any conventional
`computer or processor-based machine with a processor,
`memory and operating system and application software and
`networking (hardware and software) to communicate
`requests and receive data streams from a streaming server.
`The control server 1.1 redirects incoming client agent 1.8
`requests to the streaming servers (1.2, 1.3), preferably while
`monitoring the workload of the streaming server. The con(cid:173)
`trol server is preferably a scalable server that is capable of
`handling a large number of incoming client agent requests
`and redirecting them to the streaming servers that are
`providing the multimedia data. The control server assigns
`different identifiers to the streaming servers for delivering
`the multimedia data, and uses these identifiers to group the
`streaming servers into two or more different sets (1.5, 1.6).
`By way of example only, one set 1.5 of streaming servers 1.2
`is delivering multimedia streams through even-numbered
`ports 1.92 and another set 1.6 of streaming servers 1.3 is
`delivering the multimedia streams through odd-numbered
`ports 1.93. Port-based routing of TCP connections is well
`known in the art (see for example the aforementioned '852
`patent).
`As is also conventional, communication channels 1.4
`exist between the control server 1.1 and the streaming
`servers (1.2, 1.3), allowing the control server to preferably
`monitor the workload of the streaming servers while redi(cid:173)
`recting incoming client agent 1.8 requests to them.
`Each instance of the streaming process begins with a 55
`client agent 1.8 connecting to the control server 1.1 request(cid:173)
`ing the multimedia stream. The control server then assigns
`and redirects the client to one of the streaming servers in
`either of the two groups (1.5, 1.6). The assignment can be
`based on a conventional round-robin approach or based on 60
`some load-balancing heuristics. For example, the server 1.1
`can redirect the client 1.8 to a streaming server based on a
`weighted round-robin approach, or to a streaming server
`having a lowest utilization rate.
`An example of a system for weighted TCP routing is 65
`described in co-pending U.S. patent application Ser. No.
`08/701,939, filed Aug. 23, 1996, now U.S. Pat. No. 5,918,
`
`6
`017, entitled "Weighted TCP Routing to Service Nodes in a
`Virtual Encapsulated Cluster" by C. Attanasio, G. Hunt, G.
`Goldszmidt, and S. Smith (IBM Docket No. Y0996167),
`now U.S. Pat. No. 5,918,017. The present invention has a
`common assignee with this co-pending patent application,
`which is hereby incorporated herein by reference in its
`entirety.
`An example of a Fault Tolerant Recoverable TCP/IP
`Connection Router (FTR-CR) and methods of connecting at
`least two FTR-CRs to multiple systems, where the FTR-CRs
`have synchronized internal tables and are capable of switch-
`ing between active and standby states is described in
`co-pending U.S. patent application Ser. No. 08/929,409,
`entitled "FAULT TOLERANT RECOVERABLE TCP/IP
`CONNECTION ROUTER," by Baskey et al., filed Sept. 15,
`1997, (IBM Docket No. Y0997232). The present invention
`has a common assignee with this co-pending patent
`application, which is hereby incorporated herein by refer(cid:173)
`ence in its entirety. A recoverable TCP liP Connection Router
`is a virtual encapsulated cluster which has two TCP-router
`nodes, a primary and a backup. The server cluster is aug(cid:173)
`mented with a recovery manager which causes the backup
`TCP-router to become active if the primary fails. The
`connection state at the time of failure can be reconstructed
`by (or alternatively known at) the backup router so that zero
`25 or a minimum number of client connections will be lost due
`to failure of the TCP-router node. The configuration/
`management information of the virtual encapsulated cluster
`is also replicated (or constructed) at the backup. Finally, the
`start up protocol of the TCP-router node is changed so that
`30 recovery of the primary router will not cause a failure in a
`backup that has taken over for it.
`An example of an affinity-based router and method for
`routing and load balancing in an encapsulated cluster of
`server nodes is described in co-pending U.S. patent appli-
`35 cation Ser. No. 08/947,361, filed Oct. 8, 1997, entitled
`"Affinity-based Router and Routing Method," by Dias et al.,
`(IBM Docket No. Y0996265). The present invention has a
`common assignee with this co-pending patent application,
`which is hereby incorporated herein by reference in its
`40 entirety. The affinity-based system includes a multi-node
`server, wherein any of the server nodes can handle a client
`request, but wherein clients have affinity to one or more of
`the server nodes that are preferred to handle a client request.
`Such affinity is due to state at the servers either due to
`45 previous routing requests, or data affinity at the server. At the
`multi-node server, a node may be designated as a TCP
`router. The address of the TCP router is given out to clients,
`and client requests are sent thereto. The TCP router selects
`one of the nodes in the multi-node server to process the
`50 client request and routes the request to this server; in
`addition, the TCP router maintains affinity tables, containing
`affinity records, indicating which node a client was routed to.
`In processing the client request, the server nodes may
`determine that another node is better suited to handle the
`client request, and may reset a corresponding TCP router
`affinity table entry. The server nod