Intelligent cities: architecture (1/4)

Hilton Garcia Fernandes

This is the first post of a series on intelligent cities. The term is defined here, as well as a possible general architecture for an intelligent city. Other posts will deal with further angles of the problem.

 

Intelligent cities can be defined, in a simple way, as the ones able to solve collectively their problems.

That is by no means a consensus among researchers: intelligence is one of the most complex and controversial themes in psychology [1]. Collective intelligence  [2], a very young concept, is still more complex and controversial. To the top of that the understanding of a intelligent city is far from converging to a unified line of thought [3].

Even so, that is a definition to be kept, for it is really practical, and can guide future projects in Brazil and similar countries.

An intelligent city uses services made possible due to a network infrastructure available to the whole city [4]. That is: an intelligent city is built upon a digital city [5].

Theoretically, it would be possible that a city had collective discussion and solution of its problem only using person to person chatting. But that would be possible only for very small city. And even for them, the Internet offers tools so convenient that they allow longer conversation to be registered and reproduced with far more efficacy than they would through oral communication.

Conceptual architecture for an intelligent city

It is worth to examine the figure below to enhance the understanding of this intelligent cities definition.

Hierarchical architecture for an intelligent city

Infrastructure is the availability of a network for the whole city, offered by the digital city, or municipal wireless network. Integration is the fact that the whole city is effectively in communication to solve its common problems.

The layer named Services, still not discussed, contains exactly the services that will allow that integration.

The different services are given by numbers in the drawing, for a shorter representation. A possible list of them is:

1. Telecentre: a public place where people can access computers, the Internet, and other digital technologies [6]. It is obviously important for the people who have not computers;
2. Virtual museum: it is a survey of a city’s local culture, made available over the Internet. And people are urged to keep posting material — either from memory, or new cultural production.
   

   The team believes that the generation of culture is a way to remove the isolation of cities or communities that don’t feel they belong to the mainstream of information production. And so to raise their self-esteem.

3. Training for content generation, in the broadest sense.
   In Barra Bonita-SP, Brazil [7], the Barra Digital project hosted Joomla [7] courses for the generation of websites. In the broadest sense used here, the training should include also the creative writing and image creation. Always usign Free Software tools;
4. Third age support: people of this age range deserves special attention — even when they follow courses similar to others. They’re people that usually have more resistance to using computers, they sometimes feel themselves not belonging to this time, and eventually can suffer from diminishing vision, motion abiltiy and even intellectual skills — due to physical or psychological reasons.
   Besides that, they have lots of information and experience that shouldn’t be ignored by the community. Here the Internet can also be a good tool to minimize the physical that isolation that often may avoid the emergency helping of diseases, and major casualties;
5. Influence on the conventional school: treining of school teachers so that conventional classes can be complemented by content generation, exposed in the Internet.
   For instance, a geography class would generate several blog posts by the students, that would present and complement the information offered in class;
6. E-gov, or electronic government: softwares that will be used for the internal municipality operation, and to offer services to citizens.
   For instance, the population could consult their municipal tax status visiting a Web page. And even resolve any problem using it, always by the municipal wireless network.
   Another example is the city health system: using the digital city network, it will be fully connected, minimizing frauds and increasing control and transparency;
7. Monitoring: in an intelligent city, monitoring is concerned with the optimized use of systems that will handle devices generating audio and video signals, installed in places that demand special attention.
   These systems include but are not limited to the traditional camera-based circuits, usually referred to as CCTV [10]. Other monitoring systems can include audio sensors.
   The audio and video signals are sent to a central unit, where they’re analyzed and stored by a time lag that sometimes is defined by law;
8. Solidarity economy: is the economic development of comunities through procedures that emphasize the solidarity among people, while at the same time they search rationally a market share for the products that the communities can offer [11];
9. Urban mobility: the infrastructure of the intelligent city allows the communication of moving cars and buses with computers located next to the road. That permits, for instance:
   1. To know precisely where is a bus — that is important both for logistics of transportation, as well for the safety of passengers and the bus itself.
   2. To know how much time a given bus will take to arrive at a certain bus stop, what is very useful for the passengers waiting on the bus stop;
   3. Given a large enough number of monitoring points, that collect information on the passing cars and buses, it is possible to know better the road velocity structure of the city, and so to plan measures to enhance it.

   This knowledge provided by the intelligent city infrastructure can be used to arrived in the much wanted future urban mobility, that will be more satisfying, rational, and even sustainable [12];

10. Smart grid: means an electric network with elements that are capable of communicating and thus providing an intelligent behavior for all system [13]. That is useful to solve problems as well as to optimize the use of the electrical network. In current electrical networks, all the intelligence stays in power stations and substations.
    Almost any presentation on smart grids states that houses will be able to buy energy in day hours when it’s cheap, to store it, and to resell it when the system needs it more, and will buy it paying more. So, the intelligent houses will be able to help the system works, as well as to generate income for their users.

References

[1] Intelligence

https://secure.wikimedia.org/wikipedia/en/wiki/Intelligence

Visited on April, 11th 2011

[2] Collective intelligence

https://secure.wikimedia.org/wikipedia/en/wiki/Collective_intelligence

Visited on April, 11th 2011

[3]Intelligent city

https://secure.wikimedia.org/wikipedia/en/wiki/Intelligent_city

Visited on April, 11th 2011

[4]Intelligent cities vs.digital cities

https://secure.wikimedia.org/wikipedia/en/wiki/Intelligent_city#Intelligent_cities_vs.digital_cities

Visited on April, 12th 2011

[5] Digital city

https://secure.wikimedia.org/wikipedia/en/wiki/Digital_city

Visitado em 12/04/2011

[6]Telecentre

https://secure.wikimedia.org/wikipedia/en/wiki/Telecentre

Visited on April, 11th 2011

[7]Barra Bonita, São Paulo

