Mobile Adhoc Networking MANET Part 2

Mobile Adhoc Networking MANET Part 2

 

If we review what we have covered in the first part ,   we outlined 

- what mobile adhoc network technology is, 

- in which fields this technology is being used

- what are the requirements for adhoc routing ? 

- what are the routing protocols ?  AODV (one of the most preferred routing protocols)

We will continue talking about routing protocols. The outline of this post as follows ; 

1) Selected Routing Protocols

• Dynamic Source Routing (DSR)
• Location Aided Routing (LAR)
• Optimized Link State Routing (OLSR)  

2) Routing Dependability in Ad hoc Networks 

3) Performance Evaluation of Ad hoc Networks 

 Let's start with  what we have as  Routing Protocol except AODV . 

 1) Selected Routing Protocols

 Dynamic Source Routing (DSR)

- Very similar to AODV
-  It is a reactive protocol (on demand)
- No proactive mechanisms.
- When I want to send a packet to destination ,  I find a route. ( I do not know where the destination is, flooding happens like in AODV)


A different thing with DSR is,  each node appends its own identifier when forwarding RREQ (Request message) . Therefore RREQ grows in each hope.

  

In this figure, S wants to send a package to D but does not know the route. Therefore, it start flooding the message. First it sends it to its neighbours (B,C,E) , then it goes on like that. C sends the message to H,G  ; and B sends it to A,H (For instance in this case, H receives packet RREQ from two neighbors which might mean a potential collision). However we do not care about collision, because the network is dense  and I just would like to reach collision, even if there happens a collision most probably another node will send the message to H again, maybe A and I nodes in this case. 

As you can see in the figure, each node that receives the packet adds its own identity into the message.

 

When message packet reaches D, D knows that it is for him and stops broadcasting it. And then RREP is sent by D from the reverse path.  ( Rout reply can be sent by reversing the route in Route Request (RREQ) only if links are guaranteed to be bi-directional. IF unidirectional (asymmetric) links are allowed which means that "Ok, D knows that S sent  the message from the path S->E->F->J->D, what happens if link from F to J (F->J) is asymmetric meaning that there is no way back from J to F in which case reverse path cannot be used " *  . That's why, another route discovery from S to D is handled to find a path of which reverse path can be used in order to send the reply back . This happens of course if D does not have a route back to S. 

* It might happen when message is delivered to the destination but later on a link back is broken ( maybe destination is out of the range ) . 

Some extra mechanisms like we use in AODV can be used in order to limit broadcast in case of a re ally big network.

You might see the obvious difference between AODV and DSR from this graph above. We do not deal with tables as we do in AODV ( you need to update tables and etc) . Here, we just need to reverse the path back to the source.

After destination receives the message, it uses the path recorded in RREQ and finds out the reverse path. There is no need to store any information in the intermediary node as we do in AODV such as having tables.  Briefly the nodes between do nothing and know nothing about the route because their task it to only send the package to their neighbours.  Remember ! We are only trying to find the ROUTE ! We have not sent the real packet yet.  The "message" we were quoting was  about RREQ message. Do not confuse with RREQ message and payload (real message) .

After finding the route ;
The information about route is stored in only S and D.

 

As you can see, source specifies the route. But here is the thing about DSR.  Ok route is known, but when S sends DATA to E, E will add its own information into the DATA Message packet header, right ? Imagine this is repeated each time the data is given to the next node.  Instead of DATA[S,E,F,J,D] we will come up with IP addresses and stuff.
This will definitely cause overhead.


That's all what we need to know about DSR :)  .
To recap , we have no tables unlike AODV.  There might be some overhead as the route grows.

We have talked about Reactive Protocols (AODV and DSR) , now it is time to cover some Proactive Protocols.

Location Aided Routing (LAR)

 LAR is more detailed than AODV and DSR in this manner. It is actually designed as an extension of DSR. It has some extra features. As its name states, it gives information about location of the nodes. By this way, broadcasting can be limited.

* Location information may be obtained using GPS.

LAR defines an expected zone. I know some information about the topology, I have some idea where destination could be.  By this way, I can calculate the zone so that I do not need to waste my source by flooding message over the whole network.

Expected region is calculated based on potentially old location information and knowledge of the destination's speed.

There is also another term request zone which means a zone in that source and destination nodes exist.

Let's have a look at this graph below.

As you can imagine, when S wants to send a message to D, the nodes that will spread the message through D are restricted in the Request Zone. If a node out of the request zone such as A receives the message, it checks its zone and sees that he is not in the zone so that he will not flood that message any longer.

NOTE ! Each node has to know its physical location to determine whether it is within the request zone or not. 

 On condition that route is not found in the request zone due to miscalculation of request zone (destination node might move faster than expected) , we can always extend the request zone . 


However it could be more efficient if some nodes inform Source about estimated request zone in more accurate manner, right ? Some nodes might have more recent information and it would be better if we could make use of those information.

This newly found, discovered request zone by the help of other nodes within the zone is called "Adaptive request zone". 

! Recall that LAR is like an extension of DSR. In LAR we are keeping the track of the location of each node + we also have route information as DSR has. We can make use of route information in such a way that next discovery can be based on this previously determined route.  For instance, we might limit the broadcast or flooding by stating that new route should include at lease two-three nodes of the old one. 

Advantages of LAR 

* Reduces the scope of route request flood
* Reduces overhead of route discovery

Disadvantages of LAR

* We need more information (location of nodes)
* Another thing is that there is no way of overcoming a situation like shown below.
Let's assume that blue zone is our request zone and there is our destination in the corner of that zone (blue square) . However there is a barrier (obstacle) in front of that node depicted as red lines that does not let us reach our destination. Only solution seems to go other way around the red line which is not possible because it is out of our request node. Therefore in such cases, we might end up with some dead end.

Optimization for LAR 

Optimized Link State Routing (OLSR)  
We are able to limit flooding without physical location as mentined briefly before. If we have a known route, we might take it as a reference and create a rule from that for new discovery. We might state that route requests are propagated only along paths that are close to the previously known route.

Closeness property defined without using physical location.

Optimized Link State Routing (OLSR)   

 The name of the protocol says much about its functionality.  So far, we had protocols that are reactive, not updating routing information all the time because it is costly and network is so dynamic and so on.

OLSR is designed for different types of networks.

How does it work ?

• It floods status of its links 
• Re-broadcasts link state information received from its neighbor. 
• Keeps track of link state information received from other neighbors. 
• Uses these information to determine next hop to destinations.

Link state routing is proactive. It has all information before we need them. And local information is disseminated network wide. You are basically monitoring everything.
It is actually very similar to Standard Internet Routing. Therefore there is overhead, and the question is it  really applicable for adhoc networks ?

There must be some optimizations.  So, I will broadcast my local information to whole network, right. But while I do it in OLSR, it applies an optimized version of flooding which aims to broadcast a message only to selected neighbours. It is called multipoint relays (MPR) .  MPR is the key feature of OLSR.

How does MPR work  ?

 

A node is selected with two rules ; 

1) Any 2-hop neighbor must be covered by at least one multipoint relay.  In our example above, A's multipoint relays are node C and E in order to reach G and H.
2) The number of multipoint relays should be minimized (per node)

