WO2009064165A2

WO2009064165A2 - A fast packet forwarding engine for scalable routing

Info

Publication number: WO2009064165A2
Application number: PCT/MY2008/000139
Authority: WO
Inventors: Borhanuddin Mohd Ali; Sahar Abdul Aziz Mageed Al Talib
Original assignee: Mimos Bhd
Current assignee: Mimos Bhd
Priority date: 2007-11-15
Filing date: 2008-11-17
Publication date: 2009-05-22
Anticipated expiration: 2010-05-15
Also published as: WO2009064165A3; MY144095A

Abstract

The present invention relates to a fast packet forwarding engine for scalable routing characterized in that wherein the present invention is a forwarding engine for multicast routers that accelerates the forwarding of packets such that it improves their performance to support group communications applications and wherein the present invention comprises of a bitmap field added to the packet header such as IP source address, the IP destination address and the bitmap field and wherein when a source wants to send a packet to an active receivers, it sends a packet to a router with bitmap configuration and with a receiver list and wherein the router performs route lookups for all destinations.

Description

A FAST PACKET FORWARDING ENGlNE FOR SCALABLE ROUTING

FIELD OF THE INVENTION

The present invention relates to a fast packet forwarding engine for scalable routing. More particularly the present invention relates to a fast packet forwarding arrangement for making quick and efficient next hop determinations through the addition of a bitmap. Most particularly the present invention relates to a packet forwarding engine particularly, router algorithms and architectures for supporting packet dissemination operations.

BACKGROUND OF THE INVENTION

Routers provided in a communication network, for example, a TCP/IP network, provide a packet forwarding function whereby input data, usually in the form of packets, is switched or routed to a further destination, e.g., along a network link. IP

Multicast has been proposed to support group communications such as video conferencing and data distribution. Many multicast protocols have been developed for over a decade. However, no single multicast protocol can completely supports all types of group communications. Group communication basically implies a many-to-many communication style in a group; this goes beyond both one-to-one communication (i.e., unicast) and one-to-many communication (i.e., multicast). The existing multicast protocols are mostly proposed for a large group of many- to-many communication. However, .for small group communications, for example a video conferencing among ten people, the cost in creating the multicast trees is too expensive, and they do not scale well with a large number of groups.

As a leading issue in distributed settings, group communication is also important in ad hoc and wireless mesh networks, because these networks are inherently distributed (support from centralized services, even if applicable, may only be intermittently available). However, devising solutions to provide group communication service in ad hoc networks is extremely challenging, due to highly dynamic and unpredictable topological changes. As a result, there is no general solution to this problem, and the solution has to take into account requirements of specific scenarios.

Therefore, it is an objective of the present invention to focus on small-scale group networks that involve mainly group-oriented communications. The solution greatly facilitates the implementation of distributed algorithms in wireless mesh network. The research community has, however, largely ignored the problem of efficient data forwarding in multi-hop, wireless environments. Yet, another objective of the present invention is to develop a forwarding engine for group-oriented network layer service, other than a unicast routing protocol, to support distributed services. The invented engine will disseminate the traffic to the active subscriber stations based on the added bitmap. This lack of support and the limited and expensive construction and maintenance of the multicast delivery tree are the motivations for this invention, The present invention solves the problem of scalability through a forwarding engine that adds a bitmap to the packet header. This will eliminate the forwarding table and accelerate the forwarding of packets to the active subscriber stations (receivers).

SUMMARY OF THE INVENTION

A copy is forwarded to the router with another bitmap configuration and wherein for each copy sent by the router, the source address does not change and the bitmap is set to the active destinations for each interface. After the first packet, forwarding state was created in routers and if any router would discover that there are non-branching upstream routers, it sends a Redirect message to the first router containing the ID of the communication and the bitmap of destinations that should be redirected to itself and wherein the said first router would process the Redirect and stores the new information in its forwarding table.

The present invention further comprises a method of eliminating and replacing the forwarding table with a forwarding engine to accelerate the forwarding of packets to active subscriber stations and wherein a small communication groups can be supported efficiently. A first element of the present invention is to add a bitmap to the packet to accelerate the forwarding and wherein a second element of the present invention is to assign cluster for the subscribed receiver with a cluster head for each group of receivers and wherein a third element of the present invention is to assign the invented forwarding engine with each cluster head and wherein a fourth element of the present invention is to optimize the routing if non-branching routers exist by using the skip count.

