Message logging for reliable multicasting across a routing network

• US 7,050,432 B1
• Filed: 03/30/1999
• Issued: 05/23/2006
• Est. Priority Date: 03/30/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Strom, Robert Evan, Banavar, Guruduth Somasekhara, Sturman, Daniel Charles, Chandra, Tushar Deepak, Ward, Michael James, Miller, Kevan Lee
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): HO, CHUONG T
• Application Number:
  US09/281,421
• Time in Patent Office: 2,611 Days
• Field of Search: 370/216, 370/218, 370/219, 370/220, 370/227, 370/228, 370/237, 370/394, 370/390, 370/428, 370/408, 370/410, 370/477, 370/400, 707/10, 709/241, 714/748, 714/749
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/1895 for short real-time information, e.g. alarms, notifications, alerts, updates
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A technique for reliably multicasting a message within a router network is provided. At least one special router in the network has associated persistent storage for logging a message being routed to one or more clients. When a message is received at this logger node, the logger places the message in persistent storage and sends a logging acknowledgment back to those routers to which the message was originally routed, as well as back towards the source of the message. The logger acknowledgment includes the message id, the logger id, and a logging number. When the logger acknowledgment is received by a router, it looks up the routing information from the original message, and sends the acknowledgment to those neighboring routers to which the original message was sent, excluding the link from which the logger acknowledgment was received. If the original message corresponding to the logger acknowledgment was buffered at this router waiting to be delivered, the message is then delivered to its client nodes. Processes for recovering from node or link failure within the router network, and for at most once delivery of messages, at least once delivery of messages, and exactly once delivery of messages are also provided.

Claims

1. A method for routing messages within a network, said method comprising:

receiving a message;

routing said message to multiple clients of said network, said routing being based on data content of said message irrespective of any destination information within said message and being resilient to router or link failure within said network without loss of said message; and

wherein said network comprises a publish/subscribe system supporting content-based subscription, said one or more clients comprise subscribers, and wherein said routing comprises delivering said message to all subscribers requesting a uniform delivery quality of service or if unable to deliver said message to all of said subscribers requesting uniform delivery, delivering said message to none of said subscribers requesting uniform delivery.

2. The method of claim 1, wherein said delivering said message to all subscribers requesting uniform delivery comprises delivering said message to all subscribers requesting uniform delivery notwithstanding failure at one or more routers or links of said network, said delivering comprising storing said message to persistent storage at a logging node of said network prior to providing said message to said subscribers requesting uniform delivery.

3. The method of claim 1, wherein said routing comprises logging said message at at least one logging node within said network before delivering said message to said multiple clients of said network, said logging comprising storing said message in persistent storage.

4. The method of claim 3, further comprising subsequent to said logging of said message, sending a logging acknowledgment to at least one router of said network routing said message, and upon receipt of said logging acknowledgment at said at least one router, delivering said message to a client thereof, said client requiring uniform delivery and comprising one client of said multiple clients.

5. The method of claim 4, further comprising buffering said message at said at least one router of said network routing said message, said buffering occurring prior to said storing of said message at said persistent storage and when passing said message through said at least one router to said at least one logging node.

6. The method of claim 4, wherein said network comprises a plurality of routers coupled together, one of said routers comprising said logging node having said persistent storage associated therewith, said logging comprising employing said logging node having said persistent storage associated therewith to store said message and to thereafter send said logging acknowledgment back to each router of said network responsible for routing said message.

7. A method for routing messages within a network, said method comprising:

receiving a message;

routing said message to multiple clients of said network said routing being based on data content of said message irrespective of any destination information within said message, and being resilient to router or link failure within said network without loss of said message; and

wherein said network comprises a spanning tree and wherein said method further comprises providing a logging node within said spanning tree for logging said message to persistent storage during routing of said message to said one or more clients of said network.

8. The method of claim 7, wherein said routing comprises employing said logging of said message to persistent storage to ensure a uniform delivery quality of service of said message to said one or more clients of said network notwithstanding failure of one or more routers or links within said network.

9. The method of claim 7, wherein said spanning tree hag comprises a plurality of routers, said method further comprising detecting failure of a router within said tree before completing routing of said message to said multiple clients of said network, reconfiguring said tree to replace said failed router with a new router, and automatically generating a request for retransmission of said message.

10. The method of claim 9, further comprising prior to said detecting of said failure, logging said message within persistent storage of said network and issuing a logging acknowledgment confirming storage of said message to at least one router of said tree through which said message is routed to said multiple clients.

11. The method of claim 9, wherein said automatically generating said request for retransmission of said message occurs if said new router detects from one or more of its child routers a logging number associated with said message, said logging number having been received in said logging acknowledgment confirming storage of said message.

