Fault Tolerant Network

Definition of fault tolerance Fault tolerance is the ability of a system to continue performing its intended function in spite of faults. In a broad sense, fault tolerance is associated with reliability, with successful operation, and with the absence of breakdowns. A fault-tolerant system should be able to handle faults in individual hardware or software components, power failures or other kinds of unexpected disasters and still meet its specification.

Why do we need fault-tolerance?

• It is practically impossible to build a perfect system – suppose a component has the reliability 99.99% – a system consisting of 100 non-redundant components will have the reliability 99.01% – a system consisting of 10.000 components will have the reliability 36.79% • It is hard to forsee all the factors

A system is said to fail if it ceased to perform its intended function. System is used in this book in a generic sense of a group of independent but interrelated elements comprising a unified whole. Therefore, the techniques presented are also applicable to the variety of products, devices and subsystems. Failure can be a total cessation of function, or a performance of some function in a subnormal quality or quantity, like deterioration or instability of operation. The aim of fault-tolerant design is to minimize the probability of failures, whether those failures simply annoy the customers or result in lost fortunes, human injury or environmental disaster

Fault tolerance and redundancy

Redundancy • Redundancy is the provision of functional capabilities that would be unnecessary in a fault-free environment – replicated hardware component – parity check bit attached to digital data – a line of program verifying the correctness of the result

Applications of fault-tolerance

Applications • safety-critical applications – critical to human safety • aircraft flight control – environmental disaster must be avoided • chemical plants, nuclear plants – requirements • 99.99999% probability to be operational at the end of a 3-hour period

mission-critical applications – it is important to complete the mission – repair is impossible or prohibitively expensive • Pioneer 10 was launched 2 March 1970, passed Pluto 13 June 1983 • requirements • 95% probability to be operational at the end of mission (e.g. 10 years) • may be degraded or reconfigured before (operator interaction possible)

• bisness-critical applications – users want to have a high probability of receiving service when it is requested – transaction processing (banking, stock exchange or other time-shared systems) • ATM: < 10 hours/year unavailable • airline reservation: < 1 min/day unavailable

maintenance postponement applications – avoid unscheduled maintenance – should continue to function until next planned repair (economical benefits) – examples: • remotely controlled systems • telephone switching systems (in remote areas)

 

The main goal of fault tolerance is to increase the dependability of a system

Dependability is the ability of a system to deliver its intended level of service to its users

Dependability tree

dependability tree

 

 

 

 

Distributed Publish/Subscribe Network

Motivations for Pub/Sub model

  • Traditional Client/Server communication model (Employs RPC, message queue, shared memory etc..)
    • ¨Synchronous, tightly-coupled request invocations.
    • ¨Very restrictive for distributed applications, especially for WAN and mobile environments.
    • ¨When nodes/links fail, system is affected. Fault Tolerance must be built in to support this.
  • Require a more flexible and de-coupled communication style that offers anonymous and asynchronous mechanisms.

What is a Publish/Subscribe System?

  • Distributed Pub/Sub System is a communication paradigm that allows freedom in the distributed system by the decoupling of communication entities in terms of time, space and synchronization.
  • An event service system that is asynchronous, anonymous and loosely-coupled.
  • Ability to quickly adapt in a dynamic environment.

Key components of Pub/Sub System

  • Publishers : Publishers generate event data and publishes them.
  • Subscribers : Subscribers submit their subscriptions and  process the events received
  • P/S service: It’s the mediator/broker that filters and routes events from publishers to interested subscribers.

Publish/Subscribe System

pub-sub-system

 

Decoupling in time, space and synchronization

decopling

 

Classification of Pub/Sub Architectures

  • Centralized Broker model
    • ¨Consists of multiple publishers and multiple subscribers and centralized broker/brokers (an overlay network of brokers interacting with each other).
    • ¨Subscribers/Publishers will contact 1 broker, and does not need to have knowledge about others.
    • ¨E.g. CORBA event services, JMS, JEDI etc…
  • Peer-to-Peer model
    • ¨Each node can be publisher, subscriber or broker.
    • ¨Subscribers subscribe to publishers directly and publishers notify subscribers directly. Therefore they must maintain knowledge of each other.
    • ¨Complex in nature, mechanisms such as DHT and CHORD are employed to locate nodes in the network.
    • ¨E.g. Java distributed event service

 Key functions implemented by   P/S middleware service

  • Event filtering (event selection)
    • ¨The process which selects the set of subscribers that have shown interest in a given event. Subscriptions are stored in memory and searched when a publisher publishes a new event.
  • Event routing (event delivery)
    • ¨The process of routing the published events from the publisher to all interested subscribers

