• Abstracts
• DAS-MANET
• Machine Learning Go
• Java RMI
• Human Interfacing
• Physics Education

DAS-MANET: Dynamic Address Scheme for Mobile Ad-hoc Networks

Matthew H. Pinner and Jeramyn Feucht

December, 13 2001

Abstract

This paper discusses the analysis and implementation of the dynamic address assignment techniques proposed by Jeff Boleng in his paper “Efficient Network Layer Addressing for Mobile Ad Hoc Networks”. [1] This paper discusses a method that will allow a Mobile Ad Hoc Network (MANET) to use variable length addresses. Using variable length addresses will allow the network to reduce packet size therefore increasing network performance. This paper will first explain the method that Boleng’s proposal uses to implement dynamic address lengths. The paper will then analyze strengths and weaknesses of Boleng’s proposal. It will provide further solutions and suggestions to areas of the solution that have not been thoroughly discussed or are incomplete. The analysis will include preliminary calculations of dynamic address length savings, as well as, how the implementation has developed through out the life of the project. The paper will be broken into 5 parts an introduction, current proposal for a solution, problems, implementation, and data found. The introduction briefly explains all parts of the paper and includes basic background information. The section on the current proposal for a solution to dynamic address length assignment will discuss in a short detail how Boleng’s proposal for implementation would work. The problems section of the paper includes what we saw as potential problems the corresponding solutions. These problems include address reuse, decrease network address size, security, joining networks, and address conflict resolution. Each problem has specific trade offs that will be considered and analyzed. The implementation section shows how the proposed solution is implemented. It includes problems found during implementation as well as milestones reached. The implementation includes only the rudimentary parts of the proposed solution. It is not a complete implementation of the proposed solution. However, it does give a good foundation to build the rest of the implementation on. NS has been used for this implementation. The data collection includes a brief synopsis of what data has been calculated and gathered as well as what data would be ideal to be collected upon a full implementation. This data will help us to determine time outs and standards for variables within the addressing scheme.

1 Introduction

Network capable devices are becoming smaller and increasingly portable. The ability to form a network without prior configuration would increase the functionality of mobile devices. A device operating on a network can leverage the functions of other members of the network. Many challenges arise when one translates standard networking ideas to that of a Mobile Ad Hoc Network (MANET).

Hosts identify themselves with a unique address on a network. This address is used as an alias to that machine’s specific network card. Currently network administrators must configure their networks for a range of addresses before a network is formed. The range is specific to the number of hosts expected. Then the network is formed and hosts communicate and route based on the assigned addresses.

With a network being created on the fly one has no prior knowledge of the number of hosts and therefore no knowledge of a suitable address length. There is much needless overhead in using 32-bit addresses for a network composed of two hosts. Each packet would contain 64-bits of addressing information (32 bits for the destination and 32 bits for the source) when only 4-bits (2 for destination and 2 for source) would be required. The proposed Dynamic Addressing Scheme (DAS) aims to more closely match address size to network size. It will allow a MANET to change size and reassign larger addresses when needed.

This more efficient addressing is not without its cost. Requesting unused addresses and the joining operation of two MANETs will add network over head traffic. Despite the possible drawbacks, we will attempt to prove that the advantage of having a smaller address length will make this scheme more efficient than current MANET addressing implementations.

Other’s research on minimal configuration networking has been vital to our efforts. Boleng’s paper [1] exemplifies the variable length addressing, which will likely prove to be a great benefit. The ZeroConf group at the IETF has worked out an on-demand addressing scheme that allows network interfaces to maintain multiple addresses. Their paper [3] explains methods for changing and defending addresses. Their work on address collision detection has inspired the collision detection features in DAS-MANET. Corson’s paper [4] thoroughly describes measures of MANET performance. Internal protocol efficiency and throughput are the most noteworthy that were discussed.

2 Current proposal of implementation per Boleng’s paper

Boleng proposes that up to a 70% gain in efficiency can be gained by using dynamic addressing. This efficiency will be gained by changing how addressing is done. Boleng’s paper proposes a new structure for the address segment of all packets. The new packet header will include the first four bits of the highest address as well as four bits to indicate the number of four bit segments used by the network. The address space will begin at 16 bits.

• 4 to determine the first four bits of the highest address
• 4 to determine the number of 4 bit segments used in the address
• 4 for the destination address
• 4 for the source address

