Ping-pong scheme

Short description: Programming algorithm

Algorithms said to employ a Ping-Pong scheme exist in different fields of software engineering. They are characterized by an alternation between two entities. In the examples described below, these entities are communication partners, network paths or file blocks.

Databases

In most database management systems durable database transactions are supported through a log file. However, multiple writes to the same page of that file can produce a slim chance of data loss. Assuming for simplicity that the log file is organized in pages whose size matches the block size of its underlying medium, the following problem can occur:

If the very last page of the log file is only partially filled with data and has to be written to permanent storage in this state, the very same page will have to be overwritten during the next write operation. If a crash happens during that later write operation, previously stored log data may be lost.

The Ping-Pong scheme described in Transaction Processing^[1] eliminates this problem by alternately writing the contents of said (logical) last page to two different physical pages inside the log file (the actual last page i and its empty successor i+1). Once said logical log page is no longer the last page (i.e. it is completely filled with log data), it is written one last time to the regular physical position (i) inside the log file.

This scheme requires the usage of time stamps for each page in order to distinguish the most recent version of the logical last page one from its predecessor.

Networking

Internet

A functionality which lets a computer A find out whether a computer B is reachable and responding is built into the Internet Control Message Protocol (ICMP). Through an "Echo Request" Computer A asks B to send back an "Echo Reply".^[2] These two messages are also sometimes erroneously called "ping" and "pong".

Routing

In Routing, a Ping-Pong scheme is a simple algorithm for distributing data packets across two paths. If you had two paths A and B, then the algorithm would randomly start with one of the paths and then switch back and forth between the two.^[3]

If you were to get the next path from a function call, it would look like this in Python:

def get_next_path():
    while True:
        yield 'A'
        yield 'B'

References

↑ Gray, Jim; Reuter, Andreas (1992). Transaction Processing: Concepts and Techniques (1 ed.). Morgan Kaufmann. pp. 508-509. ISBN 978-1-55860-190-1. https://archive.org/details/transactionproce0000gray.
↑ "ICMP Echo Request and Echo Reply messages". https://www.omnisecu.com/tcpip/icmp-echo-request-and-echo-reply.php.
↑ Swaminathan, K.; Lakshminarayanan, G.; Ko, Seok-Bum (December 2012). "High Speed Generic Network Interface for Network on Chip Using Ping Pong Buffers". 2012 International Symposium on Electronic System Design (ISED). pp. 72–76. doi:10.1109/ISED.2012.11. ISBN 978-1-4673-4704-4. https://ieeexplore.ieee.org/document/6526556.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Ping-pong scheme. Read more

[1] Gray, Jim; Reuter, Andreas (1992). Transaction Processing: Concepts and Techniques (1 ed.). Morgan Kaufmann. pp. 508-509. ISBN 978-1-55860-190-1. https://archive.org/details/transactionproce0000gray.

[2] "ICMP Echo Request and Echo Reply messages". https://www.omnisecu.com/tcpip/icmp-echo-request-and-echo-reply.php.

[3] Swaminathan, K.; Lakshminarayanan, G.; Ko, Seok-Bum (December 2012). "High Speed Generic Network Interface for Network on Chip Using Ping Pong Buffers". 2012 International Symposium on Electronic System Design (ISED). pp. 72–76. doi:10.1109/ISED.2012.11. ISBN 978-1-4673-4704-4. https://ieeexplore.ieee.org/document/6526556.

[1]

[2]

[3]