https://secure.wikimedia.org/wikipedia/en/wiki/Barra_Bonita,_S%C3%A3o_Paulo

Visited on April, 12th 2011

[8]Joomla

https://secure.wikimedia.org/wikipedia/en/wiki/Joomla

Visited on April, 12th 2011

[9]Free Software

https://secure.wikimedia.org/wikipedia/en/wiki/Free_software

Visited on April, 12th 2011

[10]Closed circuit television

https://secure.wikimedia.org/wikipedia/en/wiki/Closed-circuit_television

Visited on April, 12th 2011

[11]Solidarity economy

https://secure.wikimedia.org/wikipedia/en/wiki/Solidarity_economy

Visited on April, 12th 2011

[12]Towards a new culture for urban mobility

http://eur-lex.europa.eu/LexUriServ/LexUriServ.do?uri=COM:2007:0551:FIN:EN:PDF

Visited on April, 12th 2011

[13] Smart grid

https://secure.wikimedia.org/wikipedia/en/wiki/Smart_grid

Visited on April, 12th 2011

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

How to estimate latency and bandwidth ?

Hilton Garcia Fernandes

This is another blog post about latency and bandwith in computer networks of the Wireless Technologies blog [1]. The series of texts was started with Latency and bandwidth [2], that presented these concepts along the linear model, that is relatively simple.

Where latency comes from ? [3], also in this blog, listed the network phenomena that give raise to a constant delay in the message transmissions.

The present text will present a way to estimate the parameters latency and bandwidth. The verb is not casual: to estimate means that the parameters have oscillating values, due to variation in any network’s capacity.

Besides that it is also necessary to chose a way to measure the message passing time; for there are many forms of using the network: sending and receiving e-mails, web browsing, etc.

Problem formulation

As any Internet [4] user knows very well, the capacity of a network can vary over time. So, the values that are calculated are estimated, similar to a mean average, for instance.

Besides that, there’s also the problem of how to obtain a measure: it seems intuitive to talk about the concepts, but there are many forms of using a network. So, one has to chose a limited set of activities that is able to generate a measure. In current computing jargon, one has to chose a benchmark [5].

Introducing conceptually the benchmark used

To properly measure the time it takes to send a message from a computer A to another one named B, it would be necessary that B could inform A the moment it received the message.That means, B would have to send another message to A. Unfortunately, there is a problem of synchronization of the clocks of computer A and B: since currently networks are very fast, it takes too little time to send a message, and the computer clocks would have to be adjusted with a lot of precision, what can be very hard to do.

Another solution is that A sends a message to B and waits for B to answer to it. That way all measures of the process are made in a single computer. That is the purpose of the benchmark named ping-pong [6].

That benchmark can be represented in the diagram below, that was suggested by [7]

Diagrama conceitual do benchmark ping-pong

When computer A sends a message to B, the message information has to cross network layers, as mentioned in [3]. That is represented by the slant down named d1. The message then goes through the network during the time t1, when it is received by B.

Then the message information cross the network layers, now in the inverse direction, from the physical layer to the application layer during the time to slant up s1. Once B receives the message, it immediately sends it back to A. Now the message needs to cross network layers, what it does during time d2.

Now the message is transmitted from B to A during time t2. When it arrrives at A, it crosses again the network layers during the slant up time t2. Then it is finally received by the benchmark program.

The time T´ that A measure from sending the message to its receiving is the summation of all times:

If the network conditions are the same, and computers A and B were reasonably similar, then t1 = t2 = t. Then, analogously, it is reasonable to suppose that times to slanting down to the network are equal: d1 = d2 = d. And also that the times to slanting up from the physical media to the application are also equal: s1 = s2 = s.

Thus the total time becomes:

Now, one can sum the time to slant down d and to slant up s the network layers in a unique time p to cross the network, from application to application. That is . p = d + s. Now comes the formula

This formula causes one to remember that the time T measured in A is really twice the time needed to transmit a message just from A to B, without sending it back; that is just the ping, without the pong…

Of course, time T will grow larger as the number of bytes transmitted gets larger, exactly what happens with t. However, p will remain the same, independently from the size of the message. So, getting back to the linear model

It is easy to see that

• α, the cost constant is equivalent to p, the time in which the message slants up and down the network layers, from the physical layer to the application layer and vice-versa;
• t, the time in which the message was transmitted over the network, is a function of the number of bytes that were transmitted — and in the linear model it is βn;
• the total time T of transmission of a message with n bytes is really a function of n only, and that is represented as T(n).

Indeed, using statistical methods it is possible to estimate α e β accurately. Statistics shows that it is practically total the adjustment of the linear model to the network measures obtained by benchmarks such as ping-pong.

These conclusions are discussed in the next section.

Calculating parameters through statistics

The estimation of parametrs α and β is done through linear regression [8]. In a few words, that means to minimize the approximation of the linear model to the times of T that have been measured in a real network. To do so, many measures of time, for different message sizes. In a more formal notation, one makes m time measures for several message sizes, and they are called respectively Ti e ni.

(One of the techniques to minimize the variability of measurement errors is to make several measure time measures for the same message size.)

The basic technique to that estimation is called Least Squares Method [9]. It tries to minimize the quadratic error, the summation of each difference between what was measured and what was calculated. That is expressed by the formula:

where Ti are the times measured: for each one of them there is a corresponding mesage size ni. That way, the time T1 was obtained when a message of size n1 was used etc.

Statics has tools to validate or not the approximation — particularly if the adjustment between calculated and measured values weren’t excellent, for instance, due to oscillations in network traffic. The tool named ANOVA [10] evaluates if the approximation was so bad that the parameter β may be consdered null. That means: there is no relationship between the time T for transmitting a message and n, its size in bytes.

Student’s t-test [11] let’s one evaluate the quality of each parameter. That is: how much α and β help explain the behavior of T as a function of values of n.

