`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
`
`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
`
`