Spanning Tree - Tree Creation

Today, we pick a network with switches and see step by step how the final tree is formed.  Steps will be 

1. Selecting Root Bridge in the network
2. Selecting Root Port for every switch
3. Selecting Designated Port for every segment/link
4. Selecting Alternate Ports 
5. Forwarding/Blocking/Tree

Topology

Selecting Root Bridge

We select the Root Bridge that has least (priority.mac address) value.  As default priority is 32769 for all switches.  Now the switch with least mac address, i.e. Switch A having  0001.439C.7B5E is selected as Root Bridge.

Selecting Root Ports in Every Switch

One of its connected port will be elected as Root Port in a switch. The selecting process will be:

• Lowest Root path cost
• Lowest Sender Bridge ID
• Lowest Sender Port Priority Value
• Lowest port priority value within the switch

Cost of traversing a link depends on the type of physical link used:

• Fast Ethernet 100Mbps costs 19
• Gigabit Ethernet 1000Mbps costs 4

When calculating the cost, we calculate both at the start and the end.  Start of the link incurs zero cost. At the end of the link the cost depends on the physical link.

Root Port of Switch B

We can reach Switch B from Root Bridge through 

• A.Fa0/1 - B.Fa0/1
• A.Fa0/2 - C.Fa0/2 - C.Ga0/1 - B.Ga0/1
• A.Fa0/3 - C.Fa0/3 - C.Ga0/1 - B.Ga0/1
• A.Fa0/2 - C.Fa0/2 - C.Fa0/4 - D.Fa0/4 - D.Fa0/3 - B.Fa0/3
• A.Fa0/3 - C.Fa0/3 - C.Fa0/4 - D.Fa0/4 - D.Fa0/3 - B.Fa0/3 

Have a look at the diagram, we will traverse the path "A.Fa0/3 - C.Fa0/3 - C.Ga0/1 - B.Ga0/1".  From A.Fa0/3, as the distance is not covered yet, path cost will be 0.  When it reaches C.Fa0/3, as it travelled through fast ethernet link, the cost is 19.  At CGa0/1, as it only changed the port within the switch, no additional cost will be incurred.  So, at Ga0/1, cost remains unchanged at 19.  When reaching B.Ga0/1, we would have crossed a Gigabit Ethernet Link that costs '4'.  So, the adding 4 to the cost, the root path cost at B.Ga0/1 will be 23.

Similary, we mark the costs at all the links and choose B.Fa0/1 as Root Port for switch B.

Root Port of Switch C

Root Port of Switch D

Selecting Designated Port for every link/segment

Every link here has 2 points.  There may be cases where a hub will be in between and segment will comprise of more than 2 points.  Selection process

• Lowest Root path cost
• Lowest Bridge ID
• Lowest Port Priority Value

Here is the diagram with all the root path cost calculated for all segments/links.  For every link, we selected Designated port with least root path cost.  One exception, B.Ga0/1 - C.Ga0/1 has equal root path cost.  As Bridge ID of switch B is lesser, B.Ga0/1 gets chosen as Designated port.  Also, observe that all the ports of Root Bridge will be selected as Designated Ports.

Selecting Alternate Port

Any port that is not Root or Designated will become Alternate Port.

Forwarding/Blocking/Tree

All Alternate Ports will be blocked.  All Root Ports and Designated Ports will be in forwarding State.  

For a link to be active, both ends has to be in forwarding state.  If we trace that, final tree will be the result.

Remember, Blocking ports only mean that switch will not pass any data towards that, but BPDUs will be sent and received.  This is because if there is any change in topology then the calculation will happen again, and may be one of the blocking ports comes to forward state or vice-versa.

In Cisco Packet Tracer, we make the setup observe the interface and role columns.  It will match with the tree diagram.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

