Review: Design considerations for a network of Information

In this position paper they insist on the fact that the Internet has to be reshaped and be focused on data instead of endpoints, in order to have a data centric network or network of information.
According to Jacobson [1], the first generation of the network dealt with connecting wires. The second one focused on end nodes hosting data while the third generation should refocus on what humans care the most about Information.

Their information models distinguish between 2 main objects:
Data Objects (DO): are the actual bit-patterns that contain the information: such as file, phone call, video, web page, a song(Beethoven's 9th symphony) etc. These data objects can be divided into "chunks" smaller pieces in order to simplify the transfer.
Information Objects (IO): holds semantic information and meta-data related to data objects, such as Beethoven's 9th symphony is an mp3 file encoded with 128kbps, IOs can be composed of other IOs or directly pointing to one or multiple DOs. An IO can represent the Eiffel tower and point to DO like pictures, a wiki page or service to buy tickets, etc.

Versioning and Revocation:
Since some information is frequently changing such as news papers. An IO can represent today's version, however the IO should adapt dynamically by binding to another DO (web page) the next day, and so on for the IO pointing to yesterday's news.
They suggest that objects invalidate themselves in order to conserve consistency. After an amount of time, objects should be recertified before it can be used. By applying this technique, they maintain consistency due to disconnected operation during information update of other replicas for example. DO can be deleted same way when no certification is given.

Security considerations:
Security in today's architecture is based on confidence (Encryption keys) of the host delivering the object, they propose to reshape security conventions so we can handle secured data instead of secured tunnels.
Integrity and authenticity is directly tied to object's names which means there would be a cryptographic relation between the name and object such as self-certifying names. However to enable off-line verification, DO must carry private keys which can be compromised. Another approach is to assign precomputed signatures to objects. It remains a research field.

Name resolution(NR):
Data objects are retrieved based on their unique identity (UID). NR starts with locating the object in the network then routing forwards the object retrieval query to its storage location and finally the DO is sent to the requesting client.
The naming resolution resolves an UID into one or more locations and should work on global and local scale by cooperating between NR systems for example. They show the side effects if ID/address split mechanism is adopted with the following example, if a laptop hosting numerous Data Objects moves its location then all Data objects location changes too. This will lead to huge number of updates in the NR system.
The NR system will be influenced by the characteristics of namespaces. They would like to adopt flat names which respects the non right of ownership and other characteristics revealed by [2].
Off course, using flat names prevents the use of hierarchical names spaces and systems like DNS.
DHT based solutions are promising since the are decentralized, scalable, self-organized and don't need central structure. However when going globally DHT uses flat names hence non hierarchical names which prevents cooperation with other systems.

Routing:
Addressable entities are still increasing and will reach millions even billions in few years with the emergence of sensor networks, Internet of things, growing data etc. They claim that routing research are not encouraging according to [3] (will be reviewed later). Hence, they ll investigate the efficiency of name based routing which integrate both resolution and retrieval paths. Name based routing will locate DO based on their ID by transforming the ID directly into a path without going through ID-address transition. Other techniques such as LLc and NodeID are to be investigated also (Soon will be reviewed).

Storage:
The information network can be implemented following two different models:

• Network based storage model where storage resources are provided by the network infrastructure, like dedicated storage servers.

• Network managed storage model where network nodes control portions of storage memory of users connected to the network. Users will be able to decide what DO goes public or be shared only with friends etc.

Search:
Search systems are expected to go far beyond text match search, such as semantic search or even search functionality based on GPS position, location positioning. For example when a picture of Eiffel tower is taken, a search mechanism will handle the identification of the monument based on GPS or other techniques and points to DO related informations such as web page, history etc.

This position paper gives many ideas and anticipations about the future Internet architecture and reveals the weakness in the current addressing system. They distinguish between DO and IO and argued that a network of information needs a scalable naming system supported by an efficient routing system.

References:
1 - V. Jacobson, M. Mosko, D. Smetters, and J. Garcia-Luna-Aceves. Content-centric networking. Whitepaper, Palo Alto Research Center, Jan. 2007.
2 - M. Walfish, H. Balakrishnan, and S. Shenker. Untangling the web from DNS. In NSDI’04: Proc. 1st Symp. on Networked Systems Design and Implementation, San Francisco, CA, USA, 2004.

Link to the article

Review: Survey and Taxonomy of IP Address Lookup Algorithms

I will first start with some basic definitions:

• Address Lookup: is when a router uses the packet's destination address as a key to consults its forwarding table in order to decide the next packet's destination.

• A trie is a tree based data structure allowing the organization of prefixes on a digital basis by using the bits of prefixes to direct the branching. A node on level l represents the set of all addresses that begin with the sequence of l bits consisting of the string of bits labeling the path from the root to the node. (According to the survey).
  

• Address Class Scheme: In IPv4 the address was first designed as a two part identifiers: the prefix designate the network and a suffix that identifies a host. The prefix refers to class category A (8 bits), B (16 bits) or C (24 bits). The prefix 130.86/16 is a class B with a 16 bit length (number after the slash).
  

• Address aggregation: Since routers forwards packets based on the prefix IP part, forwarding tables need only to store a single entry in order to forward packets to all hosts attached to the same network. This technique is called address aggregation.
  

• CIDR (Class Inter Domain Routing) Address Scheme: the CIDR was introduced to slow down the growth of the backbone forwarding tables. CIDR prefixes can be of arbitrary length rather than (classified addresses) 8, 16 or 24 bits long. Hence, this will allow recursive address aggregation. Forwarding Tables will reduce the number of entries of the backbone routers and will hold aggregate information rather than network information. Example: Consider the following networks 208.12.16/24 through 208.12.31/24 which are reachable from the same service provider. These networks share the same leftmost 20 bits. Instead of storing all these networks IP in a backbone router, these addresses can be aggregated into one "super router" represented by the same 20 bit prefix 208.12.16/20 and the backbone router will hold only one entry to the "super router".

• Network renumbering: this operation occurs when a network changes its service provider. Hence the change of the IP prefix which imposes the change of the IP addresses assigned in the network, this is called network renumbering.

What is the longest prefix matching?

CIDR scheme reduces the forwarding tables through aggregations, however few elements can still interfere with the process of aggregation. Such as when a network 208.12.21/24 changes its service provider but still wants to use the same IP prefix and IP addresses assigned in the network. Consequently all networks from 208.12.16/24 through 208.12.31/24 can still be reached from the same service provider except 208.12.21/24 which break the aggregation process. The "super router" cannot aggregate 208.12.16/20 anymore, it will store in its forwarding table both 208.12.16/20 and the exception entry 208.12.21/24. Since the two entries share the same 20-bit prefix, when matching we need to look for the longest prefix in order to find the most specific forwarding information to the correct destination. Therefore, we are talking about a search in two dimensions: value dimension and length dimension.

Why do we need scalable and fast address lookup algorithms?

• Number of entries in routing tables are still growing due to the increasing number of networks and exceptions.
  
• Increasing number of update operations in routing tables. Forwarding tables needs to be updated dynamically to reflect the route change. According to [1] route changes occurs 100 times/second. Hence update operations must be fast (less than 10 msec).
  

Solutions:

Binary Trie:
In a binary trie, every node has at most 2 branches with values (0/1). The search starts at the root level and goes to the left or to the right according to the bits of the destination address. While traversing the trie, every time we visit a node marked as prefix (nodes with letters inside), the prefix is remembered as the long prefix visited so far. The search ends when there is no branches matching the next bit in the destination address and the best matching prefix (BMP) is the last prefix remembered. The Binary trie is a sequential prefix search by length, at each step the search space is reduced hierarchically . Update operations are simple, inserting a prefix begins with a search until the arrival to a node with no branch the node can be inserted. Deleting operations starts also with a search unmarking the node as a prefix and deleting unused nodes. Nodes don't store prefixes since the prefixes are represented by the trie structure.


Path-compressed Tries has been introduced to improve space and time performance for tries with sequences of one-child node. The prefix b in the figure above shows a one-child node sequence. When searching in a binary trie, The bits separating prefix a from b need to be inspected even though no other branches exist. The additional search is a waste of time and the additional nodes (between prefix b and a) consume additional memory. In a path-compressed trie, one-child nodes are removed, when performing a search we can jump directly to the bit where a decision can be made. Hence, a bit number field is kept to indicate the next bit to inspect. In a path-compressed trie, the bit-number field of the nodes traversed indicates the position to inspect and the bit value in the branch reveals the destination to follow (left if 0, right if 1) depending on the inspection result. When a node marked as prefix is encountered, a comparison with the actual prefix value is performed. This step is essential since we are skipping some bits. When a match is found, the search continues and the prefix is kept as the BMP so far. The search ends when a mismatch or a leaf is encountered. Path compression is useful when the binary trie is not well populated because using comparison has little benefits. In general binary and path-compressed tries requires many memory access. (worst case 32 for IPv4 address).

Simple Search on values approach:
The data structure needed is just an array containing unordered prefixes. The search goes through all entries comparing destination address. When a prefix match is found, it keeps the longest match. At the end, the last prefix remembered is the BMP. Clearly this scheme is a function of the number of entries and is not scalable.

Prefix transformation:
Forwarding information is based on prefixes that represents address ranges. One of the most common prefix transformation techniques is prefix expansion which expands one prefix into several longer and more specific prefixes that cover the same range of addresses. Appropriate prefix expansion results in fewer different lengths and can be used to make a faster search. In order to avoid the longest prefix match a method of disjoint prefixes is used. Disjoint prefixes do not overlap and no prefix is a prefix of another one. A trie representing disjoint prefixes will have prefixes at the leaves but not at internal nodes. A disjoint-prefix binary trie is obtained by adding leaves to nodes with only one-child. The following figure is a transformation of the figure above. Prefixes a1, a2 and a3 replaced prefix a. Prefixes are pushed from internal nodes to leaves. (Which will make prefixes disjoint).


Search on prefix lengths using Multibit Tries:
Multibit trie is a trie structure that allows multibit inspection at each step. Multibit tries increase the search speed, instead of inspecting one bit per step it allows multibit inspection. The number k of bits allowed per inspection is called stride. Every node in a multibit trie has at most 2^k child. Since search traverses strides of several bits at a time, multibit tries cannot support arbitrary prefix length. Height of the trie (comparing to binary tries) decreases and so the number of memory access when searching.
The strides choice influence the search speed and memory consumption. Actually if the stride increases so does the search speed (trie’s height decreases) and memory consumption to store larger amounts of entries. With a stride of 32 bit for IPv4, there is only one level access but memory to store 2^32 entries is required.
When prefix expansion is applied, the local BMP for each node of the subtrie is computed. Inserting or deleting a prefix needs to be applied on the subtries. Hence prefix update is local, if the new prefix will be stored in a subtrie with a stride of k bits then the update requires to modify at most 2^(k-1) nodes.
Choosing larger strides will make faster searches but more memory is needed and updates will modify more entries due to expansion.
Multibit based solutions emerged in order to optimize memory consumption and increase search speed such as the Level Compressed trie, Lulea scheme, Full Expansion/Compression and many others. However these approaches are inadequate when it comes to update operations, rebuilding the whole structure is more often the only solution.

Binary Search on Prefix Lengths:
Waldvogel [2] proposes another method for prefix lookup without using a trie structure. He proposes to organize prefixes in different tables according to their lengths and to use a binary search to reduce the search space in half in each step. A comparison is applied in each step in order to decide to which half the search should proceed. If a match is found, then the search can proceed to longer prefixes but if there is no match than no decision can be made regarding the direction to take.(Longer or shorter prefixes?). Waldvogel proposes to use precomputed BMP on each prefix and extra prefixes called markers to be sure that when no match is found the binary search should proceed towards shorter prefixes.
For example, if we search the BMP for the address 11000010, since the length is 8 we ll start searching in the table prefix with length 4.(half length). We compare entries with 1100, a match is found with prefix f then f is a BMP so far and we can proceed with 110000 (the other half is 4 bit length, we take a half and continue the search it means we have a 6 bit length address). If another match occurs with a prefix when searching in the 6 bit length tables then the prefix becomes the BMP so far. The other part of the address left is 10, 2 bit length, then we proceed with address 1100001 in the 7 bit length tables etc. When going towards a next step extra markers prefixes are inserted in the adequate length in order to direct the search to shorter (resp. longer) prefixes in there is a no match (resp. match). Usually I think that extra markers are inserted when the one child subtrie situation occurs.
The markers and precomputed BMP increases the memory usage and make updates more difficult because these values need also to be updated.

Prefix Range Search:
The prefix range search flatten the two dimension (length and value) search into only one dimension by getting rid of the length dimension. One way of doing this is by applying a prefix full expansion in order to have the same length of all prefixes (expansion to 32 bit address IPv4).
Once the transformation is applied, we can proceed with range search. Every prefix determines a well defined range of address. For example for 5 bit length address, a prefix a= 0* would define the range [0,15] since after expansion the prefix range would be [00000,01111]. Hence, instead of storing addresses we will store range endpoints. The BMP of the endpoints is in theory the same of all addresses in the same range. Finding a BMP for an address would be reduced to finding the endpoints of the corresponding interval. However, this technique will not work because prefix ranges may overlap. Range addresses are not disjoint, a range may be contained in another range.
However, endpoints divide the total address space into disjoint basic intervals. The BMP of an address can be found by using the endpoints of the basic intervals (see figure below). Some basic intervals do not have explicit endpoints, so it maintains two BMPs.
The figure below shows a search tree. For example, if we search the BMP for the address (22) 10110, the search begins with the key value 26 and the search proceeds following the comparison decision until arriving to the BMP value "d".
Since the BMP for each basic interval needs to be precomputed, update operation requires to recompute the BMP for many basic intervals.
A multiway search tree can be used just like the multibit trie in order to accelerate the search speed and reduce the tree's height.

IPv6 related:
According to the survey, multibit tries scale badly with longer addresses and hence prefixes when dealing with IPv6 128 bit addresses while the range search seems to be a good approach to face scalability issues for IPv6.


This survey reveals important limitations of the Internet infrastructure and address classification design in IP addresses. It exposes the challenges facing routers and Internet growth. It points to the need of a scalable algorithm that increases the search speed of addresses and reduces memory consumption and access. Such algorithm should handle incremental updates with a minimum change to the structure.
In my opinion, every naming system will face such challenges when dealing with delivering packets to the appropriate destination or retrieving pointers through addresses as keys.
Other reviews will be added to cover the state of the art of such algorithms proposed beyond year 2001.

References:
1 - C. Labovitz, “Scalability of the Internet Backbone Routing Infrastructure,” Ph. D. Thesis, University of Michigan, 1999.
2- M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups,” Proceedings
of ACM SIGCOMM’97, pp. 25-36, September 1997.

Link to the survey

Review: RFC 4862 - IPv6 Stateless Address Autoconfiguration

RFC 4862 specifies the steps for a host (except routers) to apply in order to auto configure its interface and generate an IPv6 address.

Why Stateless auto configuration?

• Assign a unique address to an interface.
• Hosts in small networks would not require a DHCP server or a router to obtain a unique address. Such hosts should be able to generate unique addresses in the network.
• Large networks will not require DHCP servers for address auto configuration. Hosts should be able to generate global unique addresses.
• Facilitate address renumbering on a site or subnet. A site renumber it's nodes when it switches to a new network service provider (IP prefix modification). When renumbering, old IP address will coexist with the new IP address during a period until the old IP becomes invalid.
  

How stateless auto configuration works?
We can divide the process of auto configuration into the following phases:

1. A node generate a link-local address when its interface becomes enabled. (Reboot, start time, attachment to another link etc). This link-local address is formed by concatenating the interface identifier (generated from the interface MAC address for example) to the well-know link-local prefix 0xFE80::0.
2. The node checks if the address is unique by using Duplication Address Detection (DAD) techniques. If the address is unique then it will be assigned to the interface, if not another interface identifier is required to generate a unique link-local address. Administrators can supply an alternate interface identifier. If not a manual configuration is required. In this phase, the node generates a link-local unique address.
   
3. Nodes will listen to routers advertisements holding information to generate global addresses. Solicitation messages can also be sent by nodes to routers to avoid waiting for advertisement messages. If some specific flags are set then the node can use a prefix carried in the advertisement and apply it to the generated address. (Prefix concatenated with Interface ID). Actually this prefix is usually the subnet's prefix.
4. Duplication Address Detection is required before assigning the global unique address to the interface. Some implementations applies DAD only to link local addresses and assumes it is globally unique if it passes the local test. However new techniques have been developed for privacy protection issues. An interface identifier can be generated randomly for example, then a clash with another global address might occurs [RFC 4941 - Privacy extensions for stateless address autoconfiguration].

Nodes still listens to routers advertisements mainly to reset/increase the prefix lifetime or valid time. When the prefix advertised is different from the one generated, then it is a renumbering case, the node will form a new address (new prefix, Interface ID) and adds it to the list of addresses assigned to the interface.


According to this RFC, the Duplication Address Detection is not fully reliable, it will generate a large overhead when testing a global unique IP address.
Other mechanisms to detect address collision should be pushed further.
Site renumbering is another argument to be added to the list in order to separate a host's name from its identity.
Generating the same suffix every time can expose the identity and location of a node which in some cases can be unwanted.

Link to RFC 4862

Review: 6LowPAN

Why IPv6 can’t be applied directly on LowPANs?
6LoWPAN defines IPv6 protocol over Low power Wireless Personal Area Networks.
LowPAN devices uses IEEE 802.15.4 radios. In order to understand why we
can’t use IPv6 directly on top of LowPAN devices let’s list the characteristics of such
devices [2]:

• Small packet size. 81 bytes for data packets in the networking layer. (The maximum physical layer packet is 127 bytes, consequently the maximum frame size at the media access control layer is 102 octets. 21 bytes at maximum are usedfor securing link-layer communications).
• Support for both 16-bit short or IEEE 64-bit MAC addresses.
• Low cost devices: low bandwidth with data rates of (250 kbps, 40 kbps, 20 kbps) for (2.4 GHz, 915 MHz, 868 MHz). Low power typically battery dependent. Low processing and storage capabilities (8KB RAM, limited buffering, etc).
• Topologies include star and mesh operation.
  
• Large number of devices expected to be deployed.

The main problems with IP for LowPANs are the following:
The term Maximum Transmission Unit (MTU) refers to the size (in bytes) of the largest PDU that a given layer of a communications protocol can pass to other layers. A higher MTU brings greater efficiency because each packet carries more user data than protocol overheads. Large packets can occupy a slow link for some time, causing greater delays to following packets and increasing lag and minimum latency.
IPv6 protocol uses 128 bits IP address and a header of 40 bytes long. The MTU is at least 1280 bytes in order to maximize the efficiency of the transmission ((useful data)/(overhead data)).
LowPAN devices supports small packets with 81 bytes available for the networking layer and above. Using IPv6 on IEEE 802.15.4 leaves only 41 bytes for transport and applications layers. This is obviously not enough for data exchange, packet fragmentation and reassembly is needed but will use even more bytes. An IP header compression is needed.
Since large number of devices will be deployed, address auto configuration is attractive because it will reduce the overhead between devices. There is a need for a method to generate and assign an Identifier from the EUI-64 bits to a LowPAN device.
Routing protocols in mesh and star networks must be adapted to a small overhead. LowPAN devices have limited resources (memory, bandwidth, CPU, energy), processing 128 bits addresses and large headers will decrease the system’s efficiency and increase data treatment latency.

Why use IP based protocol in LowPANs?
The benefits of using IP based networks are the following [1][2]:

• The hierarchy of naming and addressing in IP networks which simplify the connectivity model.
• IP-based technologies already exist, are well-known, and proven to be working.
  
• IP networking technology is specified in open and freely available specifications.
  
• Use existing tools for diagnostics, management, and debugging of IP networks instead of designing and developing new ones.
• IP-based devices can be connected easily to other IP-based networks, without the need for intermediate entities like translation gateways or proxies.
  

Addressing Modes
IEEE 802.15.4 uses IEEE 64 bit and 16 bit addresses. Short addresses are assigned by a PAN coordinator during an event which means that validity and uniqueness of such addresses are limited by the lifetime of the association, failure of the coordinator, etc [3].
For short addresses (16 bits), a pseudo 48 bit address is formed by concatenating 16 zero bits to the 16 bit PAN ID (Personal Area Network). If no PAN ID assigned then 16 bits of zeros are used and the resulting concatenation is a 32 bits address. These 32 bits are concatenated with the short address in order to obtain a 48 bit address.
From a 48 bit address, a 64 bit interface identifier is formed as in [5] and [6] by adding 0xFFFE in the middle of the 48 bits (24 bits,0xFFFE,24bits). IPv6 local addresses are formed using the 64 interface identifier by appending the prefix FE80::/64. (0xFE80::EUI-64) or global addresses based on information advertised by routers [7].
Routers are the link between IP and LowPAN networks, those routers will handle address transition.

Header types
6LowPAN proposes specific header encoding and compression mechanisms to adapt IPv6 into IEEE 802.15.4 frames. Separating headers will reduce overhead. If a device is sending short packets directly to another node it does not pay for extra fields such as Mesh networking or fragmentation. The overhead reduction is an energy saving.
The header types are the following:

• The Dispatch Header (1 byte), define the type of header to follow. The dispatchheader is identified by the first two bits set to either 00 (non-6LowPAN frames)or 01. The remaining 6 bits indicate if the following field is an uncompressedIPv6 header or an HC1 header (IPv6 compressed header). To accomplish compression[1] the protocol uses a combination of the following facts: the low order64 bits of an IPv6 address (the link local address) can be the device’s MAC address,the 802.15.4 frame carries these MAC addresses, a number of the fields inthe IPv6 header are static.Combining all of these features allows the protocol to compress the standard 40 byte IPv6 header down to just 2 bytes (including the HC1 Header byte) for most intra-PAN unicast communication where source and destination addresses are deleted and generated from Link level frames (IEEE 802.15.4). All of the rest of the fields can be reconstituted without any state information at any of the receiving or intermediate nodes. Additionally by assigning the link local address to the device’s MAC address 6lowpan can use Stateless Address Auto configuration(Zero-conf) and eliminates the need to infrastructure servers like DHCP servers.
• The Mesh Header (4 bytes) is used to encode the hop limit and the source and destination of the packet. It includes two single bit fields to indicate if the originating
  or final address is a short or long address. The “hops left” field is a 4 bit
  field used to limit the number of intermediate hops between the source and destination.
  The value of 0xF was reserved to indicate that an extra byte is included
  allowing for network depths of up to 255 hops.
• The Fragmentation Header (4 bytes for the first fragment and 5 bytes for subsequent
  fragments) supports the fragmentation and reassembly of frames larger
  than the size of the 802.15.4 frame.

Today there is at least 6 implementations of 6LowPAN on multiple 802.15.4 radio platforms. The working group is still continuing to investigate the areas of neighbor discovery: IPv6 network prefix, local routers and other network configurations parameters.
The area of service discovery to locate other sensors and controllers and higher layer services.
Is it a good choice to push further IP based protocols to other areas such as LowPAN while efforts increases to redesign the Internet?
Should we inherit the limitation of IP which merges between naming and addressing to LowPANs?
What about cross-layering violation while compressing Ipv6 headers and regenerating source and destination address for Link level frames? According to the OSI scheme, Layers should be independent and unable to understand other layer’s data.
Even though in some cases header compression is efficient (with layer violation) other compressions remains unoptimized in LowPAN. Additional work should push routing protocols and reduce overhead of such protocols.

References:
1. The 6LoWPAN Architecture, Geoff Mulligan and 6LoWPAN Working Group, EmNets '07: Proceedings of the 4th workshop on Embedded networked sensors
2. RFC 4919: IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs):
Overview, Assumptions, Problem Statement, and Goals.
3. RFC4944 - Transmission of IPv6 Packets over IEEE 802.15.4 Networks
4. 6LoWPAN: Incorporating IEEE 802.15.4 into the IP architecture Internet Protocol
for Smart Objects (IPSO) alliance.
5. RFC 2464: Transmission of IPv6 Packets over Ethernet Networks
6. http://technet.microsoft.com/en-us/library/cc736439(WS.10).aspx
7. RFC 4862: IPv6 Stateless Address Auto configuration

