Some of your friends are working for CluNet, a builder of large commu- nication

Question

Some of your friends are working for CluNet, a builder of large commu- nication networks, and they are looking at algorithms for switching in a particular type of input/output crossbar.

Here is the setup. There are n input wires and n output wires, each directed from a source to a terminus. Each input wire meets each output wire in exactly one distinct point, at a special piece of hardware called a junction box. Points on the wire are naturally ordered in the direction from source to terminus; for two distinct points x and y on the same wire, we say that x is upstream from y if x is closer to the source than y, and otherwise we say x is downstream from y. The order in which one input wire meets the output wires is not necessarily the same as the order in which another input wire meets the output wires. (And similarly for the orders in which output wires meet input wires.) Figure 1.8 gives an example of such a collection of input and output wires.

Now, here’s the switching component of this situation. Each input wire is carrying a distinct data stream, and this data stream must be switched onto one of the output wires. If the stream of Input i is switched onto Output j, at junction box B, then this stream passes through all junction boxes upstream from B on Input i, then through B, then through all junction boxes downstream from B on Output j. It does not matter which input data stream gets switched onto which output wire, but each input data stream must be switched onto a different output wire. Furthermore—and this is the tricky constraint—no two data streams can pass through the same junction box following the switching operation.

Finally, here’s the problem. Show that for any specified pattern in which the input wires and output wires meet each other (each pair meet- ing exactly once), a valid switching of the data streams can always be found—one in which each input data stream is switched onto a different output, and no two of the resulting streams pass through the same junc- tion box. Additionally, give an algorithm to find such a valid switching.

Explanation / Answer

Answer:

In general terms, switching refers to managing the movement of data among various nodes of a computer network,
whenever it is required to send data from one source node to a destination node. As there are number of links
(wires in hardware terms) in a network, it is very much required to find a precise mapping between a source (input)
link and a destination (output) link. In other words, problem is to determine which input wire will be mapped or switched to which output wire.

The data stream of an input wire should be switched to an output wire at the earliest in order to minimize the risk of colliding with another already switched data stream. Similarly, the data steam of an output wire should be switched as as late as possible in order to minimize the risk of colliding with an yet to be switched data stream.

Algorithm for solution:

This kind of problem can be solved by Stable Marriage Algorithm. Under this algorithm, objective is to find a stable matching between two ordered sets of elements. A matching is said to be stable if an element in first set is mapped (matched) to its preferred element in second set (or vice versa) based on a ranking criteria. To find a preferred match, each element in a set ranks each element in the other set. Hence, for switching, each input wire will rank each output wire as it encounters it to find a suitable wire for upstreaming. Similarly each output wire will rank each input wire as it encounters it to find a suitable wire for downstreaming.

Validity of algorithm:

To prove the validity of algorithm, lets assume that two data streams (one input steam i and one output stream j) cross at a junction box. It means the output stream j would be one input stream that would have been switched from some other input wire, say k. But in existing situation, stream j prefers stream i in place of stream k and stream i prefers stream j to the stream, say l, onto which it is actually switched. Since it meets output j upstream. This contradicts the assumption that we chose a stable matching between input wires and output wires.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.