Transcript LANMAR-Implementatio..

LANMAR for IPv6
Jason Chen
Teresa Breyer
Yeng-Zhong Lee
Agenda
Review of LANMAR
 IPv4 and IPv6 Addressing
 LANMAR implementation
 Problems faced
 Demonstration

LANMAR



Combines features of Fisheye State Routing
(FSR) and Landmark routing.
Each set of nodes that moves as group forms
a logical subnet.
Each subnet elects a landmark.
Landmark
Logical Subnet
LANMAR




Each node has unique logical identifier.
Each identifier has subnet and host field.
Host field is unique in subnet.
Each node stores the following information:
For each destination within fisheye scope:
 Link
State
 Time Stamp
For each destination within fisheye scope
and for each Landmark node:
 Next
Hop
 Distance
LANMAR Fisheye Scope
Nodes exchange Link State only with their
neighbors.
 Update rate decreases as hop distance
increases.
 Routes within Fisheye scope are accurate.
 As hop distance increases routes
accuracy decreases.

LANMAR Fisheye Scope Cont.
Difference to FSR:
LANMAR routing table includes only
nodes within scope and landmark nodes.
⇒ Improves Scalability by reducing
Routing Table size.
 Typically all members in logical subnet are
within fisheye scope.

LANMAR Routing
•
A packet to destination within neighbor scope
is routed directly using local tables.
• A packet to destination out of scope is routed
to corresponding Landmark using the subnet
field of destination.
• Once the packet is in scope of destination,
the direct route is found in local tables.
• Packet does not need to pass through
Landmark.
LANMAR Routing Cont.
•
•
•
•
•
Node address = {subnet ID, Host ID}
Lookup local routing table to locate destination.
If successful: Send packet directly.
If failure: Look up landmark table to find destination subnet 
LM1.
Send a packet toward LM1.
LM1
Landmark
Logical Subnet
LM2
LM3
destination
source
local routing
Long haul routing
IPv4
32 bits
 Originally 4 classes of addresses:
 Shortage of Group A addresses

A
0 network
B
10
C
110
D
1110
1.0.0.0 to
127.255.255.255
host
network
128.0.0.0 to
191.255.255.255
host
network
multicast address
host
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
IPv4
32 bits

Header:
head. type of
ver len service
Total length
fragment
16-bit identifier flgs
offset
time to
IP header
protocol
live
checksum
source IP address
destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
20 bytes
IPv6


Motivation: 32-bit address space exhaustion
128 bit
 Fragmentation fields moved out of base header.
 IP options moved out of base header.
 Header Length field eliminated
 Header Checksum eliminated.
 Type of Service field eliminated.
 Time to Live Hop Limit, Protocol  Next Header
 Precedence  Priority, added Flow Label field
 Length field excludes IPv6 header.
IPv6 Cont.

Header: fixed 40 bytes length.
Version Priority
Payload Length
Flow Label
Next Header
Source Address (16 bytes, 128 bits)
Destination Address (16 bytes)
Hop Limit
IPv6 Cont.




How IPv6 addresses look like:
2128-1: 0xffffffffffffffffffffffffffffffff
Separator after 16 bits, omit leading 0x.
2128-1: ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
fe80:0000:0000:0000:0202:2dff:fe2e:3ad6
One sequence of adjacent 16 bit blocks of 0’s
can be omitted.
fe80::0202:2dff:fe2e:3ad6
Leading zeros of each block can be omitted.
fe80::202:2dff:fe2e:3ad6
IPv6 Cont.
3 types of addresses.
 Unicast: identifies single interface.
 Anycast: identifies a set of interfaces.
 Multicast: identifies a group of interfaces
replaces broadcast addresses in IPv4
prefix: 1111 1111 or ff
for example link scope: ff02: …

LANMAR Implementation




2 complementary and cooperating routing schemes,
3 threads:
A local “myopic” proactive routing scheme (we used
RIP) that operates within limited scope centered at
each node and exchange route information about
nodes up to only a few hops (Fisheye Scope) ⇒ one
thread for sending RIP messages.
A long haul distance vector routing scheme that
propagates the elected landmark of each subnet and
the path to it into entire network ⇒ another thread for
sending Landmark messages.
Common thread for receiving messages.
LANMAR Implementation

Advertisement messages
 Proactive routing protocol
 Periodic routing update message is sent.
 LANMAR routing control packet
 <LM_Address, LM_NextHop, LM_Distance, LM_Members,
Seq#>
 Landmark routes advertised to all nodes.
 Local routing control packet
 <Address, NextHop, Distance>
 Routes only advertised to nodes within its scope.
LANMAR Implementation

