Hyphos.
`A Self-Organizing, Wireless Network
`
`Robert Dunbar Poor
`
`Submitted to the Program in Media Arts and Sciences
`School of Architecture and Planning
`in partial fulfillment of the requirements for the degree of
`Master of Science at the Massachusetts Institute of Technology
`June 1997
`
`© 1997 Massachusetts Institute of Technology. All Rights Reserved.
`
`Author
`
`Certified by
`
`\
`
`Program in Media Arts & Sciences
`May 9, 1997
`
`Michael J. Hawley
`rss f Media Arts & Sciences
`Assistant Pr
`Alex Dreyfoos Jr. (1954) Career Development Professor of Media Arts & Sciences
`Thesis Supervisor
`
`Accepted by
`
`Stephen A. Benton
`Chair
`Departmental Committee on Graduate Students
`Program in Media Arts and Sciences
`
`N-s RST'UTE
`AkAH
`OF TECHNLO
`
`U C RA
`
`97
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0001
`
`

`

`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0002
`
`

`

`Abstract
`Everyday objects are beginning to find expression in digital networks, creating a
`new family of objects that displays personalized behavior and memory. But how
`can you weave a thousand objects in one room into the Web? How can you
`connect them together without a tangle of wires, a burden of battery packs, or a
`Ph.D. in network administration?
`
`is to develop Hyphos1 , a wireless network for
`The goal of this work
`interconnecting thousands of everyday objects. My thesis is that by using very
`short-range transceivers and relaying messages among the nodes, a new class of
`network emerges: a Hyphos network is self-organizing with a low cost per node;
`transmissions are tightly localized resulting in high bandwidth and low power
`consumption; fully distributed routing and control assures robust communication
`in the face of changes to the network topology.
`
`Thesis Advisor:
`Michael J. Hawley
`Assistant Professor of Media Arts & Sciences
`Alex Dreyfoos Jr. (1954) Career Development Professor of Media Arts & Sciences
`
`This research was sponsored by the Things That Think Consortium. The author
`gratefully thanks the Motorola Fellows program for its support.
`
`1. hy-phos \'h-f46s\ n [Greek hyphos web]
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0003
`
`

`

`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0004
`
`

`

`Hyphos:
`
`A Self-Organizing, Wireless Network
`
`Robert Dunbar Poor
`
`The following people have served as readers for this thesis:
`
`Reader
`
`Reader
`
`Andrew Lippman
`Associate Director
`M.I.T. Media Laboratory
`
`Steven McGeady
`Visiting Fellow
`Vice President and Genera19anager, Internet Technology Laboratory
`Intel Corporation
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0005
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0006
`
`

`

`Contents
`
`1.0
`
`2.0
`
`3.0
`
`4.0
`
`7
`9
`11
`
`19
`
`31
`
`41
`
`Contents................................................................................................
`List of Figures......................................................................................
`List of Tables..........................................................................................
`Introduction.........................................................................................13
`1.1
`What if network connections were smaller?
`A thousand connections in one room
`1.2
`1.3
`About this thesis
`1.4
`Some application scenarios
`Context ................................................................................................
`2.1
`Scope of this work
`2.2
`Design Goals
`2.3
`Approach
`2.4
`Assumptions
`2.5
`Prior Work
`System Description ................................................................................
`3.1
`System Overview
`3.2
`Reference Model
`3.3
`Message Format
`Physical Layer
`3.4
`3.5
`Data Link Layer
`3.6
`Medium Access Layer
`3.7
`Network Layer
`3.8
`'Iansport Layer
`Simulation and Results......................................................................
`Components of the Simulator
`4.1
`4.2
`The Tests
`4.3
`Simulation Assumptions
`4.4
`load: when does Hyphos hit the wall?
`density: how well does Hyphos scale?
`4.5
`4.6
`motion: how do mobile nodes affect performance?
`radius: what are the effects of adjusting transmit radius
`4.7
`4.8
`chatter: how do multiple dialogs affect performance?
`server: how does one server / many clients perform?
`4.9
`Performance Summary
`4.10
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0007
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`5.0
`
`A revised transmitter/receiver model ...............................................
`5.1
`Modelling Attenuation and Noise
`5.2
`Implications
`5.3
`The revised transceiver model
`5.4
`The Results
`load redux: when does the network hit the wall?
`5.5
`5.6
`chatter redux: multiple dialogs
`5.7
`server redux: a client/server simulation
`6.0 Conclusions ........................................................................................
`6.1
`Summary
`6.2
`Contributions
`6.3
`Future Work
`6.4
`Acknowledgments
`References ..........................................................................................
`
`7.0
`
`69
`
`83
`
`89
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0008
`
`

`