Review: An IPv6-Based Identification Scheme

This article presents an IPv6 identification scheme to identify physical objects with
RFID tags. The identification is needed in different fields such as locating objects,
health care monitoring, military operations etc.

Their scheme is based on IPv6 unicast address:

010.Registry_ID[5].Provider_ID[16].0.8].Subscriber_ID[24].0[8].Subnet_ID[16].Interface[48].

(note that the "‘."’ is used as a concatenation operator and X[n] where n indicates the
number of bits used to code the field X).

Register_ID is allocated to organizations responsible for assigning network addresses.
Provider_ID is allocated to Internet service provider. 0[8] future extension.
To identify objects they propose to use the unassigned IPv6 namespace that has the
binary prefix "‘001"’ with two formats:

General ID:
0010.Agency_ID[5].Domain_name[48].0[7].Object_Class[16].Serial_Number[48].

Agency_ID is analogous to registry ID, the agency is responsible for allocating the
identifier. Domain name for company or organization. 0[7] future use. Object class to
identify object types. Serial number ID of an object type.

Pseudo Random ID:
0011.Agency_ID[5].Random_Number[119]

This scheme provides more privacy, it does not reveals the ID of the company and other information. They clearly distinguish between and IPv6 address to locate an object and IPv6 ID
to identify and object. The prefix translation is what they propose to translate between an IPv6 ID (prefix 001) and an IPv6 address prefix (010) which means that the IPv6 ID may be used to
obtain an IPv6 address. Since physical objects are mobile, they propose the following
two methods to track objects:

