`
`
`
`
`UNIFIED PATENTS
`
`EXHIBIT 1013
`
`Unfied Patents Exhibit 1013
`Pg. 1
`
`

`

`“Data In Your Face”: Push Technology in Perspective*
`
`Michael Franklin
`
`University of Maryland
`franklin @cs.umd.edu
`
`Stan Zdonik
`
`Brown University
`sbz@cs.brown.edu
`
`1
`
`Introduction
`
`Push technology stems from a very simple idea. Rather than requir-
`ing users to explicitly request (i,e., “pull”) the information that they
`need, data can be sent to users without having them specifically ask
`for it. The advantages of push are straightforward. The traditional
`pull approach requires that users know a priori where and when to
`look for data or that they spend an inordinate amount oftime polling
`known sites for updates and/or hunting on the network for relevant
`sites. Push relieves the user of these burdens. The problems of push
`are also fairly obvious, Push transfers control from the users to the
`data providers, raising the potential that users receive irrelevant data
`while not receivingthe information they need. These potential prob-
`lems can arise due to issues ranging from poor prediction of user
`interests to outright abuse of the mechanism, such as “spamming”.
`The “in-your-face" nature of push technology is the root of both its
`potential benefits and disadvantages.
`Push technology has been around in various forms for as long
`as people have been communicating. Examples range from news-
`papers, to telephones,
`to radio and television,
`to E-mail. Early
`work on using Computer networks for pushing data was performed
`in the 1980’s. The Boston Community Information System at
`MIT [Gift90], Teletext systems for distributing data over broad—
`cast media [Amma85, Wong88], and the Datacycle database ma—
`chine [Herm87], are all examples of systems that incorporated some
`form of push technology. Recently, however, the combination of
`push technology with the Internet and Web (sometimes referred to
`as Webcasting) has generated a ground swell of excitement, com—
`mercial activity, and controversy.
`
`1.] The Push Phenomenon
`
`In February I996. PointCast made its client software available for
`free downloading over the Internet. setting oil a wave ofinterest in
`push technology. The idea was appealing: rather than using your
`idle desktop machine as a display ground for flying toasters, Point-
`Cast would turn it into an active information terminal that would dis-
`
`‘ This work has been partially supported by Rome Labs agreement nume
`her F30602-97-2—OZ4] under DARPA nrder‘numherFO78, by the NSF under
`grant IRI—9501353, and by research grants from Intel and NEC
`
`Permission to make digital or hard copies of all or part oi this work lor
`personal or classroom use In granted without lee provided that
`copies are not made or distributed lor profit or commercial advan—
`tage and that copies bear this notice and the tall citation on the first page.
`To copy otherwiu, to republish, to post on server: or to
`redistribute to lists, require: prior apeciiic permiuion and/or a loo.
`SIGMOD '98 Scuttle. WA, USA
`9 1998 ACM 0-89791-995-5/98/006..$5.00
`
`play headlines, weather forecasts, stock prices, sports scores, etc,
`with the appearance of having real-time updates. By specifying a
`profile, users could indicate their interests to the system, and the dis—
`play would bc tailored to these interests.
`For anyone who tried the software, the reaction was immediate;
`this represented a paradigm shift in the way one could think about
`using the Internet as an information delivery tool. Push technology
`on the lntemet represented a new and untapped medium. The com-
`putertrade press became inundated with articles aboutpush technol—
`ogy and dozens of companies touting push—based solutions arrived
`on the scene. A new jargon of data delivery was developed, with
`terminology borrowed from broadcast media. Users of push tech—
`nology could tune into channels that contained broadcasts of infor-
`mation on particular topics.
`By the end of 1996, the excitement had spilled over into the
`mainstream press. A steady stream of articles about push technol-
`ogy appeared in venues such as the New York Times and the Wall
`Street Journal.1 In February 1997, Business Week magazine pub—
`lished a Special Report section entitled “A Way Out of the Web
`Maze", which argued that Webcasting could solve many of the
`Web’s problems, such as information overload and the inability for
`risers to find the data they need. Similar sentiments were echoed by
`numerous vendors and technology pundits.
`The peak of the media hype for push technology was reached
`in March of 1997 when the cover article of Wired magazine blared:
`“Push! Kiss your browser goodbye”. This article began by declar-
`ing: “Remernberthe browser war between Netscape and Microsoft?
`Well forget it. The Web browser itself is about to croak. And good
`riddance”. While the article was certainly provocative and clearly
`overstated, the argument it made was simply that push technology
`would change the Web from a passive library ofinformation into a
`networked, immersive medium for information and entertainment
`delivery. Despite this simple message, the article seemed to epito—
`mize the both the promise of push technology and the potential for
`overselling its virtues.
`
`1.2 The Inevitable Backlash
`
`Around the time of the Wired article, the voices of dissent began
`to make themselves heard. A March 1997 New York Times Cyber-
`Times article by James Gleick stated: “w the promotion of Push is
`the silliest piece of puffery to waft along in several seasons.
`The
`failure of Push is preordained.". A July 1997 article in the on»line
`net—zine webmonkey (published by the same company that publishes
`Wired), was entitled simply “Why Channels Suck”. A somewhat
`more technical article at the CNET on-line site entitled “Networks
`
`1 Many of these articles had titles such as “When Push Comes to Shove”.
`“The Pull of Push", or “X Gets Pushy" (where X is some product or coni-
`pany). The observant reader will notice that we have resisted such tempta-
`tions for this paper.
`
`516
`
`Unfied Patents Exhibit 1013
`
`
`
`Pg. 2
`
`Unfied Patents Exhibit 1013
`Pg. 2
`
`

`

`Strained By Push". described a study indicating that push technolo-
`gies were using an inordinate portion of corporate network band-
`width.
`l’inally, a Byte magazine article in August 1997 had the tag
`line: “Web ptrsh technology is exploding w even though there’s no
`such thing". The Byte article went on to explain (correctly) that cur
`rent push technology is “really ptr||++”.
`
`1.3 The Current Situation
`
`Recently, the media turmoil over push has settled down and expec-
`tations for the technology (at least for the short term) have lowered
`to arguably more reasonable levels. Still, the commercial activity in
`the area is impressive. As oflanuary 1998.21 register of push tech-
`nology vendors listed 49 companies with announced products (see
`David Strom’s site at http://www.strom.com/imc/t4a.html). Many
`other companies who have not yet announced products are working
`on push—based solutions. The major web browser vendors, Netscape
`and Microsoft, have both incorporated push into their products.
`A development indicating a degree of maturation of the field is
`Microsoft's proposal ofthe Channel Definition Format (CDF) stan—
`dard to the World Wide Web Consortium (W3C). CDF is a language
`that web publishers can use to turn their content ittto “Channels” that
`can be exploited by push (or “pull++") technologies. CDF allows
`the specification of metadata about a website, including a search»
`able title and abstract and information about the structure and up-
`date schedule of the site. A number of the major push vendors such
`as PointCast, BackWeb, and AirMcdia have expressed support for
`the proposed standard. Such a standard raises the potential for push
`technology to be more widely integrated into the fabric of the Inter»
`net.
`
`1.4 Sorting it All Out
`The wide range of opinions on the pros and cons of push technology
`is understandable, given the fact that it is a major departure from the
`way distributed information systems have traditionally been built.
`Adding to the noise, however, is a wide-Spread confusion about the
`basic principles of push and where it fits in to the world of data de—
`livery.
`ln this short paper we argue that this confusion stems from
`two fundamental causes: First, push is just one dimension ofa larger
`design space ofdata delivery mechanisms", We identify three dimen-
`sions for data delivery mechanisms (push vs. pull is one ofthem) and
`show how different choices along these dimensions interact. Sec-
`ond, networked information systems can employ difi‘erent data de-
`livery options bctween difi‘erent sets of information producers and
`consumers. Thus, complex systems will likely contain mixtures of
`push and pull (along with the other options) at various points in the
`network, In such a situation, it is inappropriate to identify an entire
`system as being “push~based” or “pull-based".
`In the following, we present an overview of our ideas on data
`dissemination in order to provide a framework for thinking about
`push technology in the larger context ofnetworked information sys»
`terns. Our intent is to clarify some of the issues surrounding push
`technology and to characterize the design space for data delivery in
`dissemination-based information systems and applications.
`
`2 Fundamental Properties
`
`In this section, we present an overview ofdata delivery, focusing on
`how the notion ofdata push fits in with the other dimensions ofthe
`design space for delivery mechanisms. We then describe why it is
`often inappropriate to refer to complex distributed systems as simply
`“push~based"or “pull—based". A more detailed discussion of theses
`issues can be found in [Fran97].
`
`2.1 Options for Data Delivery
`Support for different styles of data delivery allows a distributed in—
`formation system to be optimized for various server, client, network,
`data, and application properties. We have identified three main char—
`acteristics that can be used to compare data delivery mechanisms:
`(l ) push vs. pull; (2) periodic vs. aperiodic; and (3) unicast vs.
`l-to—
`N. While there are numerous other dimensions that should be con-
`sidered. such as fault-tolerance, ordering guarantees, error proper;
`ties, network topology, etc.. we have found that these three charac-
`teristics provide a good initial basis for discussing many popularap—
`preaches. In particular, we argue that all three of these characteris—
`tics tnust be considered in order to make intelligent choices about
`delivery mechanisms for specific situations. Figure 1 shows these
`characteristics and how several common mechanisms relate to them.
`
`2.1.] Client Pull vs. Server Push
`
`We first focus on push vs. pull. Current database servers and object
`repositories manage data for clients that explicitly request data when
`they require it. When a request is received at a server, the server
`locates the information of interest and returns it to the client. This
`request-response style of operation is pull-based— the transfer of
`information from servers to clients is initiated by a client pull.
`In
`contrast, as discussed in the introduction, push-based data delivery
`involves sending information to a client population in advance of
`any specific request. With push-based delivery. the server initiates
`the transfer.
`
`2.1.2 Aperiodic vs. Periodic
`Both push and pull can be performed in either an aperiodic or pea
`riodic fashion. Aperiodic delivery is event-driven — a data request
`(for pull) or transmission (for push) is triggered by an event such as
`a user action (for pull) or data update (for push). In contrast. peri-
`odic delivery is performed according to some rare-arranged sched-
`ule. This schedule may be fixed, or may be generated with some
`degree of randomness.2 An application that sends out stock prices
`on a regular basis is an example of periodic push, whereas one that
`sends out stock prices only when they change is an example of ape—
`riodic push.
`
`2.1.3 Unicast vs. Ito—N
`
`The third characteristic of data delivery mechanisms is whether they
`are based on unicast or l-to-N communication. With unicast com-
`munication, data items are sent from a data source (e.g., a single
`server) to one other machine, while l-to—N communication allows
`multiple machines to receive the data sent by a data source.3
`Two types of l-to-N data delivery can be distinguished: multi-
`cast and broadcast. With multicast, data is sentto a specific subsetof
`clients who have indicated their interest in receiving the data. Since
`the recipients are known, given a two»way communications medium
`it is possible to make multicast reliable; that is, network protocols
`
`2For the purposes ofthis discussion, we do not distinguish between fixed
`and randomized schedules. Such a distinction is important in certain appli~
`cations. For example. algorithms for conserving energy in mobile environ-
`ments proposed by lrnielinski et al, [lmie94] depend on a strict schedule to
`allow mobile clients to “doze” during periods when no data of interest to
`them will be broadcast.
`3Some systems attempt to implement a l-tOvN style ofdata delivery using
`unrcast (i.e.. by sending identical, individual messages to multiple clients).
`As discussed in Section 3, this type of pseudo-broadcastcan result in tremene
`dous bandwidth and server overload problems. For this reason, we classify
`such systems as “unicastAbrtsed” in our taxonomy.
`
`517
`
`Unfied Patents Exhibit 1013
`
`Pg. 3
`
`Unfied Patents Exhibit 1013
`Pg. 3
`
`

`

`/
`
`Aperiodic
`
`Pu”
`\\
`
`\
`
`Periodic
`
`Push
`/\
`Aperiodic
`Periodic
`
`Unicast1-to-N
`Unicast
`1-to-N
`Unicast
`1-to-N
`Unicast
`1-to-N
`
`
`
`request/Jresponse]
`
`Icqucst/response
`polling]
`
`pollingw/snooping
`
`e-mailinglists
`
`publish/subscribe
`
`e—mail listdigests
`
`broadcastdisks
`
`
`
`
`
`
`
`
`
`
`
`subscribe
`
`>.
`w/snooping
`'
`'
`publish/
`
`Figure 1: Data Delivery Options
`
`can be developed that guarantee the eventual delivery of the mes-
`sage to all clients that should receive it.
`In contrast, broadcasting
`sends information over a medium on which an unidentified and pos-
`sibly unbounded set of clients can listen.
`
`2.2 Classification of Delivery Mechanisms
`It
`is possible to classify many existing data delivery mechanisms
`using the characteristics described above. Such a classification is
`shown in Figure I. We discuss several of the mechanisms below.
`Aperiodic Pull . Traditional request/response mechanisms use
`aperiodic pull over a unicast connection. If instead, a l—to-N con-
`nection is used, then clients can “snoop" on the requests made by
`other clients, and obtain data that they haven’t explicitly asked for
`(eg, see [Acha97, Akso981).
`Periodic Pull — III some applications, such as remote sensing, a
`system may periodically send requests to other sites to obtain sta»
`tus information or to detect changed values. If the information is
`returned over a 1—to—N link, then as with request/response, other
`clients can snoop to obtain data items as they go by. Most existing
`Web or Internet-based “push” systems are actually implemented us-
`ing Periodic Pull between the client machines and the data source(s).
`Aperiodic Push — Publish/subscribe protocols are becoming
`a popular way to disseminate information in a network [Oki93,
`Yan95, Glan96]. In a publish/subscribe system, users provide infor-
`mation (sometimes in the form of a profile) indicating the types of
`information they wish to receive. Publish/subscribe is push-based;
`data flow is initiated by the data sources, and is aperiodic, as there
`is no predefined schedule for sending data. Publish/subscribe pro-
`tocols are inherently l-to~N in nature, but due to limitations in cur—
`rent Internet technology, they are often implemented using individ—
`ual unicast messages to multiple clients. Examples of such systems
`include Internet email lists and some existing “push” systems on
`the Internet. True l—to-N delivery is possible through technologies
`such as IP-Multicast, but such solutions are typically limited to in—
`dividual Intranets or Local Area Networks.
`Periodic Push - Periodic push has been used for data dissemi—
`nation in many systems. An example of Periodic Push using unicast
`is Internet mailing lists that send out “digests" on a regular sched-
`ule. For example, the Majordomo system allows a list manager to
`set up a schedule (e.g., weekly) for sending digests. Such digests
`allow users to follow a mailing list without being continually inter-
`rupted by individual messages. There have also been many systems
`that use Periodic Push over a broadcastor multieast link. These in—
`clude TeleText [Amma85, Wong88], DataCycle [Herm87], Broad»
`cast Disks [Acha95a, Acha95b] and mobile databases [Imic94].
`
`2.3 End-to-End Considerations
`
`The second source of confusion about push technology is the fact
`that networked information systems typically contain many inter-
`connected nodes. These nodes may be (logically) organized in vari-
`ous structures, and different data delivery mechanisms may be used
`between different sets of nodes. Given the potential heterogeneity of
`delivery mechanisms in a complex system, it is often not appropri-
`ate to describe the entire end-to-end (i.e., data source to consumer)
`system as “push—based" or “pull-based”.
`In general, a distributed information system can be though of as
`having three types of nodes: (I) data sources, which provide the
`base data that is to be disseminated; (2) clients, which are net con-
`sumers of information; and (3) information brokers, (or agents, me—
`diators, etc.) that acquire information from other sources, add value
`to that information (eg, some additional computation or organiza-
`tional structure) and then distribute this information to other con-
`sumers. By creating hierarchies of brokers, information delivery
`can be tailored to the needs of many different users.
`While the previous discussion has focused primarily on differ-
`ent modes of data delivery, the brokers provide the glue that binds
`these modes together.
`In many cases, the expected usage patterns
`ofthe brokers can drive the selection of which mode of delivery to
`use. For example, a broker that typically is very heavily loaded with
`requests could be an excellent candidate for a push-based delivery
`mechanism to its clients.
`As we move upstream in the data delivery chain, brokers look
`like data sources to their clients. Receivers of information cannot
`detect the details of interconnections any further upstream than their
`immediate predecessor. This principle of network transparency al—
`lows data delivery mechanisms to change without having global ime
`pact. Supposethat node B is pulling data values from nodeA on de-
`mand. Further, supposethat node C is listening to a periodic broad-
`cast from node B which includes values that B has pulled from A.
`Node C will not have to change it's data gathering strategy if A be—
`gins to push values to B. Changes in links are ofinterest only to the
`nodes that are directly involved. Likewise, this transparency allows
`the “appearance“ of the data delivery at any node to differ from the
`way the data is actually delivered earlier in the network. This ability
`to change the appearance of data delivery is at the root of much of
`the confusion surrounding push technology.
`Figure 2 shows a simple example of the importance of consid-
`erin g multiple network components and the impact of transparency.
`The figure shows how data delivery is performed in the initial ver-
`sions of PointCast. To the user sitting at the screen, the system ap-
`pears to be “push-based”; data flows across the screen without any
`user intervention. Due to current limitations of the Internet, how—
`ever, that data is actually brought over to the client machine using
`a stream of periodic pull requests, delivered in a unicast fashion.
`
`518
`
`Unfied Patents Exhibit 1013
`
`
`
`Pg. 4
`
`Unfied Patents Exhibit 1013
`Pg. 4
`
`

