Ping-pong scheme

Last updated March 12, 2024

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:

defget_next_path():"""    This function is a generator that infinitely yields the strings "A" and "B" in an alternating sequence.    Yields:      str: The next string in the sequence, either "A" or "B".    """whileTrue:yield"A"yield"B"

Related Research Articles

The Internet Control Message Protocol (ICMP) is a supporting protocol in the Internet protocol suite. It is used by network devices, including routers, to send error messages and operational information indicating success or failure when communicating with another IP address, for example, an error is indicated when a requested service is not available or that a host or router could not be reached. ICMP differs from transport protocols such as TCP and UDP in that it is not typically used to exchange data between systems, nor is it regularly employed by end-user network applications.

ping is a computer network administration software utility used to test the reachability of a host on an Internet Protocol (IP) network. It is available for virtually all operating systems that have networking capability, including most embedded network administration software.

In computing, traceroute and tracert are computer network diagnostic commands for displaying possible routes (paths) and measuring transit delays of packets across an Internet Protocol (IP) network. The history of the route is recorded as the round-trip times of the packets received from each successive host in the route (path); the sum of the mean times in each hop is a measure of the total time spent to establish the connection. Traceroute proceeds unless all sent packets are lost more than twice; then the connection is lost and the route cannot be evaluated. Ping, on the other hand, only computes the final round-trip times from the destination point.

In telecommunications, round-trip delay (RTD) or round-trip time (RTT) is the amount of time it takes for a signal to be sent plus the amount of time it takes for acknowledgement of that signal having been received. This time delay includes propagation times for the paths between the two communication endpoints. In the context of computer networks, the signal is typically a data packet. RTT is commonly used interchangeably with ping time, which can be determined with the ping command. However, ping time may differ from experienced RTT with other protocols since the payload and priority associated with ICMP messages used by ping may differ from that of other traffic.

In computer science, ACID is a set of properties of database transactions intended to guarantee data validity despite errors, power failures, and other mishaps. In the context of databases, a sequence of database operations that satisfies the ACID properties is called a transaction. For example, a transfer of funds from one bank account to another, even involving multiple changes such as debiting one account and crediting another, is a single transaction.

A Smurf attack is a distributed denial-of-service attack in which large numbers of Internet Control Message Protocol (ICMP) packets with the intended victim's spoofed source IP are broadcast to a computer network using an IP broadcast address. Most devices on a network will, by default, respond to this by sending a reply to the source IP address. If the number of machines on the network that receive and respond to these packets is very large, the victim's computer will be flooded with traffic. This can slow down the victim's computer to the point where it becomes impossible to work on.

In computer science, Algorithms for Recovery and Isolation Exploiting Semantics, or ARIES, is a recovery algorithm designed to work with a no-force, steal database approach; it is used by IBM Db2, Microsoft SQL Server and many other database systems. IBM Fellow Dr. C. Mohan is the primary inventor of the ARIES family of algorithms.

In the field of databases in computer science, a transaction log is a history of actions executed by a database management system used to guarantee ACID properties over crashes or hardware failures. Physically, a log is a file listing changes to the database, stored in a stable storage format.

In transaction processing, databases, and computer networking, the two-phase commit protocol is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort the transaction. This protocol achieves its goal even in many cases of temporary system failure, and is thus widely used. However, it is not resilient to all possible failure configurations, and in rare cases, manual intervention is needed to remedy an outcome. To accommodate recovery from failure the protocol's participants use logging of the protocol's states. Log records, which are typically slow to generate but survive failures, are used by the protocol's recovery procedures. Many protocol variants exist that primarily differ in logging strategies and recovery mechanisms. Though usually intended to be used infrequently, recovery procedures compose a substantial portion of the protocol, due to many possible failure scenarios to be considered and supported by the protocol.

In computer science, data is any sequence of one or more symbols; datum is a single symbol of data. Data requires interpretation to become information. Digital data is data that is represented using the binary number system of ones (1) and zeros (0), instead of analog representation. In modern (post-1960) computer systems, all data is digital.

Replication in computing involves sharing information so as to ensure consistency between redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, or accessibility.

Real-Time Messaging Protocol (RTMP) is a communication protocol for streaming audio, video, and data over the Internet. Originally developed as a proprietary protocol by Macromedia for streaming between Flash Player and the Flash Communication Server, Adobe has released an incomplete version of the specification of the protocol for public use.

Packet loss occurs when one or more packets of data travelling across a computer network fail to reach their destination. Packet loss is either caused by errors in data transmission, typically across wireless networks, or network congestion. Packet loss is measured as a percentage of packets lost with respect to packets sent.

IP SLA is an active computer network measurement technology that was initially developed by Cisco Systems. IP SLA was previously known as Service Assurance Agent (SAA) or Response Time Reporter (RTR). IP SLA is used to track network performance like latency, ping response, and jitter, it also helps us to provide service quality.

An ICMP tunnel establishes a covert connection between two remote computers, using ICMP echo requests and reply packets. An example of this technique is tunneling complete TCP traffic over ping requests and replies.

A broadcast storm or broadcast radiation is the accumulation of broadcast and multicast traffic on a computer network. Extreme amounts of broadcast traffic constitute a broadcast storm. It can consume sufficient network resources so as to render the network unable to transport normal traffic. A packet that induces such a storm is occasionally nicknamed a Chernobyl packet.

Performance Monitor is a system monitoring program introduced in Windows NT 3.1. It monitors various activities on a computer such as CPU or memory usage. This type of application may be used to determine the cause of problems on a local or remote computer by measuring performance of hardware, software services, and applications. The program can define thresholds for alerts and automatic actions, generate reports, and view past performance data.

In computing, logging is the act of keeping a log of events that occur in a computer system, such as problems, errors or just information on current operations. These events may occur in the operating system or in other software. A message or log entry is recorded for each such event. These log messages can then be used to monitor and understand the operation of the system, to debug problems, or during an audit. Logging is particularly important in multi-user software, to have a central overview of the operation of the system.

BWPing is a tool to measure bandwidth and response times between two hosts using Internet Control Message Protocol (ICMP) echo request/echo reply mechanism. It does not require any special software on the remote host. The only requirement is the ability to respond on ICMP echo request messages. BWPing supports both IPv4 and IPv6 networks.

Network Performance Monitor (NPM) in Operations Management Suite, a component of Microsoft Azure, monitors network performance between office sites, data centers, clouds and applications in near real-time. It helps a network administrator locate and troubleshoot bottlenecks like network delay, data loss and availability of any network link across on-premises networks, Microsoft Azure VNets, Amazon Web Services VPCs, hybrid networks, VPNs or even public internet links.

References

↑ Gray, Jim; Reuter, Andreas (1992). Transaction Processing: Concepts and Techniques (1 ed.). Morgan Kaufmann. pp. 508-509. ISBN 978-1-55860-190-1.
↑ "ICMP Echo Request and Echo Reply messages". www.omnisecu.com. Retrieved 2023-07-04.
↑ 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. S2CID 23635498.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[2] "ICMP Echo Request and Echo Reply messages". www.omnisecu.com. Retrieved 2023-07-04.

[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. S2CID 23635498.

[1]

[2]

[3]