Developing

TCP/IP Stack
1. Interface Management & statistics
Part B
2. Dynamic L3 Route Calculation
No More Manual installation of L3 routes

3. Making TCP/IP stack dynamic LIVE**

Dynamic ARP table Entries
Pre-Requisite :
4. Develop Logging Infra Must have completed Part A
Packet Captures

5. Sample L2 Layer Application & Working with Timers

6. Programmable TCP/IP Stack

 Developing
TCP/IP Stack
Part B
1. Interface Management & statistics

2. Dynamic L3 Route Calculation

No More Manual installation of L3 routes

3. Making TCP/IP stack dynamic Pre-Requisite :

Dynamic ARP table Entries Must have completed Part A
4. Develop Logging Infra
Packet Captures
• Fast Paced Course
5. Sample L2 Layer Application & Working with Timers
• Do CLI dev self
6. Programmable TCP/IP Stack
TCP/IP Stack
Part B
End Product ➢ Automatic Routing Table
construction

➢ Timer management

➢ More User Control over

Networking Device

➢ Logging Infrastructure

➢ Appln Development

➢ Programmable TCP/IP Stack

➢ Event Notification
TCP/IP Stack Project -> Interface Management

➢ One of the most important aspect of Real-World Networking is Interface Management

➢ Networking is a game of Managing interfaces !

➢ Interface Management :
➢ Gathering Tx & Rx Statistics per Device’s interfaces
➢ Interface Disable/Enable Or up/down
➢ Creating/Updating Configuration per interfaces
➢ Notifying interface status to interested parties (applications etc ..)
➢ Network Applications need to react to Interface Config change

➢ In this Section, We shall begin adding a functionality to gather interface statistics

➢ Rx Statistics – Number of packets recvd
➢ Tx Statistics – Number of packets sent

➢ We shall enhance this feature in subsequent sections of the course, including

➢ Dump packets sent/recvd on interface
➢ Making the appln react to interface disable/enable OR Config Change

➢ This Course will push our TCP/IP Stack library developed in Part - A from being static towards dynamic .. .!
➢ Real World Demo . .
TCP/IP Stack Project -> Interface Management -> Interface Enable/Disable Problem Statement

➢ A Typical Routing Device allows the provision to admin to Enable or disable the interface of a
Network Device

➢ Properties of Disabled Interface :

➢ Do not send out any data/traffic (discards the outbound traffic just before it is placed on wire)
➢ Discards all data / traffic as soon as recvd (at physical layer itself)

Application

Transport Layer

Network Layer Out-bound traffic

In-bound traffic
I2
I1
Data link layer

Physical Layer
TCP/IP Stack Project -> Interface Management -> Interface Enable/Disable-> Code Changes
➢ Config CLI :
nwcli.c Data Structure Changes :
config node <node-name> interface <if-name> <if-up-down>
typedef struct intf_nw_props_ {
tcp-ip-project> config-node-H1-interface-eth1 $ ?
Parse Success. /*L1 Properties*/
nxt leaf -> STRING | <up | down> bool_t is_up;
...
Add the handler case in intf_config_handler(. . .) ...

Show interface status : Macro:

(enhance dump_intf_props(…) ) net.h
Introduce a macro which checks interface
tcp-ip-project> $ show topology node H1
Up/Down Status
Parse Success.
Topology Name = Dual Switch Topo
#define IF_IS_UP(intf_ptr) \
Node Name = H1, udp_port_no = 40000 /*provide implementation*/
node flags : 0 lo addr : [Link]/32
Interface Name = eth1
Nbr Node L2SW1, Local Node : H1, cost = 1
If Status : UP
IP Addr = [Link]/24 MAC : 82:08:c3:5b:00:0
TCP/IP Stack Project -> Interface Management -> Interface Enable/Disable

➢ Functional Changes

➢ Depending on the up/down status of the interface :

Reject In-bound traffic in function :

_pkt_receive(. . .)

Reject out-bound traffic in function :

send_pkt_out(. . .)

➢ Testing

Use Ping to check if the changes have taken effect

The enable/disable of an interface applies to all types of interfaces – L2 or L3

TCP/IP Stack Project -> Interface Management -> Interface Send/Recv Statistics

➢ A Typical Routing Device allows the provision to admin to Check Send & Recv Statistics per interface of a
Network Device

➢ Send Statistics :
➢ Number of Network Packets sent out of the interface

➢ Recv Statistics
➢ Number of Packets Recvd on an interface

Application

Transport Layer

Network Layer Out-bound traffic

In-bound traffic
I2
I1
Intf->recv++; Data link layer Intf->sent++;

Physical Layer
TCP/IP Stack Project -> Interface Management -> Interface Send/Recv Statistics

➢ CLI :
nwcli.c
show node <node-name> interface statistics
(must show send and recv counters of all interfaces of a device)

tcp-ip-project> $ show node H1 interface statistics ➢ Functional Changes :

Parse Success.
eth1 :: PktTx : 0, PktRx : 0 Increase the pkt_sent counter as soon as pkt is sent in fn

Backend handler fn : show_interface_handler(. . .) in nwcli.c

send_pkt_out(. . .)
Increase the pkt_recv counter as soon as pkt is recvd in fn
➢ Data Structure changes : _pkt_receive(. . .)
typedef struct intf_nw_props_ {
...
➢ Test
/*Interface Statistics*/
uint32_t pkt_recv;
uint32_t pkt_sent; Use Ping
... Interface in down state must not increment
...
} intf_nw_props_t;
its send & recv counters
Sign up Here to get Free 30 days trial access to all our courses
[Link]
TCP/IP Stack Project -> Packet generator

S B D

eths2 Lo : [Link]
UDP : 2003
L
pkt_gen.c • Feed the pkt into S as if S is receiving
the pkts on its local intf eths2
• S’s TCP/IP stack then process the pkt
as per the pkt headers
A

➢ So far, we have been using ping to test the new feature we implement in TCP/IP stack
➢ Instead, now we write a pkt generator - small separate program which would feed stream of pkts into our TCP/IP stack
➢ Terminology :
➢ Pseudo TCP/IP Stack - Our TCP/IP stack Library
➢ Actual TCP/IP Stack - The Actual TCP/IP Stack running on your local machine in kernel space
TCP/IP Stack Project -> Packet generator

S B D

eths2 Lo : [Link]
UDP : 2003
L
pkt_gen.c

➢ We want to generate stream of pkts : S sends Pseudo ICMP packet to Destination D with dest ip address : [Link]
➢ Equivalent to run node S ping [Link]
➢ pkt_gen.c is a simple UDP program which generate and sends UDP packets
➢ Revise how we implemented the packet exchange infrastructure in Part-A
TCP/IP Stack Project -> Packet generator

[Link]

The Bigger Picture S (2001)

ethb
B(2002)
ethd
D(2003)

(Recap) eths2

Actual TCP/IP Stack

We will be going to write our pkt generator application working

on the same TCP/IP Stack pkt exchange design
TCP/IP Stack Project -> Actual and Pseuodo Headers

➢ When you trigger run node S ping [Link]

Cmd on our TCP/IP stack prompt, how does the S B D
actual pkt look like which is pushed by eths1 ethb1 ethb2 ethd1
send_pkt_out(..) down to the actual TCP/IP
Stack running on your local machine Lo : [Link] eths2 Lo : [Link] Lo : [Link]
UDP : 2001 UDP : 2002 UDP : 2003
L
• sudo tcpdump -i lo -v -e udp Actual pkt content
etha1 Virtually going from
A to B

A Actual UDP Payload

ETH Hdr IP Hdr UDP Hdr Pseudo ETH Hdr Pseudo IP Hdr
Dst mac = 0 Proto = UDP Dst port = 2002 Aux Info : ethb1 Dst mac = mac(ethb1) Proto = ICMP FCS = 0 FCS =
Src mac = 0 ttl = 64 Src port = 2001 Src mac = mac(eths1) ttl = 64 <some
Type = Src ip = [Link] Type = ox0800 Src ip = [Link] actual
ox0800 Dst ip = [Link] Dst ip = [Link] value>

Actual Hdrs for actual TCP/IP Stack Pkt for our Simulated TCP/IP stack
This is just a UDP payload for actual TCP/IP Stack
TCP/IP Stack Project -> Actual and Pseuodo Headers

➢ When you trigger run node S ping [Link]

Cmd on our TCP/IP stack prompt, how does the S B D
actual pkt look like which is pushed by eths1 ethb1 ethb2 ethd1
send_pkt_out(..) down to the actual TCP/IP
Stack running on your local machine Lo : [Link] eths2 Lo : [Link] Lo : [Link]
UDP : 2001 UDP : 2002 UDP : 2003
L
• sudo tcpdump -i lo -v -e udp Actual pkt content
etha1 Virtually going from
B to D

A Actual UDP Payload

ETH Hdr IP Hdr UDP Hdr Pseudo ETH Hdr Pseudo IP Hdr
Dst mac = 0 Proto = UDP Dst port = 2003 Aux Info : ethd1 Dst mac = mac(ethd1) Proto = ICMP FCS = 0 FCS =
Src mac = 0 ttl = 64 Src port = 2002 Src mac = mac(ethb2) ttl = 63 <some
Type = Src ip = [Link] Type = ox0800 Src ip = [Link] actual
ox0800 Dst ip = [Link] Dst ip = [Link] value>

Actual Hdrs for actual TCP/IP Stack Pkt for our Simulated TCP/IP stack
This is just a UDP payload for actual TCP/IP Stack
Dst mac =Stack
TCP/IP 0 Proto = UDP-> Packet
Project Dstgenerator
port = 2001 Aux Info : eths2 Dst mac = oxFF Proto = ICMP FCS = 0 FCS =
Src mac = 0 ttl = 64 Src port = 0 Src mac = 0 ttl = 64 <some
Type = Src ip = [Link] Type = ox0800 Src ip = [Link] actual Actual
ox0800 Dst ip = [Link] Dst ip = [Link] value>
pkt

Actual Hdrs for actual TCP/IP Stack Pkt for our Simulated TCP/IP stack

S eths1 ethb1 ethb2 ethd1 D

B
Lo : [Link] eths2 Lo : [Link] Lo : [Link]
UDP : 2001 UDP : 2002 UDP : 2003
L
Input ? pkt_gen.c
etha1
A Actual TCP/IP Stack

Input to pkt_gen.c for Sending “our ICMP” pkts from S to D :

Dst IP : [Link] Aux info Ethernet Hdr IP Hdr Appln Hdr
Src ip : [Link] eths2 Dst mac = Proto = ICMP Appln Payload
Protocol : IPPROTO_UDP mac(eths2)/0xFF ttl = 64 (Not present in
Actual Hdrs Src mac = mac(etha1)/0 Src ip = [Link] this case)
Src port No : 0 (don’t matter) Type = ETH_IP Dst ip = [Link]
Dst Port No : 2001
UDP Payload :
Pseudo Hdrs
TCP/IP Stack Project -> Packet generator

New file : tcpip_stack/pkt_gen.c

Steps :
1. Create UDP socket
int udp_sock_fd = socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP );

2. Prepare packet
Aux info + Pseudo headers

3. Send data using socket created in 1 to [Link]:UDP Port no of Src node

(Socket layer will create Actual header for you)

struct sockaddr_in dest_addr;

struct hostent *host = (struct hostent *) gethostbyname("[Link]"); /*Dst ip Address*/
dest_addr.sin_family = AF_INET;
dest_addr.sin_port = dst_udp_port_no; /*UDP Port no of node S*/
dest_addr.sin_addr = *((struct in_addr *)host->h_addr);

rc = sendto(sock_fd, pkt_data, pkt_size, 0,

(struct sockaddr *)&dest_addr, sizeof(struct sockaddr));

Update Project Makefile

TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table

➢ We love our TCP/IP Stack library ☺, so, let us improve its functionality

➢ By now, you must have realized, every time we need to install L3 routes in L3 devices manually

➢ It is a painful exercise and manually doing it is error prone

➢ In this section, We would implement an algorithm using which

➢ Each L3 device in the topology computes L3 routes to every other device
➢ Loop free
➢ Leverage ECMP (Equal Cost Multiple Path)
➢ Re-correct routes (convergence) when topology changes (such as link down/up etc..)

➢ Demo … !
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table

Pre-Requisites

➢ Pls complete Appendix section A.1 and A.2 to cover up theory behind construction of L3 routing table

➢ In these Appendix Section, I cover topics from the point of getting conceptual understanding, and not understanding
implementation details

➢ Once you complete these Appendix Section, We shall be in a position to actually implement it

➢ From next lecture Video, I presume, you have the concept clarity on Routing Table Construction Algorithm and
approach, We will discuss implementation straight away

➢ This will probably first time you would realize how Networking biased algorithms are implemented
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table

➢ We will be going to add SPF algorithm to our TCP/IP stack library as a new application

➢ It would mean, SPF algorithm implementation shall be an extension to our TCP/IP stack library and not a
core part of it

➢ We shall be going to develop several other applications on top of our TCP/IP stack library in plugin-play model

➢ This would NOT require us to change/update TCP/IP stack lib core code in anyway

➢ Real world example of plugin play model :

• This is how we add additional functionality to Linux kernel through Linux kernel Modules without touching
linux kernel base core code
• Device Drivers SPF
ALGO
NMP

Application Layer DDCP OSPF

Network Layer
etc
Data Link Layer
Application Code
Physical Layer
TCP/IP Stack Core Code
We developed in Part A
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Getting started

Getting Started

➢ Creating new Spf algo Application files and folders in the project code

New file : Layer5/spf_algo/spf.c

Update Project Makefile

➢ CLI Support (nwcli.c)

run node <node-name> spf

backend handler : spf_algo_handler( ) -> void compute_spf (node_t *spf_root); /*Layer5/spf_algo/spf.c*/

show node <node-name> spf

backend handler : spf_algo_handler( ) -> void show_spf_results(node_t *node) ; /*Layer5/spf_algo/spf.c*/

TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Preparing for SPF Algo Implementation

Preparation

➢ Before we write any code to implement SPF algo, we need to do some groundwork :

➢ Understand New Data Structures

➢ Helper APIs used

➢ Operations with Priority Queue

TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Data Structures

➢ Every node would have a data structure which would store all information related to spf algorithm

➢ We need to define Two Data structures to implement spf algorithm

typedef struct node_{

...
... 2
spf_data_t *spf_data;
1 typedef struct spf_result_{
...
node_t *node;
} node_t; typedef struct spf_data_{ uint32_t spf_metric;
node_t *node; nexthop_t *nexthops[MAX_NXT_HOPS];
Valid only for spf root  glthread_t spf_result_head; glthread_t spf_res_glue;
} spf_result_t;
/*Temp fields used for calculations*/
uint32_t spf_metric;
Valid for other nodes  glthread_t priority_thread_glue;
nexthop_t *nexthops[MAX_NXT_HOPS];
} spf_data_t;
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Data Structures

➢ Example Snapshot :
Lo : [Link] Lo : [Link] Lo : [Link]
typedef struct nexthop_{ R1 R2 R3
eth0 eth1 eth2 eth3
char gw_ip[16]; 3 [Link]/24 [Link]/24 [Link]/24 [Link]/24
interface_t *oif; eth7 eth3
uint32_t ref_count; [Link]/24 [Link]/24
} nexthop_t;

[Link] [Link]
NH1 = R1-eth0 NH2 = R1-eth7
0 0 eth6 eth5
[Link]/24 [Link]/24

R4
Lo: [Link]

R2 R4 R3
10 10 20 Result of
R1 as spf root
node->spf_data-> NH1 NH2 NH1, NH2 compute_spf(R1)
spf_result_head
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

➢ We need to write some Helper APIs (arnd 10) which would make it easier to implement Spf algo

➢ These Helper APIs shall be invoked from compute_spf(..) fn

➢ You must thoroughly test these APIs before actually start using them .. Otherwise Nightmare !

➢ You can write a small driver program to test the APIs you will write Or Cross check against partB soln code base
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 1 :

net.h/.c
R1 R2
bool_t eth0 L eth1
is_interface_l3_bidirectional (interface_t *interface); /*ptr to R1-eth0*/ [Link]/24 [Link]/24

R1-eth0 is L3 bidirectional if and only if :

• R1-eth0 and Nbr interface R2-eth1 are UP &&

• R1-eth0 and R2-eth1 are configured with IP addresses &&
• IP Addresses are in same subnet &&
• None of the interfaces are operating in L2 mode ( ACCESS or TRUNK)
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 2 :