R [12] is a statistical Free Software [13] that is very complete, featuring excellent quality. It has this and many other tools already implemented in the standard distribution.

References

[1] Wireless technologies

https://wirelesstechnol.wordpress.com/

Visited on 06 August 2010

[2] Latency and bandwidth

https://wirelesstechnol.wordpress.com/2010/07/09/latency-and-bandwidth/

Visited on 06 August 2010

[3] Where network latency comes from ?

https://wirelesstechnol.wordpress.com/2010/07/22/where-network-latency-comes-from/

Visited on 06 August 2010

[4] Internet

https://secure.wikimedia.org/wikipedia/en/wiki/Internet

Visited on 06 August 2010

[5] Benchmark (computing)

https://secure.wikimedia.org/wikipedia/en/wiki/Benchmark_%28computing%29

Visited on 06 August 2010

[6] What does ping pong benchmark mean?

http://icl.cs.utk.edu/hpcc/faq/index.html#132

Visited on 06 August 2010

[7] Benchmarking of Multicast Communication Services
ftp://ftp.cse.msu.edu/pub/acs/reports/msu-cps-acs-103.ps.gz
Visited on 06 August 2010

[8] Linear regression

https://secure.wikimedia.org/wikipedia/en/wiki/Linear_regression

Visited on 06 August 2010

[9] Least square

https://secure.wikimedia.org/wikipedia/en/wiki/Least_squares

Visited on 06 August 2010

[10] ANOVA

https://secure.wikimedia.org/wikipedia/en/wiki/ANOVA

Visited on 06 August 2010

[11] Student’s t-test

https://secure.wikimedia.org/wikipedia/en/wiki/Student%27s_t-test

Visited on 06 August 2010

[12] The R Project for Statistical Computing

http://www.r-project.org/

Visited on 06 August 2010

[13] Free software

https://secure.wikimedia.org/wikipedia/en/wiki/Free_software

Visited on 06 August 2010

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 Brasil License.

Where network latency comes from ?

In Latency and bandwidth [1], on this blog Wireless technologies [2] comments were made about the linear model

that allows one to estimate the time spent transmitting a message with n bytes on a given network. In this model α is a constant cost in time for transmitting any number of bytes. The factor β that multiplies the number of bytes n is associated with the maximum bandwidth available on the network. That is: 1/β is the largest available bandwidth on it.

After that brief overview of concepts of the linear model, the next step is to discuss what causes the communication costs.

Network latency can be associated to several factors:

• in a wireline network like Ethernet [3], it is important to avoid collisions [4]. That is: two packets beeing transmitted at the same time in the same network. There is an algorithm named CSMA/CD [5], thatt can detect collisions.
  It is cost is almost the same for any single packet;
• in wireless networks like Wi-Fi [6], there is a similar problem. In that case, due to characteristics of the physical medium defined by the electromagnetic radio waves, the algorithm is called CSMA/CA [7], and tries to avoid collisions (CA is for “collision avoidance”) instead of detecting them as in CSMA/CD.
  Here the cost is also relatively constant for any single packet.
• another source of communication cost, more relevant each day in the world of internets [8], or interconnected networks — and the Internet [9], or the large world network — is the transfer of information between networks, or the routing [10]. In this case, the information packets are rewritten in order to account for their entrance in other networks. Again, that has a cost for each packet;
• there’s still another component for the fixed cost of each packet: the so called encapsulation and reverse encapsulation of a data packet, both in the theoretical sense of OSI architecture [11], or in the most implemented network architecture, the TCP/IP model [12].
  In a case or another, the network is split into several levels (or layers), and that allows, for instance, the technology independence — networks using different physical supports can let communicate between each other: a computer connected in a 3G network [13] can talk to another one in a DSL-based network [14].
  Again, the cost of transferring packets between different network layers happen for each single packet.
• packet fragmentation [15]: large messages may have to be split in smaller packets if they are larger maximum allowed packet size in that network segment, the MTU [16].
• fragmentação de pacotes [15]: pacotes muito grandes podem ter que ser quebrados em pedaços menores, se forem maiores que o tamanho máximo de pacotes naquele segmento de rede, o MTU [16].

All these costs are paid for each packet. Thus, if a message is long enough to be broken into several packets in the network, it will incur several times into the same costs of collision, routing, etc. ?

Indeed, that will happen, but there are effects that alleviate the multiplication of costs:

• acquiring medium: when a station starts to transmit throught the network, it keeps the right to transmit for some time. That feature is part of several collision handling algorithms, exactly to minimize the cost of repeated negotiating;
• pipelining [17], or “assembly line” effect: in an assembly line [18], the fact of having several independent units working in parallel different parts of car, for instance, wil warrant that the interval between the finishing of different products be sensibly smaller than the total time for the finishing of a single product.
  An old teacher used to explain that the total time to make a Beetle was 48 h. However, the time interval between two Bettles being completed was just 40 min.
  In a network transmission, there are at least two parallel units: the main CPU that will process the encapsulation and reverse encapsulation of packets, and the network card, that will handle the medium acquistion and the collision handling.

Nexts posts of Wireless Technologies will present more details of the estimation of the all important network parameters latency and bandwidth, as well as complementary parameters — that can enhance the understanding of networks.

References

[1] Latency and bandwidth

http://wirelesstechnol.wordpress.com/2010/07/09/latency-and-bandwidth/

Visited on 16 July /2010

[2] Wireless technologies

http://wirelesstechnol.wordpress.com/

Visited on 16 July /2010

[3] Ethernet

https://secure.wikimedia.org/wikipedia/en/wiki/Ethernet

Visited on 16 July /2010

[4] Colision domain

https://secure.wikimedia.org/wikipedia/en/wiki/Collision_domain

Visited on 16 July /2010

[5] CSMA/CD

https://secure.wikimedia.org/wikipedia/en/wiki/CSMA/CD

Visited on 16 July /2010

