Subject: ForCES Intra-NE routing mechanism

From: Xiaoyi Guo <[email-masked]>
Date: Thu, 13 Oct 2005 17:58:31 +0800

All,

I'm currently putting a draft of the ForCES Intra-NE routing mechaniam,
and will submit it by Thusday.Below are the major points, please comment.

About ForCES Intra-NE routing mechanism
                 -----------------   
                 |      CE       |   
                 -----------------   
                A ^    B ^    C ^   
                 /       |       \   
                /      A v        \   
               /      ------- B    \   
              /    +->| FE3 |<-+    \   
             /     |C |     |  |     \   
          A v      |  -------  |      v A   
          -------B |           |E -------   
          | FE1 |<-+           +->| FE2 |   
          |     |<--------------->|     |   
          ------- C             D -------   
           E ^ D|                 C ^  | B   
             |  |                   |  |   
             |  v                   |  v    

When a packet comes in FE1 port E and it want to forwaring to FE2 port B, 
it must across the Intra-NE FEs.

There has two ways to generate the routing paths :
1, static configuration from FEM / CEM ,
2, dynamic generated by system .

Obviously the first method is not a good choice , so we focus on the latter one.
We aleardy know the full topology from the CE topology table , this is designed and generated by 
Intra-NE topology discovery mechanism.

But this topology table need to caculate and generate to the CE's Intra-routing table.
For example , in this Figure , there exist two path from FE1 to FE2, so we must use some policy 
to select a better one which the cost is smaller. The method maybe like the OSPF SPF tree algorithm
or other similar algorithm.

See the CE topology table 
----------------------------------------------
<Node>   <Port>   <Node>   <Port>
  FE1                B      FE2     D   
  FE2                E      FE3     D   
  FE1                B      FE2     C   

We will add a Intra-FIB in each FE , this table is distributed by master CE:
i will add some structure such as nexthop(port) , nextNode(FE), so it looks like a table as below 

FE1 IFIB (part)
------------------------------------------------------------------------------------------------
<Node>   <Port>   <DstNode>   <Port>   <NextNode>   <NextPort> 
  FE1             B              FE3            D            FE2                   D  

 FE2 IFIB (part)
-----------------------------------------------------------------------------------------------
<Node>   <Port>   <DstNode>   <Port>   <NextNode>   <NextPort> 
  FE2            E                FE3             D           FE3              D       

When the packet arrived at FE1 , Then  FE1 find the Nexthop by searching FIB , 
and then searching IFIB , FE1 will know the routing path is from FE1 to FE3 then to FE2. In FE3 , 
only search the IFIB, the packet forward to FE2 with the correct path , then FE2 will forward it out the NE .

This two table searching mechanism is a bit similar to such as MPLS or other VPN label pursh/pop action.

The advantages as below :
1, The Intra-NE full topylogy need not known by each FE.
2, Intra-FE do not need the outer routing information.

Best Regards

Xiaoyi Guo
------------------------------------------------
Huawei Technologies.
No. 3 Xinxi Rd., Shang-Di Information Industry Base,
Hai-Dian District Beijing, P.R. China  100085
Tel:   +86-10-8288-2290
Fax:   +86-10-8288-2770
<mailto:[email-masked]>
<http://www.huawei.com>
------------------------------------------

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 13 Oct 2005 09:02:21 -0400

I am not sure I follow this discussion.
1) The CE can use any algorithm it likes to calculate paths.  (That applies 
both to intra-NE paths and to normal routing. ForCES does not care what 
path computation algorithm is used by the CE.)

2) I don't see the value in creating a new kind of forwarding table.  For 
each FE, the forwarding table it is given ought to translate an IP prefix 
into a next hop, and the next hop into an egress port.  You seem to be 
trying to add a third layer of mapping.  The benefit I can see for such a 
thing might be that it could reduce slightly the differences in the tables 
across the FEs. However, I would be really unhappy at mandating such an 
architecture.

Yours,
Joel

At 05:58 AM 10/13/2005, Xiaoyi Guo wrote:
>   FE1             B              FE3            D            FE2 
>           D
>   FE2            E                FE3             D           FE3 
>       D
><<mailto:[email-masked]>mailto:[email-masked]>
><http://www.huawei.com>

---

From: Jamal Hadi Salim <[email-masked]>
Date: Thu, 13 Oct 2005 09:16:00 -0400

Hello,

On Thu, 2005-13-10 at 17:58 +0800, Xiaoyi Guo wrote:
> When a packet comes in FE1 port E and it want to forwaring to FE2 port
> B, it must across the Intra-NE FEs.
>  