spf.c void
spf_flush_nexthops (nexthop_t **nexthop){
void int i = 0;
spf_flush_nexthops(nexthop_t **nexthop);
Eg : spf_flush_nexthops (node->spf_data->nexthops); if(!nexthop) return;
spf_flush_nexthops (spf_result->nexthops);
for( ; i < MAX_NXT_HOPS; i++){

if(nexthop[i]){
assert(nexthop[i]->ref_count);
nexthop[i]->ref_count - = 1;
if (nexthop[i]->ref_count == 0){
free(nexthop[i]);
}
nexthop[i] = NULL;
}
}
}
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 3 :
spf.c

static inline void

free_spf_result(spf_result_t *spf_result) {
Reference :
spf_flush_nexthops(spf_result->nexthops); typedef struct spf_result_{
remove_glthread(&spf_result->spf_res_glue); node_t *node;
free(spf_result); uint32_t spf_metric;
} nexthop_t *nexthops[MAX_NXT_HOPS];
glthread_t spf_res_glue;
} spf_result_t;
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 4 :
spf.c
typedef struct nexthop_{
static nexthop_t *
create_new_nexthop (interface_t *oif) { /*ptr to S-eth0*/
char gw_ip[16];
nexthop_t *nexthop = calloc(1, sizeof(nexthop_t)); interface_t *oif;
nexthop->oif = oif; uint32_t ref_count;
interface_t *other_intf = &oif->link->intf1 == oif ? \ } nexthop_t;
&oif->link->intf2 : &oif->link->intf1;
if(!other_intf){
free(nexthop);
return NULL; spf_root S R2
} eth0 L eth1
strncpy(nexthop->gw_ip, IF_IP(other_intf), 16); [Link]/24 [Link]/24
nexthop->ref_count = 0;
return nexthop;
}
Nh = { [Link] , ptr to S-eth0, 0 }
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 5 :
spf.c API6 :
spf.c
static bool_t
spf_insert_new_nexthop(nexthop_t **nexthop_arry, static bool_t
nexthop_t *nxthop) { spf_is_nexthop_exist(nexthop_t **nexthop_array,
nexthop_t *nxthop){
int i = 0;
int i = 0;
for( ; i < MAX_NXT_HOPS; i++){
for( ; i < MAX_NXT_HOPS; i++){
if(nexthop_arry[i]) continue;
nexthop_arry[i] = nxthop;
if (!nexthop_array[i])
nexthop_arry[i]->ref_count++;
return FALSE;
return TRUE;
}
if (nexthop_array[i]->oif == nxthop->oif)
return FALSE;
return TRUE;
} }
return FALSE;
}
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 7 :
spf.c
/* Copy all nexthops of src to dst, do not copy which are already
* present*/
static int
spf_union_nexthops_arrays(nexthop_t **src, nexthop_t **dst);

• Increase the ref count of nexthops copied

• Do not copy which are already present in dst
• Use spf_is_nexthop_exist(..) to verify if Nexthop NH already present in dst

API returns the number of Nexthops copied

TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 8 :
spf.c
API to compare two spf_data_t objects

/*Return -1 , 0 or 1 */
static int
spf_comparison_fn(void *data1, void *data2){
 This API is used as a fn pointer to PQ API
spf_data_t *spf_data_1 = (spf_data_t *)data1;
spf_data_t *spf_data_2 = (spf_data_t *)data2;  PQ will use this function to insert a new spf_data
object in PQ as per the priority (spf_metric)
if(spf_data_1->spf_metric < spf_data_2->spf_metric)
return -1;
if(spf_data_1->spf_metric > spf_data_2->spf_metric)
return 1; Reference :
return 0; typedef struct spf_data_{
} ...
/*Temp fields used for calculations*/
uint32_t spf_metric;
...
} spf_data_t;
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 9 :
spf.c
API to look up spf_result_t object from spf result list of spf_root using node ptr as lookup key

static spf_result_t *
spf_lookup_spf_result_by_node(node_t *spf_root, node_t *node){

glthread_t *curr;
spf_result_t *spf_result;
spf_data_t *curr_spf_data;

ITERATE_GLTHREAD_BEGIN(&spf_root->spf_data->spf_result_head, curr){

spf_result = spf_res_glue_to_spf_result(curr);
if(spf_result->node == node)
return spf_result;
} ITERATE_GLTHREAD_END(&spf_root->spf_data->spf_result_head, curr);
return NULL;
R2 R4 R3
}
10 10 20
spf_root->spf_data-> NH1 NH2 NH1, NH2
spf_result_head
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Helper APIs

API 10 :
spf.c

Short-hand Macros :

#define INFINITE_METRIC 0xFFFFFFFF typedef struct spf_data_{

node_t *node;
glthread_t spf_result_head;
uint32_t spf_metric;
#define spf_data_offset_from_priority_thread_glue \ glthread_t priority_thread_glue;
((size_t)&(((spf_data_t *)0)->priority_thread_glue)) nexthop_t *nexthops[MAX_NXT_HOPS];
} spf_data_t;

#define SPF_METRIC(nodeptr) (nodeptr->spf_data->spf_metric)

TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> PQ Mgmt

Priority Queue Operations

➢ SPF Algorithm uses PQ for its implementation

➢ We insert node->spf_data object into PQ on the basis of node->spf_data->spf_metric

➢ Initialization

➢ Insertion

➢ Deletion

➢ Dequeue
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> PQ Mgmt

➢ Operations with Priority Queue

Reference :
typedef struct spf_data_{
node_t *node;
glthread_t spf_result_head;
uint32_t spf_metric;
glthread_t priority_thread_glue;
nexthop_t *nexthops[MAX_NXT_HOPS];
} spf_data_t;

R1->spf_data R2->spf_data R3->spf_data

ptr to R1 ptr to R2 ptr to R3
spf_result_head spf_result_head spf_result_head
PQ of spf_root S maintained
in increasing order of spf_metric  spf_metric = spf_metric = spf_metric =
20 30 40
glthread_t priority_lst;
nexthops nexthops nexthops

• PQ stores the spf_data objects of nodes of the topology in the increasing

order of node->spf_data->spf_metric
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> PQ Mgmt

➢ Operations with Priority Queue

Checking if PQ Is Empty :
Reference :
IS_GLTHREAD_LIST_EMPTY (&priority_lst)
typedef struct spf_data_{
node_t *node;
Note : End of the Day, PQ is just a glthread (Doubly linked list)
glthread_t spf_result_head;
uint32_t spf_metric;
glthread_t priority_thread_glue;
nexthop_t *nexthops[MAX_NXT_HOPS];
} spf_data_t;

ptr to R1 ptr to R2 ptr to R3

spf_result_head spf_result_head spf_result_head
PQ of spf_root S maintained
in increasing order of spf_metric  spf_metric = spf_metric = spf_metric =
20 30 40
glthread_t priority_lst;
nexthops nexthops nexthops
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> PQ Mgmt

➢ Operations with Priority Queue

Insertion into PQ :
Reference : glthread_priority_insert (&priority_lst,
typedef struct spf_data_{ &node->spf_data->priority_thread_glue,
node_t *node; spf_comparison_fn,
glthread_t spf_result_head; spf_data_offset_from_priority_thread_glue);
uint32_t spf_metric;
glthread_t priority_thread_glue;
nexthop_t *nexthops[MAX_NXT_HOPS];
} spf_data_t;

ptr to R1 ptr to R2 ptr to R3

spf_result_head spf_result_head spf_result_head
PQ of spf_root S maintained
in increasing order of spf_metric  spf_metric = spf_metric = spf_metric =
20 30 40
glthread_t priority_lst;
nexthops nexthops nexthops
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> PQ Mgmt

➢ Operations with Priority Queue

Removal from PQ :
Reference : remove_glthread(&spf_data->priority_thread_glue);
typedef struct spf_data_{
node_t *node;
glthread_t spf_result_head;
uint32_t spf_metric;
glthread_t priority_thread_glue;
nexthop_t *nexthops[MAX_NXT_HOPS];
} spf_data_t;

ptr to R1 ptr to R2 ptr to R3

spf_result_head spf_result_head spf_result_head
PQ of spf_root S maintained
in increasing order of spf_metric  spf_metric = spf_metric = spf_metric =
20 30 40
glthread_t priority_lst;
nexthops nexthops nexthops
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> PQ Mgmt

➢ Operations with Priority Queue

Dequeue from PQ :
Reference :
glthread_t *curr;
typedef struct spf_data_{
node_t *node;
curr = dequeue_glthread_first (&priority_lst);
glthread_t spf_result_head; spf_data_t *curr_spf_data = priority_thread_glue_to_spf_data (curr);
uint32_t spf_metric;
glthread_t priority_thread_glue;
nexthop_t *nexthops[MAX_NXT_HOPS];
} spf_data_t;