Core features of OLSR 

Link sensing : By sending Hello messages to the neighbors, we can learn about our neighbourhood.

MPR selection : We can add some info into Hello messages, and we can calculate 2 hops neighbors.

Link State Messages : If we have an updated link information about something, and if others need to know it we just relay this information.

 

Conclusion for OLSR  

 Ok so, it seems a bit complicated, a lot of overhead. But it is well suited for some networks ( Large, Dense networks ) . Because, If have many neighbours  and prefer to use AODV, I have to send them all my messages which means a lot of overhead.
However in OLSR, I select two or three multipoint relays and can reach all of my neighbors. Briefly for Large and Dense network networks it is feasible and makes sense to use OLSR .

Moreover, OLSR has low latency. Because we have a routing table. When I want to send a packet, I check my table and just send it. Compared to that, AODV has to discover route when needed , reply back and stuff.  OLSR has that information on hand.

2) Routing Dependability in Ad hoc Networks

• The effects of node misbehavior.
• Modelling adhoc networks.

 There might be cases that the protocols that we have discussed cannot help out. For instance what if there are some nodes that do not want to cooperate ? or some other problems related proximity to each other. Some might behave as malicious and etc.

Recall that in ad hoc networks, there is mobility, dynamic situations.
In this part, our concern is Routing system. 

Routing protocols need to find out whom to communicate , which path to choose.
How can we characterize routing system shown as a box in the graph above ? This is what we will outline now.

We also need to define what Routing Dependability is. It is trustworthiness of a routing system.

 Node Misbehavior

A node in the middle may keep the message and not forward to package. It can affect the overall performance of the system. There are three different nodes.

Well-behaving nodes : that works, forwards the packet.
Malicious nodes :  the ones that inject false information into messages or remove them completely from the network ( black holes) .

It has been proven that if the number of selfish nodes increases, the packet loss in the network increases linearly as well.

Besides that, in case of AODV, if there are many selfish nodes in the network we need to incerase the number of control messages ( to keep the track of what is going on in the network , and reestablish route if a node does not forward the packet ) . It results in increase of routing overhead. 
Selfish nodes:  the ones that receives the packet but do not forward it .

How to measure dependability ?
There are many metrics for this purpose such as sent packets (bytes) , Lost packets (Bytes) , mean end to end delay , mean path length, maximum path length, total # of RREQ, RREP, RERR .  The metrics you would select are totally up to what routing protocol you choose.

Routing Dependability Problems 

• Most ad hoc routing algorithms assume only well-behaving nodes to support multi-hop operation of the network. However if something goes wrong in between, everything can be affected in a negative way. 

Underlying Problems ;
- Induced by mobility : High topology dynamics
- Induced by wireless communication
- Induced by node misbehavior ( we might want to add some extra mechanisms to overcome this)

3) Performance Evaluation of Ad hoc Networks

Basic Terms

• Performance Analysis = Analysis + Computer Systems
• System  = any collection of hardware + software
• Metrics = the criteria used to evaluate the system performance
• Workloads = the requests made by the users of the system

You need to know what you want to characterize in your system. You need to have a proper goal first. There is no such thing as general model.

Goals -> correct metrics, workloads, methodology.
Your performance evaluation should represent the actual usage of the system.

How to analyze (Mobile Ad hoc ) networks ? 

Challenge : Qualify and quantify the effects of 
node misbehavior on the overall performance of the routing system.

We would like to see how the system behaves.

