Application-level multicast (ALM) communications replicate packets on host level to deliver them from a single source to multiple clients, so that it can efficiently realize a variety of network applications using moving pictures such as video conferences, distance learning, and video-on-demands. In this paper, we propose the CT+ (compact tree plus) algorithm for finding a better ALM routing tree in terms of delay minimization between hosts. CT+ consists of a tree construction stage from the existing CT algorithm, and a newly added iterative tree improvement stage. Then, we define the extended ALM routing problem and its heuristic algorithm ExCT+, to optimize the effectiveness of the multihome network in ALM communications by selecting multihomed hosts and connections in the ALM routing tree simultaneously. For their evaluations, we construct a network simulation model named MINET (multiple-ISP network simulator), where the topology is composed of multiple ISP backbone networks with IX connections, and the network traffic is generated by following the M/M/1 queuing process. The simulation results using MINET verify the effectiveness of our algorithms.
en-copyright= kn-copyright= en-aut-name=FunabikiNobuo en-aut-sei=Funabiki en-aut-mei=Nobuo kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=1 ORCID= en-aut-name=IsogaiMegumi en-aut-sei=Isogai en-aut-mei=Megumi kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=2 ORCID= en-aut-name=NakanishiToru en-aut-sei=Nakanishi en-aut-mei=Toru kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=3 ORCID= en-aut-name=HigashinoTeruo en-aut-sei=Higashino en-aut-mei=Teruo kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=4 ORCID= affil-num=1 en-affil= kn-affil=Okayama University affil-num=2 en-affil= kn-affil=Okayama University affil-num=3 en-affil= kn-affil=Okayama University affil-num=4 en-affil= kn-affil=Osaka University, Osaka en-keyword=multicast communication kn-keyword=multicast communication en-keyword=queueing theory kn-keyword=queueing theory en-keyword=telecommunication network routing kn-keyword=telecommunication network routing END start-ver=1.4 cd-journal=joma no-vol=4 cd-vols= no-issue= article-no= start-page=2769 end-page=2774 dt-received= dt-revised= dt-accepted= dt-pub-year=2001 dt-pub=200110 dt-online= en-article= kn-article= en-subject= kn-subject= en-title= kn-title=A minimal-state processing search algorithm for satisfiability problems en-subtitle= kn-subtitle= en-abstract= kn-abstract=The satisfiability problem (SAT) is a typical NP-complete problem where a wide range of applications has been studied. Given a set of variables U and a set of clauses C, the goal of SAT is to find a truth assignment to variables in U such that every clause in C is satisfied if it exits, or to derive the infeasibility otherwise. This paper presents an approximation algorithm, called a minimal-state processing search algorithm for SAT (MIPS-SAT). MIPS-SAT repeatedly transits minimal states in terms of the cost function for searching a solution through a construction stage and a refinement stage. The first stage greedily generates an initial state composed of as many satisfied clauses as possible. The second stage iteratively seeks a solution while keeping state minimality. The performance of MIPS-SAT is verified through solving DIMACS benchmark instances
en-copyright= kn-copyright= en-aut-name=FunabikiNobuo en-aut-sei=Funabiki en-aut-mei=Nobuo kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=1 ORCID= en-aut-name=YokohiraTokumi en-aut-sei=Yokohira en-aut-mei=Tokumi kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=2 ORCID= en-aut-name=NakanishiToru en-aut-sei=Nakanishi en-aut-mei=Toru kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=3 ORCID= en-aut-name=TajimaShigeto en-aut-sei=Tajima en-aut-mei=Shigeto kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=4 ORCID= en-aut-name=HigashinoTeruo en-aut-sei=Higashino en-aut-mei=Teruo kn-aut-name= kn-aut-sei= kn-aut-mei= aut-affil-num=5 ORCID= affil-num=1 en-affil= kn-affil=Okayama University affil-num=2 en-affil= kn-affil=Okayama University affil-num=3 en-affil= kn-affil=Okayama University affil-num=4 en-affil= kn-affil=Osaka University affil-num=5 en-affil= kn-affil=Osaka University, Osaka en-keyword=SAT kn-keyword=SAT en-keyword=heuristic algorithm kn-keyword=heuristic algorithm en-keyword=optimization kn-keyword=optimization en-keyword=DIMACS kn-keyword=DIMACS en-keyword= MIPS_SAT. kn-keyword= MIPS_SAT. END start-ver=1.4 cd-journal=joma no-vol=35 cd-vols= no-issue=1-2 article-no= start-page=207 end-page=212 dt-received= dt-revised= dt-accepted= dt-pub-year=2001 dt-pub=20010327 dt-online= en-article= kn-article= en-subject= kn-subject= en-title= kn-title=A Group Signature Scheme with Easy Membership Canceling en-subtitle= kn-subtitle= en-abstract= kn-abstract=In the group signature scheme with a trusted party, a verifier can determine whether or not a signature is made by a member of the group, but cannot identify the member who signed the signature. In case of dispute later on, the signer can be identified by the trusted party. However, for efficient group signature schemes proposed so far, removing a member from the group can be not efficiently performed. In this paper, a group signature scheme with an easy membership canceling is proposed. By sending a request to use a resource together with the group signature on it to the manager of the resource, the manager can control anonymous accesses to the resource. In such an application, the proposed group signature scheme is suitable for canceling of the access privilege. en-copyright= kn-copyright= en-aut-name=NakanishiToru en-aut-sei=Nakanishi en-aut-mei=Toru kn-aut-name=中西透 kn-aut-sei=中西 kn-aut-mei=透 aut-affil-num=1 ORCID= en-aut-name= en-aut-sei= en-aut-mei= kn-aut-name=FujiwaraToru kn-aut-sei=Fujiwara kn-aut-mei=Toru aut-affil-num=2 ORCID= affil-num=1 en-affil= kn-affil=Department of Communication Network Engineering affil-num=2 en-affil= kn-affil=Department of Informatics and Mathematical Science, Osaka University END