`List of Figures
`
`FIGURE 2-1
`FIGURE 2-2
`FIGURE 3-1
`FIGURE 4-1
`FIGURE 4-2
`FIGURE 4-3
`FIGURE 4-4
`FIGURE 4-5
`FIGURE 4-6
`FIGURE 4-7
`FIGURE 4-8
`FIGURE 4-9
`FIGURE 4-10
`FIGURE 4-11
`FIGURE 4-12
`FIGURE 4-13
`FIGURE 4-14
`FIGURE 4-15
`FIGURE 4-16
`FIGURE 4-17
`FIGURE 4-18
`FIGURE 4-19
`FIGURE 4-20
`FIGURE 5-1
`FIGURE 5-2
`FIGURE 5-3
`FIGURE 5-4
`FIGURE 5-5
`FIGURE 5-6
`FIGURE 5-7
`FIGURE 5-8
`FIGURE 5-9
`FIGURE 5-10
`FIGURE 5-11
`FIGURE 6-1
`
`Relaying a message from A to C ......................................................
`.......
`Relay costs form a contour .........................................................
`.......
`Relaying a message from Node A to Node C............................
`......
`Testing the network with varying loads......................................
`......
`Throughput vs. Client Rate.........................................................
`Average and Maximum Latency vs. load ...................................
`......
`Reliability vs. load ......................................................................
`......
`Testing the network with varying node density..........................
`......
`Reliability vs. node count ...........................................................
`......
`Number of hops vs. node count ..................................................
`......
`Average and maximum latency vs. node count ..........................
`.......
`Testing the network as nodes move...........................................
`.......
`Network reliability vs. mobility..................................................
`Network reliability vs. mobility, potential boost = 1..................
`......
`.......
`Testing the network as the transmitter radius varies...................
`Network reliability vs. transmitter coverage.....................................
`.......
`Latency vs. coverage..................................................................
`.....
`..............................
`Testing the network with multiple "dialogs"
`Reliability vs. simultaneous dialogs .................................................
`Latency vs. simultaneous dialogs ......................................................
`......
`multiple clients talking to one server..........................................
`......
`Reliability vs. # of clients (1 server)...........................................
`......
`Latency vs. # of clients (1 server)...............................................
`.......
`Simple vs. Revised Propagation Models ...................................
`Performance a s function of load (alternate transceiver model).........
`Throughput vs. offered rate (alternate transceiver model).................
`Maximum latency vs. offered rate (alternate transceiver model).........
`.......
`Reliability vs. offered rate (alternate transceiver model)...........
`Multiple Dialogs(alternate transceiver model) ..................................
`......
`Reliability vs. # of dialogs (alternate transceiver model)...........
`......
`Latency vs. # of dialogs (alternate transceiver model)...............
`.......
`One server, many clients (alternate transceiver model).............
`Reliability vs. # of clients (alternate transceiver model) ...................
`.......
`Latency vs. # of clients (alternate transceiver model)...............
`......
`Artists conception of a Hyphos node..........................................
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0009
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0010
`
`

`

