hvn-network

My Blog List

Monday, October 31, 2016

Program to interface not implementation

In Object-Oriented Programming (OOP), the desired software is not only runnable but also extensible, maintainable and testable. In this post, I will present a principle in OOP: "Program to interface not implementation". Before digging deeper in this principle, i will present basic concepts about concrete class, abstract class and interface.

1. Basic concepts

1.1. Concrete class

Concrete class is a class that can be used to specify any specific entity. For example, class Car:
class Car{
 string color;
 string model;
public:
 string getColor(){
  return this->color;
 }
 void setColor(string color){
  this->color = color; 
 } 
 string getModel(){
  return this->model;
 }
 void setModel(string model){
  this->model = model;
 }
}

The class Car has two attributes color and model, so any object instantiated by class Car will be determistic with these attributes.

1.2. Abstract class

Suppose that we add a new method called getTax() to class Car. But this class does not know how to implement this because tax may be depended on car type (assuming car has two types: RegularCar and SupperCar). So we mark virtual keyword for the getTax() function. The class Car now is considered to be abstract.

class Car{
 string color;
 string model;
public:
 string getColor(){
  return this->color;
 }
 void setColor(string color){
  this->color = color; 
 } 
 string getModel(){
  return this->model;
 }
 void setModel(string model){
  this->model = model;
 }
 virtual float getTax();
}
We cannot use abstract class directly and the classes inheriting from this class have to provide implementation of the virtual methods.
class SportCar : public Car{
public:
 float getTax(){
   return 2000f;
 }
}

1.3. Interface

In C++ we may consider an interface as a pure abstract class (with no implementation code). For example: 
class Shape{
public:
 virtual float getArea();
 virtual float getPerimeter();
}

class Square : public Shape{
 int sideLength;
public:
 float getArea(){
  return sideLength*sideLength;
 }
 float getPerimeter(){
  return 4*sideLength;
 }
}

1.4. Why do we need Interfaces and Abstract Classes

We use interfaces and abstract class when:
 - We need multiple class to behave in a polymorphic way
 - We need some kind off contract to enforce on the classes.

2. Program to an interface, not an implementation 

This principle means uses interfaces from other part of the application rather than the concrete implementation. When we work on a software, we often spend much time maintaining than developing. If we programming to an implementation, when the requirement change, we need much more efforts in modifying code. For example:
class Dog{
public:
 void run(){
  cout <<"A dog is running";
 }
}

Class Collection{
public: 
 void performAnimalAction(){
  Dog *dog = new Dog;
  dog -> run();
 }
}
This example, use concrete implementation (Dog), it work fine if we has only Dog in Collection. Imagine that we add a new class called Cat to the class Collection later, the performAnimalAction() function will be messed up.

To handle this problem,  we create a interface Animal, and use interface instead of concrete implementation in performAnimalAction() function.

class Animal{
public:
 virtual void run();
}

class Dog : public Animal{
public:
 void run(){
  cout <<"A dog is running";
 }
}

class Cat : public Animal{
public:
 void run(){
  cout <<"A cat is running";
 }
}
class Collection{
public: 
 void performAnimalAction(Animal *_animal){
  Animal *animal = _animal;
  animal->run();
 }
}

int main(){
 Collection *collection = new Collection;
 collection->performAnimalAction(new Dog);
 collection->performAnimalAction(new Cat);
}

Reference

Wednesday, October 26, 2016

Packet flow in routing/switching





Situation 1: CPE1 talks with CPE2

- Assume at CPE1: ping 192.168.0.4

CPE1 checks its routing table to see where to send packet to. It detects that CPE2 is on same network.

Header of sending packet from CPE1.
SIP = 192.168.0.3, DIP = 192.168.0.4
SA = m1, DA=? (unknown yet)