[6] Wi-Fi

https://secure.wikimedia.org/wikipedia/en/wiki/Wi-fi

Visited on 16 July /2010

[7] CSMA/CA

https://secure.wikimedia.org/wikipedia/en/wiki/CSMA/CA

Visited on 16 July /2010

[8] Internetworking

https://secure.wikimedia.org/wikipedia/en/wiki/Internetworking

Visited on 16 July /2010

[9] Internet

https://secure.wikimedia.org/wikipedia/en/wiki/Internet

Visited on 16 July /2010

[10] Routing

https://secure.wikimedia.org/wikipedia/en/wiki/Routing

Visited on 16 July /2010

[11] OSI model

https://secure.wikimedia.org/wikipedia/en/wiki/OSI_model

Visited on 16 July /2010

[12] TCP/IP model

https://secure.wikimedia.org/wikipedia/en/wiki/TCP/IP_model

Visited on 16 July /2010

[13] 3G

https://secure.wikimedia.org/wikipedia/en/wiki/3G

Visited on 16 July /2010

[14] Digital subscriber line

https://secure.wikimedia.org/wikipedia/en/wiki/Digital_subscriber_line

Visited on 16 July /2010

[15] IP fragmentation

https://secure.wikimedia.org/wikipedia/en/wiki/IP_fragmentation

Visited on 16 July /2010

[16]Maximum Transfer

https://secure.wikimedia.org/wikipedia/en/wiki/Maximum_transmission_unit

Visited on 16 July /2010

[17]Pipelining

https://secure.wikimedia.org/wikipedia/en/wiki/Pipelining

Visited on 16 July /2010

[18]Assembly line

https://secure.wikimedia.org/wikipedia/en/wiki/Assembly_line

Visited on 16 July /2010

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Latency and bandwidth

Hilton Garcia Fernandes

A lot has been said about latency and bandwidth, and is still being said. These are two fundamental concepts for the comprehension and characterization of computer networks. It is a pity that it is not easy to find clear and precise definitions of these concepts on the Web. Maybe they belong to the kind of terms that are restricted to network practicioners and researchers.

One of best articles on this theme is [1], that defines latency and bandwidth with good humor and clarity.

It is usual [2] to describe the time in — let´s say in seconds — that a network needs to send a message with n bytes as

In mathematical terms, this is a line equation, where α is the constant, and β is the line slope or gradient.

If it was possible to transfer a message with 0 bytes, the time T(0) would be α seconds. The parameter α is called latência, or even “zero byte latency”. To understand the meaning of β in the formula for T(n), it is useful to consider the transfer rate B(n) that is achieved for n bytes. The transfer rate is calculated dividing the number of bytes that have been transferred by the time that the transfer spent. In mathematical terms

This formula can be better understood if one consider the inverse of B(n), or
Reversing the last form again, one has

When n is too large, the ratio α/n becomes too little, and one has:

That is the maximum transfer rate that could be achieved in this network. So, it is usual to call the parameter 1/β as network bandwidth. To avoid this division, Hockney [2] gives the formula for T(n) with the slope in the inverse form, that is:

That way, Hockney [2] can talk of bandwith as ρ only, not as the ratio 1/β. But that is merely a convenience, for the concepts are the same.

Conclusion

In a few words:

• latency is an initial network cost, paid for every message that is transmitted in it. Even for the theoretical message of zero byte length.
• bandwidth is the maximum network performance, achieved theoretically with messages of infinite size; the network gets close to them in messages of large length.

In any case, it is usual to consider latency and bandwidth as parameters that can describe most of a network behavior in terms of message passing.

Next posts in Wireless Technologies will present more details and implications of this pair of important parameters, as well as complementary parameters, that can give an even better picture of network behavior.

References

[1] It’s the Latency, Stupid

http://rescomp.stanford.edu/~cheshire/rants/Latency.html

Visitado em 02/06/2010

[2] R. Hockney, “The communication challenge for MPP: Intel Paragon and Meiko CS-2,” Parallel Computing, vol. 20, no. 3, pp. 389-398, March 1994.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

What is Traffic shaping ?

Rodrigo Filipe Silva Carramate

 

Although some may think otherwise, Traffic shaping [1], is not just a trick that commercial ISPs use to limit the download rate of the so called heavy users, that transfer too much information over the Internet. Indeed, there are many users reporting they’ve been affected by trafic shaping, mainly those addicted to peer-to-peer (like eMule or BitTorrent) [2]. However, this doubtful ISP practice is far from being the only utility of shaping: when carefully planned, it can make networks much more productive.

Introducing the concept

The meaning of shaping in common language already advances the purpose of the technical procedure: it is simply to model a network’s bandwidth, or better still, to attribute a control profile to a network’s bandwidth.

The reader may then ask: why should one introduce limits to a network, when one would prefer to maximize its capability? To answer that question, one should remember that the different kinds of traffic in a network have also different priorities. For instance, nobody would comply of an e-mail message arriving some seconds later to its destination. However, if the same e-mail user is in a videoconference abroad with his or her boss and is forced to wait one or two seconds among each word the boss says… The videoconference user will become upset quickly.

The two cases show clearly one of the benefits of traffic shaping: the priorization of network traffic, that delays less urgent packets so the urgent ones are delivered more quickly. This feature of traffic shaping is a mechanism of QoS — or the attempt to warranty different levels of network service for different applications of it.

Traffic shapping can work by quantizating the network bandwidth in classes of traffic. To explain that, let’s suppose a person in his or her office, on a tight schedule to deliver a report that’s essential to finish a project. Then, mysteriously the network, so necessary to finish the report, goes so slow that a web page takes minutes to be fetched. However, a lazy user, in the next table, is frantically downloading not so urgent MP3 files, under high transfer rates, using peer-to-peer connections. There are big chances that the lazy neighbor is using all network bandwidth available for the Internet in the office’s network. Some companies would simply block the use of music downloading, but let’s suppose this company has a more liberal policy.