ptr to R1 ptr to R2 ptr to R3

spf_result_head spf_result_head spf_result_head
PQ of spf_root S maintained
in increasing order of spf_metric  spf_metric = spf_metric = spf_metric =
20 30 40
glthread_t priority_lst;
nexthops nexthops nexthops
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm

➢ We will now implement SPF Algorithm Step by Step

➢Initialization Phase 1
➢Step 1, 2 and 3

➢Execution Phase 2
➢Step 4, 5 and 6

➢ECMP support in l3_route_t

➢Route Calculation Phase 3 (Step 7)

TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Initialization Phase

Initialization : Part 1
For Node • Initialize Metrics
N
N, spf_data calloc spf_data • delete old spf results if any
exist ? • Remove Nodes from PQ
• Flush Nexthops if any
Y
void
init_node_spf_data (node_t *node,
N bool_t delete_spf_result);
N ==
spf_root 1

8
4
A B
Y 3
0
10
delete old spf_result list S 5
4
6
D C

8
Init spf_metric = INFINITE
Remove node N from PQ
Flush nexthops
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Initialization Phase

Next-hop Calculation

spf_root S R2 spf_root S R2
eth0 L1(5) eth1
eth0 L eth1 [Link]/24 [Link]/24
[Link]/24 [Link]/24 eth1 L2(5) eth0
[Link]/24 [Link]/24
Nh = { [Link] , ptr to S-eth0, 0 }
Nh1 = { [Link] , ptr to S-eth0, 0 }
Nh2 = { [Link] , ptr to S-eth1, 0 }

spf_root S R2
eth0 L1(5) eth1
[Link]/24 [Link]/24  The nexthops computed by spf root are stored in
eth1 L2(10) eth0 Nbr’s spf_data->nexthops[ ] array
[Link]/24 [Link]/24

 Nexthop Eligibility
Nh = { [Link] , ptr to S-eth1, 0 } is_interface_l3_bidirectional( )
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Initialization Phase

Example

A->spf_data->nexthops
NH1 : [S-eth1, [Link], 0 ]
NH2 : [S-eth2, [Link], 0 ]
A
A->spf_data->spf_metric = 3
eth4

[Link]

B->spf_data->nexthops
B NH1 : [S-eth4, [Link], 0 ]

B->spf_data->spf_metric = 6
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Initialization Phase
For each NH = (Nbr, oif, Gw) of NH1 : [S-eth1,

8
spf_root [Link], 0 ] 4
A B
3
0
10
S 5
Is NH N Explore 4
eligible next NH 6
? D C
NH2 : [S-eth2,

8
N [Link], 0 ]
Y
2.2 spf_flush_nexthops(
2.1 Nbr->spf_data->nexthops)
link_cost(oif) link_cost(oif) NH = create_new_nexthop(oif);
N Y spf_insert_new_nexthop(
< ==
SPF_METR SPF_METR Nbr->spf_data->nexthops,
IC (Nbr) ? IC (Nbr) ? NH)
SPF_METRIC(nbr) = get_link_cost(oif);

Y
Initialization : Part 2
Initialize direct nexthops of spf root
spf_flush_nexthops(Nbr->spf_data->nexthops)
NH = create_new_nexthop(oif);
spf_insert_new_nexthop( void
Nbr->spf_data->nexthops, NH) initialize_direct_nbrs (node_t *spf_root);
SPF_METRIC(nbr) = get_link_cost(oif);
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Initialization Phase

Looping Macro
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Initialization Phase

glthread_t priority_lst;
init_glthread(&priority_lst); Initialization: Part 3
3 Initialize Priority Queue
Add Spf_root in PQ

glthread_priority_insert (&priority_lst,
&spf_root->spf_data->priority_thread_glue,
spf_comparison_fn,
spf_data_offset_from_priority_thread_glue);

8
NH1 : [S-eth1,
[Link], 0 ]
4
PQ = { S } A B
3
0
10
S 5
4
6
D C
NH2 : [S-eth2,

8
[Link], 0 ]
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> CLI Requirements

➢ Now that we have finished implementation of Core SPF Algorithm, Let us test it before proceeding forward
➢ File : spf.c

➢ Use CLI : run node <node-name> spf

➢ To Trigger SPF on a particular node

➢ spf_algo_handler( ) - -> compute_spf(node_t *node)

➢ Use CLI : show node <node-name> spf

➢ To Check SPF result list of a particular node

➢ spf_algo_handler( ) - -> show_spf_results(node_t *node)

➢ Use CLI : run spf all

➢ Running SPF on all nodes of the Topology

➢ spf_algo_handler( ) - -> compute_spf_all_routers(graph_t *topo)
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Execution Phase

spf_record_result( )
N
Is PQ
N = dequeue_glthread_first(PQ)
Empty ?

Record spf_result_t for node N

Y
spf_result_t *spf_result =
Is N == calloc(1, sizeof(spf_result_t));
Enter into Route spf_root spf_result->node = N 5
7 Calculation Phase N
? spf_result->spf_metric =
spf_install_routes(spf_root) N->spf_data->spf_metric
4 spf_union_nexthops_arrays(
Y curr_spf_data->nexthops,
spf_result->nexthops);

For Every Eligible Nbr of N,

If Nbr not in PQ then
Push Nbr into PQ Add spf result into spf result list of spf root
Process Nbrs of Node N
glthread_add_next(
spf_explore_nbrs(N, PQ)
&spf_root->spf_data->spf_result_head,
&spf_result->spf_res_glue);
6
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Exploring Rules

Algorithm Rules When a new node is explored

void spf_explore_nbrs( )

➢ If node Y is explored from predecessor node X with a better metric

Cost = m
i.e. x + m < y X Y
➢ Remove nexthops of Y
➢ Copy nexthops of X into Y Cost = x Cost = y

➢ Remove Y from PQ if present, and add it back to PQ nh1, nh2 nh1, nh3
➢ Cost(y) = Cost(x) + m

➢ If node Y is explored from predecessor node X with a same metric

i.e. x + m = y (ECMP case)
➢ Keep existing nexthops of Y
➢ Copy nexthops of X into Y
➢ Remove Duplicates in next-hop list of Y, if any

➢ If node Y is explored from predecessor node X with higher metric

i.e. x + m > y
➢ Ignore Y through this link
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Execution Phase
Process Nbrs of Node N
spf_explore_nbrs (Curr_N, PQ)
6
Continue Continue
For Every Eligible Nbr of Curr_N

ECMP case
SPF_METRIC SPF_METRIC
(Curr_N) + (Curr_N) +
spf_union_nexthops_arrays(
link_cost(Curr_N, link_cost(Curr_N,
Curr_N->spf_data->nexthops,
Nbr) < Nbr) ==
N Y Nbr->spf_data->nexthops);
SPF_METRIC SPF_METRIC
(Nbr) (Nbr) 6.2

N
Y
spf_flush_nexthops(Nbr->spf_data->nexthops); Continue
spf_union_nexthops_arrays(
curr_node->spf_data->nexthops,
nbr->spf_data->nexthops);
SPF_METRIC(Nbr) = SPF_METRIC(Curr_N) +
get_link_cost(Curr_N, Nbr); 6.1 spf_flush_nexthops(Curr_N->spf_data->nexthops);
Remove Nbr from PQ if present
When all Nbrs of Curr_N are processed
Add back Nbr in PQ
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Testing

➢ It is important that we test our implementation of SPF algorithm on various different topologies and verify the correctness
of the output before proceeding forward

➢ You need to run :

➢ run node <node-name> spf << to trigger spf on a particular node
➢ run spf all << to trigger spf on all nodes of topology
➢ show node <node-name> spf << see the output of spf run

➢ In addition, change topologies using various existing CLIs as below, and trigger run spf all and
verify all nodes update their spf results
➢ conf node <node-name> interface <if-name> metric <metric-val>
➢ conf node <node-name> interface <if-name> [up | down]

➢ Attached is the document which shows the topologies you need to be build and testing procedure
➢ Pls follow the instructions against each Test in the document

➢ Proceed to next section only when you have verified that your SPF implementation reveals correct output in all cases
➢ Fix the bugs/anomalies if any
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Route Calculation

➢ We will use the output produced by SPF algorithm for final Routing table calculation of SPF root node

