FDDI tabanlı bir ağ sistemi için etkin gerçek zamanlı iletişim yapısının tasarımı

Abstract

Gerçek zamanlı dağıtılmış sistemlerde, birbirlerinden uzaktaki bilgisayarlarda yer alan süreçler ortak işleri yerine getirmek için birlikte çalışırlar. Bu tür sistemlerde süreçlerin zaman kısıtlamalarının sağlanması ve sistemin sağlıklı olarak çalışabilmesi için, süreçler arası iletilen verilerin belli zaman sınırları içinde hedeflerine ulaşması zorunludur. Bu nedenle gerçek zamanlı dağıtılmış sistemler, bu tür çalışmaları destekleyen bir iletişim alt yapısına gerek duyarlar. Î.T.Ü. Bilgisayar Bilimleri Anabilim Dalı'nda yürütülen TÜBİTAK EEEAG-BAĞ3 projesi çerçevesinde gerçek zamanlı sistemlere iletişim hizmeti vermek üzere bir iletişim birimi tasarlanmıştır. Tez çalışmasının konusunu ise bu iletişim biriminde yer alan ağ hizmet katmanları ve onları denetleyen yönetim biriminin tasarımı ve gerçeklenmesi oluşturmaktadır. Yedi katmanlı OSI modelinin ilk üç katmanına karşı düşen ağ hizmet katmanları yönetim birimi ile birlikte, iletişim ağının özelliklerini ve sistemdeki kaynakları en iyi şekilde kullanarak gerçek zamanlı verilerin hedeflerine istenen sürelerde iletilmesinden sorumludurlar. Yönetim birimi, ayrıca sistemdeki yükün değişimine göre iletişim ağının parametrelerini güncelleyerek veri aktarımının hedeflenen şekilde yürümesini sağlamaktadır. İletişim ağı, birbirlerine bağlı hiyerarşik FDDI halkaları ile oluşturulmuştur. FDDI protokolünün değişik özellikteki sistemlerde başarılı olması için parametrelerinin uygun şekilde seçilmesi ve gerektiğinde sistemin çalışması sırasında güncellenmesi gerekir. Tez çalışmasında, durakların senkron iletim sürelerinin, gerçek zamanlı iletişimi destekleyecek şekilde seçilmesini ve gerektiğinde iletişim ve işlem yükünü fazla arttırmadan güncellenme- sini sağlayan yeni bir senkron süre atama yöntemi geliştirilmiştir. Bu yöntem, büyük ölçüde yerel verilere dayanmakta ve daha önce yayınlanmış olan yerel yöntemlere göre daha iyi sonuçlar üretmektedir. Bu çalışmada geliştirilen diğer bir yeni yöntem de, hiyerarşik FDDI halkalarından oluşan bir ağ içinde, ulaşım katmanları arasındaki uçtan uca bağlantıların istenen iletişim kalitesine uygun olarak kurulmasını ve sürdürülmesini sağlayan mantıksal bağlantı denetimi yöntemidir. Yönetim birimi, ulaşım katmanından gelen bağlantı isteklerini bu yönteme göre değerlendirerek gerekli olan sistem kaynaklarını (bellek ve senkron bant genişliği) ayırır ve sistem parametrelerini yeni duruma göre günceller. Bağlantılar kurulurken ve sonlandırılırken iletilen denetim verilerinin miktarı, gerçek zamanlı iletişimi aksatmayacak düzeyde tutulmuştur. İletişim biriminin önemli elemanlarından biri de katmanlar arasındaki bağlantıyı sağlayan ilkel kuyruklarıdır. Tez çalışmasında, bir durakta birden fazla ulaşım katmanı bağlantısı kurulması durumunda, değişik özellikteki verilere uygun iletişim hizmeti sunmak için ulaşım katmanı ile ağ hizmet katmanları araşma, her bağlantı için ayrı bir ilkel kuyruğu yerleştirilmiştir. İletişim birimindeki kuyrukların önceliklerinin ve bir kuyruktan peş peşe okunan ilkel sayısının belirlenmesi, yönetim biriminin önemli işlevleri arasındadır. Tez çalışmasında, FDDI arabirim kartlarına sahip dört adet kişisel bilgisayar ile bir sistem oluşturulmuş ve ağ hizmet katmanları ile yönetim birimine ilişkin yazılımlar bu sistem üze rinde gerçekleştirilmiştir. Programlar nesneye dayalı yöntemle C++ dili kullanılarak yazılmış ve verilerin en hızlı biçimde işlenmesi amaçlanmıştır. Kurulan fiziksel sistemin ye terli olmadığı durumlarda, geliştirilen yöntemleri değişik sistemler üzerinde sınayabilmek için benzetim programlan hazırlanmıştır. Bu programlarla elde edilen sonuçlar, tez çalışmasında geliştirilen yöntemlerin gerçek zamanlı iletişim hedeflerine ulaştığını göstermiştir.

