A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
ipv6-address-generator.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2008 University of Washington
3 * Copyright (c) 2011 Atishay Jain
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18
20
21#include "ns3/abort.h"
22#include "ns3/assert.h"
23#include "ns3/log.h"
24#include "ns3/simulation-singleton.h"
25
26#include <list>
27
28namespace ns3
29{
30
31NS_LOG_COMPONENT_DEFINE("Ipv6AddressGenerator");
32
43{
44 public:
47
58 void Init(const Ipv6Address net, const Ipv6Prefix prefix, const Ipv6Address interfaceId);
59
73
83 Ipv6Address GetNetwork(const Ipv6Prefix prefix) const;
84
91 void InitAddress(const Ipv6Address interfaceId, const Ipv6Prefix prefix);
92
102 Ipv6Address GetAddress(const Ipv6Prefix prefix) const;
103
113 Ipv6Address NextAddress(const Ipv6Prefix prefix);
114
118 void Reset();
119
130 bool AddAllocated(const Ipv6Address addr);
131
138 bool IsAddressAllocated(const Ipv6Address addr);
139
147 bool IsNetworkAllocated(const Ipv6Address addr, const Ipv6Prefix prefix);
148
152 void TestMode();
153
154 private:
155 static const uint32_t N_BITS = 128;
156 static const uint32_t MOST_SIGNIFICANT_BIT = 0x80;
157
163 uint32_t PrefixToIndex(Ipv6Prefix prefix) const;
164
169 {
170 public:
171 uint8_t prefix[16];
173 uint8_t network[16];
174 uint8_t addr[16];
175 uint8_t addrMax[16];
176 };
177
179
183 class Entry
184 {
185 public:
186 uint8_t addrLow[16];
187 uint8_t addrHigh[16];
188 };
189
190 std::list<Entry> m_entries;
192 bool m_test;
193};
194
196 : m_entries(),
197 m_base("::1"),
198 m_test(false)
199{
200 NS_LOG_FUNCTION(this);
201 Reset();
202}
203
204void
206{
207 NS_LOG_FUNCTION(this);
208
209 uint8_t prefix[16] = {0};
210
211 for (uint32_t i = 0; i < N_BITS; ++i)
212 {
213 for (uint32_t j = 0; j < 16; ++j)
214 {
215 m_netTable[i].prefix[j] = prefix[j];
216 }
217 for (uint32_t j = 0; j < 15; ++j)
218 {
219 prefix[15 - j] >>= 1;
220 prefix[15 - j] |= (prefix[15 - j - 1] & 1);
221 }
222 prefix[0] |= MOST_SIGNIFICANT_BIT;
223 for (uint32_t j = 0; j < 15; ++j)
224 {
225 m_netTable[i].network[j] = 0;
226 }
227 m_netTable[i].network[15] = 1;
228 for (uint32_t j = 0; j < 15; ++j)
229 {
230 m_netTable[i].addr[j] = 0;
231 }
232 m_netTable[i].addr[15] = 1;
233 for (uint32_t j = 0; j < 16; ++j)
234 {
235 m_netTable[i].addrMax[j] = ~prefix[j];
236 }
237 m_netTable[i].shift = N_BITS - i;
238 }
239 m_entries.clear();
240 m_base = Ipv6Address("::1");
241 m_test = false;
242}
243
245{
246 NS_LOG_FUNCTION(this);
247}
248
249void
251 const Ipv6Prefix prefix,
252 const Ipv6Address interfaceId)
253{
254 NS_LOG_FUNCTION(this << net << prefix << interfaceId);
255
256 m_base = interfaceId;
257 //
258 // We're going to be playing with the actual bits in the network and prefix so
259 // pull them out into ints.
260 //
261 uint8_t prefixBits[16];
262 prefix.GetBytes(prefixBits);
263 uint8_t netBits[16];
264 net.GetBytes(netBits);
265 uint8_t interfaceIdBits[16];
266 interfaceId.GetBytes(interfaceIdBits);
267 //
268 // Some quick reasonableness testing.
269 //
270 // Convert the network prefix into an index into the network number table.
271 // The network number comes in to us properly aligned for the prefix and so
272 // needs to be shifted right into the normalized position (lowest bit of the
273 // network number at bit zero of the int that holds it).
274 //
275 uint32_t index = PrefixToIndex(prefix);
276 NS_LOG_DEBUG("Index " << index);
277 uint32_t a = m_netTable[index].shift / 8;
278 uint32_t b = m_netTable[index].shift % 8;
279 for (int32_t j = 15 - a; j >= 0; j--)
280 {
281 m_netTable[index].network[j + a] = netBits[j];
282 }
283 for (uint32_t j = 0; j < a; j++)
284 {
285 m_netTable[index].network[j] = 0;
286 }
287 for (uint32_t j = 15; j >= a; j--)
288 {
289 m_netTable[index].network[j] = m_netTable[index].network[j] >> b;
290 m_netTable[index].network[j] |= m_netTable[index].network[j - 1] << (8 - b);
291 }
292 for (int32_t j = 0; j < 16; j++)
293 {
294 m_netTable[index].addr[j] = interfaceIdBits[j];
295 }
296}
297
300{
301 NS_LOG_FUNCTION(this);
302 uint8_t nw[16] = {0};
303 uint32_t index = PrefixToIndex(prefix);
304 uint32_t a = m_netTable[index].shift / 8;
305 uint32_t b = m_netTable[index].shift % 8;
306 for (uint32_t j = 0; j < 16 - a; ++j)
307 {
308 nw[j] = m_netTable[index].network[j + a];
309 }
310 for (uint32_t j = 0; j < 15; j++)
311 {
312 nw[j] = nw[j] << b;
313 nw[j] |= nw[j + 1] >> (8 - b);
314 }
315 nw[15] = nw[15] << b;
316
317 return Ipv6Address(nw);
318}
319
322{
323 NS_LOG_FUNCTION(this);
324
325 uint32_t index = PrefixToIndex(prefix);
326 // Reset the base to what was initialized
327 uint8_t interfaceIdBits[16];
328 m_base.GetBytes(interfaceIdBits);
329 for (int32_t j = 0; j < 16; j++)
330 {
331 m_netTable[index].addr[j] = interfaceIdBits[j];
332 }
333
334 for (int32_t j = 15; j >= 0; j--)
335 {
336 if (m_netTable[index].network[j] < 0xff)
337 {
338 ++m_netTable[index].network[j];
339 break;
340 }
341 else
342 {
343 ++m_netTable[index].network[j];
344 }
345 }
346
347 uint8_t nw[16];
348 uint32_t a = m_netTable[index].shift / 8;
349 uint32_t b = m_netTable[index].shift % 8;
350 for (uint32_t j = 0; j < 16 - a; ++j)
351 {
352 nw[j] = m_netTable[index].network[j + a];
353 }
354 for (uint32_t j = 16 - a; j < 16; ++j)
355 {
356 nw[j] = 0;
357 }
358 for (uint32_t j = 0; j < 15; j++)
359 {
360 nw[j] = nw[j] << b;
361 nw[j] |= nw[j + 1] >> (8 - b);
362 }
363 nw[15] = nw[15] << b;
364
365 return Ipv6Address(nw);
366}
367
368void
370{
371 NS_LOG_FUNCTION(this);
372
373 uint32_t index = PrefixToIndex(prefix);
374 uint8_t interfaceIdBits[16];
375 interfaceId.GetBytes(interfaceIdBits);
376
377 for (uint32_t j = 0; j < 16; ++j)
378 {
379 m_netTable[index].addr[j] = interfaceIdBits[j];
380 }
381}
382
385{
386 NS_LOG_FUNCTION(this);
387
388 uint32_t index = PrefixToIndex(prefix);
389
390 uint8_t nw[16] = {0};
391 uint32_t a = m_netTable[index].shift / 8;
392 uint32_t b = m_netTable[index].shift % 8;
393 for (uint32_t j = 0; j < 16 - a; ++j)
394 {
395 nw[j] = m_netTable[index].network[j + a];
396 }
397 for (uint32_t j = 0; j < 15; j++)
398 {
399 nw[j] = nw[j] << b;
400 nw[j] |= nw[j + 1] >> (8 - b);
401 }
402 nw[15] = nw[15] << b;
403 for (uint32_t j = 0; j < 16; j++)
404 {
405 nw[j] |= m_netTable[index].addr[j];
406 }
407
408 return Ipv6Address(nw);
409}
410
413{
414 NS_LOG_FUNCTION(this);
415
416 uint32_t index = PrefixToIndex(prefix);
417
418 uint8_t ad[16] = {0};
419 uint32_t a = m_netTable[index].shift / 8;
420 uint32_t b = m_netTable[index].shift % 8;
421 for (uint32_t j = 0; j < 16 - a; ++j)
422 {
423 ad[j] = m_netTable[index].network[j + a];
424 }
425 for (uint32_t j = 0; j < 15; j++)
426 {
427 ad[j] = ad[j] << b;
428 ad[j] |= ad[j + 1] >> (8 - b);
429 }
430 ad[15] = ad[15] << b;
431 for (uint32_t j = 0; j < 16; j++)
432 {
433 ad[j] |= m_netTable[index].addr[j];
434 }
435 Ipv6Address addr = Ipv6Address(ad);
436
437 for (int32_t j = 15; j >= 0; j--)
438 {
439 if (m_netTable[index].addr[j] < 0xff)
440 {
441 ++m_netTable[index].addr[j];
442 break;
443 }
444 else
445 {
446 ++m_netTable[index].addr[j];
447 }
448 }
449
450 //
451 // Make a note that we've allocated this address -- used for address collision
452 // detection.
453 //
454 AddAllocated(addr);
455 return addr;
456}
457
458bool
460{
461 NS_LOG_FUNCTION(this << address);
462
463 uint8_t addr[16];
464 address.GetBytes(addr);
465
466 std::list<Entry>::iterator i;
467
468 for (i = m_entries.begin(); i != m_entries.end(); ++i)
469 {
470 NS_LOG_LOGIC("examine entry: " << Ipv6Address((*i).addrLow) << " to "
471 << Ipv6Address((*i).addrHigh));
472 //
473 // First things first. Is there an address collision -- that is, does the
474 // new address fall in a previously allocated block of addresses.
475 //
476 if (!(Ipv6Address(addr) < Ipv6Address((*i).addrLow)) &&
477 ((Ipv6Address(addr) < Ipv6Address((*i).addrHigh)) ||
478 (Ipv6Address(addr) == Ipv6Address((*i).addrHigh))))
479 {
481 "Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address(addr));
482 if (!m_test)
483 {
485 "Ipv6AddressGeneratorImpl::Add(): Address Collision: " << Ipv6Address(addr));
486 }
487 return false;
488 }
489 //
490 // If the new address is less than the lowest address in the current
491 // block and can't be merged into to the current block, then insert it
492 // as a new block before the current block.
493 //
494 uint8_t taddr[16];
495 for (uint32_t j = 0; j < 16; j++)
496 {
497 taddr[j] = (*i).addrLow[j];
498 }
499 taddr[15] -= 1;
500 if (Ipv6Address(addr) < Ipv6Address(taddr))
501 {
502 break;
503 }
504 //
505 // If the new address fits at the end of the block, look ahead to the next
506 // block and make sure it's not a collision there. If we won't overlap,
507 // then just extend the current block by one address. We expect that
508 // completely filled network ranges will be a fairly rare occurrence,
509 // so we don't worry about collapsing address range blocks.
510 //
511 for (uint32_t j = 0; j < 16; j++)
512 {
513 taddr[j] = (*i).addrLow[j];
514 }
515 taddr[15] += 1;
516 if (Ipv6Address(addr) == Ipv6Address(taddr))
517 {
518 std::list<Entry>::iterator j = i;
519 ++j;
520
521 if (j != m_entries.end())
522 {
523 if (Ipv6Address(addr) == Ipv6Address((*j).addrLow))
524 {
525 NS_LOG_LOGIC("Ipv6AddressGeneratorImpl::Add(): "
526 "Address Collision: "
527 << Ipv6Address(addr));
528 if (!m_test)
529 {
530 NS_FATAL_ERROR("Ipv6AddressGeneratorImpl::Add(): Address Collision: "
531 << Ipv6Address(addr));
532 }
533 return false;
534 }
535 }
536
537 NS_LOG_LOGIC("New addrHigh = " << Ipv6Address(addr));
538 for (uint32_t j = 0; j < 16; j++)
539 {
540 (*i).addrHigh[j] = addr[j];
541 }
542 return true;
543 }
544 //
545 // If we get here, we know that the next lower block of addresses
546 // couldn't have been extended to include this new address since the
547 // code immediately above would have been executed and that next lower
548 // block extended upward. So we know it's safe to extend the current
549 // block down to include the new address.
550 //
551 for (uint32_t j = 0; j < 16; j++)
552 {
553 taddr[j] = (*i).addrLow[j];
554 }
555 taddr[15] -= 1;
556 if ((Ipv6Address(addr) == Ipv6Address(taddr)))
557 {
558 NS_LOG_LOGIC("New addrLow = " << Ipv6Address(addr));
559 for (uint32_t j = 0; j < 16; j++)
560 {
561 (*i).addrLow[j] = addr[j];
562 }
563 return true;
564 }
565 }
566
567 Entry entry;
568 for (uint32_t j = 0; j < 16; j++)
569 {
570 entry.addrLow[j] = entry.addrHigh[j] = addr[j];
571 }
572 m_entries.insert(i, entry);
573 return true;
574}
575
576bool
578{
579 NS_LOG_FUNCTION(this << address);
580
581 uint8_t addr[16];
582 address.GetBytes(addr);
583
584 std::list<Entry>::iterator i;
585
586 for (i = m_entries.begin(); i != m_entries.end(); ++i)
587 {
588 NS_LOG_LOGIC("examine entry: " << Ipv6Address((*i).addrLow) << " to "
589 << Ipv6Address((*i).addrHigh));
590
591 if (!(Ipv6Address(addr) < Ipv6Address((*i).addrLow)) &&
592 ((Ipv6Address(addr) < Ipv6Address((*i).addrHigh)) ||
593 (Ipv6Address(addr) == Ipv6Address((*i).addrHigh))))
594 {
595 NS_LOG_LOGIC("Ipv6AddressGeneratorImpl::IsAddressAllocated(): Address Collision: "
596 << Ipv6Address(addr));
597 return false;
598 }
599 }
600 return true;
601}
602
603bool
605{
606 NS_LOG_FUNCTION(this << address << prefix);
607
609 address == address.CombinePrefix(prefix),
610 "Ipv6AddressGeneratorImpl::IsNetworkAllocated(): network address and mask don't match "
611 << address << " " << prefix);
612
613 std::list<Entry>::iterator i;
614
615 for (i = m_entries.begin(); i != m_entries.end(); ++i)
616 {
617 NS_LOG_LOGIC("examine entry: " << Ipv6Address((*i).addrLow) << " to "
618 << Ipv6Address((*i).addrHigh));
619 Ipv6Address low = Ipv6Address((*i).addrLow);
620 Ipv6Address high = Ipv6Address((*i).addrHigh);
621
622 if (address == low.CombinePrefix(prefix) || address == high.CombinePrefix(prefix))
623 {
625 "Ipv6AddressGeneratorImpl::IsNetworkAllocated(): Network already allocated: "
626 << address << " " << low << "-" << high);
627 return false;
628 }
629 }
630 return true;
631}
632
633void
635{
636 NS_LOG_FUNCTION(this);
637 m_test = true;
638}
639
642{
643 //
644 // We've been given a prefix that has a higher order bit set for each bit of
645 // the network number. In order to translate this prefix into an index,
646 // we just need to count the number of zero bits in the prefix. We do this
647 // in a loop in which we shift the prefix right until we find the first
648 // nonzero bit. This tells us the number of zero bits, and from this we
649 // infer the number of nonzero bits which is the number of bits in the prefix.
650 //
651 // We use the number of bits in the prefix as the number of bits in the
652 // network number and as the index into the network number state table.
653 //
654 uint8_t prefixBits[16];
655 prefix.GetBytes(prefixBits);
656
657 for (int32_t i = 15; i >= 0; --i)
658 {
659 for (uint32_t j = 0; j < 8; ++j)
660 {
661 if (prefixBits[i] & 1)
662 {
663 uint32_t index = N_BITS - (15 - i) * 8 - j;
664 NS_ABORT_MSG_UNLESS(index > 0 && index < N_BITS,
665 "Ip64AddressGenerator::PrefixToIndex(): Illegal Prefix");
666 return index;
667 }
668 prefixBits[i] >>= 1;
669 }
670 }
671 NS_ASSERT_MSG(false, "Ipv6AddressGenerator::PrefixToIndex(): Impossible");
672 return 0;
673}
674
675void
677 const Ipv6Prefix prefix,
678 const Ipv6Address interfaceId)
679{
680 NS_LOG_FUNCTION(net << prefix << interfaceId);
681
682 SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->Init(net, prefix, interfaceId);
683}
684
687{
688 NS_LOG_FUNCTION(prefix);
689
690 return SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->NextNetwork(prefix);
691}
692
695{
696 NS_LOG_FUNCTION(prefix);
697
698 return SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->GetNetwork(prefix);
699}
700
701void
703{
704 NS_LOG_FUNCTION(interfaceId << prefix);
705
706 SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->InitAddress(interfaceId, prefix);
707}
708
711{
712 NS_LOG_FUNCTION(prefix);
713
714 return SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->GetAddress(prefix);
715}
716
719{
720 NS_LOG_FUNCTION(prefix);
721
722 return SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->NextAddress(prefix);
723}
724
725void
727{
729
731}
732
733bool
735{
736 NS_LOG_FUNCTION(addr);
737
738 return SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->AddAllocated(addr);
739}
740
741bool
743{
744 NS_LOG_FUNCTION(addr);
745
746 return SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->IsAddressAllocated(addr);
747}
748
749bool
751{
752 NS_LOG_FUNCTION(addr << prefix);
753
754 return SimulationSingleton<Ipv6AddressGeneratorImpl>::Get()->IsNetworkAllocated(addr, prefix);
755}
756
757void
759{
761
763}
764
765} // namespace ns3
static void Init(const Ipv6Address net, const Ipv6Prefix prefix, const Ipv6Address interfaceId="::1")
Initialise the base network and interfaceId for the generator.
static void TestMode()
Used to turn off fatal errors and assertions, for testing.
static Ipv6Address NextAddress(const Ipv6Prefix prefix)
Allocate the next Ipv6Address for the configured network and prefix.
static Ipv6Address GetNetwork(const Ipv6Prefix prefix)
Get the current network of the given Ipv6Prefix.
static void InitAddress(const Ipv6Address interfaceId, const Ipv6Prefix prefix)
Set the interfaceId for the given Ipv6Prefix.
static bool IsNetworkAllocated(const Ipv6Address addr, const Ipv6Prefix prefix)
Check if a network has already allocated addresses.
static bool AddAllocated(const Ipv6Address addr)
Add the Ipv6Address to the list of IPv6 entries.
static Ipv6Address GetAddress(const Ipv6Prefix prefix)
Get the Ipv6Address that will be allocated upon NextAddress ()
static Ipv6Address NextNetwork(const Ipv6Prefix prefix)
Get the next network according to the given Ipv6Prefix.
static bool IsAddressAllocated(const Ipv6Address addr)
Check the Ipv6Address allocation in the list of IPv6 entries.
static void Reset()
Reset the networks and Ipv6Address to zero.
This class holds the allocated addresses.
uint8_t addrLow[16]
the lowest allocated address
uint8_t addrHigh[16]
the highest allocated address
This class holds the state for a given network.
Implementation class of Ipv6AddressGenerator This generator assigns addresses sequentially from a pro...
void Reset()
Reset the networks and Ipv6Address to zero.
static const uint32_t MOST_SIGNIFICANT_BIT
MSB set to 1.
NetworkState m_netTable[N_BITS]
the available networks
bool AddAllocated(const Ipv6Address addr)
Add the Ipv6Address to the list of IPv6 entries.
Ipv6Address GetAddress(const Ipv6Prefix prefix) const
Get the Ipv6Address that will be allocated upon NextAddress ()
uint32_t PrefixToIndex(Ipv6Prefix prefix) const
Create an index number for the prefix.
Ipv6Address NextNetwork(const Ipv6Prefix prefix)
Get the next network according to the given Ipv6Prefix.
void TestMode()
Used to turn off fatal errors and assertions, for testing.
std::list< Entry > m_entries
contained of allocated addresses
static const uint32_t N_BITS
the number of bits in the address
void Init(const Ipv6Address net, const Ipv6Prefix prefix, const Ipv6Address interfaceId)
Initialise the base network and interfaceId for the generator.
void InitAddress(const Ipv6Address interfaceId, const Ipv6Prefix prefix)
Set the interfaceId for the given Ipv6Prefix.
bool IsNetworkAllocated(const Ipv6Address addr, const Ipv6Prefix prefix)
Check if a network has already allocated addresses.
Ipv6Address GetNetwork(const Ipv6Prefix prefix) const
Get the current network of the given Ipv6Prefix.
bool IsAddressAllocated(const Ipv6Address addr)
Check the Ipv6Address allocation in the list of IPv6 entries.
Ipv6Address NextAddress(const Ipv6Prefix prefix)
Allocate the next Ipv6Address for the configured network and prefix.
Describes an IPv6 address.
Definition: ipv6-address.h:49
void GetBytes(uint8_t buf[16]) const
Get the bytes corresponding to the address.
Ipv6Address CombinePrefix(const Ipv6Prefix &prefix) const
Combine this address with a prefix.
Describes an IPv6 prefix.
Definition: ipv6-address.h:455
void GetBytes(uint8_t buf[16]) const
Get the bytes corresponding to the prefix.
static T * Get()
Get a pointer to the singleton instance.
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition: assert.h:86
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if a condition is false, with a message.
Definition: abort.h:144
#define NS_FATAL_ERROR(msg)
Report a fatal error with a message and terminate.
Definition: fatal-error.h:179
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:268
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:282
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Every class exported by the ns3 library is enclosed in the ns3 namespace.