CPE1 broadcasts ARP to know MAC address of 192.168.0.4. After this step it knows DA as m2. Consequently, Switch1 updates its learning table
MAC (m1) ------ Port (fe1)
MAC (m2) ------ Port (fe2)

At this time, CPE1 just sends packet to CPE2 with below header.
SIP = 192.168.0.3, DIP = 192.168.0.4
SA = m1, DA=m2

Situation 2: CPE1 talks with CPE3
- Assume at CPE1: ping 192.168.11.5

CPE1 checks its routing table to see where to send packet to. It detects that CPE3 is not on same network. It has to send packet to its gateway (192.168.0.1) at interface R1(Lan1)

Header of sending packet from CPE1.
SIP = 192.168.0.3, DIP = 192.168.11.5
SA = m1, DA=? (unknown yet)

CPE1 broadcasts ARP to know MAC address of 192.168.0.1. After this, CPE1 know MAC of gateway as a1. Simultaneously, Switch1 updates its learning table.
MAC (m1) ------ Port (fe1)
MAC (m2) ------ Port (fe2)
MAC (a1) ------ Port (fe0)

CPE1 then sends packet to gateway with below header
SIP = 192.168.0.3, DIP = 192.168.11.5
SA = m1, DA=a1


Next, Router1 receives the packet, it check DIP (192.168.11.5) in its routing table to see where to forward packet. Ok, it detects that the packet should be forwarded to interface R2(Lan2, 192.168.11.1).

Router1 creates below packet.
SIP = 192.168.0.3, DIP = 192.168.11.5
SA = a2, DA=?

Now, it broadcasts ARP to know MAC address of 192.168.11.5. After this, Router1 knows MAC of 192.168.11.5 as m3. Switch2 updates learning table as
MAC (m3) ------ Port (fe1)
MAC (a2) ------ Port (fe0)

Finally, Router1 sends packet to CPE3 as below header.
SIP = 192.168.0.3, DIP = 192.168.11.5
SA = a2, DA= m3

Take note
- Switch just works at L2 (MAC address)
- Router is to transmit packets between different networks based on routing table (L3, IP address).

Routing in router:
+ Static routing (route add ...)
+ Dynamic routing (using protocol such as RIP, which broadcasts periodically its routing table to neighborhood and update the best routes).

Q&A
1. Why Home Gateway doesn't need to use RIP protocol?

Thursday, October 6, 2016

Sunday, October 2, 2016

I/O Multiplexing

Mô hình I/O multiplexing được tóm tắt như sau:



















Các hàm quan trọng:
int select(int maxfdp1, fd_set *readset, fd_set *writeset, fd_set *exceptset, const struct *timeout);

void FD_CLR(int fd, fd_set *fdset); //xóa bit tương ứng trong fdset

//sử dụng hàm này sau select để kiểm tra bit tương ứng trong fdset là được set hoặc không
int FD_ISSET(int fd, fd_set *fdset); 

void FD_SET(int fd, fd_set *fdset); //set bit trong *fdset ứng với fd

void FD_ZERO(fd_set *fdset); // xóa tất cả bit trong fdset
Nếu timeout là NULL, select bị block đến khi tồn tại fd có dữ liệu. Nếu timeout là 0, select trả lại lập tức sau khi kiểm tra các fd. Nếu timeout khác NULL và 0, select() returns khi một hoặc nhiều file discriptors trong các tập readset, wirteset, exceptset có dữ liệu cho I/O hoặc hết timeout.

Nếu trả lại thành công, select trả lại số fds có dữ liệu sẵn sàng.

Nếu không thành công, select trả lại -1 và errno. Một số errno như sau:
- EBADF: có một fd không hợp lệ
- EINTR: select bị ngắt bởi tín hiệu trước khi timeout
- EINVAL: khoảng timeout không hợp lệ

Implementation của fdset dựa trên 1 bit mask kiểu số nguyên, hoặc bit fields trong mảng số nguyên.