When a network is created the first node will look for an existing network by sending a join beacon. A join beacon is a MAC layer request to adjacent nodes to requesting that the node trying to join the network be given an address. If no response is received the new node assumes it is creating a network and begins to listen for join beacons.

If a node receives a join beacon it will respond with information saying that it is capable of assigning the new node an address. It is then necessary for the new node to choose one of these responses as an attachment agent. The attachment agent is a node that is currently participating in the network that has responded to a join beacon. Once the attachment agent is chosen the attachment agent will look at its current information regarding the next highest address. It will pick the next highest address and send a flood out to the network asking all other participating nodes if that address is in use. If no nodes respond with information about that address being in use the attachment agent will then assign the address to the joining node and that node can begin to participate in the network.

If two networks collide the larger network appends a 1 to all of its address and increments the highest used address accordingly. The smaller of the two networks will just increment its highest address accordingly and a 0 will be appended to all addresses.

A sample packet address header from the first node in the network to the last node in the network.

		Source Address			Destination address
Addr Length	Max addr	4bit section 2	4bit section 1	4bit section 0	4bit section 2	4bit section 1	4bit section 0
0010	1101	1101	1111	1111	0000	0000	0001

In this example there are a maximum of 212 nodes before the address size needs to increase. For 212 nodes this packet size will save 32 bits per packet compared to IPv4, which would use 64bits to address each packet.

3 Problems and Solutions

Boleng’s proposal contains great concepts however there are some situations that have not been thoroughly discussed. There are also some areas that we felt could be optimized to better fit the demands of a MANET.

3.1 Address Reuse

Address reuse is a very important part of the addressing scheme that is not discussed in Boleng’s proposal. If addresses are not reused the entire purpose behind creating a dynamic addressing scheme that will save packet length is nullified. The address length will just continue to grow as nodes enter and leave the network. As the address length increases the addressing scheme becomes less and less efficient.

With out address reuse if 268,435,456 or 228 addresses have been requested this type of addressing scheme will become significantly less efficient than standard IPv4 addressing. IP addressing is has 32 bit addresses. Once DasManet reaches a 28-bit address length it has the same amount of addressing overhead as IPv4. This is because each packet must contain source and destination address. There for each IPv4 packet must contain 64 bits of address. In DasManet 8 bits are used to determine the highest address as well as the address length. When compared to IPv4 this means that there are 54 bits for addresses and therefore each of the sending and receiving addresses has to be 28 bits long. 228 nodes sounds impossible to attain and it probably is.

If 100 nodes were to enter the network every hour it would only take about 306 years for the address size to get large enough for standard IP to be more efficient. This hardly seems to be the reason to implement address reuse. Perhaps we need to look at the other end to see why address reuse will be necessary. The following table shows the losses in efficiency of the address space in the packet header as address size increases. It has a comparison of DasManet to IPv4 and to IPv6. Efficiency gain compared to an average Internet traffic packet of 44 bytes is also given. The calculations for this comparison have scaled the packet to the appropriate size when compared to ipv6 therefore a typical ipv6 packet in this case is 67.75 bytes. The calculations do not incorporate the losses in efficiency of DasManet due to extra control traffic. These numbers are only valid for a static DasManet network.

Max Number of Nodes	Size of DasManet packet	Size of Packet		Efficiency gain in address space		Efficiency gain for a 44 byte packet Standardized on IPv4
		IPv4	IPv6	IPv4	IPv6	IPv4	IPv6
