`Topology Configuration
`Paul Francis
`NTT PF Labs
`francis@slab.ntt.co.jp
`www.yallcast.com
`
`0001
`
`BUNGIE - EXHIBIT 1016
`
`
`
`Yallcast-specific Content
`Protocol Stack Challenges
`Sufficient
`generality
`
`Application
`
`API
`
`Dealing with
`dynamic
`topologies
`
`Yallcast Tree Protocol (YTP)
`(framing, forwarding, sequencing)
`
`yTCP
`
`yRTP
`
`yRMTP
`
`Etc...
`
`Getting
`through NAT
`boxes
`
`Yallcast ID Protocol (YIDP)
`UDP
`TCP
`IP
`IP
`Multicast
`Unicast
`
`0002
`
`
`
`Tree Terminology
`
`Transit
`A
`
`D
`
`L
`Leaf
`
`Parent
`of C
`
`P
`
`Child
`of P
`C
`
`Root
`R
`
`Cluster
`Head
`
`H
`
`B
`
`F1
`
`F2
`
`F3
`
`F4
`
`Cluster
`Feet
`
`0003
`
`
`
`Multicast (Over Tree)
`
`Multicast (Over Tree)
`
`0004
`
`
`
`Broadcast (Over Everything)
`
`0005
`
`
`
`Multicast with Mesh Repair*
`
`X
`
`*Dramatization
`
`0006
`
`
`
`Unicast, and
`Anycast (Over Tree and Mesh)
`
`0007
`
`
`
`Tree Building Approaches
`
`Mesh First
`• Build proximal
`mesh
`• Run classical
`routing algorithm
`over mesh
`• Tree “falls out”
`• AMRoute, CMU
`
`Tree First
`• Screen known members
`for tree neighbor validity
`• Explicitly select
`proximal tree neighbor
`• Run algorithm to detect
`loops
`• Yallcast
`
`0008
`
`
`
`Member Discovery
`
`• Learn of other members to build topologies
`– Contact Rendezvous (initial)
`– Parent-side tree anycast or mesh anycast
`discovery messages (background activity)
`– Navigate tree (as-needed foreground activity)
`– If root, broadcast “I am root” message, inform
`rendezvous
`
`0009
`
`
`
`Tree Loop Detection/Prevention
`
`• Yallcast tree may have transient loops
`• Pre- and post-topology change loop
`detection
`• Three basic mechanisms:
`– Root Path
`– Topology trace
`– Incompatible changes trace
`
`0010
`
`
`
`Root Path
`
`• Analogous to BGP AS-path
`• Transmitted parent to child
`– Each member appends itself to received root
`path
`• Discovers loops after tree change
`
`0011
`
`
`
`Root Path
`R
`R
`
`A
`
`R:A
`
`D
`R:A:D
`
`L
`R:A:L
`B
`
`R:P:H:B
`
`P
`
`R:P
`
`C
`R:P:C
`
`H
`
`R:P:H
`
`F1
`
`F2
`
`F3
`
`F4
`
`Root Path
`
`Flow of Root Path
`
`0012
`
`
`
`Root Path Loop Detection
`
`R
`R
`
`A
`
`R:A
`
`P:H:B:P!!!
`P
`
`P
`
`H
`
`P:H
`
`C
`R:P:C
`
`D
`R:A:D
`
`L
`R:A:L
`
`B
`
`P:H:B
`
`F1
`
`F2
`
`F3
`
`F4
`
`0013
`
`
`
`Valid Parents
`
`P’s parent-side
`members
`
`A
`
`D
`R:A:D
`
`L
`R:A:L
`B
`
`R:P:H:B
`
`R
`R
`
`R:A
`
`P
`
`R:P
`
`C
`R:P:C
`
`H
`
`R:P:H
`
`F1
`
`F2
`
`F3
`
`F4
`
`P’s child-side members
`
`0014
`
`
`
`How Loops Form
`“Simultaneous” changes by multiple
`members (e.g. P and L)
`R
`R
`
`A
`
`R:A
`
`D
`R:A:D
`R:A:L
`R:P:H:B
`
`L
`
`B
`
`P
`
`R:P
`
`C
`R:P:C
`
`H
`
`R:P:H
`
`0015
`
`
`
`Loop Avoidance Algorithms
`
`• Coordinated Loop Avoidance
`– Have parent, want to improve
`• Emergency Loop Avoidance
`– No parent, must find one quickly
`• Coordinated has stronger loop detection
`• Coordinated scales better
`
`0016
`
`
`
`Emergency Loop Avoidance
`
`• Send “Root Path Trace” along new Root
`Path
`• Root Path Trace follows path of
`“prospective parents”
`• Last member in path, or first to discover
`loop, replies to initiator
`
`0017
`
`
`
`Emergency Loop Avoidance:
`Only P Changing Parent
`X
`
`P
`
`R:P
`
`C
`R:P:C
`
`R
`R
`reply
`trace
`
`R:A
`A
`
`D
`R:A:D
`R:A:L
`R:P:H:B
`
`L
`
`trace
`
`B
`
`H
`
`R:P:H
`
`Prospective Parent
`
`0018
`
`
`
`Emergency Loop Avoidance:
`P and L Changing Parent
`X
`
`Loop Detected!!!
`
`P
`
`R:P
`
`C
`R:P:C
`
`trace
`H
`
`R:P:H
`
`R:A
`A
`
`R
`R
`reply
`trace
`
`D
`R:A:D
`R:A:L
`R:P:H:B
`
`L
`
`trace
`
`trace
`
`B
`
`0019
`
`
`
`Coordinated Loop Avoidance
`
`• Send “Intent to Join” along tree from
`joining member to new parent
`• Members along the path record intended
`change
`• Members along the path check for and
`block incompatible changes
`
`0020
`
`
`
`Coordinated Loop Avoidance:
`Only P Changing Parent
`R
`R
`
`D
`R:A:D
`R:A:L
`R:P:H:B
`
`L
`
`accept
`
`H
`
`R:P:H
`
`B
`
`R:A
`A
`itj
`
`itj
`
`itj
`
`P
`
`R:P
`
`C
`R:P:C
`
`0021
`
`
`
`Coordinated Loop Avoidance:
`P and L Changing Parent
`R
`R
`
`R:A
`A
`
`itj
`L
`
`D
`R:A:D
`R:A:L
`R:P:H:B
`
`B
`
`itj
`
`itj
`
`reject
`accept
`
`P
`
`R:P
`
`C
`R:P:C
`
`H
`
`R:P:H
`
`0022
`
`
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
