Paper Info

Title | ||
---|---|---|

Broadcasting dependent data with minimized access latency in a multi-channel environment |

Abstract | ||
---|---|---|

Data broadcasting is an effective way to disseminate information to clients in wireless environment. We consider how to efficiently generate the broadcast schedule on multiple channels when the data set has a DAG access pattern. It is NP-complete to find an optimal broadcast schedule which not only minimizes the latency but is a topological ordering which preserves the data dependency. We rule out a condition for the input DAGs under which one can generate an optimal broadcast schedule in linear time and propose a linear time algorithm to generate the schedule under such a condition. For general DAGs, we provide three heuristics: the first one uses the overall access probability of each vertex; the second one considers the total access probability of the posterior vertices of a vertex; the third one combines the above two heuristics. We analyze these three heuristics and compare them through experiments. |

Year | DOI | Venue |
---|---|---|

2006 | 10.1145/1143549.1143711 | IWCMC |

Keywords | Field | DocType |

dag access pattern,total access probability,broadcast schedule,dependent data,overall access probability,multi-channel environment,general dags,input dags,access latency,data dependency,data broadcasting,optimal broadcast schedule,linear time,np hard,latency,dag,broadcasting | Broadcasting,Data dependency,Latency (engineering),Computer science,Topological sorting,Computer network,Communication channel,Theoretical computer science,Heuristics,Dissemination,Time complexity,Distributed computing | Conference |

ISBN | Citations | PageRank |

1-59593-306-9 | 2 | 0.39 |

References | Authors | |

13 | 2 |

Authors (2 rows)

Cited by (2 rows)

References (13 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Kun-Feng Lin | 1 | 14 | 1.26 |

Chuan-Ming Liu | 2 | 334 | 27.88 |