Dağıtılmış sistemlerde saat senkronizasyonu

Abstract

Dağıtılmış sistemlerde bir düğüm zamanı öğrenmek istediğinde kendi yerel saatine başvurur. Ortak bir görevi yürüten süreçler yine ortak bir saat bilgisine ihtiyaç duyarlar. Bu durumda ortak görevi yürüten süreçlere ait yerel saatlerin senkronize çalışmalan gerektiğini söyleyebiliriz. Aynı anda belli bir zamana ayarlanan saatler, kristallerin farklı hızlarda çalışması nedeniyle zamanla birbirierinde uzaklaşacaklardır. 8u durum saatlerin belirli aralıklarla senkronize edilmeleri gerektiğini ortaya çıkarır. Dağıtılımış sistemlerin temel problemlerinden olan bu duruma dağıtılımış sistemlerde saat senkronizasyonu problemi diyeceğiz. Saat senkronizasyon problemini çözmek için değişik algoritmalar önerilmiştir. Bu algoritmalar sıkı bir şekilde öngörülen modele bağlıdır. Temelde bu çalışmalan ana-uydu ve dağıtılımış algoritmalar olarak ikiye ayırabiliriz. Ana-uydu algoritmaların tasarlanması ve uygulanması kolay olup haberleşme maliyeti düşüktür. Dağıtılmış algoritmalar ise yüksek düzeyde hata hoşgörülüdür. Saat senkronizasyonu ile ilgili çalışmalaların ana hedefi zaman bilgisini taşıyan mesajın en kısa zamanda istenilen yere ulaştırılması ve mesajın seyahati esnasında geçen sürenin tam olarak bilinmesidir. Yol gecikmelerinin ve kuyruklardaki beklemelerin herzaman aynı olması düşünülemez. Bu nedenle mesajın yolda geçireceği süre için alt ve üst sınırların belirlenmesi ve bu sınırları kullanarak çeşitli analizlerin yapılması yoluna gidilmiştir. İletim gecikmeleri için alt ve üst sınırlar koyan deterministik algoritmalann yanında belli bir olasılıkla istenilen hassasiyete ulaşan olasıl algoritmalar da mevcuttur. Şimdiye kadar yapılan çalışmalar içinde günümüz yerel alan ağlarına uygun, çeşitli topolojilerde çalışabilecek, saat bilgisini istenildiği kadar kısa bir zaman içinde belirli bir olasılıkla iletebilecek olasıl bir algoritma daha ayrıntılı olarak incelenmiştir. Bu algoritmanın benzetim programını yazmak için gerçek zamanlı bir işletim sistemi çekirdeğinin nasıl kullanılacağı gösterilmiştir. Saat senkronizasyonunu hiyerarşik yapıdaki optik arabağlaşım devresine sahip bir yerel alan ağında gerçekleştirmek için önce FDDI protokolü incelenmiştir. Daha sonra bir FDDI geliştirme kartı kullanılarak hızlı saatiletimini sağlamak için bu kartın koşullanması ve çerçeve gönderme programının hazırlanması işlemleri gerçekleştirilmiştir. Saat senkronizasyonu dağıtılımış sistemler içinde çok çeşitli şekillerde ve değişik platformlarda incelenmiştir. Tez içinde yapılan çalışmalar sonucu Genel amaçlı olasıl bir algoritma hakkında açıklamalar yapılmış ve FDDI geliştirme seti için saat senkronizasyonunu sağlayan düzenlemelerin nasıl yapılacağı anlatılmıştır. Bu işlem için gerekli akış diyagramlan verilmiştir. Aynca hiyerarşik yapıda demokratik ve ana-uydu modelleri için önerilerde bulunulmuştur.Some applications require a distributed topology because of its nature. A distributed system consists of a set of nodes which are interconnected by a network. Each node communicate with others by message exchange mechanism. Although the nodes have independent processing ability, as a part of a complete task they need to communicate with each other. Real time systems become important research area of computer science. In real-time computing the correctness of the system depends on the logical results of the computation and the time at which the result are produced. Real-time systems have to react to events within a pre-determined time span. The timing constraints require costly hardware equipments and complex software algorithms. In a real-time distributed system each node should have a notion of time maintained by an autonomous local clock in the nodes. Clocks used for time and interval measurement. A clock in a computer system is a crystal oscillator. The crystal oscillates at a pre-determined frequency. But it never operates with this frequency exactly. It will be run slower or faster within a boundary. Therefore, it is impossible to guarantee that crystals in different nodes all run at the same frequency. Any two clocks initially adjusted at same value diverges from each other by the time. This introduces clock synchronization problem in a distributed system. In distributed systems tasks may be partitioned into many nodes for an application. In order to measure the time of occurrence of events and the time intervals between the events, it is necessary to provide a common time reference. The common time reference, called "approximate global time" or just "global time" and it can be derived from the local times of the local clocks of each nodes by a clock synchronization algorithm. The global time must be close to the actual time. The actual time may be obtained from an official source like Universal Time Coordinated (UTC) signals. UTC signals broadcast by the WWV radio station of National Bureau of standards. A radio receiver can be used to receive this signals. In a multi node system placing a receiver into each node will not be an acceptable solution. Therefore, if one machine has a receiver, the goal becomes keeping all the other nodes synchronize to it A clock synchronization algorithm must keep the differences between local times of the local clocks within a known constant. Also the algorithm should keep the global time close to the actual time, and finally the algorithm must be fault tolerant. Lamport and Melliar-Smith were the first researches studying the clock synchronization problem. They coined the term "byzantine fault" to refer to the fault VI model in which a faulty clock can exhibit arbitrary behavior and it can misrepresent itself to other clocks in the system. Many hardware and software solutions has been proposed in the literature. The software approach is more flexible and economical. But it increases message traffic in the network and may overload the system. This may cause problems in the real-time systems. The problem makes the clock synchronization algorithms stricly application and communication media dependent. Time & Clocks in computer system Computer operations based on time implemented by electronic devices called as timers. A timer is usually a precisely machined quartz crystal. When kept under tension, quartz crystals oscillate at a well-defined frequency depends on the kind of crystal, tiow it is cut and the amount of tension. Generally timers contain two registers, each oscillation of crystal decrements counter register by one. When the register gets to zero an interrupt is generated and it is reloaded from the holding register. In this way a timer can be programmed to generate 60 interrupt in a second. If we stamp the value of count register on an event when it occurs, then we can define a clock that assigns a number to each event in order. With this kind of mechanism it is possible to compare the numbers to find which event happened before. We can make no assumption about real-time using this kind of clocks. This kind of clocks called as logical clocks. The time value represented by logical clocks is called as logical time. The term physical time refers to real world time. The logical clocks' oscillation frequency can be adjusted so that a mapping function from physical time to logical time can be defined. Let C be a mapping function from physical time to logical time, then C(t)=T means when real time t the logical time at a particular node equals to T and called as local time. Faulty Clock A clock assumed as nonfaulty if its logical time follows the real time continuously and correctly. In other words let "C is a mapping function and T is physical time then C(t) always must equal to t. However because of clocks drift rate no local clock can manage this accuracy. Clocks' maximum variation over time is called drift rate and denoted by p. In general this rate is in the order 10"5 seconds per seconds. In this way a local clock drifts 0.86 sm from the physical clock in a day. A clock's which has a constant drift rate r mapping lies between (1- p)t and (1+ p)t. This variability of local clocks defined as clock envelope or synchronization envelope. A clock called as nonfaulty if it always stays within this envelope. (1-p)<=dC(t)/dt<=(1+p) Two nonfaulty clocks started with the same initial value and have different drift rates will display a skew in their clock values after an interval of time. If the vu skew stays bounded by a constant then the two clocks are said to be synchronized to within a skew 8 |C2(t)-C1(t)|<8 One of the important term for clock synchronization algorithms is read-error. In a distributed system, nodes send and receive clock information using message passing mechanism. Message delays within a network have great effect on accuracy of the synchronization. With no work load, minimum message delay (min) can be measured easily. But most times it is hard to estimate maximum value of message delay(max) in advance. Read error can be defined as max-min. Many of the synchronization algorithms use this value on its analysis. Clock Synchronization Two nonfaulty clocks which are initially adjusted to a same value diverge by the time. After an interval of R, this skew reachs to 2pR. Since the skew grows by the time a correction must be performed periodically. This correction function can be shown generally as: Cj(tj) <= /=(Cii(ti1),Ci2(ti2),..Cik(tik)) The function F varies depends on the algorithm. Same algorithm must be performed on each node in the system. On the above demonstration T describes the node number and 1,2,3... k describes other nodes which send messages. Nodes do not have to send their clock values at the same time. They can send their messages in a limited time interval. So, the variable t must contain two parameters. As shown the formula all nodes must send their clock values to all other nodes. In a distributed system a node either broadcasts its clock value or sends it to a specific node upon request. Synchronization Algorithms In a distributed system each node has a logical clock that provides a time information for all activities in the node. The logical clock generaly derived from a hardware clock. During synchronization operation (instead of hardware clocks) the logical clocks are adjusted. Because of message delays nodes can be synchronized with an error. In other words a node can never be sure that all other nodes have exactly the same value with its clock after a synchronization peroid. Therefore, we can say that only the approximate agreement can be established within a multi node system using software technics. Consequently a synchronization algorithm must satisfy agreement and accuracy in a system. Agreement means that the skews between all non faulty clocks in the system are bounded and accuracy means that the logical clocks must keep up with the actual time. There are many ways of classifying the synchronization algorithms. But basically we can divide the algorithms into two classes: master-slave algorithms and distributed algorithms. The algorithms differ in the way of satisfying the agreement and accuracy. VUl Distributed Algorithms Distributed algorithms are based on democratic agreement of all nodes on a global time. The main advantage of the algorithms is that they are highly fault tolerant. This characteristic increases communication cost, but requires no additional hardware. We can briefly explain common behaviors of the algorithms by three steps: 1) All nodes receives clock information from the all other nodes. 2) All nodes apply same algorithm on the received information. 3) All nodes updates their local clocks depend on the algorithm. There are some applications of distributed algorithms: Convergence-Averaging Algorithms The problem first addressed by Lamport and Melliar Smith.Then Lundelus and Lynch proposed a new algorithm based on interactive convergence. In the Convergence-Averaging algorithms the clock processes at each node broadcast a resynch message when their local time reachs the beginning of a synchronization period. After broadcasting the clock value, the clock proses collects the resynch messages broadcasted by other nodes during a waiting period. For each message the clock process records the time and its own local time when the message was received. At the end of the waiting period it estimates the skew of its clock with respect to each of the other nodes. It then computes a fault tolerant average of the estimated skews and uses it to correct local clock. This kind of algorithms have two important limitations. They assume that the communication network is fully connected, so that every node can send a message directly to every other node at the same time. Therefore this kind of algorithms are not scaleable. Secondly, the algorithms require a known upper bound on clock read error. Because, clock-read error has great impact on the worst-case skew. This may cause some problems. Because it is difficult to assume a bound on the clock read error for a wide network. Master-Slave Algorithms There are many master-slave algorithms proposed to keep the clocks synchronizatied. Functions of master and slave create basic differences between this kind of algorithms. Furthermore handling of the read error is another main difference. Deterministic algorithms need pre-determined maximum and minimum transmission times for a network but probabilistic approach does not need any assumption about maximum message transmission time. IX Deterministic Algorithms TEMPO is a clock synchronization algorithm on Berkeley UNIX 4.3 BSD systems. The algorithm works in a local area network. Every node in the network contains a time daemon. The algorithm works as follows: A master time daemon measures the time difference between the nodes. The master computes the global time as the average of the times provided by the nonfaulty clocks. A clock considered as faulty if its value is more than a small specified interval away from the majority of the other machines. The master then sends a correction value for each machine. In case of any fault in the master an election algorithm performed to elect a new master. Analysis of maximum error in the estimation of time difference between the clocks based on known upper and lower bound of message transmission times. e is the upper bound on the read error. Then it can be shown that if the master synchronizes a number of machines using TEMPO any two nonfaulty clocks will be within range 4e. Network Time Protocol (NTP) is designed to distribute time information in a large diverse internet system. NTP is used in the Internet system to synchronize clocks and coordinate time distribution. This protocol adjusts the clocks in a network to run at the same frequency and set them to agree at a particular epoch with respect to Coordinated Universal Time (UTC). Experiments showed that accurate and reliable internet time synchronization can be achieved only through an integrated approach to system design, including the primary reference sources, time servers, synchronization subnets, protocols and synchronization mechanisms. Time servers are time keeping systems. Each time server has a synchronization subnet. It measures the offsets between its local clock and other clocks in the subnet. NTP time server operates as a hierarchically organized subnet of loosely coupled time servers. They exchange periodic update messages containing precision time stamps to adjust local oscillator phase and frequency. The NTP system consists of primary and secondary time servers, clients and interconnecting transmission paths. A primary server is directly synchronized to a primary reference source. Time stamps exchanged between the server and possibly many other subnet peers are used to determine individual round trip delays and clock offsets, as well as provide reliable error estimates. So the algorithm does not need any predefined upper bound about message delay. Probabilistic algorithms Up to now, algorithms' probability of achieving synchronization was equal to one. Teherefore they are classified as deterministic algorithms. Synchronization skew greatly affected by message transmit delay. If unbounded random message delays are permitted the achievable synchronization skew may be too large and so the required skew becomes significantly less than achievable using the deterministic algorithms. In distributed system, if unpredictable communication delay is permitted then the task of synchronizing clocks becomes more difficult. Minimum message delay can be computed, but maximum bound of message delay depends on many random events. Measurement of process to process message delay in existing systems indicate that typically their distribution. This distribution has a maximum density at a mode point between the minimum delay min and the median delay, usually close to min, with a long tail to the right. Probabilistic approach based on an assumption that message propagation times are randomly distributed. Cristian algorithm Cristian proposes a new approach to read remote clock subject to unbounded message delays. His algorithm is probabilistic, because it does not guarantee to reading remote clock. This algorithm is particularly suitable for master-slave systems in which one clock has been designated or elected master and the other clocks act as slaves. Any desired reading error can be provided with a probability close to one. But small read error causes more communication overhead and less probability of achieving remote reading. Firstly maximum acceptable message delay (2U) must be determined. Only remote clock values which its transmission delay less than 2U is acceptable. If a node can not read remote clock within 2U time interval, it waits W time units and retries reading remote clock. The probability of slave to read remote clock successfully is p. The node retries k times if it fails. So, the probability becomes p Each slave periodically sends a message to the master node requesting its clock value. When the master receives this request it sends its local clock value. When the response reaches the requesting node it calculate the total round trip delay according to its local clock. Fiber Distributed Data Interface The Fiber Distributed Data Interface (FDDI) is a 100 Mbit/s local area network. The FDDI protocol is based on token ring access method and uses optical fiber as the medium. Physical layer and Media Access Control parts of FDDI first submitted by Sperry in 1983. Then it was developed to satisfy the needs of many application, including the back-end interface, LAN backbone, front-end high performance LAN applications. FDDI conforms to the ISO model. FDDI has all the advantages of ring topology, such as reliability, availability, and serviceability. Many protocols are developed for failing stations or fiber links. This protocols also provide logical addition and deletion of of stations without detrimental effects on existing ring traffic. FDDI is the only LAN to have management protocols specifically for the FDDI subnetwork characteristics. Other LANs management capabilities were XI added after the standard was developed. FDDI has built-in network monitoring and management capability. Optical fiber offers superior limits on the length of ring and FDDI can divide bandwith into portions hierarchically. This advantages particularly suitable for real-time applications. The basic operation of the FDDI MAC protocol is provide ordered access to ring. Access to the network is controlled by passing a permission token around the ring. In order to transmit a message a station needs to capture a token. After capturing a token, the station transmits packet data. It may not hold the token longer than the period determined by TTR algorithm. In FDDI it is not necessary for transmitting station to hold the token until all its transmitted frames have returned. This mechanism allows for more efficient usage of bandwith and is known as early token release. In order to provide a low access delay the TTR protocol specifies two classes of service. The synchronous class of service has a guaranteed bandwidth and access delay. The asynchronous class of service on the other hand, uses the remainig bandwith which dynamically shared between all nodes. Asynchronous traffic is sent on the network only if the ring is lightly loaded and is not a guaranteed bandwidth at heavy networks load. In TTR protocol stations attempt to maintain a Target Token Rotation Time (TTRT) by slowing down and speeding up the token. Clock Broadcast To provide more accurate transmission of clock value we must examine some proporties of FDDI. A request to transmit one or more frames is serviced by the ring engine. After a request is submitted to the engine the ring engine awaits an appropriate service opportunity. Frames associated with the current request may be transmitted at any time during a service opportunity. In many applications, data is ready to be transmitted when the request is presented to the interface. However in order to minimize the effect of ring latency it is desirable to capture the token when no data is ready to be transmitted. This capability results in wasted ring bandwith but it can be used for fast data transmission. The architecture of the MAC device defines two basic types of objects:Data Units and Descriptors. Data and Descriptors may consists of one or more parts. All Descriptors may be marked as First, Middle.Last or Only. Firstly we must look at frame transmission:. The Request Block in the service engine transmits frames from host memory to the ring engine. The service engine accepts frames as Output Data Unit (ODU) and sends them to the ring engine as byte stream. The request machine processes requests by first reading request descriptors from the REQ queue and then assembling frames of the specified service class. After FDDI protocol explained a fast clock transmission method is proposed. To achieve fast clock transmission service access point is configured properly and put_odudQ function is updated with some extentions. Also a new xu frame type is defined to transmit clock value. FDDI protocol and finaly we discussed clock synchronization on a hierarachical network which is appropriate for distributed real-time computer systems.