What about choice of evaluation technique ?
- Real world observations are not possible because there is no large scale MANET, and it would be expensive to set up a new one.
- Emulation / Testbed experiments are possible but in a small scale.
- Simulation studies are being conducted.
Compared to real world observations, we can play with the settings of input and output values in emulation, simulation experiments.  I can define input, predict output. Workload would be input and calculations could be output.
 Below you can see the result of an experiment.

Challenges in Ad hoc Networks 

• Security, 
• QoS, 
• Scalability, 
• Heterogeneity, 
• Adaptation, 
• Dependability.

It is for sure that there are many issues need to be handled if an optimized ad hoc network needs to be implemented which does not seem possible with today's technology.

For instance what if after 2 hops away the speed is decreasing while it is pretty fast in the nodes close to the source  ? Should I buffer it ? or what ? I need some flow control mechanisms to deal with these kind of problems.  Another problem would be priority ? which packet is important , my packet or neighbours' ?  A lot of research is being done on these issues.

What about security ? What if there is DoS attacks ? Some malicious nodes can use a specific node just to kill its battery. How can we overcome it ? or malicious nodes can temper messages , who can prevent it and how ? 

  Smart antennas might change the future of ad hoc networks. 

Summary

MANET :
Self organizing, mobile and wireless nodes
Absence of infrastructure, multi-hop routing necessary
System are both terminals ( end systems ) and routers (nodes)


Routing is a main problem in ad hoc networks

• Topology based, destination based, hierarchical, geographical, cluster-based, etc. strategies,
• Proactive, reactive, hybrid, etc. protocols. 
• Problems persist: QoS, Security, Scalability, Heterogeneity, ...

Resources : The content of this post has been generated from the slides of the presentation that was given by Matthias Hollick in UIO in 2007.

Mobile Adhoc Networking MANET Part 1

We will outline Mobile Ad hoc Network technology in this post. 

Content of this post is as follows ;

1) Introduction and Motivation
2) How is Routing in Mobile Adhoc Networks
3) Selected Routing Protocols (1)
* Ad hoc on-demand distance vector routing protocol ( AODV ) 

1) Introduction and Motivation

 

Let's first talk about wired and wireless networks 

 These aspects are explained pretty well by Julien Thomas. Let's see his explaination.

During the past years, wireless networks have widespread due to new technologies such as BlueTooth [IEEE 802.15] and WiFi [IEEE 802.11]. Contrary to wired networks, these networks do not rely on physical links. They can thus provide new services, such as easy access to the Internet (using hotspots^1.1) or access to private networks (domestic or professional) without having to install cables. However, this mean of communication calls into question several assimilated notions in wired networks. For instance, as anybody can try to access to the network or to eavesdrop communications, access management have to be reconsidered. Moreover, some wireless networks do not rely on a logic infrastructure, which complicates the problem, for instance for the services management, as presented in the next section. 
http://master.julienthomas.eu/rapports/html/rapport-node8.html ////

Differences between several wireless networks

Due to the fact that they are used to provide high level services, such as Internet connexions, the most widespread wireless networks are those relying on an infrastructure. As their names suggest, these networks are built in a logic way, respecting a stable infrastructure, in particular for the routing management. Thus, all the administration functions are managed by an Internet Service Provider (ISP), which provides a simple and reliable service.

The wireless networks without infrastructure are auto-built networks. These networks (called MANET ^1.2, Mobile Ad hoc NETwork) rely on network's nodes to satisfy all the network functioning's needs, in particular the routing politics. The network management is thus dynamic and dependent on its nodes. These networks offer new services, such as easy and fast deployment of systems, without having to envisage an administration structure (the deployment of a communicating captors network is an example of such systems). However, the lack of infrastructure leads to weakness, which can be for example exploited to limit the network availability (see section http://master.julienthomas.eu/rapports/html/rapport-node8.html ////

Wiki says : A mobile ad-hoc network (MANET) is a self-configuring infrastructureless network of mobile devices connected by wireless links. ad hoc is Latin and means "for this purpose".^[1][2]
 

 

http://www.ece.iupui.edu/~dskim/manet/images/adhocnet.gif

All of the devices in the picture above work as a router that directs the traffic to another if it does not need that packet.

Basics

• Principle is to create a communication without any infrastructure . 
• Devices can communicate with each other using short range communication. 
•  Multihop routing is necessary. 
•  Spontaneous networks can be supported by Ad hoc networks
• Self-organizing, mobile and wireless nodes.
• Systems are both terminals (end systems) and routers (nodes)

There are of course some problems, challenges in Ad hoc networks such as dynamics, energy, bandwidth, link asymmetry. We will outline them later in this blog.

Characteristics 

- Dominated by heterogeneity and variability.
- Different routing behaviors of different devices.
- Mobility characteristics ( Speed, predictability ) , Wireless characteristics( limited  range, transmission errors) , application characteristics (P2P , real time) , system characteristics (distribution, absence of infrastructure)  all of them have some effects.
Note : Adaptation is crucial. 

For instance,
I would like to send a message to a mobile device by using adhoc network, however how can I use his IP ? because IP has no topological meaning in this concept,  he moves around so his IP changes all the time ?  This is one of the biggest problems to overcome in adhoc networks.

Some Ad-hoc Applications

- Military applications ( soldiers, tanks , planes ... )
- Civilian applications ( car to car communication, emergency services, sensor networks, ... )

Let's give an example related to home networking;
We do not want to deal with cables at home, right :) generally it is a big mess. Speaker has  a cable to the TV , DVD player has another and so on. Instead of these cables, would not it be great if they communicate with each other without cables ?