➢ We need to implement fn :

int spf_install_routes (node_t *spf_root) /*Phase 3/3, Step 7 */

➢ But before that, we need to make some minor code changes to make our Routing Table and
L3 routes ECMP aware
TCP/IP Stack Project -> ECMP Support

➢ The L3 route having more than 1 nexthops is an ECMP aware route

➢ Assumption : cost of each link is 1

R1’s RT entry
[Link]/32 [Link] eth0 2 build_square_topo( )
[Link] eth7
Lo : [Link] Lo : [Link] Lo : [Link]
R1 R2 R3
RT Table / L3 route data structure must allow
eth0 eth1 eth2 eth3
a provision to allow multiple nexthops [Link]/24 [Link]/24 [Link]/24 [Link]/24
associated with an L3 route eth7 eth3
[Link]/24 [Link]/24

How ECMP help ??

Ans : Distribute traffic to utilize Network available
Bandwidths/links
Protection against link/node failures eth6 eth5
[Link]/24 [Link]/24
Next : Let us discuss Code changes to implement ECMP R4
Lo: [Link]
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Route Calculation

Implementing ECMP

Current : New :

typedef struct l3_route_{ typedef struct l3_route_{

char dest[16]; /*key*/ char dest[16]; /*key*/
char mask; /*key*/ char mask; /*key*/
bool_t is_direct; bool_t is_direct;
char gw_ip[16]; nexthop_t *nexthops[MAX_NXT_HOPS];
char oif[IF_NAME_SIZE]; uint32_t spf_metric;
glthread_t rt_glue; int nxthop_idx;
} l3_route_t; glthread_t rt_glue;
} l3_route_t;

Re-write from scratch : rt_table_add_route( ) to accommodate this change.

User should be able to install MAX_NXT_HOPS nexthops for a given route

Update clear_rt_table( ) to free the nexthops first before freeing the route, else it will cause mem leak
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Route Calculation

Consider an L3 route with 4 nexthops :

nh1…nh4

New :

typedef struct l3_route_{ Nh1

char dest[16]; /*key*/
char mask; /*key*/ Nh2
bool_t is_direct; Nh3
nexthop_t *nexthops[MAX_NXT_HOPS];
Nh4
uint32_t spf_metric;
int nxthop_idx; layer3.c/.h
glthread_t rt_glue;
nexthop_t *
} l3_route_t;
l3_route_get_active_nexthop(l3_route_t *l3_route);

• nxthop_idx - points to the nexthop which will be used by the route to forward the next pkt
• Every time the route forwards the pkt, nxthop_idx is incremented to point to the next nexthop in array
• Route forwards the pkt P1,P2,P3,P4,P5… using nexthops NH3,NH4,NH1,NH2,NH3…
• Update Functions : layer3_ip_pkt_recv_from_layer2( ) & demote_packet_to_layer3 ( ) to use new API to retrieve the
forwarding nexthop of the route
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Spf Algorithm -> Route Calculation

int
spf_install_routes(node_t *spf_root);

➢ Use spf_root->spf_data->spf_result_head list to compute routes to loopback address of all

other L3 devices of the topology

➢ Returns number of routes installed

Spf_root S
SPF Algo Result Final Routing Table of Spf Root S
Dest Node Oif Gateway cost Nexthop Dest Address Oif Gateway cost Nexthop
Replace Dest Nodes
A eth1 [Link] 3 A With their loop-back [Link]/32 eth1 [Link] 3 A
Address
D eth2 [Link] 4 D [Link]/32 eth2 [Link] 4 D
B eth1 [Link] 7 A [Link]/32 eth1 [Link] 7 A
C eth2 [Link] 10 D [Link]/32 eth2 [Link] 10 D
TCP/IP Stack Project -> Dynamic Construction of L3 Routing Table -> Routing Table Calculation on Startup

Initializing the TCP/IP stack on Start up

➢ We may need to do some one-time initialization on TCP/IP stack library start up

➢ For example:
➢ We want L3 Routing Tables get populated automatically as soon as we start our project
➢ User should not be compelled to run “run spf all” on project start up to populate RTs

➢ Write a new file : tcp_stack_init.c

➢ Write a fn : init_tcp_ip_stack( )
➢ Call this fn from main( )
Let TCP/IP Stack tell you what’s going on !
TCP/IP Stack Project -> Logging Infra -> Problem Statement

➢ Nodes of our Emulated topology forward and Recv Packets

➢ Our TCP/IP Stack library could be used to implement more new Network protocols which would generate their own
Network packets (Application headers)

➢ The common way of debugging and troubleshooting networks is to analyse what packets are being sent or recvd by node(s)
of the topology

➢ On real devices, we have tools to capture and analyze packet contents flowing across the network
➢ Tcpdump
➢ Wireshark

➢ For our Emulated TCP/IP stack library, standard tools would not likely to work and we would like to develop the way
our TCP/IP stack library could emit out what packets are in flows across the network

➢ This would help in developing and debugging Network application immensely

➢ Lets start . .
TCP/IP Stack Project -> Logging Infra -> Working Demo

➢ Let us see what we are getting into …

➢ Let us see how logging is expected to work ..

TCP/IP Stack Project -> Logging Infra -> Goals

Goals :

➢ User should be able to enable or disable logging at will using CLIs

➢ User should have a choice whether he wants to enable logging for only sent or only recv pkts or both

➢ Extra : User should have a choice whether he wants to enable logging for some selective interfaces of a node

➢ New Files :
tcpip_stack/tcp_ip_trace.c
tcpip_stack/tcp_ip_trace.h

➢ Explore use of sprint/snprintf from internet. We would be using this fn extensively for logging

➢ Let us first brainlessly write all required APIs first, then we shall see how to use the APIs for logging and control logging
using CLIs
TCP/IP Stack Project -> Logging Infra -> logging APIs hierarchy

➢ First, we need set of APIs to format the headers of various types into buffer

void tcp_dump( )

int tcp_dump_ethernet_hdr( ) int tcp_dump_ip_hdr( )

int tcp_dump_ip_hdr( ) int tcp_dump_arp_hdr( ) int tcp_dump_appln_hdr_protocol_icmp( )

tcp_ip_trace.c/.h void tcp_write_data( )

int int int int

tcp_dump_ethernet_hdr( tcp_dump_ip_hdr( tcp_dump_arp_hdr( tcp_dump_appln_hdr_protocol_icmp(
char *out_buff, char *out_buff, char *out_buff, char *out_buff,
ethernet_hdr_t ip_hdr_t *ip_hdr, arp_hdr_t *arp_hdr, char *appln_data,
*eth_hdr, uint32_t pkt_size); uint32_t pkt_size); uint32_t pkt_size);
uint32_t pkt_size);
• APIs returns number of bytes written to the output buffer
TCP/IP Stack Project -> Logging Infra -> logging hierarchy

void tcp_dump( )

int tcp_dump_ethernet_hdr( ) int tcp_dump_ip_hdr( )

int tcp_dump_ip_hdr( ) int tcp_dump_arp_hdr( ) int tcp_dump_appln_hdr_protocol_icmp( )

void tcp_write_data( )
static void
tcp_dump (int sock_fd, << if 0 then formatted pkt contents shall be written to console, -1 otherwise
FILE *log_file1, << Node level Log file ptr into where formatted pkt contents shall be w
Fn to parse the pkt FILE *log_file2, << Per interface level Log file ptr into where formatted pkt contents shall be writt
and prepare formatted char *pkt, << Pkt pointer to parse
output in buffer memory uint32_t pkt_size, << pkt size
hdr_type_t hdr_type, << Starting hdr type of the pkt
char *out_buff, << output buffer into which the formatted pkt content would b
uint32_t write_offset, << starting position in output buffer to write formatted pkt content
uint32_t out_buff_size); << size of output buffer in bytes
TCP/IP Stack Project -> Logging Infra -> logging hierarchy

void tcp_dump( )

int tcp_dump_ethernet_hdr( ) int tcp_dump_ip_hdr( )

int tcp_dump_ip_hdr( ) int tcp_dump_arp_hdr( ) int tcp_dump_appln_hdr_protocol_icmp( )

void tcp_write_data( )

static void
tcp_write_data (int sock_fd, << 0 to emit on console, -1 otherwise
Fn to write the formatted pkt content
FILE *log_file1, << Node’s log file to write formatted pkt content
to output source(s)
FILE *log_file2, << NULL
: Console
char *out_buff, << Buffer which contains formatted output
: log file(s)
uint32_t buff_size) << Size of contents in the buffer in bytes
TCP/IP Stack Project -> Logging Infra -> CLIs for logging