A fast packet forwarding arrangement for making quick and efficient next hop determinations through the addition of a bitmap. The bitmap is a number of bits that have been created and added to the packet header to improve the forwarding of packets and wherein the number of the added bits is equal to the number of subscriber stations in the subscribers list such that the bit is set if the correspondent subscriber station is active and vice versa.

The method further comprises of means to differentiate instances of the same flow and wherein the packet forwarding improves the performance of group communications. The present invention is applicable to a small group communications and if clustering of subscribers is implemented the same engine could be used at each cluster head to improve the scalability of the whole network.

BRIEF DESCRIPTION OF THE FIGURES

Figure 1 shows an illustration of the present invention

Figure 2 shows another illustration of the present invention as shown in Figure 1.

DETAILED DESCRIPTION OF THE INVENTION

The present invention will now be described with reference made to the accompanied drawings. However, it should be noted that the scope of the invention is not limited by the illustrating drawings. The present invention is a forwarding engine for multicast routers that accelerates the forwarding of packets such that it improves their performance to support group communications applications efficiently. The present invention comprises of a bitmap field added to the packet header namely the IP source address, the IP destination address and the bitmap field,

The present invention relates generally to packet forwarding engine, and particularly, router algorithms and architectures for supporting packet dissemination operations. The present invention could be implemented and resident in a router or packet forwarding engine that routes packets, e. g,, IP packets, over a network, such as, e. g.. the Internet. Reference is made to Figure 1 wherein is illustrated therein if source S wants to send a packet to the active receivers [r₂,r₅,r₇,r₁₀,r₁₅,r₂₃,r₄₀]. For this, it sends a packet to router R₃ with bitmap equal to 1111111 and a receiver list [r₂,r₅,r₇,r₁₀,r₁₅,r₂₃,r₄₀] . R₃ performs route lookups for ail destinations, η ₅ is directly reachable via the North interface, so a copy of the packet is sent directly in unicast to rjs with a bitmap of 0000100.

The remaining destinations of the packet are reachable via the East interface. A copy is forwarded to the router on the Bast link, namely router R₅ with a bitmap of 111101 1. For each copy sent by R₃, the source address does not change and the bitmap is set to the active destinations for eath interface, Figure 1. r₂₃ is directly connected to router R₅ via the North interface, so a copy of the packet is sent in unicast to r₂₃ with a bitmap of 0000010. Receivers r₅ and r₇ are directly reachable via the South interface, so a copy of the packet is sent to the group address using layer-2 multicast with a bitmap of 0110000. A copy is sent to the router on the

East link, namely router R₈ with a bitmap of 1001001.

We now have 3 packets flowing respectively to receiver r₂, r₄₀ and router R₁₀. R₈ will forward the packet to the router on the East link R₁₀ with a bitmap of 0001000 and in unicast to r₂ with bitmap of 1000000 and rio with a bitmap of 0000001. R₁₀ finally forward in unicast to the last active receiver r₁₀ with a bitmap of 0001000. Since all the mentioned routers were branching routers, the Skip Count will remain 0, After this first packet, forwarding state was created in routers aid if any router would discover that there are non-branching upstream routers, it sends a Redirect message to router R1, Figure 2 containing the ID of the communication and the bitmap of destinations that should be redirected to itself, Rl processes the Redirect and stores the new information in its forwarding table. Subsequent packets will be directly sent to router R4. The state created in router R2 will timeout and no routing will be used by R2 for further packets, only standard unicast routing.

The present invention further comprises a method of eliminating and replacing the forwarding table with a forwarding engine to accelerate the forwarding of packets to active subscriber stations. Hence, small communication groups can be supported efficiently. To have a scalable solution and support for large groups, if the subscribers are clustered and for each cluster assign a cluster head either automatically or by election, the same forwarding engine can be implemented in the cluster head as the source, As a result, the forwarding speed will increase as well as the scalability of the network. The present invention can also be characterized as a mean of route optimization tool when non-branching routers exists by adding the skip count as previously explained.