Another example can be a system that warns you before something happens. For instance, a system that stops your car before hitting the car in front of it .

Peer to Peer vs AdHoc ?  

People mix these terms . They are similar but not same .
First of all Adhoc network focuses on network layer while P2P focuses on app layer.

P2P networks replicate data and data is distributed widely. It may not be the case in Adhoc networks. 

What about Mesh network ? 

We can say that Mesh network includes both sensor networks and ad hoc networks.

Characteristics ;
- Multihop communication to reach destinations.
- Self-forming , self-healing, self-organizing
- Weak mobility and power constraits.
Compared to Adhoc networks ;
- There is wireless infrastructure
- They enable easy integration of different radio technologies.
- Additional capabilities ;  sophisticated algorithms can be applied.

 

About Ad hoc Routing - 

Why do we need a specialized ad hoc routing ?

1. To deal with topology dynamics caused by mobility
2. To reach nodes that have no direct neighbours. 
3. To match characteristics of wireless communication.
4. To support spontaneous formation of network
5. To operate without fixed infrastructure
6. Because all end systems are also acting as routers 

 What do you think the answer of this question ? which ones would you pick ?

Actually the correct answer is "there is no incorrect option". All of them are the reasons why we need a specialized ad hoc routing.  There are some protocols to meet these requirements. 

Requirements for Ad hoc routing 

The routing protocol needs to deal with these dynamics.
- The routing protocol needs to converge fast !
- It has to minimize signaling overhead.

The routing strategy ( algorithm ) may include ;
- Shortest distance
- Minimum delay
- Minimum loss
- Minimum congestion ( load - balancing )
- Minimal interference
- Maximal signal strength
- Minimum energy (power aware routing )


! Standard Internet routing cannot fulfill these requirements !
- Because Standard Internet routing assumes there is an  infrastructure, symmetrical conditions and  plenty of resources.  ( We have to have more dynamic systems  not Standard Internet routing)


So what can we do ? let's have a look at other routing protocols .

1.  Flooding of Data packets :   A simple solution , but  results in high overhead. Some sensor network application only use flooding. It reaches the destination if there is no disconnection of nodes. There might be some situations that I do not need to do flooding. 
2. Uniform routing protocols :  Each node shares the same responsibility. Each packet has a direct path to the destination. Uniform routing protocol has two paradigms; Proactive (table-driven) and reactive (on-demand) paradigms.  Proactive protocols try to maintain routes all the time. It keeps the track of routes and when the topology happens to change, we already know the  route .    Reactive protocols look for a new route on demand, route discovery is handled on demand. For example, I want to send a package to a neighbour , but I do not know the route. Then I ask the route and see the topology.  Because it looks for the route on demand, there is less overhead compared to proactive protocols.
3. Non-Uniform Protocols. In this protocol, nodes in the network have different tasks to do. While some of them deal with routing management, others might deal with something else.

Note that "There is no protocol for adhoc routing that we can say yes it is the best one to use" .  

 There are many routing protocols. The picture below is just a small part of the whole picture actually.  

There are some much details of these protocols. Each protocol might have a special feature, or operation. If you would like to go into particulars of these protocols, you can find many documentation related to them. However we will only outline some of them in our post.   You may want to check this out for further info; http://en.wikipedia.org/wiki/List_of_ad_hoc_routing_protocols


Based on your needs, you might want to select a specific protocol considering its features.

Selected Routing Protocols (generally  Preferred ones ) 

1) AODV
2) DSR/OLSR/LAR (these have things in common with AODV, that's why we will not cover them in this post)


AODV ( Ad hoc On-demand distance vector protocol )
- Reactive protocol ( on demand )
-  All nodes are treated equally.  ( they share similar responsibilities )
-  Based on distance vector principle  ( I have information about my neighbors and network topology , and I share it among  my neighbors ) so that I have a distance vector to the destination. 
- We have a route discovery cycle in AODV. We first flood-broadcast the route request thorough the network, then destination gets it. And destination replies back with the information available in the nodes' tables.

- Basic principle in AODV is to use 3 messages.
- There is no overhead on data packets.


Status :  Many implementations are available (IPv4, IPv6 )  

Each request has a sequence number, so if a node takes multiple requests coming from same source for same destination then it means it is a duplicate message which will be discarded.  So first routing request is forwarded and others are discarded.

http://www.cse.wustl.edu/~jain/cis788-99/ftp/adhoc_routing/fig4.gif

Let's assume that, Node 1 tries to send a message to the destination 8. Node 1 first sends the request to its neighbours, and its neighbours do so and so on until a route/ some routes are found. Figure a depicts this propagation of Route Request (RREQ) packet . Later, destination replies back from the path which was calculated to be the fast path, the efficient one. In this case, path taken by the Route Reply Packet (RREP) is 8->6->4->1 .

Route Maintenance in AODV 

AODV uses 2 timeouts to keep the route alive ;  one for forward path, one for reverse path. Timeout should be long enough to allow RREP to come back. Otherwise, it might be unfortunate to assume that existing route has disappeared or broken.  ( Default value for time out is 6 seconds ) 

Flooding is used. Because we have no information about the topology, what is the shortest path and so on.  First, I need to search what is going on in the network. Using flooding makes sense for this concept. It can be of course optimized.  However you need to have some extra information for optimization. Briefly we have to use flooding to get to the destination.


It also uses destination sequence numbers to determine fresh routes. By doing so, it can avoid using old/broken routes and prevent formation of loops .

From Matthias Hollick's presentation that he gave in UIO.

You can understand what actions taken in case of a route error. I would like to explain one more time how sequence number works. Defined route has a sequence number (lets say 6 links to go for destination ) , if an error detected, system tries to find >6 (because 6 was the shortest path , and now it tries find another short path  ) .

Note :AODV does not find shortest path in terms of distance , it finds the shortest path in terms of time meaning fastest path. 

From Matthias Hollick's presentation that he gave in UIO.

For instance the graph above,  we plan to reach from source 2 to destination 13 . Green path is taken as the fastest path, while dashed red line was the shortest path in terms of distance. However as you can see, even though the green line (2->20->22-> and so on) is our route,  we also propagate request message in irrelevant part of the graph as well. Red arc includes the unnecessary routes.

So what to do in order to get read of unnecessary messages ?

There are some algorithms for this purpose.
- AODV -LR Local repair .
- AODV - ESP Expanding Ring Search.  ( you do not flood the message through the network if you set time to live as 1 hope , so that it only checks one hope away neighbors )


IF you have a wide - dense network , AODV will fail . Because it is based on broadcasting mechanism , right ;) .