In this situation, it would be necessary to limit the transfer rate allocated to peer-to-peer traffic — the very purpose of traffic shaping. If the upload and download rates for peer-to-peer are limited, there would remain more band for Web browsing — so it would become faster, whether or not lazy users are downloading music.

The profiles for traffic shaping can be easily changed, to adapt the network to different uses. The network manager can run specific tools to enable the automatic change of network profiles, for instance according the specific needs of certain hours of the day.

Use of traffic shaping in municipal wireless networks

Municipal wireless networks [4] sport a large variety of uses, due to the complexity of the network uses. For instance, let’s suppose a city network designed to serve both the local government sructure as well as the citizens. A rule of traffic shaping could be to reserve some reasonable band to the local government during prime time. That way, the proper operation of the local government would be assured, and the citizens wouldn’t drain all the available band. However, off prime time, most of the reserved band could be given to the citizens. This new bandwidth partitioning would assure the operation of the emergency sites as well as allow to the citizens a more comfortable network browsing.

Concluding…

In a few words, traffic shaping can be understood as a set of rules designed to optimize the network use and adapt it to specific needs. Unfortunately, there are ISPs who use it to do harm to consumers. For instance, prohibiting Peer-to-Peer or Internet telephony, the so called VoIP [5].

References

[1] Traffic shaping

https://secure.wikimedia.org/wikipedia/en/wiki/Traffic_shaping

Visited on 05/06/2010

[2]Quality of service

https://secure.wikimedia.org/wikipedia/en/wiki/Quality_of_service

Visited on 06/14/2010

[3] Peer_to_peer

https://secure.wikimedia.org/wikipedia/en/wiki/Peer_to_peer

Visited on 06/14/2010

[4] Municipal wireless network

https://secure.wikimedia.org/wikipedia/en/wiki/Municipal_wireless_network

Visited on 06/14/2010

[5] Voice over IP

https://secure.wikimedia.org/wikipedia/en/wiki/Voice_over_IP

Visited on 06/14/2010

Learn more

Traffic control

• Linux Advanced Routing & Traffic Control HOWTO
  
  http://lartc.org/howto/
  
  A text much more conceptual than operational, but still obligatory reading
  Visited on 06/14/2010
• IPROUTE2 Utility Suite Howto
  
  http://www.policyrouting.org/iproute2.doc.html
  
  The GNU/Linux tools for traffic shaping
  Visited on 06/14/2010.

QoS

• Guide to IP Layer Network Administration with Linux
  
  http://linux-ip.net/linux-ip.pdf
  
  Overview of classic GNU/Linux network tools
  Visited on 06/14/2010.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Yet Another Asterisk Tutorial

Daniel Caraça

Nowadays, telephony is an essential communication medium. While there are many other media, telephony is still a winner for its simplicity and efficacy in transmitting information. Unfortunately, its cost can be high, particularly if we consider long distance calls. There’s a solution that’s been increasingly used is to join Internet and telephony, giving rise to VoIP [1], or “Voice over IP.” VoIP is a way to make long distance call with the cost of local calls. Using Free Software [2], the implementation of VoIP is very cheap and has the added advantage of ease installation and maintenance.

A low quality connection to the Internet can cause problems to a VoIP call. In a normal call, one has the feeling of talking to a person that’s really close, for the voice transmission looks instantaneous. But when there’s a delay for some reason, the user feels some discomfort and keeps repeating “Hello, hello?” till the other party answers; that is: till the answer signal arrives. So, a working VoIP communication demands that parameters like latency (or the time taken to have an answer) [3] and jitter (or the irregularity in that time) [4], are tuned carefully, as they warranty the quality of a VoIP call [1].

In wireless municipal networks, aka digital cities, that have been implemented using mesh networks [5] there’s a possibility that data pass for more than a node — each intermediate node is a called a hop. If the number of hops is too large, that will increase the communication latency.

The sensitivity to latency makes VoIP an excellent test to a computer network. For it is true that numbers obtained in benchmarks [6] give much information, but there’s nothing better than to feel intuitively, to experience in real life, the quality of a network.

This tutorial, that may look as just another asterisk tutorial among many, has as its purpose to show how simple can be to make a VoIP connection between two computers. And yet the type of connection presented here is the basis of VoIP systems of large size, that can connect many computers. The approach here has emphasis on the simplicity, and only the minimal necessary will be presented. Another important difference is that this text tells how to associate names — and not just numbers — to extensions, and that is not common in the average tutorial.

Three computers are used: one of them as a server, the other two as clients. The clients will run a softphone; that is: a software that simulates a telephone. This tutorial uses Ekiga [7], already installed on Ubuntu [8], nowadays the most popular Linux distribution [9]. However, Ekiga will run the same in any other distribution. In the computer server, a Free Software [2] named asterisk [10] will be used as a VoIP server software. In order to install asterisk in Linux distributions like Debian [11], Ubuntu [9] and other that have apt-get [12], all it takes is to type:

# apt-get install asterisk

In case the distribution being used doesn’t have the apt-get command, there are many tutorials available on the Internet about how to install asterisk in non-Debian distributions, using their corresponding commands. For instance, yum [13] for Fedora [14], and yaST [15] for openSUSE [16].

The asterisk software works this way: when a user logs onto the server with a client program, asterisk creates a route to its computer. That means asterisk will know where it should redirect the connection to in case somebody calls the user extension. That also means if user doesn’t long onto the server, asterisk will not know how to get into its computer. The configuration of asterisk are done using configuration files; they are where extensions are added, where one defines actions to be started when a call is received, etc. The two most used files are sip.conf and extensions.conf. They shall be modified in the next steps.

Editing sip.conf

File sip.conf holds information on the extensions that will use the SIP [17] protocol to communicate.

1) There is a line in sip.conf that begins with:

bindaddr=0.0.0.0

If 0.0.0.0 is used, o asterisk will listen to in every network interface in the computer it is being run on. But it seems advisable to write down in this field the IP number of the main server interface, for that way the VoIP-related ports won’t be blocked, as it can be seen in the description of bind [18] system call.

2) The following lines should be added to the end of the file:

[2000] type=friend secret=1234 host=dynamic context=teste [2001] type=friend secret=4321 host=dynamic context=teste

3)That means:

• [] the name between square brackets is a user login, and the corresponding extension number for the SIP protocol.
• type is the user type. There are just 3: friend, peer e user. They can receive and make calls, just receive calls, and just to make calls, in that order;
• secret is the password used to long onto the server;
• host is the IP number of the client’s computer. In case it changes dynamically, the keyword dynamic should be used;
• context is the group that the user will belong to. Groups are defined in file extensions.conf. In case the user belongs to a context, he or she won’t be able to call to another user belonging to another context; unless the call is redirected.

This frame holds the definition of two SIP users, with the least possible information. Everything else is defined by default values.

Editing extensions.conf

File extensions.conf contains the actions associated with the numbers dialed.

1) The following lines should be appended to the end of the file:

[ntsf] exten => 2000,1,Dial(SIP/2000,20) exten => 2000,2,Hangup exten => joao,1,Dial(SIP/2000,20) exten => joao,2,Hangup exten => 2001,1,Dial(SIP/2001,20) exten => 2001,2,Hangup exten => maria,1,Dial(SIP/2001,20) exten => maria,2,Hangup

2) That means:

• [] the name between square brackets will be the name of the context, or group, the extensions belong to;
• exten => 2000,x,..... means that when extension 2000 receives a call, asterisk will run commands started with 2000, beginning with priority 1, then 2, and so on…
• ....,Dial(SIP/2000,20) means that asterisk will call for 20 seconds the computer that has been logged as the extension 2000 defined in file sip.conf;
• Hangup means asterisk will hang up the call if it is not completed;
• the names joao e maria weren’t defined anywhere, but can be used. That’s an interesting feature of file extensions: it tells to asterisk do what an extension is called. That way, calling an extension doesn’t mean one will only be able to talk to a person that uses a given extension, for one can create redirectioning extensions, extensions for answering machines, automated attendant extensions etc. Making two extensions activate the same actions can be a way to let users chose between using numbers or names.

Reloading config files into asterisk

The changes made here to sip.conf and extensions.conf have been enough to allow calls using asterisk. The next thing to do is to reload the changed files into it. To do so, all one has to do is to type

# asterisk -r

That way, the # asterisk CLI [20] will be opened. Now the following commands should be typed onto it:

# sip reload

# dialplan reload

That way, files sip.conf and extensions.conf will be reloaded. Now asterisk is ready to manage calls.

Making calls

In each client, one should start Ekiga, and then click on the Edit tab. Then, click on Accounts. A dialog box will appear, where one should click in Accounts and then in Add a SIP account. In the new dialog, the asterisk server IP number should be informed in registrar. Fields user e authentication user should be filled with the calling user — for instance 2000 –, and password should hold his or her password. Type any name you wish in field name, since it is an information for Ekiga only. Field timeout should be filled with an appropriate timeout in seconds — for instance, 60. Now, one should press Ok, and then close in the previously open dialog.

Do a similar configuration in the other client computer, and the client configuration steep is finished.

To communicate the two clients, fill in the field labeled sip: in one then with extension@server.ip, where extension is the extension number of the other client, and server.ip is the IP number of the server computer with asterisk. Press the Enter key or click in the button with the green arrow, and the call will be made.

Further steps

The configurations will only let two computers call each other. However, asterisk has a far larger potential, and will offer answering machines, sounds, conference room etc. More information can be found in Internet tutorials like VoIP Wiki [21]

References

[1] VoIP

https://secure.wikimedia.org/wikipedia/en/wiki/VoIP

Visited on 04/04/2010

[2] Free Software

https://secure.wikimedia.org/wikipedia/en/wiki/Free_software

Visited on 04/04/2010

[3] Latency (engineering)

https://secure.wikimedia.org/wikipedia/en/wiki/Latency_(engineering)

Visited on 04/04/2010

[4] Jitter

https://secure.wikimedia.org/wikipedia/pt/wiki/Jitter

Visited on 04/04/2010

[5] Wireless mesh networks and graphs

http://wirelesstechnol.wordpress.com/2010/01/25/wireless-mesh-networks-and-graphs/

Visited on 04/04/2010

[6] Benchmark (computing)

https://secure.wikimedia.org/wikipedia/en/wiki/Benchmark_(computing)

Visited on 04/04/2010

[7] Ekiga

https://secure.wikimedia.org/wikipedia/en/wiki/Ekiga

Visited on 04/05/2010

[8] Ubuntu

https://secure.wikimedia.org/wikipedia/en/wiki/Ubuntu_(operating_system)

Visited on 04/05/2010

[9] DistroWatch.com

http://distrowatch.com/index.php

Visited on 04/05/2010

[10] asterisk

https://secure.wikimedia.org/wikipedia/en/wiki/Asterisk

Visited on 04/05/2010

[11] Debian

https://secure.wikimedia.org/wikipedia/en/wiki/Debian

Visited on 04/05/2010

[12] Advanced Packaging Tool

https://secure.wikimedia.org/wikipedia/en/wiki/Advanced_Packaging_Tool

Visited on 04/05/2010

[13] Yum

http://fedoraproject.org/wiki/Tools/yum

Visited on 03/23/2010

[14] Fedora

https://secure.wikimedia.org/wikipedia/en/wiki/Fedora_(operating_system)

Visited on 04/05/2010

[15] YaST

https://secure.wikimedia.org/wikipedia/en/wiki/Yast

Visited on 04/05/2010

[16] openSUSE

