Method and apparatus for forwarding data packets using aggregating router keys

Abstract

Method and apparatus for supporting the forwarding of received data packets in a router ( 402,702 ) of a packet-switched network. A forwarding table ( 706 a ) is configured in the router based on aggregating router keys and associated aggregation related instructions received from a key manager ( 400,700 ). Each aggregating router key represents a set of destinations. When a data packet (P) is received comprising an ingress tag derived from a sender key or router key, the ingress tag is matched with entries in the forwarding table. An outgoing port is selected for the packet according to a found matching table entry that further comprises an associated aggregation related instruction. An egress tag is then created according to the aggregation related instruction, and the packet with the created egress tag attached is sent from the selected outgoing port to a next hop router.

The invention claimed is: 
     
       1. A method of forwarding received data packets through a packet-switched network, comprising:
 configuring, in a router, a forwarding table based on aggregating router keys and aggregation instructions associated with the aggregating router keys received from a key manager, each aggregating router key representing a set of destinations, the forwarding table comprising at least one table entry and each of the at least one table entries comprising a candidate ingress key, an egress key, key index, an outgoing port indication, and an aggregation instruction; 
 receiving a data packet comprising an ingress tag; 
 applying a mathematical function, matching the ingress tag in the received data packet with the candidate ingress key of the at least one table entry in the forwarding table to find a matching table entry; 
 if a matching table entry is found, selecting as an outgoing port to forward the received data packet the outgoing port corresponding to the outgoing port indication of the matching table entry; 
 creating an egress tag according to the egress key or the aggregation instruction of the matching table entry; 
 attaching the key index of the matching table entry and the created egress tag to the received data packet; and 
 forwarding the received data packet attached with the created egress tag using the selected outgoing port to another router. 
 
     
     
       2. The method according to  claim 1 , wherein the mathematical function includes applying a tag derivation function to the candidate ingress key of a table entry of the forwarding table to derive a candidate ingress tag, and wherein a match is considered to be found if the candidate ingress tag satisfies a predetermined relation with the ingress tag of the received data packet. 
     
     
       3. The method according to  claim 2 , wherein the predetermined relation is equality, and a match is thereby considered to be found if the candidate ingress tag is identical to the ingress tag of the received data packet. 
     
     
       4. The method according to  claim 1 , wherein creating the egress tag comprises applying a tag derivation function to the egress key of the matching table entry. 
     
     
       5. The method according to  claim 1 , wherein the received data packet further comprises a key index associated with an entry or a set of entries of the at least one entry in the forwarding table for applying the mathematical function. 
     
     
       6. The method according to  claim 1 , wherein creating the egress tag comprises attaching one or more sub-tags, derived from one or more egress keys in the matching table entry, to the received data packet to execute aggregation, or by removing one or more sub-tags from the received data packet to execute de-aggregation. 
     
     
       7. The method according to  claim 6 , wherein creating the egress tag further comprises applying a predetermined combination function to the ingress tag of the received data packet and the one or more sub-tags when executing aggregation. 
     
     
       8. The method according to  claim 7 , wherein the predetermined combination function is concatenation or an XOR function. 
     
     
       9. The method according to  claim 1 , wherein a hierarchical scheme of router keys and destination keys is used wherein creating the egress tag comprises exchanging the ingress tag of the received data packet for a new tag derived from an egress key in the matching table entry and adding aggregation information to the egress tag, wherein the aggregation information can be used to determine the original destination. 
     
     
       10. The method according to  claim 9 , wherein the hierarchical router key scheme has a tree-structure iteratively generated from;
 a root router key value; 
 a router key value of a node position above a current tree level; and 
 an integer indicating a node position within the current tree level; 
 wherein destination keys of end-hosts correspond to leaves of the tree-structure, and any router key values on tree levels above the leaves can be used as aggregating router keys. 
 
     
     
       11. The method according to  claim 10 , wherein the resulting key scheme is composed of key values that can be calculated, by applying a recursive function to the root router key value. 
     
     
       12. An apparatus in a router of a packet-switched network for forwarding received data packets, comprising:
 an ingress unit configured to receive a data packet comprising an ingress tag derived from a sender key or router key, 
 a forwarding unit configured to configure a forwarding table based on aggregating router keys and aggregation instructions associated with the aggregating router keys received from a key manager, each aggregating router key representing a set of destinations, the forwarding table comprising at least one table entry and each of the at least one table entries comprising a candidate ingress key, an egress key, key index, an outgoing port indication, and an aggregation instruction, the forwarding unit comprising:
 a tag matching unit configured to:
 apply a mathematical function matching the ingress tag in the received data packet with the candidate ingress key of the at least one table entry in the forwarding table to find a matching table entry; and 
 if a matching table entry is found, select as an outgoing port to forward the received data packet the outgoing port corresponding to the outgoing port indication of the matching table entry; and 
 
 a tag creating unit configured to:
 create an egress tag according to the egress key or the aggregation instruction of the matching table entry; and 
 attach the key index of the matching table entry and the created egress tag to the received data packet; and 
 
 
 an egress unit configured to forward the received data packet attached with the created egress tag using the selected outgoing port to another router. 
 
     
     
       13. The apparatus according to  claim 12 , wherein the tag matching unit is further configured to apply a tag derivation function to the candidate ingress key of a table entry of the forwarding table to derive a candidate ingress tag, and wherein a match is considered to be found if the candidate ingress tag satisfies a predetermined relation with the ingress tag of the received data packet. 
     
     
       14. The apparatus according to  claim 13 , wherein the predetermined relation is equality, and a match is thereby considered to be found if the candidate ingress tag is identical to the ingress tag of the received data packet. 
     
     
       15. The apparatus according to  claim 12 , wherein the tag creating unit is configured to create the egress tag by applying a tag derivation function to the egress key of the matching table entry. 
     
     
       16. The apparatus according to  claim 12 , wherein the tag creating unit is configured to create the egress tag by attaching one or more sub-tags, derived from one or more egress keys in the matching table entry, to the received data packet to execute aggregation, or by removing one or more additional sub-tags from the received data packet to execute de-aggregation. 
     
     
       17. The apparatus according to  claim 16 , wherein the tag creating unit is configured to create the egress tag by applying a predetermined combination function to the ingress tag of the received data packet and the one or more sub-tags when executing aggregation. 
     
     
       18. The apparatus according to  claim 17 , wherein the predetermined combination function is concatenation or an XOR function. 
     
     
       19. The apparatus according to  claim 12 , wherein a hierarchical scheme of router keys and destination keys is used wherein the tag creating unit is configured to create the egress tag by exchanging the ingress tag of the received data packet for a new tag derived from an egress key in the matching table entry and adding aggregation information to the egress tag, wherein the aggregation information can be used to determine the original destination. 
     
     
       20. The apparatus according to  claim 19 , wherein the hierarchical router key scheme has a tree-structure iteratively generated from:
 a root router key value; 
 a router key value of a node position above a current tree level; and 
 an integer indicating a node position within the current tree level; 
 wherein destination keys of end-hosts correspond to leaves of the tree-structure, and any router key values on tree levels above the leaves can be used as aggregating router keys. 
 
     
     
       21. The apparatus according to  claim 20 , wherein the resulting key scheme is composed of key values that can be calculated, along a path from by applying a recursive function to the root router key value. 
     
     
       22. A method performed by a key manager for supporting routers in a packet-switched network, comprising:
 registering destination keys for end-hosts; 
 determining one or more aggregating routers; 
 creating aggregation information comprising aggregating router keys and aggregation instructions associated with the aggregating router keys, each aggregating router key representing a set of destinations; 
 distributing the aggregation information to the one or more aggregating routers thereby enabling the one or more aggregating routers to configure their forwarding tables based on the aggregation information; 
 receiving an address query from a querying end-host regarding a target end-host; 
 creating a sender key by applying a key derivation function to at least a destination key associated with the target end-host; and 
 sending the created sender key to the querying end-host in response to the address query, thereby enabling the querying end-host to attach a sender tag generated from the sender key to a data packet to be transmitted, the sender tag directing the data packet to the target end-host; 
 wherein each end-host is connected to the packet-switched network via an access router; 
 wherein the access router is one of the routers in the packet-switched network; and 
 wherein the one or more aggregating routers are routers in the packet-switched network and are configured to execute at least one of route aggregation and de-aggregation. 
 
     
     
       23. An apparatus in a key manager for supporting at routers in a packet-switched network, comprising:
 a network controlling unit configured to;
 register destination keys for end-hosts; and 
 determine of one or more aggregating routers; 
 
 a key distributor configured to:
 create aggregation information comprising aggregating router keys and aggregation instructions associated with the aggregating router keys, each aggregating router key representing a set of destinations; and 
 distribute the aggregation information inctructions to the one or more aggregating routers, thereby enabling the one or more aggregating routers to configure their forwarding tables based on the aggregation information; 
 
 an address query manager configured to:
 receive an address query from a querying end-host regarding a target end-host; 
 create a sender key by applying a key derivation function to at least a destination key associated with the target end-host; and 
 send the created sender key to the querying end-host in response to the address query, thereby enabling the querying end-host to attach a sender tag generated from the sender key to a data packet to be transmitted, the sender tag directing the data packet to the target end-host; 
 
 wherein each end-host is connected to the packet-switched network via an access router; 
 wherein the access router is one of the routers in the packet-switched network; and 
 wherein the one or more aggregating routers are routers in the packet-switched network and are configured to execute at least one of route aggregation and de-aggregation.