Potential PR: source routing in Merlin?

[ziyuezzy]

This is a issue made for a potential PR:

Dear devs,

I am working on a feature for SST-Merlin. Because it contains a considerable amount of work, I would really appreciate your opnions on whether or not this is a Pull Request that you will consider to merge. Any comments on the current design approach is welcome.

Objective

The main goal is to support source-routing in SST-merlin. Source routing means the routed path will be determined before a packet enters the first router or switch.

This will require the network admin to be aware of the network topology, and there should be algorithms (e.g., in the endpoint NICs) to determine the routed paths for the given network topology.

Design

In additional to the original merlin module, the following additions will be made:

1. Add source-routing support in routers (implemented throught the topology modules).

• For this, I am now adopting an input-from-file method. So the user would need to generate a .graphml file (for example, using the networkx library in python) to describe the network topology and input that into the SST config file.

• A new topology class is now implemented , namely topo_any, which will parse the input graph description and build the network accordingly. Note that the main motivation was to support source routing. However, topology-independent Destination-tag routing would also be possible with the topo_any topology class.

  • Source routing: it will require the encapsulated request can be dynamic_cast into a SRRequest (will be explained later) that has an embedded routed path. What the router do in this case is basically reading the next-hop router id defined in the embedded routed path and forward.
  • Destination-tag routing: it will require another input file to specify the routing table (for each router, a mapping from the destination EP id to the next-hop router id). Building on this, topology-independent ECMP or UGAL routing algorithms can be implemented. For topology-specific destination-tag routing algorithms, one should still use that specific topology class.

2. Add source-routing support in the endpoints.

• For this, I am defining a new class endpointNIC which is a child class of SST::Interfaces::SimpleNetwork. It interacts with two sides -- a traffic generator and a linkcontrol module. This endpointNIC class will build a framework to enable NIC features at the endpoins, while its child classes will further extend NIC-specific functionalities, as will be explained later.

  • On the endpoint side, 'endpointNIC' talks to a traffic generator which can be any module that generates traffic for merlin, e.g., offeredload, simple_patterns/*, test/nic, trafficgen, emberjob, etc.
  • On the network side, 'endpointNIC' holds either a LinkControl or a ReorderLinkControl as a subcomponent, delegating all sends and receives to it.
  • ( Note that this is distinct from the test NIC defined in sst-elements-src/src/sst/elements/merlin/test/nic.h, which is actually a traffic generator.)

• The role of endpointNIC is to enable simulating NIC/smartNIC behaviors such as source routing, ECMP entropy/flow-hash manipulation (e.g., Ultra-Ethernet), or RDMA-related offloads. While in the current scope, I will focus on implementing the source routing feature.

• A new class SourceRoutingNIC will inherit from class endpointNIC. It will construct a list of available paths for each router, parsed from an external file. When a request passes by, a path will be selected for routing. And the original request, together with this routed path, will be converted to an instance of the SRRequest class.

• The new class SRRequest inherits from SST::Interfaces::SimpleNetwork::Request, with an extra variable path, and the corresponding set_path() and get_path() methods.

• Apart from parsing routed paths from external files, there will also be interfaces to change the stored paths during the simulation. For example, new paths can be calucalted with weighted Dijkstra algorithms, while the graph weights can be related to the link bandwidth ultilization information. This will be more on the control plane of SDN, which we plan to handle in another PR.

• When interfacing with Ember+Firefly, the Request generated by the firefly nic will also be converted to SRRequest.

The following figure illustrates the original data flow inside an Merlin endpoint:

With SourceRoutingNIC in the middle, the data flow will look like the following figure:

[feldergast]

At quick glance, this looks like a reasonable approach. I will have more time after the user group meeting next week to look a little deeper and think through any implications.