MuxSchemeStatistical swap sequence and purification scheme

[yoursunny]

As of #65, MuxSchemeStatistical only supports ASAP swap sequence [1, 0, 0, .., 0, 0, 1] and does not allow purification scheme.
Normally, swap sequence and purification scheme are supplied from a FIB entry.
However, in MuxSchemeStatistical, the FIB entry is unspecified during QubitEntangledEvent processing.

This issue is to find a solution to this problem.

[yoursunny]

As mentioned in #65 (comment) , the consumption condition in MuxSchemeStatistical.qubit_is_eligible currently relies on naming convention.
I'm able to eliminate this assumption by performing a FIB lookup:

1. When a qubit becomes ELIGIBLE, it must have an associated EPR.
2. The EPR's (src,dst) tuple is used to query FIB entries.
3. If one or more FIB entries are found where fib_entry.route[0] == epr.src.name and fib_entry.route[-1] == epr.dst.name, the EPR is deemed an end-to-end entanglement satisfying the request in this FIB entry, and thus it is consumed.

This still places an assumption: if one request's src-dst pair is on another request's route, most entanglements would be consumed for the shorter request.
Suppose the topology is A-B-C-D-E and there are two FIB entries req=0 A-B-C swap=[1,0,1] and req=1 A-B-C-D-E swap=[2,0,1,0,2]:

• Every A-C entanglement matches request 0 and is consumed.
• Request 1 can never receive entanglements.

[yoursunny]

Inspired by the consumption condition solution, I believe it's possible to perform a (more complex) FIB lookup for supporting purification scheme.

1. As with current code, newly entangled qubit has purif_rounds=0 and its tmp_path_ids contains path_ids that identify FIB entries whose route includes the qchannel.
2. Check want_rounds = fib_entry.purif[epr.src, epr.dst] for each FIB entry.

• A If qubit.purif_rounds == want_rounds, this qubit should enter ELIGIBLE state.
• B If qubit.purif_rounds < want_rounds, this qubit should undergo a round of purification.

3. If all FIB entries have A condition or all FIB entries have B condition, do it.
4. If some FIB entries have A condition while other FIB entries have B condition, choose one according to certain strategy, and then narrow the tmp_path_ids set to only identify FIB entries compatible with the chosen condition.

This shares some similarity with MuxSchemeDynamicEpr, except that it defers the narrowing of tmp_path_ids for each round of purification.

For example, consider a topology S---A---B---D0,D1,D2,D3 with four FIB entries:

0. S-A-B-D0 purif={A-B: 0}
1. S-A-B-D1 purif={A-B: 1}
2. S-A-B-D2 purif={A-B: 0}
3. S-A-B-D3 purif={A-B: 1}

When A receives an A-B entanglement,

1. It finds two FIB entries with want_rounds = 0 and two FIB entries with want_rounds = 1.
2. It decides to perform purification to qubit.purif_rounds = 1, which narrows epr.tmp_path_ids = [1,3].
3. It finds two FIB entries with want_rounds = 1.
4. It sets the qubit to ELIGIBLE since that's the only choice.

A problem in this idea is how to coordinate between A and B.
Without a swap sequence, A is the primary on A-B purification segment.
Nevertheless, A might decide to purify while B simultaneously decide to swap.
Then, when the purif_solicit arrives at B, the referred EPRs would no longer exist there.

[amar-ox]

can you apply similar logic to swap sequences? With tmp_path_ids narrows as only path with "compatible" configurations are selected. I didn't think much about it, just suggesting.

[yoursunny]

It is necessary to tightly define a swap sequence before defining a purification scheme.
Some swap sequence has multiple possible orders, which would cause the EPR to escape a purification.
Example:

• Topology: A-B-C-D-E
• Instructions: swap=[1,0,0,0,1] purif={"A-C":1, "C-E":1}
• If C performs swapping first forming B-D EPR, and then B and D each performs swapping, there would be no purification.

Since MuxSchemeStatistical currently can only effectively use swap=[1,0,0,0,1], it isn't possible to solve purification scheme issue, until after the swap sequence is solved.

[yoursunny]

The part I'm struggling with is, narrowing the swap sequence and purif scheme would require the primary and secondary nodes to coordinate their decisions.
The coordination would either require centralized control or classical communication.