`List of Tables
`
`Table 3-1:
`Table 3-2:
`
`Format of a Hyphos message..........................................................................
`Format of a Routing Table Entry .....................................................................
`
`30
`34
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0011
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0012
`
`

`

`1.0 Introduction
`
`1.0
`
`Introduction
`
`1.1 What if network connections were smaller?
`
`Today, connecting to a digital network usually involves a computer. This isn't
`surprising: most network interfaces are designed and marketed specifically for use
`with a computer. The smallest interfaces currently available, marketed for lap-top
`computers, cost on the order of hundreds of dollars and require support from the
`operating system in order to communicate with the target network.
`
`But what will happen when the cost of connecting to a digital network drops to a
`few dollars and doesn't require the direct support of a computer? What kinds of
`new connections will be possible?
`
`- You won't need to set your watch ever again. Your watch will be on-line all the
`time and will query the nearest network time server to discover the local time.
`Your appointment book, also on the network, will ask your watch to notify you
`about upcoming appointments.
`
`- Tomorrow's "radio" will be a network appliance: regardless of when you turn it
`on, it immediately starts reading the latest headlines custom tailored to your
`interests.
`
`e The smoke detector in your basement will be networked. If it detects trouble,
`rather than futilely beeping in isolation, it will enlist the services of an effective
`software ally to alert the members of the house, and if none are found, to start
`making telephone calls until someone is found to address the problem.
`
`- A custom-built office chair will be on-line from the moment it's ordered until
`the time it's delivered to the customer. A networked tag, carrying all of the
`ordering and shipping information, will literally be built into the chair as it
`progresses through the production line. At each station, the tag informs the
`machinery as to the desired fabric, style, and options and logs the progress of
`the operations. At the loading dock, the tag informs the truck of the customer's
`shipping address.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0013
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`- Toy dolls will know how to read, talk and listen. Rather than putting a powerful
`computer in each toy, it will suffice to network each toy to the local family PC.
`Connected to the Web, the family PC can download new activities and lessons
`every day; these toys will always have new surprises in store.
`
`1.2
`
`A thousand connections in one room
`
`Today, the density of network connections rarely exceeds one connection per
`person: one network connection serves one computer which serves one person.
`But this ratio will change.
`
`The number of host computers connected to the Internet is estimated to be
`growing by a factor of ten every three years. This could facetiously be interpreted
`to mean that you'll have ten computers on your desk where you now have one.
`More likely, however, networks will diffuse into objects much smaller than today's
`personal computer, and a typical room will contain dozens or hundreds of devices
`connected to networks.
`
`What is required to move beyond the one person / one computer / one network
`model of today? What are the implications of a hundred network connections per
`room, or even per person?
`
`1.2.1 Wireless
`
`First, such a network must be wireless: In a room with hundreds of connections
`we can afford neither the clutter nor the expense of hundreds of interconnecting
`cables.
`
`1.2.2
`
`Low power
`
`Second, the individual nodes on the network must be low power. Since the nodes
`are wireless, they must be powered from batteries or from surplus energy
`scavenged from the environment. As a practical consideration, nodes powered
`from batteries should run unattended for at least a year.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0014
`
`

