faction architecture proposal

[Robert Morris]

Right now factions have a natural "push" architecture. All events are
driven by packet arrivals. We don't have a good story for what should
happen in the output side of the router, where we can't just push
packets into the output hardware. The example configuration that's
driving this redesign looks like:

    queue1           output interface A
          \         /
           scheduler
          /         \
    queue2           output interface B

The intent is to share load across two parallel outputs, presumably
connected to the same destination router. When output A is ready to
send a new packet, the scheduler can pick from either queue, but it
had better send the packet to A rather than B.  In the general case
there might be lots of factions between the scheduler and the outputs,
so the decision isn't as simple as it might seem.

We're planning to solve this by supporting two kinds of paths, "push"
and "pull", which will make sense on the input and output sides of the
router respectively. You can think of both as nested function calls.

Here's how push will look:

  inputfaction::interrupt()  [ie hardware receive interrupt]
    faction1::push(packet *p)
      faction2::push(packet *p)
        queuefaction::push(packet *p)

That is, each faction's push() method is responsible for choosing an
output and calling that output's push(). push() functions don't need
to be aware of which input called them, though we may want to add a
"which input" argument to push(). A push() method could make push()
calls on multiple outputs if it wants to do multicast.

Here's how pull will look:

  outputfaction::interrupt() [ie transmit complete interrupt]
    packet *p = faction1::pull()
      packet *p = faction2::pull()
        packet *p = queuefaction::pull()
        return(p);
      return(p);
    shove p into the output hardware.

Factions that make decisions may have to commit to being inherently
push or pull. Push decisions (which output?) seem like routing
decisions. Pull decisions (which input?) seem like scheduling
decisions.

Factions that make no decisions can work in either mode. We can supply
default push() and pull() methods that look like:

  handle_push(packet *p) {
    action(p);
    call_push(0, p); /* 0 is the output index */
  }
  handle_pull(){
    packet *p = call_pull(0); /* 0 is the input index */
    action(p);
    return(p);
  }

And the faction implementer would just supply the action() function.
Statistics gathering factions and encapsulation factions are examples
that can work either way.

The queue faction is the only one I can think of that would
simultaneously involve push and pull. A queue is a push/pull
converter. I'm not sure you could build a converter without involving
buffering somehow.

Queues need to alert all the outputs that might pull from them when
they become non-empty. Maybe the requirements checker can
automatically arrange for this.