There is an increasing use of computers in real-time applications, such as space ve hicle systems, image processing and transmission and industrial process control. These systems usually have a distributed implementation, because distributed sys tems share resources well and are reliable and extensible. In these systems, compu tational tasks reside on different nodes in the system and cooperate to achieve a common goal. Messages sent between these tasks have deadlines by which they must be transmitted. If a message fails to meet its transmission deadline it is considered to be lost and this message loss can lead to a catastrophe in a mission critical system. The key to meet the timing requirements in real-time systems is to have an underly ing network that ensures timely delivery of inter-task messages. In TÜBÎTAK EEEAG-BAG3 project, we have implemented a Communication Unit (CU) which provides reliable and real time communication services for the "client" processes. The aim of this thesis is to design and implement the Network Service Layers (NSL) and the Management Unit (MU) of the CU. These entities are re sponsible for sending data over an FDDI network in predefined time constraints. In this thesis, we propose a new synchronous bandwidth allocation scheme for FDDI networks and a new logical connection management protocol. The main task of the logical connection management entity is to allocate the system resources for transport layer connections and to tune the operational parameters of the FDDI ring. We built an experimental FDDI network by using four PCs with FDDI adapter cards. We implemented and tested programs related to NSL and MU in this communication system. Since this physical configuration is insufficient to test all capabilities of our new synchronous bandwidth allocation scheme and logical connection management protocol, we also wrote simulation programs to test them in different network con figurations. The interconnection network is made of FDDI rings as shown in Figure 1. Timed to ken access and synchronous data transfer capabilities are the main reasons of the FDDI protocol to be used in this work. An FDDI station in this network consists of a communication unit, which gives real-time communication service to a processor. The processors, which heavily communicate to each other take place in the same ring in the network. Some rings are grouped to form a cluster. They are connected via a router. The Communication Unit consists of the following parts:. The Session Layer (SL): It provides real time communication services for user processes implementing bi-directional links. xiv The Transport Layer (TL): It offers to the Session Layer a real-time, error-free, and connection oriented transport service. The Network Service Layer (NSL): It provides connectionless communication and routing services for the TL and MU in a multi-FDDI ring system. The Management Unit (MU): It is responsible for managing the CU and tuning some FDDI parameters by working with the MUs of other CUs in the ring. R: Router S: Station Figure 1. Overview of the Interconnection Network The NSL matches to the three bottom layers of the OSI network model. With this structure NSL provides the transfer of time-critical data between the processors in the network. The basis of the NSL is the FDDI protocol. The structure of the NSL is shown in Figure 2 and its sublayers are explained below:. The Physical Layer (PL): This layer is functionally equivalent to the Physical Layer and Physical Medium Dependent (PMD) of the FDDI standard. These two layers of the FDDI standard have not been modified in this work.. The Medium Access Control Layer (MAC): MAC schedules and performs all data transfers on the ring based on the timed token protocol of FDDI standard. This layer has been implemented by using an FDDI adapter card with National Semi conductor's FDDI Media Access Controller and System Interface DP 83266 chip (MACSI) and 256KB SRAM memory on it.. The Routing and Frame Control Layer (R&FCL): The main function of the R&FCL is to build the FDDI frame from the Service Data Units (SDU) of the Transport Layer (TL), and write them to the related outgoing frame queue of MAC. The R&FCL locates the target processor using the destination NSAP (NSL Service Access Point) address, and determines the destination MAC address of the FDDI frame. Than the frame type is determined to be synchronous or asynchro nous depending on the priority and the time-critical nature of data. The frame that is built is placed to one of the two outgoing frame queues of MAC. Frames, which xv come from MAC are placed to one of the appropriate primitive queues of the Transport Layer depending on their synchronous or asynchronous types. Queue Man. Timers Clock Synchronization Logical Conn. Management MU Frame Services Ring Management Physical Conn. Management ?>: Q3 -> Q2 -"<- Transport Layer TL -> AT n £ İ İ İ Q4 bd Q5H Q6H Q7tdQ8 ö ^ ^ T.1. T ->:..I 'vU Ql Q9 | -; Q10 f ^S. :jM isr MAC 1N_ ISR.^w^ v.... J.._....' v :..'..... Frame I Queues Hardware PL Network Service Layers - NSL Qi: Primitive Queues A T: Address Table: ISR : Interrupt Service Routine F: Function Figure 2. Network Service Layer (NSL) The Management Unit (MU) consists of the following entities:. The Physical Connection Management Entity (CME) directs the PL and MAC for establishing connection with the peer layers of the neighbor CUs.. The Ring Management Entity (RME) is responsible for initiating recovery func tions on detecting faults like duplicate addresses.. The Fame Service Entity (FSE) enables the MU to communicate with other MUs in the ring.. The Logical Connection Management Entity (LCME) allocates system resources for TL connections and tunes the operational parameters of the FDDI ring.. The Timer Entity (TE) provides timer functions to other layers. These functions are used to measure time and to invoke some periodic processes.. The Queue Management Entity (QME) coordinates the activities in CU by allo cating the communication processor to different layers and entity processes ac cording to the length of primitive queues between them.. The Clock Synchronization Entity The router has been implemented with a Pentium based PC and more than one FDDI card on it. Each card provides a connection to a different ring. The main function of the router is to direct and send the data packets between different FDDI rings. The structure of a router is shown in Figure 3. The router has a PL and MAC for each ring xvi it is connected to. These units perform the same functions as in other CUs. However, the router has only one R&FCL, which performs the routing of data packets. Routing and Frame Control Layer R&FCL routers table local table MAC MAC MAC MAC PL PL PL PL to ring 0 to ring 1 to ring n to ring of routers Management Unit MU Figure 3. The Structure of the Router FDDI uses the timed token MAC (Medium Access Control) protocol that provides a guaranteed amount of channel bandwidth to support timely delivery of inter-task messages. With this protocol, messages are distinguished into two types: synchro nous messages and asynchronous messages. Synchronous messages, such as sam pled/digitized voice and video data, are periodic messages which arrive at regular intervals and have delivery time constraints. Asynchronous messages are nonperiodic and may arrive in a random way and have no time constraints. At network initializa tion time, all nodes negotiate a common value for the target token rotation time (TTRT) since each node has different synchronous transmission requirements to be satisfied. The negotiated value for TTRT should be chosen small enough to satisfy the most stringent response-time requirements of all nodes. Each node is assigned a frac tion of the TTRT, known as its synchronous bandwidth (Hi), which is the maximum time the node is allowed to transmit its synchronous messages every time it receives the token. After synchronous message transmission, asynchronous messages can be initiated (if any), but only if the token has arrived at the node earlier than expected. That is, synchronous traffic is assigned a guaranteed bandwidth while the leftover bandwidth (unallocated, unused or both) is dynamically shared among all the nodes for asynchronous traffic. The FDDI network guarantees, to each node, an average bandwidth and a bounded access delay for synchronous traffic. However, this guarantee alone, although neces sary, is insufficient for the timely delivery of deadline-constraint messages. For guar anteeing the synchronous message deadlines with the timed token protocol, the pro tocol parameters (TTRT and the synchronous bandwidths) have to be properly se lected. In dynamic environments where synchronous data connections are often established or terminated, the data load on the network changes during the operation. In these systems synchronous bandwidths of the nodes, their data load changes must be recal culated. In this thesis we propose a new synchronous bandwidth allocation scheme for guaranteeing synchronous messages with arbitrary deadlines. In allocating syn chronous bandwidth to a node, this scheme uses information locally available to the xvu node and the sum of the synchronous bandwidths allocated to other nodes. The lim ited use of global data makes the new scheme flexible and suitable for use in dy namic environments, since the recalculation of the synchronous bandwidth of a node does not effect other nodes until total synchronous bandwidth of the ring exceeds a predefined threshold. In the following paragraphs of the thesis we analyze the new synchronous bandwidth allocation scheme and show that it performs better than pre viously published local SBA schemes. To develop a new synchronous bandwidth allocation scheme the timing properties of the FDDI protocol are investigated: The network is assumed to consist of n nodes arranged to form a ring and be free from any hardware and software failures. Mes sage transmission is controlled by the timed token protocol. Token walk time T in cludes the ring latency, the token transmission time and other protocol/network de pendent overheads and thus represents the portion of TTRT that is not available for message transmission. There are n streams of synchronous messages Sı, S2, S3,..., Sn, with stream St originat ing at node /. Each synchronous message stream St can be characterized as Si=(Q, Pt, Dj), where 1. Q is the maximum amount of time required to transmit a message in the stream. 2. P{ is the interarrival period between messages in the stream. Let the first message in stream St arrive at node i at time fa. The/th message in stream St will arrive at node * at time t{j = tiX +(j~l)Pi} where j > 1. 3. D t is the relative deadline of messages in the stream, that is, the maximum amount of time that can elapse between a message arrival and completion of its transmis sion. Thus the transmission of the /th message in stream St which arrives at fa, must be completed by fa+Df. 4. Each synchronous message stream places a certain load on the system. We need a measure for this load. We define the effective utilization, Ut of stream Si as fol lows: ' mın( JJ.D,) 5. Asynchronous messages may arrive in a random way and have no time con straints. To ensure stable operation of the timed-token protocol, the total bandwidth allocated to synchronous messages must be less than the available network bandwidth. This protocol constraint is; f.H^TTRT-T (1) Zhang and Burns give an upper bound on the time elapsed between any v consecu tive token arrivals, derived a tighter upper bound and generalized Johnson and Sevcik's Theorem as follows: Ti(v) = vTTRT+ J,Hh+T- - For a given allocation H=[H\, H%,... Jf"], the minimum amount of time Xt available for node / to transmit its synchronous data in time interval [t, t+D,) is given by xvm TTRT-lJHh-T (2) Xi(H) = (qi-l)Hi + max(0,rmn(Di-Ti(qi),Hi)), where ^ =.TTRT. (3) Although, local SBA schemes use only local information available to the involved node, in implementation, every node shall know the total allocated synchronous bandwidth Z"=1 H. to be able to test the deadline constraint. By using the broadcast capability of the FDDI structure, each node can send its //,. value with only one frame to other nodes in the ring, and this increases the data traffic in the ring only by a neg ligible amount. The new SBA scheme uses only the total sum of allocated synchro nous bandwidths as global data in addition to local information. It performs better than local schemes and it is more flexible than global schemes, that makes it suitable to dynamic environments. In the new scheme, allocated synchronous bandwidth of the node i will be calculated with the following steps: 1. By using only local information the initial value 77/ such as V/,77/>77j will be calculated. 2. Each node broadcasts its initial value 77/ to the other nodes in the ring. 3. Each node calculates its actual synchronous bandwidth 77, by using 77/ initial val ues according to the new SBA scheme. 4. Each node broadcasts its actual 77} value to the other nodes. In order to calculate HI initial values, we generalized the local scheme developed by Zhang et al. as follows: 77/= W n- -{^4q-(o WKre#,= n L77KT. qt. 777*7; Dt >PiAqiTIKT>Pi,and £f=jij, Z^>/?A^,772?r<7? (4) In order to allocate synchronous bandwidths to nodes properly, deadline constraint equation (5) must be solved. That is, Xt (H) = (Hi, 3) 0 < Dt - Tt (q{ )<="" +t="" -%-="" ı="" ttrt-="" xh',="" -t="" d<="" style="margin: 0px; padding: 0px; outline: 0px;">plA2?:ft-i)+jy/>iî D^PiAJ^qt-D + H^P, DiPiAlXqi) + H;>Pi D^PiATfrqJ + HlZPi Dttransition(queue_number); global variables Base Object local variables transition function Object of State 1 local variables transition function, Object of State 2 local variables transition function Object of State k Figure 4. Derivation of State Objects The queue manager determines which layer to invoke, depending on which primitive queues in the system have data. It polls the primitive queues in a priority order. If it detects that there is a primitive in a queue, it invokes that layer, which takes primitive from this queue. The queue manager handles the data in higher priority queues first. When the higher priority queue is empty or a specified amount of primitive has al ready been taken from this queue, then the queue with the lower priority is served. The queues which belong to MU have higher priority than other queues. For each transport layer connection, we create a new primitive queue between the transport layer and the network service layers. Multiple streams on a node are thought of as multiple FDDI stations, each heaving its own FDDI interface. However, physically they share the single communication path and the single synchronous queue on the FDDI interface. The queue polling algorithm is similar to token based access proto col of FDDI standard. It has a circular service property with the period equal to TTRT. Each connection has an allocated synchronous bandwidth value Hy. The poll ing algorithm enables the NSL to read synchronous data with the length of Hy in each TTTJrtime unit from the queue of thej'th connection. The main contributions of this thesis are presented below:. A new synchronous bandwidth allocation scheme was proposed. The new scheme performs better than previously published local schemes and it is also suitable for dynamic environments.. A new logical connection management protocol for end-to-end connections was developed. The management unit allocates system resources to connections and tunes system parameters by using this protocol. The network service layers and the management unit of an FDDI station are designed and implemented. These entities are responsible for transferring real time data on a hierarchical multiring network. An experimental FDDI network was built, and the software was developed on this system. We also wrote simulation programs, to test and compare our new schemes with previously published schemes. The results of these tests show that, our new schemes perform successfully and efficient, in view of deadline guarantees of real-time data in an FDDI network.