Review: RFC 4984 - Report from the IAB Workshop on Routing and Addressing

This document is a report on the proceedings of the workshop on Routing and addressing held in 2006. It points on major limitations of today's internet (IPv4 and IPv6) and the features to keep in mind when redesigning tomorrow's internet.

The following paragraph presents a brief summery of the major problems:

The Scalability of the Routing System: the growth of the routing tables (Routing Information Base (RIB)) results from adding more address prefixes in the table. This growth is due to the natural growth of the internet and the de-aggregation of address prefixes. This de-aggregation is caused mainly by multihoming and traffic engineering.

Multihoming is when a host is served with more than one Internet Service Provider (ISP). This provides a host usually running critical applications more reliance. In case of failure of the primary ISP, the host can switch to another ISP. This solution avoids the single point of failure and allows the host to continue serving its clients.
Consider a network C with a prefix from an Internet Provider P1. When C multihomes with a second provider P2 then both P1 and P2 should announce globally that C can be reached from P1 and P2. This causes prefix de-aggregation since it is not provided by P2. So P2 updates its RIB with the prefix of C provided by P1. P2 informs C prefix globally this means that other routers will update their RIB too.
This operation causes the growth of RIB tables by adding additional de-aggregated prefix entries.

Traffic engineering: is used for load balancing, it allows packets to use or avoid network paths. When a path is overloaded traffic engineering allows routers to deliver packets using another paths. This operation causes to add more de-aggregated prefixes to the routing tables. Sometimes it is used for political reasons. The traffic of one government is not allowed to transit through routers of an other government.

Large numbers of mobile networks: with the increasing number of mobile devices, users can now access internet from almost anywhere even on planes as Boieng announced. Today each mobile network can be announced by a prefix, actual routers handles several thousands of mobile networks prefixes.
There is an open question regarding the impact of global routing if the number of such networks increases (e.g. on planes, trains, ships).

Mobile hosts: Billions of gadgets, sensors can become online in the next several years. The current solutions use home agents, so from routing perspective it is considered like stationary hosts.
However if another solution was proposed with a clear separation between identity-location than there might be some impact. This is why further investigation is needed.

The overloading of IP address semantics: IP address is used as an identifier and a locater while we should split the identity from location. When a host moves its position, its identity remains the same while its location changes.
In the multihoming example, a prefix is used to locate and identify a network.
Though an IP address must be used only to locate a host based on network topology.

IPv6: It is believed that IPv4 address space (32 bits) restrained the growth of the RIB tables. The deployment of IPv6 with a larger address space (128 bits) might cause the growth of RIB tables by a factor of 4.

Hardware limitations: the growth of RIB tables increases the need to build more powerful routers to handle this growth. However the costs of silicon is dominated by the actual fabrication hosts. The silicon used in core routers is produced in low volume (1.000 - 10.000) unit per year while the microprocessors volume is in millions per year. This places the router silicon under the cost curve.
The increase in bandwidth forced router manufacturers to increase
silicon technology but now the hardware is near to its limits. This means that the hardware will not keep up with the increase of bandwidth.
In routers, DRAM is used for storing the routing table entries, the DRAM access speed must grows faster to keep up with the extension of the RIB entries.
More entries means more access speed to maintain a certain level of performance.
There is also the Heat and Power Factor actually transistors consume power even when it is Idle. The smaller and hotter the transistors, the larger the current, so powerful routers need cooling technology and at present the air cooling is starting to be a limiting factor.



Link to the RFC 4984

Review: LHA -Logical Hierarchical Addressing Protocol For Mobile Ad-hoc Networks

The LHA allocation scheme uses the private block (192.168.0.0 - 192.168.255.255) to assign addresses to hosts in a MANET. The Host address is divided to 2 parts:

• Extended MANET ID, (ExMaID) 6 bits.
• Host ID, 16 bits.

They also use a NetID based on MAC address to identify a network.

An AA node is an Address Agent which assigns new free addresses to requesters. A requester node chooses its AA node from its neighbors.
The AA node which provides an address to the requester is his predecessor, and the requester is the successor of the AA node.

Network initialization:
The node starts a network when no messages are received for address assignment request. To choose the first address, the node selects a random number in the range of [1-30] as Host ID then another number from 6 bits as ExMaID. The NetID is defined by using the node's MAC address.

