Fixing the "Broken-Link" Problem:
The W3Objects Approach

by David Ingham, Steve Caughey, and Mark Little

Arjuna Distributed Systems Group,
Department of Computing Science,
Newcastle University,
United kingdom.

For more information, see the W3Objects site.

Presentation Contents

• Motivation for W3Objects research
• W3Objects overview
• Referencing in the Web
• Techniques for tracking migrating objects
• The W3Objects referencing model
• W3Objects system architecture
• Interoperability with current Web software
• Conclusions

Motivation for W3Objects Research

• Extensibility
  • HTTP defines a fixed set of operations for all resources
    • difficult to augment interface or alter implementation
  • Incorporating non-standard resources using CGI is difficult
    • too low-level programming model cf. stub generation
    • difficult to write parameter marshaling code; easy to introduce errors
    • no architectural support for advanced resources
• Referencing Model
  • Highly visible problem of broken-links

W3Objects Overview

• Key goal is to provide an extensible Web architecture
• Framework to aid in the construction of Web-based applications
• Based on an object-oriented distributed computing approach
• W3Objects are encapsulated entities
• W3Objects support abstraction
• Interface inheritance provides polymorphism
• Code reuse achieved using behavioral inheritance

See http://arjuna.ncl.ac.uk/w3objects/

Referencing in the Web

• The Web as a whole is greater than the sum of the parts
  • the Web’s power is achieved by the connection of related information
  • uni-directional linking using location-based addressing (URLs)
• System lacks referential integrity and migration transparency
  • referenced resources are deleted
  • resources move around (both intra and inter-server)
  • resulting in broken-links or dangling references
• Proposed solutions
  • HTTP redirect directive (HTTP code 302)
  • Persistent URLs (PURLs) from OCLC
  • Uniform Resource Names (URNs)
  • Hyper-G’s p-flood - broadcast updates using flooding technique

Object Migration Scenario

• Consider a system partitioned into S spaces
• An object, O, resides at one of the spaces, S_source
• R spaces contain a reference to O
• N spaces contain name-servers which refer to O
• Reference holder on space S_migrator sends a message to S_source instructing O to migrate to S_destination
• Assumptions
  • R and N are disjoint sets
  • S_migrator is not equal to S_source which is not equal to S_destination
  • communication achieved using unicast RPC with at-most-once semantics

Object Migration Scenario

Options for Tracking Object Migration

• Option 1: do nothing at migration time
  • object fault occurs at next invocation through each reference
  • object must be located through the use of search
• Option 2: replace migrated object with forward reference
  • invocations are redirected transparently to the new location
  • references are updated through piggy-backed information
• Option 3: callback to all references at migration time
  • no further work necessary at invocation time
• Option 4: update name-server(s) at migration time
  • object fault occurs at next invocation through each reference
  • name-server query to determine new location of object
  • reference invokes object at new location

Comparison of Messaging Costs

Comparison of Messaging Costs

• Consider the effects of faults:
  • callbacks & name-server updates must now be atomic
  • transactional update mechanisms can be expensive
  • migrations are more likely to fail

forward referencing solution imposes least cost

• Fault-tolerance, availability & performance
  • referencing chains can introduce additional points of failure
  • invocation overhead cannot always be tolerated

composite model provides greatest flexibility

W3Objects Referencing Model

• Aims
  • to provide referential integrity
  • to provide migration transparency
  • to provide flexible mechanisms to support differing object requirements
• Integration of referencing techniques
  • all W3Objects support forward referencing with chain short-cutting
  • cheapest guarantee of referential integrity
  • per reference customisation for fault-tolerance or performance
• Prototype implementation built using Shadows
• Deployed within W3Objects servers
  • guarantees integrity of links between W3Objects

Object Migration & Short-cutting

Obtaining References

Name-servers

maintaining bindings between names and objects

Name-servers

providing alternative paths to objects

Referencing Model Summary

• Forward referencing
  • default mechanisms for all W3Objects
  • achieves referential integrity
  • provides migration transparency
  • chain-shortcutting reduces points of failure
• Name-servers
  • used to provide name to object bindings
  • used to provide alternative paths to an object
• Callback
  • used in conjunction with name-servers to eliminate common paths
  • used with references to minimise invocation overhead

W3Objects System Architecture

Working with Existing Web Software

• Supporting HTTP access
  • gateway module incorporated into ‘extensible’ Web servers
  • CGI-based gateway
• Reference translation; browsers only understand URLs
  • URLs to W3Objects provide no RI guarantees
  • URLs are correct at time of translation, perhaps not after short-cutting
  • URLs based on name-server references provide best option`
  • compound references translated to multiple URLs
• Bringing W3Object references closer to clients
  • W3Object-based hotlist server

Conclusions

• Object-oriented, flexible & distributed scheme
• Forward-referencing provides cheap referential integrity
• Supplemented with name-server & callback
  • to achieve higher degrees of fault-tolerance
  • to improve performance
• Appropriate combination chosen on a per-reference basis
• Evolutionary approach
  • can be used as added-value service for existing resources