create new tag
, view all tags

Network Stitching Services and API Design

Stitching Computation Service (SCS)

API Design

The API will be based on XML-RPC format to be consistent with other GENI APIs. It currently has only one method:

struct ComputePath ( string slice_urn,
                     geni.rspec request_rspec,
                     struct options )


             code {
                 geni_code: <int, success or error code>,
                 options: <struct, other code values>, optional
             value {
                 service_rspec: <geni.rspec, computed/expanded RSpec on success>, optional
                 workflow_data: <struct, workflow support data>, optional
             output: <string, error or information message>, optional


  • The request RSpec is composed by user or agent/proxy and contains an optional stitching extension part.
  • When a stitching extension exists in the RSpec, SCS will take it as the path computation request.
  • When stitching extension is missing, SCS will construct path request from all the multi-aggregate links in the main body.
  • A typical request RSpec has at least one stitching path or one multi-aggregate link with source and destination hops/interfaces.
  • Multiple concurrent stitching paths may be requested in a single request RSpec.
  • Initial SCS implementation does not support bridged multi-point (MP). Only single or multiple Point-to-Point paths are allowed.
  • boolean geni_hold_path: (optional, default=false), SCS to hold the path exclusively for a preconfigured holding period to avoid contention.
  • geni_start_time: (optional, default=now), projected starting time for the stitching path(s).
  • geni_end_time: (optional, default=infinite), projected expiration time for the stitching path(s).
  • geni_routing_profile: (optional), a struct of {path_id: routing_profile} map. The path_id corresponding to a stitching path id in request_rspec. routing_profile is a struct of two optional items {'hop_inclusion_list': array of urn strings} and {'hop_exclusion_list': array of urn strings}.
    • In both 'hop_inclusion_list' and 'hop_exclusion_list', we can specify list of URN strings the SCS request wants to include in or exclude from resulting paths. Each URN represents an aggregate, node, port or link.
    • A request may also exclude a series of VLAN tags and tag ranges from any 'link' hops in the 'hop_exclusion_list'. An example is urn:publicid:IDN+emulab.net+interface+procurveA:3.19=100-104,110-200, where VLAN range 100-104 and 110-200 are excluded from link emulab.net:procurveA:3.19.
    • In addition, any intermediate hops of 'strict' type (default type='strict') in a request_rspec stitching path will be added to 'hop_inclusion list'.
  • boolean geni_workflow_data: (optional, default=true), SCS to return workflow data in support of user / agent / tool workflow logic.


SCS Core Code
  • The implementation will be based on ARCHSTONE MxTCE, an advanced topology computation engine written in C++.
  • Use xmlrpc-c lib to add XML-RPC API server to MxTCE
  • Parse GENI RSpec formats to load GENI Aggregate and DCN topologies
  • Load topologies from static/cached local RSpec files for now.

Handling Multi-Aggregate Advertisement
  • Building inter-aggregate topology from advertisement with stitching extension:
    • Add internal Aggregate Reflector URNs, e.g., urn:publicid:IDN+ion.internet2.edu+interface+*:*:* and urn:publicid:IDN+ion.internet2.edu+interface+*:*:**
    • Handle both two field and three field links, e.g., urn:publicid:IDN+emulab+interface+procurve-salt:2.39 vs. urn:publicid:IDN+ion.internet2.edu+interface+rtr.newy:ae0:ban
    • Add internal links between network interfaces and host interfaces in main part of an advertisement RSpec.
    • Handle wildcard inward facing links, e.g., urn:publicid:IDN+ion.internet2.edu+interface+rtr.sal:*:*
      • This allows individual AM to micro-manage the connectivity, capacity and capability it wants to advertise for how specific stitching links are connected to rest of the aggregate.
      • When none such wildcard inward facing link exists in the advertisement, SCS add one for each node in stitching extension and connect them to the Aggregate Reflector.
      • When at least one such wildcard inward facing link exists, SCS assume the AM want to micro-manage advertisement for all stitching links for inward facing connectivity. It will not add any such links automatically. Any stitching node without advertised connection to rest of aggregate may be disconnected in the generated topology.
    • Aggregate 'capabilities' information is learned from advertisement and then populated into every hop/link in the SCS reply service_rspec. These information will be used in computing workflow dependencies.

Service Request and Reply

Workflow Support

  • SCS computes workflow data to facilitate user / agent / tool side workflow logic. The "workflow_data" is of the following format:
    • a struct of {path_id: dependencies} map, where path_id corresponds a stitching path in "service_rspec".
    • "dependencies" is an array of root-level dependency struct of the below format
      • hop_urn: string
      • aggregate_urn: string
      • aggregate_url: string
      • dependencies: array of recursive structs referring to further dependencies
      • import_vlans: boolean, indicate whether to import VLAN tags from underlying dependency hops

  • The dependency relationships are generated by the Heuristic Algorithm below
    1. place all path hops in a list
    2. scan the list to create a list of initial dependency structs with empty dependency references
    3. run first pass of dependency check based on Producer-Consumer relationship. Hops in 'consumer' only role will become dependencies to neighboring hops with 'producer' role.
    4. run second pass of dependency check based on VLAN-Continuation relationship. If neither of two neighboring hops is capable of VLAN translation, then the one belonging to center aggregate (more hops) becomes dependency to its neighbor (edge, few hops). If they tie, calculate available-VLAN range intersections between ingress and egress ports for aggregates the hops belong to. The one with narrower range will become dependency to its neighbor with wider range.
      • note: Addition of the new dependency must be dependency-loop-free. If adding the new dependency relationship causes a dependency-loop, it is skipped. Depth first search (DFS) is used to conduct the loop-free check.
    5. run third pass of dependency check based on VLAN-Translation relationship. If a hop is capable of VLAN translation and its neighboring hop is not, the former will become dependency to latter.
      • note: Again a dependency-loop-free check is conducted. If adding the new dependency relationship causes a dependency-loop, it is skipped.
    6. a final pass of the dependency list to conduct a loop-free merge so that dependency structs of same domain are depended by same dependency upper-level structs.
    7. generate the dependencies XML-RPC tree output in recursive format.

  • Below is a Heuristic Algorithm to merge workflow dependencies of multiple P2P paths
    1. sort the paths in descending order of hop length
    2. create an empty workflow dependency list and merge workflow dependencies one by one in the above order
    3. for each being merged workflow, scan its dependency list to check each dependency struct
    4. if a dependency struct does not exist in current workflow dependency list, copy it over
    5. for the equivalent dependency struct (copied or already existed) in current workflow, find all other dependency structs that exist in both workflows
    6. add the relationships (both depending and depended) of this dependency struct to others from the being merged workflow to the current workflow. Make sure each newly added relationship is loop-free. Otherwise, skip it.
    7. repeat 4-7 for every path until a "all_paths_merged" workflow dependency list is created.

  • MxTCE core always computes a single, specific VLAN tag to put into vlanAvailableRange and vlanSuggestedRange for every hop. SCS will do post-processing to widen the VLAN ranges to facilitate negotiation-based workflow.
    • Copy source and destination VLAN tag ranges from request to source and destination hops of resulting path. This could be combination of 'any' and/or specific VLANs in order to be consistent with user request.
    • All middle hops of L2SC type will have VLAN range widened to "any". This is to facilitate open-ended negotiation.
    • vlanSuggestedRange remains unchanged with the computed specific VLAN tag(s).

  • Examples 'workflow_data' information in XML-RPC reply can be seen in "Implementation / Service Request and Reply" section.

Known Issues

  • SCS has no authentication mechanism. A minimal security feature should include SSL client authentication that trusts certs from the following:
    • GENI Clearinghouse
    • pgeni.gpolab
    • planetlab
    • PG Utah
  • SCS is very fast in responding to requests. However, we have not done any stress test and performance evaluation.

Future Features

  • Add proxy for topology retrieval from a global Topology Service instead of static files.
  • Provide multiple alternate paths as a request option. The reply will contain the requested number of alternate paths for each stitching path.
  • Handle DCN domains that are not GENI aggregates.
    • SCS has no problem to compute a path across such domains if domain topology is learned.
    • However, SCS cannot pick the correct egress DCN hop and skip intermediate hops so that a chain-mode DCN circuit can be created from GENI DCN domain to non-GENI DCN domain.
  • The SCS is open for other heuristic algorithms to compute workflow dependency. In particular, we want the following features:
    • Ability to handle multiple paths in one slice that have cross-path dependencies. The challenge that two or more paths crossing the same aggregate must be requested simultaneously thus must have same level of dependency related to neighboring aggregates. This may conflict with other dependency relationships and require a heuristic to resolve the conflicts.
  • Support bridged multi-point stitching. In particular, we need SCS to help compute bridged multi-point VLAN across aggregates.
Topic revision: r24 - 2014-02-17 - XiYang
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback