Reliable synchronization apparatus and method within a multicast and broadcast service zone

• US 8,391,198 B2
• Filed: 03/05/2010
• Issued: 03/05/2013
• Est. Priority Date: 11/13/2009
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Kuo, Wei-Han, Liu, Chia-Lung, Wang, Jui-Tang, Yang, Jen-Shun
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): HAMPTON, TARELL A
• Application Number:
  US12/717,958
• Publication Number:
  US 20110116434A1
• Time in Patent Office: 1,096 Days
• Field of Search: 370/312, 370/503, 370/507, 370/509, 709/248
• US Class Current: 370/312
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others

Abstract

A reliable synchronization apparatus and method within a multicast and broadcast service (MBS) zone having m sync executers (SEs) belonging to n retransmission zones is provided. Each retransmission zone has a selected leader SE and other member SEs. The apparatus comprises a sync controller and the n selected leader SEs. When the Sync controller multicasts a sync ruler to all SEs in a retransmission zone, the leader SE that loses the Sync ruler sends a NACK message to request the sync controller to retransmit the sync ruler. An election is triggered for updating leader information and announcing election to all SEs. The member SE that loses the sync ruler sends a NACK message to request its leader or the Sync controller to retransmit the sync ruler.

Claims

1. A reliable synchronization apparatus within a multicast and broadcast service (MBS) zone, said MBS zone having m sync executers (SEs) and said m SEs belonging to n retransmission zones respectively, m>

n≧

1, each retransmission zone having a selected leader SE and un-selected SEs being member SEs of the selected leader SE, said apparatus comprising;

n selected leader SEs; and

a sync controller, wherein in each retransmission zone, when said sync controller multicasts a sync ruler to all SEs in said retransmission zone, the leader SE not having received said sync ruler unicasts a NACK message to said sync controller to request retransmitting said sync ruler, said sync controller retransmits said sync ruler and triggers an election of a new leader SE to update leader SE information and multicasts new leader SE information to all SEs in said retransmission zone, and each member SE not having received said sync ruler unicasts a NACK message to the leader SE of said retransmission zone or said sync controller to request retransmitting said sync ruler.

2. The apparatus as claimed in claim 1, wherein for each retransmission zone of said n retransmission zones, said sync controller further includes a leader priority list to record priority information of selecting the leader SE in said retransmission zone.

3. The apparatus as claimed in claim 1, wherein said sync controller multicasts through a core network a sync ruler in every other recovery period of sync ruler to all SEs of said retransmission zone.

4. The apparatus as claimed in claim 3, wherein said core network is a wireless network.

5. The apparatus as claimed in claim 1, wherein after said election generates an election result, said sync controller multicasts said election result to all SEs of said retransmission zone and updates leader SE information.

6. The apparatus as claimed in claim 3, wherein said sync controller keeps said sync ruler during said recovery period of said sync ruler.

7. The apparatus as claimed in claim 1, wherein each member SE further includes a timer and sets said timer when receiving an election message multicast by said sync controller, and when said timer expires, said member SE unicasts current leader SE information to said sync controller.

8. The apparatus as claimed in claim 1, wherein if said member SE not having received said sync ruler has not received said sync ruler after a recovery period of said sync ruler expires, the member SE requests said leader SE to retransmit said sync ruler.

9. The apparatus as claimed in claim 1, wherein if said member SE not having received said sync ruler has not received said sync ruler after a recovery period of said sync ruler expires and before a MAX_REQUEST_DELAY_BOUND expires, the member SE requests said leader SE to retransmit said sync ruler.

10. The apparatus as claimed in claim 1, wherein said sync controller generates an election result containing the new leader SE information according to an election algorithm.

11. A reliable synchronization method within a multicast and broadcast service (MBS) zone, said MBS zone having m sync executers (SEs) and said m SEs belonging to n retransmission zones respectively, m>

n≧

1, said method comprising;

pre-selecting a leader SE in each retransmission zone of said n retransmission zones, un-selected SEs in said retransmission zone being corresponding member SEs of said leader SE;

through a sync controller, multicasting a sync ruler to all SEs of each retransmission zone of said n retransmission zones;

unicasting a NACK message from the leader SE not having received said sync ruler to said sync controller to request retransmitting said sync ruler, said sync controller retransmitting said sync ruler and triggering an election of a new leader SE to update leader SE information and multicasting new leader SE information to all SEs in said retransmission zone; and

unicasting a NACK message from each of member SEs not having received said sync ruler to the leader SE of said retransmission zone or said sync controller to request retransmitting said sync ruler.