Joining of a node:
When a node joins a network it requests a free address from its neighbors. It then chooses its AA node based on its address and the available free addresses at this node.
AA node uses the following equation to assign a new free address:
New_Ad = Root_Ad + k*(Agent_Ad - (Root_Ad - 1)) - Afa +1.
Afa is the number of the available free addresses at this node.
K is the number of direct successor a node can have.

If an AA node don't have any addresses left, it broadcasts a request to its neighbors asking for a free address, the new node will be a successor to the node who provided the free address.

If no addresses are available, the new node is a root node for a new network.

Departure of a node:
When leaving a network, the node broadcasts informing his departure. The predecessor nodes updates their informations.

Network Partitioning:
When an AA node fails to assign a free address it checks it ALN (the number of lost nodes), if ALN > Threshold then there is network partition.
One of the partitions with the root node will increment its ExMaID while the other partition decreases its ExMaID and assigns the address of the root node to the new joining node. NetID is also updated in this partition.
All nodes free their missed addresses of their successors.

Network Merging:
There is 2 types of network merging:

• Soft merging: when the ExMaID are different then there is no address duplicated addresses. One of the partitions updates it NetID and save the ExMaID
• Hard merging: when ExMaID are identical then there is a high probability of address conflict. One of the networks increment its ExMaID by 2 and save the NetID of the other network.
  

Results shows that this method reduces latency to obtain IP address by 50 % comparing to the Token-based address assignment.

This work claim to reduce latency by 50% comparing to another address assignment protocol.
However it leaves many unresolved or unexplained points such as:

• How to determine how much successors a node can have, the value of K in the equation of address assignment. This value will definitely impact the number of free address allocations because every node is an AA node.
• When the root node leaves the network, the NetID should be changed and another node should be the new root node. What if a root node left the network then decides to join but because it is out of the transmission range, this node will not receive further messages from other nodes in the network. This node can initiate a new network with the same NetID, ExMaID and assign addresses to new nodes. When the node goes back into the transmission range of the initial network there is a high probability of address conflict which can go undetected because the NetID, ExMaID are identical.
• In the network partitioning if (ALN > Threshold) this is not necessarily a network partition. It can be simply nodes left the network after crash, empty battery etc, though too much unnecessary effort is done by changing ExMaID and broadcasting it.
• Since the NetID and not the ExMaID is used to identify a network then all the routing is based on the NetID and not IP address. This method will have impact on routing.
• When Hard merging, ExMaID is incremented by 2, what if there was a partition before, this means that one of the partion will increase its ExMaID by 1 what if the same partition was partitioned its ExMaID will be incremented by 1 which means the sum of increments is 2, equal to incrementing ExMaID when hard merging. This will lead to more conflict when partitions merge with a network who just had a Hard merging.
  

link to the article

Mobile IP

Nowadays a device might belong to a home network which means that it maintains a permanent address known as its home address and a temporary internet address assigned to it when joining another network.
This permanent unique address is used to communicate with such hosts.
When a host with a permanent address is attached to another network, the data received at the home network should be forwarded to the visited network.

There are several methods to keep track of migrating hosts such as:

• A server that keep the binding between the permanent address and temporary address. However this method has several limitations, mainly it is impossible to provide an on-line migration, transport protocols need to know about the new address in order to reestablish communication. It increase network traffic to update the mapping and caches if existed.
  

• Broadcast solution: when a host wants to send data to a migrating host, it broadcasts a query packet in a network and the migrating host reply with its temporary address. This mechanism can only be applied to small networks.

There are three well know problems involved when dealing with host migration:
[Internet draft NETLMM problem]

• Update latency: the update of the new temporary address is always necessary when a host migrate, though this update might take time if the migrating host did not notify about his mobility, network traffic, crashed routers,etc. During this time, the home network will forward received packets to an old temporary IP address until the new mapping occurs.
• Signaling overhead: when moving to another network, the migrating host notifies its home network and acquire a new address. The configuration and notification can be expensive depending on the method and the node resources (bandwidth, battery dependent etc).
• Location privacy: the change in temporary address exposes the migrating host topologically.
  

"The on-line Migration":
With the huge development of Wireless networks, a host can migrate from one network to another in a short time while still connected to other hosts. This is called "on-line" migration.
When migrating several applications need to stop and reestablish the communication with distant hosts using the new assigned address. This causes service or application interruption.