16	16	64	256	75.00%	93.75%	13.64%	44.28%
256	24	64	256	62.50%	90.63%	11.36%	42.80%
4096	32	64	256	50.00%	87.50%	9.09%	41.33%
65536	40	64	256	37.50%	84.38%	6.82%	39.85%
1048576	48	64	256	25.00%	81.25%	4.55%	38.38%
16777216	56	64	256	12.50%	78.13%	2.27%	36.90%
268435456	64	64	256	0.00%	75.00%	0.00%	35.42%
4294967296	72	64	256	-12.50%	71.88%	-2.27%	33.95%
68719476736	80	64	256	-25.00%	68.75%	-4.55%	32.47%
1.09951E+12	88	64	256	-37.50%	65.63%	-6.82%	31.00%
1.75922E+13	96	64	256	-50.00%	62.50%	-9.09%	29.52%
2.81475E+14	104	64	256	-62.50%	59.38%	-11.36%	28.04%
4.5036E+15	112	64	256	-75.00%	56.25%	-13.64%	26.57%
7.20576E+16	120	64	256	-87.50%	53.13%	-15.91%	25.09%
1.15292E+18	128	64	256	-100.00%	50.00%	-18.18%	23.62%
1.84467E+19	136	64	256	-112.50%	46.88%	-20.45%	22.14%
2.95148E+20	144	64	256	-125.00%	43.75%	-22.73%	20.66%
4.72237E+21	152	64	256	-137.50%	40.63%	-25.00%	19.19%
7.55579E+22	160	64	256	-150.00%	37.50%	-27.27%	17.71%
1.20893E+24	168	64	256	-162.50%	34.38%	-29.55%	16.24%
1.93428E+25	176	64	256	-175.00%	31.25%	-31.82%	14.76%
3.09485E+26	184	64	256	-187.50%	28.13%	-34.09%	13.28%
4.95176E+27	192	64	256	-200.00%	25.00%	-36.36%	11.81%
7.92282E+28	200	64	256	-212.50%	21.88%	-38.64%	10.33%
1.26765E+30	208	64	256	-225.00%	18.75%	-40.91%	8.86%
2.02824E+31	216	64	256	-237.50%	15.63%	-43.18%	7.38%
3.24519E+32	224	64	256	-250.00%	12.50%	-45.45%	5.90%
5.1923E+33	232	64	256	-262.50%	9.38%	-47.73%	4.43%
8.30767E+34	240	64	256	-275.00%	6.25%	-50.00%	2.95%
1.32923E+36	248	64	256	-287.50%	3.13%	-52.27%	1.48%
2.12676E+37	256	64	256	-300.00%	0.00%	-54.55%	0.00%
3.40282E+38	264	64	256	-312.50%	-3.13%	-56.82%	-1.48%

As is shown in the table the efficiency in the address space of DasManet quickly deteriorates as the number nodes increase when compared to IPv4. Many applications of MANETs would be less than 256 nodes at any one point in time. However, if a MANET were to be long lived it wouldn’t take very long for the number of addresses requested to exceed 256 nodes. Going from 256 to greater than 256 you loose about 20% of the efficiency on an averaged sized packet. It would definitely be advantageous to be able to reuse addresses in the network.

Efficient networks can be attained with less than 300 nodes [2]. Based on this if the average time to live for each of the 300 nodes was about 10 minuets which is a reasonable estimate for a MANET with address reuse the address would only need to be 12 bits long. However if this same network had no address reuse it would increase to a 16-bit address after only 2.5 hours. This justifies the need for attention paid to address reuse. In order to reuse addresses a scheme must be determined for doing this. We developed three proposals.

Keeping the network address size small is on reason to implement an address reuse alga rhythm however there is a much more pressing need for an address reuse alga rhythm. Each time two MANETs join our dynamic address allocation alga rhythm increments the address length by one. For instance a network that has a high address of 0100.0000.0000 would now have a high address of 1100.0000.0000 skipping 2048 possible addresses. This poses a major problem to the network. In this method it would only take 24 network joins between two networks of less than 16 nodes for this addressing alga rhythm to be less efficient than IPv4. This is based on calculation discussed above. Assuming an initial address length of 4 bits before the first network join.

This is a much more pressing reason to ensure that addresses will be reused if they are not assigned on the network.

3.1.1 Routing Table Dependant Address Reuse Algorithm

The first proposal was dependant on a network protocol that kept topology information of the entire network. If a protocol such as DVRP was used the addressing algorithm could simply use the DVRP routing table to find addresses that were no longer in use. DVRP is a routing alga rhythm that has a god’s eye view of the network. It proactively keeps track of all links to all nodes on the network. Since DVRP is a costly protocol that is not scalable in a MANET situation this is not a viable solution.

3.1.2 Sign off packet Address Reuse Algorithm

This method of reuse algorithm would require that when nodes know they are leaving the network they send a packet to adjacent nodes saying they are going to leave the network. When the adjacent nodes receive this packet they add that address to their available address cache. As long as nodes know they are leaving this is an efficient and quick method to reuse addresses. In a MANET it is not a good assumption that nodes will be able to announce when they are leaving. This is because links to the network may break due to movement or because a device may loose power with out knowing it is going to happen. This method, however, is simple to implement and requires little overhead. When an address is placed into the available address cache using this method it ensures that the address could only be reassigned to by any nodes that hear the goodbye packet. This increases the probability that the address will not be in use when an attachment agent tries to reassign the address to a new node. Another advantage to using this algorithm is seen when a node is repeatedly joining and leaving the network. If it is joining and leaving from the same location it is likely that it will receive the same address when a new address is assigned.