switch-A#show spanning-tree VLAN0001 Spanning tree enabled protocol ieee Root ID Priority 32769 Address 0001.439C.7B5E This bridge is the root Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Bridge ID Priority 32769 (priority 32768 sys-id-ext 1) Address 0001.439C.7B5E Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Aging Time 20 Interface Role Sts Cost Prio.Nbr Type ---------------- ---- --- --------- -------- -------------------------------- Fa0/3 Desg FWD 19 128.3 P2p Fa0/1 Desg FWD 19 128.1 P2p Fa0/2 Desg FWD 19 128.2 P2p switch-B#show spanning-tree VLAN0001 Spanning tree enabled protocol ieee Root ID Priority 32769 Address 0001.439C.7B5E Cost 19 Port 1(FastEthernet0/1) Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Bridge ID Priority 32769 (priority 32768 sys-id-ext 1) Address 000B.BE33.284A Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Aging Time 20 Interface Role Sts Cost Prio.Nbr Type ---------------- ---- --- --------- -------- -------------------------------- Fa0/3 Desg FWD 19 128.3 P2p Fa0/1 Root FWD 19 128.1 P2p Gi0/1 Desg FWD 4 128.25 P2p switch-C#show spanning-tree VLAN0001 Spanning tree enabled protocol ieee Root ID Priority 32769 Address 0001.439C.7B5E Cost 19 Port 2(FastEthernet0/2) Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Bridge ID Priority 32769 (priority 32768 sys-id-ext 1) Address 00D0.58CE.8C09 Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Aging Time 20 Interface Role Sts Cost Prio.Nbr Type ---------------- ---- --- --------- -------- -------------------------------- Fa0/4 Desg FWD 19 128.4 P2p Fa0/2 Root FWD 19 128.2 P2p Fa0/3 Altn BLK 19 128.3 P2p Gi0/1 Altn BLK 4 128.25 P2p switch-D#show spanning-tree VLAN0001 Spanning tree enabled protocol ieee Root ID Priority 32769 Address 0001.439C.7B5E Cost 38 Port 3(FastEthernet0/3) Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Bridge ID Priority 32769 (priority 32768 sys-id-ext 1) Address 0001.C717.DA66 Hello Time 2 sec Max Age 20 sec Forward Delay 15 sec Aging Time 20 Interface Role Sts Cost Prio.Nbr Type ---------------- ---- --- --------- -------- -------------------------------- Fa0/3 Root FWD 19 128.3 P2p Fa0/4 Altn BLK 19 128.4 P2p

FIFO - file to file transfer

 Today, we try to send a message through FIFO file from one program to another program.

(write)file_send|>>----------------file_fifo.txt----------------------->>|file_recv(read)

Sender Script

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<fcntl.h> int main() { char fil[15]="file_fifo.txt"; char wrch[20]; int siz=20; memset(wrch,'\0',siz); strcpy(wrch,"hello world"); int fd = open(fil,O_WRONLY); int cw=write(fd,wrch,siz); printf("Sender: write -%s- of %d chars to %s\n",wrch,cw,fil); return 0; }

Lets breakdown the script 

1. Line 8: Take the fifo file into a string
2. Line 10-14: Initialize the string with "hello world"
3. Line 16: Open the file in write only mode
4. Line 17: Send the text

Receiver Script

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<stdio.h> #include<stdlib.h> #include<fcntl.h> int main() { char fil[15]="file_fifo.txt"; mkfifo(fil,0666); char rdch[20]; int siz=20; int fd = open(fil,O_RDONLY); printf("Receiver: Waiting for message from Sender\n"); int rd=read(fd,rdch,siz); printf("Receiver: read -%s- of %d chars to %s\n",rdch,rd,fil); return 0; }

Lets breakdown the script

1. Line 8-9: Create a fifo file using mkfifo function. As receiver is to the executed before sender, we have to create fifo file here.
2. Line 11-12: Initialize character array to read the message from Sender program.
3. Line 14: Open the fifo file in read only mode
4. Line 16: Read the message from sender into rdch string

Execution

Start the receiver first.  It will be blocked waiting for message from Sender.

1 2 3

# gcc fifo-recv.c -o fifo-recv # ./fifo-recv Receiver: Waiting for message from Sender

Start the sender in another terminal.  It will send the message.

1 2 3

# gcc fifo-send.c -o fifo-send # ./fifo-send Sender: write -hello world- of 20 chars to file_fifo.txt

Verify in the receiver terminal, receive program would have received the message.

1 2 3 4

# gcc fifo-recv.c -o fifo-recv # ./fifo-recv Receiver: Waiting for message from Sender Receiver: read -hello world- of 20 chars to file_fifo.txt

FIFO - Basic

Today, we replicate whatever we did on Pipes-Basic using FiFo.  It is a pipe, but a name assigned to it.  If I have a pipe, I can access only within the program, forked program and its decendants.  I have to call it using integer array.

If I have a fifo, I can access it just like any other file.  I can pass the information from one program to another.  Now, we pass information from parent to child and then from child to parent using 2 FIFO files.

(read)child|<<----------------file_p2c.txt-----------------------<<|parent(write)