Added As Assignment
Notify the Subscribers about the events !
Notification Chains

➢ Notification Chains is an architectural concept used to notify multiple subscribers interested in the particular event

➢ A party which generates an Event is called Publisher, and parties which are interested in being notified of the event
are called subscribers

➢ There is one publisher and multiple subscriber

➢ Once the Event is generated/produced by the Publisher, the Event is pushed to Subscriber(s)

➢ Subscriber can register and de-register for the event at their will

➢ Publisher/Subscribers could be any entities :

➢ Multiple threads of the same process
➢ Multiple processes running on same system
➢ Multiple processes running on different systems
➢ Different components of the same big software system
Notification Chains

➢ We implemented an Application – Spf Algorithm

➢ An Application ( = spf algo as an example ) must react to certain common configuration changes or events
happening on a networking device

➢ Example : Interface level config change by admin

➢ IP address change
➢ MTU change
➢ Enable/disable IP address
➢ VLAN config change
➢ etc

➢ We need a mechanism that whenever an admin change such common interface level config, then all interested
application must be notified of this change so that they can take appropriate action

➢ Let me illustrate more …

Notification Chains

➢ Consider a topology build_square_topo( )

Lo : [Link] Lo : [Link] Lo : [Link]

R1 R2 R3
➢ R1’s route to R2
eth0 eth1 eth2 eth3
[Link]/24 [Link]/24 [Link]/24 [Link]/24
[Link]/32 [Link] eth0 1
eth7 eth3
[Link]/24 [Link]/24

➢ Let us assume, that admin has disabled the interface

R1-eth0

➢ Application Running on R1 must be informed of this

eth6 eth5
event and take corrective measures [Link]/24 [Link]/24

➢ SPF Algo on R1 must re-trigger and compute the route to R4

R2 should be : Lo: [Link]

[Link]/32 [Link] eth7 3

Conclusion : Individual Applications must be notified of generic config change done by admin, We would achieve this
through notification chains, a mechanism to distribute events
TCP/IP Stack Project -> Notification Chains

Plan :

➢ We will implement NCM as a mini-lib

➢ Whenever user do change in config of an interface,

NCM will distribute this change to all applications SPF Algo A1 A2 A3

Transport Layer
➢ Design : nwcli.c
Network Layer
➢ NCM is nothing but a linked list of
callbacks registered by applications I1
I2
Notification Data link layer
Chains
➢ On Interface config change, we will iterate over this Module
linked list and invoke all callbacks Physical Layer

➢ At the time of initialization of TCP/IP stack, applications

need to register its callback with NCM
Fa1() Fa2() Fa3()
TCP/IP Stack Project -> Notification Chains -> Another Working Example

Subscribers
App1 App2 App3 App4
Publisher
Fa1() Fa2() Fa3() Fa4()
[Link]/32 [Link] eth0 1
[Link]/32 [Link] eth1 1
[Link]/32 [Link] eth1 1
[Link]/32 [Link] eth1 1

[Link]/32 [Link]/32 [Link]/32 <no key>

Fa1() Fa2() Fa3() Fa4()

➢ Let us say, Publisher is the owner of Routing Table (data source)

➢ Subscribers have registered their callbacks with the publishers against the entries which they are
interested in

➢ Whenever publisher update the entry in its routing table, it iterates over NFC and invoke callbacks of
Subscribers matching the entry

➢ Subscribers who have registered without key will be notified for all updates
TCP/IP Stack Project -> Notification Chains -> Writing NFC files

We will implement a generic NFC infrastructure in files :

tcpip_stack/notif.c
tcpip_stack/notif.h

➢ NFC is a linked list of callbacks ( function pointers )

notif_chain_elem_t
typedef struct notif_chain_ {

char nfc_name[64]; key key key

glthread_t notif_chain_head; << head of linked list Fa1() Fa2() Fa3()
} notif_chain_t;

typedef struct notif_chain_elem_{

char key[MAX_NOTIF_KEY_SIZE];
size_t key_size; typedef void (*nfc_app_cb)(void *, size_t);
bool_t is_key_set;
nfc_app_cb app_cb;
glthread_t glue;
} notif_chain_elem_t;
TCP/IP Stack Project -> Notification Chains -> Writing NFC files

We will implement a generic NFC infrastructure in files :

tcpip_stack/notif.c
tcpip_stack/notif.h Subscription Request
void
➢ NFC is a linked list of callbacks ( function pointers) nfc_register_notif_chain (notif_chain_t *nfc,
notif_chain_elem_t *nfce);

typedef struct notif_chain_ {

Invoke Request
char nfc_name[64];
void
glthread_t notif_chain_head; << head of linked list
nfc_invoke_notif_chain (notif_chain_t *nfc,
} notif_chain_t;
void *arg, size_t arg_size,
typedef struct notif_chain_elem_{ char *key, size_t key_size);

char key[MAX_NOTIF_KEY_SIZE];
size_t key_size; typedef void (*nfc_app_cb)(void *, size_t);
bool_t is_key_set;
nfc_app_cb app_cb;
glthread_t glue;
} notif_chain_elem_t;
TCP/IP Stack Project -> Notification Chains -> Interface Events Relay

➢ Now that we have implemented a generic NFC infra, Now we will implement how any change in interface config done by
by the admin can be notified to applications (spf algo) using NFC

➢ Once you understand this pattern of communication, We shall implement several other notification chains in our project to
implement different features
Eg : how application can tell TCP/IP Stack dynamically that in which protocol packets it is interested in

➢ We will write two new files which would represent notification Chains specific to our TCP/IP Stack. These two files would be
wrapper over generic notif.c/notif.h

tcpip_notify.h/.c
To illustrate, let me first implement NFC concept for
notify.h/.c
Interface config change notifications

Once we implement a complete mechanism, then you would

Clearly understand and look at the bigger picture regarding
how NFC works
TCP/IP Stack Project -> Notification Chains -> Interface Events Relay

Step 1 : Define registration by the Subscriber

Step 2 : Generating notification

Step 3 : Processing notification (by the Subscriber)

TCP/IP Stack Project -> Notification Chains -> Interface Events Relay

Step 1 : Define registration by the Subscriber

➢ To be invoked by subscriber during init

➢ For interface notification, subscriber don’t

have to specify key (the specific intf)

void ➢ It means, whenever there will be interface config

nfc_intf_register_for_events(nfc_app_cb app_cb); change, subscriber will be notified irrespective
of which interface it is

➢ It is subscriber responsibility to discard the notif

if interface is of no interest

➢ Eg : For SPF algo, change in interface vlan membership

is of no interest to SPF algo since spf algo appln do not
work on L2 Interfaces (vlan enabled interfaces)
TCP/IP Stack Project -> Notification Chains -> Interface Events Relay

Step 2 : Generating notification

void
nfc_intf_invoke_notification_to_sbscribers( ➢ To be invoked by NFC to notify subscriber
about change in interface config
interface_t *intf, ➢ Based on change_flags value, subscriber can find
intf_nw_props_t *old_intf_nw_props, out what is changed
uint32_t change_flags); ➢ This routine packs all data into a structure
intf_notif_data_t to be passed as argument to su
Callback fn

➢ Notif need to be generated whenever there is config change on an interface by the user

➢ Publisher must pack all interested data into a single container ( intf_notif_data_t ) to be notified to subscriber
TCP/IP Stack Project -> Notification Chains -> Interface Events Relay

Step 3 : Processing notification (by the Subscriber)

• Subscriber’s Callback fn will be invoked with notif data as an argument

• Appln must de-wrap the structure intf_notif_data_t and find the data of interest in its callback fn

• Appln can now process the notified data

Let’s add a dynamic flavor to our Project
TCP/IP Stack Project -> Using Timers

Relevance

Video Already Uploaded

TCP/IP Stack Project -> Using Timers

Plan

➢ We shall integrate an external timer library to our project

➢ This timer library is based on POSIX threads, so specific to Unix family Operating systems only

➢ We shall first go through the steps for library integration, and then we walk over the timer APIs and how to use them

➢ Timer would give our TCP/IP Stack a dynamic flavor

➢ Timers are used to implement various Networking based problem statements and their solutions

➢ We shall then add a minor Timer based functionality to our project

TCP/IP Stack Project -> Using Timers -> Lib Integration

