Hardware Reference
In-Depth Information
Cartesian product with union, projection with restriction and lifting with expansion.
The largest solution of parallel equations for prefix-closed regular languages had
been known already in the process-algebra literature [90, 94, 118].
2.3.2
An Application to Converter Synthesis: The Protocol
Mismatch Problem
We apply the algorithm in Sect. 2.3.1 to an equation over finite automata to solve a
problem of converter synthesis, i.e., the design of an automaton to translate between
two different protocols.
A communication system has a sending part and a receiving part that ex-
change data through a specific protocol. A mismatch occurs when two systems
with different protocols try to communicate. The mismatch problem is solved
by designing a converter that translates between the receiver and the sender,
while respecting the overall service specification of the behavior of the composed
communication system relative to the environment. We formulate the problem as a
parallel language equation: given the service specification C of a communication
system, a component sender and a component receiver, find a converter X whose
composition with the sender and receiver A meets the system specification after
hiding the internal signals: A ˘ X C .
As an example we consider the problem of designing a protocol converter to
interface: an alternating-bit (AB) sender and a non-sequenced (NS) receiver. This
problem is adapted from [78] and [56]. A communication system based on an
alternating bit protocol is composed of two processes, a sender and a receiver, which
communicate over a half duplex channel that can transfer data in either directions,
but not simultaneously. Each process uses a control bit called the alternating bit,
whose value is updated by each message sent over the channel in either direction.
The acknowledgement is also based on the alternating bit: each message received
by either process in the system corresponds to an acknowledgement message that
depends on the bit value. If the acknowledgement received by a process does not
correspond to the message sent originally, the message is resent until the correct
acknowledgement is received. On the other hand, a communication system is non-
sequenced when no distinction is made among the consecutive messages received or
their corresponding acknowledgements. This means that neither messages nor their
acknowledgements are distinguished by any flags such as with the alternating bit.
Figure 2.4 shows the block diagram of the composed system. Each component
is represented by a rectangle with incoming and outgoing labeled arrows to indicate
the inputs and outputs, respectively. The sender consists of an AB protocol sender
( PS ) and of an AB protocol channel ( PC ). Meanwhile, the receiving part includes
an NS protocol receiver ( PR ). The converter X must interface the two mismatched
protocols and guarantee that its composition with PS, PC and PR refines the
service specification ( SS ) of the composed system. The events Acc ( Accept )and Del
Search WWH ::




Custom Search