The first element of the present invention is to add a bitmap to the packet to accelerate the forwarding. A second element of the present invention is to assign cluster for the subscribed receiver with a cluster head for each group of receivers. The third element of the present invention is to assign the invented forwarding engine with each cluster head. The fourth element of the present invention is to optimize the routing if non-branching routers exist by using.the skip count.

As a result, a simple, scalable, easy to improve forwarding engine is generated for each router. The router then operates according to the new invented forwarding engine. Advantageously, the forwarding architecture is such that it may be manufactured in integrated circuit form for ready implementation in packet forwarding engine or router.

A fast packet forwarding arrangement for making quick and efficient next hop determinations through the addition of a bitmap. The bitmap is a number of bits that have been created and added to the packet header to improve the forwarding of packets. The number of the added bits is equal to the number of subscriber stations in the subscribers list such that the bit is set if the correspondent subscriber station is active and vice versa.

The method further comprises of means to differentiate instances of the same flow; it is changed whenever the membership changes and useful to ensure that forwarding is done correctly. The packet forwarding improves the performance of group communications applications so as to offer a better performance of multicast routers by optimizing the routing path and hence the amount of total traffic injected into the network by each multicast session.

The instant invention is applicable to small group communications and if clustering of subscribers is implemented the same engine could be used at each cluster head to improve the scalability of the whole network. As a result, the routers performance will be improved because there is no need to save the routing states and the expenses of building the multicast delivery tree will be deleted.

Claims

1. A fast packet forwarding engine for scalable routing characterized in that wherein the present invention is a forwarding engine for multicast routers that accelerates the forwarding of packets such that it improves their performance to support group communications applications and wherein the present invention comprises of a bitmap field added to the packet header such as ΪP source address, the IP destination address and the bitmap field and wherein when a source wants to send a packet to an active receivers, it sends a packet to a router with bitmap configuration and with a receiver list and wherein the router performs route lookups for all destinations.

2. A fast packet forwarding engine for scalable routing as claimed in Claim 1 wherein a copy is forwarded to the router with another bitmap configuration and wherein for each copy sent by the router, the source address does not change and the bitmap is set to the active destinations for each interface.

3. A fast packet forwarding engine for scalable routing as claimed in Claim 1 wherein after the first packet, forwarding state was created in routers and if any router would discover that there are non-branching upstream routers, it sends a

Redirect message to the first router containing the ID of the communication and the bitmap of destinations that should be redirected to itself and wherein the said first router would process the Redirect and stores the new information in its forwarding table.

4. A fast packet forwarding engine for scalable routing as claimed in Claim 1 wherein the present invention further comprises a method of eliminating and replacing the forwarding table with a forwarding engine to accelerate the forwarding of packets to active subscriber stations and wherein a small communication groups can be supported efficiently.

5. A fast packet forwarding engine for scalable routing as claimed in Claim 4 wherein a first element of the present invention is to add a bitmap to the packet to accelerate the forwarding and wherein a second element of the present invention is to assign cluster for the subscribed receiver with a cluster head for each group of receivers and wherein a third element of the present invention is to assign the invented forwarding engine with each cluster head and wherein a fourth element of the present invention is to optimize the routing if non- branching routers exist by using the skip count.

6. A fast packet forwarding engine for scalable routing as claimed in Claim 5 wherein a fast packet forwarding arrangement for making quick and efficient next hop determinations through the addition of a bitmap.

7. A fast packet forwarding engine for scalable routing as claimed in Claim 6 wherein the bitmap is a number of bits that have been created and added to the packet header to improve the forwarding of packets and wherein the number of the added bits is equal to the number of subscriber stations in the subscribers list such that the bit is set if the correspondent subscriber station is active and vice versa.

8. A fast packet forwarding engine for scalable routing as claimed in Claim 4 wherein the method further comprises of means to differentiate instances of the same flow and wherein the packet forwarding improves the performance of group communications

9. A fast packet forwarding engine for scalable routing as claimed in any of the preceding claims wherein the present invention is applicable to a small group communications and if clustering of subscribers is implemented the same engine could be used at each cluster head to improve the scalability of the whole network.