3.1.3 Aggressive Address Reuse Algorithm

The third proposal we developed uses local link state information to update a list of possible addresses. When a join beacon is detected an ACK or HELLO packet is sent to known adjacent nodes. If any of those nodes have left the network or have recently moved to an adjacent node and the link state has not been updated then a request for the address is sent. And the routing table for the attachment agent is updated. Any time a packet is received it ensures that the source address is not in the available cache. Any node that receives the address request packet and believes it is an adjoining node to the requested address must send a hello packet to make sure that that node is reachable before returning a denial of request packet. If a denial of request packet is not received then the attachment agent will assign the address to the joining node and an address conflict will occur. At this point it will be necessary to have a method for detecting and resolving conflicting addresses. All other nodes will make sure that that address doesn’t exist in the available address cache and will then disregard the packet. If a node that has that address receives the packet it will send a denial of the request for the address. Every node on the network must be kept in at least one other node’s routing table. This method prevents a request for address from having to reach the node directly to get a denial of request. Since every node must be in at least one other node’s routing table this, also ensures that all addresses will be reused with out the need for sending exit packets.

3.1.4 Active Address Reuse Algorithm

A fourth method would be a proactive available address cache. This would make use of link state information. While similar to the method that would make use of a global network topology view this method would be protocol independent. Since it is a requirement of most all hardware layers to keep the link state of adjacent nodes this algorithm would work. When it is detected that a node no longer has a route to an adjacent node the detecting node would send a packet to other adjacent nodes asking them if they can route the address of the node with a broken link. If they reply saying they can then the address is just removed from the link state table. If there is no reply that that node can be reached then that address is placed in the available address cache. In this manner the available address can be cached and reused. This algorithm would not work in a highly mobile network or a sparse network. This is because nodes could move multiple hops before a search is started for the node and the network would start to assign addresses of nodes that are still in the network. If the nodes are spare when a link is broken between two nodes it is unlikely that another adjacent node will be able to reach the node that is no longer available.

The last two methods are limited since an address will only be available at the node where the exit occurred. However, since addresses will tend to enter and exit the network at the same points this should maximize efficiency. They are also inefficient because double work will be done. When two nodes move apart they will both try to find each other and it is more likely for a moving node to not have nodes next to it that can reach it’s previous links. Neither of these algorithms are an affective solution.

One problem with the last suggested method is exactly the same problem that will occur in some situations with network join detection discussed later. Since it works on similar principles based on the assumption that nodes will move to adjacent nodes this method will add addresses to the available address cache when that address is really not available. Figure 1 can be used to explain this. If node F moves along path (1) from point I to point II it goes through a short period of no connectivity. This would be acceptable in a MANET. When E realizes it can no longer reach F it will look to its neighbor D to see if D can see F. Since D cannot see F, E will add F’s address to its available address table. Since this scenario is a relatively rare occurrence and the request to use F’s address will be denied by F this is a minor issue. However, it will cause more serious problems in the network join application.

3.1.5 Mobile agent address collector

A mobile agent address collector could be used to collect and redistribute unused addresses. This would keep the network from growing to large. A mobile agent is a small self-contained program that would be passed around the network from node to node to collect and distribute data. Each node would need to have the ability to create a mobile agent. The mobile agent would route its self through all the addresses in the network. As it passes through the network it will make note of all address it passes through. Beginning at node 0 it would route to 1 then to 2 and so on and so forth until it has either found a rout that cannot be completed or it reaches the highest known address in the network. There could be multiple agents on this route. Each time an agent came to a node it would update the available address cache on that node. It would also update its information with the most recent available information. Using this type of a scheme would keep all nodes in the network updated with current available address cache information. If each entry in the address cache had a time stamp the mobile agent could compare the known information for the given nodes in the address cache and either update its self or update the node appropriately.

This would be a good method of address reuse because the originally proposed scheme for a node entering the network does not have to change. It ensures that all unused addresses will get reused. It adds a minimal amount of network traffic because it is only one set of data per agent being passed from node to node. As it passes through the network all nodes adjacent to the path that the mobile agent is on will hear the agent and will be able to update their information. In this way the information will get updated much faster. Since node 0 and node 1 could be on opposite sides of the network the mobile agent may be able to update nodes 2,3,4,5,6, and 7 on its way across the network and would not have to revisit those nodes until the next time around.

