CRC is back!

Despre calculul CRC am mai scris si aici.

Dar de data asta am calculat mult mai explicit (babeste);

Pe scurt, avem doua programe numite Generator si Verifier (~ Sender si Receiver din foto)

* Generatorul ia ca input, de la tastatura, un sir de biti de m caractere numit "Data" si un sir de biti de (n+1) caractere, numit Divisor. Sirul de biti este simulat in C++ cu un string ale carui valori sunt 1 si 0 (dar nefacandu-se verificarea inputului);

* Lui Data i se ataseaza n biti de 0, si se "imparte" la Divisor (important, divizorul trebuie sa aiba primul si ultimul bit de 1).

* Impartirea nu este una normala ci una numita "Modulo 2 Division" (link) de unde ne intereseaza restul, care devine CRC. Am implementat-o pur si simplu babeste, asa cum se face pe hartie (dar asta nu inseamna ca e si usor de inteles...);

* Datei initiale i se va atasa acest CRC, servit ca output intr-un fisier, alaturi de Divisor, pe randul doi. Asta este ceea ce face Generator;

* Verifier ia din acelasi fisier Data si Divisor si le imparte unul la altul (in acelasi mod);

* Daca restul este 0, datele au fost transmise corect de la "sender" la "receiver", altfel exista erori.

* Pentru simularea erorii, intervine programul Alter, care intrand in fisierul scris de Generator, inverseaza random un bit din Data (oricare dar nu cel mai semnificativ); daca se ruleaza Verifier, rezultatul va fi eroare.

Programele se pot descarca de aici.

E-mail spam

Protocoale pentru posta electronica

Anatomia mesajelor e-mail

Un mesaj e-mail a fost întotdeauna transmis in format plain-text. Chiar si prin adăugarea attachmenturilor, mesajele de e-mail sunt trimise tot ca mesaje plain-text, prin folosirea unor mecanisme de codificare (uuencode/uudecode, MIME/BASE64). Un mesaj este format dintr-o secţiune de headere, urmata de o secţiune cu conţinutul mesajului. Structura headerelor este descrisa in RFC 822, RFC 1521 si RFC 1806, ele având in general următoarea structura:
- Unul sau mai multe headere Received: , care indica ce cale a fost urmata de mesaj de la sursa pana la destinaţie
- Mime-Version: versiunea mime folosita, 1.0 in general
- Content-Type: text/plain pentru mesaje text, multipart/mixed pentru mesaje cu ataşamente
- Subject: - subject-ul mesajului
- Date: - data si ora când a fost trimis mesajul
- Message ID: - un ID pentru mesaj, folosit pentru identificarea in mod unic a unui mesaj
- From: - numele si adresa de mail a expeditorului
- To: - numele si adresa de mail a destinatarului
- Cc: - carbon copy - alţi destinatari

Mesajele cu ataşamente pot folosi una din următoarele tehnici pentru codificarea acestora:

• uuencode - la începuturile e-mail-ului, fişierele care se doreau trimise prin email trebuiau convertite in format text si invers prin folosirea utilitarelor numite uuencode/uudecode. Si in zilele de azi, unii clienţi de mail adaugă ataşamentele la sfârşitul mesajelor, codificându-le cu algoritmul folosit de uuencode.
• MIME / Base64 - aceasta tehnologie este cea recomandata pentru trimiterea de mesaje cu ataşamente.

In terminologia folosita de sistemele de e-mail, exista 3 actori in cadrul sistemului de e-mail. Aceştia pot fi situaţi pe 3 maşini diferite sau pot co-exista pe acelaşi computer:

• Mail User Agent (MUA), sau client de e-mail - aceasta este aplicaţia folosita de utilizator pentru a citi si trimite mesaje email. El nu primeşte direct mesaje, acesta fiind rolul Mailbox Server-ului.
• Mailbox Server, sau server de e-mail - acesta este calculatorul/serverul care primeşte si stochează mesajele.
• Mail Transfer Agent (MTA), sau "router" de e-mail - aceasta este aplicaţia care primeşte si retrimite mesajele spre un alt MTA sau spre un Mailbox Server.

Protocolul SMTP este folosit si de către clienţii de mail când se trimit mesaje e-mail. Astfel, pentru a trimite un mesaj clienţii de mail (MUA) se conectează la serverele SMTP (MTA) si comunica prin protocolul SMTP. In schimb, la transferul mesajelor recepţionate intre Mailbox Server si clientul de mail
se folosesc alte protocoale, cele mai cunoscute fiind POP3 (POP versiunea 3) si IMAP.

Protocolul POP (Post Office Protocol) este destinat folosirii in mod "offline" si este cel mai vechi dintre cele doua protocoale. In paradigma POP, mesajele sunt stocate pe un server, iar un client de mail interoghează periodic serverul, aducând mesajele noi pe calculatorul utilizatorului. După ce un mesaj este descărcat, este şters de pe server. In continuare, toate procesările asupra mesajelor sunt făcute pe calculatorul utilizatorului.