However there are multiple open issues in AODV such as Security , QoS.
These issues are being studied currently.

AODV optimizations - Gossiping (1) 

- We said that that flooding is inefficient if the network is dense.
Gossiping is one of the mechanisms to deal with density.  Gossiping randomly selects subsets of neighbors to send the message. 

AODV Extension - Multipath (2) 

- Instead of dropping duplicate RREQ packets, AODVM uses RREQ table to store all RREQ information in order to have alternative ways of sending the reply back. If the nodes on the way back are mobile , or they fail whatever , why not use multipath.




Resources : The content of this post has been generated from the slides of the presentation that was given by Matthias Hollick in UIO in 2006.

RealTime Multimedia in Presence of Firewalls and Network Address Translation

Our purpose in this blog is to understand how RealTime Multimedia technologies work under the limitations caused by Firewalls and NAT devices. To give an example, you would like to connect to your laptop (which is in another network, using another rooter)  by your smartphone to send something.  However the firewall of your laptop blocks all the connections coming from the network where your smartphone is in. Assume that this kind of problem is occurred in real time applications such as that you would like to be able to be called anytime regardless of what infrastructure you are behind while you are outside home and changing your position so fast.  Therefore the application you and the ones you are interacting with needs to adapt itself somehow and overcome the limitations of firewall and NAT devices so that no package is dropped and quality of the conversation or service could stay as planned.

First of all, for introduction, let's recall the terms we need to know to cover this topic.

 

What is Firewall  ? 

 

I can basically say that firewall is a wall that protects your computer's ports ( they say that a hacker can reach thousands of ports in your computer )  so that it is defined what kind of connections would be possible through your network.

http://static.ddmcdn.com/gif/firewall.gif

I will not go into particulars but for the ones who want to know more about firewall can check this blog ; http://howto-hsk.blogspot.com/2012/03/what-is-firewall.html

But briefly guys, do not destroy your firewall !  we do not want to mess up with hackers :)


Basically  Firewall ;
 - Blocks all incoming traffic except established connections.
 * All communication must be initiated from inside.
 - Might block certain protocols
 *Some vendors consider UDP dangerous.
 - It keeps the track of established communication in a table located in NAT device.
* For TCP connections it is possible to take them into consideration as ESTABLISHED because TCP is a connection based protocol while UDP is connectionless meaning that UDP communication paths are considered as ESTABLISHED only if it has been responded to .

What is NAT  ( Network Address Translation )  ? 

Cisco says that : Network Address Translation allows a single device, such as a router, to act as agent between the Internet (or ""public network"") and a local (or ""private"") network. 



Imagine that there are lots of computers, devices conected to Internet behind FIREWALL . By NAT device, let's say located on the firewall ;   these devices use only one shared, public  IP address to reach outside.  As far as I know using NAT devices was introduced because of lack  of IPv4 adresses so that many devices could use one public IP adress for ouside the firewall. I believe that most of you have a NAT router in your home. When you use your laptop + smartphone + desktop at home, this is what is going on in your router.


NAT is divided into two groups; Source NAT and Destination NAT.

Source NAT :  When you initaite a connection from inside, destination hosts out of yor firewall will see some public IPs assigned by Source NAT.
- Only receiver can detect a sender's port.
* May vary between destination hosts.  ( when you communicate with a destination host you get an IP address,  while for another destination host you end up with another IP address) .

Destination NAT:  When you have a service that you want to allow outside world to benefit from your service which is behind a firewall, you need to tell NAT to map a port with this service so that people on the other side of the wall can access this service.



It should be stated that, firewall and NAT devices are in the same box meaning that they are related to each other in many aspects.

What do we mean by Real Time Multimedia ? 

We mean a system that can work real time (e.g  people can call you any time when you are out )  irrespective of behind what network infrastructure you are.

If you want a better definition here it is :
Definition: Real-time multimedia refers to applications in which multimedia data has to be delivered and rendered in real time; it can be broadly classified into interactive multimedia and streaming media. http://encyclopedia.jrank.org/articles/pages/6877/Real-Time-Multimedia.html

 

However,  Firewalls and NAT devices cause some problems in this aspect .
Thus, I will try to explain what those problems are and what are the mechanisms being developed to overcome those problems .