Ví dụ sau về 1 hàm bị block cho tới khi 1 trong 2 fd sẵn sàng có dữ liệu.


#include errno.h
#include sys/select.h

int whicisready(int fd1, int fd2) {
 int maxfd;
 int nfds;
 fd_set readset;
 
 if (fd1 < 0 || fd1 >= FD_SETSIZE || fd2 < 0 || fd2 >= FD_SETSIZE)
 {
  errno = EINVAL;
  return -1;
 }
 
 maxfd = (fd1 > fd2) ? fd1: fd2;
 FD_ZERO(&readset);
 FD_SET(fd1,&readset);
 FD_SET(fd2,&readset);
 ndfs = select(maxfd+1, &readset, NULL, NULL, NULL);
 if (ndfs == -1)
  return -1;
 if (FD_ISSET(fd1, &readset))
  return fd1;
 if (FD_ISSET(fd2, &readset))
  return fd2;
 
 errno = EINVAL;
 return -1;
}




Friday, September 23, 2016

[C Programming] Exercises on Types, Operators and Expressions

We cover solution of exercises on types, operators and expressions in book "The C programming language".

Exercise 2-1. Write a program to determine the ranges of char, short, int, and long variables, both signed and unsigned, by printing appropriate values from standard headers and by direct computation. Harder if you compute them: determine the ranges of the various floating-point types.
Solution

Exercise 2-2. Write a loop equivalent to the for loop above without using && or ||.
Solution

Convert s to integer

Convert c to lower case

Pseudo-random generator

Exercise 2-3. Write a function htoi(s), which converts a string of hexadecimal digits (including an optional 0x or 0X) into its equivalent integer value. The allowable digits are 0 through 9, a through f, and A through F.
Solution

Squeeze

Strcat

Exercise 2-4. Write an alternative version of squeeze(s1,s2) that deletes each character in s1 that matches any character in the string s2.
Solution

Exercise 2-5. Write the function any(s1,s2), which returns the first location in a string s1 where any character from the string s2 occurs, or -1 if s1 contains no characters from s2. (The standard library function strpbrk does the same job but returns a pointer to the location.)
Solution

Exercise 2-6. Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.
Solution

Exercise 2-7. Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.
Solution

Exercise 2-8. Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n positions.
Solution

Bit count

Exercise 2-9. In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x. Explain why. Use this observation to write a faster version of bitcount.
Solution

Exercise 2-10. Rewrite the function lower, which converts upper case letters to lower case, with a conditional expression instead of if-else.
Solution



[C Programming] Exercises on Control flow

We cover solution of exercises on Control flow in book "The C programming language".

Binary search

Exercise 3-1. Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside.) Write a version with only one test inside the loop and measure the difference in run-time.
Solution

Count digit

Exercise 3-2. Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like \n and \t as it copies the string t to s. Use a switch. Write a function for the other direction as well, converting escape sequences into the real characters.
Solution

Convert string to integer

Shellsort

Reverse string

Exercise 3-3. Write a function expand(s1,s2) that expands shorthand notations like a-z in the string s1 into the equivalent complete list abc...xyz in s2. Allow for letters of either case and digits, and be prepared to handle cases like a-b-c and a-z0-9 and -a-z. Arrange that a leading or trailing - is taken literally.
Solution

Convert n to characters

Exercise 3-4. In a two's complement number representation, our version of itoa does not handle the largest negative number, that is, the value of n equal to -(2wordsize-1). Explain why not. Modify it to print that value correctly, regardless of the machine on which it runs.
Solution

Exercise 3-5. Write the function itob(n,s,b) that converts the integer n into a base b character representation in the string s. In particular, itob(n,s,16) formats s as a hexadecimal integer in s.
Solution

Exercise 3-6. Write a version of itoa that accepts three arguments instead of two. The third argument is a minimum field width; the converted number must be padded with blanks on the left if necessary to make it wide enough.
Solution

Strim

Goto