Protocolul IMAP (Internet Message Access Protocol) poate face si procesare offline, dar este in general folosit pentru accesul "online" la mail. In modul online, mesajele sunt stocate tot pe un server, dar clientul nu copiază pur si simplu mesajele pe calculatorul utilizatorului. Se foloseşte un mod de comunicaţie interactiv, in care clientul poate cere doar headere de mesaje, doar anumite mesaje, sau poate căuta mesaje care respecta anumite criterii. Mesajele pot fi marcate ca "deleted" sau "answered" si acest marcaj este făcut pe server. Pe scurt, protocolul IMAP permite manipularea mesajelor de la distanta ca si cum ar fi stocate local.

Urmatorul program implementeaza un client simplu de smtp folosind socketsi tcp. Se apeleaza folosind ca parametru adresa serverului care accepta sa gazduiasca clientul (accepta telnet). In continuare, trimite la adresa de e-mail specificata mesaje de la un "expeditor" oarecare...


#include "sys/socket.h"
#include "netinet/in.h"
#include "arpa/inet.h"
#include "unistd.h"
#include "sys/types.h"
#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "errno.h"

#define SMTP_PORT 25
#define MAXLEN 500

/**
* Citeste maxim maxlen octeti din socket-ul sockfd. Intoarce
* numarul de octeti cititi.
*/
ssize_t Readline (int sockd, void *vptr, size_t maxlen) {
ssize_t n, rc;
char c, *buffer;

buffer = vptr;

for ( n = 1; n<=maxlen-1; n++ ) {
if ( (rc = read(sockd, &c, 1)) == 1 ) {
*buffer++ = c;
if ( c == '\n' )
break;
}
else if ( rc == 0 ) {
if ( n == 1 )
return 0;
else
break;
}
else {
if ( errno == EINTR )
continue;
return -1;
}
}

*buffer = 0;
return n;
}

/**
* Trimite o comanda SMTP si asteapta raspuns de la server.
* Comanda trebuie sa fie in buffer-ul sendbuf.
* Sirul expected contine inceputul raspunsului pe care
* trebuie sa-l trimita serverul in caz de succes (de ex. codul
* 250). Daca raspunsul semnaleaza o eroare se iese din program.
*/
void send_command(int sockfd, char sendbuf[], char *expected) {
char recvbuf[MAXLEN];
int nbytes;
char CRLF[3];

CRLF[0] = 13; CRLF[1] = 10; CRLF[2] = 0;
strcat(sendbuf, CRLF);
printf("Trimit: %s", sendbuf);
write(sockfd, sendbuf, strlen(sendbuf));
nbytes = Readline(sockfd, recvbuf, MAXLEN - 1);
recvbuf[nbytes] = 0;
printf("Am primit: %s", recvbuf);
if (strstr(recvbuf, expected) != recvbuf) {
printf("Am primit mesaj de eroare de la server!\n");
exit(-1);
}
}

int main(int argc, char **argv) {
int sockfd;
int port = SMTP_PORT;
struct sockaddr_in servaddr;
char server_ip[15];
char sendbuf[MAXLEN];
char recvbuf[MAXLEN];

if (argc != 2) {
printf("Utilizare: ./send_msg adresa_server");
exit(-1);
}
strcpy(server_ip, argv[1]);

if ( (sockfd = socket(AF_INET, SOCK_STREAM, 0))<0>
printf("Eroare la creare socket.\n");
exit(-1);
}

/* formarea adresei serverului */
memset(&servaddr, 0, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_port = htons(port);

if (inet_aton(server_ip, &servaddr.sin_addr)<=0) {
printf("Adresa IP invalida.\n");
exit(-1);
}

/* conectare la server */
if (connect(sockfd, (struct sockaddr *) &servaddr, sizeof(servaddr))<0>
printf("Eroare la conectare\n");
exit(-1);
}

Readline(sockfd, recvbuf, MAXLEN -1);
printf("Am primit: %s\n", recvbuf);

sprintf(sendbuf, "HELO `adresa_ip_aici`");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "mail from: Anonymous@yahoo.com");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "rcpt to: yourSecretLover@yahoo.com");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "data");
send_command(sockfd, sendbuf, "354");

sprintf(sendbuf, "secret message from a secret person\n.");
send_command(sockfd, sendbuf, "250");

sprintf(sendbuf, "quit");
send_command(sockfd, sendbuf, "221");

close(sockfd);
}

Protocolul HTTP

HTTP (HyperText Transfer Protocol - protocol pentru transfer de hipertext) este protocolul standard folosit in Web. HTTP este un protocol ASCII simplu. O interactiune HTTP consta dintr-o cerere de tip text, urmata de un raspuns care consta in fisierul transferat (ca mesaj în format standard MIME). Se poate spune ca protocolul HTTP este format din multimea cererilor (uzual GET, POST) de la programele de navigare catre servere si din multimea raspunsurilor trimise de acestea (antetele si corpurile mesajelor sunt asemanatoare cu cele din standardul MIME).
HTTP cunoaste mai multe versiuni succesive si este in continua evolutie; ultimele versiuni de MIME sunt foarte flexibile, avand o deschidere pentru viitoare aplicatii obiectuale.
HTTP este utilizat de catre navigatoare, dar ar putea fi folosit si de catre o persoana aflata la un terminal pentru a "discuta" direct cu un server Web, folosind o conectare TCP (de exemplu, prin programul telnet).