Name System: (Same ID, multiple addresses)
They propose to use canonical name written in a reverse order in which they are constructed.
They reverse it so it can be used as a URL DNS like. By doing this, they can integrate their scheme in existing systems like DNS.

Serial_number.object-class.company.organization.obj.
DNS query will start at "obj"’ level than it will go from right to left.

When objects moves, we need only to update DNS records which maps a name into an address. When objects moves to a different domain, the new owner of objects should update the DNS record. Since DNS is not suited for updates, a localization service provided by the proxy should handle the update.

Address forward scheme:
They use the home agent approach (see Mobile IP paragraph).
They assume that routers are configured to distinguish identifiers from addresses.
We can search for an object by its ID because routers will translate the IPv6 ID into an IPv6 address by modifying the 3 bits prefix. The ID will remain the same and so the address. Objects of the same owner are assigned to a dedicated proxy. The proxy’s address will have same domain prefix. When a router receives an object ID, it translates it and forwards it to the correspondent proxy according to the domain name. When an object moves, its ID and so its address remains the same. The object updates his home proxy with the new location where it moved recently. It also informs the new proxy about its ID. Routers will forward the packets to the proxy according to the domain name. This proxy will have the same role as a home agent in an IP mobile. The proxy will forward requests to the new proxy where the object has moved.

The approach is very comprehensive specially the mapping between ID and address with the 3 bits prefix and the facility of integration in today’s system without major modifications and without a need to query directories like DNS.
However since objects are usually manufactured in thousands and millions (Gillette raisers) when a container moves from an owner to another. The traffic update will generate a massive overhead between owners.
We are faced to the same problems when dealing with mobile IP. We lost object’s trace during transition from one proxy to another.
Not all companies have the same productions capacities. Small companies manufacturers small number of items which means that small companies will not use the IDs assigned to it, while big companies will exhaust ID in a short time (comparing to small companies). Should small companies share the domain ? This means that proxies of small companies cannot use a routing mask when dealing with IDs and IP addresses.
Two companies can share same domain, these 2 companies will have same prefix and since it cannot apply a mask. A proxy will list all the IDs of owned objects. Proxies will be overloaded then and I/O time query will be slow due to the huge amount of data.
Mobile IP approach what if home proxy or company owner of the domain is closed for economic or other reasons. How to maintain the address forwarding?

Link to the article

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

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.