This interruption of service is encountered because in the OSI layers, the IP address is used for both host identification and routing (data delivery).
In the transport layer (TCP, UDP) the IP address is used as an identifier along with other parameters in order to uniquely address a host or a communication session.
As for the network layer, the IP address is used as a way to locate a host and deliver data.

The following paragraphs describes some solutions for the host migration.

Review: A network architecture providing host migration transparency

The Sony team proposes a network architecture in order to provide host mobility. Even though the article was written back in the 1991, we are still facing the same problem when dealing with host migration transparency.
They propose to separate the network layer to two sub-layers:

• The virtual network (VN) is a logical network that exists on the physical network. Each host in always connected to a VN just as it is connected to a PN. A host never migrates from its VN even if it migrates from its PN. A host has a VN address (permanent) and PN address (temporary).
  
• The physical network (PN): is the IP layer where the PN address indicates the location of the host in the PN which is used for routing.
  

The transport layer specifies the target host by its VN-address no matter where it migrates in the PN. The PN and VN have the same format.
When a host migrates, only its PN-address changes. Thereby the path to deliver data and not its identity (VN-address).
If host A wants to communicate with another distant host B, A uses B-VN-address. Host A-PN layer will translate Host B-VN-address to B-PN-address.

The Sony team uses the propagating cache method in order to reduce the overhead of address conversion. In this method each host and gateway hold a cache for address conversion. it is actually an address mapping table between the host's PN-address and the VN-address. Every entry in the table hold a VN/PN address, a source address timestamp used to determine whether the entry is obsolete and an Idle time (a Time To Live).
When a host changes a physical network it sends an update message "control packet" to its native network. This packet includes its VN-address and the new PN-address. When the packet travels to its native network, gateways on the path updates their entry with the new PN-address.
When a host A sends a request to another distant host B without any knowledge of host B PN-address, A just sets the host B PN-address with host B VN-address. The packets will be redirected to its native network and then will be redirected to its actual PN because on the path to the native network an address mapping of VN-PN will be hold by gateways.

This approach is interesting and seems to reduce overhead traffic comparing to Central server and broadcast methods.
However since packets sent from host A to host B don't always take the same path. Some of the routers and gateways will be updated and others will still hold an old mapping information. This would definitely lead to obsolete cache entries and loss of packets due to routing error.

link to the article

Review: Prophet address allocation for large scale MANETs

The Prophet address allocation scheme uses an arithmetic function F based on an IP address and a state value of F. This function seems to generate a sequence of numbers with a low probability of redundancy. The minimal interval between two occurrences is very large and depends on the IP address range.
Every host holds F and can assign a unique IP to other nodes.
When joining a network, a node A requests a unique IP address. If his request was ignored then A can start configuring a MANET. It proceeds by choosing a random private IP address and a random state value. When a new node B joins the network, A allocates a free IP address to B using F. Then A transmit to B, its new IP address and its state of F. A updates its state of F.
B is now capable to assign free IP addresses to new nodes.
As for partitioning and merging, since the IP addresses are "unique" no changing is required.
When dealing with scenario#3, a host configuring a MANET chooses a Network ID and sends it to new nodes with the free IP address.
When merging two alternative mechanisms have been proposed one of the MANET group should drop its IP addresses and request new free addresses. This method will break on-going communication and routing in the changing MANET.
The second mechanism requires only nodes with conflicting addresses to obtain new addresses. This mechanism requires high overheads to detect conflict addresses and does not provide an answer regarding what function to use for future allocations.
Node A chooses the seed for the whole network and the sequences may be computed locally which means it knows in advance which addresses are going to be allocated.

This scheme is able to reduce communication overheads in scenarios #1 and #2 since every node is able to generate a unique IP address with a low probability of conflict. However the low probability is based on a large range of IP address which is not the case with the private addresses. As for the Scenario #3, it will be handled in their future work.
Their approach is not suitable for large scale MANETs where the probability of assigning the same IP address is high.

link to the article

Review: Hosts Address Auto Configuration for Mobile Ad Hoc Networks.

This article propose a method for MANET nodes to assign a unique IP address.
Their approach is based on defining a MANET ID and a HOST ID from a private IP address block, (172.16.0.0 - 172.31.255.255) for exemple.
The MANET ID is a randomly 8 bits number while the HOST ID is a 16 bits number. the IP address will have the following form 172.MANET_ID.HOST_ID.