I searched existing cases of this coordination and found this code in MuxSchemeDynamicEpr.qubit_is_entangled (moved from here in #65):
https://github.com/amar-ox/dynamic-qnetsim/blob/372b643b3d943c179cbee3e688002f086b502be6/qns/network/proactive/mux_dynamic_epr.py#L44-L54
The epr instance is shared between two nodes.
Effectively, this code would allows one node to make a decision (which path_id to put in epr.tmp_path_ids), which is instantly known by the other node without communication.
How does this work in reality?

[amar-ox]

Since dynamic EPR affectation affects EPR to a path at creation (independent of EPRs existing at each node), tmp_path_ids is assumed to be set by one of the nodes during EPR generation.

[yoursunny]

dynamic EPR affectation affects EPR to a path at creation, tmp_path_ids is assumed to be set by one of the nodes during EPR generation

I see, so it can be included as part of the reservation message.

Well, this wouldn't work for MuxSchemeStatistical.
Including the choices (or a random seed that dictates the choices) in the reservation message would effectively turn MuxSchemeStatistical into MuxSchemeDynamicEpr.

[amar-ox]

Yes. But looking more closely, this is not really a coordination. I believe when a path is served by a channel, both neighbors will have it in their qchannel-path map. As long as tmp_path_ids is not modified by a local decision (as in dynamic EPR) the list should be the same as set by either neighbors.
Here, tmp_path_ids is used only to search for eligible EPRs. Then there is a detection of conflictual swapping decisions.

[yoursunny]

For MuxSchemeDynamicEpr, choosing a singular path_id in tmp_path_ids is a coordination, but it can be chosen during reservation time, instead of EPR arrival time.

For MuxSchemeStatistical, currently tmp_path_ids is gathered from qchannel-path map, which would be the same on both ends, as long as the controller did not install or uninstall a path at runtime.
However, if one node is allowed to make a "swap or purif" decision and accordingly narrow tmp_path_ids, this would be a local decision.

---

Consider the topology show below, and imagine E-F is the bottleneck due to its long distance while A-E C-E F-B F-D entanglements are readily available:

A         B
 \       /
  +E---F+
 /       \
C         D

Consider paths A-E-F-B swap=[1,0,0,1] purif={} and C-E-F-D swap=[1,0,0,1] purif={}:

• E has 50-50 chance of swapping into A-E-F vs C-E-F.
• F has 50-50 chance of swapping into E-F-B and E-F-D
• Possible end-to-end entanglements are A-E-F-B (25%, OK), C-E-F-D (25%, OK), A-E-F-D (25%, wasted), C-E-F-B (25%, wasted).
• Overall, 50% of E-F elementary entanglements are wasted due to conflictual parallel swapping.

If we also have differing purif schemes in the paths A-E-F-B swap=[1,0,0,1] purif={"E-F":0} and C-E-F-D swap=[1,0,0,1] purif={"E-F":1}:

• When an E-F entanglement arrives at E, E may choose to:
  • Swap into A-E-F.
  • Either save the EPR for later purification or initiate purification together with a saved EPR.
• When an E-F entanglement arrives at F, F may choose to:
  • Swap into E-F-B.
  • Save the EPR awaiting purif solicit message.
• If every probability is set to 50%, overall 50% of E-F elementary entanglements are wasted due to conflictual parallel decisions.
• Other probabilities lead to different wastage percentages and different fairness between the two flows.

I'd imagine doing a local choice without coordination between E and F could be workable.
However, the choice cannot be directly written into tmp_path_ids field, but has to be reconciled via messages in a similar manner as conflictual parallel swapping detection.

[amar-ox]

The wasted EPRs due to conflicting decisions seems to be a good metric to evaluate decision strategies here.

We should keep in mind that statistical is expected to mirror the behavior of forwarding in IP networks (best effort). So, we can define some principles to follow, like:

• Refrain from using explicit messaging for coordination between nodes.
• Rely on swapping/purification messages to detect (and potentially resolve) conflictual decisions.
• Decision strategy can be random by default, and customizable by the user.

Regarding the assumptions, in the example above, even if the controller uninstalls a path at runtime, the qchannel-path maps of both nodes will update similarly.