Timer Library Integration Steps

➢ Download these two files :

➢ [Link]
➢ [Link]

➢ Place in directory :
➢ tcpip_stack/WheelTimer

➢ Update Makefile

➢ Add to OBJS list : WheelTimer/WheelTimer.o

➢ Add compilation Rule :

WheelTimer/WheelTimer.o:WheelTimer/WheelTimer.c
${CC} ${CFLAGS} -c -I gluethread -I WheelTimer WheelTimer/WheelTimer.c -o WheelTimer/WheelTimer.o

> Add clean and cleanall rule

rm -f WheelTimer/WheelTimer.o
TCP/IP Stack Project -> Dynamic ARP Tables

Dynamic ARP Tables

➢ Properties :

➢ Currently ARP table entry is static – meaning once installed it shall be there for forever in ARP Table

➢ ARP Table entry my go obsolete as topology changes, and therefore, ARP table entries which are useless should
be deleted from ARP table automatically

➢ Install ARP Table entry with the Expiration time of 30 sec

➢ If ARP Table entry is not used for traffic forwarding for 30 sec, delete it

➢ If ARP table entry is used for traffic forwarding, refresh its expiration timer back to 30 sec again

➢ Enhance show node <node-name> arp to show expiration time arp entry as an additional field
TCP/IP Stack Project -> Using Timers -> Get Familiar

Get Familiar with Timer Library

➢ Go through Section Appendix B

➢ Go to next video only after you have completed Appendix B

➢ Next we shall proceed to implement dynamic ARP tables

TCP/IP Stack Project -> Dynamic ARP Tables

Dynamic ARP Tables

➢ Solution Steps :

➢ Each Node in the topology, must have its own Wheel-Timer instance running

➢ A Node will schedule all its events using its own Wheel-Timer instance

➢ Now that each ARP table entry is associated with the timer, we need to add below member :

struct arp_entry_{
...
...
wheel_timer_elem_t *exp_timer_wt_elem; /* This represents that this ARP entry is being tracked by Timer now */
};
TCP/IP Stack Project -> Dynamic ARP Tables

Dynamic ARP Tables

New APIs to be written in layer2.h/layer2.c to handle ARP entry’s timer

wheel_timer_elem_t *
arp_entry_create_expiration_timer( • Should be called when ARP entry is installed in routing table for the first time
node_t *node,
1 arp_entry_t *arp_entry,
uint16_t exp_time);

void
arp_entry_delete_expiration_timer( • Should be called when ARP entry is deleted from ARP Table
2 arp_entry_t *arp_entry);

void
arp_entry_refresh_expiration_timer( • Should be called whenever ARP entry is referenced for traffic forwarding Or
3 arp_entry_t *arp_entry); • Whenever the ARP entry status changed from Sane to Resolved

uint16_t
• Should be used while displaying the arp entry and showing how
arp_entry_get_exp_time_left(arp_entry_t *arp_entry);
4 many seconds remaining for it to expire
 Developing
TCP/IP Stack
• How to Implement a new Network Application
Part C
in Application Layer
• Dynamic Protocol Registration

• Sample Network Applications We shall Develop :

• NMP Protocol ( Nbrship Mgmt Protocol ) Pre-Requisite :
• Extensive use of Timers Must have completed Part A and B
• Election Algorithm

• DDCP (Distributed Data Collection Protocol)

• Concept of TLVs
• Packet flooding
• Gathering Replies from different nodes
Notification Chains
TCP/IP Stack Project -> Dynamic Protocol Registration

➢ We shall be going to implement a mechanism using which an application can express interest in the packets it is interested
in receiving from underlying TCP/IP stack

➢ The Application must be able to :

➢ Tell our TCP/IP Stack that in which packets (ip_hdr->protocol for L3 pkts & ethernet_hdr->type for
L2 pkts) the application is interested in

➢ Our TCP/IP Stack should handover the pkt to the application based on protocol ( &type) fields
in IP Hdr ( & ethernet hdr)

➢ I will show the implementation for ip_hdr->protocol field, you need to complete it for ethernet_hdr->type field as a
part of assignment

➢ You should be able to realize that it implementation should make use of Notification Chains as it is another typical
case of publisher (Layer3/Layer2) and Subscribers (Applications)

➢ Let us understand the problem statement pictorially

TCP/IP Stack Project -> Dynamic Protocol Registration

➢ Let us say, we have some dummy appln - ddcp (Distributed Data Collection) running in application layer

➢ This application works with two types of packets :

➢ DDCP_MSG_TYPE_FLOOD_QUERY
➢ This is L2 packet, meaning the pkt is encapsulated within ethernet hdr

Dst MAC Src MAC Type Payload FCS

➢ Dst Mac : ff:ff:ff:ff:ff:ff

➢ Src Mac : 00:00:00:00:00:00
➢ Type = DDCP_MSG_TYPE_FLOOD_QUERY
➢ Payload : DDCP Application Data
➢ FCS = 0

➢ DDCP_MSG_TYPE_UCAST_REPLY
➢ This is L3 pkt , meaning the pkt is encapsulated within IP hdr
TCP/IP Stack Project -> Dynamic Protocol Registration

➢ Let us say, we have some dummy appln - ddcp (Distributed Data Collection) running in application layer

➢ This application works with two types of packets :

➢ DDCP_MSG_TYPE_FLOOD_QUERY
➢ This is L2 packet, meaning the pkt is encapsulated within ethernet hdr

➢ DDCP_MSG_TYPE_UCAST_REPLY
➢ This is L3 pkt , meaning the pkt is encapsulated within IP hdr

➢ Protocol : DDCP_MSG_TYPE_UCAST_REPLY
➢ Src Addr : Lo address of sender
➢ Recv Addr : lo addr of Receiver
Learn Integrate Timer Library in 30 Minutes
Using Timers

➢ Goal of this Course :

➢ To quickly take a look how we can integrate a ready-made timer library with our
application and start using timers straightaway on linux systems

> No discussion on internal Implementation

Using Timers

Src Code

git clone [Link]

Dir : WheelTimer/WheelTimer/
Files : WheelTimer.c, WheelTimer.h
gluethread/glthread.h, gluethread/glthread.c
Demo : main.c
Compile : gcc -g main.c gluethread/glthread.c WheelTimer.c -o exe -lpthread

Timer Basics and Terminologies

• Suppose at t = 0 , you start a timer of 10 sec to send out a packet to remote machine

• At t = 0 , timer is started

• At t = 10, timer is fired Or timer is expired

• Timer was running from t = 0 to t = 10

Using Timers

Working with Timers

Application TimerLibrary (separate thread)

wt = init_wheel_timer( )
start_wheel_timer(wt);
0 1
9 2
wt_elem = register_app_event(wt, . . .)
A handle which 3
application has 8
to cache to
perform future de_register_app_event (wt, 4
7
operations on wt_elem); 6 5
this event wt_elem = NULL;
Using Timers

Application Callback

➢ The Timer library does the application’s work by invoking the Application fn

➢ This Application fn is called ‘timer callback’

Prototype : void (*fn)(void *, int);

Eg : void print_string(void *arg, int arg_size) {

char *data = (char *)arg;

int string_len = arg_size;
printf(“String = %s\n”, data);
}

➢ Application should write the fn of this prototype to be register with the timer

➢ Now let us see timer in Action..

Using Timers

Using Timer Library 4 /* De-register the already scheduled event */

void
/* Creating a new timer */ 1 de_register_app_event (wheel_timer_t *wt,
wheel_timer_elem_t *wt_elem);
wheel_timer_t*
init_wheel_timer(int wheel_size, int clock_tic_interval);
/* Reschedule event again */
/* Starting the new timer */
2 void
void 5
wt_elem_reschedule (wheel_timer_t *wt,
start_wheel_timer(wheel_timer_t *wt);
wheel_timer_elem_t *wt_elem,
int new_time_interval);
/*Scheduling event with the timer */
/* Get Remaining time left for the event to fire */
3
wheel_timer_elem_t * 6 int
register_app_event(wheel_timer_t *wt,
wt_get_remaining_time(wheel_timer_t *wt,
app_call_back call_back,
wheel_timer_elem_t *wt_elem);
void *arg,
int arg_size,
/* Stop the timer */
int time_interval,
char is_recursive);
7 void
cancel_wheel_timer (wheel_timer_t *wt);
Using Timers

Conclusion

➢ We Quickly (~30 min) toured the API to make use of timers