When to talk about Real time multimedia you might imagine the services below ;

Types of services : Unified communications
- Voice
- Video
- Chat / presence
- Application sharing

Unified communications have some characteristics such as ;
- Real time properties needed
- We tend to find shortest / best path for media because we do not want to face with delay and jitter.

 * Delay  : Delay is basically latency in the communication. When you say something in Skype ,  your girlfriend hears it 10 seconds after when you actually say it . It might cause some problems :P .

 * Jitter : Jitter is the amount of variation in latency/response time, in milliseconds.
 Let's give an example for this ;  let's assume that you are expecting your girlfriend to meet you everyday  to have a dinner together at 7:30.  However the time your gf shows up is not stable meaning that she sometimes shows up around 9:oo  sometimes 5:59 ( waits for you and then gives up and leaves :P I do not what kind of girlfriend does that)    what would you do in this case ?
The point here is that this situation of variation in meeting time of your girlfriend will result in some decrease of the quality of your relationship for sure .


I believe you got my point :)  You might adapt this scenario for Skype . If the jitter is low, then the quality of your realtime voice communication will be better ;)

So what about firewalls ? Let's talk about it by giving some examples . 

Given that I would like to call my gf by Skype and she has a firewall that does not allow my network to reach through hers . What happens in this case is that she will not even be able to know that I made a call because the package has been dropped by her firewall.

And assuming I have no firewall, if she makes the call ( she knows my port and IP no) the call works fine because I can use the same link - connection that she opened to call me.

However what happens if we both have firewall ? This is where 3rd party application comes into the picture.  This can be a registrar that registers the parts' IP and port number stating to others that "you can reach this registered guy by using this port and IP ".   For instance,  in order for me and my girlfriend to communicate, we both need to use registrar because we have firewalls that do not let us have a direct communication, right ?   By using registrar ,  I register myself in registrar's database with my IP and port, so my gf does.   By this way, Registrar works as a relay service letting us communicate without a problem  .

You might ask,  why do we need to use registrar while my firewall somehow could be able show them to my girlfriend's firewall ?   In this scenario , it simply does not work. Because the IP address and port number that registrar registers are probably seen only by register while in case that her firewall tries to access these port and IP directly ( NAT device might translate them into different numbers for outside of my network) ,  and they might simply be shown with different IP and port numbers to my gf's firewall.

So what is the connection of Firewalls and NAT devices with Multimedia ?

To recap;

- Firewall/NAT devices interfere and block communications.
* Cannot send packets to a private address from Internet.
* Firewalls only accept outbound communications initiated from inside.
* NAT : packets from the same port may be seen with different src by different hosts.



What about multimedia ?
 - Most protocols for realtime multimedia
* uses multiple ports for a single application.  ( 1 port for audio + 1 port for video and so on )
* Most protocols have not been designed for NAT devices. They can send IP+port numbers in the payload. (Upps this is no good) The schema breaks down in NAT devices meaning that NAT violates the system. 

We will be talking about TCP/UDP protocols, so we had better have a review of them at this point. 

http://www.it20.info/misc/pictures/TCP-clouds-UDP-clouds-design-for-fail-and-AWS1.jpg

IF we imagine that we use TCP for a video conference, it is basically no good because sequence is important in TCP , assume that packet 1, packet 2 is received by your device while sender somehow could not send the packet 3 ( router-switch might decide to drop it because of too much traffic) then incoming messages will be hold in receiver's stack without sending them to the device in order to keep everything in order because as we stated the order of messages is important meaning in our scenario that, packet 4-5-6 and so on cannot be sent before the receiver takes packet 3 . After the sender is able to send packet 3 , the receiver stack will know that now the order is ok ( from packet 3 till last packet )  , and then the whole message packets will be delivered once. It means that the interval of receiving packets by the receiver  is ruined. And this means jitter which we cannot tolerate in real-time apps.

Thats why we prefer UDP over TCP for media transfering, although we might lose some packets in UDP. IF we have to use TCP for some reason in some hopes, then for the rest of the hops, UDP should be prefered.

Note: I will talk about UDP and TCP comprehensively in my future posts.

Mechanisms to enable realtime multimedia services work well in presence of firewalls and NAT devices. 

They are actually to detect and handle Firewalls and NAT devices.

 

1) STUN ( Simple Traversal Utilities for NAT) 

2) TURN (Traversal Using Relays around NAT )

3) (N)ICE ( Interactive Connectivity Establishment ) 

4) Tunneling

5) Modifying / involving the firewall. 

4 and 5th solutions are generally not possible to apply .  We cannot ask a company to access its firewall configurations, right ? :) we can, but the answer will be "No" unless you are working for that company as a network admin or something .


Before we outline these protocols, let's first talk about typical Firewall / NAT configurations. These might be the cases on the firewall.

1. All TCP/UDP allowed + NAT is used on the firewall
2. All TCP allowed but UDP is only allowed from add:port that was sent to- and No NAT
3. All TCP allowed from inside
4. All UDP / TCP blocked
5. All direct access to outside is forbidden. (internet access is available by web proxy ) 

 It might also be beneficial to talk about the categorization of NAT devices. They are three categories.