Event Filtering (Subscription Model) Topic based VS Content based

  • Topic based
    • ¨Generally also  known as topic based, group based or channel based event filtering.
    • ¨Each event is published to one of these channels  by its publisher.
    • ¨Subscribers subscribes to a particular channel and will receive ALL events published to the subscribed channel.

Topic-based subscription

topic based

  • ¨Simple  process  for  matching an event to subscriptions. However, limited expressiveness.
  • ¨Event filtering is easy, event routing is difficult (Heavy load on the network). The challenge is to multicast event effectively to subscribers.

Event Filtering- Subscription Model Topic based VS Content based

  • Content based
    • ¨More flexibility and power to subscribers, by allowing more expression in arbitrary/customized query over the contents of the event.
    • ¨Event publication by a key/value attribute pair, and subscriptions specify filters using a explicit subscription language.
    • ¨E.g. Notify me of all stock quotes of IBM from New York stock exchange if the price is greater than 150

Content-based Subscription

contentbased

  • ¨Added complexity in matching an event to subscriptions. (Implementation: Subscription arranged in a matching tree, where each node is a partial condition.
  • However, more precision is provided and event routing is easier

Event Routing

  • After filtering the events, the broker/brokers must route the events to the corresponding subscribers.
  • Can be done in the following ways:
    • ¨Unicast
    • ¨Multicast
    • ¨Server push/ client pull
  • The broker makes the decision: how to route the message to the subscriber.
  • Several optimization schemes are available.
    • “Profile forwarding scheme – brokers only forward the event to their neighbor broker which fulfill their subscription
    • ¨Filtering the total covering of the subscription of the system – accept publisher events only if a subscriber has subscribed this event.

Example: SIENA

  • SIENA is a wide area notification service that uses covering-based routing.
    • ¨Consists of Nodes and servers (access points), Event notifications & filters, Publish/subscribe protocol + advertisements, Identities and handlers, Filtering
  • Siena system can be configured in three types of inter-connection topologies:
    • ¨Hierarchical client/server architecture
    • ¨Acyclic P2P architecture
    • ¨General P2P architecture

SIENA: Hierarchical Architecture

siena arc

  • Servers interact with each other in an asymmetric client-server fashion.
  • Server is not distinguished from objects of interest or interested parties
  • Potential overloading of server stationed at higher level of hierarchy
  • Failure of one node in hierarchy causes all the nodes below that node to fail

Acyclic P2P architecture and General P2P architecture

  • The acyclic P2P architecture and General P2P architecture are very similar.
    • ¨Both represented by an undirected graph and allows bidirectional communication.
    • ¨Scaling an issue for both.
  • Acyclic P2P
    • ¨Restriction on the configuration of connections between servers to forming acyclic graph representation
    • ¨Therefore no redundant connections/ multiple paths are not allowed. (Enforcement by a cycle avoiding algorithm)
    • ¨Can be difficult to maintain and not as robust as general P2P architecture.¨
  • General P2P architecture
    • ¨Requires less coordination among servers.
    • ¨Redundancy enforces robustness of Siena system with respect to failure of single servers.
    • ¨Drawback: Special algorithms must be run to choose the best path.

Siena: Routing

  • Simplest strategy is to maintain the subscriptions at their access point and broadcast the notification throughout the network
    • ¨Least efficient
    • ¨Consumes lots of bandwidth
  • Send the notification towards the event servers that have clients that are interested in that notification (possibly using shortest path)
  • Downstream Replication
    • ¨Events are kept as one copy as long as possible and only replicated when it is as close as possible to the subscribing servers/clients.

downstreamrep

  • Upstream Evaluation
    • ¨Applying filters upstream, that is as close to the event publisher as possible

upstream

Advantages of Pub/Sub

  • Highly suited for mobile applications, ubiquitous computing and distributed embedded systems
  • Robust – Failure of publishers or subscribers does not bring down the entire system
  • Scalability- Suited to build distributed applications consisting a large number  of entities
  • Adaptability- can be varied to suit different environments (mobile, internet game, embedded systems etc…)

Disadvantages of Pub/Sub

  • Reliability – no strong guarantee on broker to deliver content to subscriber. After a publisher publishes the event, it assumes that all corresponding subscribers would receive it.
  • Potential bottleneck in brokers when subscribers and publishers overload them. (Solve by load balancing techniques)
  • Security an issue:
    • ¨Encryption hard to implement when the brokers has to filter out the events according to context.
    • ¨Brokers might be fooled into sending notifications to the wrong client, amplifying denial of service requests against the client.

Conclusion

  • Distributed Pub/Sub System provides a loosely-coupled, asynchronous model which is useful in many fields of network utilization.
  • Several areas are still open for research:
    • ¨Effective routing and filtering algorithms for better performance
    • ¨Scalability versus expressiveness issue
    • ¨Fault tolerance
    • ¨Security

References

  • Papers:
    • ¨P.Eugster, P.Felber,RGuerraoui and A.Kermarrec. The Many Faces of Publish/Subscribe. In ACM Computing Surveys, Vol. 35, No.2, June 2003.
    • ¨A.Carzaniga, D.Rosenblum, A.Wolf . Design and Evaluation of a Wide-Area Event Notification Service. ACM Transactions on Computer Systems, Vol. 19, No. 3, August 2001.¨
  • Wikipedia:

SOURCE:

Presentation by : Yu-Ling Chang

 

 

 

Location Sensing

Aspek yang terpenting dalam mobile networking tidak hanya memberikan akses dimana saja untuk user, tetapi juga memberikan informasi yang relevan dengan konteks user pada saat tersebut. Salah satu penentu konteks user terpenting adalah faktor lokasi user tersebut berada. Dengan sederhana user dapat disajikan informasi penting sesuai dengan lokasi saat user tersebut berada sehingga user dapat mendapatkan informasi yang paling relevan dan dibutuhkannya saat itu. Untuk sistem dapat menyajikan infromasi yang sesuai dengan keberadaan user saat itu, sistem harus dapat menangkap lokasi user pada saat tersebut dan kemudian menyajikan informasi yang ter-custom sesuai dengan kebutuhan user tersebut.

Triangulation

Dalam trigonimetri dan geimetri, triangulasi adalah proses untuk menentukan lokasi sebuah titik dengan membentuk segitiga menuju titik tersebut dari titik-titik yang telah diketahui posisinya.

Triangulasi terdiri dari lateration dan angulation. Lateration berhubungan dengan pengukuran jarak. Posisi 2D sebuah objek dihitung dengan mengukur jaraknya dari 3 titik non-collinear(tidak segaris).

Untuk menghitung posisi dalam 3D maka diperlukan 4 titik yang non-coplanair(tidak dalam bidang yg sama)

Ada 4 cara untuk mengukur jarak:

  1. Cara langsung, cara ini elibatkan pengukuran yang melibatkan aksi fisik atau bergerak untuk mengukurnya, misalnya dengan menggunakan meteran.
  2. Time-of-Flight: melibatkan pengukuran jarak antara sebuah objek (diam atau bergerak) menuju titik P dengan mengukur waktu yang diperlukan antara objek tersebut dan P pada kecepatan yang diketahui. Dalam hal ini sinkronisasi clock sangatlah diperlukan untuk memberikan sinkronisasi waktu antara pengirim dan penerima sehingga dapat mengkalkulasi jarak dengan tepat.
  3. Attenuation: menurunnya intensitas sinyal sejalan dengan bertambahnya jarak yang harus ditempuh dari sumber sinyal. Dengan ini memungkinkan untuk mengukur jarak antara objek dan titik P menggunakan sebuah rumus fungsi yang mengkaitkan attenuation, jarak dari jenis emisi, dan kekuatan sinyal awal dari emisi.
  4. Angulation: melibatkan pengukuran sudut daripada jarak.

PROXIMITY

Proximity adalah teknik penginderaan lokasi yang melibatkan penentuan saat sebuah benda berada di dekat lokasi yang sudah diketahui.

Ada tiga pendekatan dalam proximity:

  1. Deteksi kontak fisik dengan menggunakan sensor tekanan, sensor sentuh, dan detektor medan kapasitif.
  2. Memonitor AP selular nirkabel yang melibatkan pendeteksian saat perangkat mobile dalam jangkaun satu atau lebih AP dalam jaringan selular nirkabel.
  3. Monitoring sistem ID otomatis yang melibatkan penggunaan sistem ID otomatis seperti point-of-sale kartu kredit, catatan telepon, riwayat login komputer, dan penggunaan kartu ATM. Misalnya, lokasi seseorang yang berkendara di jalan raya dapat disimpulkan dari waktu terakhir orang tersebut menggunakan kartu e-toll karena pemindai yang membaca kartu tersebut memiliki lokasi yang statis dan diketahui.

Taksonomi dari Sistem Lokasi

Sistem lokasi memiliki karakterisitik properti seperti berikut:

  • Lokasi fisik dan simbolis: Sistem lokasi dapat menyediakan dua jenis informasi: posisi fisik dan posisi simbolis. Posisi fisik memberi lokasi absolute suatu objek; Misalnya, sistem GPS memberi informasi lintang, bujur, dan ketinggian untuk menemukan objek di lokasi yang tepat. Posisi simbolis adalah posisi relatif, misalnya di lab di lantai dua. Posisi simbolis sering didasarkan pada proximity, seperti pemindai barcode atau kartu akses ke bangunan. Tergantung pada kebutuhan dari aplikasi, informasi lokasi dapat bersifat fisik atau simbolis. Misalnya, posisi simbolik cukup untuk fungsi aplikasi aktif badge. Aplikasi juga dapat menggunakan kedua jenis informasi tersebut bersamaan. Posisi simbolik dapat digunakan untuk menambahkan informasi dari posisi fisik; Misalnya, koordinat GPS (posisi fisik) yang dapat menentukan lokasi turis digunakan untuk menemukan pusat bengkel servis terdekat (posisi simbolis) bagi wisatawan yang mobilnya mogok di jalan raya.
  • Mutlak(absolute) atau relatif: Sistem lokasi absolut menggunakan referensi gridi berbagi untuk semua objek yang ada; Misalnya, sistem GPS menggunakan garis lintang, bujur, dan ketinggian. Di sisi lain, sistem lokasi relatif memungkinkan objek memiliki kerangka referensi sendiri, misalnya, posisi pengguna ke restoran Thailand terdekat.
  • Komputasi lokasi yang dilokalkan: Suatu objek dapat menghitung lokasinya secara lokal/internal. Komputasi lokal dapat melindungi privasi, karena tidak ada objek lain di dalam sistem yang mengetahui lokasi objek lain tersebut kecuali objek tersebut memberikan informasinya ke luar. Misalnya, satelit GPS tidak mengetahui siapa yang memanfaatkan sinyal yang mereka kirim. Sebaliknya, sebuah objek dapat memancarkan sinyal yang dapat digunakan oleh objek lain untuk menyimpulkan lokasinya. Sinyal dapat disiarkan secara berkala atau sebagai tanggapan atas permintaan dari objek lain. Sistem infrastruktur yang ada kemudian bisa menghitung posisi objek tanpa melibatkan objek tersebut dalam perhitungan. Keuntungan dari pendekatan ini adalah beban melakukan perhitungan ditempatkan pada infrastruktur, oleh karena itu, mengurangi tuntutan komputasi dan daya pada objek.
  • Akurasi dan ketepatan: Misalkan bila sistem dapat menemukan sebuah objek di dalamnya dalam jarak 10-m dengan akurasi sampai 95%. Jarak menunjukkan keakuratan, dan persentase menunjukkan presisi (yaitu, seberapa sering kita bisa mendapatkan akurasi itu). Akurasi dapat dikorbankan untuk mendapatkan presisi. Akurasi dan presisi dapat ditingkatkan dengan menggunakan sensor campuran terpadu, dimana sejumlah Sistem lokasi terintegrasi untuk membentuk tingkat hirarkis dan mempunyai level resolusi yang saling tumpang tindih
  • Scale: Skala sistem lokasi mengacu pada area cakupan per unit dari infrastruktur dan jumlah objek yang dapat ditemukan oleh sistem per unit infrastruktur per interval waktunya. Misalnya, sistem penginderaan lokasi mungkin dapat menemukan benda-benda di dalam ruangan, bangunan, kampus, kota, atau di seluruh dunia. Sebuah satelit GPS dapat melayani jumlah receiver yang tidak terbatas, sedangkan pembaca tag elektronik tidak dapat membaca tag apa pun jika jaraknya di luar jangkauannya. Waktu merupakan faktor penting dalam menentukan skala sistem lokasi karena bandwidth yang tersedia memiliki batas pada frekuensi dan batas jumlah update lokasi dalam sebuah interval waktu. Misalnya, jika jumlahnya Komunikasi dalam sistem berbasis RF melebihi ambang batas tertentu, maka salurannya akan menjadi penuh/congested
  • Recognition: Aplikasi tertentu perlu mengenali objek untuk menentukan tindakan selanjutnya Misalnya, pemindai membaca tag pada koper di sebuah bandara dan mengirimkannya ke bagian klaim yang tepat; sebuah sistem memungkinkan pengguna untuk mengakses bagian bangunan tertentu setelah pemindai sidik jari mengidentifikasi pengguna yang berwenang. Beberapa perangkat yang digunakan oleh sistem untuk pengenalan indentifikasi adalah kamera, scanner, dan pembaca kartu. Umumnya, teknik pengenalan memerlukan penetapan ID unik global (GUID) ke objek. Sistem mencari GUID dalam database untuk menentukan, misalnya, hak akses objek terhadap sumber daya
  • COST: Biaya sistem penginderaan lokasi mencakup biaya waktu (waktu yang dibutuhkan untuk menginstal sistem), biaya ruang (jumlah infrastruktur terpasang dan ukuran dan form factor perangkat keras), dan biaya modal (harga per unit atau eleme infrastruktur dan gaji personil pendukung).
  • Limitations: Suatu sistem yang berfungsi dengan baik di satu lingkungan mungkin tidak berfungsi juga di lingkungan lain. Misalnya, sistem IR cocok untuknya penggunaan di dalam ruangan; sistem GPS tidak bekerja di dalam ruangan kecuali repeater GPS dipasang di gedung untuk membroadcast ulang sinyal; pembaca tag tertentu bisa hanya membaca tag dengan benar jika tidak ada tag lain di dekatnya.

Context-Aware Computing

Context-aware computing merujuk pada salah satu kemampuan pada mobile sistem yang dapat mengdeteksi lingkungan fisik dimana sistem tersebut berada atau dijalankan dan kemudian beradaptasi sesuai dengan lingkungan tersebut.

Sistem Context-aware ini adalh merupakan salah satu koponen pada ligkungan komputing ubiquitous computing atau pervasive.

Walaupun lokasi masihlah merupakan kemampuan utama dari mobile sistem, tetapi location-aware saja tidak mampu menangkap poin-poin interest dari user yang mobile atau berubah-rubah lokasinya. Context-aware secara umum malah banyak digunakan dengan menyertakan hal-hal yang terdekat(nearby) seperti, orang, alat/device, cahaya, level noise, ketersediaan jaringan, dan bahkan situasi sosial misalnya apakah anda sedang bersama kelurga atau teman.

Konteks dapat didapatkan dari berbagai macam tipe sensor (misalnya lokasi, load), visi komputer (misalnya gesture, petujuk dan deteksi aktivitas), modeling perilaku user (misalnya pikiran, aksi, dan kata-kata), menyimpulkan dari database atau kalender, atau input eksplisit dari user/device sendiri. Seketika didapat konteksnya, maka kita dapat melihat bagaimana konteks informasi dapat digunakan untuk berbagai macam aplikasi untuk menyediakan service atau informasi yang khusus.

Aplikasi dapat menggunakan konteks secara pasif untuk melakukan kostumisasi pda penyajian aplikasi atau dapat secara proaktif menerima dan menggunakan informasi konteks yang tersedia secara konstan dalam proses pengambilan keputusan.

KONTEKS

Konteks adalah istilah umum yang dapat dikategorikan ke dalam tiga kategori dalam ranah komputasi mobile, yaitu konteks komputasi, konteks pengguna, dan konteks fisik.

3 komponen penting dalam konteks user adalah: dimana Anda berada, dengan siapa Anda berada, dan sumber daya apa yang terdekat.

Ketiga kategori tersebut dapat dijelaskan sebagai berikut:

  1. Konteks Komputasi (sumber daya apa yang Anda miliki) – seperti konektivitas jaringan, biaya komunikasi, dan bandwidth komunikasi dan sumber daya terdekat seperti printer, display, dan workstation
  2. Konteks pengguna (Anda bersama dengan siapa) – seperti profil pengguna, lokasi, orang di sekitar, bahkan situasi sosial saat ini
  3. Konteks fisik (di mana Anda berada) – seperti pencahayaan, tingkat noise, kondisi lalu lintas, dan suhu

Beberapa tambahan kategori dan subkategori yang menarik dari konteks:

  • Konteks geografik (misal: gedung, lantai, kantor)
  • Konteks organisasi (misal departemen, project)
  • Konteks aksi (misal: tugas)
  • Konteks teknologi (misal: programmer Java)
  • Konteks waktu (misal: jam dalam satu hari, bulan, musim tertentu dalam setahun)

Apapun informasi kontekstual yang dikumpulkan oleh sistem, informasi tersebut harus direpresentasikan dalam bentuk yang dapat dicerna oleh aplikasi yang tergantung pada koteks tersebut.

AKUISISI KONTEKS

Tujuan utama dari akuisisi ini adalah untuk mengumpulkan informasi dan menyediakannya dalam cara yang aman dan dapat diandalkan untuk platform middleware menggunakannya untuk menentukan keputusan.

Seringkali tidak cukup hanya mengumpulkan semua informasi kontekstual dari sebuah sensor saja. Dalam komputasi mobile, sensor dapat berada di satu tempat atau didistribusikan secara spasial. Dalam susunan banyak sensor, protokol komunikasi harus dapat direkayasa untuk memfasilitasi perpaduan data tersebut. Hal ini dapat melibatkan pos-prosesing yang lebih rumit. Sebagai contoh, dalam komputasi wearable, sensor-sensor dapat dipasang pada seluruh bagian tubuh. Penempatan sensor ini sangatlah penting bagi observasi kontekstual. Dalam aplikasi apa saja, sang designer harus dapat memilih tipe sensor yang tepat dan posisi penempatannya  yang relevan.

Akuisisi Data sensor

Terdapat banyak pilihan sensor dan teknologi sensing yang dapat diaplikasikan untuk mengumpulkan informasi kontekstual. Beberapa teknologi sensing dapat dikategorikan sebagai berikut:

  • Thermal dan kelembaban
  • Penglihatan dan cahaya
  • Lokasi, orientasi, dan keberadaan
  • Magnetik dan medan elektrik
  • Sentuhan, tekanan dan getaran
  • Audio/suara
  • Berat
  • Bau : sensor gas
  • Akselarasi: deteksi gerak

KESADARAN KONTEKS

Kesadaran konteks dapat diklasifikasikan ke dalam 2 kelompok: yang menggunakan konteks secara pasiv dan yang lainnya yang beradaptasi kepada konteks secara proaktif.

Konteks memodulasi perilaku dengan mempengaruhi tindakan yang digunakan untuk mencapai tujuan serta memilih waktu dan cara bagaimana tindakan ini akan dilakukan. Dengan memperhatikan konteksnya, sebuah agen cerdas dapat lebih cepat memilih perilaku yang tepat untuk mencapai tujuannya, dan ini dapat secara lebih efektif memusatkan perhatiannya dan responsnya kepada kejadian yang tidak terduga. Konteks-kesadaran juga bisa dikategorikan ke dalam set-set fitur sebgai berikut:

  • Pilihan proksimat – pilihan proksimat adalah teknik interaksi di mana sebuah daftar objek (misal:printer) atau tempat (misal:kantor) disajikan dan diman item yang relevan dengan konteks pengguna diberikan penekanan atau dibuat lebih mudah untuk dipilih.
  • Rekonfigurasi kontekstual otomatis – teknik tingkat sistem yang menciptakan pengikatan otomatis ke sumber daya yang tersedia berdasarkan konteks saat ini.
  • Aplikasi perintah kontekstual – layanan executable yang tersedia karena konteks pengguna atau yang pelaksanaannya dimodifikasi berdasarkan konteks pengguna.
  • Tindakan yang dipicu oleh konteks – aplikasi yang secara otomatis memahami konteks keberadaan mereka dan menjalankan layanan secara otomatis bila ada kombinasi konteks yang tepat.