3.2 Decrease Network Address Size

Since network size may vary greatly it is important to consider methods of reducing the address length as a network size decreases. During the day when most people are using their mobile devices the network size is likely to grow greater than 256 nodes however during the evening and night when fewer users would be using a MANET it would be nice to scale the address length back to 4 or 8 bits if the network were small enough to be handled by this address length. In order to simply scale back the address length addresses would have to be redefined at the lower end of the spectrum until all the addresses upper bits read zeros. This would be a difficult and expensive network task. It is basically unreasonable to do this. The method that we felt would be effective is to simply initiate a network rebuild where all nodes exit the network and then the network is rebuilt from scratch. The most preeminent problem with this is the down time required to rebuild a network. The other problem that is readily viewable with this approach is the method to tell when the network rebuild should occur. One method could use the proactive available address caching to figure out when a network rebuild is necessary. Once a node reached an available address cache threshold it could assume that other nodes have similar address cache tables and initiate a network rebuild.

Another method could use a bandwidth counter. If the bandwidth through a node reaches a low threshold for a sustained period of time it would initiate a network rebuild. The bandwidth counter algorithm could be augmented using another threshold that ensured that there were a minimum number of adjacent nodes. This would make sure that the node was an intermediary step between nodes. This would attempt to make sure that it was a better estimate of true bandwidth usage.

A third option may be to initiate a counter packet periodically, if network usage is not high, that is flooded through the network that counts the number of nodes currently in the network. The node that would initiate this request would meet both the conditions above. It would have a high amount of available cache packets and low bandwidth usage. It would initiate a flood and every node that received the packet would increment the number of nodes that the packet has reached and then forward the packet. If the packet reaches a certain value or has made to many stops the node will reply to the originator that too many hops have been made to justify a rebuild. If the originator receives no such reply it will initiate a rebuild. The decision to rebuild or not would be based on the maximum number of hops that needs to be made to flood the network. Assuming that the network is randomly distributed the maximum number of hops should correspond closely to network size. This would be a good indicator as to the actual network size. The point at which the request to not rebuild is reached would depend on the current size of the network. If the network was already at 8 bits the maximum number of hops before rebuild is canceled would be very small however if the network were at 16 bytes the maximum number of hops would be much larger. This is an area that would need significant research before it could be implemented effectively.

3.3 Security

This networking protocol would be susceptible to malicious activity. If someone wanted to bring this addressing scheme to a screeching halt they could set up a node that appeared to have a maximum address of millions of nodes then try to join that network with an existing network. The existing network would accept these new parameters and the address size could suddenly grow to 64 bits. This would destroy all advantages of using a scalable address length. If a network level security policy were to be put in place each node would have to do a security handshake before initiating a request for address. A handshake would increase the address request time significantly but it would also provide a much more secure networking environment. An alternative to this is to implement security on each mobile device. Device specific security would keep users from using resources other than network recourses on each node. The distributed security would require the initiator of the network to decide the security parameters of the network. This would cause further complications when networks joined each other. In general it is much more reliable and scalable to implement the security at the individual node level. This would keep users from abusing bandwidth availability by implementing security measures to keep their node from forwarding data.

3.4 Joining Networks

Joining networks is a major concern. Since there is no network authentication and nothing that identifies one network from another if two networks come together they must be able to distinguish from each other and expand the address scheme to include both networks (See Figure 2 for one node join). This should be broken into two parts. New network discovery and network combination.

3.4.1 New network discovery

A new network can be discovered using multiple methods. One method compares the address size, length, and highest address to discover new networks. A second method uses the known MAC address information to discover new nodes. A third method uses IP address conflict resolution.

The dynamic addressing scheme proposed in Boleng’s paper will proactively update its address length and maximum address information. If it sees packets with higher highest address information it will automatically update its packet header information to the higher number. If there is a significant difference between the current stored maximum address and the maximum address received on an incoming packet you can assume that the incoming packet is from a new network. This is not a very reliable method to detect new networks because there is no guarantee that an adjacent network will have a “significant” difference in the maximum address.