Programul urmator se conecteaza la adresa IP a unui server (de exemplu google) si citeste de la consola un cuvant, pe care il trimite serverului, iar fluxul de informatii care rezulta (din cautare de exemplu) este transferat intr-un fisier numit rezultat.html. Cererea folosita este GET.

#include "sys/socket.h"
#include "netinet/in.h"
#include "arpa/inet.h"
#include "unistd.h"
#include "sys/types.h"
#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "errno.h"

#define HTTP_PORT 80
#define MAXLEN 500000

ssize_t Readline (int sockd, void *vptr, size_t maxlen) {
ssize_t n, rc;
char c, *buffer;
buffer = vptr;

for ( n = 1; n<=maxlen-1; n++ ) {
if ( (rc = read(sockd, &c, 1)) == 1 ) {
*buffer++ = c;
if ( c == '\n' )
break;
}
else if ( rc == 0 ) {
if ( n == 1 )
return 0;
else
break;
}
else {
if ( errno == EINTR )
continue;
return -1;
}
}
*buffer = 0;
return n;
}


void send_command (FILE *g, int sockfd, char sendbuf[]) {
char recvbuf[MAXLEN];
int nbytes;
char CRLF[3];

CRLF[0] = 13; CRLF[1] = 10; CRLF[2] = 0;
strcat(sendbuf, CRLF);
write(sockfd, sendbuf, strlen(sendbuf));
nbytes = Readline (sockfd, recvbuf, MAXLEN - 1);
recvbuf[nbytes] = 0;
fprintf(g,"%s", recvbuf);
}

