Equivalence and generalization in a layered network model

摘要

We propose a formal model of layered telecommunication networks. The model includes ports, which are access points to data streams; links, which transmit data streams; and adapters, which convert data streams from one layer to another. Two ports communicate if there is a path from one to the other in which every adaptation is balanced by a reverse adaptation. Two networks M and N with the same public ports are equivalent if for any other network Q, two ports in the composition M∘Q communicate exactly if they communicate in N∘Q. M generalizes N if whenever two ports communicate in N∘Q, the ports also communicate in M∘Q. We give linear time algorithms to decide equivalence and generalization of networks when adaptation is “simple”, i.e. one or more data streams can be adapted into only a single data stream. If adaptation models “protection switching,” then testing equivalence is co-NP-complete.