LANMAR-Implementatio..
Download
Report
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