Saya kali ini akan membagi tutorial bagaimana cara untuk forwarding pada sebuah switch yang bisa dijadikan sebagai implementasi Software Define Network, saya menggunakan emulator yang dapat di install pada ubuntu 14.04 atau sistem operasi linux yang lain, berikut tutorial dan sourcecode yang sudah saya pelajari selama kuliah.

Forrwarding : Meneruskan suatu paket yang dikirimkan oleh host ke interface lain sesuai dengan tujuan yang sudah ditentukan oleh pengirim paket.

Topologi :

Gambar 1 : Topologi 3 switch 6 host

Prosedur :

Source Code Forwarding1.py :

Screenshoot :

Gambar 2 : Menjalankan forwarding1.py

Gambar 3 : Ping ke semua host

Oke selamat mencoba, semoga berhasil.

A.    Definisi Tree

Tree diartikan sebagai satu kumpulan dari elemen salah satunya disebut dengan akar atau root, dan sisa elemen lainnya terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan sub pohon, atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon ini juga mempunyai akar dan sub-subpohonnya masing-masing, tree bisa juga disebut sebagai sebuah struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah penghubung yang dinamakan vektor. Setiap node dapat memiliki 1 atau lebih node anak. Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya.

Cara penggunaan Tree :
• notasi kurung
• diagram venn
• notasi tingkat
• notasi garis

                Sehingga dari data diatas dapat disimpulkan bahwa, tree dapat didefinisikan sebagai kumpulan simpul atau node dengan satu elemen yang disebut akar (root) dan cabang (node) atau disebut juga sub tree atau sub pohon. Sehingga secara sederhana pohon bisa didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut dengan akar (root) dan elemen yang lainnya (simpul), terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu dengan yang lainnya.

Dibawah ini adalah istilah – istilah umum yang digunakan dalam tree :

a) Prodecessor : node yang berada diatas node tertentu.

b) Successor : node yang berada di bawah node tertentu.

c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

e) Parent : predecssor satu level di atas suatu node.

f) Child : successor satu level di bawah suatu node.

g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.

h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua  karakteristik dari tree tersebut.

i) Size : banyaknya node dalam suatu tree.

j) Height : banyaknya tingkatan/level dalam suatu tree.

k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

l) Leaf : node-node dalam tree yang tak memiliki seccessor.

m) Degree : banyaknya child yang dimiliki suatu node.

Dikutip dari (Struktur Data TREE dan Penjelasaanya Secara Lengkap   New Funday.htm)

         Implementasi dalam pemrograman, dalam pokok bahasan ini akan dibicarakan untuk pohon biner saja. Asumsi awal adalah data yang hendak dimasukkan ke dalam node, bertipe data integer.

1.  Deklarasi Tree

Karena tree tersusun oleh node-node, maka yang perlu kita deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita namai Node.

Contoh deklarasi Source code:

Struct node {

   Int data;

   node *kanan;

   node *kiri;

};

Variabel data adalah untuk menyimpan nilai, sedangkan kiri dan kanan, bertipe pointer, masing-masing yang akan menunjuk ke node anak kiri dan kanan.

2.  Inisialisasi Tree

Untuk pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal adalah pohon itu belum bertumbuh, belum memiliki node sama sekali, sehingga masih kosong.

3.  Menambahkan Node Pada Tree

Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah

node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner:

1.      Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.

2.      Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:

a.  Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

b.  Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan  node  yang  sedang  dicek.  Seandainya  kanan  node  sudah  terisi,  lakukan  kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

Binary Tree

         Pohon biner bisa didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau mempunyai akar dan dua subpohon yang saling terpisah yang disebut dengan subpohon kiri dan sub pohon kanan. Subpohon disebut juga sebagai cabang. Karakteristik dari pohon biner ialah bahwa setiap simpul paling banyak hanya mempunyai dua buah anak. Dengan kata lain derajat tertinggi dari sebuah pohon biner adalah dua. Pengertian daun, root, level, tinggi dan derajad yang berlaku pada pohon juga berlaku pada binary tree. Penyajian binary tree pada komputer di gunakan double link list. Pengertian lain dari Pohon biner adalah sebuah tree yang pada masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul  anak.  Tidak  boleh  lebih.  Pada  pohon  biner,  umumnya  kedua  node  anak  disebut  dengan posisinya, yaitu kiri dan kanan.

         Pada setiap simpul pohon biner hanya berisi dua buah pointer yang menunjuk ke cabang kiri dan cabang kanan, dengan melihat hal tersebut maka lebih baik struktur double link list dapat digunakan dalam binary tree ini.

Pencarian pada BST dapat dilakukan dengan cara rekursif atau iteratif.

Langkah –langkah pencarian:

1. Periksa apakah nilai pada simpul yang sekarang sedang diperiksa sesuai dengan yang dicari. Jika ya maka nilai ditemukan, jika tidak:

2. Jika nilai yang dicari lebih kecil daripada nilai yang sedang diperiksa sekarang: jika simpul yang sekarang sedang diperiksa tidak memiliki anak kiri, maka nilai yang dicari tidak ada pada BST.

Jika ada, ulangi langkah yang sama pada anak kiri.

3. Jika nilai yang dicari lebih besar daripada nilai yang sedang diperiksa sekarang , periksa anak kanan. Jika simpul yang sedang diperiksa tidak punya anak kanan maka nilai yang dicari tidak ada dalam BST. Jika punya, ulangi lankah yang sama pada anak kanan.

b. Insertion/Penyisipan

Awal dari cara kerja penyisipan sama dengan pencarian, jika akar yang sedang diperiksa tidak sama dengan nilai yang ingin disisipi, kunjungi anak pohon kiri atau kanan hingga akhirnya kita menemukan simpul eksternal dan menyisipkan nilai sebagai anak kiri atau kanan—bergantung dari nilai.

Terdapat 3 kasus yang mungkin dan perlu diatasi dalam penghapusan elemen pohon BST:

- Menghapus simpul yang merupakan daun

- Menghapus simpul dengan 1 anak

- Menghapus simpul dengan 2 a

Jadi dapat disimpulkan bahwa pohon biner adalah jenis dari struktur data pohon dimana setiap node hanya bisa paling banyak memiliki 2 anak node. Seperti struktur data lainnya, pohon digunakan untuk menyimpan informasi. Tidak seperti struktur data Stack dan Queue, yang keduanya adalah struktur data linear, pohon (biner) adalah struktur data hirarkis. Untuk mengatakan bahwa struktur data pohon hirarkis berarti elemen pohon terurut diatas atau dibawah elemen lainnya.