(write)parent|>>----------------file_c2p.txt----------------------->>|child(read)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<unistd.h> #include<fcntl.h> int main() { char p2c[15]="file_p2c.txt"; char c2p[15]="file_c2p.txt"; mkfifo(p2c,0666); mkfifo(c2p,0666); char wrch[20],rdch[20]; int siz=20; memset(wrch,'\0',siz); strcpy(wrch,"hello world"); pid_t id=fork(); if(id != 0) { int wfd = open(p2c,O_WRONLY); int cw=write(wfd,wrch,siz); printf("write -%s- of %d chars to %s\n",wrch,cw,p2c); int rfd = open(c2p,O_RDONLY); int cr=read(rfd,rdch,siz); printf("read -%s- of %d chars from %s\n",rdch,cr,c2p); wait(id,NULL,0); } else { int rfd = open(p2c,O_RDONLY); int cr=read(rfd,rdch,siz); printf("Read -%s- of %d chars from %s\n",rdch,cr,p2c); printf("Sleeping for 5 seconds\n"); sleep(5); int wfd = open(c2p,O_WRONLY); int cw=write(wfd,wrch,siz); printf("write -%s- of %d chars to %s\n",wrch,cw,c2p); } return 0; }

Lets get into breaking down the code: 

Creating FiFo files (#9 to #12)

Use mkfifo procedure to create 2 fifo files with 666 permission(read and write and not execute for all)

Initializing string buffers (#14 to #18)

Create 2 read and write strings.  Initialize write string with "hello world"

Fork a child (#20)

Opening FiFO files;parent to child (#23, #33)

Parent opens the file_p2c.txt in write mode, child opens file_p2c.txt in read mode

Send traffic; parent to child(#24,#25,#34,#35)

Parent writes the wrch string and child reads into rdch string.

Sleep for 5 seconds(#38)

Opening FiFO files; child to parent(#27, #40)

Child opens the file_c2p.txt in write mode, parent opens file_c2p.txt in read mode

Send traffic; child to parent(#28,#29,#41,#42)

Child writes the wrch string and parent reads into rdch string.

Harvest Time

When this program is run

1 2 3 4 5 6

# ./a.out write -hello world- of 20 chars to file_p2c.txt Read -hello world- of 20 chars from file_p2c.txt Sleeping for 5 seconds write -hello world- of 20 chars to file_c2p.txt read -hello world- of 20 chars from file_c2p.txt

Observe that first 2 lines, we transfer data from parent to child.  Sleep for 5 seconds and then transfer the same string from child to parent.

Pipes - Basic

 Today, we demonstrate pipe using a simple example.  It is a way to transfer data between different processes created by fork and its descendants.  It is a unidirectional way of communication.  It is created and handled by kernel and will be controlled by our program.

(read)fdx[0]|<<----------------FDX-----------------------<<|fdx[1](write)

(write)fdy[0]|>>----------------FDY----------------------->>|fdy[1](read)

In the program, we create two pipes FDX and FDY.  We send a string "hello world" from parent to child.  Sleep for 5 seconds.  Send the same string back from child to parent.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<unistd.h> int main() { int fdx[2]; int fdy[2]; char s[20]; int siz,cw,cr; siz=sizeof(s); memset(s,'\0',siz); strcpy(s,"hello world"); pipe(fdx); pipe(fdy); pid_t fk = fork(); if(fk != 0) { cw = write(fdx[1],s,siz); fprintf(stdout,"PIPE FDX: sent %d chars\n",cw); cr = read(fdy[0],s,siz); fprintf(stdout,"PIPE FDY: received -%s- of %d chars\n",s,cr); wait(fk,NULL,0); } else { cr = read(fdx[0],s,siz); fprintf(stdout,"PIPE FDX: received -%s- of %d chars\n",s,cr); fprintf(stdout,"Sleeping for 5 seconds\n"); sleep (5); cw=write(fdy[1],s,siz); fprintf(stdout,"PIPE FDY: sent the received fdx string -%s- of %d chars\n",s,cw); } return (0); }

Lets skip the library declarations.  Breaking down the code.

Preparing String(#13 to #15)

Create string of size 20.  Fill it with all NULLs.  Initialize with "hello world".

Creating Pipes(#17 and #18)

Creating two pipes fdx and fdy

Forking(#20)

Fork the process

Send Traffic from Parent to Child(#23, #24, #31, #32)

Pass string 's' to write function with (write end of the pipe)fdx[1] and read it in the child with (read end of the pipe)fdx[0].

After sleeping for 5 seconds.

Same string is passed to (write end of pipe)fdy[1] at the child and read in the parent using read function with (read end of the pipe)fdy[0].

Conclusion(#28)

Use wait function to pause the parent till child ends.

Harvesting

When executed the shell shows like this

1 2 3 4 5 6

# ./a.out PIPE FDX: sent 20 chars PIPE FDX: received -hello world- of 20 chars Sleeping for 5 seconds PIPE FDY: sent the received fdx string -hello world- of 20 chars PIPE FDY: received -hello world- of 20 chars