1. Endpoint independent mapping ( the most open one )  meaning that when you as a source start a connection with a destination host,  this connection can be reused by other destination hosts.
2. Address dependent mapping meaning that when you have a connection with a destination host, because it is only address dependent, the ports on that host can use the available connection. 
3. Address and port dependent mapping  is as its name shows that a connection between source and destination host is unique ( source address port + dest. address port)  , by this way no other host or  ports in the same host can reuse this connection.

1) STUN ( Simple Traversal Utilities for NAT)  

* Client/Server based protocol.
* Designed to allow detection of firewall / NAT properties
(detects If we can have the connection directly or if we need to have a 3rd parties)
* What properties NAT has , discover public addresses assigned to address on the private network
* Discover if the public address seen by one destination host/port can be used another host.


Thanks to STUN servers, each part knows the public IP and port of each other. The devices behind the firewall use STUN servers to figure out these public IP and PORT. No translation of addresses are done in STUN servers. 

 What happens if STUN server fails ? 

For instance my firewall-NAT might block all UDP for some specific purposes let's say.  In this case STUN server fails and tries to communicate with my device through TCP.  It succeeds because my NAT device accepts TCP connections. After communicating via TCP ,  STUN server then keeps communicating with the destination host via UDP ( because the connection is already established and UDP has less links compared to the links that are supposed to be created for TCP) .


However in this case of using TCP as alternative for UDP , we might have many problems due to TCP such as packet loss or some distortion in sound or video. Because TCP when packet gets dropped, TCP retransmits it and we come up with delay and jitter that we dont want to have in real time apps .

2) TURN (Traversal Using Relays around NAT ) 

 * Let's say that my device behind the firewall asks a TURN server to give a public port.  Then the server directs all to traffic by this port to my device.  However this wastes twice more bandwith because imagine that there are two devices and a STUN server in the middle.  1 traffic is caused by while sending something to the Server by another device , and 2nd traffic happens when the server directs this traffic to my device.

Of course it is much better always if direct communication is possilbe. But in case it is not possible, TURN is one of the solutions.

With TURN, UDP and TCP communication is possible .


In this point, before we go through the remaining part of the mechanisms, let's talk a little bit about the differences between guaranteed delivery and real time applications.

Guaranteed delivery is something we face with when you download something (like mp3, or media). In this case , we do not care about latency that much. What we care is only the completion of download, right ?

What about a video conference ? or a call from your family by skype ? Can you show some tolerance to jitter or delay ?
Answer should be "NO" , because even a slight jiiter, burst or delay in sound packages, it might distort the conversation meaning that parts may not understand each other.

3) (N)ICE ( Interactive Connectivity Establishment )

It is another recent alternative protocol for exchanging channels  for communication.
It uses STUN, TURN and other technologies under the hood. 
It basically gathers as many addresses/ports pairs as possible for the parts that want to communicate with each other . This pairs are kept in a prioritized  order so that sender and receiver can try these ports and addresses until the communication is set up. 

Thanks to ICE, we can avoid a situation in which one part thinks that other part sees him ( video conference ) but actually there is no stream taken in other part.  ICE deals with this kind of similar miscommunication problems. 


- End to end protocol between clients
- Servers are not direclty involved ( but Turn and Stun servers can be used when needed) 

4) Tunneling (RealTunnel)

Client on the local network (let's assume we have a mobile phone) finds network connectivity by the help of STUN and some more.  This application, RealTunnel, works together with RealTunnelServers located in different geographical locations to find available transport mechanism for the peers in a call.

RealTunnel is a product that can be used when everything else is failed .

5) Modifying / involving the firewall. ( Control the FIREWALL) 

Actually we all are familiar with modifying our firewalls from the case when we would like to play some games ( after installation you are asked to change your firewall settings to enable the application to do some stuff, right ? )  . However we know that for game players, there is no more important thing than just starting to play the game which can be a big mistake.  It might have its the consequences ;)

Doing such operations are not allowed in corporate network.

Another way of modifying the firewall is for voice and video which is for example to use a Session Border Controller. Session Border Controller bypasses the firewall so that actually Session Border Controller works as a firewall, it handles some protocols that it already knows.

Session Border Controller is an  Application level gateway which will mask the fact that  there are different addresses inside and outside by converting all the payload.


About Application Level Gateways ; Check wiki for more info about Session Border Controller
Wiki says : " It allows customized NAT traversal filters to be plugged into the gateway to support address and port translation for certain application layer "control/data" protocols such as FTP, BitTorrent, SIP, RTSP, file transfer in IM applications etc. In order for these protocols to work through NAT or a firewall, either the application has to know about an address/port number combination that allows incoming packets, or the NAT has to monitor the control traffic and open up port mappings (firewall pinhole) dynamically as required."


However Application Level Gateways ;
* Gateways interfere at application level. it means it breaks firewall principle .  Each time the high level protocol changes,  application level  also needs to adapt to new conditions.  It is not always possible to change encrypted data. In some scenarios app. level gateway solution might not be good .


Some protocols having difficulties with NAT and FIREWALLS