The second method of network detection is to use the address resolution protocol (ARP) to detect a new network. A MAC address to network address table would be kept for all nodes joining the network. When a node joins it will receive the current table from its attachment agent. And its network address and MAC address would be forwarded to all nodes in the network during the address request phase. This method requires greater overhead since the MAC address must be included with an address request. This also requires a significant amount of storage space on each node (40 bits per assigned address plus the current address size) to store this information. This information would only have to be transmitted during a node join. This means it wouldn’t reduce the advantage of using DasManet. This means it would require about 104 bits per node on the maximum size network. 104 bits is a significant amount of data. To consider a network of the size discussed earlier we will do an example of 300 nodes. This will require address lengths of 12 bits and a 40-bit MAC address. So 52 bits per entry and 300 nodes is 15600 bits or about 1.9 KB. This isn’t much but on a battery powered mobile device it is a significant amount of data to be storing just to check and see if a new network is joining or not. For this method, when a new node is detected within transmission range the MAC address and the network address of the new node are compared with the stored relationship between that address and MAC address. If the two do not match the two nodes initiate a network join.

Another method that also uses ARP requires much less overhead but at the same time is much less reliable. The ARP table is only kept for adjacent nodes or nodes that can be reached directly. When a new node is detected a request is sent to the detecting node's neighbors asking if the new node existed in their tables. This allows a couple of things. It allows the neighbors to update their route tables and also provides new network detection. If none of the neighbors reply that the new node came from them then it is assumed that the node came from a new network.

This, however, is not a reliable detection method for the following reason: Looking at Figure 1 Node F moves along path (1) from point I to point II it goes through a short period of no connectivity which would be acceptable in a mobile network. When it finally comes back into contact with node B node, B will see that it is a valid address on the network and will check with its neighbors to see if the MAC address is one that corresponds to that network address on the network since neither A nor C have F as a valid MAC address on the network B will initiate a new network command putting node F on a new network and incrementing the network address size with out need. On a sparsely populated network this could be a very common occurrence quickly increasing the address size of the network with out need.

In a real world situation this may occur often in an instance where nodes were traveling on parallel interstates where there were few nodes or no nodes on roads that connect the two interstates as nodes would disconnect upon leaving the interstate and reconnect to the other interstate when the get on the interstate they would create this situation. Perhaps another situation in a military instance where a troop is connected though peers to a larger network node that communicates back to a home command or base station and that troop leaves the connection to peers and heads towards the command station upon reaching the command station would initiate a new network with out need. This method has some benefits but it doesn’t provide a reliable solution to network detection.

Using address conflict resolution detection to detect new networks could be an effective method. More research is needed in the area of address conflict resolution. If when an address conflict is detected the node that has a conflicting address sends out a packet acknowledging the conflict then disconnects from the network and initiates a join. If the rate of conflicts reaches a high enough threshold then the network would assume that there are two networks that have come into contact with one another. This method is costly because it allows duplicate addresses for a period of time as well as requires that a good address conflict resolution method be in place.

3.4.2 Using a unique network identifier to resolve address conflicts

This method of network join detection would use the MAC address of the founding node as an identifier for the network. Part of the address assignment when each node is given an address includes the MAC address of the founding node. This will ensure that the network has a unique identifier. Then every time a new link is detected the node would as part of the HELLO packet send the network identification address. If the addresses didn’t match then a network join can be detected. Using a specific identifier for the network would be a very reliable method of detecting new networks with a minimal amount of added overhead. When it does add a little overhead by increasing the address assignment packet by 40 bits as well as increasing the network join packet by 40 bits. These packet types don’t account for much of the overall network traffic so it shouldn’t affect performance. This is a good solution because it is very reliable and adds little overhead.

3.4.3 Network update once new network is detected

When a new network is detected and the process to combine the two networks is initiated there are a couple of immediate problems. How do you distinguish between the two networks when you are informing one of the two networks that it is the lower address bit and the other is the higher address bit. And, how do you keep from losing addresses due to prepending when a network is combined (See Figure 3). We were able to come up with two ways to distinguish between the two networks that were not protocol dependant.

If the joining node floods a packet saying that the network needs to prepend a 0 or a 1 then both networks will receive that message unless the other side of the joining node realizes that it shouldn’t forward that packet because it has requested for the opposite action. Once a node receives a packet informing itself that it needs to go to a larger network it needs to add all addresses that are in between the current highest address and the new highest address to it available address cache before making the update. This will eliminate the loss of significant numbers of addresses.

