Ping-pong scheme
Encyclopedia
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.
s 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 eliminates this problem by alternatingly 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.
(ICMP). Through an "echo request" Computer A asks B to send back an "Echo response". These two messages are also sometimes called "ping
" and "pong".
, a Ping-Pong scheme is a simple algorithm for distributing data packets across
two paths.
If you had two paths
would randomly start with 1 of the paths and then switch back and forth
between the two.
If you were to get the next path from a function call, it would look like
this in Python
:
get_next_path:
while True:
yield 'A'
yield 'B'
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
. 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 transactionDatabase transaction
A transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
s are supported through a log file
Transaction log
In the field of databases in computer science, a transaction log is a history of actions executed by a database management system to guarantee ACID properties over crashes or hardware failures...
. 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
Block (data storage)
In computing , a block is a sequence of bytes or bits, having a nominal length . Data thus structured are said to be blocked. The process of putting data into blocks is called blocking. Blocking is used to facilitate the handling of the data-stream by the computer program receiving the data...
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
Crash (computing)
A crash in computing is a condition where a computer or a program, either an application or part of the operating system, ceases to function properly, often exiting after encountering errors. Often the offending program may appear to freeze or hang until a crash reporting service documents...
happens during that later write operation, previously stored log data may be lost.
The Ping-Pong scheme described in eliminates this problem by alternatingly 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.
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 ProtocolInternet Control Message Protocol
The Internet Control Message Protocol is one of the core protocols of the Internet Protocol Suite. It is chiefly used by the operating systems of networked computers to send error messages indicating, for example, that a requested service is not available or that a host or router could not be...
(ICMP). Through an "echo request" Computer A asks B to send back an "Echo response". These two messages are also sometimes called "ping
Ping
Ping is a computer network administration utility used to test the reachability of a host on an Internet Protocol network and to measure the round-trip time for messages sent from the originating host to a destination computer...
" and "pong".
Routing
In RoutingRouting
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
, 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 algorithmwould randomly start with 1 of the paths and then switch back and forth
between the two.
If you were to get the next path from a function call, it would look like
this in Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
:
get_next_path:
while True
yield 'B'