Overhead 1: Motivation

UCB Activities

• Katz, Brewer, McCanne ARPA-sponsored project on collaboration technologies
• Rowe's "Berkeley Multimedia Research Center" Distance learning facilities and systems infrastructure

use SRM as building block (control protocol, data distribution)

Overhead 2: Scalable Reliable Multicast (SRM)

Joint work with Floyd, Jacobson, Zhang, Liu

Receiver reliable protocol:

• source multicast data to group
• receivers detect missing data
• ask for data using "repair-requests"

<figure showing ACK implosion problem>

Overhead 3: SRM Continued

Solution: multicast everything including repair request!

• Anyone that has data can reply, not just original source
• Nodes use randomized delay before generating "repair reply"
• Receipt of repair packet (request or reply) cases node to suppress its own attempt

On average, only one or two session members downstream of a loss will generate a repair request. And in response, only one or two members generate reply

More details in SIGCOMM '95 paper

Overhead 4: Chronology

• worked out specific instance of SRM in wb (spring 1992 term project)
• in SIGCOMM paper, "recast" wb/SRM repair mechanism as reliable multicast "framework" (and refined timer algorithm/adaptation scheme

But haven't actually worked out details of this "framework" where we can distill into specific instances of application protocols

Overhead 5: SRM Skeleton

(described in SIGCOMM95 paper)

Goal: share common protocol piece across multiple application instances and allow application semantics to be reflected back into SRM

We claim layering won't work:

Slide 6: SRM Skeleton

Slide 7: Data Naming

Example of an open problem

• traditional transports name data as byte-offset and length (e.g., sequenced byte stream)
• SRM wants "self-describing" structured names

want to give application flexibility to ask for specific pieces of data and ignore others

Slide 8: Example: wb

Data name is as hoc: 3-level field:

can grow data in any of 3 dimensions (can't do this with 1-D sequential space)

Slide 9: generalized SRM data naming

What if we wanted a more general wb page hierarchy, e.g.,

(imagine infinitely long SRM sessions)

Observation: we have

1. objects (each with a 1-D sequence space
2. object hierarchy

Unix file system analogy

• object name UFS path name
• object content file contents

can map this directly onto disk (nice for archiving)

Slide 10: Example: wb

Problems:

1. how to distribute hierarchy (i.e., "state announcement") recursive application of SRM to disseminate "directory entries"
2. how to encode path name efficiently?
   • Live with variable length ASCII path names
   • profile-specific encoding (e.g., wb 3-level sequence number)
   • entropy code path names (e.g., profile-specific Huffman code)

Slide 11: summary

Think we're at the point where we can start thinking about experimental protocol specifications.

But many open problems:

• congestion control
• receiver heterogeneity
• scalable state announcement (how to disseminate seq. offsets of all leaves in directory hierarchy)
• scalable distance estimates (how to avoid computing O(n**2) distance estimates for SRM repair algorithm