➢ Quickly Integrate the timer library with your projects and start using !

➢ Assignment

➢ Src Code :
[Link]
Using Timers

Solution Steps

1. Create a Wheel Timer instance for a Routing Table

2. Add a wheel_timer_elem_t member to the rt entry. This member keeps track of the exp timer of the entry

3. Add the time of installing the rt entry into routing Table, schedule the expiration of the rt entry with the Wheel timer

4. Write a new timer callback function. This fn shall be invoked by WheelTimer on timer expiry. This fn should delete the
rt entry after un-scheduling the rt entry with the WheelTimer
 Developing
Application
TCP/IP Stack
Transport Layer
Part B
Network Layer
1. Interface Management & statistics
Data link layer
2. Dynamic L3 Route Calculation
No More Manual installation of L3 routes

3. Making TCP/IP stack dynamic

Dynamic ARP table Thank You !
4. Sample L2 Layer Application & Working with Timers

5. Programmable TCP/IP Stack

6. Develop Logging Infra

Packet Captures
Notify the Subscribers about the events !
Notification Chains

➢ Notification Chains is an architectural concept used to notify multiple subscribers interested in the particular event

➢ A party which generates an Event is called Publisher, and parties which are interested in being notified of the event
are called subscribers

➢ There is one publisher and multiple subscriber

➢ Once the Event is generated/produced by the Publisher, the Event is pushed to Subscriber(s)

➢ Subscriber can register and de-register for the event at their will

➢ Publisher/Subscribers could be any entities :

➢ Multiple threads of the same process
➢ Multiple processes running on same system
➢ Multiple processes running on different systems
➢ Different components of the same big software system
Notification Chains -> Pictorial Representation

S1
Comm Subs Subs Subs
Info,
E1,E2
S1 S2 S3

Notification Channel :
• Network Sockets (Different Machines)
Publisher
Event E1
• IPCs (Same Machine, Different Processes)
• Callbacks (Same process)

S1 S2 S3
Comm Comm Comm
Info, Info, Info
E1,E2 E1 E2

Let us discuss one realistic Example !

Notification Chains -> Pictorial Representation
S1
SUBS Thread Thread Process
Comm Info =
f1_ptr T1 T2 P3
E1 = [Link]/32

Routing Table
Mgr
(Publisher,
Thread T0)

Dest Mask OIF Gw S1 S2 S3

SUBS SUBS SUBS
[Link] 32 Eth0 [Link] Comm Info = Comm Info = Comm Info =
f1_ptr f2_ptr “[Link], 2000”
[Link] 32 Eth1 [Link] E1 = [Link]/32
E1 = [Link]/32 E1 = [Link]/32
[Link] 32 Eth2 [Link]

How Subscribers Subscribe and unsubscribe with publisher ?

Notification Chains -> Project Pre-requisites

➢ We will be going to implement a Library which implements Notification Chains functionality

➢ Pre-requisites
➢ IPC
➢ Socket Programming
➢ Function Pointers
➢ Good Command on C/C++
➢ MsgQs, Unix Domain Sockets ( optional )

➢ Expected LOCs
➢ 1500 – 2000 ( if you implement Fully )
➢ Level of Difficulty : Medium

➢ It’s a concept – So you are free to implement in your fav Programming language, But I will use C for Demo on Linux
➢ NF is used all over the industry (Publisher Subs Model is very common Design pattern of communication)

➢ Create your github account if not already, Do all your coding on github

➢ Along the way you will learn more new programming concepts
➢ TLVs, Timers, KeepAlive msgs
Notification Chains -> Project Components

APIs to be provided by the NF Lib: APIs Thread

Publisher Use : ST1
NF Library
Create NF chains
Send Notification to Subs

Subscriber Use:
Register/Unregister for Events APIs

Communication
Common: Routing Table Channel Thread
Data Serialization/Deserialization Mgr ST2
(Publisher,
Thread T0)

One Single Process

Process
The End product of this Course is a NF Chain Library !
SP3
Notification Chains -> Project Code Access

➢ All Codes Accessible at

➢ [Link]

➢ /CompleteProject (Complete solved Project, use it for reference)

➢ /PubSubModelDemo (Simplified, we develop in this course )

Let’s Start … ! ☺
Notification Chains -> Development Phases

Phase 1 : Writing a Sample Publisher Code which is in-charge of sample data source

Phase 2 : Notification Chain Data Structures

Phase 3 : Writing Sample Subscriber with Communication Channel as Network Sockets

Phase 4 : (De)-Registration Procedure

Phase 5 : Sending Event notification from Publisher to Subscriber

Phase 6 : Detecting Subscriber Liveness

Phase 7 : Serialized Communication using TLVs

Phase 8 : What if Publisher Dies ?

Notification Chains -> Phase 1 -> Publisher

➢ A Publisher is an entity which is in-charge/owner of the data source

➢ In our Project, We will create a Publisher – Routing Table Manager who is in-charge of Routing table, a
Data source

Routing Table
Mgr
(Publisher) Dest Mask OIF Gw

[Link] 32 Eth0 [Link]

[Link] 32 Eth1 [Link]

[Link] 32 Eth2 [Link]

➢ A publisher can modify the data source at its will

➢ Publisher must notify the update of its data source to all subscribers who have subscribed for the update

➢ Publisher can be in-charge of multiple data sources

Notification Chains -> Phase 1 -> Publisher

Data Source : rt.h , rt.c

Dest Mask OIF Gw

[Link] 32 Eth0 [Link]

typedef struct rt_entry_keys_{
[Link] 32 Eth1 [Link]
char dest[16]; [Link] 32 Eth2 [Link]
char mask;
} rt_entry_keys_t;

typedef struct rt_entry_{

APIs : CRUD
rt_entry_keys_t rt_entry_keys;

char gw_ip[16];
char oif[32];
struct rt_entry_ *prev;
struct rt_entry_ *next;
} rt_entry_t;

typedef struct rt_table_{

rt_entry_t *head;
} rt_table_t;
Notification Chains -> Realistic Example

Application

Transport Layer

Network Layer
I2
I1
Data link layer

Physical Layer
Notification Chains -> Realistic Example

When Admin Shut down an interface I1:

A2 • A1, A2 may want to stop sending hello pkts

A1 A3
• A3 may want to trigger some algorithm
Transport Layer Publisher : Intf mgmt Module (Kernel space)
Subscribers : Application (User Space)
Network Layer Communication Channel :
USA < - - > KS IPC techniques
I1 I2
Data link layer
Intf Mgmt
Module Physical Layer
TCP/IP Stack Project -> Notification Chains

➢ In the prev section, we noticed that every time the user changes the physical structure of the topology, user need to
manually trigger spf algo using “run spf all” to update the Routing tables

➢ Our Goal is :
➢ Whenever user does anything which changes the physical topology and require update of routes, then SPF algorithm
must trigger automatically
➢ Events :
➢ Intf up/down SPF ALGO
compute_spf_all_routers( )
➢ Intf IP Address Change
➢ Link metric change Transport Layer
➢ Etc ..

➢ We will implement NC in our TCP/IP stack lib Network Layer

I2
I1
➢ Publisher : Interface Backend handlers Notification Data link layer
Chains
➢ Subscriber : Applns(spf.c) Module
➢ Communication Channel : Physical Layer
➢ Appln callbacks
TCP/IP Stack Project -> Notification Chains

➢ Todo :

➢ How SPF algorithm (any application) Express its interest with NCM in specifically interface up/down events ?
➢ SPF algo may have no interest if user changes the MTU or bandwidth of the interface

➢ How Application can unregister or register for more new events dynamically with NCM ?

➢ How NCM notifies the exact event to Spf Algo appln ?

➢ Is it IP address changes Or link metric Change Or interface enable/disable ?

SPF ALGO
compute_spf_all_routers( )
Plan :
Transport Layer
1. First we will implement NCM as a mini-lib
Network Layer
2. Test it with dummy publisher/subscriber I2
I1
Notification Data link layer
3. Will integrate this library with TCP/IP stack lib Chains
Module
Physical Layer
TCP/IP Stack Project -> Notification Chains
Notification Chains -> Design and Implementation

➢ We Create one instance of notification Chain per Event type

➢ For example :
➢ Publisher generates Events E1, E2 and E3
➢ There could be different set of subscribers interested in each events
➢ All Subscribers interested in particular event are grouped together under one notification chain
➢ Though subscribers subscribed for same Event E, may choose different communication channels to be notified
Thank you