12. The method as claimed in claim 11, wherein said sync controller generates an election result containing the new leader SE information according to one of either distributed or centralized election algorithm.

13. The method as claimed in claim 11, wherein if said leader SE of said retransmission zone has successfully received said sync ruler multicast by said sync controller, said leader SE further executes:

checking whether a retransmission request is received from a member SE in a recovery period of said sync ruler; and

if so, transmitting said sync ruler to said member SE;

repeating said operation until no further retransmission request is received in said recovery period of said sync ruler.

14. The method as claimed in claim 11, wherein if a member SE of said retransmission zone has successfully received said sync ruler multicast by said sync controller, said member SE further executes:

checking whether a retransmission request is received from other member SEs having lost said sync ruler in a recovery period of said sync ruler; and

if so, said member SE transmitting said sync ruler and current leader SE information to the member SE requesting retransmission; and

updating the leader SE information.

15. The method as claimed in claim 14, wherein if no retransmission request from other member SEs having lost said sync ruler is received, and if the leader SE of said retransmission zone is crashed or overloaded, said member SE receives a message of electing a new leader SE and an election result, and then updates the leader SE information.

16. The method as claimed in claim 11, wherein among all of said member SEs not having received said sync ruler, if a member SE has received said sync ruler after a recovery period of said sync ruler expires and before a MAX_REQUEST_DELAY_BOUND expires, said member SE further executes:

requesting its leader SE to retransmit said sync ruler after said recovery period of said sync ruler expires;

before said MAX_REQUEST_DELAY_BOUND expires, receiving said sync ruler; and

checking whether current leader SE information is received, and updating leader SE information if said current leader SE information is received.

17. The method as claimed in claim 11, wherein among all of said member SEs not having received said sync ruler, if a member SE has received said sync ruler after a MAX_REQUEST_DELAY_BOUND expires, said member SE further executes:

requesting its leader SE to retransmit said sync ruler;

requesting said sync controller to retransmit sync ruler after said MAX_REQUEST_DELAY_BOUND expires; and

receiving said sync ruler.

18. The method as claimed in claim 11, wherein among all of said member SEs not having received said sync ruler, if a first member SE receives a NACK message from a second member SE, said first member SE further executes:

checking whether to repeat obtaining said sync ruler; and

if so, returning said sync ruler and current leader SE information;

otherwise, returning current leader SE information.

19. The method as claimed in claim 11, wherein among all of said member SEs not having received said sync ruler, if a member SE has received current leader SE information before a MAX_REQUEST_DELAY_BOUND expires,

said member SE further executes:

checking whether to repeat obtaining said sync ruler; and

updating current leader SE information and requesting a new leader SE in the current leader SE information to retransmit said sync ruler if said sync ruler has not been received;

otherwise, updating current leader SE information.

20. The method as claimed in claim 11, wherein among all of said member SEs not having received said sync ruler, if a member SE has received current leader SE information after a MAX_REQUEST_DELAY_BOUND expires, said member SE updates current leader SE information.

21. The method as claimed in claim 11, wherein among all of said member SEs not having received said sync ruler, if a member SE has received a message of electing a new leader SE during a recovery period of said sync ruler, said member SE ignores said message.

22. The method as claimed in claim 11, wherein in the condition of a leader SE successfully receiving said sync ruler, each member SE of said leader SE not having received said sync ruler requests to said leader SE for retransmitting said sync ruler, and said leader SE retransmits said sync ruler to the member SE requesting retransmission.

23. The method as claimed in claim 11, wherein in the condition of a leader SE having lost said sync ruler, said leader SE loses leadership and unicasts said NACK message to said sync controller, and then said election is triggered and said sync controller generates and announces new leader SE information according to an election algorithm.

24. The method as claimed in claim 11, wherein in the condition of a leader SE having lost said sync ruler and in a crashed state, if a member SE has not received said sync ruler before a MAX_REQUEST_DELAY_BOUND expires, said member SE requests said sync controller for retransmitting said sync ruler, and said sync controller further executes:

retransmitting said sync ruler to said member SE; and

performing an election process of a new leader SE, and announcing new leader SE information.

25. The method as claimed in claim 12, wherein when said sync ruler uses said distributed election algorithm, each member SE in said retransmission zone has a fair opportunity to become the leader SE of said retransmission zone.

26. The method as claimed in claim 12, wherein when said sync ruler uses said centralized election algorithm, a leader priority list is used in generating a new leader SE.