https://secure.wikimedia.org/wikipedia/en/wiki/OpenSUSE

Visited on 04/05/2010

[17] Session Initiation Protocol

https://secure.wikimedia.org/wikipedia/en/wiki/Session_Initiation_Protocol

Visited on 04/06/2010

[18] Bind

http://publib.boulder.ibm.com/infocenter/tpfhelp/current/index.jsp?topic=/com.ibm.ztpf-ztpfdf.doc_put.cur/gtpc2/cpp_bind.html

Visited on 23/03/2010

[19] Command Line Interface

http://en.wikipedia.org/wiki/Command-line_interface

Visited on 23/03/2010

[20] VoIP Wiki

http://www.voip-info.org/wiki/view/Asterisk

Visited on 23/03/2010

Connectivity of mesh networks

Ricardo Andrade Dalla Bernardina

Mesh networks, and particularly wireless mesh networks, can be studied using the graph theory [1]. If they’re to work correctly, any AP (or “Access Point”) should have communication with any other, even if not directly. Due to that, it is natural the relationship between the connectivity in a mesh network and the connectivity of the graph associated to it [2]. With that in mind, connect.g [3], a small program, was developed to evaluated whether a graph, eventually associated with a mesh network, is connected or not, using the gvpr programming language [4]. Here follows the program:

BEGIN {
     graph_t comp;
}
N {
     comp = compOf ($G, $);
     printf ("%s\n", $G.name);
     if (comp.n_nodes < $G.n_nodes) {
          printf("'%s' is not a connected graph.\n", $G.name);
     }
     else{
          printf("'%s' is a connected graph.\n", $G.name);
     }
     exit(0);
}

In the BEGIN block, the graph comp is declared. This graph is used in the N block, where it receives the return of a call to compOf() over the graph the connectivity is evaluated. Given a graph g and a node n in this graph, he function compOf() evaluates which nodes of g are connected, directly or not, to n. This function yields a subgraph of g with only the nodes connected to n. This subgraph has not the edges in g, and if they are needed, one should issue a call to induce() onto that subgraph.

The program issues a call to compOf($G, $), where $G means the graph currently being processed, and $ the current node in the context of N. In a connected graph, any node is, by definition, connected to each other, the number of nodes of the subgraph resulting from this call to compOf() should be equal to the number of nodes in the original graph. So, the comparison

if (comp.n_nodes < $G.n_nodes)

It evaluates whether the number of nodes in the result of compOf() is smaller than the number of nodes in the original graph. If the answer is positive, the graph is not connected. Then, the program displays on screen a message stating the graph is not connected. In case the answer is negative, the number of nodes in compOf() result is equal to the number of nodes in the original graph, since it’s not possible that a subgraph has a larger number of nodes than its parent graph. So the program will display a message informing the graph is connected.

Then in the program is issued a call to exit(0) so that the program doesn’t issue the same message for all the nodes — for if the node is not connected, the call compOf() for each of the nodes will generate a connected component with less vertices than the original graph.

So, it is necessary to test a single node — what means this is a rather efficient method.

Referências

[1] Wireless mesh networks and graphs

http://wirelesstechnol.wordpress.com/2010/01/25/wireless-mesh-networks-and-graphs/

Visited on 03/29/2010

[2] Graph theory

https://secure.wikimedia.org/wikipedia/pt/wiki/Teoria_dos_grafos

Visited on 03/29/2010

[3] connect.g

http://sites.google.com/site/hgfernan/arquivos/connect.g?attredirects=0

Visited on 03/29/2010

[4] Introducing gvpr

http://wirelesstechnol.wordpress.com/2010/02/22/presenting-gvpr/

Visited on 03/29/2010

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Introducing gvpr

Ricardo Andrade Dalla Bernardina

DOT [1] is a language designed to define graphs [2]. It was initially used in the program also named dot, a part of the graphviz [3] package, that has lots of tools for the visualization and manipulation of graphs.

Here follows a very basic sample of the construction of a graph, to be stored in .dot file. The first thing that should be be done is to give a name to the graph. Supposing the name chosen was g, one would write:

    graph g {}

Everything else in the file should be inside the braces after graph g.

The next step is the creation of nodes, and for that one writes:
X [label="node"]; — being X the node name (sometimes named an ‘identifier’ in other languages), and node the node label. For instance,

    graph g {
        nA [label = "node A"];
    }

There is no practical limit in the number of nodes that can be used.

After that, to describe an edge, one should write down the pair of node identifiers that are connected (directed graphs are not being considered), and between them insert “--“, or two contiguous dashes. For instance, X -- Y; is the edge that connects the nodes named X and Y.

Then the saved file should read by a visualization program, like dot [4], mentioned before, and the graph could be seen — for instance, as a JPEG image. Here is an image of the code in [5]:

In the graphviz package there’s also the gvpr [6] tool. It is very powerful, but not well known. It can process, manipulate and — in general terms — rewrite graphs.

Here follows a brief presentation of program descstat.g [7], that uses gvpr to calculate the maximum and minimum node degree of a given graph, besides calculating mean average, variance, standard deviation and coefficient of variation of the graph node degrees.

First of all, one should remember that gvpr interprets only graphs defined in DOT language, being useless for any other graph definition language. The gvpr environment defines a programming language that has the following predefined blocks

• BEGIN is run only once, at the program’s start;
• END is run only once, at program’s end;
• there’s also BEG_G, that is run for each graph, before its processing;
• and the corresponding END_G, that is similarly run for each graph, but after its processing;
• and N is run for each and every graph node;
• and the corresponding E, that is run for each and every graph edge.

BEG_G and END_G should be between BEGIN and END. Besides that, E and N should be between BEG_G and END_G. Actually, this is the processing order — these blocks can be written down in any order, and the processing order will still be the same. Concerning N and E, their sequence of processing can be defined programmatically.

