The Experts below are selected from a list of 33 Experts worldwide ranked by ideXlab platform
Guy Kortsarz - One of the best experts on this subject based on the ideXlab platform.
-
a combinatorial logarithmic approximation algorithm for the Directed telephone Broadcast problem
SIAM Journal on Computing, 2005Co-Authors: Michael Elkin, Guy KortsarzAbstract:Consider a synchronous network of processors, modeled by Directed or unDirected graph $G = (V,E)$, in which in each round every processor is allowed to choose one of its neighbors and to send a message to this neighbor. Given a processor $s \in V$ and a subset $T \subseteq V$ of processors, the telephone multicast problem requires computing the shortest schedule (in terms of the number of rounds) that delivers a message from $s$ to all the processors of $T$. The particular case $T = V$ is called the telephone Broadcast problem. These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the unDirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the Directed variants of these problems is an open problem, posed by Ravi in [Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, (FOCS '94), 1994, pp. 202-213]. We devise a combinatorial logarithmic approximation algorithm for these problems that applies also for the Directed Broadcast problem. Our algorithm has significantly smaller running time and seems to reveal more information about the combinatorial structure of the solution than the previous algorithms that are based on linear programming. We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the unDirected (resp., Directed) Broadcast problem we show that it is NP-hard (resp., impossible unless $NP \subseteq DTIME(n^{O(\log n)})$) to approximate it within a ratio of $3 - \epsilon$ for any $\epsilon > 0$ (resp., $\Omega(\sqrt{\log n})$).
-
combinatorial logarithmic approximation algorithm for Directed telephone Broadcast problem
Symposium on the Theory of Computing, 2002Co-Authors: Michael Elkin, Guy KortsarzAbstract:(MATH) Consider a synchronous network of processors, modeled by Directed or unDirected graph G = (V,E), in which on each round every processor is allowed to choose one of its neighbors and to send him a message. Given a processor s e V, and a subset T ⊆ V of processors, the telephone multicast problem requires to compute the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of T. The particular case T = V is called telephone Broadcast problem.These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the unDirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the Directed variants of these problems is anopen problem, posed in [15].We devise a combinatorial logarithmic approximation algorithm for these problems, that applies also for the Directed Broadcast problem. Our algorithm has significantly smaller running time, and seems to reveal more information about the combinatorial structure of the solution, than the previous algorithms, that are based on linear programming.(MATH) We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the unDirected (resp., Directed) Broadcast problem we show that it is NP-hard (resp., impossible unless $NP ⊇ DTIME(nO(log n))) to approximate it within a ratio of 3 —e for any e ρ 0 (resp., ω(\sqrt log n)).Finally, we study the radio Broadcast problem. Its setting is similar to the telephone Broadcast problem, but in every round every processor may either send a message to all its neighbors or may not send it at all. A processor is informed in a certain round if and only if it receives a message from precisely one neighbor.(MATH) This problem was known to admit O(log2 n)-approximation algorithm, but no hardness of approximation was known. In this paper we show that the problem is ω(log n)-inapproximable unless NP ⊆ BPTIME(nlog log n}).
Michael Elkin - One of the best experts on this subject based on the ideXlab platform.
-
a combinatorial logarithmic approximation algorithm for the Directed telephone Broadcast problem
SIAM Journal on Computing, 2005Co-Authors: Michael Elkin, Guy KortsarzAbstract:Consider a synchronous network of processors, modeled by Directed or unDirected graph $G = (V,E)$, in which in each round every processor is allowed to choose one of its neighbors and to send a message to this neighbor. Given a processor $s \in V$ and a subset $T \subseteq V$ of processors, the telephone multicast problem requires computing the shortest schedule (in terms of the number of rounds) that delivers a message from $s$ to all the processors of $T$. The particular case $T = V$ is called the telephone Broadcast problem. These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the unDirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the Directed variants of these problems is an open problem, posed by Ravi in [Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, (FOCS '94), 1994, pp. 202-213]. We devise a combinatorial logarithmic approximation algorithm for these problems that applies also for the Directed Broadcast problem. Our algorithm has significantly smaller running time and seems to reveal more information about the combinatorial structure of the solution than the previous algorithms that are based on linear programming. We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the unDirected (resp., Directed) Broadcast problem we show that it is NP-hard (resp., impossible unless $NP \subseteq DTIME(n^{O(\log n)})$) to approximate it within a ratio of $3 - \epsilon$ for any $\epsilon > 0$ (resp., $\Omega(\sqrt{\log n})$).
-
combinatorial logarithmic approximation algorithm for Directed telephone Broadcast problem
Symposium on the Theory of Computing, 2002Co-Authors: Michael Elkin, Guy KortsarzAbstract:(MATH) Consider a synchronous network of processors, modeled by Directed or unDirected graph G = (V,E), in which on each round every processor is allowed to choose one of its neighbors and to send him a message. Given a processor s e V, and a subset T ⊆ V of processors, the telephone multicast problem requires to compute the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of T. The particular case T = V is called telephone Broadcast problem.These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the unDirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the Directed variants of these problems is anopen problem, posed in [15].We devise a combinatorial logarithmic approximation algorithm for these problems, that applies also for the Directed Broadcast problem. Our algorithm has significantly smaller running time, and seems to reveal more information about the combinatorial structure of the solution, than the previous algorithms, that are based on linear programming.(MATH) We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the unDirected (resp., Directed) Broadcast problem we show that it is NP-hard (resp., impossible unless $NP ⊇ DTIME(nO(log n))) to approximate it within a ratio of 3 —e for any e ρ 0 (resp., ω(\sqrt log n)).Finally, we study the radio Broadcast problem. Its setting is similar to the telephone Broadcast problem, but in every round every processor may either send a message to all its neighbors or may not send it at all. A processor is informed in a certain round if and only if it receives a message from precisely one neighbor.(MATH) This problem was known to admit O(log2 n)-approximation algorithm, but no hardness of approximation was known. In this paper we show that the problem is ω(log n)-inapproximable unless NP ⊆ BPTIME(nlog log n}).
Joseph Francis Dries - One of the best experts on this subject based on the ideXlab platform.
-
The Concise Guide to Enterprise Internetworking and Security
2000Co-Authors: Kyle Cassidy, Joseph Francis DriesAbstract:Introduction. About Security. Layout of This Book. Where to Go for More Information. 1. TCP/IP and Related Protocols. How Data Travels Across Networks. The Monolithic Versus Layered Method of ApplicationDesign. The OSIModel. The Physical Layer. The Data Link Layer. The Network Layer. The Transport Layer. The Session Layer. The Presentation Layer. The Application Layer. TCP/IP and the Internet Layer Model. Mapping TCP/IP to the OSIModel. The Basics of Layer. Address Resolution Protocol. Connection Versus Connectionless Communication. TCP/IP. Making TCPConnections. IPAddressing. IPAddress Classes. Routing. User Datagram Protocol. IPPacket Headers. Telnet. HTTP. SMTP. FTP. DNS. Internet Control Message Protocol (ICMP). Ping. Internet Protocol Version 6 (IPv6) and ICMPv6. 2. Understanding WAN Bandwidth Delivery. Introduction to Bandwidth Delivery: How the Computer Crashed into the Telephone. Packet Switched Versus Circuit Switched Networks. The Telco Engineers Versus the Network Engineers. Analog Modems. Hierarchy of Dedicated Digital Services. Physical Properties. Signal Encoding. DS0: The One True Standard. DS1: the Ever Popular. The T1 Frame. Fractional. T3. Fractional. SONET. ISDN. Basic Rate Interface (BRI). Primary Rate Interface (PRI). ISDN Layer 1-Physical. ISDN Layer 2-Data Link. ISDN Layer 3-Network. Digital Subscriber Line (XDSL, aDSL, sDSL). ADSL. R-ADSL. HDSL. IDSL. VDSL. SDSL. Splitterless DSL or DSL-Lite. Loading Coils. Cable Modems. Shared Network Technologies. More on Sharing. Frame Relay. Circuit Switched Versus Packet Switched. Advantages of Frame Relay. Components of Frame Relay. Congestion and Delay. Asynchronous Transfer Mode (ATM). It's All About Timing. Mitosis. Why 53 Octets? ATM OSI Layers. ATM Adaptation Layers. Guaranteed Service Levels. Wireless. Hardware Requirements for Different Networks. 3. Security Concepts. Who Is Threatening Your Data? Common Types of Attacks. Web Defacement. Unsolicited Commercial Email (UCE or Spam). Spoofing. Denial of Service (DoS). Important Security Terminology. Authentication. Authorization. Integrity. Encryption. Of Public Keys and Private Washrooms. X.509 Certificates. Pretty Good Privacy (PGP) Keys. Public Key Infrastructure (PKI). Security Hardware. Token-Based Cards. Smart Cards. Security Through Obscurity. World View Versus Internal View. Different Layers of Security. No Security. Hardened Security. Firewalls. Demilitarized Zone. Intrusion Detection Systems. Different Kinds of Access Control. Packet Screening. Circuit Proxies. Application Gateways. Stateful Inspection. Network Address Translation. 4. Defining Connection Requirements. Getting an Idea of What Your Users Need. Internet Applications Provided to the Internet. Sizing Your Internet Connection. Buying the Skills. Hiring the Skills. Earning the Skills. Bandwidth Doesn't Always Mean Performance. Criticality of Internet Connection. Hosting All Servers On-Site. Critical Outbound Access, No Critical On-Site Servers. Bandwidth-on-Demand: Out of Speed. Additional Services. Virtual Private Networks. Remote Access. Multimedia, Multicasting, and the MBONE. Security. Cost. Customer Premises Equipment. Firewalls and Servers. Where to Cut Corners. Reiteration Is Your Constant Companion. Connection Requirements Checklist. 5. Choosing an ISP. Selecting the Right ISP Is a Critical Decision. NSP or ISP? Network Access Point (NAP). Metropolitan Area Exchange (MAE). The Tiers of Babel. Cost. Paying by Bandwidth. Paying by Usage. Extras. Reimbursements for Network Downtime. Reliability/Reputation. Peer Survey. Capacity (Can Your ISP Meet Your Needs?). Installation and Setup Services ISPs Offer. Bandwidth Options. Web Hosting. Mail Hosting. Knowledge Services (Help Desk/Consulting). Managing Equipment Lease. IP Address Blocks. Co-locate: Your Equipment, the ISP's Building. Co-Location Considerations. Extended Protocols and Services. Provisioning a WAN. Customer Premises Equipment. Managed Services. Managing Your Router. Managing Your Firewall. Managing VPN Connectivity. Offering Proxy Services. Domain Name Registration. DNS Mail Exchanger Records. 6. Consulting, Consultants, and Contractors. Consultants, Contractors, and Projects. Can You Do It All Yourself? From the Inside. Before You Hire a Consultant. Before You Hire a Contractor. What Tasks Should You Farm Out? Questions You Should Ask Your Hired Help. Bonding and Insurance. The Request For Proposal. Agreeing Parties. Stated Objectives. Deliverables. Scope of Services. Risks. Requirements. Coordinators. Issues and Change Management. Timeline and Costs. Additional Costs. Defining a Statement of Work. Segment the Project into Stages. Information Collection. Analysis and Evaluation. Recommendation. Implementation. Acceptance and Transition. 7. Design Considerations. Before Building Your Network. Getting Your Service from the Wall Through Hall. Terminating the Telecom Demarcation. Wiring Contractors. Configuring Clients for a New Connection. Proxy Configuration. IP Addressing. Internet Software. Standard Build Process. Defining IPArchitecture. Multi-Protocol Network Requirements. Tunneling of Protocols Within IP. Tunneling IPv6 in IPv4. Availability, Capacity, and Reliability. Bandwidth, Latency, and Throughput. Backup Circuits. On-Demand Circuits. Remote Access Policy. Doing Away with Dialups. 8. Assessing Your Security Needs. Build an Adaptable Infrastructure. The Tao of Security: Simplicity. Service Assessment. Serving the World. Services Allowed from the Internet. The Special Case of FTP. Rules, Rulesets, and Rulebases. Rule Order. Performance-Tuning Your Firewall. Turning Security Policy into Security. Security Policy. Default Stance. Security Architecture. Security Architecture to Rulebase. Change Management. Harden All Your Servers. Drop Source Routed Traffic. Drop Directed Broadcast Traffic. Lock Down Your DNS Servers. Disable Relaying and Other Information Features on Your SMTP Server. Sample Prototype Designs. Packet Filter Router Only. Packet Filter Router with a DMZ. Router/Firewall and DMZ Revisited with VPN. 9. Getting Connected. Equipment Selection. Router Selection. CSU/DSU Selection. Staging the Hardware. Setting Up the Hardware: Out of the Box and Onto the Wall. Connect and Configure the CSU/DSU. B8ZS. Connect and Configure the Router. Burn In. 10. Implementing Security. Setting Proper Expectations. Hardening Systems. Windows NT 4.0. Windows 2000 Server. Lock Down Your DNS Server. Application-Specific Hardening. UNIX/Linux Systems. Tweak Your Network Configurations for Security. Remote Log Server. UNIX/Linux. Windows NT and 2000. EventLogs. Sample Packet Filter Router Only. Sample Packet Filter Router with a DMZ. Sample Packet Filter Router with a Firewall and DMZ. Minimal Router Filtering. Starting Free and Clear. Allow Internal Network Traffic Outbound to the Internet. Protect the Firewall. Allow Only Internal Admin Access to the Firewall. Drop Traffic You Do Not Want Logged. Services Provided to the Internet. Drop DMZ Initiated Traffic. Default Policy of Drop Everything. Sample Packet Filter Router with a Firewall, DMZ, and VPN Security Gateway. Bringing It All Together. Check Point FireWall-1 on Windows NT. Linux 2.2 and ipchains. OpenBSD 2.7 and IP Filter. 11. Testing and Validation. Is Your Network Working Properly? Assembling the Tools. Software Utilities. Hardware Sniffers. Network Analyzers/Protocol Analyzers. Testing Your Routing. Using ARP. Default Route. Testing Your Required Services. Testing Your Exposed Services. Testing Your Security. 12. Managing Your Internet Connection. Evaluating New Services. Sign Up for BUGTRAQ. Sign Up for NTBUGTRAQ. Checking for Security Breaches. Periodic Vulnerability Assessment. Tools for Simple Intrusion Detection. Monitoring and Baselining. What to Baseline. How Long Should Baselining Last? Peaks Versus Averages. Identify the Sources of Peaks. Log Monitoring. Monitoring Usage. Planning for the Future. What's Going to Break First? Appraising New Technologies. 13. Moving to a New ISP. Equipment Return. IPAddressing-The Return of Leased Numbers. DNS Modifications. New Equipment Purchases. Transition Period. Security Mail Servers. Upgrades. Index.
P Rogers - One of the best experts on this subject based on the ideXlab platform.
-
Directed Broadcast a mac level primitive for robust network Broadcast
Wireless and Mobile Computing Networking and Communications, 2005Co-Authors: P Rogers, Nael AbughazalehAbstract:Network wide Broadcast (NWB) is a common and important operation in mobile ad hoc networks (MANETs). NWBs are used to propagate routing requests and/or state in routing protocols as well as application data in group communication protocols. NWB rely on MAC level Broadcast which is unreliable. In the presence of shadowing or collisions, this leads to loss of coverage, especially in low density networks or for optimized NWB algorithms with limited redundancy. In this work, we propose a new MAC level primitive, Directed Broadcast, which significantly improves the reliability of link level Broadcast. In particular, Directed Broadcast is especially suited for optimized NWB algorithms that build a virtual backbone because it allows full reliability for the messages as they cross the backbone. We show that using Directed Broadcast can significantly improve the reliability of NWB operation.
-
WiMob (3) - Directed Broadcast: a MAC level primitive for robust network Broadcast
WiMob'2005) IEEE International Conference on Wireless And Mobile Computing Networking And Communications 2005., 1Co-Authors: P Rogers, Nael Abu-ghazalehAbstract:Network wide Broadcast (NWB) is a common and important operation in mobile ad hoc networks (MANETs). NWBs are used to propagate routing requests and/or state in routing protocols as well as application data in group communication protocols. NWB rely on MAC level Broadcast which is unreliable. In the presence of shadowing or collisions, this leads to loss of coverage, especially in low density networks or for optimized NWB algorithms with limited redundancy. In this work, we propose a new MAC level primitive, Directed Broadcast, which significantly improves the reliability of link level Broadcast. In particular, Directed Broadcast is especially suited for optimized NWB algorithms that build a virtual backbone because it allows full reliability for the messages as they cross the backbone. We show that using Directed Broadcast can significantly improve the reliability of NWB operation.
David Leon Clark - One of the best experts on this subject based on the ideXlab platform.
-
Enterprise Security: The Manager's Defense Guide
2002Co-Authors: David Leon ClarkAbstract:Preface. I. THE FORGING OF A NEW ECONOMY. 1. What is E-Business? The E-Business Sweepstakes. Caesars of E-Business: An Embattled Business Culture. The Lure of Overnight Successes. Crossing the Digital Chasm. The Sobering Reality. Real-World Examples. E-Business: The Shaping and Dynamics of a New Economy. The E-Business Supply Chain. Related E-Business Trends. Summary. 2. What Is E-Security? E-Security at Your Service. Demands on Traditional IT Security: A Changing of the Guard. Principles of E-Security. Risk Management in the New Economy. How E-Security Enables E-Business. The E-Security Dilemma: Open Access versus Asset Protection. 3. The Malicious Opponents of E-Business. The Lure of Hacking. Hackers versus Crackers. Hacker Groups. Why Hackers Love to Target Microsoft. Meeting the Hacker Threat. National Infrastructure Protection Center. Central Intelligence Agency. Other White Hats. II. PROTECTING INFORMATION ASSETS IN AN OPEN SOCIETY. 4. A New Theater of Battle. From the Demilitarized Zone and the Perimeter to Guerilla Warfare. The Triumph of Intranets, Extranets, and Virtual Private Networks. The Vanishing World of Controlled, or Closed, Access. The Impact of Open Access. The Correlation between Open Access and Asset Protection. The Role of Authentication and Privacy in the New Economy. Summary. 5. Reempowering Information Technology in the New Arms Race. The Failings of the Old Paradigm. Infiltration of Rogue Applets. Human Error and Omission. Ongoing Change in the Enterprise Network. Deploying and Maintaining Complex Layer Client/Server Software. Shortage of Human Capital. Rigidity of Enterprise Security Policy. Tools for Rearming the IT Manager. Guidelines for E-Security. Enterprise Security Policy. Summary. III. WAGING WAR FOR CONTROL OF CYBERSPACE. 6. Attacks by Syntax: Hacker and Cracker Tools. Inherent Shortcomings of TCP/IP. Standard "Ports" of Call. TCP/IP Implementation Weaknesses. IP Spoofing. Distributed Denial-of-Service Attacks and Tools. Trin00. Tribe Flood Network. Tribe Flood Network 2000. Stacheldraht. ICMP Directed Broadcast, or Smurf Bandwidth Attack. Backdoor Programs and Trojan Horses. Backdoor Program Functions. Examples of Backdoor Programs. Summary. 7. Attacks by Automated Command Sequences. Script Attacks. The Next Generation of E-Mail Attacks. The Bubble Boy Virus. Mainstream JavaScript Attacks. Attacks through Remote Procedure Call Services. Brown Orifice. Summary and Recommendations. 8. Countermeasures and Attack Prevention. Surviving an Attack. Formulate an Emergency Response Plan and an Incident Response Team. Obtain Outside Assistance. Contact Law Enforcement Authorities. Use Intrusion Detection System Software. Countering an Attack. Disconnect Compromised Host/System from Your Network. Copy an Image of the Compromised System(s). Analyze the Intrusion. Recognizing What the Intruder Leaves Behind. 9. Denial-of-Service Attacks. Effects of DoS and DDoS Attacks. General Computing Resources. High-Performance Firewall. Network Bandwidth. Handling a SYN Flood DDoS Attack. Countermeasures. Precautions. Handling a Bandwidth DDoS Attack. Guarding against Being an Accomplice Network. Guarding against Becoming an Intermediary Network. Guarding against Being a Victim. Handling a UDP Flood Bomb. Using an IDS. Recovering from a DDoS Attack. 10. Creating a Functional Model for E-Security. Developing a Blueprint for E-Security. Understanding Business Objectives. Honing in on Your IT Security Policy. Making Good on IT Security's Best Practices. The IT Security Functional Model. Deploying Effective E-Security Architecture: Hardening the Network's Infrastructure. Hardening Your Router. Hardening Your Operating Systems. Summary. 11. Building a Security Architecture. Firewall Architecture Deployment, Controls, and Administration. Types of Firewalls. Hardening Firewalls. Remote-Access Architecture. Encryption Options for Administrators. Securing Remote-Administration Pipes for Administrators. Remote-Access Architecture/Solutions for Users. Vulnerability Assessment Architecture/Solutions. Network-Based Assessment Architecture. Host Vulnerability Assessment. Intrusion Detection Architecture. Network-Based IDS Architecture. Host-Based IDS Solutions. IV. ACTIVE DEFENSE MECHANISMS AND RISK MANAGEMENT. 12. Vulnerability Management. Types of Vulnerabilities. Managing IT Systems Vulnerabilities. Conducting Vulnerability Analysis. Network-Based Vulnerability Analysis. Host-Based Vulnerability Analysis. 13. Risk Management. The Role of Assessment in Risk Management. The Process of Risk Management. Defining the System Boundaries. Threat Analysis. Impact Analysis. Risk Determination. Summary. Appendix A: SANs/fbi Top 20 Internet Security Vulnerabilities. Appendix B: Sample CERT/Coordination Center Incident Response Form. Appendix C: Windows 2000 Security/Hardening Plan. Appendix D: Denial-of-Service Attacks. Glossary. Bibliography. Index. 020171972XT08282002