A Node creates the first network if no answers are received from hosts in an Ad Hoc network. it has a node number "0". it selects a randomly MANET ID between [0x16 and 0x32] and takes the first address in the host ID space [0x00.0x00]. The node "0" can allocate the addresses using the following equation:
Sum(i=0,i=Base_Value-1, n*Base_value+1).
Where base value= 2,3, ...
Host number n=0,1,2 ..
i = 0,1,2 ..(Base value-1)

The new node willl be add the generated value to the node "0" IP address. It will obtain a unique IP address in the Network.
The higher the value, the wider the tree and the higher the number of leaves with free addresses to allocate.
With base value=2, node 0 allocates values 0 and 1. Node 4 allocates values 8 and 9....
When a host joins a network, it broadcasts asking for a unique IP address. Nodes with available addresses will answer it. The new host should gives priority to the address allocating host with the lowest address.
This approach defines also use cases to reallocate addresses of hosts departing the network. ex when node 8 leaves, node 4 can reassign only value 8.
When network partition occurs nodes should free allocated addresses of non reachable hosts. The non reachable hosts are identified when routing packets and route discovery.
As for the network merging they propose to use the highest MANET ID between the 2 networks. The addresses with the lowest MANET ID will be reassigned.

Even though this approach seems interesting however when reallocating addresses there is high traffic of information to parent nodes to restrict the generation of certain IDs. It can be done when the Base value is low but when it increases, the restrictions exchange will be harder to maintain.
As for the merging, I think it would be more convenient to use the MANET ID of the network with the highest number of nodes. This approach will reassign new addresses to fewer nodes.
The solution don't provide a solution when 2 networks with same randdom selected MANET ID merges.

link to the article

Mobile Ad Hoc NETwork (MANET)

A Mobile Ad Hoc Network is formed by the association of mobile devices, usually wireless and capable of multi-hop communication among themselves even if there is no networking infrastructure available. [MANET Auto configuration Internet-Draft].

Node's mobility (arrival and departure of nodes in the network) makes it difficult to rely on a central trusted node whose role will be to allocate free unique IP addresses. The failure or departure of such central node will prevent further IP allocation.
Since there is no central networking infrastructure, MANET nodes should request from other nodes (or auto-assign) a unique identifier in order to communicate with other MANET nodes.

When building an address allocation system, the following 3 scenarios should be handled:
[Prophet allocation ...]

1. Join and leave: A mobile node joins a network and leaves forever with/without acknowledgment of departure. How to detect unacknowledged departure and reuse allocated IP address. How to allocate a unique IP address for 2 nodes joining at the same time.
2. Partition and Merge: a node or more of the MANET moves outside other's transmission range. When they move back within the transmission range, they should merge again with the MANET. What if other nodes joined and same IP addresses where allocated to them.
3. Two separated MANETs with different IP configuration merging.
   

Existing solutions can be divided into the following three categories:

1. Conflict-detection allocation: A new node selects an address from the private address space and requests approval from all nodes in the MANET. If it receives a conflict message from a node in the network, then it selects another address until the address is free, it becomes the new node's address. (Duplicate Address Detection method). These methods can handle easily scenario#1.
   
2. Conflict-free allocation: Free IP addresses are assigned to new nodes. Dynamic Configuration and Distribution Protocol is an example of conflict-free allocation algorithms which is based on dividing the address pool in two halves every time a new node joins the MANET. This insures the uniqueness of the allocated addresses. These methods can handle scenario #1 and #2 since the addresses are already different. However when it comes to dealing with scenario #3 conflicts are unavoidable. The pool addresses are taken from the private addresses range.
3. Best effort allocation: the nodes responsible for allocating new addresses attempt to provide a conflict free address to the best of their knowledge, but conflicts may still occur, say due to the same address being allocated to two joining nodes before there is time for updating the table of existing addresses. An example of best-effort allocation is MANETConf Protocol.
   

The next section describes a summary of an auto address assignment methods to MANET nodes.

Introduction

Hi,
My name is Charbel EL KAED, I am a PhD student at the National Polytechnic Institute of Grenoble and France Telecom Labs.
I am interested in the naming and addressing for large scale and mobile devices.
LAMONAHD is an alias for LArge MObile Naming and Addressing for Heterogeneous Devices.
This blog contains a summary of the papers and RFCs that I am currently reading.

Please feel free to post your comments or/and suggestions in English or French.

You can look at my webpage at:
http://sites.google.com/site/charbelweb/