Internet DRAFT - draft-kakkar-srini-ospf-multi-links
draft-kakkar-srini-ospf-multi-links
Internet Draft OSPF Multi Links December 2005
Network Working Group
Internet Draft Nitin Kakkar
K.L Srini
Document: draft-kakkar-srini-ospf-multi-link- Huawei
00.txt Technologies
Bangalore
Expires: June 2006 December 2005
OSPF Multiple Interface Optimizations
Status of this Memo
This document is a submission by the author to IETF Network Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the nitink@huawei.com.
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
OSPF is a link state IGP routing protocol, but it does not utilizes
multiple links between adjacent routers efficiently.
This Memo tries to utilize multiple links between adjacent routers to
make initial adjacency establishment & flooding more optimized, such
that these procedures become faster and consumes lesser bandwidth.
Conventions used in this document
<Kakkar-Srini> Expires - June 2006 [Page 1]
Internet Draft OSPF Multi Links December 2005
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119.
Table of Contents
1. Introduction...................................................2
2. Adjacency formation Recommendation.............................2
3. Flooding Recommendations.......................................4
4. Adjacency Switching Recommendations............................6
5. Patents........................................................6
6. Formal Syntax..................................................6
Security Considerations...........................................6
References........................................................6
Acknowledgments...................................................7
Author's Addresses................................................7
Disclaimer of Validity............................................7
1.
Introduction
In this document ospf refers to both version 2 and version 3 of open
shortest path first protocol.
Any large network is likely to have multiple links between routes, if
ospf is running in such environment it is likely to receive multiple
requests to form adjacency with peer on . Under large databases
adjacency formation put extreme strain on cpu and network resources.
Similarly during flooding, LSA’s are flooded and retransmitted
multiple times to the same neighbor because no special handling is
provided for topologies involving multiple interfaces between peers.
In order to improve cpu and network utilization during initial
adjacency establishment and flooding we provide some recommendations
in section 2,3 and 4.
2.
Adjacency formation Recommendation
If two adjacent routes have multiple links between them, whenever
links/routers come up simultaneously, OSPF tries to form multiple
adjacencies with the same neighbor almost simultaneously (Subjected
to Maximum Concurrent Adjacencies Number described in [3]).
This approach has following problems
1) LSDB’s are traversed multiple times.
2) Most of the LSA's are propagated Multiple times
<Kakkar-Srini> Expires - June 2006 [Page 2]
Internet Draft OSPF Multi Links December 2005
AS Scope LSA’s will be propagated multiple times, Area scope
LSA's May be propagated multiple times if adjacencies are in same
area.
2) Subjected to Maximum Concurrent Adjacencies Number [3], some
distinct router will have to wait to form adjacency.
To avoid these problems we provide following recommendations
Classify every adjacency as ‘‘Primary’’ or ‘‘Secondary’’. Always first
adjacency with a peer is marked as Primary and subsequent
adjacencies with the same peer are marked as ‘‘Secondary’’.
Before entering 2way state with a peer,
1. If there is NO existing adjacency with the peer
Prepare DB description packet as described in [1].
2.If there is already a FULL adjacency with the same peer.
A)If there is an existing adjacency in same area with the peer,
Only describe Link Scope LSA’s in Db description packet
B)If there is an existing adjacency in different, non stub area
with the peer,
Only describe Area scope and Link Scope LSA’s in Db
description packet
C) If all existing adjacencies with the peer are in stub area and
new adjacency is in non-stub area,
Prepare DB description packet as described in [1].
3.If already an adjacency formation is in progress with the peer
(i.e NFSM state 2 way or greater but less then full, irrespective
of area and interface).
A)Mark adjacency as Secondary
B)Prepare DB Description packet as described in 2.A , 2.B and 2.C
above.
C)If secondary adjacency exhausts its request list first, borrow
some external LSA headers(Or area scope LSA’s if both primary
and secondary adjacencies are in same area) from Primary
adjacencies request list, Mark secondary adjacency state as
‘‘Borrowed’’ and request LSA’s to peer on secondary adjacency ,
till primary adjacency’s request list also exhausts.
D)If to some reason secondary adjacency is terminated abnormally
and its state is borrowed, simply copy the retransmit list of
Secondary neighbor to Primary adjacency’s neighbor.
E)Do not make secondary adjacency FULL before primary adjacency.
<Kakkar-Srini> Expires - June 2006 [Page 3]
Internet Draft OSPF Multi Links December 2005
F)If to some reason Primary adjacency is terminated abnormally,
router must restart all secondary adjacencies by sending a
deliberate sequence number mismatch,( This is faster method to
reestablish adjacency then One way Hello).
It is easier to see that in presence of multiple interfaces between
peers adjacency establishment will be faster because of 1) Reduced
request list size of secondary adjacencies. 2) Concurrent and
disjoint usage of link bandwidth for multiple adjacencies.
3.
Flooding Recommendations
Whenever multiple adjacencies exists between same peers it is
fruitless to flood LSA’s multiple times. In this section we will
present an approach to optimize flooding by minimizing the
duplication of LS updates.
We introduce following new flags,
In neighbor structure we introduce flag ‘‘ASMaster’’, used for AS
scope LSA’s.
Whenever multiple adjacencies exist between two peers, it will
naturally have multiple neighbor entries. One of these neighbor
entries from non stub area will be marked as ‘‘ASMaster’’
A) If the interface on which it is connected to neighbor is the
fastest (highest bandwidth) among all interfaces connected to same
neighbor,
B) If multiple interfaces are of same bandwidth then interface with
highest IP(ipv6 for ospfv3) MTU is preferred.,
C) If Mtu is also same, interface with highest IF Index is
preferred.
In Interface structure we introduce a new flag ‘‘FloodAS’’,
Whenever an Interface contains at least one neighbor with ‘‘ASMaster’’
flag set, its ‘‘FloodAS’’ flag will be set.
Similarly we introduce a flag ‘‘AreaMaster’’ in neighbor structure,
used for AREA Scope LSA’s. This flag will be set on per area basis
for the neighbor on fastest link. I.e Among adjacencies to same
pear in same area, FloodArea will set for the neighbor stucture on
fastest interface (Same criteria as described in A,B & C above).
Similarly in Interface structure we introduce another new flag
‘‘FloodArea’’, will be set if there is a neighbor with ‘‘AreaMaster’’
flag set.
<Kakkar-Srini> Expires - June 2006 [Page 4]
Internet Draft OSPF Multi Links December 2005
Example
Lets say between two routers A & B there are 4 adjacencies number 1
-4, And assume link 1 & 2 are in Area 0, Link 3 & 4 are in Area 1.
Further Link capacities are Link1-1Mbps, Link2-100Mbps, Link3-
64kbps, MTU1500, Link4-64Kbps MTU 1280.
_____ _____
| |--------|1 |
| A |--------|2 B |
| |--------|3 |
|_____|--------|4____|
According to algorithm described
Link 2 will be marked as ‘‘FloodAS’’ and also ‘‘FloodArea’’ for area 0.
Link 3 will be marked as ‘‘FloodArea’’ for area 1.
Flooding Algorithm Modification
Basic flooding mechanisms remain the same as section 13 of [1] with
the following additional checks
1) Flood an AS scope LSA on an interface only when it’s ‘‘FloodASE’’
flag is set
2) Add AS Scope LSA’s to the retransmit list of only neighbors with
‘‘ASEmaster’’ flag set,
3) Flood an Area scope LSA on an interface only when its ‘‘FloodArea’’
flag is set.
4) Add Area scope LSA’s to the retransmit list of only neighbors
with ‘‘AREAMaster’’ flag set.
5) When Ifdown event occurs for interface marked as
‘‘FloodASE’’/’’FloodArea’’, or KillNbr event occur for neighbors
marked as ‘‘ASMaster’’ or ‘‘AreaMaster’’, select a new ‘‘ASMaster’’
and ‘‘AreaMaster’’ neighbor and copy the retransmit list from
neighbors to the new ‘‘master’’. If no new neighbor is found
discard entries from retransmit list.
It is easier to see that flooding will be lighter because only one
interface is used for retransmission and only a few interfaces will
be used for flooding.
From our example only Link-2 will be used to flood AS Scope LSA’s.
Further Link-2 will be used to flood Area scope LSA’s in Area 0 &
Link 3 will be used to flood Area Scope LSA’s in Area 1.
<Kakkar-Srini> Expires - June 2006 [Page 5]
Internet Draft OSPF Multi Links December 2005
4.
Adjacency Switching Recommendations
RFC 4222 explicitly defines max concurrent DD number and advises to
throttle more adjacencies. Further RFC4222 prohibits terminating
adjacencies in the middle. This approach has a problem that whenever
slow interfaces come up first and makeup max dd count number faster
interfaces have to wait unusually long time to form adjacencies.
For this scenario we recommend
1) If a new adjacency request comes up from a neighbor which is
already having an adjacency with us do not apply max concurrent
DD criteria on it.
2) While building Database Description packet, keep a count of all
LSA’s sizes, so that we know the total amount of bytes to be sent
to peer.
3) Whenever receive an acknowledge packet during dd formation, keep
a count of bytes already reached peers.
These two count along with interface bandwidth will give us an
estimate of remaining time for an adjacency.
If Remaining time for forming adjacency >> Time for new adjacency,
send sequence number mismatch to first adjacency and form adjacency
on the faster interface.
5.
Patents
A Patent has been applied for this mechanism in Peoples Republic of
China’s Beijing patent office. Approval is pending.
6.
Formal Syntax
The following syntax specification uses the augmented Backus-Naur
Form (BNF) as described in RFC-2234.
Security Considerations
This document does not introduce any new security issues to OSPF.
References
[RFC2328] J Moy, ‘‘OSPF Version 2’’.
[RFC2740] J Moy, R Coltun, D Ferguson, ‘‘OSPF for IPV6’’.
<Kakkar-Srini> Expires - June 2006 [Page 6]
Internet Draft OSPF Multi Links December 2005
[RFC4222] G Chodhury, Ed. " Prioritized Treatment of Specific OSPF
Version 2 Packets and Congestion Avoidance’’.
Acknowledgments
We would like to acknowledge the support and helpful comments of Mr
Praveen GS, Mr Anup, Mr Raghu, Mr Zhangjinagping ,Mr Fucho.and Mr
Prabhu G.Biradar.
Author's Addresses
Nitin Kakkar
Huawei Technologies India Pvt Ltd,
Level-3, Leela Galleria,
The Leela Palace, #23 Airport Road,
Bangalore 560008, India
Phone: +91 80 5217192
Email: nitink@huawei.com
KL Srini
Huawei Technologies India Pvt Ltd,
Level-3, Leela Galleria,
The Leela Palace, #23 Airport Road,
Bangalore 560008, India
Phone: +91 80 5217192
Email: kls@huawei.com
Disclaimer of Validity
"This document and the information contained herein are provided on
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE
INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
Copyright Statement
Copyright (C) The Internet Society (2005). This document is
subject to the rights, licenses and restrictions contained in BCP
78, and except as set forth therein, the authors retain all their
rights.
<Kakkar-Srini> Expires - June 2006 [Page 7]