I am not sure i understood what you mean by FEM/CEM doing this. The CE
does the update in the above scenario. The static case will not have any
routing protocol (such as OSPF) running on the CE whereas the dynamic
case will.

> We aleardy know the full topology from the CE topology table , this is
> designed and generated by Intra-NE topology discovery mechanism.
>  

right.

> But this topology table need to caculate and generate to the CE's

right - i.e the NH entry for each route.

> For example , in this Figure , there exist two path from FE1 to FE2,
> so we must use some policy to select a better one which the cost is
> smaller. The method maybe like the OSPF SPF tree algorithm

Yes, this is described in the Topology draft.

> See the CE topology table 

Depends on the FE; one could look at the NextNode:NextPort as
part of the NextHop description in the forwarding.  i.e the IFIB becomes
part of the NH table used by the FIB. 

> When the packet arrived at FE1 , Then  FE1 find the Nexthop by
> searching FIB , and then searching IFIB , FE1 will know the routing
> path is from FE1 to FE3 then to FE2. In FE3 , 
> only search the IFIB, the packet forward to FE2 with the correct
> path , then FE2 will forward it out the NE .
>  

Again implementation detail depending on the FE (the ASIC and the
Forwarding fabric used to be precise).
The rules are if you are going to do that you must make sure the ttl
does not get decremented more than once.
 
> 2, Intra-FE do not need the outer routing information.

I have to say i see everything you have described as implementation details.
i.e
The FE Object LFB[1] lists the concept of neighbors. These neighbors are
going to be derived from the topology LFB. And from that info you can
derive the NH details for routing. How you do this is dependent on the
chip and the interconnect.

cheers,
jamal

[1]The neighbor information is insufficient at the moment by claiming that
neighbors can only have MAC addresses and ignores the forwarding path
could be over SPI3/4 or even over purely L2 ethernet for example - we
have had many debates on the list and that debate is going to resurface
RealSoonNow.

---

From: Xiaoyi Guo <[email-masked]>
Date: Fri, 14 Oct 2005 15:11:11 +0800

hi, Joel.

Best Regards!
Xiaoyi .

----- Original Message ----- 
From: "Joel M. Halpern" <[email-masked]>
> path computation algorithm is used by the CE.)
Yes, you are right. ForCES does not care the algorithm , but i think we can find a better algorithm for Intra-NE.
So I prefer a implement for it.

> across the FEs. However, I would be really unhappy at mandating such an 
I think i can understand your comments and your thoughts. So  i will give more information about this mechanism.
if one NE include many FEs ,  there exist many paths cross the Intra-NE. Let's suppose one of the paths
cross many FEs such as 10 FEs, but only the two edge FEs have the connection to other routers,  the other 8 FEs are
intra-FEs. I think they don't need the information of outside routers , even they can be configured with private ip addr.
So these 8 FE just have the intra- fowarding table as i metioned .  That the reason why i suggest this multi-hop forwarding mechanism.

---

From: "Joel M. Halpern" <[email-masked]>
Date: Fri, 14 Oct 2005 07:26:47 -0400

I follow your reasoning.  I believe that initially the intra-NE links 
between FEs can be handled just like any other next-hop.  The next-hop 
handling has to allow for a variety of media, so it should support whatever 
interconnect media is used.  We can later consider several 
enhancements.  We could improve the behavior by supporting meta-data on 
such links for some media.  We could also improve the ability to multicast 
information by adding a layer of indirection so that all the FEs would see 
the same external next hop, rather than each FE being sent a different next 
hop where some see an external next hop and some see an internal next hop.

One aspect here is that I think we should focus first on those LFBs that we 
must have, with a structure that points out which ones we would like to 
have.  I am going to try to get a draft together before the deadline 
(Monday) that gives us a starting point [It was politely pointed out to me 
that if I think this is important I should "send text"].

Yours,
Joel M. Halpern

At 03:11 AM 10/14/2005, Xiaoyi Guo wrote:
>Yes, you are right. ForCES does not care the algorithm , but i think we 
>can find a better algorithm for Intra-NE.
>cross many FEs such as 10 FEs, but only the two edge FEs have the 
>connection to other routers,  the other 8 FEs are
>intra-FEs. I think they don't need the information of outside routers , 
>even they can be configured with private ip addr.
>So these 8 FE just have the intra- fowarding table as i metioned .  That 
>the reason why i suggest this multi-hop forwarding mechanism.