Talk:Dev:onl reservation algorithm

Suggested refinement of terminology. Let's refer to the physical infrastructure as a "host graph" and each reservation as a "guest graph". The problem we are solving is the scheduling of guest graphs.

Need to add edge weights to both the physical topology and the reservations. Constrain the mapping of guest graphs onto the host graph so that the host graph edges are not overloaded.

Also, I think we want to include the notion of a multipoint link. That is, ports on several different components (not just 2) can be connected to a single multipoint link. This is implemented using a VLAN of course, preferably with all endpoints on the same infrastructure switch, but this need not be a hard constraint.

It's also important to include numbered ports on components in the guest graph. We're not just connecting components together. We are connecting specific ports of components and these port numbers are visible to users.

Jon

=================

First another terminology note. Let's use "substrate node" rather than "infrastructure node" to refer the abstraction of configuration switches. Just for the sake of brevity.

Now, some more thoughts on multipoint links. A link connecting N hosts can potentially carry N Gb/s of traffic. This is fine if all N links are on the same substrate node, but is a problem if they are not. If they split across two substrate nodes, then the max load on the inter-node link is determined by the substrate node with the larger number of hosts.

So, I think it would be worthwhile to allow users to specify (1) that a multipoint link must be "nonblocking" (meaning that all connected endpoints can send simultaneously and the traffic will get through so long as receivers are not overloaded) or (2) that a multipoint link can have a guaranteed bandwidth smaller than the sum of the endpoint bandwidths. So for example, a multipoint link with 30 hosts split across two substrate links could have bandwidth up to 12 Gb/s. If/when we move to having a 10 Gb/s switch linking the current 1 Gb/s switches, we can have multipoint links with a 10 Gb/s bandwidth limit. In fact, we might even be able to support smaller bandwidth limits (say 5 Gb/s) if the switches will allow us to assign class-of-service codes to VLANs. I think our switches may support this, which means we should be able to map point-to-point vlans onto a high priority class and multipoint VLANs onto a lower priority class. Then when a (single) multipoint VLAN shares a substrate link with several point-to-point VLANs it gets whatever bandwidth they don't use. So if a user requests a 6 Gb/s multipoint link, we can put four point-to-point 1 Gb/s links on the same substrate link with it.

Jon