int main(int argc, char **argv) {
int sockfd;
int port = HTTP_PORT;
struct sockaddr_in servaddr;
char server_ip[15];
char sendbuf[MAXLEN];
char recvbuf[MAXLEN];

if (argc != 2) {
printf("Utilizare: ./send_msg adresa_server");
exit(-1);
}
strcpy(server_ip, argv[1]);

if ( (sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0 ) {
printf("Eroare la creare socket.\n");
exit(-1);
}

memset(&servaddr, 0, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_port = htons(port);

if (inet_aton(server_ip, &servaddr.sin_addr) <= 0 ) {
printf("Adresa IP invalida.\n");
exit(-1);
}

if (connect(sockfd, (struct sockaddr *) &servaddr, sizeof(servaddr)) < 0 ) {
printf("Eroare la conectare\n");
exit(-1);
}

char word[30];
scanf("%s", word);
FILE * g = fopen("rezultat.html","w");

char *c = (char*)malloc(100*sizeof(char));
c = strcat(c,"GET /search?q=");
c = strcat(c, word);
c = strcat(c, " HTTP/1.0\n");

printf("%s\n",c);
sprintf(sendbuf, "%s", c);
while(1)
send_command(g,sockfd, sendbuf);

close(sockfd);
}

Socketi "raw"

Socketii "raw", din familia de protocoale PF_PACKET sunt folositi pentru a receptiona sau trimite pachete "raw" direct la nivelul dispozitivului fizic (nivelul OSI 2). Sunt folositi pentru a implementa protocoale direct in user-space fie pentru a le testa fie pentru ca protocolul nu are rost sa fie implementat in kernel. Aceasta familie de protocoale pune la dispozitie doua tipuri de socketi:

• SOCK_RAW - pachetele sunt prezentate utilizatorului asa cum sunt primite de la device driver (i.e. cu tot cu headerul de nivel 2); de asemenea la trimiterea unui pachet printr-un socket de acest tip pachetele sunt trimise nemodificate astfel incat trebuie sa contina si headerul
• SOCK_DGRAM - pachetele sunt prezentate utilizatorului fara headerul de nivel 2; pachetelor trimise pritr-un socket de acest tip li se va adauga headerul de nivel 2; practic utilizatorul vede doar continul pachetului

Socketii "raw" sunt creati la fel ca si socketii normali cu apelul de sistem socket:

packet_socket = socket(PF_PACKET, int socket_type, int protocol);

unde socket_type poate fi SOCK_RAW sau SOCK_DGRAM iar protocol una din constantele definite in linux/if_ether.

Aplicatia de mai jos "asculta" toate pachetele care ajung in calculator si printeaza continutul lor, fie ca ii sunt adresate calculatorului sau nu.


#include "netinet/in.h"
#include "stdio.h"
#include "unistd.h"
#include "netpacket/packet.h"
#include "sys/types.h"
#include "sys/socket.h"
#include "net/if.h"
#include "stdlib.h"
#include "sys/ioctl.h"
#include "string.h"
#include "net/if_arp.h"
#include "linux/if_ether.h"

int start(int proto) //eth_p_ip
{
int fd = socket(PF_PACKET, SOCK_DGRAM, htons(proto));

if (fd < 0)
{
perror("can't create protocol socket:");
return -1;
}
return fd;
}

int bind_socket(int fd, int interface, int protocol)
{
struct sockaddr_ll sock_info;

memset(&sock_info, 0, sizeof(sock_info));

sock_info.sll_family = AF_PACKET;
sock_info.sll_protocol = htons(protocol);
sock_info.sll_ifindex = interface;

if (bind(fd, (struct sockaddr *)&sock_info, sizeof(sock_info)))
{
perror("can't bind socket to i/f %m\n");
return -1;
}
return 0;
}

int find_interface(char *name)
{
struct ifreq ifr;
int iindex = 1;
int sock = socket(PF_PACKET, SOCK_RAW, 0);

ifr.ifr_ifindex = iindex;

while (ioctl(sock, SIOCGIFNAME, &ifr) == 0)
{
if (strcmp(ifr.ifr_name, name) == 0)
{
close(sock);
return iindex;
}
ifr.ifr_ifindex = ++iindex;
}
close(sock);
return -1;
}

int set_promisc(int fd, int ifn)
{
struct packet_mreq pack_info;

pack_info.mr_type = PACKET_MR_PROMISC;
pack_info.mr_alen = 0;

pack_info.mr_ifindex = ifn;

if (setsockopt(fd, SOL_PACKET, PACKET_ADD_MEMBERSHIP, &pack_info, sizeof(pack_info)))
{
printf("can't set promiscous mode\n");
return -1;
}

return 0;
}

int recv_packet(int sockfd, int *ifn, unsigned char macaddr[], unsigned char *data, int maxlen)
{
struct msghdr msg;
struct iovec iov;
struct sockaddr_ll sock_info;

int len;

memset(&msg, 0, sizeof(msg));
msg.msg_name = &sock_info;
msg.msg_namelen = sizeof(sock_info);
msg.msg_iovlen = 1;
msg.msg_iov = &iov;

iov.iov_len = maxlen;

iov.iov_base = data;

len = recvmsg(sockfd, &msg, 0);

*ifn = sock_info.sll_ifindex;
memcpy(macaddr, sock_info.sll_addr, 6);

return len;
}


int main()
{
int sockfd = start(ETH_P_IP);
int interface = find_interface("eth0");
int b = bind_socket(sockfd, interface, ETH_P_IP);
unsigned char *macaddr=(unsigned char *)malloc(256*sizeof(unsigned char)), *data= (unsigned char *)malloc(256*sizeof(unsigned char));
while (1) {
int promise = set_promisc(sockfd, interface);
int recv = recv_packet(sockfd, &interface, macaddr, data, 256), i;
for(i=0; i < 256;i++)
printf("%c",data[i]);
printf("\n");
}
return 0;

}

Nota
Fisierul va fi executat din pozitie de admin (in Linux: sudo su)

Algoritmi de dirijare

Problema dirijarii apare la nivelul retea, si consta in a determina calea pe care o vor parcurge pachetele de la calculatorul sursa la calculatorul destinatie. Software-ul nivelului retea trebuie sa asigure desfasurarea a doua procese distincte:

• retransmitere (forwarding): ceea ce se intampla cand un pachet ajunge la ruter, si acesta trebuie sa stabileasca, prin consultarea unei tabele de rutare, linia de iesire pe care va transmite pachetul mai departe
• dirijare (routing): este procesul de construire si actualizare a tabelei de rutare - adica de stabilire a cailor pe care vor fi transmise pachetele

Referitor la algoritmii ce tin de procesul de dirijare, putem distinge doua categorii de algoritmi: algoritmi neadaptivi (ce realizeaza o dirijare statica - toate rutele sunt determinate initial si nu se tine cont de modificarile ulterioare de trafic si topologie ce apar in retea) si algorimi adaptivi (rutele sunt modificate ca urmare a schimbarilor de topologie si de trafic din retea).

Dintre algoritmii neadaptivi fac parte:

• dirijarea pe calea cea mai scurta (shortest path routing): subreteaua este reprezentata ca un graf, in care ruterele sunt noduri, si se aplica un algoritm (de exemplu Dijkstra) pentru a determina caile cele mai scurte dintre noduri; se pot folosi diverse metrici, cum ar fi numarul de rute intermediare, distanta geografica, intarzierile medii de transmisie
• inundarea (flooding): ruterul trimite fiecare pachet receptionat pe toate liniile de iesire, in afara de cea pe care a venit pachetul; varianta: inundarea selectiva (selective flooding)

Algoritmii adaptivi cel mai des utilizati sunt:

• dirijarea cu vectori distanta (distance vector routing): fiecare ruter mentine o tabela cu calea cea mai buna pentru fiecare destinatie si linia de iesire corespunzatoare acestei cai; tabelele sunt actualizate pe baza informatiilor primite de la celelalte rutere
• dirijarea folosind starea legaturilor (link state routing): fiecare router determina costurile asociate cailor catre vecini, apoi trimite aceste informatii in toata subreteaua; dupa schimburile de informatii, fiecare ruter are informatii complete despre graf si poate determina caile minime

Exemple de protocoale de dirijare:

• RIP (Routing Internet Protocol) - utilizeaza algoritmul distance vector
• OSPF (Open Shortest Path First Protocol) - utilizeaza algoritmul link state
• BGP (Border Gateway Protocol)

Programul de mai jos citeste dintr-un fisier un numar n reprezentand dimensiunea unei matrici de adiacenta a unui graf cu nodurile retelei, precum si aceasta matrice. Initial creeaza o tabela de rutare pentru fiecare nod, care contine informatii despre toate nodurile retelei, sub forma : Destinatar , Cost (=valoarea asociata muchiei dintre acel nod si destinatar), Next_Hop (=nodul urmator de urmat pentru a ajunge la destinatar). Apoi, pentru fiecare nod se vor actualiza informatiile despre celelalte noduri combinand informatiile gasite in fiecare tabela de rutare cercetata.


#include "stdio.h"
#include "stdlib.h"
#define INF 1000

int **a, n;

typedef struct tabela {

int *dest;
int *cost;
int *next_hop;

} Tabela;

void printTabela(Tabela t) {

int i;
for(i=0; i < n; i++)
printf("%d\t%d\t%d \n", t.dest[i], t.cost[i], t.next_hop[i] );
}

int find_dest(Tabela t, int poz) { // prima dest incepand cu poz

int i=poz;
while(t.cost[i] == INF && i<=n-1)
i++;
if (i<=n-1)
return t.dest[i];
return -1; // nu a gasit
}

int main () {

FILE * f = fopen ("in", "r");
fscanf(f, "%d",&n);
int i,j,k;
a = (int **)malloc(n*sizeof(int));

for(i=0; i < n ; i++)
a[i] = (int *)malloc(n*sizeof(int));
for(i=0; i < n ; i++)
for(j=0; j < n ; j++)
fscanf(f, "%d", &a[i][j]);

Tabela * tab = (struct tabela *)malloc(sizeof(struct tabela)*n);
for(i=0; i < n ; i++) {
tab[i].dest = (int *)malloc(n*sizeof(int));
tab[i].cost = (int *)malloc(n*sizeof(int));
tab[i].next_hop = (int *)malloc(n*sizeof(int));
}

// constructia tabelei in forma initiala
for (i=0; i < n ; i++) { // pt fiecare tabela
for(j=0; j < n ; j++)
if (a[i][j]) {
tab[i].dest[j] = j;
if(i!=j)
tab[i].cost[j] = 1;
else
tab[i].cost[j] = 0;
tab[i].next_hop[j] = j;
}
else {
tab[i].dest[j] = j;
tab[i].cost[j] = INF;
tab[i].next_hop[j] = -1;
}
}

printf("Tabela 5 inainte de aplicarea algoritmului:\n");
printTabela(tab[5]); // printam un anumit nod


for(i=0; i < n ; i++) // pt fiecare tabela

for(j=0; j < n ; j++) { // pt fiecare destinatie din tabela
k = find_dest(tab[j],0);
while(k!=-1) {
if (tab[i].cost[k] > tab[j].cost[k] + tab[i].cost[j]) {
tab[i].cost[k] = tab[j].cost[k] + tab[i].cost[j];
tab[i].next_hop[k] = tab[j].dest[j];
}
k = find_dest(tab[j],k+1);
}
}

printf("Tabela finala 5 cu drumuri optime:\n");
printTabela(tab[5]);

return 0;

}

Purificarea retelelor Petri

In procesul de modelare a protocoalelor folosind RP, pot aparea retele impure. De exemplu, o tranzitie impura t are un loc de intrare l, care este simultan nod de iesire. Pentru o RP pura niciun loc nu este intrare si iesire a aceleiasi tranzitii. Se demonstreaza ca orice RP impura poate fi transformata intr-o RP pura prin reducere. Reducerea ei se face astfel:

- se suprima arcele (l, t) si (t, l)

- se suprima t daca ea devine izolata

Urmatorul program indeplineste urmatoarele functii:

• isi creeaza un exemplu de retea Petri folosind locuri si tranzitii
• verifica daca reteaua contine impuritati;
• aplica reducerea specificata asupra fiecarei tranzitii impure;
• in final printeaza reteaua purificata
  

#################################

#include"stdio.h"

typedef struct {
int pre[100];
int post[100];
int Npre,Npost;
} tran;

int main() {
tran t[6];

t[1].Npre=2;
t[1].Npost=2;
t[1].post[0]=1;
t[1].post[1]=2;
t[1].pre[0]=1;
t[1].pre[1]=2;

t[2].Npre=3;
t[2].Npost=1;
t[2].post[0]=3;
t[2].pre[2]=3;
t[2].pre[0]=1;
t[2].pre[1]=2;


t[3].Npre=1;
t[3].Npost=1;
t[3].post[0]=1;
t[3].pre[0]=3;

t[4].Npre=1;
t[4].Npost=1;
t[4].post[0]=2;
t[4].pre[0]=3;

t[5].Npre=1;
t[5].Npost=1;
t[5].post[0]=3;
t[5].pre[0]=3;

int n=5,ok=1,i,k,l;

do {
ok=1;
for(i=1;i<=n;i++)
for(k=0;k<=t[i].Npre-1 ; k++)
for(l=0; l<=t[i].Npost-1; l++)
if((t[i].pre[k]==t[i].post[l]) && (t[i].pre[k]!=0)) // daca a gasit tranzitie impura
{
ok=0;
t[i].pre[k]=t[i].post[l]=0; // purifica
break;
}
} while(ok==0);

for(i=1;i<=n;i++) {
printf("\nT%d:\nPre:",i);
for(k=0;k<=t[i].Npre-1;k++)
printf("%d ",t[i].pre[k]);
printf("\nPost:");
for(k=0; k<=t[i].Npost-1 ; k++)
printf("%d ",t[i].post[k]);
}

return 0;
}

Protocoale cu fereastra glisanta pentru legatura de date

In cazul acestor protocoale, la orice moment de timp, emitatorul mentine o multime de numere de secventa care corespund cadrelor pe care are permisiunea sa le trimita. Aceste cadre apartin unei ferestre de transmisie. Receptorul va mentine o fereastra de receptie (avand de asemenea o multime de numere de secventa) corespunzatoare cadrelor ce pot fi acceptate. Cele doua ferestre (ale emitatorului si receptorului) nu trebuie sa aiba aceeasi dimensiune.

Protocolul cu fereastra glisanta de un bit utilizeaza metoda stop-and-wait, deoarece emitatorul transmite un cadru si asteapta confirmarea sa inaintea transmiterii urmatorului cadru.

Urmatoarea aplicatie emitator / receptor functioneaza conform cu descrierea protocolului cu fereastra glisanta de un bit. Cele doua aplicatii transmit date intre ele prin intermediul unor pipe-uri, contorizand numarul pachetului trimis/receptionat.
Emitatorul trimite cadre dintr-un pachet pe care le contorizeaza, trimite si contorul acestora. Receptorul stie la ce contor sa se astepte, si daca primeste un cadru nedorit, trimite la randul sau propriul contor neupdatat, astfel emitatorul mai trimite o data cadrul respectiv.
In plus, s-a folosit codificarea si decodificarea crc pentru a verifica si mai bine datele. Emitatorul calculeaza propriul tabel crc si, pentru fiecare cadru trimis, calculeaza acumulatorul, pe care il transmite. Receptorul la randul lui si-a creat tabelul crc, primeste acumulatorul dar si calculeaza un nou acumulator pe baza cadrului primit. In plus fata de conditia de concordanta a numarului cadrelor, diferenta intre acumulatoare trebuie sa fie 0.

sender.c

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "unistd.h"
#include "fcntl.h"
#include "sys/types.h"
#include "sys/stat.h"
#include "crc.h"

char *text = "smoke this in your pipe and stuff it please";


int main () {


int fd1, fd2;
fd1 = open ("pipe1", O_RDONLY );
fd2 = open ("pipe2", O_WRONLY );
int inc = 0, i=0, primit=0, j, acum=0;
word *tabel;
tabel = tabelcrc(CRCCCITT);
int ok=1;

do {
if(ok)
crctabel(text[i], &acum, tabel);
ok = 0;
write (fd2, &text[i], 1);
write (fd2, &inc, 4);
write(fd2, &acum, 2);
printf("%d\n",acum);
read (fd1, &primit, 4);
if(primit==inc)
{ inc++;
i++;
ok = 1;
}
} while(i < strlen(text)+1);

close (fd1);
close(fd2);
return 0;

}


receiver.c

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "unistd.h"
#include "sys/types.h"
#include "sys/stat.h"
#include "fcntl.h"
#include "crc.h"


int main () {

int fd1, fd2;
char buf;
int contor=-1;
int cadru;
fd1 = open ("pipe1", O_WRONLY );
fd2 = open ("pipe2", O_RDONLY );
word acum, acum_nou=0;
word * tabel = tabelcrc(CRCCCITT);
word ac;


while(1) {
read ( fd2, &buf, 1);
read ( fd2, &cadru,4);
read(fd2, &acum, 2);

crctabel(buf, &acum_nou, tabel);
ac = acum_nou;
crctabel(ac>>8, &acum, tabel);
crctabel(ac& 0x00FF, &acum, tabel);
// printf("%d\n", acum);
printf ( "%c\n", buf );
if(cadru == contor+1 && acum==0) {
contor++;
write(fd1, &contor, 4);
}
else
write (fd1, &contor, 4);
}

close (fd1);
close (fd2);
return 0;

}

La compilare se va folosi si fisierul crc.c definit aici.

Detectarea si corectarea erorilor in legatura de date

Informatiile schimbate intre diferite sisteme sunt codificate, pentru a realiza adaptarea statistica a sursei la canalul de comunicatie. Canalul de comunicatie poate fi afectat sau nu de perturbatii.Un canal neperturbat ar corespunde unei criptari sau compresii a informatiei, pe cind un canal perturbat transmisiei acesteia.
Sistemele actuale care inglobeaza calculatoare si echipamente automate necesita o transmisie cit mai corecta a informatiei; pentru aceasta semnalul trimis este prelucrat inainte de a fi emis. Prelucrarea semnalului se realizeaza foarte usor in cazul transmisiei de semnale discrete, prin codificare. Receptorul va decodifica semnalul primit si va incerca sa estimeze daca au aparut erori. Pentru tratarea codificarii/decodificarii s-a dezvoltat un amplu aparat matematic, bazat pe calculul vectorial si polinomial. Astfel, in cazul codurilor bloc, folosind alfabetul binar {0,1}, se pot realiza 2^n combinatii (cuvinte de cod de aceeasi lungime n) folosind n biti.
Aceste cuvinte de cod pot fi asimilate cu vectori sau cu polinoame. Daca toate cele 2^n combinatii reprezinta cuvinte utile (cu sens), atunci aparitia unei erori transforma un cuvint de cod in altul, fara a se putea realiza detectia sau corectia erorilor. De aceea, informatia utila va fi codificata pe k
Un program de calcul al codului de control ciclic CRC-CCITT este urmatorul:


crc.h

#define CRCCCITT 0x1021 // polinomul generator

#include "stdio.h"
#include "stdlib.h"

typedef unsigned short int word;
typedef unsigned char byte;

word calculcrc (word, word, word);
word* tabelcrc (word);


crc.c

#include "crc.h"
#include "stdio.h"
#include "string.h"
//
// calculeaza noul rest partial pe baza vechiului rest
// (acum), a unui octet de date (data) si a polinomului
// generator (genpoli)
//

word calculcrc (word data, word genpoli, word acum)
{
int i;
data <<= 8;
for (i=8; i > 0; i--)
{
if ((data^acum) & 0x8000)
acum = (acum << 1) ^ genpoli;
else
acum <<= 1;
data <<= 1;
}
return acum;
}

/*
Functia "calculcrc" determina efectul aplicarii procedeului clasic de calcul CRC asupra unui octet de date. Generatorul polinomial (genpoly) si continutul initial al acumulatorului
(accum) sint date ca argumente.

Calculul prin program al secventei de control sugereaza posibilitatea de a trata problema nu la nivelul fiecarui bit al unui mesaj, ci la nivelul octetilor. Ideea este de a gasi o modalitate mai simpla prin care, dat fiind un octet de date si continutul vechi al acumulatorului (registrul de deplasare) sa se calculeze noua valoare a acumulatorului. Facind o simulare a operatiilor, se poate constata ca octetul de date se combina doar cu bitii mai semnificativi ai acumulatorului, noua valoare a acumulatorului fiind suma (modulo 2 a) secventei de control corespunzatoare acestei valori combinate si a octetului mai putin semnificativ al acumulatorului. Deoarece valoarea combinata ocupa 8 biti, ea poate avea 256 de valori diferite, secventele de control pentru toate aceste valori putind fi calculate si pastrate intr-un tablou. In acest mod calculul noului acumulator se poate face foarte simplu, prin insumarea modulo 2 a octetului inferior al acumulatorului cu o valoare precalculata, din cea totala.

Functia tabelcrc construieste acest tablou; ea are ca parametri:
generatorul polinomial si un pointer la o functie CRC (de ex. calculcrc) si intoarce (unsigned short * ) un pointer in tabela.
*/

//
// calculeaza tabelul codurilor CRC
// alcatuieste tabelul codurilor CRC pentru un anumit
// polinom generator (poli); apeleaza "calculcrc" pentru
// toate cele 256 combinatii posibile ale octetului de date
// intoarce un pointer la tabelul de coduri, alocat dinamic
//

word* tabelcrc (word poli )
{
word* ptabelcrc;
int i;
if ((ptabelcrc = (word*) malloc (256 * sizeof (word))) == NULL)
return NULL;
for (i=0; i < 256; i++)
ptabelcrc [i] = calculcrc (i, poli, 0);
return ptabelcrc;
}

// calculeaza CRC partial (acum) corespunzator unui octet
// (data) prin utilizarea tabelului codurilor CRC (tabelcrc)

void crctabel (word data, word* acum, word* tabelcrc)
{
word valcomb;
valcomb = ((*acum >> 8) ^ data) & 0x00FF;
*acum = ((*acum & 0x00FF) << 8) ^ tabelcrc [valcomb];
}

//
// calculeaza CRC pentru un fisier al carui nume este dat de utilizator; pentru verificare, dupa calculul CRC corespunzator fisierului, se continua calculul considerind si valoarea CRC gasita;
// rezultatul (acumulator) dupa adaugarea CRC este nul

int main ()
{
char s [] = "stuff this in your pipe";
word acum = 0, *tabel = tabelcrc(CRCCCITT); // CRCCCITT este generatorul de polinoame
int i;
for(i=0; i < strlen(s); i++)
crctabel(s[i], &acum, tabel); // pt toate car din string
printf("%d\n",acum);

word ac = acum;
crctabel(ac>>8, &acum, tabel);
crctabel(ac& 0x00FF, &acum, tabel);

printf("%d\n",acum);
return 0;

}

Protocolul SLIP

Protocolul SLIP (Serial Line Internet Protocol) actioneaza la nivelul legaturii de date, realizand incapsularea pachetelor IP pentru transmisia acestora pe linii seriale si pe conexiuni modem. SLIP a fost primul protocol de acest gen, si datorita numarului mic de functionalitati pe care le ofera a fost inlocuit de-a lungul timpului cu alte protocoale, cel mai cunoscut fiind PPP (Point-to-Point Protocol).

Principalul obiectiv realizat de SLIP este de a delimita pachetele de date (pentru ca acestea sa fie percepute ca separate). In acest scop, la sfarsitul fiecarui pachet de date se adauga un caracter special numit, in cadrul acestui protocol, END; END este caracterul cu codul ASCII 192. Astfel apare problema ca, daca in interiorul pachetului de date se afla un caracter cu codul 192, acesta sa fie interpretat gresit de catre receiver ca fiind "sfarsit de pachet". Problema se rezolva prin inlocuirea caracterelor 192 din interiorul pachetelor, astfel:

Se defineste un caracter special numit ESC, cu codul ASCII 219 (nu trebuie confundat cu caracterul ESC din codul ASCII; in cazul de fata ESC e doar o denumire ce tine de protocolul SLIP). Daca in interiorul unui pachet de date apare un caracter END, acesta e inlocuit cu o secventa de 2 caractere: caracterul ESC urmat de caracterul cu codul 220. Si caracterele ESC trebuie modificate - ele se inlocuiesc cu secventa formata din caracterul ESC urmat de caracterul 221.

O varianta imbunatatita a protocolului consta din adaugarea de caractere END si la inceputul pachetelor, care il ajuta pe receiver sa poata ignora niste eventuali octeti ce apar "in plus" intre pachete din cauza zgomotului de pe linie.

RFC 1055 (specificatia protocolului SLIP): http://tools.ietf.org/html/rfc1055

sender.c

#include "stdio.h"
#include "string.h"
#include "sys/types.h"
#include "sys/stat.h"
#include "fcntl.h"

char send220 = 220;
char send221 = 221;
char END = '%';
char ESC = '#';

int fd1;

void send (char *phrase)
{
int len=strlen(phrase), i=0;

while (len--)
{
if(phrase[i] == END)
{
write (fd1, &ESC, 1 );
write (fd1, &send220, 1 );
}
else if(phrase[i]==ESC)
{
write (fd1, &ESC, 1 );
write (fd1, &send221, 1 );
}
else
write (fd1, &phrase[i], 1 );
i++;
}
}

int main ()
{
fd1 = open ( "mypipe", O_WRONLY );
char * phrase = "Stuff this#in your pipe% and smoke it\n";
char * phrase1 = "SMOKE%IT!!!\n";
send(phrase);
send(phrase1);

write (fd1, &END, 1 );
close (fd1);
return 0;
}

receiver.c

#include "stdio.h"
#include "sys/types.h"
#include "sys/stat.h"
#include "fcntl.h"

char END = '%';
char ESC = '#';

int main ()
{
int fd1;
char buf, b;

fd1 = open ( "mypipe", O_RDONLY );
do{
read ( fd1, &buf, 1 );
if(buf==ESC)
{
read ( fd1, &b, 1 );
if(b==220)
printf("%c",END);
else if(b==221)
printf("%c",ESC);
}
else if(buf !=END)
printf("%c",buf);

}while(buf!=END);

close (fd1);
return 0;
}

Protocolul ABP folosind comunicatia prin pipe-uri

Pipe-urile permit comunicatia intre doua procese pe sisteme Unix.
ABP (alternating bit protocol) este un transmitator de date simplu care transmite date corupte sau pierdute. Fiecare mesaj de la A la B contine doua parti: data (ce se transmite propriu-zis) si o secventa de 1 bit (0 sau 1) numita tag. In schimb, B transmite lui A un mesaj de confirmare (ACKnowledgement) ACK0 sau ACK1. Cand A trimite un mesaj, il trimite in mod continuu, pana cand primeste mesajul de confirmare de la B care contine acelasi lucru ca si tag. Cand acest lucru se intampla, A transmite urmatorului mesaj.
Cand B primeste un mesaj care nu este corupt si are ca si continut 0, incepe sa trimita ACK0, pana cand primeste un mesaj valid cu numarul 0. Apoi incepe sa trimita ACK1, etc.

Mai jos, sunt prezentate 2 programe in C care simuleaza transmiterea de date intre doua programe. In Linux se deschid 2 console, unde se creeaza 2 pipe-uri cu numele date in program:

mkfifo pipe1
mkfifo pipe2

Apoi se ruleaza programele in acelasi timp si se observa transmiterea de date.

receiver.c

#include "stdio.h"
#include "unistd.h"
#include "sys/types.h"
#include "string.h"
#include "sys/stat.h"
#include "fcntl.h"

//receiver

int main ()

{
char tag;
int fd1, fd2;
fd1 = open ( "pipe1", O_RDONLY );
fd2 = open ("pipe2", O_WRONLY);

char buf [100];
int p;

while(1) {
read ( fd1, buf, 100 );
p=strlen (buf);
printf ( "%s \n", buf );
tag = buf [p-1];
write (fd2, &tag, 1);
}

close (fd1);
close (fd2);
return 0;
}


sender.c

#include "stdio.h"
# include "string.h"
#include "sys/types.h"
#include "unistd.h"
#include "sys/stat.h"
#include "fcntl.h"

// sender

char * phrase = "Stuff this in your pipe and smoke it";

int main ()

{ int fd1, fd2;
char tag;
fd1 = open ( "pipe1", O_WRONLY );
fd2 = open ("pipe2", O_RDONLY);
int i;
for(i=0 ; i < strlen (phrase); i+=3) {
write (fd1, phrase+i, 3);
read (fd2, &tag, 1);
}
close (fd1);
close(fd2);
return 0;
}

Tutorial Retele de calculatoare

Tanenbaum - Retele de Calculatoare