Message process
 A subnet
mask is used to extract the group ID
from a node’s IP address.
 Each group is a logical subnet.
 Landmark election is performed only among
nodes in the same LANMAR group.
 Local scope: RIP
LANMAR Subnet Masks

IPv4:
LANMAR Group ID
Node ID
x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x
Subnet
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0
Mask

IPv6:
48 bits
Network ID
Subnet
Mask
16 bits
64 bits
Group ID Node ID
00000000………0000000 111…11
000000……………………000000
LANMAR Routing Table
Routing table management
 Unicast Routing Table
 Stores routing information for all unicast routing
protocols running on router.
 Routing Table has 2 sub tables
 Local routing table is flat without the concept of group
or subnet.
 Landmark routing table keeps only one entry from
each group or subnet.
LANMAR Routing Table Cont.
Local routing table
Dest.
Prefix
Next Hop
Met
fe80:0:0:1333::3ad6
128
::
0
fe80:0:0:1444::4352
128
fe80:0:0:1333::cf49
2
Landmark routing table
Landmark Address
Prefix
Next Hop
Metric
0:0:0:1333::
64
fe80:0:0:1333::cf49
1
0:0:0:1444::
64
fe80:0:0:1444::4352
1
Challenges in
porting IPV4
LANMAR to IPV6
Data Structure
Selected examples:
struct sockaddr_in6 {
sa_family_t sin6_family; /*AF_INET6*/
in_port_t sin6_port; /*Port number*/
uint32_t sin6_flowinfo; /*IPv6 traffic class
and flow information*/
struct in6_addr sin6_addr; /*IPv6 address */
uint32_t sin6_scope_id; /*Set of interfaces for
a scope*/
}
instead of
struct sockaddr {
sa_family_t sin_family; /*AF_INET*/
in_port_t sin_port; /*Port number*/
struct in_addr sin_addr; /*IP address*/
}
Data Structures Cont.
struct in6_addr {
uint8_t s6_addr[16];
}
where
typedef unsigned char uint8_t;
instead of
struct in_addr {
in_addr_t s_addr;
}
where
typedef uint32_t in_addr_t;
typedef unsigned int uint32_t;
⇒ Write library to compare, assign, logical &, and logical | uint8_t
arrays.
Uintfunc Library
void uintcmp(uint8_t array1[], const uint8_t
array2[], int n);
int uintcmp(const uint8_t array1[], const uint8_t
array2[], int n);
void uintand(uint8_t result[], const uint8_t
array1[], const uint8_t array2[], int n);
void uintor(uint8_t result[], const uint8_t
array1[], const uint8_t array2[], int n);
int uintzero(const uint8_t array[], int n);
Syntax for IPv6

Address and protocol family constants:
AF_INET and PF_INET
Replace with:
AF_INET6 IPv6 address family.
PF_INET6 IPv6 protocol family.

Numerous other syntax changes.
Substituting IPv4 functions with newer
IPv6 versions
•
gethostbyname(): retrieves the network host entry referenced by a
host name with an IPv4 address
Replace with:
gethostbyname2(): retrieves the network host entry referenced by
a host name and its address family, which will be AF_INET6
• inet_addr(): interprets a character string representing an address
in Internet ``dot'' notation (IPv4) and returns a value suitable for use
as an Internet address
Replace with:
inet_pton(): performs the same operation for both IPv4 and IPv6
address notations
• inet_ntoa(): interprets an IPv4 internet address and converts it to a
character string.
Replace with:
inet_ntop(): performs the same operation for both IPv4 and IPv6
addresses.
Masks

IPv4
SUBNET_MASK = 255.255.255.0
LANDMARK_MASK = 255.255.255.0
NORMAL_MASK = 255.255.255.255

IPv6
SUBNET_MASK6 = 0000:0000:0000:ffff::
LANDMARK_MASK6 = 0000:0000:0000:ffff::
NORMAL_MASK6 = ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
REVERSE_MASK6 = ffff:ffff:ffff::ffff:ffff:ffff:ffff
Routing Table

Kernel IPv4 Routing
Table (route)








Destination
Gateway
Genmask
Flags
Metric
Ref
Use
Iface

Kernel IPv6 Routing
Table (route –A inet6)








Destination/Prefix
Source/Prefix
Next Hop
Flags
Metric
Ref
Use
Iface
⇒ change part of code updating routing table (adding,
deleting, and searching routes)
Routing Table Cont.
Change part of code updating routing table
(adding, deleting, searching for routes).
 Problem: new field Prefix.
 Calculate Prefix for group entry via
LANDMARK_MASK6.
 For unicast routes prefix = 128.

Demonstration