`

`1.0 Introduction
`
`1.2.3 Self-organizing
`Third, the network must be dynamically self-organizing. A network may contain
`hundreds or thousands of nodes, some of which may be mobile or temporary. In
`such a network, it's impossible to maintain network routing tables manually.
`Rather, the network must automatically adapt as its topology changes and as
`nodes arrive at or depart from the network environment.
`
`Some corollaries arise from the above rules:
`1.2.4
`Limited range
`Nodes will communicate only with their nearby neighbors. Since nodes operate
`with limited power, they have a limited broadcast range. In a turnabout of
`conventional wisdom, a limited broadcast range has advantages over the larger
`broadcast areas touted by today's wireless LANs. In particular, when a node turns
`on its transmitter, it usurps the airspace for its area of coverage. A node with a
`smaller area of coverage affects fewer nodes, permitting a higher overall network
`bandwidth.
`
`1.2.5
`
`Fully distributed routing
`
`Since any node communicates only with its immediate neighbors, there can be no
`central controlling "hub," and the burden of network control falls upon the
`individual nodes. Each node must play an equal part in routing packets and
`maintaining network state.
`
`1.3 About this thesis
`
`This thesis describes Hyphos (from the Greek word for web): a self-organizing,
`wireless network. A node in a Hyphos network communicates only with other
`nodes in its immediate vicinity. Neighbors relay messages to their neighbors in
`turn until the message reaches its destination.
`
`1.3.1 A scene at a banquet
`
`Imagine you are seated at a large banquet table. You need urgently to deliver a
`message to your host, seated at the head of the table. You scribble a note and seal
`it in an envelope addressed to your host. You then pass the envelope to your
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0015
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`neighbor with instructions to "pass it on" until it reaches the host. The amount of
`effort expended by each guest is minimal-conversation is barely interrupted-
`and your message quickly finds its way into the hands of your host.
`
`The above scenario approximates the basic workings of a Hyphos network. The
`principal difference is that in Hyphos the communication consists of electronic
`bits and radio links rather than sheets of paper and hands.
`
`1.3.2
`
`The rest of this document
`
`Hyphos has been designed to create fine-grained, low-cost networks. The last
`section of this chapter describes several novel applications made possible by this
`approach.
`
`The essence of Hyphos is captured by an architecture (an interconnected network
`of wireless nodes) and a set of protocols (the routing and message forwarding
`algorithms resident in each node). Chapter 2.0, "Context" describes the scope of
`this thesis, specifying the design goals, underlying assumptions, and prior work in
`the field.
`
`Chapter 3.0, "System Description," gives the technical details of Hyphos and how
`it is implemented. The chapter introduces the layered reference model used to
`describe the network and the format of messages relayed among Hyphos nodes. It
`follows with a detailed description of each of layer.
`
`Hyphos's behavior has been modelled by software simulation. Chapter 4.0,
`"Simulation and Results" describes the assumptions made in the simulation and
`presents quantified results of the simulation.
`
`Chapter 5.0, "A revised transmitter/receiver model" investigates a model for
`wireless communication more precise than the simple model used in Chapter 4.0,
`and shows its effects on network performance.
`
`Chapter 6.0, "Conclusions" describes the innovations particular to Hyphos,
`summarizes the results of the Hyphos network and suggests directions for future
`work.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0016
`
`

`

`1.0 Introduction
`
`1.4
`
`Some application scenarios
`
`Imagine a Hyphos network, created simply by virtue of assembling a collection of
`wireless nodes. The nodes of this network are:
`
`- Compact: Each node is a small disc, 25mm diameter by 10mm thick.
`
`" Inexpensive: Each node costs approximately $2.
`
`- Fast: Each node provides a 2 M bit / second data link to the network.
`
`- Simple: Each node is self-configuring, adding itself to the network upon being
`physically placed in an environment with other nodes.
`
`What applications can we build from a collection of these nodes?
`
`1.4.1 Corporate LANs
`
`A corporate office populated with a Hyphos network can dispense with intra-
`building network wiring. Every workstation, printer, and laptop uses a Hyphos
`node rather than an Ethernet interface. This approach eliminates the installation
`costs associated with wall jacks, cabling, and phone closets. Adding new
`equipment to the network is as simple as powering up a new node. Relocating
`equipment requires no more work than carrying it to its new location-no cables
`have to be moved, no routing tables updated.
`
`1.4.2
`
`"Last millimeter" delivery into the home
`
`Many communications carriers are scrambling to get networks to the home.
`Carriers don't generally provide wiring
`inside
`the house; however few
`homeowners wish to pay for extensive rewiring.
`
`A Hyphos network offers a cost-effective gateway between an external network
`and devices within the house. Since each node is wireless, cables are eliminated.
`Nodes are inexpensive, making it practical to connect "everyday objects" to the
`network. For example, all clocks are connected to centralized time server; the
`"flashing 12:00" on a VCR becomes a thing of the past. The ubiquitous TV
`Remote Control brings up today's TV guide from the WEB and instructs the VCR
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0017
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`as to which shows are to be recorded. An appliance automatically calls its home
`office for self-diagnosis or firmware updates.
`
`1.4.3
`
`Intelligent Warehousing, Routing and Shipping
`
`Every box and pallet in a warehouse carries a Hyphos node. Since nodes can
`contain state and computing power, database functions are distributed among the
`objects themselves, rather than maintained in a central database.
`
`An incoming box announces its contents to the warehouse when it arrives. The
`warehouse assigns that box to a particular truck for the outbound leg, using
`dynamic routing to minimize cost. When the time comes to send the box, the truck
`queries the boxes in the warehouse directly: "Which ones of you belong in this
`truck?" Each box maintains its entire shipping history and can be queried at any
`time.
`
`Since state and routing information is kept with the shipping boxes themselves,
`maintaining database consistency is no longer a problem.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0018
`
`

`

`2.0 Context
`
`2.0 Context
`
`2.1
`
`Scope of this work
`
`This work examines the domain of ad-hoci wireless networking and presents a
`design for Hyphos, a self-organizing wireless network. A Hyphos network is
`formed by a collection of individual wireless nodes, whose overall architecture is
`presented in terms of the algorithms and data structures resident in each node. A
`software simulator checks
`the correctness and behavior of the Hyphos
`architecture.
`
`To use terminology from the International Standards Organization's OSI (Open
`Systems Interconnection) Reference Model, the design of the Hyphos algorithms
`focuses on a Medium Access Layer and a Networking Layer, which are described
`in detail in Chapter 3.0, "System Description."
`
`Hyphos does not try to specify what applications or even what high-level
`protocols are to be run over the network. The contract of Hyphos is to deliver
`valid data packets to a Transport Layer upon which higher level protocols (e.g.
`TCP) can be implemented.
`
`At the low end of the design space, Hyphos doesn't specify what sort of physical
`medium is used to transport the bits from one node to the other. The primary
`assumption that Hyphos makes of the Data Link Layer and the Physical Layer is a
`"local multicast" system, that is, when a node transmits data, one or more nearby
`nodes receive the transmission.
`
`2.2
`
`Design Goals
`
`The goal of this work is to define Hyphos, a new model for digital networks. By
`significantly decreasing the cost and complexity of forming a digital connection,
`new possibilities arise. Everyday objects, previously excluded from participation
`
`1. The term "ad-hoc" is applied to networks that don't require pre-existing infrastructure and whose topolo-
`gies are dynamically established.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0019
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`in the digital realm, can now provide means for much richer communication
`between people and the digital world.
`
`Towards this goal, the design of Hyphos has the following objectives.
`
`2.2.1
`
`Low Cost
`
`Assertion: The cost per network connection should be sufficiently low that
`connecting a thermostat or a clock to the network is economically attractive. The
`cost of a connection should add no more than 10% to the cost of these devices.
`
`Implications: Assuming the cost of finished goods for a clock or thermostat to be
`$20, the cost of a Hyphos node will not exceed $2.
`
`2.2.2 Dense, fine-grained networking
`
`Assertion: The network should be able to interconnect dozens or hundreds of
`objects in one room or building.
`
`Implications: It's neither practical nor economical to string cables between
`hundreds of devices in one room. Hyphos nodes will be wireless.
`
`2.2.3 Easy setup and low maintenance
`
`Assertion: Since there are potentially hundreds of nodes on the network, it is
`impractical to manually update host and routing tables for individual nodes.
`
`Implications: The Hyphos network will be self-organizing, and will adapt
`automatically as new nodes are introduced into or removed from the network.
`
`2.2.4
`
`Low Power
`
`Assertion: A network node should run unattended for over a year.
`
`Implications: Since a Hyphos node is wireless, it will scavenge power from
`environmental sources (photocells, stray RF energy), or will run from a battery.
`Given a small lithium cell battery with a capacity of 1000 mAH, a Hyphos node
`will limit its average current consumption to 110 pA or less.
`
`2.2.5 Mobile
`
`Assertion: Nodes may be carried on people or mobile objects, and may constantly
`be moving in relation to other nodes.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0020
`
`

`

`2.0 Context
`
`Implications: The routing algorithms of Hyphos will support a network topology
`that is constantly changing.
`
`2.2.6 Robust
`
`Assertion: The network should remain functional as nodes come on-line or go off-
`line. Single point failures must not bring down the network.
`
`Implications: Routing and control functions will be fully distributed throughout
`the network.
`
`2.3 Approach
`2.3.1 Multi-hop communication
`
`As has been established, a Hyphos node is wireless and low-power. Taken
`together, this means that a node has limited transmit range. In order to transmit a
`message beyond the range of a single transmitter, a Hyphos node calls upon one
`or more of its neighbors in order to relay the message to its final destination. This
`technique is commonly called multi-hop communication.
`
`|Node C
`
`Node A
`
`,
`
`--
`
`. Node B
`
`FIGURE 2-1 Relaying a message from A to C
`FIGURE 2-1 shows an example of multi-hop communication in a network of
`three nodes. Each node, indicated by a solid dot, has a limited transmit range, as
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0021
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`indicated by a dotted circle around the dot. Node A can't communicate with Node
`C directly, so it enlists the services of Node B to relay messages to node C; this is
`the basis of all multi-hop communication systems.
`
`Different multi-hop systems use different strategies in routing messages through a
`network. To date, these strategies can be categorized as "link state routing" or
`"source path routing" algorithms. By contrast, Hyphos uses a new technique
`called "contour routing." Each approach is described briefly below.
`
`2.3.2 Link State Routing
`In link state routing, each node maintains a routing table that, given a particular
`destination, specifies which one of its neighbor offers the optimal path towards the
`destination. "Optimal" is generally interpreted to mean the shortest path, but may
`account for other factors such as load balancing.
`
`When a node in a link state routing system wishes to relay a message, it checks
`internal routing tables to determine which of its neighbors should relay the
`message; the address of that neighbor is installed in the message header as the
`recipient. The node sends the message. Of all the neighbors receiving the
`broadcast, only the designated recipient acts on the message. That neighbor
`repeats the process, re-relaying the message as required until the message reaches
`the ultimate destination.
`
`Internet routers use Link State routing algorithms.
`
`2.3.3 Source Path Routing
`In source path routing, the originating node constructs an entire source route or
`"itinerary" of the message in the message header, giving the address of each node
`through which the message should be relayed in order to reach the destination. If a
`receiving node isn't the last node named in the message's source route, it simply
`relays the message to the next node on the source route. This process repeats until
`the message arrives at its ultimate destination.
`
`Systems that employ Source Path Routing include UUCP mail headers (e.g.
`packets
`IP
`debugging
`certain
`and
`barney!bedrock!berkeley)
`[Tane96](415).
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0022
`
`

`

`2.0 Context
`
`2.3.4 Contour Routing
`
`Both Link State Routing and Source Path Routing schemes require that each node
`in the network keep a constant record of neighboring nodes. This requires that
`each node sends periodic "ping" or "I am here" messages to its neighbors. These
`periodic transmissions consume power and clutter up the airwaves. These periodic
`messages pose a problem in certain sensitive applications as it makes it easier for
`eavesdroppers to locate individual nodes.
`
`By contrast, a node in a Hyphos network doesn't require knowledge of its
`neighbors in order to relay messages. Instead, the node keeps an estimate of the
`"cost" required to deliver a message to a particular destination. When it comes
`time to deliver or relay a message, the sending node writes the estimated cost in
`the message header and broadcasts the message. Of all the neighboring nodes that
`receive the broadcast, only those that can relay the message to the destination at a
`lower cost will do so. FIGURE 2-2 helps to visualize this process.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0023
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`FIGURE 2-2 Relay costs form a contour
`FIGURE 2-2 depicts the process of sending a message from node A to node C.
`Next to each node is a number indicating the estimated cost from that node to
`Node C. The cost of relaying a message from Node C to itself is 0.0; the cost
`increases with the number of hops from Node C.
`
`Node A has established the cost of sending a message to C to be 2.0. When Node
`A sends a message to Node C, it writes information in the header of the message
`indicating that the message is to be delivered to Node C at a cost of less than 2.0.
`The neighbors of Node A (Nodes B, D, and E) all receive A's transmission. Since
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0024
`
`

`

`2.0 Context
`
`only Node B can deliver the message at a cost less than 2.0, it relays the message
`while the other neighbors ignore it.
`
`By this process, only nodes that are "closer to" the destination (in some
`topological sense) will participate in forwarding the message. Viewing each
`node's estimated routing cost as an "altitude," the process of relaying a message
`towards its destination is analogous to "rolling a message down a hill." Given this
`analogy, this routing technique has been termed Contour Routing.
`
`Routing tables are compact and tend to remain small. An entry in a routing table
`essentially consists of the ID of a target node and the accrued cost of the last
`message from that target1 . A node creates a routing table entry only when it
`receives a message originated by a new target. The routing table entry will be
`pruned if no message is received from that target within a period of time. Over
`time, the routing table will contain entries only for those targets for whom this
`node is actively involved in relaying messages. For example, if a node lies along a
`routing path shared by six different originators, then its routing table will contain
`only six entries.
`
`The exact mechanics of Contour Routing are described in Chapter 3.
`
`2.3.5 Establishing initial routes
`
`A node estimates the cost to a particular originating node based upon the "accrued
`cost" of messages it receives from that originating node. But this presumes that
`the originating node has already sent a message, which would normally require
`that the originating node already has a cost estimate to its target. This leads to the
`proverbial chicken and egg quandary: how do initial routes become established?
`
`If an originating node wishes to send a message to another node for which there is
`no routing information, the originating node will initiate a "flood" message. The
`flood message carries with it the ID of the intended target, the ID of the originator,
`and a sequence number keyed to the originator.
`
`1. In truth, a routing table entry contains two additional fields: the sequence number of the last message
`received from the target and a time stamp used in "pruning" old entries.
`
`Fitbit, Inc. v. Philips North America LLC
`IPR2020-00783
`
`Fitbit, Inc. Ex. 1034 Page 0025
`
`

`

`Hyphos: A Self-Organizing, Wireless Network
`
`Each node in the network receiving a flood message will relay the message
`exactly once. When a node relays a flood message, it makes a note in its routing
`table, which includes the originator and sequence number. If the node receives
`another copy of that flood message, the sequence number in the routing table will
`indicate that the message is a duplicate, and the node won't relay it a second time.
`The node will, however, update the cost entry in the routing table if the newer
`message indicates a lower cost than stored in the routing table.
`
`Barring certain pathologies, a flood message will reach every node in the
`network'. After the flood, every node will have a routing table entry "back to" the
`originator of the flood message, and the designated recipient of the flood message
`can enter into a dialog with the originator using the routing information
`established by the act of flooding.
`
`2.4
`
`Assumptions
`
`Hyphos makes a number of assumptions: Some of these assumptions are
`questioned or addressed in Section 6.3, "Future Work," on page 84.
`
`- Nodes are homogenous. In particular, nodes run the same algorithms and are
`willing to forwards packets on behalf of other nodes within their own network.
`
`- Hyphos assumes that the wireless links of the network form a single connected
`graph, that is, there exists at least one path between any pair of transmitters and
`receivers.
`
`- Transceiver