1. SIP (Session Initiation Protocol) is the preferred protocol for VoIP   = The protocol can be used for creating, modifying and terminating two-party (unicast) or multiparty (multicast) sessions. Sessions may consist of one or several media streams. (WIKI SAYS so )  TURN , STUN, ICE protocols are made by SIP community.
2.  H323 and FIREWALL/NAT =  Old fashioned protocol that has similar functionalities with SIP .
3. OSCAR- AIM, ICQ- and FIREWALL / NAT = Supports most types of firewalls and NATs.   Has similar mechanisms as used for SIP
4. Skype and Firewall/NAT =  Developed for KAZAA . Skype is encrypted (we do not know how it works )  It uses your connection to relay others' calls meaning that they use your bandwidth.   When it crashed once in 2007, it was thought to be due to the reason that people (users) had used firewalls and relaying was not that possible in that condition. 
5. MSNP (MSN) will be replaced by Skype !  :Microsoft bought Skype ! 
6. XMPP
7. IPsec is also subject to this problem .  Encyrpted VPN solutions use IPsec . IPsec uses AH ( Authentication Protocol) which is an additional header that authenticates the information in the IP header. Ensures that packet header information is not changed by firewall or any other mechanisms . However it is the whole deal of NAT :)    and IPsec uses ESP (Encapsulating Security Payload protocol) that encapsulates and encrypts a checksum of the IP payload meaning that port modifications are not possible (because port numbers are in the payload) so if someone tries to modify it , the package gets dropped.

What about IPv6 and FIREWALL / NAT
- Do you think will we need NAT in IPv6  ? Because the reason why we use NAT is we have few IP addresses.  Therefore we will not need NAT in this sense.

However we can make use of NAT for ;

*  Security measure : Topology hiding to prevent host counting by attackers.
* Backward compatibility
-  If you have large private network with one million devices with static IP addresses , when changing Internet provider,  you dont to modify those 1 million machines. Briefly we will most probably need NAT devices.

To SUM UP ! (Finally :)

There are still no specific standard to support all these scenarios .

However discovery and traversal tools can help find the best path !
STUN, TURN, ICE. 

Basically , when to ends want to communicate and if they have firewalls blocks them to communicate directly , a third party mechanism such as registrar is needed for registration.  After that , they will know what port and IP to use for direct communication if possible.

Same problems will most probably occur in IPv6.






PS: Almost all of the content of this post has been utilized from the presentation that was given by Knut OMANG in University of Oslo.

What is a "Distributed System" ?

A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal. A computer program that runs in a distributed system is called a distributed program, and distributed programming is the process of writing such programs. ( WIKI definition )

http://www.python.org/files/success/devil/devil-nettree.png

 

In this blog, I will try to explain you guys, what are the terms that you are supposed to be familiar with, and what are the topics being studied under DISTRIBUTED SYSTEMS technology. 

I hope, it is going to be beneficial . 

Please join this journey with me ;) 

Some useful terms - before going into particulars

Some useful terms before going into details of Distributed Systems


Replication is the process of sharing information so as to ensure consistency between redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, or accessibility. It could be data replication if the same data is stored on multiple storage devices, or computation replication if the same computing task is executed many times. A computational task is typically replicated in space, i.e. executed on separate devices, or it could be replicated in time, if it is executed repeatedly on a single device. (WIKI)

* Replicating user's data in different servers minimizes inter-server traffic for reads, but increases replication overhead !
(This has a negative impact on ;

•  query execution times
•  network traffic for updates and 
• maintaining consistency across replicas.

 Stateless application : is kind of an application that does not remember the user's previous actions. Eg: WorldWideWeb . However making the application remember previous actions of user is pretty useful . That's why, some extra mechanisms are being developed to remember configuration settings such as enabling cookies in HTTP protocol.



Scalability :  A popular buzzword that refers to how well a hardware or software system can adapt to increased demands. For example, a scalable network system would be one that can start with just a few nodes but can easily expand to thousands of nodes. Scalability can be a very important feature because it means that you can invest in a system with confidence you won't outgrow it.  (http://www.webopedia.com/TERM/S/scalable.html)

Scaling ? There are two definitions for making a system scalable.

1) Vertical Scaling = Eg. adding more partitions - upgrading existing hardware. (Facebook scales its system across thousands of machines) * Vertical Scaling is generally too expensive!


2) Horizontal Scaling = It is a more cost effective approach. (Eg. adding more commodity servers into the system so that the workload can be shared among them ) *Thanks to the developments in Cloud computing, now it is easier to reinforce your system by removing the need to your own hardware and adding more VMs from the cloud. * Application front end is stateless which is a plus because the application can be started on new servers on demand. On the other hand, application back end keeps state which is a minus ( this is related to partition of data, if data is partitioned into separated divisions, horizontal scaling still exists
 /This disadvantage of keeping state in backend might be explained comprehensively ! Please send me an email if you have a good example /


To be continued ...

What is Bloom filter ?

 

 

-----------------------------

 Hashing ? and Inconsistent Hashing ?

1. 1. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 

   2. pages.cs.wisc.edu/~akella/CS740/S07/notes/lect14.ppt

   
   

 

---------------------------------

 Attacks that we always hear about 

Sybil Attacks : 

The Sybil attack in computer security is an attack wherein a reputation system (like e-bay)  is subverted by forging identities in peer-to-peer networks.



-------------------------------------------------

What is dirty bit?

Sometimes CPU modifies a bit but does not write it back to the storage. In this case, that modified bit is called Dirty Bit. This bit is located in a cache or virtual storage.



--------------------------------------------

References : The Little Engine(s) That Could: Scaling Online Social Networks Josep M. Pujol, Vijay Erramilli, Georgos Siganos, Xiaoyuan Yang Nikos Laoutaris, Parminder Chhabra, Pablo Rodriguez Telefonica Research { jmps, vijay, georgos, yxiao, nikos, pchhabra, pablorr }@tid.es