For those acquainted with awk [8], the text stream processing powerhouse, it is enlightening to know that gvpr follows a similar programming model.

The declaration and statement syntax is really similar, when not equal to C syntax [9].

In descstat.g, only BEGIN, BEG_G, N, and END_G are necessary.

Variables in descstat.g were declared in BEGIN block, their values were inicialized in BEG_G, for they should be initialized for each graph descstat.g processes. The degree of a node is obtained by the expression $.degree in block N, for in this context, $ means the current node, and degree is, of course, its corresponding degree.

The fragment for block N is copied below:

N {
    if ($.degree > maxd) {
        maxd = $.degree;
    }

    if ($.degree < mind) {
        mind = $.degree;
    }

    mean += $.degree;
    var  += $.degree * $.degree;
}

descstat.g implements the algorithm that allows the parallel calculation of the mean and the variance as linear and quadratic sums.

$G means the current graph. The mean and variance calculations are finished in END_G block, that also presents the results on screen.

Acknowledgements

Many thanks to Emden R. Gansner, gvpr author, for taking the time to read these very basic attempts at introducing gvpr to a broader audience. So, he is responsible for most of text qualities, and is not responsible for its eventual problems.

References

[1] The DOT Language

http://graphviz.org/doc/info/lang.html

Visited on 03/29/2010

[2] Graph

https://secure.wikimedia.org/wikipedia/en/wiki/Graph_theory

Visited on 03/29/2010

[3] Graphviz – Graph Visualization Software

http://graphviz.org/About.php

Visited on 03/29/2010

[4] Drawing graphs with dot

http://graphviz.org/pdf/dotguide.pdf

Visited on 03/29/2010

[5] 4.dot

http://sites.google.com/site/hgfernan/arquivos/4.dot?attredirects=0&d=1

Visited on 03/29/2010

[6] gvpr(1) – Linux man page

http://linux.die.net/man/1/gvpr

Visited on 01/29/2010

[7] descstat.g

http://sites.google.com/site/hgfernan/arquivos/descstat.g?attredirects=0&d=1

Visited on 03/29/2010

[8] AWK

https://secure.wikimedia.org/wikipedia/en/wiki/AWK

Visited on 02/02/2010

[9] C (programming language)

https://secure.wikimedia.org/wikipedia/en/wiki/C_(programming_language)

Visited on 03/29/2010

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Wireless mesh networks and graphs

Hilton Garcia Fernandes

A wireless mesh network [1] connects several access points (APs) [2] directly through radio, avoiding the need of cable connections, therefore enlarging the coverage of a wireless network to several APs, not just one.

Mesh networking is a broad concept, but it is chiefly used for local area wireless networks, or WLANs, particularly of Wi-Fi type [3].

The computers that are client of an AP without direct Interect connection can obtain that connection from another, connected AP, using the hopping mechanism: the unconnected AP sends its client information packets to the connected one. Then, the connected AP sends back the answer packets from Internet to the unconnected AP, that sends them back to its clients that demanded the connection.

Hopping can also be used to connect to the Internet clients of APs that are not neighbor of a connected AP. For instance, an AP B that has a connected neighbor C can offer this connection to a third, unconnected AP, named A, that sees the former, but not the latter. That is: a client of A sends its packets to A, that then sends them to B, using hopping. Using hopping again, B sends A client´s packets to C.

Theoretically, it is possible to use hopping to connect to the Internet APs very distant to a connected one. However, there’s a rule of thumb from field practice that states that hop counts longer than 3 are not efficient.

Wireless mesh networks can be studied using several different approaches. One of the most interesting is certainly via graph theory [4].

Graph theory is based upon simple but powerful concepts. A graph can be simply described as a set of objects that are connected pairwise. The objects are named vertices or nodes, and the connections between pairs of them are named edges

Relating graphs to mesh networks, an AP would be a node, and the connection between two APs would be an edge. Graphs that model mesh networks can be considered undirected, for if a first AP is connected to a second one, then there’s a connection from the second to the first.

A graph is connected when from any node it is possible to get to any other one, even though it becomes necessary to use several edges to get there. A tree is a graph that has the minimum number of edges to be connected [5]. In mathematical terms, if n is the vertex count of a graph, its edge count will be n – 1.

Practical mesh networks have fault tolerance as an interesting property. That means there are several different paths between an AP and another — particularly between an AP connected to the Internet and another one not connected. When one of the paths fails, there will be an alternative path. Maybe the alternative is not as fast as the original one, but even so, it will offer access to the Internet anyway.

So, a proper mesh network should have more than the minimum number of connections, in order to offer fault tolerance in at least a connection. That is: in this context, a proper mesh network that is associated with the graph mentioned before should have at least n edges. A fully connected network [6] is a network with

n*(n – 1)/2

connections, what is not feasible for networks with a large number of nodes.

A key factor for the quality of mesh networks is that the connection count be distributed as uniformly as possible. A single node shouldn’t concentrate all redundant connections — for this node will be a single point of failure for the network: if it goes down, it will take with it an important part of the network. The number of connections of a given node is called degree of the node.

The program descstat.g [7] generates basic statistics of the node degrees for a given graph — one of the most important is named coefficient of variation [8], that measures the disparity of the node degrees of the given graph. Ideally, the coefficient of variation would be zero for a mesh network where all nodes had exactly the same number of connections.

The program connect.g [9] evaluates whether a given graph is connected or not. In the context of wireless mesh networks, it defines whether all nodes see each other or not.

Both descstat.g [7] and connect.g [9] have been written using the gvpr programming environment, a powerful and flexible opensource software, very used for the visualization of graphs.

References

[1] Wireless mesh network

[2] Wireless access point

[3] Wi-Fi

[4] Graph theory

[5] Tree (graph theory)

[6] Fully-connected network

[7] descstat.g

[8] Coefficient of variation

[9] connect.g

[10] graphviz

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.