Asynchronous transfer mode
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Asynchronous Transfer
Mode
Asynchronous Transfer Mode (ATM) is
an International Telecommunication Union-Telecommunications Standards Section
(ITU-T) standard for cell relay wherein information for multiple service types,
such as voice, video, or data, is conveyed in small, fixed-size cells. ATM
networks are connection-oriented.
ATM is a cell-switching and multiplexing technology that combines the
benefits of circuit switching (guaranteed capacity and constant transmission
delay) with those of packet switching (flexibility and efficiency for
intermittent traffic). It provides scalable bandwidth from a few megabits per
second (Mbps) to many gigabits per second (Gbps). Because of its asynchronous
nature, ATM is more efficient than synchronous technologies, such as
time-division multiplexing (TDM).
With
TDM, each user is assigned to a time slot, and no other station can send in that
time slot. If a station has much data to send, it can send only when its time
slot comes up, even if all other time slots are empty. However, if a station has
nothing to transmit when its time slot comes up, the time slot is sent empty and
is wasted. Because ATM is asynchronous, time slots are available on demand with
information identifying the source of the transmission contained in the header
of each ATM cell.
ATM transfers information in fixed-size units called cells. Each
cell consists of 53 octets, or bytes. The first 5 bytes contain cell-header
information, and the remaining 48 contain the payload (user information). Small,
fixed-length cells are well suited to transferring voice and video traffic
because such traffic is intolerant of delays that result from having to wait for
a large data packet to download, among other things. Figure illustrates the
basic format of an ATM cell. Figure :An ATM Cell Consists of a Header and Payload
Data
ATM Protocol architecture:
ATM is almost similar to cell relay and packets witching
using X.25and framerelay.like packet switching and frame relay,ATM involves the
transfer of data in discrete pieces.also,like packet switching and frame relay
,ATM allows multiple logical connections to multiplexed over a single physical
interface. in the case of ATM,the information flow on each logical connection
is organised into fixed-size packets, called cells. ATM is a streamlined
protocol with minimal error and flow control capabilities :this reduces the
overhead of processing ATM cells and reduces the number of overhead bits
required with each cell, thus enabling ATM to operate at high data rates.the
use of fixed-size cells simplifies the processing required at each ATM
node,again supporting the use of ATM at high data rates. The
ATM architecture uses a logical model to describe the functionality that it
supports. ATM functionality corresponds to the physical layer and part of the
data link layer of the OSI reference model. . the protocol referencce model
shown makes reference to three separate planes:
user plane provides for user information transfer ,along with
associated controls (e.g.,flow control ,error control).
control
plane performs call control and connection control functions.
management
plane includes plane management ,which performs management function related
to a system as a whole and provides coordination between all the planes ,and
layer management which performs management functions relating to resource and
parameters residing in its protocol entities .
•
•
•
Finally, the
higher layers residing above the AAL accept user data, arrange it into packets,
and hand it to the AAL. Figure :illustrates the ATM reference model.
Structure of an ATM cell
An ATM cell consists of a 5 byte header and a 48
byte payload. The payload size of 48 bytes was a compromise between the needs
of voice telephony and packet networks, obtained by a simple averaging of the
US proposal of 64 bytes and European proposal of 32, said by some to be motivated
by a European desire not to need echo-cancellers on national trunks.
ATM defines two different cell formats: NNI
(Network-network interface) and UNI (User-network interface). Most ATM links
use UNI cell format.
GFC = Generic Flow Control
(4 bits) (default: 4-zero bits)
VPI = Virtual Path Identifier (8 bits UNI) or (12
bits NNI)
VCI = Virtual channel identifier (16 bits)
PT = Payload Type (3
bits)
CLP = Cell Loss Priority (1-bit)
HEC = Header Error Correction (8-bit CRC,
polynomial = X8 + X2 + X + 1)
The PT field is used to designate various special
kinds of cells for Operation and
Management (OAM) purposes, and to delineate packet boundaries in
some AALs.
Several of ATM's link protocols use the HEC field
to drive a CRC-Based Framing algorithm, which allows the
position of the ATM cells to be found with no overhead required beyond what is
otherwise needed for header protection. The 8-bit CRC is used to correct
single-bit header errors and detect multi-bit header errors. When multi-bit header
errors are detected, the current and subsequent cells are dropped until a cell
with no header errors is found.
In a UNI cell the GFC field is reserved for a
local flow control/submultiplexing system between users. This was intended to
allow several terminals to share a single network connection, in the same way
that two ISDN phones can share a single basic rate ISDN connection. All four
GFC bits must be zero by default.The NNI cell format is almost identical to the
UNI format, except that the 4-bit GFC field is re-allocated to the VPI field,
extending the VPI to 12 bits. Thus, a single NNI ATM interconnection is capable
of addressing almost 212 VPs of up to almost 216 VCs each
(in practice some of the VP and VC numbers are reserved).
A Virtual Channel (VC) denotes the
transport of ATM cells which have the same unique identifier, called the
Virtual Channel Identifier (VCI). This identifier is encoded in the cell
header. A virtual channel represents the basic means of communication between
two end-points, and is analogous to an X.25 virtual circuit.
A Virtual Path (VP) denotes the transport of ATM cells belonging to
virtual channels which share a common identifier, called the Virtual Path
Identifier (VPI), which is also encoded in the cell header. A virtual path, in
other words, is a grouping of virtual channels which connect the same
end-points. This two layer approach results in improved network performance.
Once a virtual path is set up, the addition/removal of virtual channels is
straightforward
ATM Classes of Services
ATM
is connection oriented and allows the user to specify the resources required on
a per-connection basis (per SVC) dynamically. There are the five classes of
service defined for ATM (as per ATM Forum UNI 4.0 specification). The QoS parameters
for these service classes are summarized in Table 1.
Benefits of ATM
The benefits of ATM are the following:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Monday, October 1, 2012
COMPUTER NETWORK LECTURE NOTES-- Asynchronous transfer mode (ATM)
COMPUTER NETWORK LECTURE NOTES-- Frame RelayNetworks
Frame RelayNetworks
|
Frame relay Networks
Frame Relay often is
described as a streamlined version of X.25, offering fewer of the robust
capabilities, such as windowing and retransmission of last data that are offered
in X.25.
Frame Relay Devices
DTEs generally are
considered to be terminating equipment for a specific network and typically are
located on the premises of a customer. In fact, they may be owned by the
customer. Examples of DTE devices are terminals, personal computers, routers,
and bridges.
DCEs are carrier-owned
internetworking devices. The purpose of DCE equipment is to provide clocking and
switching services in a network, which are the devices that actually transmit
data through the WAN. In most cases, these are packet switches. Figure 10-1
shows the relationship between the two categories of devices.
Standard Frame Relay Frame
Each frame relay PDU consists of the following
fields:
Frame Check Sequence (FCS) Field. Since one cannot completely ignore the
bit error-rate of the medium, each switching node needs to implement error
detection to avoid wasting bandwidth due to the transmission of erred frames. The error detection mechanism used in frame relay uses the cyclic redundancy check (CRC) as its basis.
Congestion-Control
Mechanisms
Frame Relay reduces
network overhead by implementing simple congestion-notification mechanisms
rather than explicit, per-virtual-circuit flow control. Frame Relay typically is
implemented on reliable network media, so data integrity is not sacrificed
because flow control can be left to higher-layer protocols. Frame Relay
implements two congestion-notification mechanisms:
•
Frame Relay versus X.25
The design of X.25 aimed to provide error-free delivery
over links with high error-rates. Frame relay takes advantage of the new links
with lower error-rates, enabling it to eliminate many of the services provided
by X.25. The elimination of functions and fields, combined with digital links,
enables frame relay to operate at speeds 20 times greater than
X.25.
X.25 specifies processing at layers 1, 2 and 3 of the OSI
model, while frame relay operates at layers 1 and 2 only. This means that frame
relay has significantly less processing to do at each node, which improves
throughput by an order of magnitude.
X.25 prepares and sends packets, while frame relay
prepares and sends frames. X.25 packets contain several fields used for error
and flow control, none of which frame relay needs. The frames in frame relay
contain an expanded address field that enables frame relay nodes to direct
frames to their destinations with minimal processing
.
X.25 has a fixed bandwidth available. It uses or wastes
portions of its bandwidth as the load dictates. Frame relay can dynamically
allocate bandwidth during call setup negotiation at both the physical and
logical channel level.
|
Paxos algorithm (computer science)
Paxos (computer science)
Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures.[1]
Consensus protocols are the basis for the state machine approach to distributed computing, as suggested by Leslie Lamport[2] and surveyed by Fred Schneider.[3] The state machine approach is a technique for converting an algorithm into a fault-tolerant, distributed implementation. Ad-hoc techniques may leave important cases of failures unresolved. The principled approach proposed by Lamport et al. ensures all cases are handled safely.
The Paxos protocol was first published in 1989 and named after a fictional legislative consensus system used on the Paxos island in Greece.[4] It was later published as a journal article in 1998.[5]
The Paxos family of protocols includes a spectrum of trade-offs between the number of processors, number of message delays before learning the agreed value, the activity level of individual participants, number of messages sent, and types of failures. Although no deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous network (a result proved in a paper by Fischer, Lynch and Paterson[6]), Paxos guarantees safety (freedom from inconsistency), and the conditions that could prevent it from making progress are difficult to provoke.[5][7][8][9][10]
Paxos is normally used in situations requiring durability (for example, to replicate a file or a database), in which the amount of durable state could be large. The protocol attempts to make progress even during periods when some bounded number of replicas are unresponsive. However, a reconfiguration mechanism is available, and can be used to drop a permanently failed replica, or to add new replicas to the group.
Reconfigurable state machines have strong ties to prior work on reliable group multicast protocols that support dynamic group membership, for example Birman's virtually synchronous gbcast[13] protocol. However, it should be noted that gbcast is unusual in supporting durability and addressing partitioning failures. Most reliable multicast protocols lack these properties, which are required for implementations of the state machine replication model. This point is elaborated in a paper by Lamport, Malkhi and Zhou.[14]
Quorums are defined as subsets of the set of Acceptors such that any two subsets (that is, any two Quorums) share at least one member. Typically, a Quorum is any majority of participating Acceptors. For example, given the set of Acceptors {A,B,C,D}, a majority Quorum would be any three Acceptors: {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}. More generally, arbitrary positive weights can be assigned to Acceptors and a Quorum defined as any subset of Acceptors with the summary weight greater than half of the total weight of all Acceptors.
By merging roles, the protocol "collapses" into an efficient client-master-replica style deployment, typical of the database community. The benefit of the Paxos protocols (including implementations with merged roles) is the guarantee of its safety properties.
A typical implementation's message flow is covered in the section Typical Multi-Paxos deployment.
If the leader is relatively stable, phase 1 becomes unnecessary. Thus, it is possible to skip phase 1 for future instances of the protocol with the same leader.
To achieve this, the instance number I is included along with each value. Multi-Paxos reduces the failure-free message delay (proposal to learning) from 4 delays to 2 delays.
This reduction in processor requirements comes at the expense of liveness; if too many main processors fail in a short time, the system must halt until the auxiliary processors can reconfigure the system. During stable periods, the auxiliary processors take no part in the protocol.
Intuitively, if the leader has no value to propose, then a client could send an Accept! message to the Acceptors directly. The Acceptors would respond as in Basic Paxos, sending Accepted messages to the leader and every Learner achieving two message delays from Client to Learner.
If the leader detects a collision, it resolves the collision by sending Accept! messages for a new round which are Accepted as usual. This coordinated recovery technique requires four message delays from Client to Learner.
The final optimization occurs when the leader specifies a recovery technique in advance, allowing the Acceptors to perform the collision recovery themselves. Thus, uncoordinated collision recovery can occur in three message delays (and only two message delays if all Learners are also Acceptors).
In such cases, the conflicting operations can both be accepted, avoiding the delays required for resolving conflicts and re-proposing the rejected operation.
This concept is further generalized into ever-growing sets of commutative operations, some of which are known to be stable (and thus may be executed). The protocol tracks these sets of operations, ensuring that all proposed commutative operations of one set are stabilized before allowing any non-commuting operation to become stable.
Note X in this table indicates operations which are non-commutative.
Byzantine Paxos[8][10] adds an extra message (Verify) which acts to distribute knowledge and verify the actions of the other processors:
Note the Accepted message in Fast Byzantine Paxos is sent to all Acceptors and all Learners, while Fast Paxos sends Accepted messages only to Learners):
Consensus protocols are the basis for the state machine approach to distributed computing, as suggested by Leslie Lamport[2] and surveyed by Fred Schneider.[3] The state machine approach is a technique for converting an algorithm into a fault-tolerant, distributed implementation. Ad-hoc techniques may leave important cases of failures unresolved. The principled approach proposed by Lamport et al. ensures all cases are handled safely.
The Paxos protocol was first published in 1989 and named after a fictional legislative consensus system used on the Paxos island in Greece.[4] It was later published as a journal article in 1998.[5]
The Paxos family of protocols includes a spectrum of trade-offs between the number of processors, number of message delays before learning the agreed value, the activity level of individual participants, number of messages sent, and types of failures. Although no deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous network (a result proved in a paper by Fischer, Lynch and Paterson[6]), Paxos guarantees safety (freedom from inconsistency), and the conditions that could prevent it from making progress are difficult to provoke.[5][7][8][9][10]
Paxos is normally used in situations requiring durability (for example, to replicate a file or a database), in which the amount of durable state could be large. The protocol attempts to make progress even during periods when some bounded number of replicas are unresponsive. However, a reconfiguration mechanism is available, and can be used to drop a permanently failed replica, or to add new replicas to the group.
Contents
|
History
The topic predates the protocol. In 1988, Lynch, Dwork and Stockmeyer had demonstrated [11] the solvability of consensus in a broad family of "partially synchronous" systems. Paxos has strong similarities to a protocol used for agreement in viewstamped replication, first published by Oki and Liskov in 1988, in the context of distributed transactions.[12] Notwithstanding this prior work, Paxos offered a particularly elegant formalism, and included one of the earliest proofs of safety for a fault-tolerant distributed consensus protocol.Reconfigurable state machines have strong ties to prior work on reliable group multicast protocols that support dynamic group membership, for example Birman's virtually synchronous gbcast[13] protocol. However, it should be noted that gbcast is unusual in supporting durability and addressing partitioning failures. Most reliable multicast protocols lack these properties, which are required for implementations of the state machine replication model. This point is elaborated in a paper by Lamport, Malkhi and Zhou.[14]
Assumptions
In order to simplify the presentation of Paxos, the following assumptions and definitions are made explicit. Techniques to broaden the applicability are known in the literature, and are not covered in this article; please see references for further reading.Processors
- Processors operate at arbitrary speed.
- Processors may experience failures.
- Processors with stable storage may re-join the protocol after failures (following a crash-recovery failure model).
- Processors do not collude, lie, or otherwise attempt to subvert the protocol. (That is, Byzantine failures don't occur. See Byzantine Paxos for a solution that tolerates failures that arise from arbitrary/malicious behavior of the processes.)
Network
- Processors can send messages to any other processor.
- Messages are sent asynchronously and may take arbitrarily long to deliver.
- Messages may be lost, reordered, or duplicated.
- Messages are delivered without corruption. (That is, Byzantine failures don't occur. See Byzantine Paxos for a solution which tolerates corrupted messages that arise from arbitrary/malicious behavior of the messaging channels.)
Number of processors
In general, a consensus algorithm can make progress using 2F+1 processors despite the simultaneous failure of any F processors.[15] However, using reconfiguration, a protocol may be employed which survives any number of total failures as long as no more than F fail simultaneously.Roles
Paxos describes the actions of the processes by their roles in the protocol: client, acceptor, proposer, learner, and leader. In typical implementations, a single processor may play one or more roles at the same time. This does not affect the correctness of the protocol—it is usual to coalesce roles to improve the latency and/or number of messages in the protocol.- Client
- The Client issues a request to the distributed system, and waits for a response. For instance, a write request on a file in a distributed file server.
- Acceptor (Voters)
- The Acceptors act as the fault-tolerant "memory" of the protocol. Acceptors are collected into groups called Quorums. Any message sent to an Acceptor must be sent to a Quorum of Acceptors. Any message received from an Acceptor is ignored unless a copy is received from each Acceptor in a Quorum.
- Proposer
- A Proposer advocates a client request, attempting to convince the Acceptors to agree on it, and acting as a coordinator to move the protocol forward when conflicts occur.
- Learner
- Learners act as the replication factor for the protocol. Once a Client request has been agreed on by the Acceptors, the Learner may take action (i.e.: execute the request and send a response to the client). To improve availability of processing, additional Learners can be added.
- Leader
- Paxos requires a distinguished Proposer (called the leader) to make progress. Many processes may believe they are leaders, but the protocol only guarantees progress if one of them is eventually chosen. If two processes believe they are leaders, they may stall the protocol by continuously proposing conflicting updates. However, the safety properties are still preserved on that case.
Quorums
Quorums express the safety properties of Paxos by ensuring at least some surviving processor retains knowledge of the results.Quorums are defined as subsets of the set of Acceptors such that any two subsets (that is, any two Quorums) share at least one member. Typically, a Quorum is any majority of participating Acceptors. For example, given the set of Acceptors {A,B,C,D}, a majority Quorum would be any three Acceptors: {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}. More generally, arbitrary positive weights can be assigned to Acceptors and a Quorum defined as any subset of Acceptors with the summary weight greater than half of the total weight of all Acceptors.
Proposal Number & Agreed Value
Each attempt to define an agreed value v is performed with proposals which may or may not be accepted by Acceptors. Each proposal is uniquely numbered for a given Proposer. The value corresponding to a numbered proposal can be computed as part of running the Paxos protocol, but does not have to.Safety and liveness properties
In order to guarantee safety, Paxos defines three safety properties and ensures they are always held, regardless of the pattern of failures:- Non-triviality
- Only proposed values can be learned.[8]
- Consistency
- At most one value can be learned (i.e., two different learners cannot learn different values).[8][9]
- Liveness(C;L)
- If value C has been proposed, then eventually learner L will learn some value (if sufficient processors remain non-faulty).[9]
Typical deployment
In most deployments of Paxos, each participating process acts in three roles; Proposer, Acceptor and Learner.[16] This reduces the message complexity significantly, without sacrificing correctness:| “ | In Paxos, clients send commands to a leader. During normal operation, the leader receives a client's command, assigns it a new command number i, and then begins the ith instance of the consensus algorithm by sending messages to a set of acceptor processes.[9] | ” |
A typical implementation's message flow is covered in the section Typical Multi-Paxos deployment.
Basic Paxos
This protocol is the most basic of the Paxos family. Each instance of the Basic Paxos protocol decides on a single output value. The protocol proceeds over several rounds. A successful round has two phases. A Proposer should not initiate Paxos if it cannot communicate with at least a Quorum of Acceptors:Phase 1a: Prepare
- A Proposer (the leader) creates a proposal identified with a number N. This number must be greater than any previous proposal number used by this Proposer. Then, it sends a Prepare message containing this proposal to a Quorum of Acceptors.
Phase 1b: Promise
- If the proposal's number N is higher than any previous proposal number received from any Proposer by the Acceptor, then the Acceptor must return a promise to ignore all future proposals having a number less than N. If the Acceptor accepted a proposal at some point in the past, it must include the previous proposal number and previous value in its response to the Proposer.
- Otherwise, the Acceptor can ignore the received proposal. It does not have to answer in this case for Paxos to work. However, for the sake of optimization, sending a denial (Nack) response would tell the Proposer that it can stop its attempt to create consensus with proposal N.
Phase 2a: Accept Request
- If a Proposer receives enough promises from a Quorum of Acceptors, it needs to set a value to its proposal. If any Acceptors had previously accepted any proposals, then they'll have sent their values to the Proposer, who now must set the value of its proposal to the value associated with the highest proposal number reported by the Acceptors. If none of the Acceptors had accepted a proposal up to this point, then the Proposer may choose any value for its proposal.[17]
- The Proposer sends an Accept Request message to a Quorum of Acceptors with the chosen value for its proposal.
Phase 2b: Accepted
- If an Acceptor receives an Accept Request message for a proposal N, it must accept it if and only if it has not already promised to only consider proposals having an identifier greater than N. In this case, it should register the corresponding value v and send an Accepted message to the Proposer and every Learner. Else, it can ignore the Accept Request.
- Rounds fail when multiple Proposers send conflicting Prepare messages, or when the Proposer does not receive a Quorum of responses (Promise or Accepted). In these cases, another round must be started with a higher proposal number.
- Notice that when Acceptors accept a request, they also acknowledge the leadership of the Proposer. Hence, Paxos can be used to select a leader in a cluster of nodes.
- Here is a graphic representation of the Basic Paxos protocol. Note that the values returned in the Promise message are null the first time a proposal is made, since no Acceptor has accepted a value before in this round.
Message flow: Basic Paxos
(first round is successful) Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| |<---------X--X--X | | Promise(1,{null,null,null})
| X--------->|->|->| | | Accept!(1,V)
| |<---------X--X--X------>|->| Accepted(1,V)
|<---------------------------------X--X Response
| | | | | | |
Error cases in basic Paxos
The simplest error cases are the failure of a redundant Learner, or failure of an Acceptor when a Quorum of Acceptors remains live. In these cases, the protocol requires no recovery. No additional rounds or messages are required, as shown below:Message flow: Basic Paxos, failure of Acceptor
(Quorum size = 2 Acceptors) Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| | | | ! | | !! FAIL !!
| |<---------X--X | | Promise(1,{null,null, null})
| X--------->|->| | | Accept!(1,V)
| |<---------X--X--------->|->| Accepted(1,V)
|<---------------------------------X--X Response
| | | | | |
Message flow: Basic Paxos, failure of redundant Learner
Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| |<---------X--X--X | | Promise(1,{null,null,null})
| X--------->|->|->| | | Accept!(1,V)
| |<---------X--X--X------>|->| Accepted(1,V)
| | | | | | ! !! FAIL !!
|<---------------------------------X Response
| | | | | |
The next failure case is when a Proposer fails after proposing a value, but before agreement is reached. Ignoring Leader election, an example message flow is as follows:Message flow: Basic Paxos, failure of Proposer
(re-election not shown, one instance, two rounds)Client Leader Acceptor Learner
| | | | | | |
X----->| | | | | | Request
| X------------>|->|->| | | Prepare(1)
| |<------------X--X--X | | Promise(1,{null, null, null})
| | | | | | |
| | | | | | | !! Leader fails during broadcast !!
| X------------>| | | | | Accept!(1,Va)
| ! | | | | |
| | | | | | | !! NEW LEADER !!
| X--------->|->|->| | | Prepare(2)
| |<---------X--X--X | | Promise(2,{null, null, null})
| X--------->|->|->| | | Accept!(2,V)
| |<---------X--X--X------>|->| Accepted(2,V)
|<---------------------------------X--X Response
| | | | | | |
The most complex case is when multiple Proposers believe themselves to be Leaders. For instance the current leader may fail and later recover, but the other Proposers have already re-elected a new leader. The recovered leader has not learned this yet and attempts to begin a round in conflict with the current leader.Message flow: Basic Paxos, dueling Proposers
(one instance, four unsuccessful rounds)Client Proposer Acceptor Learner
| | | | | | |
X----->| | | | | | Request
| X------------>|->|->| | | Prepare(1)
| |<------------X--X--X | | Promise(1,{null,null,null})
| ! | | | | | !! LEADER FAILS
| | | | | | | !! NEW LEADER (knows last number was 1)
| X--------->|->|->| | | Prepare(2)
| |<---------X--X--X | | Promise(2,{null,null,null})
| | | | | | | | !! OLD LEADER recovers
| | | | | | | | !! OLD LEADER tries 2, denied
| X------------>|->|->| | | Prepare(2)
| |<------------X--X--X | | Nack(2)
| | | | | | | | !! OLD LEADER tries 3
| X------------>|->|->| | | Prepare(3)
| |<------------X--X--X | | Promise(3,{null,null,null})
| | | | | | | | !! NEW LEADER proposes, denied
| | X--------->|->|->| | | Accept!(2,Va)
| | |<---------X--X--X | | Nack(3)
| | | | | | | | !! NEW LEADER tries 4
| | X--------->|->|->| | | Prepare(4)
| | |<---------X--X--X | | Promise(4,{null,null,null})
| | | | | | | | !! OLD LEADER proposes, denied
| X------------>|->|->| | | Accept!(3,Vb)
| |<------------X--X--X | | Nack(4)
| | | | | | | | ... and so on ...
Multi-Paxos
A typical deployment of Paxos requires a continuous stream of agreed values acting as commands to a distributed state machine. If each command is the result of a single instance of the Basic Paxos protocol, a significant amount of overhead would result.If the leader is relatively stable, phase 1 becomes unnecessary. Thus, it is possible to skip phase 1 for future instances of the protocol with the same leader.
To achieve this, the instance number I is included along with each value. Multi-Paxos reduces the failure-free message delay (proposal to learning) from 4 delays to 2 delays.
Message flow: Multi-Paxos, start
(first instance with new leader) Client Proposer Acceptor Learner
| | | | | | | --- First Request ---
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(N)
| |<---------X--X--X | | Promise(N,I,{Va,Vb,Vc})
| X--------->|->|->| | | Accept!(N,I,Vm)
| |<---------X--X--X------>|->| Accepted(N,I,Vm)
|<---------------------------------X--X Response
| | | | | | |
Vm = last of (Va, Vb, Vc)Message flow: Multi-Paxos, steady-state
(subsequent instances with same leader)Client Proposer Acceptor Learner | | | | | | | --- Following Requests --- X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N,I+1,W) | |<---------X--X--X------>|->| Accepted(N,I+1,W) |<---------------------------------X--X Response | | | | | | |
Typical Multi-Paxos deployment
The most common deployment of the Paxos family is Multi-Paxos,[16] specialized for participating processors to each be Proposers, Acceptors and Learners. The message flow may be optimized as depicted here:Message flow: Collapsed Multi-Paxos, start
(first instance with new leader) Client Servers
| | | | --- First Request ---
X-------->| | | Request
| X->|->| Prepare(N)
| |<-X--X Promise(N,I,{Va,Vb,Vc})
| X->|->| Accept!(N,I,Vn)
| |<-X--X Accepted(N,I)
|<--------X | | Response
| | | |
Message flow: Collapsed Multi-Paxos, steady state
(subsequent instances with same leader)Client Servers X-------->| | | Request | X->|->| Accept!(N+1,I,W) | |<-X--X Accepted(N+1,I) |<--------X | | Response | | | |
Optimizations
A number of optimizations reduce message complexity and size. These optimizations are summarized below:-
- "We can save messages at the cost of an extra message delay by having a single distinguished learner that informs the other learners when it finds out that a value has been chosen. Acceptors then send Accepted messages only to the distinguished learner. In most applications, the roles of leader and distinguished learner are performed by the same processor.
-
- "A leader can send its Prepare and Accept! messages just to a quorum of acceptors. As long as all acceptors in that quorum are working and can communicate with the leader and the learners, there is no need for acceptors not in the quorum to do anything.
-
- "Acceptors do not care what value is chosen. They simply respond to Prepare and Accept! messages to ensure that, despite failures, only a single value can be chosen. However, if an acceptor does learn what value has been chosen, it can store the value in stable storage and erase any other information it has saved there. If the acceptor later receives a Prepare or Accept! message, instead of performing its Phase1b or Phase2b action, it can simply inform the leader of the chosen value.
-
- "Instead of sending the value v, the leader can send a hash of v to some acceptors in its Accept! messages. A learner will learn that v is chosen if it receives Accepted messages for either v or its hash from a quorum of acceptors, and at least one of those messages contains v rather than its hash. However, a leader could receive Promise messages that tell it the hash of a value v that it must use in its Phase2a action without telling it the actual value of v. If that happens, the leader cannot execute its Phase2a action until it communicates with some process that knows v."[7]
-
- "A proposer can send its proposal only to the leader rather than to all coordinators. However, this requires that the result of the leader-selection algorithm be broadcast to the proposers, which might be expensive. So, it might be better to let the proposer send its proposal to all coordinators. (In that case, only the coordinators themselves need to know who the leader is.)
-
- "Instead of each acceptor sending Accepted messages to each learner, acceptors can send their Accepted messages to the leader and the leader can inform the learners when a value has been chosen. However, this adds an extra message delay.
-
- "Finally, observe that phase 1 is unnecessary for round 1 .. The leader of round 1 can begin the round by sending an Accept! message with any proposed value."[8]
Cheap Paxos
Cheap Paxos extends Basic Paxos to tolerate F failures with F+1 main processors and F auxiliary processors by dynamically reconfiguring after each failure.This reduction in processor requirements comes at the expense of liveness; if too many main processors fail in a short time, the system must halt until the auxiliary processors can reconfigure the system. During stable periods, the auxiliary processors take no part in the protocol.
-
- "With only two processors p and q, one processor cannot distinguish failure of the other processor from failure of the communication medium. A third processor is needed. However, that third processor does not have to participate in choosing the sequence of commands. It must take action only in case p or q fails, after which it does nothing while either p or q continues to operate the system by itself. The third processor can therefore be a small/slow/cheap one, or a processor primarily devoted to other tasks."[7]
Message flow: Cheap Multi-Paxos
3 main Acceptors, 1 Auxiliary Acceptor, Quorum size = 3, showing failure of one main processor and subsequent reconfiguration { Acceptors }
Proposer Main Aux Learner
| | | | | | -- Phase 2 --
X----------->|->|->| | | Accept!(N,I,V)
| | | ! | | --- FAIL! ---
|<-----------X--X--------------->| Accepted(N,I,V)
| | | | | -- Failure detected (only 2 accepted) --
X----------->|->|------->| | Accept!(N,I,V) (re-transmit, include Aux)
|<-----------X--X--------X------>| Accepted(N,I,V)
| | | | | -- Reconfigure : Quorum = 2 --
X----------->|->| | | Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->| Accepted(N,I+1,W)
| | | | |
Fast Paxos
Fast Paxos generalizes Basic Paxos to reduce end-to-end message delays. In Basic Paxos, the message delay from client request to learning is 3 message delays. Fast Paxos allows 2 message delays, but requires the Client to send its request to multiple destinations.Intuitively, if the leader has no value to propose, then a client could send an Accept! message to the Acceptors directly. The Acceptors would respond as in Basic Paxos, sending Accepted messages to the leader and every Learner achieving two message delays from Client to Learner.
If the leader detects a collision, it resolves the collision by sending Accept! messages for a new round which are Accepted as usual. This coordinated recovery technique requires four message delays from Client to Learner.
The final optimization occurs when the leader specifies a recovery technique in advance, allowing the Acceptors to perform the collision recovery themselves. Thus, uncoordinated collision recovery can occur in three message delays (and only two message delays if all Learners are also Acceptors).
Message flow: Fast Paxos, non-conflicting
Client Leader Acceptor Learner | | | | | | | | | X--------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | X------------------->|->|->|->| | | Accept!(N,I,W) | |<---------X--X--X--X------>|->| Accepted(N,I,W) |<------------------------------------X--X Response(W) | | | | | | | |
Message flow: Fast Paxos, conflicting proposals
Conflicting proposals with uncoordinated recovery. Note: the protocol does not specify how to handle the dropped client request.Client Leader Acceptor Learner | | | | | | | | | | | X------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | | | | | | | | | | | !! Concurrent conflicting proposals | | | | | | | | | !! received in different order | | | | | | | | | !! by the Acceptors | X--------------?|-?|-?|-?| | | Accept!(N,I,V) X-----------------?|-?|-?|-?| | | Accept!(N,I,W) | | | | | | | | | | | | | | | | | | !! Acceptors disagree on value | | |<-------X--X->|->|----->|->| Accepted(N,I,V) | | |<-------|<-|<-X--X----->|->| Accepted(N,I,W) | | | | | | | | | | | | | | | | | | !! Detect collision & recover | | |<-------X--X--X--X----->|->| Accepted(N+1,I,W) |<---------------------------------X--X Response(W) | | | | | | | | |
Message flow: Fast Paxos, collapsed roles
(merged Acceptor/Learner roles)Client Servers | | | | | | | | X->|->|->| Any(N,I,Recovery) | | | | | | | | | | | | !! Concurrent conflicting proposals | | | | | | !! received in different order | | | | | | !! by the Servers | X--------?|-?|-?|-?| Accept!(N,I,V) X-----------?|-?|-?|-?| Accept!(N,I,W) | | | | | | | | | | | | !! Servers disagree on value | | X--X->|->| Accepted(N,I,V) | | |<-|<-X--X Accepted(N,I,W) | | | | | | | | | | | | !! Detect collision & recover |<-----------X--X--X--X Response(W) | | | | | |
Generalized Paxos
Generalized consensus explores the relationship between the operations of a distributed state machine and the consensus protocol used to maintain consistency of that state machine. The main discovery involves optimizations of the consensus protocol when conflicting proposals could be applied to the state machine in any order. i.e.: The operations proposed by the conflicting proposals are commutative operations of the state machine.In such cases, the conflicting operations can both be accepted, avoiding the delays required for resolving conflicts and re-proposing the rejected operation.
This concept is further generalized into ever-growing sets of commutative operations, some of which are known to be stable (and thus may be executed). The protocol tracks these sets of operations, ensuring that all proposed commutative operations of one set are stabilized before allowing any non-commuting operation to become stable.
Example
- In order to illustrate Generalized Paxos, this example shows a message flow between two concurrently executing clients and a distributed state machine performing the operations of a read/write register with 2 independent register addresses (A and B).
| Read(A) | Write(A) | Read(B) | Write(B) | |
|---|---|---|---|---|
| Read(A) | X | |||
| Write(A) | X | X | ||
| Read(B) | X | |||
| Write(B) | X | X |
- Proposed Series of operations (global order):
1:Read(A)
2:Read(B)
3:Write(B)
4:Read(B)
5:Read(A)
6:Write(A)
7:Read(A)
- One possible permutation allowed by commutes:
{ 1:Read(A), 2:Read(B), 5:Read(A) }
{ 3:Write(B), 6:Write(A) }
{ 4:Read(B), 7:Read(A) }
- Observations:
5:Read(A)may commute in front of3:Write(B)/4:Read(B)pair.4:Read(B)may commute behind the3:Write(B)/6:Write(A)pair.- In practice, a commute occurs only when operations are proposed concurrently.
Message flow: Generalized Paxos (example)
Responses not shown. Note: message abbreviations differ from previous message flows due to specifics of the protocol, see [9] for a full discussion. { Acceptors }
Client Leader Acceptor Learner
| | | | | | | | !! New Leader Begins Round
| | X----->|->|->| | | Prepare(N)
| | |<-----X--X--X | | Promise(N,null)
| | X----->|->|->| | | Phase2Start(N,null)
| | | | | | | |
| | | | | | | | !! Concurrent commuting proposals
| X--------?|-----?|-?|-?| | | Propose(ReadA)
X-----------?|-----?|-?|-?| | | Propose(ReadB)
| | X------X-------------->|->| Accepted(N,<ReadA,ReadB>)
| | |<--------X--X-------->|->| Accepted(N,<ReadB,ReadA>)
| | | | | | | |
| | | | | | | | !! No Conflict, both accepted
| | | | | | | | Stable = <ReadA, ReadB>
| | | | | | | |
| | | | | | | | !! Concurrent conflicting proposals
X-----------?|-----?|-?|-?| | | Propose(<WriteB,ReadA>)
| X--------?|-----?|-?|-?| | | Propose(ReadB)
| | | | | | | |
| | X------X-------------->|->| Accepted(N,<WriteB,ReadA> . <ReadB>)
| | |<--------X--X-------->|->| Accepted(N,<ReadB> . <WriteB,ReadA>)
| | | | | | | |
| | | | | | | | !! Conflict detected, leader chooses
| | | | | | | | commutative order:
| | | | | | | | V = <ReadA, WriteB, ReadB>
| | | | | | | |
| | X----->|->|->| | | Phase2Start(N+1,V)
| | |<-----X--X--X-------->|->| Accepted(N+1,V)
| | | | | | | | Stable = <ReadA, ReadB> .
| | | | | | | | <ReadA, WriteB, ReadB>
| | | | | | | |
| | | | | | | | !! More conflicting proposals
X-----------?|-----?|-?|-?| | | Propose(WriteA)
| X--------?|-----?|-?|-?| | | Propose(ReadA)
| | | | | | | |
| | X------X-------------->|->| Accepted(N+2,<WriteA> . <ReadA>)
| | |<--------X--X-------->|->| Accepted(N+2,<ReadA> . <WriteA>)
| | | | | | | |
| | | | | | | | !! Leader chooses order W
| | X----->|->|->| | | Phase2Start(N+2,W)
| | |<-----X--X--X-------->|->| Accepted(N+2,W)
| | | | | | | | Stable = <ReadA, ReadB> .
| | | | | | | | <ReadA, WriteB, ReadB> .
| | | | | | | | <WriteA, ReadA>
| | | | | | | |
Generalized Paxos vs. Fast Multi-Paxos
- The message flow above shows Generalized Paxos performing agreement on seven values in (nominally) 10 message delays. Fast Multi-Paxos would require 15-17 delays for the same sequence (3 delays for each of the three concurrent proposals with uncoordinated recovery, plus at least 2 delays for the eventual re-submission of the three rejected proposals, concurrent re-proposals may add two additional delays).
Byzantine Paxos
Paxos may also be extended to support arbitrary failures of the participants, including lying, fabrication of messages, collusion with other participants, selective non-participation, etc. These types of failures are called Byzantine failures, after the solution popularized by Lamport.[18]Byzantine Paxos[8][10] adds an extra message (Verify) which acts to distribute knowledge and verify the actions of the other processors:
Message flow: Byzantine Multi-Paxos, steady state
Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N,I,V) | | X<>X<>X | | Verify(N,I,V) - BROADCAST | |<---------X--X--X------>|->| Accepted(N,V) |<---------------------------------X--X Response(V) | | | | | | |Fast Byzantine Paxos removes this extra delay, since the client sends commands directly to the Acceptors.[8]
Note the Accepted message in Fast Byzantine Paxos is sent to all Acceptors and all Learners, while Fast Paxos sends Accepted messages only to Learners):
Message flow: Fast Byzantine Multi-Paxos, steady state
Client Acceptor Learner | | | | | | X----->|->|->| | | Accept!(N,I,V) | X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST |<-------------------X--X Response(V) | | | | | |The failure scenario is the same for both protocols; Each Learner waits to receive F+1 identical messages from different Acceptors. If this does not occur, the Acceptors themselves will also be aware of it (since they exchanged each other's messages in the broadcast round), and correct Acceptors will re-broadcast the agreed value:
Message flow: Fast Byzantine Multi-Paxos, failure
Client Acceptor Learner
| | | ! | | !! One Acceptor is faulty
X----->|->|->! | | Accept!(N,I,V)
| X<>X<>X------>|->| Accepted(N,I,{V,W}) - BROADCAST
| | | ! | | !! Learners receive 2 different commands
| | | ! | | !! Correct Acceptors notice error and choose
| X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST
|<-------------------X--X Response(V)
| | | ! | |
Production use of Paxos
- Google uses the Paxos algorithm in their Chubby distributed lock service in order to keep replicas consistent in case of failure. Chubby is used by BigTable which is now in production in Google Analytics and other products.
- Google Spanner uses the Paxos algorithm internally
- The OpenReplica replication service uses Paxos to maintain replicas for an open access system that enables users to create fault-tolerant objects. It provides high performance through concurrent rounds and flexibility through dynamic membership changes.
- IBM supposedly uses the Paxos algorithm in their IBM SAN Volume Controller product to implement a general purpose fault-tolerant virtual machine used to run the configuration and control components of the storage virtualization services offered by the cluster. This implementation features: dynamic quorum (which considers power domains and extends the Paxos protocol to an optional quorum disk to maintain fault-tolerance down to clusters as small as two nodes); concurrent ballots of batched requests broadcast and collated using an overlay binary tree network for efficiency; automatic reintegration of restarted nodes without stalling the cluster (by state delta transfer using an overlay hypercube network followed by catch-up of ballots committed during the state transfer) and an underlying view management algorithm used to select a leader and gracefully handle asymmetric network partitions.[citation needed]
- Microsoft uses Paxos in the Autopilot cluster management service from Bing.
- WANDisco have implemented Paxos within their DConE active-active replication technology.
Subscribe to:
Posts (Atom)