The other possible implementation is dependant on the network identification discussed in section 3.4.2. Using this method the packet used to update both networks could be the same packet. It would contain the information that tells each network the new current highest address, addresses that can be added to the available address cache, and the founding address of the network. Of the two this is probably the most efficient algorithm. It will be the basis of our implementation.

3.5 Address Conflict Resolution

This is an area that needs further research. In this scheme we do our best to keep there from ever being an address conflict. Address conflicts can cause significant problems on any network. If an address conflict does occur or in the case of using address conflicts to detect network collisions there must be an address conflict resolution algorithm in place. The solution that would work well with the network collision detection that uses address conflict resolution is fairly simple [3]. When a node receives a packet that had to be requested but the node did not request the packet the node knows that there is an address conflict. When this conflict occurs that node will flood a packet acknowledging the conflict. Hopefully, this packet will reach the conflicting node before the conflicting node realizes that there is a conflicting address. The acknowledgment packet is used as a counter to detect network collisions. Once this packet has been flooded the node drops its connection and initiates a join beacon. This eliminates the duplicate address and quickly establishes a clean link to the violated node.

4 Implementation

The implementation consists of primarily two parts, the DasPacket type and the DasAgent.

The DasPacket contains a DasManet specific header, hdr_das. It is used for all communication messages between DasAgents. This header contains information on packet type, founding node id, the current highest address, highDasAdr.

The DasAgent handles all DasPacket types. The different DasPacketTypes are now describe as they current work.

The DAS_AGENT_REQ_PACKET is broadcast by a new node looking to attach to the network. Current this is done with TCL call, "beacon n", where n is 0 for the founding node.

A DAS_AGENT_RESPONSE packet is a reply sent by all agents who hear the DAS_AGENT_REQ_PACKET. Some more information about the node could be included, so a joining node may make a more informed decision.

A joining node will hear a DAS_AGENT_REQ_PACKET from all neighbors and could build a neighbor list at this point. A single DAS_AGENT_ACCEPT packet must be sent to the neighbor of choice. The first node heard is currently the one selected. Perhaps without using a jitter this would help to select the closest or strongest node.

When a node receives the DAS_AGENT_ACCEPT, he is responsible for providing a valid address to the joining node. She will increment her highDasAdr and flood it with a DAS_ADDR_REQ_PACKET. This packet will propagate the highDasAdr to all nodes with DasManet addresses. One their highDasAdr in a reply with a DAS_ADDR_DENY_PACKET, if anyone should notice their highDasAdr is larger than that of the DAS_ADDR_REQ_PACKET flood.

When a DAS_ADDR_DENY_PACKET is received the highDasAdr if the node is updated with the highDasAdr of the DAS_ADDR_DENY_PACKET. This new address will then be flooded as before with a new DAS_ADDR_REQ_PACKET. One might want to wait to hear if any other DAS_ADDR_DENY_PACKETs are heard before stating the new flood.

Only after a DAS_ADDR_REQ_TIMEOUT amount of time should the attachment node send a DAS_ADDR_ASSIGN_PACKET with its highDasAdr. The joining node will receive this packet and set its dasAddr.

Output from packet traffic has been sent to cmu-trace in the standard way. Unfortunately, it has been far from useful, without the awk scripting to re format it. Verbosity can be set in TCL which will enable all debug output. Variable levels of verbosity are not handled, but for development it hasn't been a problem. All information is easily extracted with a "grep" command. Some useful search strings might be, node, DAS, AGENT, or ADDR.

5 Data metrics

Metrics calculated are time to get address and time to attach. The time is logged when the initial join request is sent. This time is then subtracted form the current time to determine each value. The time to attach is calculated just before sending the DAS_AGENT_ACCEPT packet. The time to get address will be calculated when the joining node receives the DAS_ADDR_ASSIGN_PACKET.

If address reuse were added, a metric for how often would be useful. Another valuable feature would be to collect the difference in packets sizes due to the smaller address space.

This data should allow us to make conclusions as to what are the best standards for our delays and time outs. It will also allow us to prove the efficiency gains by using this algorithm.

Summary

In implementing Jeff Boleng’s proposal for dynamic address assignment with variable length addressing we considered many areas where improvements could be made. These areas included address reuse, decrease network address size, security, joining networks, and address conflict resolution. Basic solutions and preliminary ideas were discussed for each of those points. We have implemented a basic set of functionality that is a good basis for continuing future work on DasManet.

References

MPinner : Essays and Publications : DASMANET