`

`1
`1
`
`‘1i
`
`
`1
`l
`
`Poincast 1.0
`PULL
`,
`1
`into
`\i
`user
`
`
`Sewer
`i
`i gallierer
`/
`interface
`‘
`1‘2"
`1
`I
`t
`,
`1
`1
`V1
`.,1
`
`i
`l
`
`Figure 2: Puintcast 1.0
`
`Thus, the implementation of PointCast 1.0 between the client and
`the PointCast server is actually the exact opposite ofthe view that is
`presented to the user in all three dimensions ofthe hierarchy of Fig—
`ure 1. This situation is not unique to PointCast; in fact, it is true for
`virtually all ofthe Internet—based push solutions, and stems from the
`fact that current IP and HTTP protocols do not adequately support
`push or l—to-N communication
`
`3 Reexamining Current Push Technology
`
`The previous section identified several of the sources of confusion
`in the current discussions and debate regarding push technology.
`In particular, the confusion stems from the mismatch between the
`user's perception and the actual data delivery mechanisms used by
`the system. Furthermore, this mismatch is also at the root of many
`of the performance concerns (particularly bandwidth overload) as-
`sociated with cun'ent push technology. The impact of the mismatch
`on performance can be summarized as follows:
`Pull instead ofpush. - Current webcasting solutions typically use
`data pull to obtain information from data sources. This choice is due
`to limitations of the HTTP protocol, which is primarily pull-based.
`As stated previously, replacing push with pull requires that the pull
`be done in a polling manner. Polling can be quite resource inten-
`sive because it generates many requests. These requests consume
`client, server, and network resources. The problems are exacerbated
`if all clients poll individually, which could result in servers becom-
`ing overloaded due to the high volume of requests.
`Periodic illslpad ofaperiodic — Polling is typically done in a pe—
`riodic manner that is independentof the events (e.g., data modifica-
`tions) that would require data to be transfered. This independence
`results in a granularity problem:
`if polling is done too frequently,
`then the overhead can become substantial; if it is done too infre-
`quently, then clients may unknowingly be accessing stale data.
`Unir‘ast insimd of I-ro—N » In the absence of a true broadcastor
`multicast facility, systems that require letoiN behavior must imple-
`ment it using multiple identical messages, one for each intended re-
`cipient. The potential bandwidth problems ofsuch an approach are
`obvious. If n clients are interested in the same data item, then that
`same item must be sent over the network n times.
`Fortunately. the concept of Network Transparency can be used
`to ameliorate this situation. One solution involves placing a local
`server inside an organization’s firewall. All the clients interact with
`the local server in the way that is most appropriate for the local net-
`work and system configuration. The local server can then perform
`polling of the remote data source on behalf of the entire organiza-
`tion, which reduces Internet traffic. Likewise. the data source needs
`only to send a single copy ofeach data item to the local server, which
`cart then distribute it to all the clients it represents. The local server
`can then multicast the data to its clients, if such capability exists.
`
`4 Conclusions
`
`In summary, push is currently a hot topic, but it is essential that it
`be placed in the proper context. Push is one choice (among many)
`for data delivery in distributed information systems. Push is not, for
`example, the same as broadcast. In fact, many existing push—based
`products are based on periodic pull over unicast connections. In our
`work on data dissemination, we have advocated a new look at the
`construction of distributed information systems that allows a seam»
`less integration of all data delivery mechanisms including, but not
`limited to the various forms of push. We believe that this is a fertile
`area of work for the database community since the use of careful
`data management techniques in this context can have a significant
`impact on overall system performance and usability.
`
`References
`
`[Acha95a] S. Aeharya, R. Alonso, M. Franklin, S. Zdonik, “Broad-
`cast Disks: Data Management for Asymmetric Communication
`Environments”,ACM SIGMOD Conf, San Jose, May, 1995.
`[Acha95b] S. Acharya, M. Franklin, S. Zdonik, “Dissemination
`based Data Delivery Using Broadcast Disks”, IEEE Personal
`Communications, 2(6). December. 1995.
`
`[Acha97] S. Acharya, M. Franklin, S. Zdonik, “Balancing Pu sh and
`Pull for Data Broadcast",ACM SIGMOD Conf, 1997.
`
`[Akso98] D. Aksoy, M. Franklin. “Scheduling for Large-Scale On-
`Demand Data Broadcasting", Proc. IEEE INFOCOM Conf, San
`Francisco. March, 1998.
`
`[AmmaSS] M. Ammar, J. Wong, “The Design of Teletext Broad—
`cast Cycles", Perf. Evaluation, 5 (1985).
`[Fran97] M. Franklin, S. Zdonik, “A Framework for Sea]—
`able Dissemination-Based Information Systems”ACM OOPSLA
`Conf, Atlanta. October, 1997.
`
`[Giff90] D. Gifford, “Polychannel Systems for Mass Digital Com~
`munication", CACM, 33(2), February, 1990.
`
`[Glan961 D. Glance, “Multicast Support for Data Dissemination in
`OrbixTalk", IEEE Data Engineering Bulletin, 19(3), Sept., 1996.
`[Herm87l G. Herman,G. Gopal, K. Lee, A. Weinrib, “The Dataey-
`cle Architecture for Very High Throughput Database Systems“,
`Proc. ACM SIGMOD Conf, San Francisco, CA, May, 1987.
`[Imie94] T. Imielinski, S. Viswanathan, B. Badrinath, “Energy EfA
`ficient Indexing on Air”, ACM SIGMOD Conf, 1994.
`[Oki93] B. Oki, M. Pfluegl, A. Siegel, D. Skeen, “The Information
`Bus - An Architecture for Extensible Distributed Systems", Proc.
`14m SOSP. Ashville, NC, December, 1993.
`
`[Wong88] J. Wong, “Broadcast Delivery”, Proceedings of the
`IEEE, 76(12), December, 1988.
`
`[Yan95] T. Yan, H. Garcia-Molina, “SIFI' — A Tool for Wide»
`area Information Dissemination", Proc. 1995 USENIX Technical
`Conference. 1995.
`
`519
`
`Unfied Patents Exhibit 1013
`
`
`
`Pg. 5
`
`Unfied Patents Exhibit 1013
`Pg. 5
`
`