12. The method of claim 7, wherein said routing further comprises determining within said network whether said message comprises a duplicate message to said multiple clients of said network, and if so, aborting said duplicate message such that said message is delivered to said multiple clients at most once.

13. The method of claim 7, further comprising automatically informing a sender of said message when the message has not been received by the network to allow the sender to retransmit said message to the network for routing to said multiple clients of said network so that said message is delivered at least once to said multiple clients.

14. A method for routine messages within a network, said method comprising:

receiving a message;

routing said message to multiple clients of said network, said routine being based on data content of said message irrespective of any destination information within said message, and being resilient to router or link failure within said network without loss of said message; and

wherein said routing comprises logging said message at at least one logging node within said network before delivering said message to said multiple clients of said network, said logging comprising storing said message into persistent storage, and wherein said method further comprises subsequent to said logging of said message, sending a logging acknowledgment to at least one router of said network routing said message, and upon receipt of said logging acknowledgment at said at least one router of said network routing said message, looking up routing information for said message from a message table maintained at said at least one router, then sending said logging acknowledgment across said network using said looked up routing information, and thereafter deleting said routing information from said message table.

15. A system of routing messages within a network, said system comprising:

means for receiving a message;

means for routing said message to multiple clients of said network, said routing being based on data content of said message irrespective of any destination information within said message, and wherein said means for routing is resilient to router or link failure within said network without loss of said message;

wherein said network comprises a publish/subscribe system supporting content-based subscription, and wherein said one or more clients comprise subscribers, with said message being received from a publisher; and

wherein said means for routing comprises means for delivering said message to all subscribers requesting a uniform delivery quality of service or if unable to deliver said message to all of said subscribers requesting uniform delivery, for delivering said message to none of said subscribers requesting uniform delivery.

16. The system of claim 15, wherein said means for routing delivers said message to said subscribers requesting uniform deliver notwithstanding failure at one or more routers or links of said network, and wherein said system further comprises means for logging said message to persistent storage prior to delivery thereof to said subscribers requesting uniform delivery.

17. A system of routing messages within a network, said system comprising:

means for receiving a message;

means for routing said message to multiple clients of said network, said routing being based on data content of said message irrespective of any destination information within said message, and wherein said means for routing is resilient to router or link failure within said network without loss of said message, and

wherein said means for routing comprises means for logging said message to at least one logging node within said network before delivering said message to said multiple clients of said network, said means for logging comprising means for storing said message in persistent storage.

18. The system of claim 17, further comprising means for sending a logging acknowledgment to at least one router of said network routing said message after said means for logging stores said message in persistent storage, and wherein said system further comprises, at said at least one router of said network routing said message, means for delivering said message to a client thereof upon receipt of said logging acknowledgment, said client requiring uniform delivery and comprising one client of said multiple clients.

19. The system of claim 18, further comprising means for buffering said message at said at least one router of said network routing said message, said buffering occurring prior to said storing of said message at said persistent storage by said means for logging.

20. The system of claim 18, wherein said network comprises a plurality of routers coupled together, one of said routers comprising said logging node having said persistent storage associated therewith, and wherein said means for logging comprises means for employing said logging node having said persistent storage associated therewith to store said message and to thereafter send said logging acknowledgment back to each router of said network responsible for routing said message.

21. The system of claim 17, wherein said network comprises a spanning tree and wherein said system further comprises a logger node within said spanning tree for logging said message to persistent storage during routing of said message to said multiple clients of said network.

22. The system of claim 17, wherein said means for routing comprises means for employing said logger node to log said message to persistent storage to ensure a uniform delivery quality of service of said message to said multiple clients of said network notwithstanding failure of one or more routers or links within said network.

23. The system of claim 17, wherein said network comprises a spanning tree having a plurality of routers, and further comprising means for detecting failure of a router within said tree before completing routing of said message to said multiple clients of said network, and means for reconfiguring said tree to replace said failed router with a new router, and means for automatically generating a request for retransmission of said message.

24. The system of claim 23, further comprising means for logging said message within persistent storage of said network and for issuing a logging acknowledgment confirming storage of said message to at least one router of said tree through which said message is routed to said multiple clients.

25. The system of claim 24, wherein said means for automatically generating a request for retransmission of said message comprises means for detecting a logging number associated with said message stored at one or more child routers of said new router.

26. The system of claim 17, wherein said means for routing further comprises means for determining within said network whether said message comprises a duplicate message to said multiple clients of said network, and if so, for aborting said duplicate message such that said message is delivered to said multiple clients at most once.

27. The system of claim 17, further comprising means for automatically informing a sender of said message when said message has not been received by the network to allow the sender to retransmit said message to the network for routing to said multiple clients of said network so that said message is delivered at least once to said multiple clients.